undefined | Better HN

0 pointsplopilop5y ago0 comments

Nitpicking, but RSA does not rely on the DLP, rather on factorisation and modular roots. I guess you meant Elgamal or Diffie-Hellman?

0 comments

The discrete logarithm is the inverse operation of exponentiation and modulo. Being able to find a discrete logarithm quickly would break RSA.

Shor's algorithm does exactly that by using quantum computation to solve discrete logarithms.

I 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.

Pick 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

j / k navigate · click thread line to collapse