Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
The discrete logarithm problem is the mathematical trap door function underpinning elliptic curve cryptography. If it's naturally hard to climb back through the trap door, how can there be insecure elliptic curves?
Any answer would be most beneficial for me if it remained light on the math, if that's at all possible.
Discrete Logarithm on elliptic curves is hard in the following sense: on an $n$-bit curve, solving DL has cost $2^{n/2}$. Thus, this is infeasible only as long as $n$ is large enough to make that cost prohibitive. A 256-bit curve is large enough; a 60-bit curve is not.
Also, some curves have a special structure which can be leveraged to compute DL faster. Notably:
If the curve order is not prime or does not have a big prime factor, then DL is easier (the same applies to normal non-curve DL).
Some curves have a low embedding degree, which allows for converting DL on the curve into a comparatively easier DL in the multiplicative subgroup of a finite field extension. This is very heavy in maths. If the curve is somewhat weakened but not too much, then it can still be safe while allowing computation of a pairing, an algebraic operation which is useful for some complicated cryptographic protocols (e.g. identity-based encryption).
Some curves make it easier to implement them securely, e.g. without leaking secret information through side channels.
Generating a new curve entails trying out equation parameters and checking that the resulting curve is not one of the known “bad cases”. In practice, a non-prime order is the most frequent case; for 256-bit curves, you need to try a hundred curves or so before getting one with a prime order. Curves with a low embedding degree are extremely rare, and easy to check for.
Thomas's answer is excellent. I will just add that formally it makes no sense to actually say something like "we assume the discrete log problem is hard". Rather, we really have to refer to a specific group (or family of groups) and assume that the problem is hard in those group. This is because it is blatantly easy in some groups (e.g., the additive group over $\mathbb{Z}_p$) and believed to be hard in others. Since each curve defines a different group, there can certainly be some curves for which it is not hard.
To amplify Yehuda Lindell's answer even within a single family of groups, here is an example of a 2046-bit modulus $p$ for which discrete logs in $(\mathbb Z/p\mathbb Z)^\times$, as in standard modular multiplication Diffie–Hellman, are extraordinarily easy to compute:
0x2465a7bd85011e1c9e0527929fff268c82ef7efa416863baa5acdb0971dba0ccac3ee4999345029f2cf810b99e406aac5fce5dd69d1c717daea5d18ab913f456505679bc91c57d46d9888857862b36e2ede2e473c1f0ab359da25271affe15ff240e299d0b04f4cd0e4d7c0e47b1a7ba007de89aae848fd5bdcd7f9815564eb060ae14f19cb50c291f0bbd8ed1c4c7f8fc5fba51662001939b532d92dac844a8431d400c832d039f5f900b278a75219c2986140c79045d7759540854c31504dc56f1df5eebe7bee447658b917bf696d6927f2e2428fbeb340e515cb9835d63871be8bbe09cf13445799f2e67788151571a93b4c1eee55d1b9072e0b2f5c4607f.
2046-bit moduli should be secure, right? No, not at all. First of all, it helps if they're prime (or at least if you don't know their prime factorization, but for public DH or DSA parameters, you would like to know this sort of thing about them). This number $p$ is not prime; rather, it is the product of the first 232 prime numbers except 2. So, given fixed $h$, to solve $$g^x \equiv h \pmod p$$ for $x$, it suffices to compute the discrete logs $x_3$, $x_5$, $x_7$, etc., satisfying
\begin{align*} g^{x_3} &\equiv h \pmod 3, \\ g^{x_5} &\equiv h \pmod 5, \\ &\vdots \end{align*}
independently, and then assemble them into a solution for $x$ with the Chinese remainder theorem:
\begin{align*} x &\equiv x_3 \pmod{\phi(3)}, \\ x &\equiv x_5 \pmod{\phi(5)}, \\ &\vdots \end{align*}
where $\phi(3) = 3 - 1$, $\phi(5) = 5 - 1$, etc., since they're all prime.
This algorithm is so cheap that you could do it with pen and paper using schoolbook long division and schoolbook multiplication in a few hours. But the easiness of this algorithm means nothing about how easy or hard it is to compute discrete logs in $(\mathbb Z/q\mathbb Z)^\times$ where $q$ is the RFC 3526 Group #14 modulus
0xffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca18217c32905e462e36ce3be39e772c180e86039b2783a2ec07a28fb5c55df06f4c52c9de2bcbf6955817183995497cea956ae515d2261898fa051015728e5a8aacaa68ffffffffffffffff.
The same algorithm using the Chinese remainder theorem doesn't work because $q$ is prime, so you can't solve the problem independently modulo all its factors and then recombine the results into a solution.
The choice of field, curve shape, curve parameters, etc., has the same kind of impact on the ease or difficulty of computing elliptic-curve discrete logs as the choice of modulus has on the ease or difficulty of computing modular multiplication discrete logs.
