34
$\begingroup$

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?

$\endgroup$

1 Answer 1

24
$\begingroup$

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$.

$\endgroup$
3
  • 1
    $\begingroup$ If I understand correctly, you're saying using 2 for the generator is no less safe, in which case I can simply shift left for the exponential operation. It sounds too good to be true - is it? $\endgroup$
    – jnm2
    Jun 13, 2011 at 16:51
  • $\begingroup$ @Thomas, Doesn't using g=2 (instead of making g a full-size group element) reduce the cost of an exponentiation operation from x to about 2x/3, i.e., a 33% reduction in time to exponentiate? (Because about 2x/3 of the time x is taken on squarings, and x/3 is taken on multiplies; when you make g=2, the time for the multiplies goes to approximately zero.) Or am I confused? $\endgroup$
    – D.W.
    Jun 13, 2011 at 17:44
  • $\begingroup$ Thanks, @Thomas! Very helpful. (@jnm2: probably historical inertia, the defaults, lack of knowledge, and/or performance just doesn't matter enough for anyone to worry about it; I see this a lot in crypto.) $\endgroup$
    – D.W.
    Jun 16, 2011 at 18:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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