<div dir="ltr"><div>Short version: cracking modern ECC, at least in this special case, is equivalent to adding up arc-lengths on the infinity symbol.  However, the math is hard, and no one has figured it out.  Do you want to have a try?   :-)</div><div><br></div><div><img src="cid:ii_1509217183ca2291" alt="Inline image 1" width="366" height="130"><br></div><div><br></div><div>Fear mongering disclaimer: Please _do_ continue to use ECC with confidence (224 bits or more).  I see no reason to believe ECC DH is weaker than regular DH (2048 bits or more), or the other way around.  I personally consider the security of the ECDLP assumption to be on-par with the security of the DLP assumption.  I doubt either will be cracked in my lifetime.  I also doubt we'll see quantum computers capable of cracking ECC-224.  Any "crypto expert" who thinks one is obviously easier to crack than the other is not really a crypto expert, IMO.  Preferences for one or the other are fine, but no one has a crystal ball that tells them which problem will fall first.  If you are really paranoid, consider using _both_ so that your security relies on both problems being cracked at the same time.  This suggestion is from DjB, where I read his recommendation for using regular DH for long-term keys, and ECDH for ephemeral keys, bound to the long-term keys.  Also, there is no pending "cryptopocalypse", and quantum computing at this scale remains comfortably in the far distant future.  Use either DH or ECC DH depending on the specific needs of your application.  Don't fall victim to the fear mongering.</div><div><br></div><div>Now, back to attacking ECC, just for fun...</div><div><br></div><div>For the case of d == -1 on <a href="https://en.wikipedia.org/wiki/Edwards_curve">Edwards Curves</a>, the "thing being added" when we add points together in Elliptic Curve Crypto is arc-lengths on the infinity symbol, called a <a href="http://mathworld.wolfram.com/Lemniscate.html">Lemniscate</a>.  If we can compute the following integral, mod p, we can break ECC in this case (-1 is not a square mod p, or a different p would have been used), and likely gain insight into how to crack the general ECC case:</div><div><br></div><div>    arcLength(x) = integrate 1/sqrt(1  - t^4) dt from 0 to x</div><div><br></div><div>Here, x is the x-coordinate of Alice's public key (x, y) which she computed as m*g, where g is the "generator point" on the infinity symbol.  What we mean by m*g is the point on the infinity symbol we reach when moving m times the arc length from the center to g.  By choosing units for the arc length of g to be 1, rather than using radians or degrees, the arc length to Alice's point m*g is just m.</div><div><br></div><div>There is a problem: the point m*g on the infinity symbol wraps around many times. There is a solution.  Simply find the point "h" in the group closest to the origin (0, 0), and convert Alice's point m*g into m*h.  This is done by multiplying Alice's point m*g by n, where h = n*g.  We find n at the same time as finding h.  This turns out to be easy, so long as we know the rational point on the curve used to generate g.  This is the case for my prefered signature scheme Ed25519.  It is not the case for the curve we actually use most of the time: ECDSA-P256.  The NSA decided not to tell us the original rational X-coordinate that they used to compute their generator point, which means we can't find h, and we can't solve the wrapping-around problem.  I'm not saying this is strong evidence of a back-door in ECDSA-P256, but it does make me go "hmmm..."</div><div><br></div><div>Other than for NSA designed ECC curves, it is common practice to publish how the generator point was selected, which is usually to start with a simple rational X-coordinate on the curve, which enables us to find h.  Using 'h' rather than 'g'.  m*h never wraps all the way around the lemniscate, so arcLength(m*h) = m in units of arcLength(h).</div><div><br></div><div>All we have to do is compute that simple arc-length integral.  If we can do that, we can reveal m.  However, no one knows how to do this, SFAIK.  We don't even seem to have promising leads.  We do have strong evidence that solving this integral is at least as hard as finding x given 2^x mod p.  However, if p is only 256 bits, we can trivially crack that in Python.  The rest of ECC's security, at least for d == -1, relies on the assumption that no one will figure out a solution to this very difficult problem, and the somewhat more difficult ones where d != -1.  However, we have no proof that it cannot be done, just as we have no proof that we can't solve regular DPL in polynomial time.  Crypto is based on assumptions that problems are hard.  We can't "prove" they are hard.  Instead, we get there by having lot's of people try to solve it and fail.  Want to help out by taking a crack at it?</div><div><br></div><div>Have fun,</div><div>Bill</div></div>