The Generator point and Mod P in ECDSA

Question

I've been reading about The discrete logarithm problem as of recent and i decided to try it out on a small portion of numbers myself and i actually came to a mental gridlock after watching this Video.

In the video, he uses the mod p which is prime to find a specific generator point (which is also prime) that could iterate all possible points(which i know that G is constant throughout the curve. but why use the order of the curve to find a suitable generator point.). And he also mentions that some numbers can't provide all possible digits that can iterate through all possible values.

But what baffles me the most is that the real values like the generator point and the order of the curves for example secp256k1, secp192ri is/are not prime. And did i mention that all the answers on the discrete logarithm problem online ALL had prime generator points and the order of the curve were also prime. Can i get a breakdown as of what is going on?

Any opinions would be appreciated.

Answer 1

The video (at least, where the question links) illustrates the Baby-step/Giant-step Discrete Logarithm method in the multiplicative group modulo $p$, for prime $p$. That is the set $\{1,2,\ldots,p-2,p-1\}$, under the internal operation multiplication modulo $p$.

This group has essentially nothing to do with an Elliptic Curve group. The principle of Baby-step/Giant-step is the same regardless of group, however the operation analog to multiplication modulo $p$ is extremely different in an Elliptic Curve group.

---

It is important for security that the order of the group generated by $g$ (that is, the number of distinct values $g^x\bmod p$ can take) is prime, or at least has a large prime factor. When working in the multiplicative group modulo $p$, the order of the full group is $p-1$, and the order of $g$ is some divisor of that. One option is to choose $p$ such that $(p-1)/2$ is prime ($p$ is a so-called safe prime). Now we can take any $g$ except $g=1$ and $g=p-1$, and it's order will be $p-1$ or $(p-1)/2$, which both have a large prime factor $(p-1)/2$.

There is no imperious reason to choose a generator $g$ that is prime. It happens that $2$ and $3$ are popular, and prime; and some people have found satisfactory to choose $g$ prime.

There's even less reason to worry about prime $g$ in ECC groups. In secp256k1, both the $x$ and $y$ coordinates of the generator point are large even integers, thus not prime. What matters is the order of the group generated by $g$. That is noted $n$, and the curve parameters are usually chosen such that $n$ is prime.

Answer 2

If I've understood correctly, you are talking about the curve order $n = |E(K)|$ and a prime subgroup generated by a point $G$ with order $r = |\langle G\rangle|$. Then we have a cofactor $h = \frac{n}{r}$.

Some curves like Curve25519 is doesn't have prime order, since it has cofactor 8. This means that there are other subgroups of $E(K)$ with order $2,4,8,r,2r,4r,8r$ with $r$ is a large prime.

There is a small subgroup attack called the Lim–Lee active small-subgroup attacks. The attacker chooses $P$ send to the user and the user reveals $[k]P$. The obvious method for the attacker is choosing $P$ in a small group where the ECDLP is easy. If the curve $|E(K)|$ is prime then there are no non-trivial subgroups for the attacker. If near the prime like 8 in the Curve25519 the prevention is easy just clear the least significant 3 bits.

We always want the $r$ to be prime to resist the Pohlig–Hellman algorithm which is very effective if the order is not a prime and doesn't have a big factor.

Does cofactor affect security?

• cofactor = 1; It is clear that the $\langle G\rangle$ is the whole curve and any non-zero point can be a generator. Lim–Lee will fail, since the order is prime the Pohlig-Helman, too.

• cofactor >1; Then we need to check that the incoming point is not on the small subgroup, rather than the $\langle G\rangle$. The designers of the curves take this into consideration like the Curve25519 has cofactor 8. When used with Diffie-Hellman key exchange (named X25519) then while users select the private key, the three least significant bit set to zero to guarantee that the private key in the $\langle G\rangle$

As we can see that the $cofacor =1$ is easy to use. However, having $>1$ some other advantages like the Montgomery Curves

• has the side-channel resistant Montgomery Ladder,
• every Montgomery Curve has a point of order 2 i.e. the cofactor is always >1.