finding a generator for elgamal

how are generators found for the elgamal signature scheme? are there values that are used by most programs that are good generators? or is there a method to find a generator for a prime value? if so, how? Would it be true to say that a prime number has at 开发者_C百科least 1 generator?

---

Use DSA instead of the ElGamal signature scheme.

There are just too many mistakes that can be made implementing ElGamal. One of those mistakes is what GregS proposed: to use the IKE parameters. These parameters were generated for the ElGamal encryption and not for the signature scheme. The two schemes have distinct requirements. In particular using g=2 as a generator is a good choice for the encryption, but a very bad choice for the signature scheme. (See e.g. the "Handbook of Applied Cryptography" http://www.cacr.math.uwaterloo.ca/hac/ note 11.67 in chapter 11 for some details). Correct would be to select the generator randomly. But once again, if you just use DSA then you can simply avoid these pitfalls by following the standard.

Just to add a little more: OpenPGP https://www.rfc-editor.org/rfc/rfc4880 used to allow ElGamal signatures, but has deprecated them some time ago. This deprecation was quite reasonable, since DSA has only advantages: it is more efficient, more secure and standardized. Of course, you could look at old PGP implementations, but it wouldn't tell you if these implementations give you reasonable choices without reading the literature first.

---

how are generators found for the elgamal signature scheme? are there values that are used by most programs that are good generators? or is there a method to find a generator for a prime value? if so, how?

You can use the generic, probabilistic algorithm 4.86 in Handbook of Applied Cryptography. You still need to weed out from the output of such algorithm the values known to be insecure for Elgamal signature though. At the very least any value that divides p-1 (for instance 2) and any value whose inverse divides p-1. Note that those are the conditions I am aware of today. Some in-depth research over papers published on the topic may be needed.

Personally, I would not trust domain parameters already used in existing programs. The authors may not have considered all the conditions above, plus research may have highlighted new conditions since they were chosen.

Would it be true to say that a prime number has at least 1 generator?

Absolutely true: there always is at least one generator for the multiplicative group over the integers modulo p (with p being a prime number). It has actually many more: phi(phi(p)), with phi being the totient function. Not all of them will be safe for the Elgamal signature scheme though.

---

El Gamal can be seen as a variant of the Diffie Hellman algorithm, and parameters for the latter can be used for the former. So for example you can use IKE groups 1 and 2 from RFC 2409, and larger IKE groups sprinkled in other RFCs. You can also follow the discussion in FIPS 186 for generating DSA parameters. Also, see this discussion of primitive roots.

EDIT:
As noted by @abc, this is wrong for el gamal signatures. Follow the DSA link (FIPS 186).