1
$\begingroup$

Suppose one is implementing a cryptographic scheme over a group where one needs the discrete logarithm to be hard - what is the recommended group to use? I'm looking for a group where calculations are simple but it doesn't need to be extremely efficient. I would therefore prefer some type of multiplicative group mod n. It seems different "diffie-hellmann" like schemes employ different groups. So here's some possibilities - I would ideally like them "ranked" in terms of security wrt. the discrete log problem (or any comments if some of them are terrible/insecure choices)

1) Generate a random, big prime "p" and use (Z_p)* as the group (i.e. the multiplicative group modulo a prime p) - the group will have order p-1.

2) Generate a random big integer "n" and use (Z_n)* as the group (i.e. the group will have order phi(n)).

3) Generate a large prime "p" and find a large prime-sized subgroup of (Z_p)*.

4) Generate a large number (not prime) "n" and find a large prime-sized subgroup of (Z_n)*.

(My guess of a ranking - in increasing level of security - would be 2, 1, 3/4).

Some articles seem to call for #3-#4. But are the benefits and are 1+2 inherently secure (I would guess #2 might be depending on factorization of n)? Also, what is the best way to generate a group like #3/#4 (depending on which one is better) Are there other even better choices for groups than 1-4? Also, does it matter what generator one uses? For instance, is the security of #1 intact if one uses the base g = 2?

Thank you in advance!

$\endgroup$
  • 2
    $\begingroup$ Check NIST and ANSI standards for discrete log-based crypto, they discuss parameter generation. $\endgroup$ – pg1989 Nov 26 '13 at 20:57
  • 1
    $\begingroup$ Note that Decisional Diffie-Hellman will be easy for #1 and #2. $\;$ $\endgroup$ – user991 Nov 26 '13 at 21:58
  • 1
    $\begingroup$ If you only want to rely on the discrete log problem and no additional assumptions such as factoring, choices #1 and #3 are suitable. In the former case you have to avoid choosing smooth group orders, i.e., that $p-1$ has only small factors. You can avoid this by choice #3 which is typically done by choosing $p$ to be a safe prime and then you also avoid that the DDH is easy (as Ricky mentioned for #1). As @pg1989 mentioned you can find strategies in NIST standards. And no, it doesn't matter which generator you choose - the smaller the better the efficiency. $\endgroup$ – DrLecter Nov 26 '13 at 22:00
  • $\begingroup$ @RickyDemer why #2 is easy? $\endgroup$ – curious Nov 10 '14 at 13:29

Your Answer

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

Browse other questions tagged or ask your own question.