<div dir="ltr"><div class="gmail_extra">I think I'm finally getting the basics of why we like elliptic curve crypto.  Here's my attempt to explain it in regular English.</div><div class="gmail_extra"><br></div><div class="gmail_extra">These are curves such that they fit into this form:</div><div class="gmail_extra"><br></div><div class="gmail_extra">    a @ b = Finv(F(a) + F(b))</div><div class="gmail_extra"><br></div><div class="gmail_extra">The @ is the group "addition" operator and the + is some group operation, likely addition or multiplication.  In the case of Edwards elliptic curves, F(a) is a line integral along a path on the unit sphere.</div><div class="gmail_extra"><br></div><div class="gmail_extra">These would all be trivially broken except:</div><div class="gmail_extra"><br></div><div class="gmail_extra">1) F(a) is a transcendental function, with no modular arithmetic equivalent</div><div class="gmail_extra">2) Finv(F(a) + F(b)) is algebraic</div><div class="gmail_extra"><br></div><div class="gmail_extra">This means we can easily compute the result, but not the magic in the middle, where we're doing addition or multiplication on the transcendental functions.</div><div class="gmail_extra"><br></div><div class="gmail_extra">In elliptic curve crypto, during DH key agreement, Alice publishes Finv(am*F(g)) mod p, where am is Alice's secret and g is the group generator.  If we could compute Finv(x) mod p, Alice's secret would be revealed.</div><div class="gmail_extra"><br></div><div class="gmail_extra">It's a rare function that fits in this form and is algebraic when built with a transcendental function F.  The circle group is in this form, when F = arcsin(x).  It turns out that:</div><div class="gmail_extra"><br></div><div class="gmail_extra">    sin(arcsin(x1) + arcsin(x2)) = x1x2 - y1y2</div><div class="gmail_extra">    where y1 = sqrt(1 - x1^2), and y2 = sqrt(1 - x2*2)</div><div class="gmail_extra"><br></div><div class="gmail_extra">If this weren't the same as simple matrix multiplication, we might have trouble analyzing it, but it is, and we can convert this easily to regular DLP.  So, naturally, we want to know what functions are in this form but are not equivalent to some well understood linear system.  Elliptic curves seem to fit the bill.</div><div class="gmail_extra"><br></div><div class="gmail_extra">In unrelated noodling...</div><div class="gmail_extra"><br></div><div class="gmail_extra">I was trying to figure out what the NSA could possibly hide in a random looking group seed.  It might be the case that they know the original arithmetic representation of the group seed on the curve, and no one else does.</div><div class="gmail_extra"><br></div><div class="gmail_extra">If I were attacking either the circle group or any Edwards curve, and I knew the generator's original arithmetic (x, y) position on the curve, and if I could find an arithmetic point on the curve which is in the group and maps to Alice's public key point, then it becomes trivial to reveal Alice's secret.  Could it be helful to know the arithmetic representation of g on the curve to map Alice's pubic key to such a point?<br></div><div class="gmail_extra"><br></div><div class="gmail_extra">I think we've shown that finding such a point in the circle group is equivalent to DLP, since I can convert the circle group problem into regular DLP, and find the multiple of g that generates Alice's pubic key point.  So, using DLP, I can find the arithmetic point on the curve.  If instead, I were given an arithmetic representation (it would be a big operator tree corresponding to the multiplication of g by am), I can easily find am just by doing line integrals to am and dividing by the line integral to g.</div><div class="gmail_extra"><br></div><div class="gmail_extra">Therefore, on the circle group mapping a public key point to an arithmetic point in the group on the circle is equivalent to DLP.  We can pose the same problem for Edwards curves.  If we can map Alice's public key point to an arithmetic representation of the point on the curve that is in the group, then we can trivially reveal Alice's secret.  This problem is equivalent to finding Alice's secret on Edwards curves.</div><div class="gmail_extra"><br></div><div class="gmail_extra">Would knowing the arithmetic representation for g help?  I it might...</div><div class="gmail_extra"><br></div><div class="gmail_extra">That's the only potential use for obscuring the original point that I can think of...</div><div class="gmail_extra"><br></div><div class="gmail_extra">Bill</div></div>