Elgamal is a public key scheme similar to the Diffie-Hellman (DH) cryptosystem.

Find below the steps of Elgamal scheme.

First, you have to generate your key-pair using the following steps:

- Choose a prime number q and a, such a is a primitive root of q
- Generate a random number X
_{A}, such that 1 < X_{A}< q-1 - Calculate Y
_{A}= a^{XA}mod q - Your private key X
_{A}, and your public key is {q,a,Y_{A}}

Now, anyone that has access to your public key can send you an encrypted message as follows:

- Choose your message M.
- Convert M to an integer m, where 0<=m<q. If the message is long enough and it cannot be represented with a number less than q-1, then the message is sent a sequence of blocks that can be converted into integers greater than 0 and less than q-1.
- Choose a random integer k, 0<k<q
- Calculate a one-time-key K = Y
_{A}^{k}mod q. - Encrypt M as a pair of integers (A,B) where A= a
^{k}mod q and B = KM mod q - Send the encrypted message as the pair (A,B)

When you receive the encrypted message (A,B), you will decrypt it as follows:

- Calculate the one-time K used to encrypt the message as K = A
^{XA}mod q - Calculate M = BK
^{-1}mod q

## Elgamal cryptosystem example

Let’s see an example with specific numbers, so you can get a better understanding on how this cryptosystem works.

### Generate your key-pair

- q=11, a=7. Notice 7 is a primitive root of 11
- X
_{A}= 5 - Y
_{A}= 10 - The private key 5 and the public key is {11,7,10}

### Message encryption

A user gets your public key {11,7,10} and encrypt message as follows:

- M=3
- k=7
- K = Y
_{A}^{k}mod q = 10^{7}mod 11 = 10 - A= a
^{k}mod q = 7^{7}mod 11 = 6 - B = KM mod q = 10 x 3 mod 11 = 8
- The encrypted message (6,8) is sent

### Message decryption

You received the encrypted message (6,8). Notice that A=6 and B=8. You also have your private key X_{A}=5

- Calculate K = A
^{XA}mod q = 6^{5}mod 11 = 10 - Calculate M = BK
^{-1}mod q = 8 x 10^{-1}mod 11 = 8×10 mod 11 = 3

So, M=3 is the encrypted message.

Notice that inverse modular inverse is not a straightforward calculation. In this case, you have to use the Extended Euclidean Algorithm.

You can check your calculation of modular inverse as follows:

a^{-1} mod n = x. Here the sign = means congruent.

ax = 1 mod n. Here the sign = means congruent.

## Applications of Elgamal cryptosystem

Two of the applications of this cryptosystem are:

**Related posts:**