3 ms·
The discrete logarithm is the inverse operation of exponentiation and modulo. Being able to find a discrete logarithm quickly would break RSA.
by Znafon 6y ago
The discrete logarithm is the inverse operation of exponentiation and modulo. Being able to find a discrete logarithm quickly would break RSA.
- plopilop 6y agoI don't think so. Computing the discrete log of g^x assumes g to be known. In RSA the ciphertext is c = m^e and by definition, m is unknown. The reverse operation of RSA is the modular e-th root, not the discrete log.
- archgoon 6y agoPick a base k. log_k(c) = e*log_k(m) log_k(c)*e^-1 = log_k(m) Raising k by both sides yields k^(log_k(c)*e^-1) => m
- deleted 6y ago[deleted]
- plopilop 6y agoI don't think this works mod N. Since N is not a prime, you have no guarantee that for k your base, c belongs to the multiplicative group generated by k. Take for instance N = 15, you can't find a log base 12 of 7, for instance (12 -> 9 -> 3 -> 6 -> 12). So you'd first need to find a fitting base, not sure how hard this is. It has been proven [0] that factoring is as hard as solving DLP, but RSA also relies on the modular e-th root hypothesis, which we don't know to be as hard or easier than factoring. In the end, because of [0] is you solve DLP you solve factoring yes, but we usually don't talk about DLP for RSA, even if as I said I was nitpicking. [0] https://www2.eecs.berkeley.edu/Pubs/TechRpts/1984/5973.html https://www2.eecs.berkeley.edu/Pubs/TechRpts/1984/5973.html
- deleted 6y ago[deleted]
- deleted 6y ago[deleted]
- vmilner 6y agoShor's algorithm does exactly that by using quantum computation to solve discrete logarithms.