The generation of an ElGamal key pair is comparatively simpler than the equivalent process for RSA. But the encryption and decryption are slightly more complex than RSA.
ElGamal Encryption
Suppose sender wishes to send a plaintext to someone whose ElGamal public key is (p, g, y), then −
- Sender represents the plaintext as a series of numbers modulo p.
- To encrypt the first plaintext P, which is represented as a number modulo p. The encryption process to obtain the ciphertext C is as follows −
- Randomly generate a number k;
- Compute two values C1 and C2, where −
C1 = gk mod p C2 = (P*yk) mod p
- Send the ciphertext C, consisting of the two separate values (C1, C2), sent together.
- Referring to our ElGamal key generation example given above, the plaintext P = 13 is encrypted as follows −
- Randomly generate a number, say k = 10
- Compute the two values C1 and C2, where −
C1 = 610 mod 17 C2 = (13*710) mod 17 = 9
- Send the ciphertext C = (C1, C2) = (15, 9).
ElGamal Decryption
- To decrypt the ciphertext (C1, C2) using private key x, the following two steps are taken −
- Compute the modular inverse of (C1)x modulo p, which is (C1)-x , generally referred to as decryption factor.
- Obtain the plaintext by using the following formula −
C2 × (C1)-x mod p = Plaintext
- In our example, to decrypt the ciphertext C = (C1, C2) = (15, 9) using private key x = 5, the decryption factor is
15-5 mod 17 = 9
- Extract plaintext P = (9 × 9) mod 17 = 13.
Leave a Reply