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$.
Improve this question
$\endgroup$
9
  • $\begingroup$ In exactly the same way, using the appropriate group operation of course. $\endgroup$
    – fkraiem
    Commented Dec 14, 2015 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
    Commented Dec 14, 2015 at 22:18
  • 1
    $\begingroup$ Replacing $p-1$ with the appropriate group order is included in "using the appropriate group operation". ;) $\endgroup$
    – fkraiem
    Commented Dec 14, 2015 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
    Commented Dec 14, 2015 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
    Commented Dec 14, 2015 at 23:57

1 Answer 1

Reset to default
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.)

Improve this answer
$\endgroup$
6
  • $\begingroup$ What do you mean by "insecure point" ? B.t.w Curve25519's cofactor is 8. $\endgroup$
    – Ruggero
    Commented Dec 15, 2015 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
    Commented Dec 15, 2015 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
    Commented Dec 16, 2015 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
    Commented Dec 16, 2015 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
    Commented Dec 16, 2015 at 10:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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