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.

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?

share|improve this question
add comment

1 Answer

up vote 4 down vote accepted

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.

share|improve this answer
    
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 –  HiVoltRock Dec 16 '13 at 23:58
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.