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.

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?

share|improve this question
add comment

migrated from security.stackexchange.com Sep 6 '11 at 20:51

This question came from our site for Information security professionals.

1 Answer

up vote 16 down vote accepted

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

share|improve this answer
1  
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? –  jnm2 Jun 13 '11 at 16:51
    
@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? –  D.W. Jun 13 '11 at 17:44
    
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.) –  D.W. Jun 16 '11 at 18:35
add comment

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.