Hacker News Reader

Comment by ddoolin | Hacker News Reader

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?

View on HN

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.

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.

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?

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

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

Thanks, that was a truly good talk

Reply on news.ycombinator.com