Hacker News Reader

Comment by cococonspirator | Hacker News Reader

You won’t necessarily be able to verify it works empirically, even if you can prove so analytically, because it would be a complexity bound that was broken. If I could crack RSA keys for a mere one million times the computational resources used to create them, that would be a groundbreaking result and I would have “broken RSA”, but _I_ still wouldn’t be able to crack any RSA keys at all.

View on HN

>If I could crack RSA keys for a mere one million times

You are off by many magnitudes. 1M is very little and equivalent computing power can be bought for a few tens of euros.

True, it could still be impossible to break RSA keys used in the wild with one normal PC. But still, you could factor smaller numbers faster than any other algorithm which would give you the confidence that it works.

> _I_ still wouldn’t be able to crack any RSA keys at all.

Everybody can crack RSA keys if the modulos is small enough. You just need to factor a number :)

There actually nice list of numbers to try: https://en.wikipedia.org/wiki/RSA_numbers

You can factor, e.g, RSA-100 on a normal PC with state of the art algorithms in reasonable time.

That said, I had some new insight into factoring, and I was only a mere factor of one million away from factoring industrial crytography, I'd maybe try to optimize it a bit more.

In short, no. There's a reason that General Number Sieve is only used for numbers bigger that 10^80 and Elliptic Curve Method (ECM) is used instead. If number is smaller, than you don't benefit from the better complexity. This invalidates your point, because it might happen that your hardware is fast enough to factor a number using ECM and not fast enough to do the same with GNFS. So practically speaking, you don't have any assurance that what you have is fast or slow. Of course, it might happen that you actually manage to factor some big numbers, in that case you have the empirical proof you sought.

I agree in principle. But I disagree that you cannot test GNFS on small numbers. You can do this, but you are right that you might have trouble to easily verify that it has a better asymtotic complexity than other algorithms.

Reply on news.ycombinator.com