[Cryptography] Why is ECC secure?

[Bill Cox]

On Tue, Jun 2, 2015 at 1:00 PM, Tony Arcieri <bascule at gmail.com> wrote:

> On Mon, Jun 1, 2015 at 10:35 PM, Bill Cox <waywardgeek at gmail.com> wrote:
>
>> 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...
>>
>
> I'm not sure I really follow what you have in mind, but it sounds somewhat
> similar to the baby-step giant-step algorithm?
>
> https://en.wikipedia.org/wiki/Baby-step_giant-step
>
> 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.
>
> If you're thinking of some other attack, what do you think its big O
> complexity is?
>
> --
> Tony Arcieri
>

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.

Bill
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20150602/e0b8e3e6/attachment.html>