readme.md

title	tags
Milestone 03. ElGamal Algorithm	zk basic cryptography elgamal

WTF zk Tutorial Milestone 03: ElGamal Algorithm

In this lesson, we will introduce the ElGamal encryption and signature algorithms. ElGamal is a public key cryptography algorithm based on the difficulty of computing discrete logarithms. It was proposed by ElGamal in 1985 and extended the Diffie-Hellman key exchange algorithm to the field of encryption and digital signatures.

1. ElGamal Encryption Algorithm

The ElGamal algorithm is a public key cryptography algorithm that relies on the difficulty of computing discrete logarithms. The ElGamal algorithm consists of two parts: encryption and digital signatures. Let's take a look at the encryption algorithm.

Assume that Alice wants to communicate with Bob using the ElGamal algorithm.

1.1 Key Generation

Bob's key generation using the ElGamal algorithm includes the following steps:

1. Choose a large prime number $p$: Choose a sufficiently large prime number $p$ as the modulus of $Z^_p$. According to the existence of primitive elements, $Z^_p$ is a cyclic group with a primitive element.
2. Choose a primitive element $g$: Choose a primitive element $g$ modulo $p$. At this time, the order of $g$ is $p-1$, and the discrete logarithm problem is difficult.
3. Choose a private key $x$: Randomly choose a private key $x$, $1 < x < p$.
4. Compute the public key $y$: Compute the public key $y = g^x \mod p$.

In the end, the public key is $(p, g, y)$, which is made public; the private key is $x$, which is kept private.

1.2 Encryption

After obtaining the public key $(p, g, y)$, Alice uses the ElGamal encryption as follows:

1. Choose a random number $k$: Randomly choose a $k$, $1 < k < p$.
2. Compute the temporary public key $a$ and the temporary ciphertext $b$: Compute $a \equiv g^k \mod p$ and $b \equiv y^k \cdot M \equiv g^{xk} \cdot M \mod p$, where $M$ is the plaintext message to be encrypted.
3. Ciphertext: The ciphertext is $(a, b)$, which is made public.

The random number $k$ will change with each encryption, ensuring that the ElGamal algorithm will output different temporary ciphertexts even if the same plaintext is encrypted. In the encryption operation, the private key $x$ and the random number $k$ are kept private, while the public key $(p, g, y)$ and the ciphertext $(a, b)$ are made public.

1.3 Decryption

After receiving the ciphertext $(a, b)$, Bob decrypts it using the ElGamal decryption process:

1. Compute the shared key $s$: Compute $s \equiv a^x \mod p$.
2. Compute the modular inverse $s^{-1}$.
3. Restore the plaintext $M$: Restore the plaintext $M \equiv b \cdot s^{-1} \mod p$. Because $b \cdot s^{-1} = b \cdot a^{-x} = g^{xk} \cdot M \cdot g^{-xk} = M$.

The ElGamal algorithm ingeniously allows $b \cdot s^{-1}$ to restore the original plaintext, and calculating $s$ requires knowledge of the private key $x$. Without the private key, an eavesdropper would have to solve the discrete logarithm problem (which cannot be solved) in order to obtain the plaintext.

1.4 Example

Let's illustrate the ElGamal encryption algorithm with a simple example.

Assume that $p = 13$, $g = 6$ is a primitive element of $p$, $x = 4$ is the private key, and $y = g^x = 9$ is the public key. After key generation, Bob makes $(p, g, y)$ public.

Now, Alice wants to encrypt the message $M = 5$. Alice randomly chooses $k = 7$ (note that it must be coprime to $p$) and calculates:

1. Temporary public key $a \equiv 6^{7} \equiv 7 \pmod{13}$.
2. Temporary ciphertext $b \equiv 9^{7} \cdot 5 \equiv 6 \pmod{13}$.

Therefore, the ciphertext is $(7, 6)$.

Next, Bob receives the ciphertext and decrypts it:

1. Compute the shared key $s \equiv 7^{4} \equiv 9 \pmod{13}$.
2. Compute the modular inverse $s^{-1} \equiv 9^{-1} \equiv 3 \pmod{13}$.
3. Restore the plaintext $M \equiv 6 \cdot 3 \equiv 5 \pmod{13}$.

In the end, Bob successfully decrypts and restores the original message $M = 5$.

2. ElGamal Signature Algorithm

Before introducing the algorithm, let's first understand what a digital signature is. In traditional industries, people sign paper contracts with handwritten signatures, which have legal effects. A digital signature is a technology used to ensure the integrity of digital information, authenticate the identity of the sender, and prevent denial. A digital signature generates a unique identifier (signature) attached to a message or document using encryption algorithms. This digital signature can be verified to confirm that the message was generated by a specific sender and has not been tampered with during transmission.

Digital signatures typically involve two key components: private keys and public keys. The sender uses the private key to sign the message, and the recipient uses the public key to verify the validity of the signature. This method is based on asymmetric encryption, where the private key is used for signature generation and the public key is used for signature verification.

Digital signatures have the following key properties:

1. Identity authentication: Proving that the signer is the holder of the private key.
2. Non-repudiation: The sender cannot deny sending the message.
3. Integrity: By verifying the digital signature generated for the transmitted message, it can be determined whether the message has been tampered with during transmission.

Similar to the ElGamal encryption algorithm, the ElGamal signature algorithm also uses the difficulty of the discrete logarithm problem to ensure the security of the signature. The algorithm is mainly divided into three steps: key generation, signature generation, and signature verification. Let's demonstrate with Alice (the signer) and Bob (the verifier).

2.1 Key Generation

Alice generates a key for signing:

1. Choose parameters: Choose a large prime number $p$ and a primitive element $g$.
2. Generate a private key: Randomly choose a private key $x$, with $1 < x < p-1$.
3. Compute the public key: Compute the public key $y \equiv g^x \pmod{p}$.

The key generation steps are the same as the ElGamal encryption algorithm, and the final public key is $(p, g, y)$, which is made public; the private key is $x$, which is kept private.

2.2 Signature Generation

Alice uses the private key and the hash of the message to generate a signature:

1. Choose a random number: Randomly choose an integer $k$, ensuring that $1 < k < p-1$ and $gcd(k, p-1) = 1$. This is because we will later calculate $k^{-1} \pmod{p-1}$, which requires the existence of the inverse element of $k$ modulo $p-1$.
2. Compute the intermediate value $r$: Compute $r \equiv g^k \pmod{p}$.
3. Compute the signature: Compute $s \equiv k^{-1}(H(M) - xr) \pmod{p-1}$, where $H(M)$ is the hash value of the message. Note that the modulus used here is $p-1$.

If $s=0$, then we need to re-generate a random number $k$ and calculate again. Originally, the paper used the message $M$ itself instead of the hash $H(M)$, but this would bring security issues. The final signature is $(r, s)$, which is made public.

2.3 Signature Verification

Bob can use the public information $(g, p, r, s, M)$ to verify the authenticity of the signature.

1. Verify parameters: If $0 < r < p$ and $0 < s < p-1$ are satisfied, proceed to the next step.
2. Verify the signature: If $g^{H(M)} \equiv y^rr^s \pmod{p}$ holds, then the signature is valid.

Because $y^rr^s = g^{xr}r^{s} = g^{xr}g^{ks} = g^{xr+ks}$, and $xr+ks = xr +k(k^{-1}(H(M) - xr)) = H(M) \pmod{p-1}$. Therefore, if $g^{H(M)} \equiv y^rr^s \pmod{p}$, that is, $xr+ks = H(M) \pmod{p-1}$ holds, then the signature is valid.

2.4 Example

Let's illustrate the ElGamal signature algorithm with a simple example. Suppose we already have a key pair $(p, g, x, y)$, where $p = 13$, $g = 6$, $x = 4$, $y = 9$, and the hash of the message is $H(M) = 5$.

During signing, we randomly choose $k = 7$, which is relatively prime to $p-1 = 12$, and calculate:

1. Temporary value $r \equiv 6^7 \equiv 7 \mod 13$.
2. Compute $s \equiv 7^{-1} \cdot (5 - 4 \cdot 7) \equiv 7 \mod 12$.

Therefore, the signature is $(7, 7)$.

Next, we verify whether the signature is valid:

Calculating $g^{H(M)} \equiv y^rr^s \pmod{p}$ is complicated, so we can directly verify whether $xr+ks = H(M) \mod 12$ holds. $xr+ks = 4 \times 7 + 7 \times 7 = 77 = 5 = H(M) \mod 12$, and $g^{5} \equiv g^{77} \equiv 2 \pmod{13}$. Therefore, the signature is valid.

3. Code Implementation

3.1 ElGamal Encryption Algorithm

## ElGamal Encryption Algorithm

from random import randint
from sympy import isprime, mod_inverse

def generate_keys():
    # Generate the large prime number p and the primitive element g
    while True:
        p = randint(1000, 2000)
        if isprime(p):
            break
    g = randint(2, p-1)

    # Private key x
    x = randint(1, p-2)

    # Public key y
    y = pow(g, x, p)

    return (p, g, y), x

def encrypt(public_key, message):
    p, g, y = public_key
    k = randint(1, p-2)

    # Encryption
    C1 = pow(g, k, p)
    C2 = (message * pow(y, k, p)) % p

    return (C1, C2)

def decrypt(private_key, p, ciphertext):
    C1, C2 = ciphertext
    a = private_key

    # Decryption
    s = pow(C1, a, p)
    m = (C2 * mod_inverse(s, p)) % p

    return m

# Example
public_key, private_key = generate_keys() # Generate keys
message = 123  # Plaintext message
ciphertext = encrypt(public_key, message) # Ciphertext
decrypted_message = decrypt(private_key, public_key[0], ciphertext) # Decryption

print("Public key (p, g, y):", public_key)
print("Private key x:", private_key)
print("Plaintext message:", message)
print("Ciphertext:", ciphertext)
print("Decrypted plaintext:", decrypted_message)

## Output Example
# Public key (p, g, y): (1307, 643, 698)
# Private key x: 11
# Plaintext message: 123
# Ciphertext: (690, 1225)
# Decrypted plaintext: 123

3.2 ElGamal Signature Algorithm

## ElGamal Signature Algorithm

from sympy import gcd

def generate_keys_signature():
    # Same as the ElGamal encryption algorithm
    return generate_keys()

def sign(private_key, p, g, message):
    while True:
        k = randint(1, p-1)
        if gcd(k, p-1) == 1:  # k is coprime to p-1
            break

    r = pow(g, k, p)
    x = private_key
    s = ((message - x * r) * mod_inverse(k, p-1)) % (p-1)

    return (r, s)

def verify(public_key, p, g, message, signature):
    y = public_key[2]
    r, s = signature

    if not (0 < r < p) or not (0 < s < p-1):
        return False

    return pow(g, message, p) == (pow(y, r, p) * pow(r, s, p)) % p

# Example
public_key, private_key = generate_keys_signature() # Generate keys
message = 123  # Plaintext message
signature = sign(private_key, public_key[0], public_key[1], message) # Generate signature
verification_result = verify(public_key, public_key[0], public_key[1], message, signature) # Verify signature

public_key, private_key, signature, verification_result

print("Public key (p, g, y):", public_key)
print("Private key x:", private_key)
print("Plaintext message:", message)
print("Signature:", signature)
print("Verification result:", verification_result)

## Output Example
# Public key (p, g, y): (1409, 853, 1193)
# Private key x: 1035
# Plaintext message: 123
# Signature: (1126, 1403)
# Verification result: True

4. Summary

In this lesson, we introduced the ElGamal algorithm, which extends the ideas of the Diffie-Hellman algorithm to the fields of encryption and digital signatures. Like the Diffie-Hellman algorithm, the security of the ElGamal algorithm is also based on the difficulty of the discrete logarithm problem.

Thought question: Why is the calculation of the signature $s$ in the ElGamal signature algorithm performed modulo $p-1$?