3 ms·
> Diffie-Hellman is based on discrete logarithms, > but RSA is not. Well, sort of, but not entirely. Yes, the obvious way to break RSA is to factor the modu
by ColinWright 13y ago
> Diffie-Hellman is based on discrete logarithms,
> but RSA is not.
Well, sort of, but not entirely. Yes, the obvious way to break RSA is to factor the modulus, and then compute the private key from the public key.
But that's not the only thing.
You encrypt by raising the message M to the power of the public key e modulo the public modulus n.
E = M^e (mod n)
That means that
log_e(E) = M (mod n) [ This is wrong - see below ]
If you can compute logarithms base e modulo n then given the public information, you can recover M.
So unrestricted discrete logs let you break RSA.
Added in edit:
Sorry, I mis-spoke myself as I was (and still am) in a hurry. As benmmurphy correctly points out, this is wrong, but not in an unfixable way. In short:
(all done mod n)
E = M^e (mod n)
log(E) = e.log(M)
log(E)/e = log(M)
exp(log(E)/e) = exp(log(M)) = M
Again, unrestricted discrete log lets you break RSA.
PS: There's a non-zero chance I screwed up again - feel free to say so!
- benmmurphy 13y agothis doesn't look like log to me. i think the function you want is e'th root.
- barrkel 13y agon'th root of x = exp(log(x) / n)
- deleted 13y ago[deleted]
- benmmurphy 13y agowhat 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 agoPossibly 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 agohttps://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 agoIndeed, 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 agoupdated 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.
- pbsd 13y agoIf you can compute discrete logarithms modulo composite n, you can actually factor n. Suppose that n = p * q. The order of the multiplicative group of the integers modulo n is (p-1) * (q-1). Suppose that, given a randomly generated a, we can find a nontrivial x such that a^x = 1 (mod n). Then x divides the order of n, i.e. (p-1)*(q-1), and we can quickly extract p and q from there. Edit: Terminology correction. Thanks xyzzyz!
- xyzzyz 13y agoThe order of the ring of integers modulo n is (p-1)(q-1) You mean, the order of the multiplicative group. The order of the ring of integers modulo n is always n, regardless of n.
- djao 13y agoYou're assuming unrestricted discrete logarithms over a composite modulus. This is a much stronger assumption than discrete logarithms over prime moduli. Even if someone found a fast way to break discrete logarithms modulo primes, your assumption would still not automatically hold. Since cryptography uses discrete logarithms over prime moduli, the discrete logarithm problem that cryptographers are working on is not the same problem as the problem that they would need to solve in order to break RSA.
- ColinWright 13y agoAbsolutely, and that's why I say the unrestricted discrete log lets you break RSA. It's certainly not the special case that cryptographers are currently working on, but it's very much related. And equally, although the completely unrestricted version needed to break general RSA is very much out of reach at the moment, it's possible (although still incredibly unlikely) that a particular choice of parameters may be broken because we happen to find the right discrete log solution. These are not currently viable methods of attack, but speculating on them may lead to useful insights, and certainly discussing them can help non-experts gain insight.
- djao 13y agoThe only relation between the two problems is that they involve the same type of equation. The underlying number systems are totally different. There is no reason to expect the two problems to be of comparable difficulty. As an illustrative example, the equation for the RSA problem itself can be defined over prime fields, and it is trivially easy to solve in that setting. The same problem over a composite modulus is believed to be hard, and forms the basis for the RSA cryptosystem. Just because an equation can be solved over prime fields does not mean, at all, that it can be solved over composite moduli.
- ColinWright 13y agoI suspect we are arguing past each other, and if we were to sit down over coffee (or equivalent) in from of a whiteboard (or equivalent) then we would have a really useful and interesting conversation. Everything you say is right, but I believe there are more connections going on at a deeper level. This is my intuition speaking, and as a PhD in Combinatorics and Graph Theory who has dabbled for decades (literally - I started in 1967) in integer factorization and discrete logs, I've learned to listen to my intuition. It's sometimes wrong, and it may well be in this case, but I feel that the deeper structures in Z_{pq} and Z_p have a cross-fertilization that we may eventually find. I agree that these aren't the obvious things to be working on, and the more direct attacks - factorization for RSA and discrete logs in Z_p for DHMW - are just that, more direct, and will certainly be more fruitful in the short to medium term. It would be nice to make that real-life conversation happen. Feel free to email me? Details in my profile.