In learning how DH works for cryptography applications, I'm coming across some confusing language. For starters, most of the time DH is discussed in the context of "generating" their shared secret. However, I'm also seeing that it can be used for encryption purposes as well (such as encrypting the shared secret using an ephemeral key).

As a concrete example, I'm trying to encrypt with the following formula:

y = mgabmod n

However, I'm having trouble finding how to decrypt based on that formula. What is the use case for that formula, and what is the decryption process?


To decrypt with this system, the decryptor first computes $g^{ab}$ (which he can do because he knows one of the two private exponents); then, he computes the modular inverse of $g^{ab}$; that is written as $(g^{ab})^{-1}$.

The modular inverse is defined the same way that the regular multiplicative inverse is defined in the reals (although there it is commonly referred to as the reciprocal): $b = a^{-1}$ is true iff $a\times b = 1$.

So, $(g^{ab})^{-1}$ is that value $x$ where $x \times g^{ab} \equiv 1 \bmod n$.

Modular inverses can be computed using the Extended Euclidean method; another method (which is usually more expensive, but not drastically so) that works if $n$ is prime is using the identity (for $n$ prime and $a \neq 0$):

$$a^{-1} \equiv a^{n-2} \bmod n$$

Once you have that, then the decryption can then be computed by a single modular multiplication:

$$m = y \times (g^{ab})^{-1} \bmod n$$

In addition: When using DH for encryption using the method you are using, it is more normally called ElGamal (after the person who first invented it); you might want to use that as the search term to look up more information on it.

In addition, there is a distinct (but generally better) alternative method for using the DH primitive to perform encryption; that is known as the Integrated Encryption Scheme; you might want to study that as well. One advantage that has is that it doesn't require a modular inverse to decrypt.

  • $\begingroup$ That's a pretty concise answer. Thank you. So ElGamal is basically just DH, only used for encryption in that manner? Interesting. I guess that would by why I had trouble searching for the answer $\endgroup$ – HiVoltRock Dec 16 '13 at 23:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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