Live data from Hacker News

Very Basic Intro to Elliptic Curve Cryptography

qvault.io

21–23 of 23 posts

Re: Very Basic Intro to Elliptic Curve Cryptography

#21

Earlier quoted context omitted.

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

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

Re: Very Basic Intro to Elliptic Curve Cryptography

#22

Earlier quoted context omitted.

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

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 mo…

[deleted]

Re: Very Basic Intro to Elliptic Curve Cryptography

#23

Earlier quoted context omitted.

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

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 mo…

[deleted]
Post reply on HN