<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Fri, May 29, 2015 at 5:21 PM, Tony Arcieri <span dir="ltr"><<a href="mailto:bascule@gmail.com" target="_blank">bascule@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><span class="">On Fri, May 29, 2015 at 12:26 PM, Bill Cox <span dir="ltr"><<a href="mailto:waywardgeek@gmail.com" target="_blank">waywardgeek@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><div><span style="color:rgb(37,37,37);font-family:sans-serif;font-size:14px;line-height:8.96000003814697px">Why do we believe this is secure, other than the fact that in EEC's short life, no one has cracked it?  Compared to DLP and integer factorization, I doubt many people have tried.</span></div></div></blockquote><div><br></div></span><div>For what it's worth, you can say the same thing about factorization. The only reason RSA is secure is because factoring large numbers is generally considered a hard problem.</div></div></div></div></blockquote><div><br></div><div>Is the following problem hard?  I'm still trying to grok the basics of what make ECC hard to attack.  The simplified system I'm trying to attack is just the unit circle, which is basically an Edwards Curve with d = 0.  I think I might be able to find the discrete log on the circle if I could just map the (x, y) mod p point back to a rational point on the circle.</div><div><br></div><div>For a given prime p, the given integer x, y point mod p satisfies</div><div><br></div><div>    (x, y) = s*G mod p</div><div><br></div><div>where G is a generator point, and s is a secret value.  I'm trying to find s, which looks doable if I can map (x, y) back to a rational point on the circle, (l/n, m/n).  The (x, y) point satisfies:</div><div><br></div><div>    x^2 + y^2 = 1 mod p</div><div><br></div><div>This point corresponds to a rational point on the unit circle, (l/n, m/n), where</div><div><br></div><div>    (l/n)^2 + (m/n)^2 = 1   (not modular arithmetic)</div><div><br></div><div>or equivalently:</div><div><br></div><div>    l^2 + m^2 = n^2</div><div><br></div><div>At the same time:</div><div><br></div><div>    l/n = x mod p</div><div>    m/n = y mod p</div><div><br></div><div>or equivalently:</div><div><br></div><div>    l = n*x mod p</div><div>    m = n*y mod p</div><div><br></div><div>There are three unknowns (l, m, and n) and three equations restricting their values.  I would expect to be able to find a solution in most similar cases.  I have not figured out any better way to compute l, m, and n given x and y than the giant-step/baby-step algorithm.  Is this problem known to be hard?  Have I simply failed to find the known solution?</div><div><br></div><div>Thanks,</div><div>Bill</div></div></div></div>