Do we always choose a generator of prime order for ECDH? If yes, then why?

user93353

11/6/23, 7:54 AM

I am looking at the description of Weil MOV Attack from the Vanstone, Menezes Book (Guide to Elliptic Curve Cryptograpy)

Suppose now that the prime order $n$ of $P \in E(F_q)$ satisfies $gcd(n,q) = 1$. Let $k$ be the smallest positive integer such that $q^k \equiv 1 \pmod n$, the integer $k$ is the multiplicative order of $q$ modulo $n$ and therefore is a divisor of $n − 1$. Since $n$ divides $q^k − 1$, the multiplicative group ${F^\star}_{q^k}$ of the extension field $F_{q^k}$ has a unique subgroup $G$ of order $n$. The Weil pairing attack constructs an isomorphism from $\langle P \rangle$ to $G$ when the additional constraint $n \nmid (q − 1)$ is satisfied

So the $MOV$ attack would work only if the $ECDH$ problem is of the kind $nG = R$ with $G$ a point of prime order. So for $ECDH$, do we always chose a generator of prime order. If so, why?

So there seems to be 4 conditions which need to be satisfied for the MOV attack to work

Prime order of Generator.
The order of the generator is coprime to the order of the Field
The order of the genarator does not divide $(q − 1)$
Small embedding degree

So even if you do have a small embedding degree what would be probability that the $MOV$ attack would be applicable. A lot of different conditions need to be satisfied - i.e. you could choose a small embedding degree as long as one of the other conditions aren't satisfied.

217

1 + 0

elliptic-curves

diffie-hellman

attack

Score:3

Crypto

Daniel S

11/6/23, 11:19 AM

In broad generality we can solve the discrete logarithm $nG=R$ problem for a point of order $m$ by solving for $n\pmod q$ for every prime power that divides $m$ and combining them with the Chinese remainder theorem.

Generically we can solve the component discrete logarithm problem modulo $q=p^t$ with $O(tp^{1/2})$ work using methods such as Pollard's kangaroo.

However for especially badly chosen primes where one of the primes dividing $n$ divides the underlying field characteristics (so that the Smart/Semaev anomalous curve attack applies), or where there is a small embedding degree for that prime (so that the MOV attack applies), the value $n\pmod q$ can be recovered in work sub exponential in $p$. This applies whether $q=n$ or whether there is a cofactor.

The small embedding degree would always make this component of the discrete logarithm very easy to recover so that the hardness of the overall discrete logarithm is dependent on the other primes. At this point one might as well simply work outside the subgroup generated by the prime power with small embedding degree.

The choice to use a generator of prime order is one of efficiency. For, say, 128-bits of security while not leaking any information about $n$, we would want every prime factor of the order of the generator to be 256-bits in size and neither anomalous nor of low embedding degree. We could do this with a case where the order of the generator is the product of two 256-bit primes, but then we would need an underlying field of at least 512-bits and be passing around similarly sized coordinates as public keys. By only using one prime we can work with the smallest possible underlying field while having the appropriate level of security.

+ 3

user93353

11/6/23, 11:22 AM

Could you also answer the question in the title. Is the generator always a Prime? If yes, then why?

Daniel S

11/6/23, 11:25 AM

Do you mean a generator prime order? In which case, see the last paragraph (I saved the first paragraphs partway through writing).

user93353

11/6/23, 11:56 AM

ok, thank you ...

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Do we always choose a generator of prime order for ECDH? If yes, then why?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.