ELGAMAL CIPHER

Elgamal is a public-key cryptographic scheme introduced by T. Elgamal in 1984, leveraging discrete logarithms, closely related to the Diffie-Hellman technique. It is widely employed in standards such as the Digital Signature Standard (DSS) and the S/MIME email standard.

Example:

Given:

• p = 23,
• g = 5 (publicly known)
• Private Key a is randomly chosen
• Public Key A is calculated as A = g^a mod p
• Original Message: 15

Encryption:

1. Choose a random k, compute B = g^k mod p, calculate s = A^k mod p
2. Compute c1 = g^k mod p and c2 = (plaintext * s) mod p
3. The ciphertext is (c1, c2).

Decryption:

1. Compute s = c1^a mod p, calculate s^-1 = s^-1 mod p
2. Decrypt the message using decrypted_text = (c2 * s^-1) mod p