News for hackers. Stuff that matters.
Re:Math Advances Suggest RSA Encryption Could Fall Within 5 ... by benmmurphy on Saturday August 10, 2013 @12:51PM (#6191714)
what base do you compute the logs when you do this attack? i assume in (mod n) rsa group there is no generator b that generates all of the numbers (mod n). and you could only recover the message M if you have M = b^x (mod n). so how do you choose b? or is this not a problem.
Re:Math Advances Suggest RSA Encryption Could Fall Within 5 ... by ColinWright on Saturday August 10, 2013 @01:01PM (#6191759)
Possibly it only works for some bases, and then possibly it only works for some n and e. I don't have time now to work through all the details, but my gut feeling is that for log(n) selection of bases, at least one will work for the calculation you need to perform. But I am not an expert, so my intuition is not to be trusted.

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.

  > ... you could only recover the message M
  > if you have M = b^x (mod n).
We know that that equation has a solution, because M=E^d (mod n) where d is the private key.

  > ... what base do you compute the logs when you
  > do this attack?
That would suggest we compute logs base E. Reworking the sums, and specifically using logs base E:

    E = M^e (mod n)
    log_E(E) = e.log_E(M)
    log_E(E)/e = log_E(M)
    1 / e = log_E(M)
    E^(1/e) = E^(log_E(M)) = M
Still just idly musing, but it seems right.
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.