Assume the case, that two participants have agreed on a key $K=g^{ab} \mod p$ via Diffie Hellman. I have the need to change the key every now and then. The first idea I had was to simply initiate a new agreement, so both chose another exponent, so the new key would be $K'=g^{a'b'}\mod p$.

I wonder if it would be also a secure method to just change the generator, so that $K'=h^{ab}\mod p$. Is there something I've overlooked (as I am a newbie to number theory), that would make this a bad approach?

  • 1
    $\begingroup$ Why do you want to change the key? In your question it sounds like you change keys for changes sake. $\endgroup$ Sep 2, 2013 at 14:07
  • $\begingroup$ How would you get your partners public key with respect to the new generator? $\endgroup$ Sep 2, 2013 at 14:07
  • $\begingroup$ The reason I want to change the key is, that I want to use K to derive a symmetric key from it and encrypt a file with it. The file will change and it will be reencrypted with the current symmetric key. I wanted to tackle the problem, that an attacker would get an amount of ciphertext for the same key for cryptoanalysis and breaking the encryption. So I thought, changing the agreed key between the both parties every now and then would be beneficial. $\endgroup$
    – LostAvatar
    Sep 2, 2013 at 17:28
  • 2
    $\begingroup$ "that an attacker would get an amount of ciphertext for the same key for cryptoanalysis and breaking the encryption." As long as you use strong encryption, you shouldn't worry about that. The added complexity is a far greater risk than AES getting broken. But if you insist, you should HKDF with different info strings on the shared key to derive the individual keys instead of re-running DH. Or, my preferred way of encrypting files, use a new random key for each file, and encrypt that key with the master key. $\endgroup$ Sep 2, 2013 at 17:35
  • $\begingroup$ "The file will change and it will be reencrypted with the current symmetric key". This problem is fixed by using the correct mode of operation for this kind of problem, you do not need to change the key. $\endgroup$ Sep 3, 2013 at 6:58

2 Answers 2


There are a bunch of issues involved with this question; the bottom line is that it while it wouldn't be a bad approach from a cryptographical standpoint, it appears to be more costly than the standard approach.

Let us first examine the number theory issues: the first question to ask is "does $g$ generate a large prime subgroup of $Z/p$?". That is, does $g^x \bmod p$ take on a prime number of distinct values (depending on $x$), and that prime number is fairly large? If that's not true, you need to change your values of $p$ and $g$ so that it is true. If you need a suggestion about what group to use, I always point people here; this gives a number of precomputed groups that are well designed.

Now the good news: as long as you're working in a prime subgroup, it doesn't matter which generator you're using; all elements of the subgroup (other than 1) generate the entire subgroup and (here's the best part) none are weaker as far as Diffie-Hellman is concerned. To be more precise; if someone can solve the computational Diffie-Hellman problem with a generator $h$ (that is, given $h^a$ and $h^b$, compute $h^{ab}$), then he can solve the Diffie-Hellman problem with generator $g$; hence if $h$ is weak, then $g$ turns out to be weak as well.

Now, let us examine another issue: why are you rekeying in the first place? What security properties do you hope hold for the new keys? Do you hope to get Perfect Forward Secrecy (PFS, that is, if someone happens to get hold of the entire cryptographical state on one of the two sides at some point, they are still unable to obtain the new keys)?

If you are changing keys simply because that's good cryptographical practice (and don't care about PFS), there are a number of ways to do this securely. We generally don't bother recomputing a public key operation (which is expensive); instead, what we generally do is use a Key Derivation Function to convert the DH shared secret (and some public nonces exchanged by the two parties) into the actual keying material we use; when we want to change keys, we just rerun the Key Derivation function with different nonces (possibly exchanged that that time); and we have new keys which are cryptographically unrelated to the previous keys.

On the other hand, if we want to get PFS, the recomputing the Key Derivation Function doesn't work (because an attacker with the previous state can do that as well); to do that, we generally do another DH exchange; that gives us PFS because we select new secret exponents at the time of the exchange; someone learning the state previous to that doesn't learn the secret exponents, and hence cannot learn the new keys).

We might consider doing a virtual DH exchange with another generator; the issue is "where does $h$ come from, and do we know the value $x$ such that $h = g^x$? Note that they may appear to be a Discrete Log problem, however we may know the value $x$ by selecting that first, and then computing $h = g^x$.

If we know such the value $x$, then both sides can compute ${(g^{ab})}^x = h^{ab}$. However, if both sides can compute it, so can the attacker (who learns the previous cryptographical state), and so you don't achieve PFS. If you don't need PFS, this works, however rerunning a Key Derivation Function is rather cheaper than doing another modular exponentiation.

If we don't know such a value $x$, then both sides would need to compute $h^a$, $h^b$ and exchange them; effectively doing another Diffie-Hellman operation. However, in contrast to an independent Diffie-Hellman operation, both sides must retain their $a$, $b$ values; and so an attacker learning the cryptographical state would learn one of those values, and so you don't achieve PFS. Now, you could have the two sides discard their $a$, $b$ values, and select new ones; at this point, you're doing the traditional Diffie-Hellman, except you're changing generators; that isn't harmful, but doesn't appear to gain you any benefits either.

So, the bottom line is that if you need Perfect Forward Secrecy, your proposal doesn't do it; if you don't need Perfect Forward Secrecy, there are cheaper ways to do it.

  • $\begingroup$ Pleas see my comment on the question for the reason to change the key $\endgroup$
    – LostAvatar
    Sep 2, 2013 at 17:29

How are the exponents $a$ and $b$ selected?

In case they are private/public keys of the two users then changing the generator will change $a$ or $b$ as well.


Your Answer

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

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