# Elliptic Curve ElGamal and DSA - smooth group order and element of large prime order

In regular ElGamal and DSA, we choose large primes $p$ and $q$ such that $p\equiv 1\pmod{q}$, and a group element $g$ of order $q$ by computing $a^{(p-1)/q}$ for some random $a$. This is to prevent smooth group order which can then be factorized, and the discrete log problem can be solved by Pohlig-Hellman algorithm.

How can the same be accomplished for a group of points on an elliptic curve over finite field?

• Make sure the group order is not smooth
• Find an element of large prime order $q$.
• In exactly the same way, using the appropriate group operation of course. Dec 14, 2015 at 22:17
• Not exactly; the size of the elliptic curve group is (typically) not $p-1$ (and it would be really bad if it was). Dec 14, 2015 at 22:18
• Replacing $p-1$ with the appropriate group order is included in "using the appropriate group operation". ;) Dec 14, 2015 at 23:20
• @fkraiem But then the group order is not guaranteed to be non-smooth; i.e., there's no way to know that it has large prime divisor $q$. Even supposing that the group order has a large prime divisor $q$, there's no way to find $q$ except to factorize the group order (which is hard to do since it's not smooth). Even suppose further that we can factorize the group order, so can an adversary, and he'll be able to break the crypto with Polhig-Helman. Dec 14, 2015 at 23:46
• @Myath The group order of the curve can typically be factored, so we can identify if it has a large prime factor $q$. Then we work in the subgroup of order $q$, which has prime order by construction and is thus immune to Pohlig-Hellman. Dec 14, 2015 at 23:57

Moreover, standard curves such as the NIST curves or Curve25519 are chosen so that the order of the group of points is either prime (as in the NIST curves) or is a large prime multiplied by a small cofactor ($$8$$ in the case of Curve25519), so if you use a standard curve you know there is a subgroup of large prime order for you to work in. (It is important that you work in a group of prime order to prevent other types of attacks.)
• Oh yes, I misread the output of factor()... By "insecure point" I quite obviously mean a point which should not be used as a generator. (aka "points of smooth order") Dec 15, 2015 at 8:20
• Assuming Curve25519's order is $8l$. You are suggesting that using, as generator, a point of order $2,4,8$ is insecure. But why are you excluding from the "insecure point" definitions points of order $2l,4l$ and $8l$ ? Dec 16, 2015 at 8:19
• Because $l$ is prime, so a point of order a multiple of $l$ is not insecure, why would it be? Dec 16, 2015 at 8:23
• Assume we are using curve25519 (but not X25519). In a static DH scenario, define a public key $Q=dG$ where $G$ has order $l$, then we can mount a small group attack to recover $d \mod l$ by providing as our fake public key a point of order $8$ or a properly crafted point of order $8l$. Where you referring to other types of attacks ? (I'm sorry I'm going a bit OT) Dec 16, 2015 at 10:21