Large prime numbers in ECC and discrete logarithm

In elliptic curve cryptography using Diffie-Hellman protocol, we need to use large prime numbers.

So my question is what makes discrete logarithm hard to solve when we use large prime numbers.

I guess since we use large prime numbers we will have a lot of points that satisfy our curve equation

The answer is not so simple;

• First of all the number of points that satisfy the curve equation $N$ on the curve is bounded by the Hasse's bound $$|N - (q+1)| \le 2 \sqrt{q}$$ for a prime $q$. This simply says that if you want a curve that has a large number of points then you need a big prime ( short story).

• The curve order must be prime ( prime curves) or must have at least one large prime factor. Curve25519 is not a prime curve, that has a cofactor $h=N/8$, this enables Montgomery representation of the curve that helps secure implementations. If the curve has smooth order, which means it won't have a large prime then the Poglig-Helamn will destroy it regardless of order. Having a large order or a large prime order is important.

• The twist of the curve must have large prime order against twist attacks.

• The order of the curve and order of the base field $(K)$ are the same then the discrete logarithm on this curve runs in linear time Smart 97.

• The curve should not be supersingular, otherwise, the Discrete logarithm is easy ( now they are in use for isogeny that doesn't use discrete logarithm and expected to be secure against Shor's attack)

Now combining these we can say if the point curve group of the ECC has a large prime and doesn't have some special property ( we can say it is a generic curve) then the best attack is the Pollard's Rho with $\mathcal{O}(\sqrt{N})$.

With this, we can say Curve25519 has around 128-bit discrete log security, and Curve448 has 224-bit discrete log security.

And, finally, for more information visit the safecurves.

In elliptic curve cryptography using Diffie-Hellman protocol we need to use large prime numbers.

More precisely

• We usually use a curve with a generator which order is divisible by a large prime, because that gives insurance against the Pohlig-Hellman method to compute discrete logarithms.
• We often make the generator of exactly that prime order, because we can easily do so, and that makes the curve+generator more suitable for other uses, such as signature. That's however not useful for the security of Diffie-Hellman, AFAIK.
• We often use a curve on a field of large prime order, even though we do not have too, for reasons discussed there.