[Cryptography] Why is ECC secure?

[Tony Arcieri]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20150602/f233efdb/attachment.html>