2
$\begingroup$

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$.
$\endgroup$
  • $\begingroup$ In exactly the same way, using the appropriate group operation of course. $\endgroup$ – fkraiem Dec 14 '15 at 22:17
  • 1
    $\begingroup$ Not exactly; the size of the elliptic curve group is (typically) not $p-1$ (and it would be really bad if it was). $\endgroup$ – poncho Dec 14 '15 at 22:18
  • 1
    $\begingroup$ Replacing $p-1$ with the appropriate group order is included in "using the appropriate group operation". ;) $\endgroup$ – fkraiem Dec 14 '15 at 23:20
  • $\begingroup$ @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. $\endgroup$ – Myath Dec 14 '15 at 23:46
  • $\begingroup$ @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. $\endgroup$ – fkraiem Dec 14 '15 at 23:57
1
$\begingroup$

For the curves used in cryptography today, the order of the group of points is typically 256 bits, sometimes 512. Such numbers are within the range of current factoring algorithms (indeed, this is why you don't use 512-bit RSA keys), and so typically the order of the group can be factored and it is easy to see whether it has a large prime factor.

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.)

$\endgroup$
  • $\begingroup$ What do you mean by "insecure point" ? B.t.w Curve25519's cofactor is 8. $\endgroup$ – Ruggero Dec 15 '15 at 8:08
  • $\begingroup$ 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") $\endgroup$ – fkraiem Dec 15 '15 at 8:20
  • $\begingroup$ 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$ ? $\endgroup$ – Ruggero Dec 16 '15 at 8:19
  • $\begingroup$ Because $l$ is prime, so a point of order a multiple of $l$ is not insecure, why would it be? $\endgroup$ – fkraiem Dec 16 '15 at 8:23
  • $\begingroup$ 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) $\endgroup$ – Ruggero Dec 16 '15 at 10:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.