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.

I am trying to read up on the math behind DH and ran into the word generator used a lot. I am not sure what it means. Can someone explain?

I see this question where the OP talks about g as the generator. The accepted answer does not make me understand what a generator is. I always thought g is just a large prime in group. What is the generator and how is it different from the DH parameters?

share|improve this question
    
Look up 'generator of a cyclic group' –  figlesquidge May 15 at 21:32

1 Answer 1

up vote 7 down vote accepted

A generator of a finite group is a value $g$ such that all elements of the group can be represented as $g^k$ for some integer $k$. Another key of looking at it is that if we consider the sequence $g,\ \ g \cdot g,\ \ g \cdot g \cdot g, ...$, saying $g$ is a generator means that all values in the group will appear somewhere in the sequence.

Now, when it comes to Diffie-Hellman, generator is used in two slightly different meanings (and that may be what is confusing you).

In the first meaning, a "generator" is defined to be an element that generates the entire group. That is, when we talk about DH (and thus the group $\mathbb{Z}_p^*$), we say that $g$ generates the entire group means $g^k \bmod p$ can take on any value between 1 and $p-1$.

In the second meaning, we say that an element $g$ "generates" a subgroup. That is, when we consider all the possible values $g^k \bmod p$, those possible values also form a group (which may be $\mathbb{Z}_p^*$, and may be a strictly smaller group), and it makes sense to consider the Diffie-Hellman operation over this subgroup. In this case, we may call $g$ the "generator" (even if it doesn't generate the full group). Now, this doesn't denote anything special about $g$ (because all elements generate some subgroup by this meaning), instead we call $g$ the generator to denote that it's the element we have chosen to use.

As I pointed out in my answer to the cited question, using a "generator" for the entire group is often not wise; it often makes more sense to deliberately use an element that generates a prime-sized subgroup.

As to whether $g$ itself is prime or not, well, that's actually not very relevant. After all, $g$ is actually a member of $\mathbb{Z}_p^*$; whether it corresponds to a prime when it is mapped into $\mathbb{Z}$ using the obvious mapping is not that important.

share|improve this answer

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.