Hacker News Reader

Comment by weavie | Hacker News Reader

So if decrypting an RSA encoded message just involves multiplying the message by itself x amount of times, couldn't you just do keep multiplying until the result message makes sense, then you have discovered x?

Sure in the example the key was so small it could only do one character at a time. With a larger key you wouldn't know the length of bytes to decode in one go. But that would only slow things down a bit.

There must be more to it than that?

View on HN

You could keep multiplying m by itself, sure, but in practice you're dealing with numbers so huge that it rapidly becomes impractical to test all values in the range m^2 to whatever (e.g. m^49863657239487123495780934672309687239458732946585601239587146245192587126978563425981758234729374837833000023013834769482349111943853593463798) before you finally stumble on the correct one.

Effort is better spent trying to factor the public modulus n which you already have. Because the private exponent(m^498636... above) can be derived from it.

If you could do a multiply in a nano-second, you could do about 3 x 10^16 multiplies in a year. Keys are about 10^300, so it would take 10^84 years.

Sort of.

In practice it's more complicated than that, but the numbers involved are HUGE. Doing the math with small examples always gives completely the wrong impression, like doing hill-climbing in 3D.

Yes I see.

So, I assume there must be a quicker way to work out x ^ n that incorporates wrapping than just doing x = x * x % y repetitively. Darn it, my maths is getting rusty in my old age.

There is a fast exponentiation that is effectively Russian Peasant Multiplication, and it works in time proportional to number of bits in the exponent. Look up "fast exponentiation" or similar.

Got it. This has been very enlightening. Thanks.

There is. x^n = (x^(n/2))^2 if n is even, (x^(n-1/2))^2 if n is odd, so it's possible to exponentiation in logarithmic time.

Reply on news.ycombinator.com