Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
For the Diffie-Hellman protocol I've heard that the generator 3 is as safe as any other generator. Yet, 32-bit or 256-bit exponents are sometimes used as generators. What is the benefit of using these very large generators if they are just as safe as the generator 3?
If 3 is not the safest generator, how could one calculate the shortest length generator that would be considered secure?
The security of Diffie-Hellman depends upon the group in which DH is used, but not upon which generator is used for this group. See note 3.53 (chapter 3, page 103) of the Handbook of Applied Cryptography.
In more details: for DH, we use a subgroup of size $q$ of the integers modulo $p$ (a big prime) with the multiplication as group operation. $q$ should be a prime of length at least $2n$ bits for a $2^n$ security level (or, at least, $q$ should have a prime divisor of at least $2n$ bits). Typical parameter sizes are 160 bits for $q$ and 1024 bits for $p$, or 256 bits for $q$ and 2048 bits for $p$. The generator $g$ is an element of order $q$.
When $p$ is a "safe prime", this means that $\frac{(p-1)}{2}$ is also prime. We then define $q = \frac{(p-1)}{2}$. In that situation, the order of any non-zero $g \bmod p$ (except 1 and $p-1$) is either $q$ or $2q$, hence every $g$ between $2$ and $p-2$ (inclusive) is a fine DH generator and ensures optimal security. Therefore it is customary to select a $g$ which makes computations easier, usually $g = 2$ or $g = 3$.
Another way to define a DH group is inherited from what is done with DSS (a signature algorithm which also works in that kind of group): we first select a prime $q$ of appropriate size (e.g. 160 bits), then we look for $p$ by setting $p = qr+1$ for random values of $r$ of the right size (so that $p$ has the size we need), until we hit a prime $p$. This allows the use of a smaller $q$, thus smaller DH exponents and faster computations; on the other hand, we cannot choose the generator as freely in that case, because there are only $q-1$ generators of a subgroup of order $q$ modulo $p$. So we take a random value $s$ and compute $g = s^{(p-1)/q} \bmod p$. This yields an appropriate generator, but not a small one such as $2$ or $3$.
Why wouldn't everyone use the obvious $2$ or $3$ rather than 256-bit numbers?
A modular exponentiation uses a "square and multiply" algorithm. Using $2$ as generator simplifies the multiplies, but not the squarings, which represent the wide majority of the computation (especially when using window-based optimizations). Using $g=2$ is neat but does not imply that much of a performance enhancement.
Window-based optimization groups multiplications. Basically, you precompute $g^2, g^3 \dots g^{15}$; then, you do the squarings and you multiply with one of the precomputed values only once every four squarings. This is with a 4-bit window, you can have bigger windows; there are possible savings on the window building too. This is why the squarings use more than $\frac{2}{3}$ of the total CPU cost, closer to 80 or 85%. This leaves relatively little to optimize with $g=2$.
Most probably, someone had at some point a fuzzy feeling of a 256-bit number being "more secure" in some unspecified way. I have not seen that personally. Several protocols (e.g. IKE, used for IPsec) use the "Oakley groups" from RFC 2412 (Appendix E) which have $g=2$.
