5 ms·

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 u

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?

dan-robertson 6y ago
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.
- pfortuny 6y ago
  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.
- wagslane 6y ago
  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?
hoppla 6y ago
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...
- ufo 6y ago
  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_-_201412272145_-_ecchacks_-_djb_-_tanja_lange https://media.ccc.de/v/31c3_-_6369_-_en_-_saal_1_-_201412272...
  - hoppla 6y ago
    Thanks, that was a truly good talk

dan-robertson 6y ago

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.

pfortuny 6y ago
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.
wagslane 6y ago
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?

hoppla 6y ago

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

ufo 6y ago
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_-_201412272145_-_ecchacks_-_djb_-_tanja_lange https://media.ccc.de/v/31c3_-_6369_-_en_-_saal_1_-_201412272...
- hoppla 6y ago
  Thanks, that was a truly good talk