ElGamal Cryptographic System
The ElGamal cryptosystem is an asymmetric encryption method that relies on the discrete logarithm problem.
A sender encrypts a message using the recipient’s public key and a random value, producing a pair of encrypted values.
Only the recipient, with their private key, can decrypt the original message. The system's security is grounded in the computational difficulty of solving the discrete logarithm problem.
How It Works
First, a finite field \( F_q \) and a generator \( g \) of the multiplicative group \( F_q^* \) are selected.
Each user \( A \) has two keys:
- Private Key: A randomly chosen secret integer \( a \) (\( 0 < a < q-1 \))
- Public Key: Computed as \( g^a \)
Encrypting the Message
If user \( B \) wants to send a message \( P \) to user \( A \), they follow these steps:
- Randomly select an integer \( k \), ensuring \( k < q \) and that a new \( k \) is chosen for each message.
- Calculate two values:
- \( y_1 = g^k \), derived from \( g \) and \( k \).
- \( y_2 = P \cdot g^{ak} \), which combines the message \( P \) with \( g^{ak} \), dependent on \( A \)'s public key \( g^a \). - Send the pair \( (y_1, y_2) \) to \( A \). This pair represents the encrypted message.
Decrypting the Message
When \( A \) receives \( (y_1, y_2) \), they can decrypt the original message \( P \) as follows:
- Raise \( y_1 \) to their private key \( a \): \( (y_1)^a = (g^k)^a = g^{ak} \)
- Compute the modular inverse of \( g^{ak} \), denoted \( (g^{ak})^{-1} \), and use it to retrieve \( P \): $$ P = y_2 \cdot (g^{ak})^{-1} $$
The system's security lies in the fact that intercepting \( y_1 \) and \( y_2 \) does not allow an attacker to compute \( g^{ak} \) without solving the discrete logarithm problem, which is computationally infeasible.
Additionally, even knowing \( g^a \) (the public key), it is practically impossible to determine \( a \) (the private key) without solving the same problem.
In summary, the encryption depends on \( g^{ak} \), which only those with \( A \)'s public key can compute. However, only \( A \), with their private key, can decrypt the message.
Note: Like other cryptographic systems (e.g., RSA), ElGamal is not unbreakable. Its security relies on the assumption that decrypting the message would require an impractical amount of computational power. However, advances in technology could make problems deemed unsolvable today feasible in the future.
A Practical Example
Let’s take an example where the field \( F_q \) is defined by a prime \( q = 23 \), and the generator is \( g = 5 \).
Note: These numbers are intentionally small for simplicity. Real-world implementations use numbers with hundreds of digits.
User \( A \) selects a private key \( a = 6 \), a random integer between \( 1 \) and \( q-1 \).
They calculate their public key \( g^a \mod q \):
$$ g^a = 5^6 \mod 23 = 15625 \mod 23 = 8 $$
Thus, \( A \)’s public key is \( (g = 5, g^a = 8) \).
Encrypting the Message
User \( B \) wants to send a message \( P = 15 \) to \( A \).
First, \( B \) chooses a random \( k \), for example, \( k = 3 \).
They calculate the first part of the encrypted pair:
$$ y_1 = g^k \mod q $$
$$ y_1 = 5^3 \mod 23 $$
$$ y_1 = 125 \mod 23 = 10 $$
Next, they compute the second part:
$$ y_2 = P \cdot g^{ak} \mod q $$
Using \( A \)’s public key \( g^a = 8 \):
$$ g^{ak} = (g^a)^k \mod q $$
$$ g^{ak} = 8^3 \mod 23 $$
$$ g^{ak} = 512 \mod 23 = 6 $$
Thus:
$$ y_2 = 15 \cdot 6 \mod 23 $$
$$ y_2 = 90 \mod 23 = 21 $$
Finally, \( B \) sends \( A \) the encrypted pair \( (y_1, y_2) = (10, 21) \).
Decrypting the Message
Upon receiving \( (y_1, y_2) \), \( A \) decrypts as follows:
First, compute \( (y_1)^a \mod q \):
$$ (y_1)^a = 10^6 \mod 23 $$
$$ (y_1)^a = 1000000 \mod 23 = 6 $$
Then, find the modular inverse of \( (y_1)^a \mod q \):
The modular inverse of \( 6 \mod 23 \) is \( 4 \), as \( 6 \cdot 4 \equiv 1 \mod 23 \).
Finally, retrieve the original message:
$$ P = y_2 \cdot ((y_1)^a)^{-1} \mod q $$
$$ P = 21 \cdot 4 \mod 23 $$
$$ P = 84 \mod 23 = 15 $$
The original message \( P = 15 \) is successfully decrypted by \( A \).
Why Is the Discrete Logarithm Hard to Solve?
The discrete logarithm problem is challenging due to the exponential growth of the search space in modular arithmetic.
In a problem like \( g^x \mod p = y \), even with \( g \), \( p \), and \( y \) known, finding \( x \) requires an exhaustive search among possible values of \( x \), which becomes computationally infeasible as \( p \) grows larger.
Currently, no efficient algorithms exist to solve this problem in polynomial time for large numbers typically used in cryptography.
Note: Techniques like baby-step giant-step or the Number Field Sieve can solve the problem for smaller values of \( p \) but are impractical for large primes used in secure systems.
Carefully choosing \( p \) (e.g., a large prime) ensures the multiplicative group \( F_p^* \) has properties that further increase the problem's difficulty.
This creates a computational asymmetry in operations.
While computing \( g^x \mod p \) is efficient, reversing the operation to find \( x \) is computationally prohibitive, making it ideal for cryptographic applications.
However, it’s worth noting that the problem is not inherently impossible, just "computationally difficult" with current tools.
New algorithms or advancements in technology, such as quantum computing, could make this problem solvable in the future.
And so on.
