4 ms·

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

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.

ColinWright 13y ago
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.
- jaekwon 13y ago
  https://gist.github.com/jaekwon/6201493 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.
  - ColinWright 13y ago
    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.
    - jaekwon 13y ago
      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.

ColinWright 13y ago

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.

jaekwon 13y ago
https://gist.github.com/jaekwon/6201493 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.
- ColinWright 13y ago
  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.
  - jaekwon 13y ago
    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.