Re:Math Advances Suggest RSA Encryption Could Fall Within 5 ...
by jaekwon on Saturday August 10, 2013 @02:10PM
(#6192038)
https://gist.github.com/jaekwon/6201493
edit: it doesn't work. :P It worked when e or d was set to 1. oops.
you might want to see if there's a bug in the main function.
Re:Math Advances Suggest RSA Encryption Could Fall Within 5 ...
by ColinWright on Saturday August 10, 2013 @02:15PM
(#6192053)
Indeed, but these are really small numbers. RSA only works with really BIG numbers, which is one reason people are starting to insist that PKC should use ECC.
Re:Math Advances Suggest RSA Encryption Could Fall Within 5 ...
by jaekwon on Saturday August 10, 2013 @02:29PM
(#6192106)
updated my comment.
The only thing I can think of is that discrete logs don't work that way.
while E^(e.log_E(M)) == E mod n, e.log_E(M) doesn't equal 1. And I'm not sure what /e means in the realm of exponents, besides *d, and I don't know how to find d without knowing M.
But these very simple calculations show that in at least some cases, being able to compute unrestricted discrete logs will break RSA, perhaps just not in general. Perhaps it's another case where the modulus and exponent need to have extra conditions.
Added in edit. Again.
We know that that equation has a solution, because M=E^d (mod n) where d is the private key. That would suggest we compute logs base E. Reworking the sums, and specifically using logs base E: Still just idly musing, but it seems right.