[Cryptography] Why is ECC secure?

[Viktor Dukhovni]

On Mon, Jun 01, 2015 at 10:35:43PM -0700, Bill Cox wrote:

> I still cringe whenever anyone throws around "real
> numbers" and "infinity" without any mathematical definition, which is why
> Cantor's diagonal proof is wrong.

Standard definition of infinity:

	http://en.wikipedia.org/wiki/Axiom_of_infinity

The axiom of infinity, the axiom of choice, ... are powerful tools
that amplify the power of discrete mathematics.  Provided these
are non inconsistent with more elementary axioms, any results they
prove about elementary arithmetic are correct (have no elementary
counter-examples).

> Here's my latest dumb attack on Edwards curves, still working the
> circle-angle.  I know it's a dumb attack...
> 
> Points used in cryptography on a curve like Ed25519 correspond to real
> points on a real-numbered 2D curve.

You can stop right there, points on elliptic curves over F_p (prime
fields or perhaps their Galois extensions) do not in any sense
"correspond" to points on real-number curves (characteristic 0).

Further-more, unlike circle arithmetic, even with real elliptic
curves addition of points is highly non-monotone in any smooth
parametrization of the curve.

> The group will include 2G, 3G, 4G, etc, and these points all line up
> increasing in the clockwise direction.

This is simply false.

> I do not see why there would be
> points in the group between multiples of G.

If we're still talking about real curves, what does "between" mean?

> I also don't see why I can't
> do a simple binary search to determine m, when given m*G.

Because there is no computationally feasible way given a*G and b*G
(but not a,b) to determine which of them arises from the smaller
multiplier.

> If that works,

If grandma had wheels she'd be a wagon.

> 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...

If there are effective attacks on EC, they're not nearly so naive.
These posts would be embarrassing, if only you knew enough to know
what you don't know.  It is best to stop here.

-- 
	Viktor.