Elgamal Cryptographic System

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

As with Diffie-Hellman, the global elements of ElGamal are a prime number $q$  and $\alpha$ , which is a primitive root of $q$. User $A$ generates a private/public key pair as follows:

1.Generate a random integer $X_A$ , such that $1 \lt X_A \lt q-1$.

2.Compute  $Y_A=\alpha ^{X_A} \pmod q$

3. A’s private key is $X_A$ ;A’s pubic key is $[q,\alpha, Y_A]$

Any user B that has access to A’s public key can encrypt a message as follows:

1. Represent the message $M$ as an integer in the range  $0 \le M \le q-1$. Longer messages are sent as a sequence of blocks, with each block being an integer less than $q$

2. Choose a random integer $k$ such that $1 \le k \le q-1$

3.Compute a one-time key $K=(Y_A)^k \pmod q$

4.Encrypt $M$ as the pair of integers $(C_1,C_2)$ , where

$C_1=\alpha^k  \pmod q$; $C_2=KM \pmod q$

User A recovers the plaintext as follows:

1. Recover the key by computing $K=(C_1)^{X_A} \pmod q$.

2.Compute $M=(C_2K^{-1} \pmod q$ 

We can restate the ElGamal process as follows, using Figure below

1. Bob generates a random integer $k$.

2. Bob generates a one-time key $K$ using Alice’s public-key components $Y_A, q,$ and $k$.

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

4. Bob encrypts the plaintext message $M$ using $K$.

5. Alice recovers $K$ from $C_1$ using her private key .

6. Alice uses $K^{-1}$ to recover the plaintext message from $C_2$.

Thus $K$, functions as a one-time key, used to encrypt and decrypt the message

Let us demonstrate why the ElGamal scheme works. First, we show how $K$ is recovered by the decryption process:

$K = (Y_A)^k \pmod q$    $K$ is defined during the encryption process

$K = (\alpha ^{X_A} \pmod q)^k \pmod q$ substitute using  $Y_A = \alpha ^{X_A} \pmod q$

$K = \alpha ^{kX_A} \pmod q$   by the rules of modular arithmetic

$K = (C_1)^{X_A} \pmod q$  substitute using $C_1 = \alpha ^k \pmod q$

Next, using $K$ , we recover the plaintext as

$C_2 = KM \pmod q$

$(C_2K^{-1}) \pmod q = KMK^{-1} \pmod q = M \pmod q = M$

Example:

For example, let us start with the prime field GF(19); that is, $q = 19.$ It has primitive roots {2, 3, 10, 13, 14, 15}. We choose $\alpha= 10.$

Alice generates a key pair as follows:
1.Alice chooses $X_A = 5.$
2.Then $Y_A = \alpha ^{X_A} \pmod q = 10^5 \pmod{19}= 3$

3.Alice’s private key is 5 and Alice’s public key is $\{q, \alpha, Y_A \} = \{19, 10, 3\}.$

Suppose Bob wants to send the message with the value $M = 17$. Then:

1.Bob chooses $k = 6.$
2.Then $K = (Y_A)^k \pmod q = 3^6 \pmod {19} = 729 \pmod {19} = 7.$
3.So
$C_1 = \alpha^k \pmod q = 10^6 \pmod {19}= 11$

$C_2 = KM \pmod q = 7 * 17 \pmod {19} = 119 \pmod{19} = 5$

4. Bob sends the ciphertext $(11, 5)$.

For decryption:

1.Alice calculates $K = (C_1)^{X_A }\pmod q = 11^5 \pmod {19} = 161051 \pmod {19}= 7$.
2.Then $K^{-1}$ in $GF(19)$ is $7^{-1} \pmod {19 }= 11.$
3.Finally,$M = (C_2K^{-1}) \pmod q = 5 * 11 \pmod {19}= 55 \pmod{19}= 17.$

If a message must be broken up into blocks and sent as a sequence of encrypted blocks, a unique value of $k$ should be used for each block. If $k$ is used for more than one block, knowledge of one block $M_1$ of the message enables the user to compute other blocks as follows. Let

$C_{1,1 }= \alpha^k \pmod q;\quad C_{2,1} = KM_1 \pmod q$

$C_{1,2 }= \alpha^k \pmod q;\quad C_{2,2} = KM_2 \pmod q$

Then, $$\frac{C_{2,1}}{C_{2,2}}= \frac{KM_1 \pmod q}{KM_2 \pmod q } = \frac{M_1 \pmod q }{M_2\pmod q}$$

If $M_1$ is known, then $M_2$ is easily computed as

$$M_2 = (C_{2,1})^{-1} C_{2,2}M_1 \pmod q$$

The security of Elgamal is based on the difficulty of computing discrete logarithms. To recover A’s private key, an adversary would have to compute $X_A = dlog_{\alpha,q}(Y_A)$. Alternatively, to recover the one-time key $K$, an adversary would have to determine the random number $k$, and this would require computing the discrete logarithm $k = dlog_{\alpha,q}(C_1)$. These calculations are regarded as infeasible if $q$ is at least 300 decimal digits and $q-1$ has at least one “large” prime factor.

Python code  - Elgamal Crypto System

import random

from sympy import mod_inverse 

# Function to calculate modular exponentiation

# Function to generate keys

def generate_keys(p, g):

    # Private key

    #xa = random.randint(1, p - 2)  # x < p-1

    xa=5

    # Public key

    ya = pow(g, xa, p)

    return (p, g, ya), xa  # (Public Key, Private Key)

# Function to encrypt a message

def encrypt(public_key, m):

    p, g, ya = public_key

    #k = random.randint(1, p - 2)  # k < p-1

    k=6

    K= pow(ya, k, p)

    c1=pow(g,k,p)

    c2=(K*m) %p

    return c1, c2

# Function to decrypt a message

def decrypt(private_key,p,cipher):

    xa=private_key

    c1=cipher[0]

    K=pow(c1,xa,p)

    K_inv=mod_inverse(K,p)

    c2 = cipher[1]

    m=(c2*K_inv) % p

    return m

# Example usage

if __name__ == "__main__":

    # Prime number p and generator g

    p = 19  # A prime number

    g = 10    # A generator for Z_p*

    # Generate keys

    public_key, private_key = generate_keys(p, g)

    print("Public Key:", public_key)

    print("Private Key:", private_key)

    # Message to be encrypted

    message = 17 # Message should be less than p

    print("Original Message:", message)

    # Encrypt the message

    cipher = encrypt(public_key, message)

    print("Encrypted Message:", cipher)

    # Decrypt the message

    decrypted_message = decrypt(private_key,p, cipher)

    print("Decrypted Message:", decrypted_message)

Output:

Public Key: (19, 10, 3) 

Private Key: 5 

Original Message: 17 

Encrypted Message: (11, 5) 

Decrypted Message: 17