Re:(Very) Basic Intro to Elliptic Curve Cryptography
by ddoolin on Sunday February 14, 2021 @02:08PM
(#26135140)
Cool intro, I had no idea about ECC. However something is a bit lost on me: if the number of hops is the "private key" in this scenario, couldn't you just hop until you've found the endpoint? What makes this particularly difficult?
[ Parent
| on HN ]
Re:(Very) Basic Intro to Elliptic Curve Cryptography
by dan-robertson on Sunday February 14, 2021 @02:15PM
(#26135222)
The number may be very large (think: much bigger than 2^64). The reason it’s possible to compute these in logarithmic time (ie linear in the number of bits of the key) is the same reason that it is possible to compute a^b (mod c) even when b is very large: there are operations in elliptic curves akin to multiplying and squaring so a^(2b_1 + b_2) = a^(b_2) (a^2)^(b_1) can have the cost of computing a^(b_1) (say b_1 is 0 or 1, so this is constant), the cost of a multiply (constant), the cost of a square (constant), and the cost of an exponentiation of a number with one less bit, hence by induction the cost is linear in the number of bits.
Re:(Very) Basic Intro to Elliptic Curve Cryptography
by pfortuny on Sunday February 14, 2021 @02:57PM
(#26135662)
And exponentiating is (relatively) easy beacuse
a^(xyz) = ((a^x)^y)^z
and as long as you know how to square, you can pretty much compute exponentials in log2(exponent) time.
Re:(Very) Basic Intro to Elliptic Curve Cryptography
by wagslane on Sunday February 14, 2021 @03:21PM
(#26135878)
Thanks for helping out with this explanation. I just updated the article and added an answer section briefly addressing this. Maybe check it out and let me know if you think the answer is sufficient?
Re:(Very) Basic Intro to Elliptic Curve Cryptography
by hoppla on Sunday February 14, 2021 @02:23PM
(#26135319)
I am also puzzled by this, and if the number is hops is so large that it’s unfeasible to enumerate, how does the key generator know many hops it should be...
Re:(Very) Basic Intro to Elliptic Curve Cryptography
by ufo on Sunday February 14, 2021 @02:36PM
(#26135454)
I remember watching a presentation by Tanja Lange and djb that explained that kind of thing very well. It starts with easy to visualize examples using "clock crypto" and then transitions to real ECC curves.
https://media.ccc.de/v/31c3_-_6369_-_en_-_saal_1_-_201412272...