Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

What are the properties a generator $g$ should have to be secure for ElGamal signatures (original scheme)?

I am aware that it is poorly chosen and not secure when $g|p-1$ or $g^{-1}|p-1$, where $p$ is the large prime so that $g$ generates $Z_p^*$ and $g$ has maximum order (that is, $p-1$).

Are there other properties one should consider? Additionally, should $g$ be picked randomly over $[1..p-1]$ or is it safe to choose it to be a small integer to start with?

share|improve this question

1 Answer 1

First you should know that Elgamal encryption and signature security is based on DDH problem (Decisional Diffie Hellman) which is tractable in some groups that CDH problem is believed to be hard (Computational Diffie Hellman). As in the case of $\mathbb{Z_q}$ in which CDH is believed to be hard but DDH is apparently tractable.

Let $p = 2p_1 + 1$ where both $p$ and $p_1$ are prime. Let $Q_p$ be the subgroup of quadratic residues in $\mathbb{Z_p}$. $Q_p$ is a cyclic group of prime order itself in which DDH assumption is believed to be hard. This group and some other groups in which DDH problem is intractable are mentioned in this paper by Dan Boneh.

Any randomly chosen primitive element in $\mathbb{Z_p}$, say $g$, to the power of two ($g_1=g^2$) is a 'safe' generator for the subgroup of quadratic residues in $\mathbb{Z_p}$ (it is defined above as $Q_p$). A primitive element of $\mathbb{Z_q}$ is an element which are relatively prime to $p$. ($gcd(g,p)=1$)

share|improve this answer
    
What you write is true for semantic security of ElGamal encryption. But security oft ElGamal signatures is not related to the DDH assumption in the used group. It would be more than surprising if unforgeability of ElGamal signatures could be reduced to a decisional problem instead of a computational one. –  DrLecter Feb 21 at 21:46

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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