Chapter 29: The ElGamal Cryptosystem (SageMath)#
Python Version Available
This notebook contains the SageMath implementation. A pure Python/NumPy version is available in Chapter 29: The ElGamal Cryptosystem.
29.1 Introduction: From Key Exchange to Public-Key Encryption#
In 1985, Taher ElGamal, an Egyptian-American cryptographer working at Hewlett-Packard, published a paper titled “A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms” in the proceedings of CRYPTO ‘84. This paper demonstrated that the Diffie–Hellman key exchange (Chapter 28) could be transformed into a full public-key encryption scheme and a digital signature scheme.
The insight was elegant: if computing discrete logarithms in a cyclic group \(G = \langle g \rangle\) of order \(q\) is hard, then the tuple \((g, g^x, g^k)\) reveals nothing useful about \(g^{xk}\) to a passive adversary. This decisional Diffie–Hellman assumption (DDH) underpins the semantic security of ElGamal encryption.
The ElGamal cryptosystem has had enormous practical impact:
PGP/GPG: Phil Zimmermann’s Pretty Good Privacy adopted ElGamal encryption as one of its core public-key algorithms, making it a cornerstone of email encryption worldwide.
DSA: The Digital Signature Algorithm, standardized by NIST in 1991 (FIPS 186), is a variant of ElGamal’s signature scheme. DSA was the first digital signature standard adopted by the US government.
Homomorphic properties: ElGamal’s multiplicative homomorphism makes it useful in electronic voting protocols, mix-nets, and zero-knowledge proofs.
Randomized encryption: Unlike RSA (which is deterministic in its textbook form), ElGamal is inherently randomized – the same plaintext encrypts to different ciphertexts each time. This property is essential for achieving semantic security.
Tip
From key exchange to encryption. The conceptual leap from Diffie–Hellman to ElGamal is this: instead of both parties contributing ephemeral secrets, the sender chooses a random ephemeral key \(k\), computes a shared secret \(s = h^k\) (where \(h = g^x\) is the recipient’s public key), and uses \(s\) to mask the message. The recipient recovers \(s\) using their private key \(x\). This “one-sided Diffie–Hellman” is the heart of ElGamal.
29.2 Formal Definitions#
We work in the multiplicative group \(\mathbb{Z}_p^*\) where \(p\) is a large prime. In practice, one often works in a prime-order subgroup of \(\mathbb{Z}_p^*\) for security reasons, but the basic scheme operates as follows.
Definition 29.1 (ElGamal Key Generation)
Choose a large prime \(p\) and a generator \(g\) of the cyclic group \(\mathbb{Z}_p^* = \{1, 2, \ldots, p-1\}\) (or a generator of a prime-order subgroup of order \(q\)).
Choose a private key \(x\) uniformly at random from \(\{1, 2, \ldots, p-2\}\).
Compute the public key component \(h = g^x \bmod p\).
Public key: \((p, g, h)\). Private key: \(x\).
Definition 29.2 (ElGamal Encryption)
To encrypt a message \(m \in \{1, 2, \ldots, p-1\}\) using the recipient’s public key \((p, g, h)\):
Choose a random ephemeral key \(k\) uniformly from \(\{1, 2, \ldots, p-2\}\).
Compute:
\[ c_1 = g^k \bmod p \]\[ c_2 = m \cdot h^k \bmod p\]The ciphertext is the pair \((c_1, c_2)\).
The value \(s = h^k \bmod p\) is the shared secret (an ephemeral Diffie–Hellman shared value). The message is masked by multiplying with \(s\).
Definition 29.3 (ElGamal Decryption)
To decrypt a ciphertext \((c_1, c_2)\) using the private key \(x\):
Compute the shared secret: \(s = c_1^x \bmod p\).
Compute the modular inverse: \(s^{-1} \bmod p\).
Recover the message: \(m = c_2 \cdot s^{-1} \bmod p\).
Alternatively, one can compute \(s^{-1} = c_1^{p-1-x} \bmod p\) using Fermat’s little theorem, avoiding an explicit inverse computation.
Definition 29.4 (ElGamal Signature Scheme)
To sign a message \(m\) using the private key \(x\) and public parameters \((p, g, h)\):
Choose a random \(k\) with \(\gcd(k, p-1) = 1\).
Compute \(r = g^k \bmod p\).
Compute \(s = (m - x \cdot r) \cdot k^{-1} \bmod (p-1)\).
The signature is \((r, s)\).
Verification: Accept the signature if \(g^m \equiv h^r \cdot r^s \pmod{p}\).
Theorem 29.1 (ElGamal Correctness)
Encryption correctness. For any message \(m\), if \((c_1, c_2)\) is a valid ElGamal ciphertext, then decryption recovers \(m\):
Signature correctness. For a valid signature \((r, s)\) on message \(m\):
Proof
Encryption: We have \(c_1 = g^k\) and \(c_2 = m \cdot h^k = m \cdot g^{xk}\). The decryptor computes \(s = c_1^x = g^{kx}\) and then \(c_2 \cdot s^{-1} = m \cdot g^{xk} \cdot g^{-xk} = m\). \(\blacksquare\)
Signature: We have \(r = g^k\) and \(s = (m - xr)k^{-1} \bmod (p-1)\), so \(ks = m - xr \bmod (p-1)\). Therefore \(h^r \cdot r^s = g^{xr} \cdot g^{ks} = g^{xr + ks} = g^{xr + m - xr} = g^m \pmod{p}\) by Fermat’s little theorem. \(\blacksquare\)
29.3 Security Foundations#
Semantic Security and Randomized Encryption
A public-key encryption scheme is semantically secure (IND-CPA) if no efficient adversary, given a public key and a ciphertext, can determine any partial information about the plaintext beyond its length.
ElGamal achieves semantic security under the Decisional Diffie–Hellman (DDH) assumption: given \((g, g^a, g^b, Z)\), it is computationally hard to determine whether \(Z = g^{ab}\) or \(Z\) is a random group element.
The crucial feature enabling semantic security is randomized encryption: each encryption uses a fresh random \(k\), so the same plaintext \(m\) produces a different ciphertext \((g^k, m \cdot h^k)\) each time. This is in stark contrast to textbook RSA, where \(\text{Enc}(m) = m^e \bmod n\) is deterministic.
Danger
Never reuse the ephemeral key \(k\). If two messages \(m_1, m_2\) are encrypted with the same \(k\), an attacker who knows \(m_1\) can recover \(m_2\):
This is exactly the vulnerability that led to the PlayStation 3 ECDSA key compromise in 2010 – Sony reused the random nonce \(k\) in their signature scheme.
Ciphertext expansion. ElGamal has a 2:1 ciphertext expansion ratio: each message element \(m\) produces a ciphertext pair \((c_1, c_2)\), doubling the data size. This is the price paid for randomized encryption and is an inherent cost of any IND-CPA-secure scheme.
29.4 Implementation in SageMath#
We implement the ElGamal cryptosystem using SageMath’s built-in number theory functions: power_mod() for modular exponentiation, inverse_mod() for modular inverses, factor() for integer factorization, is_prime() for primality testing, and primitive_root() for finding generators.
Key Generation#
The key generation algorithm finds a generator of \(\mathbb{Z}_p^*\) by factoring \(p-1\) and uses it to build a public/private key pair. The following FindGen implementation is taken verbatim from the original SageMath course material – it uses factor() to decompose \(p-1\) and constructs a generator from the Chinese Remainder Theorem on prime-power cyclic subgroups.
#implementation of the key
def FindGen(p):
fact=(p-1).factor()
gammali=[]
for i in range(0,len(fact)):
b=1
while b==1:
a=randint(1,p-1)
b=power_mod(a,(p-1)//fact[i][0],p)
gammali+=[power_mod(a,(p-1)//(fact[i][0]**fact[i][1]),p)]
gamma=prod(gammali)%p
return gamma
def PublicPrivateKey(p): #assume here that p is a prime number
g=FindGen(p)
q=p-1
x=randint(1,q-1)
h=power_mod(g,x,p)
return x,(p,q,g,h)
AlicePrivateKey, AlicePublicKey = PublicPrivateKey(11)
print("Alice's private key:", AlicePrivateKey)
print("Alice's public key (p, q, g, h):", AlicePublicKey)
Alice's private key: 6
Alice's public key (p, q, g, h): (11, 10, 7, 4)
Message Encoding#
We assume that there exists a bijection of the message space \(\mathcal{M}\) onto a subset of \(G\). Hence we can identify each message \(M\) with an element \(m \in G\).
Complete ElGamal Class#
Below is a complete ElGamal class for SageMath supporting key generation, encryption, decryption, digital signatures, and verification. It uses power_mod(), inverse_mod(), factor(), is_prime(), and gcd() throughout – replacing all NumPy and pure-Python equivalents from the Python version.
def find_generator_sage(p):
"""
Find a generator (primitive root) of Z_p^* for prime p.
Uses SageMath's factor() to find prime factors of p-1, then
constructs a generator via the CRT approach (original course algorithm).
"""
fact = (p - 1).factor()
gammali = []
for i in range(len(fact)):
b = 1
while b == 1:
a = randint(1, p - 1)
b = power_mod(a, (p - 1) // fact[i][0], p)
gammali += [power_mod(a, (p - 1) // (fact[i][0]^fact[i][1]), p)]
gamma = prod(gammali) % p
return gamma
class ElGamal:
"""
ElGamal public-key cryptosystem over Z_p^* (SageMath implementation).
Supports encryption, decryption, digital signatures, and verification.
Uses SageMath builtins: power_mod(), inverse_mod(), factor(), is_prime().
"""
def __init__(self, bits=32, p=None, g=None, seed=None):
if seed is not None:
set_random_seed(seed)
if p is not None:
assert is_prime(p), f"{p} is not prime"
self.p = ZZ(p)
else:
self.p = self._generate_prime(bits)
if g is not None:
self.g = ZZ(g)
else:
self.g = find_generator_sage(self.p)
# Key generation
self.x = randint(2, self.p - 2) # private key
self.h = power_mod(self.g, self.x, self.p) # public key component
def _generate_prime(self, bits):
"""Generate a random prime of approximately `bits` bits."""
while True:
candidate = ZZ(randint(2^(bits - 1), 2^bits - 1))
if is_prime(candidate):
return candidate
@property
def public_key(self):
"""Return the public key tuple (p, g, h)."""
return (self.p, self.g, self.h)
@property
def private_key(self):
"""Return the private key x."""
return self.x
def encrypt(self, m, k=None):
"""
Encrypt a message m in {1, ..., p-1}.
Parameters
----------
m : int
The plaintext message (must be in {1, ..., p-1}).
k : int, optional
Ephemeral key (random if not specified). WARNING: never reuse k.
Returns
-------
tuple (c1, c2) : the ciphertext pair.
"""
assert 1 <= m < self.p, f"Message must be in [1, {self.p - 1}]"
if k is None:
k = randint(2, self.p - 2)
c1 = power_mod(self.g, k, self.p)
s = power_mod(self.h, k, self.p) # shared secret
c2 = (m * s) % self.p
return (c1, c2)
def decrypt(self, c1, c2):
"""
Decrypt a ciphertext (c1, c2) using the private key.
Uses inverse_mod() for the modular inverse of the shared secret.
"""
s = power_mod(c1, self.x, self.p) # shared secret
s_inv = inverse_mod(s, self.p) # s^(-1) mod p
m = (c2 * s_inv) % self.p
return m
def sign(self, m):
"""
Sign a message m using the ElGamal signature scheme.
Returns
-------
tuple (r, s) : the signature.
"""
p1 = self.p - 1
while True:
k = randint(2, p1 - 1)
if gcd(k, p1) == 1:
break
r = power_mod(self.g, k, self.p)
k_inv = inverse_mod(k, p1)
s = ((m - self.x * r) * k_inv) % p1
return (r, s)
def verify(self, m, r, s):
"""
Verify an ElGamal signature.
Returns True if g^m == h^r * r^s (mod p).
"""
if not (0 < r < self.p):
return False
lhs = power_mod(self.g, m, self.p)
rhs = (power_mod(self.h, r, self.p) * power_mod(r, s, self.p)) % self.p
return lhs == rhs
def __repr__(self):
bits = self.p.nbits()
return f"ElGamal(p={self.p} [{bits}-bit], g={self.g}, h={self.h})"
# --- Quick demo ---
eg = ElGamal(bits=20, seed=42)
print(f"System: {eg}")
print(f"Public key: (p={eg.p}, g={eg.g}, h={eg.h})")
print(f"Private key: x={eg.x}")
print(f"Prime bits: {eg.p.nbits()}")
System: ElGamal(p=953131 [20-bit], g=272574, h=249119)
Public key: (p=953131, g=272574, h=249119)
Private key: x=42087
Prime bits: 20
29.5 Encryption and Decryption Demo#
We demonstrate the basic encrypt-decrypt cycle, verifying correctness on multiple messages.
# Set up the ElGamal system
eg = ElGamal(bits=20, seed=42)
print(f"ElGamal system: p={eg.p}, g={eg.g}, h={eg.h}")
print(f"Private key: x={eg.x}")
print("=" * 70)
# Encrypt and decrypt several messages
set_random_seed(123)
test_messages = [42, 1, eg.p - 1, 12345, randint(2, eg.p - 2)]
print(f"{'Message':>10} {'c1':>10} {'c2':>10} {'Decrypted':>10} {'Correct':>8}")
print("-" * 58)
all_correct = True
for m in test_messages:
c1, c2 = eg.encrypt(m)
m_dec = eg.decrypt(c1, c2)
ok = (m_dec == m)
all_correct &= ok
print(f"{m:>10} {c1:>10} {c2:>10} {m_dec:>10} {'YES' if ok else 'NO':>8}")
print("=" * 58)
print(f"All decryptions correct: {all_correct}")
ElGamal system: p=953131, g=272574, h=249119
Private key: x=42087
======================================================================
Message c1 c2 Decrypted Correct
----------------------------------------------------------
42 492569 180748 42 YES
1 536284 210353 1 YES
953130 309935 533784 953130 YES
12345 732012 542616 12345 YES
230690 801745 373218 230690 YES
==========================================================
All decryptions correct: True
29.6 Randomized Encryption: Same Plaintext, Different Ciphertexts#
A defining feature of ElGamal is that encryption is randomized: each call to encrypt uses a fresh ephemeral key \(k\), so the same plaintext maps to a different ciphertext every time. This contrasts sharply with textbook RSA, where \(\text{Enc}(m) = m^e \bmod n\) is deterministic.
Note
Randomized encryption is necessary for semantic security (IND-CPA). If an encryption scheme is deterministic, an attacker can encrypt candidate messages under the public key and compare with the target ciphertext – immediately breaking IND-CPA.
# Demonstrate randomized encryption
eg = ElGamal(bits=20, seed=42)
message = 7777
n_encryptions = 20
print(f"Encrypting the SAME message m={message} twenty times:")
print(f"{'#':>3} {'c1':>10} {'c2':>10} {'Decrypts to':>12}")
print("-" * 42)
c1_values = []
c2_values = []
for i in range(n_encryptions):
c1, c2 = eg.encrypt(message)
m_dec = eg.decrypt(c1, c2)
c1_values.append(c1)
c2_values.append(c2)
print(f"{i+1:>3} {c1:>10} {c2:>10} {m_dec:>12}")
# Check that all ciphertexts are distinct
pairs = list(zip(c1_values, c2_values))
unique_pairs = len(set(pairs))
print(f"\nUnique ciphertext pairs: {unique_pairs} / {n_encryptions}")
print(f"All decrypt correctly: {all(eg.decrypt(c1, c2) == message for c1, c2 in pairs)}")
# Scatter plot of (c1, c2) values using SageMath plotting
pts = [(c1_values[i], c2_values[i]) for i in range(n_encryptions)]
P = scatter_plot(pts, markersize=40, facecolor='steelblue', edgecolor='navy',
axes_labels=['$c_1 = g^k \;\mathrm{mod}\; p$', '$c_2 = m \\cdot h^k \;\mathrm{mod}\; p$'])
P += sum(text(str(i+1), (pts[i][0], pts[i][1]), fontsize=7, color='gray',
horizontal_alignment='left', vertical_alignment='bottom')
for i in range(n_encryptions))
P.set_axes_range(xmin=0, xmax=eg.p, ymin=0, ymax=eg.p)
show(P, title=f'Randomized Encryption: 20 ciphertexts of m={message}', figsize=(8, 6))
Encrypting the SAME message m=7777 twenty times:
# c1 c2 Decrypts to
------------------------------------------
1 474715 239991 7777
2 765107 575535 7777
3 591943 465404 7777
4 287753 395392 7777
5 310830 634343 7777
6 197003 481012 7777
7 432848 703892 7777
8 159325 401245 7777
9 88418 216383 7777
10 394637 662560 7777
11 372169 634196 7777
12 874580 866933 7777
13 454310 877593 7777
14 720633 786008 7777
15 725965 103347 7777
16 384597 74243 7777
17 216189 333354 7777
18 30733 668088 7777
19 187208 226378 7777
20 467804 297359 7777
Unique ciphertext pairs: 20 / 20
All decrypt correctly: True
<>:28: DeprecationWarning: invalid escape sequence '\;'
<>:28: DeprecationWarning: invalid escape sequence '\;'
<>:28: DeprecationWarning: invalid escape sequence '\;'
<>:28: DeprecationWarning: invalid escape sequence '\;'
/var/folders/z7/wp7m8p7x1250jzvklw5z24mm0000gn/T/ipykernel_23120/279471588.py:28: DeprecationWarning: invalid escape sequence '\;'
axes_labels=['$c_1 = g^k \;\mathrm{mod}\; p$', '$c_2 = m \\cdot h^k \;\mathrm{mod}\; p$'])
/var/folders/z7/wp7m8p7x1250jzvklw5z24mm0000gn/T/ipykernel_23120/279471588.py:28: DeprecationWarning: invalid escape sequence '\;'
axes_labels=['$c_1 = g^k \;\mathrm{mod}\; p$', '$c_2 = m \\cdot h^k \;\mathrm{mod}\; p$'])
29.7 Ciphertext Expansion#
ElGamal has a 2:1 ciphertext expansion ratio: each plaintext element \(m\) produces a ciphertext pair \((c_1, c_2)\) consisting of two group elements. This means the ciphertext is exactly twice the size of the plaintext (measured in group elements).
This expansion is an inherent cost of achieving randomized encryption in a group-based scheme. Let us visualize this ratio across different parameter sizes.
# Demonstrate ciphertext expansion
bit_sizes = [16, 20, 24, 28, 32]
expansion_data = []
print(f"{'Prime bits':>12} {'p':>12} {'msg bits':>10} {'ct bits':>10} {'Ratio':>6}")
print("-" * 56)
for bits in bit_sizes:
set_random_seed(100 + bits)
eg_tmp = ElGamal(bits=bits)
p_bits = eg_tmp.p.nbits()
msg_bits = p_bits # message is one element in Z_p^*
ct_bits = 2 * p_bits # ciphertext is two elements
ratio = ct_bits / msg_bits
expansion_data.append((p_bits, msg_bits, ct_bits, ratio))
print(f"{p_bits:>12} {eg_tmp.p:>12} {msg_bits:>10} {ct_bits:>10} {float(ratio):>6.1f}")
# Bar chart comparing plaintext vs ciphertext sizes using SageMath
msg_sizes = [d[1] for d in expansion_data]
ct_sizes = [d[2] for d in expansion_data]
G = Graphics()
width = 0.35
for i in range(len(bit_sizes)):
G += polygon2d([(i - width, 0), (i - width, msg_sizes[i]),
(i, msg_sizes[i]), (i, 0)],
color='steelblue', alpha=0.8, edgecolor='navy')
G += polygon2d([(i, 0), (i, ct_sizes[i]),
(i + width, ct_sizes[i]), (i + width, 0)],
color='crimson', alpha=0.8, edgecolor='darkred')
G += text(f"{int(ct_sizes[i]/msg_sizes[i])}x", (i + width/2, ct_sizes[i] + 2),
fontsize=9, color='darkred')
G += text("Plaintext (blue) vs Ciphertext (red)", (len(bit_sizes)/2, max(ct_sizes) + 8),
fontsize=11, color='black')
show(G, axes_labels=['Prime size', 'Size (bits)'],
title='ElGamal Ciphertext Expansion (2:1 Ratio)', figsize=(9, 5))
Prime bits p msg bits ct bits Ratio
--------------------------------------------------------
16 56443 16 32 2.0
20 954043 20 40 2.0
24 12297473 24 48 2.0
28 144632087 28 56 2.0
32 2425981303 32 64 2.0
29.8 Ciphertext Malleability: The Homomorphic Property#
ElGamal has a remarkable algebraic property: it is multiplicatively homomorphic. Given two ciphertexts that encrypt \(m_1\) and \(m_2\) respectively, one can compute a ciphertext that encrypts \(m_1 \cdot m_2\) without knowing the private key or the individual plaintexts.
Specifically, if \((c_1, c_2) = (g^{k_1}, m_1 \cdot h^{k_1})\) and \((c_1', c_2') = (g^{k_2}, m_2 \cdot h^{k_2})\), then:
This is a valid encryption of \(m_1 \cdot m_2\) under ephemeral key \(k_1 + k_2\).
Warning
Malleability is a double-edged sword. While the homomorphic property enables useful applications (electronic voting, secure computation), it also means that ElGamal is not CCA-secure (IND-CCA2). An attacker can manipulate ciphertexts in meaningful ways without detection. Real-world systems must add integrity checks (e.g., the Cramer–Shoup cryptosystem).
# Demonstrate the multiplicative homomorphic property
eg = ElGamal(bits=20, seed=42)
p = eg.p
m1 = 123
m2 = 456
m_product = (m1 * m2) % p
print(f"ElGamal system: p={p}")
print(f"m1 = {m1}")
print(f"m2 = {m2}")
print(f"m1 * m2 mod p = {m_product}")
print("=" * 50)
# Encrypt m1 and m2 separately
(c1_a, c2_a) = eg.encrypt(m1)
(c1_b, c2_b) = eg.encrypt(m2)
print(f"Enc(m1) = ({c1_a}, {c2_a})")
print(f"Enc(m2) = ({c1_b}, {c2_b})")
# Homomorphic multiplication: multiply ciphertexts component-wise
c1_prod = (c1_a * c1_b) % p
c2_prod = (c2_a * c2_b) % p
print(f"\nHomomorphic product: ({c1_prod}, {c2_prod})")
# Decrypt the product ciphertext
m_dec_product = eg.decrypt(c1_prod, c2_prod)
print(f"Decrypted product: {m_dec_product}")
print(f"Expected (m1*m2 mod p): {m_product}")
print(f"Homomorphic property holds: {m_dec_product == m_product}")
# Extended demo: chain of multiplications
print("\n" + "=" * 50)
print("Chained homomorphic operations:")
messages = [7, 11, 13, 17]
running_product = 1
running_c1 = 1
running_c2 = 1
for i, m in enumerate(messages):
c1, c2 = eg.encrypt(m)
running_c1 = (running_c1 * c1) % p
running_c2 = (running_c2 * c2) % p
running_product = (running_product * m) % p
dec = eg.decrypt(running_c1, running_c2)
print(f" After m={m:>3}: product={running_product:>8}, "
f"decrypted={dec:>8}, match={dec == running_product}")
ElGamal system: p=953131
m1 = 123
m2 = 456
m1 * m2 mod p = 56088
==================================================
Enc(m1) = (474715, 493291)
Enc(m2) = (765107, 861133)
Homomorphic product: (45597, 594016)
Decrypted product: 56088
Expected (m1*m2 mod p): 56088
Homomorphic property holds: True
==================================================
Chained homomorphic operations:
After m= 7: product= 7, decrypted= 7, match=True
After m= 11: product= 77, decrypted= 77, match=True
After m= 13: product= 1001, decrypted= 1001, match=True
After m= 17: product= 17017, decrypted= 17017, match=True
29.9 Re-Randomization#
Because ElGamal is randomized, we can re-randomize a ciphertext: given an encryption of \(m\), produce a fresh-looking encryption of the same \(m\) without knowing \(m\) or the private key.
To re-randomize \((c_1, c_2) = (g^k, m \cdot h^k)\), choose a fresh random \(k'\) and compute:
This is a valid encryption of the same \(m\) under a new ephemeral key \(k + k'\). Re-randomization is essential in mix-nets and electronic voting protocols.
eg = ElGamal(bits=20, seed=42)
p, g, h = eg.public_key
set_random_seed(999)
message = 31415
c1_orig, c2_orig = eg.encrypt(message)
print(f"Original message: {message}")
print(f"Original ciphertext: ({c1_orig}, {c2_orig})")
print(f"Decrypts to: {eg.decrypt(c1_orig, c2_orig)}")
print("\nRe-randomizing 10 times (without knowing the message):")
print(f"{'#':>3} {'c1':>10} {'c2':>10} {'Decrypted':>10} {'Correct':>8}")
print("-" * 48)
for i in range(10):
k_prime = randint(2, p - 2)
c1_new = (c1_orig * power_mod(g, k_prime, p)) % p
c2_new = (c2_orig * power_mod(h, k_prime, p)) % p
m_dec = eg.decrypt(c1_new, c2_new)
print(f"{i+1:>3} {c1_new:>10} {c2_new:>10} {m_dec:>10} "
f"{'YES' if m_dec == message else 'NO':>8}")
print(f"\nAll re-randomized ciphertexts decrypt to the original message.")
Original message: 31415
Original ciphertext: (803650, 755093)
Decrypts to: 31415
Re-randomizing 10 times (without knowing the message):
# c1 c2 Decrypted Correct
------------------------------------------------
1 567625 834149 31415 YES
2 262651 589676 31415 YES
3 391008 479181 31415 YES
4 525934 206726 31415 YES
5 87619 7078 31415 YES
6 326965 511036 31415 YES
7 625159 622595 31415 YES
8 890577 644708 31415 YES
9 862881 545164 31415 YES
10 534916 194899 31415 YES
All re-randomized ciphertexts decrypt to the original message.
29.10 Digital Signatures#
ElGamal’s signature scheme provides authentication and non-repudiation. The signer uses their private key \(x\) to produce a signature \((r, s)\) that anyone can verify using the public key \((p, g, h)\).
eg = ElGamal(bits=20, seed=42)
print(f"ElGamal system: p={eg.p}, g={eg.g}, h={eg.h}")
print(f"Private key: x={eg.x}")
print("=" * 60)
# Sign several messages
messages_to_sign = [42, 1000, 99999, 7, 314]
print(f"\n{'Message':>10} {'r':>10} {'s':>10} {'Valid':>6}")
print("-" * 42)
signatures = []
for m in messages_to_sign:
r, s = eg.sign(m)
valid = eg.verify(m, r, s)
signatures.append((m, r, s))
print(f"{m:>10} {r:>10} {s:>10} {'YES' if valid else 'NO':>6}")
# Demonstrate that a tampered message fails verification
print("\n--- Tampered message verification ---")
m_orig, r_orig, s_orig = signatures[0]
m_tampered = m_orig + 1
valid_tampered = eg.verify(m_tampered, r_orig, s_orig)
print(f"Original message: {m_orig}, Signature valid: {eg.verify(m_orig, r_orig, s_orig)}")
print(f"Tampered message: {m_tampered}, Signature valid: {valid_tampered}")
# Demonstrate that a forged signature fails
print("\n--- Forged signature verification ---")
r_forged = (r_orig + 1) % eg.p
valid_forged = eg.verify(m_orig, r_forged, s_orig)
print(f"Original r={r_orig}: valid={eg.verify(m_orig, r_orig, s_orig)}")
print(f"Forged r={r_forged}: valid={valid_forged}")
ElGamal system: p=953131, g=272574, h=249119
Private key: x=42087
============================================================
Message r s Valid
------------------------------------------
42 372169 716193 YES
1000 384597 720157 YES
99999 467804 434673 YES
7 685348 533087 YES
314 438093 133943 YES
--- Tampered message verification ---
Original message: 42, Signature valid: True
Tampered message: 43, Signature valid: False
--- Forged signature verification ---
Original r=372169: valid=True
Forged r=372170: valid=False
29.11 Timing Comparison: ElGamal vs. RSA#
We compare the computational cost of ElGamal encryption/decryption against a simple textbook RSA implementation. Both schemes rely on modular exponentiation, but ElGamal requires two exponentiations per encryption (computing \(g^k\) and \(h^k\)) plus a multiplication, while RSA requires one exponentiation.
import time
class SimpleRSA:
"""Minimal textbook RSA for timing comparison (SageMath version)."""
def __init__(self, bits=32, seed=None):
if seed is not None:
set_random_seed(seed)
# Generate two primes using SageMath's random_prime()
self.p_rsa = random_prime(2^(bits//2), lbound=2^(bits//2 - 1))
self.q_rsa = random_prime(2^(bits//2), lbound=2^(bits//2 - 1))
while self.q_rsa == self.p_rsa:
self.q_rsa = random_prime(2^(bits//2), lbound=2^(bits//2 - 1))
self.n = self.p_rsa * self.q_rsa
phi = (self.p_rsa - 1) * (self.q_rsa - 1)
self.e = ZZ(65537)
while gcd(self.e, phi) != 1:
self.e += 2
self.d = inverse_mod(self.e, phi)
def encrypt(self, m):
return power_mod(m, self.e, self.n)
def decrypt(self, c):
return power_mod(c, self.d, self.n)
# Timing comparison across different bit sizes
bit_sizes = [16, 20, 24, 28, 32]
n_trials = 200
eg_enc_times = []
eg_dec_times = []
rsa_enc_times = []
rsa_dec_times = []
for bits in bit_sizes:
eg_sys = ElGamal(bits=bits, seed=200 + bits)
rsa_sys = SimpleRSA(bits=bits, seed=300 + bits)
set_random_seed(777 + bits)
msgs_eg = [randint(2, eg_sys.p - 2) for _ in range(n_trials)]
msgs_rsa = [randint(2, rsa_sys.n - 2) for _ in range(n_trials)]
# Time ElGamal encryption
t0 = time.perf_counter()
cts_eg = [eg_sys.encrypt(m) for m in msgs_eg]
eg_enc_times.append((time.perf_counter() - t0) / n_trials * 1e6)
# Time ElGamal decryption
t0 = time.perf_counter()
_ = [eg_sys.decrypt(c1, c2) for c1, c2 in cts_eg]
eg_dec_times.append((time.perf_counter() - t0) / n_trials * 1e6)
# Time RSA encryption
t0 = time.perf_counter()
cts_rsa = [rsa_sys.encrypt(m) for m in msgs_rsa]
rsa_enc_times.append((time.perf_counter() - t0) / n_trials * 1e6)
# Time RSA decryption
t0 = time.perf_counter()
_ = [rsa_sys.decrypt(c) for c in cts_rsa]
rsa_dec_times.append((time.perf_counter() - t0) / n_trials * 1e6)
# Print results
print(f"{'Bits':>6} {'EG Enc (us)':>12} {'EG Dec (us)':>12} "
f"{'RSA Enc (us)':>13} {'RSA Dec (us)':>13}")
print("-" * 62)
for i, bits in enumerate(bit_sizes):
print(f"{bits:>6} {float(eg_enc_times[i]):>12.1f} {float(eg_dec_times[i]):>12.1f} "
f"{float(rsa_enc_times[i]):>13.1f} {float(rsa_dec_times[i]):>13.1f}")
# Plot using SageMath bar chart
G_enc = Graphics()
G_dec = Graphics()
width = 0.35
for i in range(len(bit_sizes)):
# Encryption bars
G_enc += polygon2d([(i - width, 0), (i - width, eg_enc_times[i]),
(i, eg_enc_times[i]), (i, 0)],
color='steelblue', alpha=0.8)
G_enc += polygon2d([(i, 0), (i, rsa_enc_times[i]),
(i + width, rsa_enc_times[i]), (i + width, 0)],
color='darkorange', alpha=0.8)
# Decryption bars
G_dec += polygon2d([(i - width, 0), (i - width, eg_dec_times[i]),
(i, eg_dec_times[i]), (i, 0)],
color='steelblue', alpha=0.8)
G_dec += polygon2d([(i, 0), (i, rsa_dec_times[i]),
(i + width, rsa_dec_times[i]), (i + width, 0)],
color='darkorange', alpha=0.8)
show(G_enc, title='Encryption Time: ElGamal (blue) vs RSA (orange)',
axes_labels=['Prime size index', 'Time (us)'], figsize=(7, 4))
show(G_dec, title='Decryption Time: ElGamal (blue) vs RSA (orange)',
axes_labels=['Prime size index', 'Time (us)'], figsize=(7, 4))
print("\nNote: ElGamal encryption requires 2 modular exponentiations vs. 1 for RSA.")
print("RSA decryption uses a large private exponent d, making it slower than encryption.")
Bits EG Enc (us) EG Dec (us) RSA Enc (us) RSA Dec (us)
--------------------------------------------------------------
16 10.0 4.7 4.4 4.9
20 11.7 4.6 4.4 5.3
24 15.7 9.2 6.5 4.2
28 17.2 11.2 4.3 9.4
32 19.8 9.2 6.5 11.3
Note: ElGamal encryption requires 2 modular exponentiations vs. 1 for RSA.
RSA decryption uses a large private exponent d, making it slower than encryption.
29.12 The Danger of Ephemeral Key Reuse#
We now demonstrate concretely why reusing the ephemeral key \(k\) is catastrophic. If two messages \(m_1, m_2\) are encrypted with the same \(k\), the shared secret \(s = h^k\) is identical in both ciphertexts, allowing an attacker who knows one plaintext to recover the other.
eg = ElGamal(bits=20, seed=42)
p = eg.p
m1 = 12345
m2 = 67890
# DANGEROUS: encrypt both messages with the same k
k_reused = 9999
c1_a, c2_a = eg.encrypt(m1, k=k_reused)
c1_b, c2_b = eg.encrypt(m2, k=k_reused)
print("=== Ephemeral Key Reuse Attack ===")
print(f"p = {p}")
print(f"m1 = {m1}, Enc(m1) = ({c1_a}, {c2_a})")
print(f"m2 = {m2}, Enc(m2) = ({c1_b}, {c2_b})")
print(f"Note: c1 values are identical (same k): c1_a == c1_b = {c1_a == c1_b}")
# Attack: suppose the attacker knows m1 and both ciphertexts
print("\n--- Attacker knows m1 and sees both ciphertexts ---")
# c2_a = m1 * h^k mod p --> h^k = c2_a * m1^(-1) mod p
# c2_b = m2 * h^k mod p --> m2 = c2_b * (h^k)^(-1) mod p
# Combined: m2 = c2_b * m1 * c2_a^(-1) mod p
c2_a_inv = inverse_mod(c2_a, p)
m2_recovered = (c2_b * m1 * c2_a_inv) % p
print(f"Recovered m2 = c2_b * m1 * c2_a^(-1) mod p = {m2_recovered}")
print(f"Actual m2 = {m2}")
print(f"Attack successful: {m2_recovered == m2}")
print("\n--- Lesson: NEVER reuse the ephemeral key k ---")
=== Ephemeral Key Reuse Attack ===
p = 953131
m1 = 12345, Enc(m1) = (719452, 542024)
m2 = 67890, Enc(m2) = (719452, 458422)
Note: c1 values are identical (same k): c1_a == c1_b = True
--- Attacker knows m1 and sees both ciphertexts ---
Recovered m2 = c2_b * m1 * c2_a^(-1) mod p = 67890
Actual m2 = 67890
Attack successful: True
--- Lesson: NEVER reuse the ephemeral key k ---
29.13 Visualizing the Group Structure#
To build intuition about why ElGamal works, let us visualize the structure of \(\mathbb{Z}_p^*\) for a small prime \(p\). We plot the discrete powers \(g^0, g^1, g^2, \ldots, g^{p-2}\) to see how the generator cycles through all elements.
# Small prime for visualization -- use SageMath's primitive_root()
p_small = 47
g_small = primitive_root(p_small)
# Compute all powers of g
powers = [power_mod(g_small, i, p_small) for i in range(p_small - 1)]
# Powers of g as a sequence
P1 = list_plot(list(enumerate(powers)), plotjoined=True, marker='o',
color='steelblue', axes_labels=['Exponent $k$', f'$g^k \% {p_small}$'])
P1 += list_plot(list(enumerate(powers)), color='steelblue', size=20)
show(P1, title=f'Powers of g={g_small} in Z_{p_small}^*', figsize=(7, 4))
# Circular arrangement showing the cyclic group
import math as pymath
theta = [2 * pymath.pi * k / (p_small - 1) for k in range(p_small - 1)]
radius = 1.0
x_circle = [radius * pymath.cos(t) for t in theta]
y_circle = [radius * pymath.sin(t) for t in theta]
# Points on circle colored by index
G_circ = Graphics()
for k in range(p_small - 1):
hue_val = float(k) / (p_small - 1)
G_circ += point((x_circle[k], y_circle[k]), size=30,
color=Color(hue_val, 1, 1, space='hsv'), zorder=3)
# Draw arrows for first few steps
for i in range(min(12, p_small - 2)):
G_circ += arrow((x_circle[i], y_circle[i]),
(x_circle[i+1], y_circle[i+1]),
color='gray', alpha=0.4, width=0.5)
# Label a few elements
for k in [0, 1, 2, 5, 10, 20, p_small - 3]:
if k < p_small - 1:
G_circ += text(f'$g^{{{k}}}$={powers[k]}',
(x_circle[k]*1.3, y_circle[k]*1.3),
fontsize=7, color='black')
show(G_circ, title=f'Cyclic Group Z_{p_small}^* (g={g_small})',
axes=False, aspect_ratio=1, figsize=(7, 7))
print(f"Generator g = {g_small}, prime p = {p_small}, group order = {p_small - 1}")
print(f"g generates all {p_small - 1} elements: {sorted(powers) == list(range(1, p_small))}")
<>:10: DeprecationWarning: invalid escape sequence '\%'
<>:10: DeprecationWarning: invalid escape sequence '\%'
/var/folders/z7/wp7m8p7x1250jzvklw5z24mm0000gn/T/ipykernel_23120/1261080694.py:10: DeprecationWarning: invalid escape sequence '\%'
color='steelblue', axes_labels=['Exponent $k$', f'$g^k \% {p_small}$'])
verbose 0 (162: primitive.py, options) WARNING: Ignoring option 'alpha'=0.400000000000000
verbose 0 (162: primitive.py, options)
The allowed options for Arrow from (1.0,0.0) to (0.9906859460363308,0.1361666490962466) are:
arrowshorten The length in points to shorten the arrow.
arrowsize The size of the arrowhead
head 2-d only: Which end of the path to draw the head (one of 0 (start), 1 (end) or 2 (both)
hue The color given as a hue.
legend_color The color of the legend text.
legend_label The label for this item in the legend.
linestyle 2d only: The style of the line, which is one of 'dashed', 'dotted', 'solid', 'dashdot', or '--', ':', '-', '-.', respectively.
rgbcolor The color as an RGB tuple.
thickness The thickness of the arrow.
width The width of the shaft of the arrow, in points.
zorder 2-d only: The layer level in which to draw
verbose 0 (162: primitive.py, options) WARNING: Ignoring option 'alpha'=0.400000000000000
verbose 0 (162: primitive.py, options)
The allowed options for Arrow from (1.0,0.0) to (0.9906859460363308,0.1361666490962466) are:
arrowshorten The length in points to shorten the arrow.
arrowsize The size of the arrowhead
head 2-d only: Which end of the path to draw the head (one of 0 (start), 1 (end) or 2 (both)
hue The color given as a hue.
legend_color The color of the legend text.
legend_label The label for this item in the legend.
linestyle 2d only: The style of the line, which is one of 'dashed', 'dotted', 'solid', 'dashdot', or '--', ':', '-', '-.', respectively.
rgbcolor The color as an RGB tuple.
thickness The thickness of the arrow.
width The width of the shaft of the arrow, in points.
zorder 2-d only: The layer level in which to draw
verbose 0 (162: primitive.py, options) WARNING: Ignoring option 'alpha'=0.4
verbose 0 (162: primitive.py, options)
The allowed options for Arrow from (1.0,0.0) to (0.9906859460363308,0.1361666490962466) are:
arrowshorten The length in points to shorten the arrow.
arrowsize The size of the arrowhead
head 2-d only: Which end of the path to draw the head (one of 0 (start), 1 (end) or 2 (both)
hue The color given as a hue.
legend_color The color of the legend text.
legend_label The label for this item in the legend.
linestyle 2d only: The style of the line, which is one of 'dashed', 'dotted', 'solid', 'dashdot', or '--', ':', '-', '-.', respectively.
rgbcolor The color as an RGB tuple.
thickness The thickness of the arrow.
width The width of the shaft of the arrow, in points.
zorder 2-d only: The layer level in which to draw
verbose 0 (162: primitive.py, options) WARNING: Ignoring option 'alpha'=0.400000000000000
verbose 0 (162: primitive.py, options)
The allowed options for Arrow from (0.9906859460363308,0.1361666490962466) to (0.9629172873477994,0.2697967711570243) are:
arrowshorten The length in points to shorten the arrow.
arrowsize The size of the arrowhead
head 2-d only: Which end of the path to draw the head (one of 0 (start), 1 (end) or 2 (both)
hue The color given as a hue.
legend_color The color of the legend text.
legend_label The label for this item in the legend.
linestyle 2d only: The style of the line, which is one of 'dashed', 'dotted', 'solid', 'dashdot', or '--', ':', '-', '-.', respectively.
rgbcolor The color as an RGB tuple.
thickness The thickness of the arrow.
width The width of the shaft of the arrow, in points.
zorder 2-d only: The layer level in which to draw
verbose 0 (162: primitive.py, options) WARNING: Ignoring option 'alpha'=0.400000000000000
verbose 0 (162: primitive.py, options)
The allowed options for Arrow from (0.9906859460363308,0.1361666490962466) to (0.9629172873477994,0.2697967711570243) are:
arrowshorten The length in points to shorten the arrow.
arrowsize The size of the arrowhead
head 2-d only: Which end of the path to draw the head (one of 0 (start), 1 (end) or 2 (both)
hue The color given as a hue.
legend_color The color of the legend text.
legend_label The label for this item in the legend.
linestyle 2d only: The style of the line, which is one of 'dashed', 'dotted', 'solid', 'dashdot', or '--', ':', '-', '-.', respectively.
rgbcolor The color as an RGB tuple.
thickness The thickness of the arrow.
width The width of the shaft of the arrow, in points.
zorder 2-d only: The layer level in which to draw
verbose 0 (162: primitive.py, options) WARNING: Ignoring option 'alpha'=0.4
verbose 0 (162: primitive.py, options)
The allowed options for Arrow from (0.9906859460363308,0.1361666490962466) to (0.9629172873477994,0.2697967711570243) are:
arrowshorten The length in points to shorten the arrow.
arrowsize The size of the arrowhead
head 2-d only: Which end of the path to draw the head (one of 0 (start), 1 (end) or 2 (both)
hue The color given as a hue.
legend_color The color of the legend text.
legend_label The label for this item in the legend.
linestyle 2d only: The style of the line, which is one of 'dashed', 'dotted', 'solid', 'dashdot', or '--', ':', '-', '-.', respectively.
rgbcolor The color as an RGB tuple.
thickness The thickness of the arrow.
width The width of the shaft of the arrow, in points.
zorder 2-d only: The layer level in which to draw
verbose 0 (162: primitive.py, options) WARNING: Ignoring option 'alpha'=0.400000000000000
verbose 0 (162: primitive.py, options)
The allowed options for Arrow from (0.9629172873477994,0.2697967711570243) to (0.917211301505453,0.39840108984624145) are:
arrowshorten The length in points to shorten the arrow.
arrowsize The size of the arrowhead
head 2-d only: Which end of the path to draw the head (one of 0 (start), 1 (end) or 2 (both)
hue The color given as a hue.
legend_color The color of the legend text.
legend_label The label for this item in the legend.
linestyle 2d only: The style of the line, which is one of 'dashed', 'dotted', 'solid', 'dashdot', or '--', ':', '-', '-.', respectively.
rgbcolor The color as an RGB tuple.
thickness The thickness of the arrow.
width The width of the shaft of the arrow, in points.
zorder 2-d only: The layer level in which to draw
verbose 0 (162: primitive.py, options) WARNING: Ignoring option 'alpha'=0.400000000000000
verbose 0 (162: primitive.py, options)
The allowed options for Arrow from (0.9629172873477994,0.2697967711570243) to (0.917211301505453,0.39840108984624145) are:
arrowshorten The length in points to shorten the arrow.
arrowsize The size of the arrowhead
head 2-d only: Which end of the path to draw the head (one of 0 (start), 1 (end) or 2 (both)
hue The color given as a hue.
legend_color The color of the legend text.
legend_label The label for this item in the legend.
linestyle 2d only: The style of the line, which is one of 'dashed', 'dotted', 'solid', 'dashdot', or '--', ':', '-', '-.', respectively.
rgbcolor The color as an RGB tuple.
thickness The thickness of the arrow.
width The width of the shaft of the arrow, in points.
zorder 2-d only: The layer level in which to draw
verbose 0 (162: primitive.py, options) WARNING: Ignoring option 'alpha'=0.4
verbose 0 (162: primitive.py, options)
The allowed options for Arrow from (0.9629172873477994,0.2697967711570243) to (0.917211301505453,0.39840108984624145) are:
arrowshorten The length in points to shorten the arrow.
arrowsize The size of the arrowhead
head 2-d only: Which end of the path to draw the head (one of 0 (start), 1 (end) or 2 (both)
hue The color given as a hue.
legend_color The color of the legend text.
legend_label The label for this item in the legend.
linestyle 2d only: The style of the line, which is one of 'dashed', 'dotted', 'solid', 'dashdot', or '--', ':', '-', '-.', respectively.
rgbcolor The color as an RGB tuple.
thickness The thickness of the arrow.
width The width of the shaft of the arrow, in points.
zorder 2-d only: The layer level in which to draw
verbose 0 (162: primitive.py, options) WARNING: Ignoring option 'alpha'=0.400000000000000
verbose 0 (162: primitive.py, options)
The allowed options for Arrow from (0.917211301505453,0.39840108984624145) to (0.8544194045464886,0.5195839500354336) are:
arrowshorten The length in points to shorten the arrow.
arrowsize The size of the arrowhead
head 2-d only: Which end of the path to draw the head (one of 0 (start), 1 (end) or 2 (both)
hue The color given as a hue.
legend_color The color of the legend text.
legend_label The label for this item in the legend.
linestyle 2d only: The style of the line, which is one of 'dashed', 'dotted', 'solid', 'dashdot', or '--', ':', '-', '-.', respectively.
rgbcolor The color as an RGB tuple.
thickness The thickness of the arrow.
width The width of the shaft of the arrow, in points.
zorder 2-d only: The layer level in which to draw
verbose 0 (162: primitive.py, options) WARNING: Ignoring option 'alpha'=0.400000000000000
verbose 0 (162: primitive.py, options)
The allowed options for Arrow from (0.917211301505453,0.39840108984624145) to (0.8544194045464886,0.5195839500354336) are:
arrowshorten The length in points to shorten the arrow.
arrowsize The size of the arrowhead
head 2-d only: Which end of the path to draw the head (one of 0 (start), 1 (end) or 2 (both)
hue The color given as a hue.
legend_color The color of the legend text.
legend_label The label for this item in the legend.
linestyle 2d only: The style of the line, which is one of 'dashed', 'dotted', 'solid', 'dashdot', or '--', ':', '-', '-.', respectively.
rgbcolor The color as an RGB tuple.
thickness The thickness of the arrow.
width The width of the shaft of the arrow, in points.
zorder 2-d only: The layer level in which to draw
verbose 0 (162: primitive.py, options) WARNING: Ignoring option 'alpha'=0.4
verbose 0 (162: primitive.py, options)
The allowed options for Arrow from (0.917211301505453,0.39840108984624145) to (0.8544194045464886,0.5195839500354336) are:
arrowshorten The length in points to shorten the arrow.
arrowsize The size of the arrowhead
head 2-d only: Which end of the path to draw the head (one of 0 (start), 1 (end) or 2 (both)
hue The color given as a hue.
legend_color The color of the legend text.
legend_label The label for this item in the legend.
linestyle 2d only: The style of the line, which is one of 'dashed', 'dotted', 'solid', 'dashdot', or '--', ':', '-', '-.', respectively.
rgbcolor The color as an RGB tuple.
thickness The thickness of the arrow.
width The width of the shaft of the arrow, in points.
zorder 2-d only: The layer level in which to draw
verbose 0 (162: primitive.py, options) WARNING: Ignoring option 'alpha'=0.400000000000000
verbose 0 (162: primitive.py, options)
The allowed options for Arrow from (0.8544194045464886,0.5195839500354336) to (0.7757112907044198,0.6310879443260529) are:
arrowshorten The length in points to shorten the arrow.
arrowsize The size of the arrowhead
head 2-d only: Which end of the path to draw the head (one of 0 (start), 1 (end) or 2 (both)
hue The color given as a hue.
legend_color The color of the legend text.
legend_label The label for this item in the legend.
linestyle 2d only: The style of the line, which is one of 'dashed', 'dotted', 'solid', 'dashdot', or '--', ':', '-', '-.', respectively.
rgbcolor The color as an RGB tuple.
thickness The thickness of the arrow.
width The width of the shaft of the arrow, in points.
zorder 2-d only: The layer level in which to draw
verbose 0 (162: primitive.py, options) WARNING: Ignoring option 'alpha'=0.400000000000000
verbose 0 (162: primitive.py, options)
The allowed options for Arrow from (0.8544194045464886,0.5195839500354336) to (0.7757112907044198,0.6310879443260529) are:
arrowshorten The length in points to shorten the arrow.
arrowsize The size of the arrowhead
head 2-d only: Which end of the path to draw the head (one of 0 (start), 1 (end) or 2 (both)
hue The color given as a hue.
legend_color The color of the legend text.
legend_label The label for this item in the legend.
linestyle 2d only: The style of the line, which is one of 'dashed', 'dotted', 'solid', 'dashdot', or '--', ':', '-', '-.', respectively.
rgbcolor The color as an RGB tuple.
thickness The thickness of the arrow.
width The width of the shaft of the arrow, in points.
zorder 2-d only: The layer level in which to draw
verbose 0 (162: primitive.py, options) WARNING: Ignoring option 'alpha'=0.4
verbose 0 (162: primitive.py, options)
The allowed options for Arrow from (0.8544194045464886,0.5195839500354336) to (0.7757112907044198,0.6310879443260529) are:
arrowshorten The length in points to shorten the arrow.
arrowsize The size of the arrowhead
head 2-d only: Which end of the path to draw the head (one of 0 (start), 1 (end) or 2 (both)
hue The color given as a hue.
legend_color The color of the legend text.
legend_label The label for this item in the legend.
linestyle 2d only: The style of the line, which is one of 'dashed', 'dotted', 'solid', 'dashdot', or '--', ':', '-', '-.', respectively.
rgbcolor The color as an RGB tuple.
thickness The thickness of the arrow.
width The width of the shaft of the arrow, in points.
zorder 2-d only: The layer level in which to draw
verbose 0 (162: primitive.py, options) WARNING: Ignoring option 'alpha'=0.400000000000000
verbose 0 (162: primitive.py, options)
The allowed options for Arrow from (0.7757112907044198,0.6310879443260529) to (0.6825531432186541,0.730835964278124) are:
arrowshorten The length in points to shorten the arrow.
arrowsize The size of the arrowhead
head 2-d only: Which end of the path to draw the head (one of 0 (start), 1 (end) or 2 (both)
hue The color given as a hue.
legend_color The color of the legend text.
legend_label The label for this item in the legend.
linestyle 2d only: The style of the line, which is one of 'dashed', 'dotted', 'solid', 'dashdot', or '--', ':', '-', '-.', respectively.
rgbcolor The color as an RGB tuple.
thickness The thickness of the arrow.
width The width of the shaft of the arrow, in points.
zorder 2-d only: The layer level in which to draw
verbose 0 (162: primitive.py, options) WARNING: Ignoring option 'alpha'=0.400000000000000
verbose 0 (162: primitive.py, options)
The allowed options for Arrow from (0.7757112907044198,0.6310879443260529) to (0.6825531432186541,0.730835964278124) are:
arrowshorten The length in points to shorten the arrow.
arrowsize The size of the arrowhead
head 2-d only: Which end of the path to draw the head (one of 0 (start), 1 (end) or 2 (both)
hue The color given as a hue.
legend_color The color of the legend text.
legend_label The label for this item in the legend.
linestyle 2d only: The style of the line, which is one of 'dashed', 'dotted', 'solid', 'dashdot', or '--', ':', '-', '-.', respectively.
rgbcolor The color as an RGB tuple.
thickness The thickness of the arrow.
width The width of the shaft of the arrow, in points.
zorder 2-d only: The layer level in which to draw
verbose 0 (162: primitive.py, options) WARNING: Ignoring option 'alpha'=0.4
verbose 0 (162: primitive.py, options)
The allowed options for Arrow from (0.7757112907044198,0.6310879443260529) to (0.6825531432186541,0.730835964278124) are:
arrowshorten The length in points to shorten the arrow.
arrowsize The size of the arrowhead
head 2-d only: Which end of the path to draw the head (one of 0 (start), 1 (end) or 2 (both)
hue The color given as a hue.
legend_color The color of the legend text.
legend_label The label for this item in the legend.
linestyle 2d only: The style of the line, which is one of 'dashed', 'dotted', 'solid', 'dashdot', or '--', ':', '-', '-.', respectively.
rgbcolor The color as an RGB tuple.
thickness The thickness of the arrow.
width The width of the shaft of the arrow, in points.
zorder 2-d only: The layer level in which to draw
verbose 0 (162: primitive.py, options) WARNING: Ignoring option 'alpha'=0.400000000000000
verbose 0 (162: primitive.py, options)
The allowed options for Arrow from (0.6825531432186541,0.730835964278124) to (0.5766803221148671,0.816969893010442) are:
arrowshorten The length in points to shorten the arrow.
arrowsize The size of the arrowhead
head 2-d only: Which end of the path to draw the head (one of 0 (start), 1 (end) or 2 (both)
hue The color given as a hue.
legend_color The color of the legend text.
legend_label The label for this item in the legend.
linestyle 2d only: The style of the line, which is one of 'dashed', 'dotted', 'solid', 'dashdot', or '--', ':', '-', '-.', respectively.
rgbcolor The color as an RGB tuple.
thickness The thickness of the arrow.
width The width of the shaft of the arrow, in points.
zorder 2-d only: The layer level in which to draw
verbose 0 (162: primitive.py, options) WARNING: Ignoring option 'alpha'=0.400000000000000
verbose 0 (162: primitive.py, options)
The allowed options for Arrow from (0.6825531432186541,0.730835964278124) to (0.5766803221148671,0.816969893010442) are:
arrowshorten The length in points to shorten the arrow.
arrowsize The size of the arrowhead
head 2-d only: Which end of the path to draw the head (one of 0 (start), 1 (end) or 2 (both)
hue The color given as a hue.
legend_color The color of the legend text.
legend_label The label for this item in the legend.
linestyle 2d only: The style of the line, which is one of 'dashed', 'dotted', 'solid', 'dashdot', or '--', ':', '-', '-.', respectively.
rgbcolor The color as an RGB tuple.
thickness The thickness of the arrow.
width The width of the shaft of the arrow, in points.
zorder 2-d only: The layer level in which to draw
verbose 0 (162: primitive.py, options) WARNING: Ignoring option 'alpha'=0.4
verbose 0 (162: primitive.py, options)
The allowed options for Arrow from (0.6825531432186541,0.730835964278124) to (0.5766803221148671,0.816969893010442) are:
arrowshorten The length in points to shorten the arrow.
arrowsize The size of the arrowhead
head 2-d only: Which end of the path to draw the head (one of 0 (start), 1 (end) or 2 (both)
hue The color given as a hue.
legend_color The color of the legend text.
legend_label The label for this item in the legend.
linestyle 2d only: The style of the line, which is one of 'dashed', 'dotted', 'solid', 'dashdot', or '--', ':', '-', '-.', respectively.
rgbcolor The color as an RGB tuple.
thickness The thickness of the arrow.
width The width of the shaft of the arrow, in points.
zorder 2-d only: The layer level in which to draw
verbose 0 (162: primitive.py, options) WARNING: Ignoring option 'alpha'=0.400000000000000
verbose 0 (162: primitive.py, options)
The allowed options for Arrow from (0.5766803221148671,0.816969893010442) to (0.4600650377311522,0.8878852184023752) are:
arrowshorten The length in points to shorten the arrow.
arrowsize The size of the arrowhead
head 2-d only: Which end of the path to draw the head (one of 0 (start), 1 (end) or 2 (both)
hue The color given as a hue.
legend_color The color of the legend text.
legend_label The label for this item in the legend.
linestyle 2d only: The style of the line, which is one of 'dashed', 'dotted', 'solid', 'dashdot', or '--', ':', '-', '-.', respectively.
rgbcolor The color as an RGB tuple.
thickness The thickness of the arrow.
width The width of the shaft of the arrow, in points.
zorder 2-d only: The layer level in which to draw
verbose 0 (162: primitive.py, options) WARNING: Ignoring option 'alpha'=0.400000000000000
verbose 0 (162: primitive.py, options)
The allowed options for Arrow from (0.5766803221148671,0.816969893010442) to (0.4600650377311522,0.8878852184023752) are:
arrowshorten The length in points to shorten the arrow.
arrowsize The size of the arrowhead
head 2-d only: Which end of the path to draw the head (one of 0 (start), 1 (end) or 2 (both)
hue The color given as a hue.
legend_color The color of the legend text.
legend_label The label for this item in the legend.
linestyle 2d only: The style of the line, which is one of 'dashed', 'dotted', 'solid', 'dashdot', or '--', ':', '-', '-.', respectively.
rgbcolor The color as an RGB tuple.
thickness The thickness of the arrow.
width The width of the shaft of the arrow, in points.
zorder 2-d only: The layer level in which to draw
verbose 0 (162: primitive.py, options) WARNING: Ignoring option 'alpha'=0.4
verbose 0 (162: primitive.py, options)
The allowed options for Arrow from (0.5766803221148671,0.816969893010442) to (0.4600650377311522,0.8878852184023752) are:
arrowshorten The length in points to shorten the arrow.
arrowsize The size of the arrowhead
head 2-d only: Which end of the path to draw the head (one of 0 (start), 1 (end) or 2 (both)
hue The color given as a hue.
legend_color The color of the legend text.
legend_label The label for this item in the legend.
linestyle 2d only: The style of the line, which is one of 'dashed', 'dotted', 'solid', 'dashdot', or '--', ':', '-', '-.', respectively.
rgbcolor The color as an RGB tuple.
thickness The thickness of the arrow.
width The width of the shaft of the arrow, in points.
zorder 2-d only: The layer level in which to draw
verbose 0 (162: primitive.py, options) WARNING: Ignoring option 'alpha'=0.400000000000000
verbose 0 (162: primitive.py, options)
The allowed options for Arrow from (0.4600650377311522,0.8878852184023752) to (0.3348796121709863,0.9422609221188204) are:
arrowshorten The length in points to shorten the arrow.
arrowsize The size of the arrowhead
head 2-d only: Which end of the path to draw the head (one of 0 (start), 1 (end) or 2 (both)
hue The color given as a hue.
legend_color The color of the legend text.
legend_label The label for this item in the legend.
linestyle 2d only: The style of the line, which is one of 'dashed', 'dotted', 'solid', 'dashdot', or '--', ':', '-', '-.', respectively.
rgbcolor The color as an RGB tuple.
thickness The thickness of the arrow.
width The width of the shaft of the arrow, in points.
zorder 2-d only: The layer level in which to draw
verbose 0 (162: primitive.py, options) WARNING: Ignoring option 'alpha'=0.400000000000000
verbose 0 (162: primitive.py, options)
The allowed options for Arrow from (0.4600650377311522,0.8878852184023752) to (0.3348796121709863,0.9422609221188204) are:
arrowshorten The length in points to shorten the arrow.
arrowsize The size of the arrowhead
head 2-d only: Which end of the path to draw the head (one of 0 (start), 1 (end) or 2 (both)
hue The color given as a hue.
legend_color The color of the legend text.
legend_label The label for this item in the legend.
linestyle 2d only: The style of the line, which is one of 'dashed', 'dotted', 'solid', 'dashdot', or '--', ':', '-', '-.', respectively.
rgbcolor The color as an RGB tuple.
thickness The thickness of the arrow.
width The width of the shaft of the arrow, in points.
zorder 2-d only: The layer level in which to draw
verbose 0 (162: primitive.py, options) WARNING: Ignoring option 'alpha'=0.4
verbose 0 (162: primitive.py, options)
The allowed options for Arrow from (0.4600650377311522,0.8878852184023752) to (0.3348796121709863,0.9422609221188204) are:
arrowshorten The length in points to shorten the arrow.
arrowsize The size of the arrowhead
head 2-d only: Which end of the path to draw the head (one of 0 (start), 1 (end) or 2 (both)
hue The color given as a hue.
legend_color The color of the legend text.
legend_label The label for this item in the legend.
linestyle 2d only: The style of the line, which is one of 'dashed', 'dotted', 'solid', 'dashdot', or '--', ':', '-', '-.', respectively.
rgbcolor The color as an RGB tuple.
thickness The thickness of the arrow.
width The width of the shaft of the arrow, in points.
zorder 2-d only: The layer level in which to draw
verbose 0 (162: primitive.py, options) WARNING: Ignoring option 'alpha'=0.400000000000000
verbose 0 (162: primitive.py, options)
The allowed options for Arrow from (0.3348796121709863,0.9422609221188204) to (0.20345601305263375,0.9790840876823229) are:
arrowshorten The length in points to shorten the arrow.
arrowsize The size of the arrowhead
head 2-d only: Which end of the path to draw the head (one of 0 (start), 1 (end) or 2 (both)
hue The color given as a hue.
legend_color The color of the legend text.
legend_label The label for this item in the legend.
linestyle 2d only: The style of the line, which is one of 'dashed', 'dotted', 'solid', 'dashdot', or '--', ':', '-', '-.', respectively.
rgbcolor The color as an RGB tuple.
thickness The thickness of the arrow.
width The width of the shaft of the arrow, in points.
zorder 2-d only: The layer level in which to draw
verbose 0 (162: primitive.py, options) WARNING: Ignoring option 'alpha'=0.400000000000000
verbose 0 (162: primitive.py, options)
The allowed options for Arrow from (0.3348796121709863,0.9422609221188204) to (0.20345601305263375,0.9790840876823229) are:
arrowshorten The length in points to shorten the arrow.
arrowsize The size of the arrowhead
head 2-d only: Which end of the path to draw the head (one of 0 (start), 1 (end) or 2 (both)
hue The color given as a hue.
legend_color The color of the legend text.
legend_label The label for this item in the legend.
linestyle 2d only: The style of the line, which is one of 'dashed', 'dotted', 'solid', 'dashdot', or '--', ':', '-', '-.', respectively.
rgbcolor The color as an RGB tuple.
thickness The thickness of the arrow.
width The width of the shaft of the arrow, in points.
zorder 2-d only: The layer level in which to draw
verbose 0 (162: primitive.py, options) WARNING: Ignoring option 'alpha'=0.4
verbose 0 (162: primitive.py, options)
The allowed options for Arrow from (0.3348796121709863,0.9422609221188204) to (0.20345601305263375,0.9790840876823229) are:
arrowshorten The length in points to shorten the arrow.
arrowsize The size of the arrowhead
head 2-d only: Which end of the path to draw the head (one of 0 (start), 1 (end) or 2 (both)
hue The color given as a hue.
legend_color The color of the legend text.
legend_label The label for this item in the legend.
linestyle 2d only: The style of the line, which is one of 'dashed', 'dotted', 'solid', 'dashdot', or '--', ':', '-', '-.', respectively.
rgbcolor The color as an RGB tuple.
thickness The thickness of the arrow.
width The width of the shaft of the arrow, in points.
zorder 2-d only: The layer level in which to draw
verbose 0 (162: primitive.py, options) WARNING: Ignoring option 'alpha'=0.400000000000000
verbose 0 (162: primitive.py, options)
The allowed options for Arrow from (0.20345601305263375,0.9790840876823229) to (0.06824241336467123,0.9976687691905392) are:
arrowshorten The length in points to shorten the arrow.
arrowsize The size of the arrowhead
head 2-d only: Which end of the path to draw the head (one of 0 (start), 1 (end) or 2 (both)
hue The color given as a hue.
legend_color The color of the legend text.
legend_label The label for this item in the legend.
linestyle 2d only: The style of the line, which is one of 'dashed', 'dotted', 'solid', 'dashdot', or '--', ':', '-', '-.', respectively.
rgbcolor The color as an RGB tuple.
thickness The thickness of the arrow.
width The width of the shaft of the arrow, in points.
zorder 2-d only: The layer level in which to draw
verbose 0 (162: primitive.py, options) WARNING: Ignoring option 'alpha'=0.400000000000000
verbose 0 (162: primitive.py, options)
The allowed options for Arrow from (0.20345601305263375,0.9790840876823229) to (0.06824241336467123,0.9976687691905392) are:
arrowshorten The length in points to shorten the arrow.
arrowsize The size of the arrowhead
head 2-d only: Which end of the path to draw the head (one of 0 (start), 1 (end) or 2 (both)
hue The color given as a hue.
legend_color The color of the legend text.
legend_label The label for this item in the legend.
linestyle 2d only: The style of the line, which is one of 'dashed', 'dotted', 'solid', 'dashdot', or '--', ':', '-', '-.', respectively.
rgbcolor The color as an RGB tuple.
thickness The thickness of the arrow.
width The width of the shaft of the arrow, in points.
zorder 2-d only: The layer level in which to draw
verbose 0 (162: primitive.py, options) WARNING: Ignoring option 'alpha'=0.4
verbose 0 (162: primitive.py, options)
The allowed options for Arrow from (0.20345601305263375,0.9790840876823229) to (0.06824241336467123,0.9976687691905392) are:
arrowshorten The length in points to shorten the arrow.
arrowsize The size of the arrowhead
head 2-d only: Which end of the path to draw the head (one of 0 (start), 1 (end) or 2 (both)
hue The color given as a hue.
legend_color The color of the legend text.
legend_label The label for this item in the legend.
linestyle 2d only: The style of the line, which is one of 'dashed', 'dotted', 'solid', 'dashdot', or '--', ':', '-', '-.', respectively.
rgbcolor The color as an RGB tuple.
thickness The thickness of the arrow.
width The width of the shaft of the arrow, in points.
zorder 2-d only: The layer level in which to draw
verbose 0 (162: primitive.py, options) WARNING: Ignoring option 'alpha'=0.400000000000000
verbose 0 (162: primitive.py, options)
The allowed options for Arrow from (0.06824241336467123,0.9976687691905392) to (-0.06824241336467088,0.9976687691905392) are:
arrowshorten The length in points to shorten the arrow.
arrowsize The size of the arrowhead
head 2-d only: Which end of the path to draw the head (one of 0 (start), 1 (end) or 2 (both)
hue The color given as a hue.
legend_color The color of the legend text.
legend_label The label for this item in the legend.
linestyle 2d only: The style of the line, which is one of 'dashed', 'dotted', 'solid', 'dashdot', or '--', ':', '-', '-.', respectively.
rgbcolor The color as an RGB tuple.
thickness The thickness of the arrow.
width The width of the shaft of the arrow, in points.
zorder 2-d only: The layer level in which to draw
verbose 0 (162: primitive.py, options) WARNING: Ignoring option 'alpha'=0.400000000000000
verbose 0 (162: primitive.py, options)
The allowed options for Arrow from (0.06824241336467123,0.9976687691905392) to (-0.06824241336467088,0.9976687691905392) are:
arrowshorten The length in points to shorten the arrow.
arrowsize The size of the arrowhead
head 2-d only: Which end of the path to draw the head (one of 0 (start), 1 (end) or 2 (both)
hue The color given as a hue.
legend_color The color of the legend text.
legend_label The label for this item in the legend.
linestyle 2d only: The style of the line, which is one of 'dashed', 'dotted', 'solid', 'dashdot', or '--', ':', '-', '-.', respectively.
rgbcolor The color as an RGB tuple.
thickness The thickness of the arrow.
width The width of the shaft of the arrow, in points.
zorder 2-d only: The layer level in which to draw
verbose 0 (162: primitive.py, options) WARNING: Ignoring option 'alpha'=0.4
verbose 0 (162: primitive.py, options)
The allowed options for Arrow from (0.06824241336467123,0.9976687691905392) to (-0.06824241336467088,0.9976687691905392) are:
arrowshorten The length in points to shorten the arrow.
arrowsize The size of the arrowhead
head 2-d only: Which end of the path to draw the head (one of 0 (start), 1 (end) or 2 (both)
hue The color given as a hue.
legend_color The color of the legend text.
legend_label The label for this item in the legend.
linestyle 2d only: The style of the line, which is one of 'dashed', 'dotted', 'solid', 'dashdot', or '--', ':', '-', '-.', respectively.
rgbcolor The color as an RGB tuple.
thickness The thickness of the arrow.
width The width of the shaft of the arrow, in points.
zorder 2-d only: The layer level in which to draw
Generator g = 5, prime p = 47, group order = 46
g generates all 46 elements: True
29.14 Distribution of Ciphertext Components#
For a secure ElGamal system, the ciphertext components \((c_1, c_2)\) should appear uniformly distributed over \(\mathbb{Z}_p^*\). Let us verify this empirically by encrypting many random messages and examining the distribution of \(c_1\) and \(c_2\) values.
# Generate many ciphertexts
eg = ElGamal(bits=16, seed=42)
p = eg.p
n_samples = 2000
set_random_seed(555)
messages = [randint(1, p - 1) for _ in range(n_samples)]
c1_vals = []
c2_vals = []
for m in messages:
c1, c2 = eg.encrypt(m)
c1_vals.append(c1)
c2_vals.append(c2)
# Histogram of c1 values using SageMath
n_bins = 50
bin_width = RR((p - 1) / n_bins)
c1_hist_data = {}
c2_hist_data = {}
for v in c1_vals:
b = int(int(v) // int(bin_width))
c1_hist_data[b] = c1_hist_data.get(b, 0) + 1
for v in c2_vals:
b = int(int(v) // int(bin_width))
c2_hist_data[b] = c2_hist_data.get(b, 0) + 1
# Normalize to density
scale = n_samples * bin_width
H1 = Graphics()
for b, count in sorted(c1_hist_data.items()):
x0 = b * bin_width
x1 = (b + 1) * bin_width
h = count / scale
H1 += polygon2d([(x0, 0), (x0, h), (x1, h), (x1, 0)],
color='steelblue', alpha=0.8, edgecolor='navy')
H1 += line([(0, 1/(p-1)), (p, 1/(p-1))], color='red', linestyle='--', alpha=0.6,
legend_label='Uniform: 1/(p-1)')
show(H1, title='Distribution of $c_1 = g^k$',
axes_labels=['$c_1$ value', 'Density'], figsize=(7, 4))
H2 = Graphics()
for b, count in sorted(c2_hist_data.items()):
x0 = b * bin_width
x1 = (b + 1) * bin_width
h = count / scale
H2 += polygon2d([(x0, 0), (x0, h), (x1, h), (x1, 0)],
color='darkorange', alpha=0.8, edgecolor='saddlebrown')
H2 += line([(0, 1/(p-1)), (p, 1/(p-1))], color='red', linestyle='--', alpha=0.6,
legend_label='Uniform: 1/(p-1)')
show(H2, title='Distribution of $c_2 = m \cdot h^k$',
axes_labels=['$c_2$ value', 'Density'], figsize=(7, 4))
# Joint scatter plot
P_joint = scatter_plot(list(zip(c1_vals, c2_vals)), markersize=3, alpha=0.3,
facecolor='purple',
axes_labels=['$c_1$', '$c_2$'])
show(P_joint, title='Joint $(c_1, c_2)$ Distribution', figsize=(7, 5))
print(f"p = {p}, n_samples = {n_samples}")
print(f"c1 range: [{min(c1_vals)}, {max(c1_vals)}] (expected [1, {p-1}])")
print(f"c2 range: [{min(c2_vals)}, {max(c2_vals)}] (expected [1, {p-1}])")
<>:52: DeprecationWarning: invalid escape sequence '\c'
<>:52: DeprecationWarning: invalid escape sequence '\c'
/var/folders/z7/wp7m8p7x1250jzvklw5z24mm0000gn/T/ipykernel_23120/523147175.py:52: DeprecationWarning: invalid escape sequence '\c'
show(H2, title='Distribution of $c_2 = m \cdot h^k$',
p = 41467, n_samples = 2000
c1 range: [57, 41454] (expected [1, 41466])
c2 range: [56, 41444] (expected [1, 41466])
29.15 Exercises#
Exercise 29.1: Manual ElGamal#
Let \(p = 23\), \(g = 5\), and the private key \(x = 7\). Compute the public key \(h\). Then encrypt the message \(m = 10\) using ephemeral key \(k = 3\). Verify by decrypting.
Hint
\(h = 5^7 \bmod 23 = 78125 \bmod 23 = 17\). Encryption: \(c_1 = 5^3 \bmod 23 = 10\), \(s = 17^3 \bmod 23 = 4913 \bmod 23 = 15\), \(c_2 = 10 \cdot 15 \bmod 23 = 150 \bmod 23 = 12\). Decryption: \(s = c_1^x = 10^7 \bmod 23 = 10000000 \bmod 23 = 15\), \(s^{-1} = 15^{-1} \bmod 23\). Since \(15 \cdot 2 = 30 \equiv 7\) and \(15 \cdot 17 = 255 \equiv 2 \pmod{23}\)… use Fermat: \(s^{-1} = 15^{21} \bmod 23\). Or note \(c_1^{p-1-x} = 10^{15} \bmod 23\). Then \(m = c_2 \cdot s^{-1} \bmod 23 = 10\).
Exercise 29.2: Homomorphic Voting#
Design a simple yes/no voting protocol using ElGamal’s homomorphic property. Encode “yes” as \(g^1\) and “no” as \(g^0 = 1\). If there are \(n\) voters and \(t\) vote yes, what does the product of all ciphertexts decrypt to? How do you recover \(t\) from \(g^t\)?
Hint
Each voter encrypts \(g^{v_i}\) where \(v_i \in \{0, 1\}\). The homomorphic product decrypts to \(g^{v_1} \cdot g^{v_2} \cdots g^{v_n} = g^{v_1 + v_2 + \cdots + v_n} = g^t\). To recover \(t\), compute \(g, g^2, g^3, \ldots\) until finding \(g^t\). This is feasible since \(t \leq n\) and \(n\) is small (number of voters). This approach is called “exponential ElGamal” and is used in real e-voting systems like Helios.
Exercise 29.3: Proving the DDH Separation#
Show that the Computational Diffie–Hellman (CDH) problem does not immediately imply the Decisional Diffie–Hellman (DDH) problem. Give an example of a group where CDH is believed hard but DDH is easy.
Hint
Consider a group equipped with a bilinear pairing \(e: G \times G \to G_T\). Given \((g, g^a, g^b, Z)\), one can check whether \(Z = g^{ab}\) by testing if \(e(g^a, g^b) = e(g, Z)\). This breaks DDH while CDH may still be hard. Supersingular elliptic curves provide concrete examples. This is why ElGamal must be instantiated in groups where DDH holds – typically prime-order subgroups of \(\mathbb{Z}_p^*\) or suitable elliptic curves.
Exercise 29.4: Nonce Reuse Attack on Signatures#
Suppose an ElGamal signer uses the same nonce \(k\) to sign two different messages \(m_1 \neq m_2\), producing signatures \((r, s_1)\) and \((r, s_2)\) (same \(r\) since \(r = g^k\)). Show how to recover the private key \(x\) from these two signatures.
Hint
From the signing equation: \(s_1 = (m_1 - x \cdot r) \cdot k^{-1} \bmod (p-1)\) and \(s_2 = (m_2 - x \cdot r) \cdot k^{-1} \bmod (p-1)\). Subtracting: \(s_1 - s_2 = (m_1 - m_2) \cdot k^{-1} \bmod (p-1)\), so \(k = (m_1 - m_2) \cdot (s_1 - s_2)^{-1} \bmod (p-1)\) (when the inverse exists). Then from the first equation: \(x = (m_1 - k \cdot s_1) \cdot r^{-1} \bmod (p-1)\). This is essentially the attack used against Sony’s PS3 ECDSA implementation.
Exercise 29.5 (Challenge): CCA Attack via Malleability#
An oracle \(\mathcal{O}\) decrypts any ciphertext except the target \((c_1^*, c_2^*)\). Given a target ciphertext \((c_1^*, c_2^*)\) that encrypts an unknown message \(m^*\), use ElGamal’s homomorphic property to construct a different ciphertext that the oracle will decrypt, and use the oracle’s response to recover \(m^*\).
Hint
Choose any known message \(m' \neq 1\) and encrypt it: \((c_1', c_2') = (g^{k'}, m' \cdot h^{k'})\). Compute the modified ciphertext \((c_1^* \cdot c_1', c_2^* \cdot c_2')\). This is different from \((c_1^*, c_2^*)\), so the oracle will decrypt it, returning \(m^* \cdot m' \bmod p\). Then \(m^* = (m^* \cdot m') \cdot (m')^{-1} \bmod p\). This demonstrates that ElGamal is not IND-CCA2 secure.
# Exercise 29.1: Manual ElGamal verification with SageMath
p = 23; g = 5; x = 7
h = power_mod(g, x, p)
print(f"Public key h = g^x mod p = {g}^{x} mod {p} = {h}")
m = 10; k = 3
c1 = power_mod(g, k, p)
s = power_mod(h, k, p)
c2 = (m * s) % p
print(f"\nEncryption with k={k}:")
print(f" c1 = g^k mod p = {c1}")
print(f" s = h^k mod p = {s}")
print(f" c2 = m * s mod p = {c2}")
# Decrypt
s_dec = power_mod(c1, x, p)
s_inv = inverse_mod(s_dec, p)
m_dec = (c2 * s_inv) % p
print(f"\nDecryption:")
print(f" s = c1^x mod p = {s_dec}")
print(f" s^(-1) mod p = {s_inv}")
print(f" m = c2 * s^(-1) mod p = {m_dec}")
print(f" Correct: {m_dec == m}")
Public key h = g^x mod p = 5^7 mod 23 = 17
Encryption with k=3:
c1 = g^k mod p = 10
s = h^k mod p = 14
c2 = m * s mod p = 2
Decryption:
s = c1^x mod p = 14
s^(-1) mod p = 5
m = c2 * s^(-1) mod p = 10
Correct: True
29.16 Summary and Key Takeaways#
In this chapter, we have studied the ElGamal cryptosystem, a public-key encryption and signature scheme based on the discrete logarithm problem:
From Diffie–Hellman to encryption. ElGamal transforms the DH key exchange into a full public-key cryptosystem by having the sender perform a “one-sided” key exchange with a fresh ephemeral key \(k\) for each message.
Randomized encryption. Each encryption uses a fresh random \(k\), so the same plaintext encrypts to different ciphertexts. This is essential for semantic security (IND-CPA) under the DDH assumption.
Ciphertext expansion. The 2:1 expansion ratio (one plaintext element becomes two ciphertext elements) is the price of randomization.
Multiplicative homomorphism. The component-wise product of two ciphertexts decrypts to the product of the plaintexts. This enables applications in e-voting and secure computation, but also means ElGamal is malleable (not CCA-secure).
Digital signatures. ElGamal’s signature scheme (and its DSA variant) provides authentication via the discrete log problem. Nonce reuse is catastrophic.
Ephemeral key discipline. Reusing \(k\) completely breaks both the encryption scheme (known-plaintext recovery) and the signature scheme (private key recovery).
Tip
The power of randomization. ElGamal demonstrates a fundamental insight in modern cryptography: introducing randomness into the encryption process is not a luxury but a necessity. Deterministic public-key encryption can never be semantically secure, because the attacker can always encrypt candidate messages under the public key and compare. The ephemeral key \(k\) in ElGamal – and analogous randomness in OAEP-padded RSA, lattice-based schemes, etc. – is what makes public-key encryption meaningful.
What comes next: In Chapter 30, we explore index calculus methods for attacking the discrete logarithm problem, which is the computational assumption underlying ElGamal’s security.
29.17 References#
ElGamal, T. (1985). “A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms.” IEEE Transactions on Information Theory, 31(4), 469–472. The original paper presenting both the encryption scheme and the signature scheme. Remarkably concise at only 4 pages.
Diffie, W. and Hellman, M. (1976). “New Directions in Cryptography.” IEEE Transactions on Information Theory, 22(6), 644–654. The foundational paper that introduced public-key cryptography and the Diffie–Hellman key exchange, upon which ElGamal is built.
Tsiounis, Y. and Yung, M. (1998). “On the Security of ElGamal Based Encryption.” Public Key Cryptography (PKC ‘98), Springer LNCS 1431, 117–134. Formal security analysis showing ElGamal is IND-CPA secure under the DDH assumption.
Cramer, R. and Shoup, V. (1998). “A Practical Public Key Cryptosystem Provably Secure against Adaptive Chosen Ciphertext Attack.” CRYPTO ‘98, Springer LNCS 1462, 13–25. Extends ElGamal to achieve IND-CCA2 security by adding hash-based integrity checks.
Menezes, A., van Oorschot, P., and Vanstone, S. (1996). Handbook of Applied Cryptography. CRC Press. Chapter 8. Comprehensive reference covering ElGamal encryption, signatures, and their variants in practical detail.
NIST FIPS 186-4 (2013). Digital Signature Standard (DSS). The US federal standard for digital signatures, which includes DSA – a variant of ElGamal’s signature scheme.