Very Basic Intro to Elliptic Curve Cryptography

Re:Very Basic Intro to Elliptic Curve Cryptography by plopilop on Wednesday July 22, 2020 @11:32AM (#23918084)

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.

[ Parent | on HN ]

Re:Very Basic Intro to Elliptic Curve Cryptography by archgoon on Wednesday July 22, 2020 @07:56PM (#23922826)

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

[ Parent | on HN ]

Re:Very Basic Intro to Elliptic Curve Cryptography by plopilop on Thursday July 23, 2020 @10:26AM (#23927684)

I 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

[ Parent | on HN ]