ElGamal Algorithm

ElGamal algorithm is one of public-key cryptography algorithm created by Taher ElGamal in 1984. Algorithm in the generally used for digital signatures, but later modified so that also could be used for encryption and description. ElGamal is used in security software developed by GNU, PGP programs and other security systems. The strength of this algorithm lies in the difficulty of calculating discrete logarithms.
ElGamal algorithm is not patentable. However, this algorithm is based on the algorithm Diffie - Hellman, so the algorithm patents Diffie - Hellman also include ElGamal algorithm. Due to patent the algorithm Diffie - Hellman ended in April 1997, the ElGamal algorithm can be implemented for commercial applications.
Quantities used in the ElGamal algorithm:
1. Prime numbers, p (not secret)
2. Random numbers, g (g <p) (not secret)
3. Random numbers, x (x <p) (confidential) 
4. M (plaintext) (confidential) 
5. a and b (ciphertext) (no secret)
  Procedures Creating Key Pairs
· Select an arbitrary prime number p.
· Select two random numbers, g and x, provided g <p and 1 ≤ x ≤ p - 2.
· Compute y = gx mod p.
Public key is y, the secret key is x. Value of g and p are not confidential and can be announced to members of the group.
Encryption
· Plaintext arranged into blocks m1, m2, ..., such that each block represents the value in the range 0 to p - 1.
· Select k random numbers, which in this case £ 0 k £ p - 1, such that k is relatively prime with p - 1.
· Each block is encrypted using the formula m
a = gk mod p
b = ykm mod p
Pairs a and b is the ciphertext for block a message m. Thus, the size twice the size plainteksnya ciphertext.
Decryption
To decrypt a and b use a secret key, x, and the plaintext m is obtained again by equation
m = b / ax mod p
Note that because
gkx º ax (mod p)
then
b / ax º ykm / ax
º gxkm / gxk
º m (mod p)
which means that the plaintext can be recovered from ciphertext pairs a and b.

Flowchart

Examples

Siti want to generate the key pair. Siti chose p = 2357, g = 2 and x = 1751. Then calculate:

y = gx mod p = 21 751 mod 2357 = 1185

So the public key (y = 1185, g = 2, p = 2357) and the corresponding private key (x = 1751, p = 2357).

Encryption

Suppose Ahmad wants to send palinteks m = 2035 (m value was still inside the interval [0, 2357-1]). Ahmad choose a random number k = 1520 (k values ​​are still in the interval [0, 2357-1]). Then calculate Ahmad

a = gk mod p = 21 520 mod 2357 = 1430

b = ykm mod p = 11851520 × 2035 mod 2357 = 697

Thus, the resulting ciphertext is (1430, 697). Ahmad send this ciphertext to Siti.

Decryption

Siti describe ciphertext of Ahmad by calculating as follows:

1/ax = (ax) - 1 = ap - 1 - x mod p = 1430605 mod 2357 = 872

m = b / ax mod p = 697 × 872 mod 2357 = 2035

The decrypted plaintext, 2035, the same plaintext sent by Ahmad.