Elgamal Cryptographic System

 1. Elgamal Cryptographic System :

In 1984, T. Elgamal announced a public Key scheme based on discrete logarithms closely related to Diffie Hellman technique. This uses in some form in a number of standards including the digital signature(DSS) and the S/MIME e-mail standard. 

Global Public Elements q Prime number α α < q and α a primitive root of q.   Key Generation by Alice Select Private Key Xa Xa < q-1 Calculate Ya Ya = α^(Xa) mod q Public Key {q, α, Ya} Private Key Xa   Encryption by Bob with Alice’s Public Key Plaintext M < q Select random integer K K < q Calculate K K = (Ya)^k mod q Calculate C1 C1 = α^(k) mod q Calculate C2 C2 = kM mod q Ciphertext (C1, C2)   Decryption by Alice with Alice’s Private Key Ciphertext (C1, C2) Calculate k K = (C1)^(Xa) mod q Plaintext M = (C2k’) mod q

We can restate the elgamal process as follows, using above table. 

1. Bob generates a random integer k.

2. Bob generates a one-time k using Alice's public key components Ya, q, and k.

3. Bob encrypts k using the public key component α, yielding C1. C1 provides sufficient information for Alice to recover k.

4. Bob encrypts the plaintext message M using k.

5. Alice recovers k from C1 using her private key.

6. Alice uses k' (here k' = inverse of k) to recover the plaintext message C2. 

Thus, k function as a one-time key, used to encrypt and decrypt the message.