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!
