[royalfork]

For RSA, most non-experts have an intuitive feel for why the cryptosystem is secure: we all know that factoring numbers is hard. Do you think it's possible to give a concise explanation for why ECC is secure aside from "hand wavey black box" + understandable algebra = security?

Total aside: when I was writing this, you answered a lot of my questions in #bitcoin. Thanks for helping me out :)

[defen]

I'll describe the discrete logarithm problem; the elliptic curve discrete logarithm problem is like it, but harder (different group operation).

Pick a prime number p.

Pick a positive integer x < p

Then every positive integer < p can be written in the form: x^n (mod p), for some positive integer n < p.

For example if p is 5 and x is 2: 2^1 ≡ 2 (mod 5); 2^2 ≡ 4 (mod 5); 2^3 ≡ 3 (mod 5); 2^4 ≡ 1 (mod 5);

Try it with larger p or different x's and try to find a pattern. The discrete logarithm problem says: given c, x, and p, find y such that x^y ≡ c (mod p). In English, what power do I have to raise x to, in order to get a number that is equivalent to c, modulo p. The "modulo p" thing is what makes it hard - without that you just have x^y = c, so ln(x^y) = ln(c) and therefore y = ln(c)/ln(x)