<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Tue, Jun 2, 2015 at 1:00 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:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><span class="">On Mon, Jun 1, 2015 at 10:35 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 class="gmail_extra"><div class="gmail_quote"><span style="font-size:12.8000001907349px">Points used in cryptography on a curve like Ed25519 correspond to real points on a real-numbered 2D curve.  We start with a point where X == 9, and use this as the group generator.  Just clockwise of the identity element (0, 1), is going to be the minimal generator, which I'll call G.  The group will include 2G, 3G, 4G, etc, and these points all line up increasing in the clockwise direction.  I do not see why there would be points in the group between multiples of G.  I also don't see why I can't do a simple binary search to determine m, when given m*G.  If that works, then given the real group generator H, I should be able to find n such that H = n*G.  After that, I think it's basic arithmetic to find o, when given o*H.  I'm making a lot of assumptions, like being able to find G easily.  I know I have an error or invalid assumption.  Where is it?  This is simple enough to code, and that's where I always find the flaw...</span></div></div></div></blockquote><div><br></div></span><div>I'm not sure I really follow what you have in mind, but it sounds somewhat similar to the baby-step giant-step algorithm?</div><div><br></div><div><a href="https://en.wikipedia.org/wiki/Baby-step_giant-step" target="_blank">https://en.wikipedia.org/wiki/Baby-step_giant-step</a></div><div><br></div><div>You can of course do things like this. The problem is the fields and scalars involved are both astronomically large (i.e. 2^255ish for e.g. Curve25519), and the complexity of baby-step giant-step is O(sqrt(n)), well outside the range of a feasible brute-force attack.</div><div><br></div><div>If you're thinking of some other attack, what do you think its big O complexity is?</div><span class="HOEnZb"><font color="#888888"><div><br></div></font></span></div><span class="HOEnZb"><font color="#888888">-- <br><div>Tony Arcieri<br></div>
</font></span></div></div>
</blockquote></div><br></div><div class="gmail_extra">My dumb attack fails (as expected).  I missed the fact that we cannot easily convert from (x, y) form to an actual location on the curve that I can plot.  Modular addition hides the actual point position well.  I do not even see how to attack this even when using points on a circle.</div><div class="gmail_extra"><br></div><div class="gmail_extra">Bill</div></div>