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
  4. Your private key XA, and your public key is {q,a,YA}

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

  1. Choose your message M.
  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.

Generate your key-pair

  • 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:

Recent posts