Just Cryptography

Learn Cryptography and Information Security

Home » Blog » What is Elgamal Cryptographic System?

# What is Elgamal Cryptographic System?

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:

1. Choose a prime number q and a, such a is a primitive root of q
2. Generate a random number XA, such that 1 < XA < q-1
3. Calculate YA = aXA mod q

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

2. 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.
3. Choose a random integer k, 0<k<q
4. Calculate a one-time-key K = YAk mod q.
5. Encrypt M as a pair of integers (A,B) where A= ak mod q and B = KM mod q
6. 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 = AXA 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.

• q=11, a=7. Notice 7 is a primitive root of 11
• XA = 5
• YA= 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 = YAk mod q = 107 mod 11 = 10
• A= ak mod q = 77 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 XA=5

• Calculate K = AXA mod q = 65 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: