Chapter 25 — The RSA Cryptosystem

“The magic words are squeamish ossifrage.” — Plaintext of the RSA-129 challenge, factored by Atkins et al., 1994

In this chapter we develop the RSA public-key cryptosystem from first principles, implement it with pure Python and NumPy, and explore its mathematical structure through experiments and visualizations.

25.1 Historical Context

The year 1976 marked a turning point in the history of cryptography. In their landmark paper New Directions in Cryptography, Whitfield Diffie and Martin Hellman proposed the revolutionary concept of public-key cryptography — a system in which the encryption key could be made public without compromising the secrecy of the decryption key. This idea shattered the millennia-old assumption that sender and receiver must share a secret key in advance.

Diffie and Hellman described the concept of a public-key cryptosystem but did not provide a concrete instantiation. That challenge was taken up by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT, who in 1977 devised the first practical public-key encryption and signature scheme. Their system, published in the February 1978 issue of Communications of the ACM under the title A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, became known as RSA after the initials of its inventors.

Year	Event
1973	Clifford Cocks at GCHQ discovers an equivalent scheme (classified until 1997)
1976	Diffie and Hellman publish New Directions in Cryptography
1977	Rivest, Shamir, and Adleman invent RSA at MIT
1978	RSA paper published in Communications of the ACM
1983	RSA patented (US Patent 4,405,829; expired 2000)
1991	RSA-129 challenge posted (factored in 1994)
1998	Bleichenbacher’s padding oracle attack on PKCS#1 v1.5
2020	RSA-250 (829 bits) factored by Boudot et al.

Unknown to the public, the British mathematician Clifford Cocks, working at the Government Communications Headquarters (GCHQ), had independently discovered an equivalent scheme in 1973 — four years before Rivest, Shamir, and Adleman. Cocks’s work was classified as a military secret and was not declassified until 1997. His colleague James Ellis had earlier proposed the general concept of “non-secret encryption” in 1970, predating Diffie and Hellman by six years.

Tip

The RSA story illustrates a recurring pattern in cryptographic history: ideas developed in secrecy by intelligence agencies are independently rediscovered by academic researchers. The academic versions become the public standards precisely because they are open to scrutiny — a vindication of Kerckhoffs’s principle.

25.2 Formal Definitions

We now define the RSA cryptosystem with full mathematical precision.

Definition 25.1 (RSA Key Generation)

The RSA key generation algorithm proceeds as follows:

1. Choose two distinct large primes \(p\) and \(q\) independently and uniformly at random.

2. Compute the RSA modulus \(n = pq\).

3. Compute Euler’s totient \(\varphi(n) = (p-1)(q-1)\).

4. Choose a public exponent \(e\) with \(1 < e < \varphi(n)\) and \(\gcd(e, \varphi(n)) = 1\).

5. Compute the private exponent \(d = e^{-1} \bmod \varphi(n)\), i.e., \(ed \equiv 1 \pmod{\varphi(n)}\).

The public key is the pair \((n, e)\). The private key is \((n, d)\). The primes \(p, q\) and the totient \(\varphi(n)\) must be kept secret.

Definition 25.2 (RSA Encryption and Decryption)

Given an RSA public key \((n, e)\) and private key \((n, d)\):

• Encryption: For a message \(M \in \{0, 1, \ldots, n-1\}\), the ciphertext is

  \[ C = M^e \bmod n.\]

• Decryption: Given ciphertext \(C\), the plaintext is recovered as

  \[ M = C^d \bmod n.\]

The message space and ciphertext space are both \(\mathbb{Z}_n = \{0, 1, \ldots, n-1\}\).

Theorem 25.1 (RSA Correctness)

For any RSA key pair \((n, e, d)\) generated as in Definition 25.1 and any message \(M \in \{0, 1, \ldots, n-1\}\):

\[ (M^e)^d \equiv M \pmod{n}.\]

That is, decryption correctly recovers the original message.

Proof

Since \(ed \equiv 1 \pmod{\varphi(n)}\), we can write \(ed = 1 + k\varphi(n)\) for some non-negative integer \(k\).

Case 1: \(\gcd(M, n) = 1\). By Euler’s theorem, \(M^{\varphi(n)} \equiv 1 \pmod{n}\). Therefore:

\[ M^{ed} = M^{1 + k\varphi(n)} = M \cdot (M^{\varphi(n)})^k \equiv M \cdot 1^k = M \pmod{n}.\]

Case 2: \(\gcd(M, n) \neq 1\). Since \(n = pq\) and \(M \in \{0, \ldots, n-1\}\), if \(\gcd(M, n) \neq 1\) then either \(p \mid M\) or \(q \mid M\) (but not both, since \(M < n = pq\)).

Suppose \(p \mid M\) but \(q \nmid M\). Then:

• Modulo \(p\): \(M \equiv 0 \pmod{p}\), so \(M^{ed} \equiv 0 \equiv M \pmod{p}\).

• Modulo \(q\): Since \(\gcd(M, q) = 1\), by Fermat’s little theorem, \(M^{q-1} \equiv 1 \pmod{q}\). Since \((p-1) \mid \varphi(n)\), we have \(\varphi(n) = (p-1)(q-1)\), so

  \[ M^{ed} = M^{1 + k(p-1)(q-1)} = M \cdot (M^{q-1})^{k(p-1)} \equiv M \cdot 1 = M \pmod{q}.\]

By the Chinese Remainder Theorem, since \(M^{ed} \equiv M \pmod{p}\) and \(M^{ed} \equiv M \pmod{q}\) with \(\gcd(p, q) = 1\), we conclude \(M^{ed} \equiv M \pmod{n}\). \(\square\)

Definition 25.3 (Textbook RSA vs. Padded RSA)

Textbook RSA (also called “raw” or “plain” RSA) refers to the direct application of the encryption function \(C = M^e \bmod n\) without any preprocessing of the message \(M\). Textbook RSA is deterministic and therefore not semantically secure.

Padded RSA applies a randomized padding scheme to \(M\) before encryption. Examples include:

• PKCS#1 v1.5 (1993): deterministic structure with random bytes; vulnerable to Bleichenbacher’s chosen-ciphertext attack.

• OAEP (Optimal Asymmetric Encryption Padding, Bellare and Rogaway, 1994): provably IND-CCA2 secure in the random oracle model.

In practice, RSA should always be used with a proper padding scheme.

Danger

Never use textbook RSA in production. Textbook RSA is deterministic (the same plaintext always produces the same ciphertext), has the multiplicative homomorphic property (\(E(M_1) \cdot E(M_2) = E(M_1 M_2 \bmod n)\)), and is vulnerable to numerous attacks including chosen-ciphertext attacks, small-message attacks, and related-message attacks. Always use RSA-OAEP for encryption and RSA-PSS for signatures.

25.3 Implementation

We implement RSA from scratch using only Python’s standard library and NumPy. We begin with the fundamental number-theoretic building blocks: modular exponentiation, the extended Euclidean algorithm, Miller–Rabin primality testing, and random prime generation.

import numpy as np
import math


def mod_pow(base, exp, mod):
    """
    Compute base^exp mod mod using the square-and-multiply algorithm.
    
    This is the fundamental operation in RSA.  Naive exponentiation
    would produce astronomically large intermediate values; square-and-
    multiply keeps all values bounded by mod^2.
    
    Parameters
    ----------
    base : int
        The base.
    exp : int
        The exponent (non-negative).
    mod : int
        The modulus (positive).
    
    Returns
    -------
    int
        base^exp mod mod.
    """
    base, exp, mod = int(base), int(exp), int(mod)
    if mod == 1:
        return 0
    result = 1
    base = base % mod
    while exp > 0:
        # If exp is odd, multiply result by base
        if exp % 2 == 1:
            result = (result * base) % mod
        # Square the base
        exp = exp >> 1
        base = (base * base) % mod
    return result


def extended_gcd(a, b):
    """
    Extended Euclidean Algorithm.
    
    Returns (gcd, x, y) such that a*x + b*y = gcd(a, b).
    Used to compute modular inverses: if gcd(a, b) = 1,
    then a^{-1} mod b = x mod b.
    
    Parameters
    ----------
    a, b : int
        Input integers.
    
    Returns
    -------
    tuple of (int, int, int)
        (gcd(a,b), x, y) where a*x + b*y = gcd(a,b).
    """
    if a == 0:
        return b, 0, 1
    g, x1, y1 = extended_gcd(b % a, a)
    x = y1 - (b // a) * x1
    y = x1
    return g, x, y


def mod_inverse(a, m):
    """
    Compute the modular inverse a^{-1} mod m using the extended GCD.
    
    Parameters
    ----------
    a : int
        The integer to invert.
    m : int
        The modulus.
    
    Returns
    -------
    int
        a^{-1} mod m.
    
    Raises
    ------
    ValueError
        If gcd(a, m) != 1 (inverse does not exist).
    """
    g, x, _ = extended_gcd(a % m, m)
    if g != 1:
        raise ValueError(f'Modular inverse does not exist: gcd({a}, {m}) = {g}')
    return x % m


# --- Tests ---
# Square-and-multiply vs Python's built-in pow
assert mod_pow(7, 256, 13) == pow(7, 256, 13)
assert mod_pow(2, 1000, 1000000007) == pow(2, 1000, 1000000007)
assert mod_pow(123456789, 987654321, 1000000007) == pow(123456789, 987654321, 1000000007)

# Extended GCD
g, x, y = extended_gcd(35, 15)
assert g == 5 and 35 * x + 15 * y == 5

# Modular inverse
assert (mod_inverse(3, 26) * 3) % 26 == 1
assert (mod_inverse(7, 40) * 7) % 40 == 1
assert (mod_inverse(65537, 3120) * 65537) % 3120 == 1

print('mod_pow tests passed.')
print(f'  7^256 mod 13 = {mod_pow(7, 256, 13)}')
print(f'  2^1000 mod 10^9+7 = {mod_pow(2, 1000, 1000000007)}')
print()
print('extended_gcd tests passed.')
print(f'  gcd(35, 15) = {g}, 35*{x} + 15*{y} = {35*x + 15*y}')
print()
print('mod_inverse tests passed.')
print(f'  3^(-1) mod 26 = {mod_inverse(3, 26)}')
print(f'  65537^(-1) mod 3120 = {mod_inverse(65537, 3120)}')

mod_pow tests passed.
  7^256 mod 13 = 9
  2^1000 mod 10^9+7 = 688423210

extended_gcd tests passed.
  gcd(35, 15) = 5, 35*1 + 15*-2 = 5

mod_inverse tests passed.
  3^(-1) mod 26 = 9
  65537^(-1) mod 3120 = 2753

import numpy as np
import math


def is_probable_prime(n, k=20):
    """
    Miller-Rabin probabilistic primality test.
    
    Tests whether n is a probable prime by running k rounds of the
    Miller-Rabin test.  The probability of a composite being declared
    prime is at most 4^{-k}.
    
    Parameters
    ----------
    n : int
        The number to test (n >= 2).
    k : int
        Number of rounds (default 20, giving error probability < 2^{-40}).
    
    Returns
    -------
    bool
        True if n is probably prime, False if n is definitely composite.
    """
    if n < 2:
        return False
    if n < 4:
        return True
    if n % 2 == 0:
        return False
    
    # Write n - 1 = 2^r * d with d odd
    r, d = 0, n - 1
    while d % 2 == 0:
        r += 1
        d //= 2
    
    # Use stdlib random for witness selection
    import random as _rand
    
    for _ in range(k):
        # Choose random witness a in [2, n-2]
        a = _rand.randrange(2, n - 1)
        x = pow(a, d, n)  # Use Python built-in for speed in primality test
        
        if x == 1 or x == n - 1:
            continue
        
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False  # Definitely composite
    
    return True  # Probably prime


def generate_prime(bits, rng=None):
    """
    Generate a random prime number of the specified bit length.
    
    Parameters
    ----------
    bits : int
        Desired bit length of the prime.
    rng : numpy.random.Generator, optional
        Random number generator. If None, uses Python's stdlib random.
    
    Returns
    -------
    int
        A probable prime of the specified bit length.
    """
    if rng is None:
        import random as _rnd
        candidate = _rnd.getrandbits(bits) | (1 << (bits - 1)) | 1
        while not is_probable_prime(candidate):
            candidate = _rnd.getrandbits(bits) | (1 << (bits - 1)) | 1
        return candidate
    
    while True:
        # Generate a random odd number with the MSB set
        # to guarantee the correct bit length
        candidate = int(rng.integers(2**(bits - 1), 2**bits)) if bits <= 62 else int.from_bytes(rng.bytes((bits + 7) // 8), "big") % (2**bits - 2**(bits-1)) + 2**(bits-1)
        candidate |= 1  # Ensure odd
        candidate |= (1 << (bits - 1))  # Ensure MSB is set
        
        if is_probable_prime(candidate):
            return candidate


# --- Tests ---
# Known primes
known_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 997, 7919, 104729]
for p in known_primes:
    assert is_probable_prime(p), f'{p} should be prime'

# Known composites
known_composites = [4, 6, 8, 9, 10, 12, 15, 100, 1000, 561]  # 561 = Carmichael number
for c in known_composites:
    assert not is_probable_prime(c), f'{c} should be composite'

print('Miller-Rabin primality test passed all checks.')
print(f'  is_probable_prime(104729) = {is_probable_prime(104729)}')
print(f'  is_probable_prime(561) = {is_probable_prime(561)}  (Carmichael number)')
print()

# Generate primes of various sizes
rng = np.random.default_rng(42)
for bits in [16, 32, 64]:
    p = generate_prime(bits, rng)
    print(f'  {bits}-bit prime: {p} ({p.bit_length()} bits)')

import numpy as np
import math


class RSA:
    """
    Complete RSA implementation for educational purposes.
    
    Supports key generation, encryption, decryption, signing, and
    verification.  This is TEXTBOOK RSA without padding --- it must
    NOT be used for any real-world application.
    
    Parameters
    ----------
    bit_length : int
        Bit length of the RSA modulus n (each prime is bit_length // 2 bits).
    e : int, optional
        Public exponent (default 65537).
    seed : int, optional
        Seed for reproducibility.
    """
    
    def __init__(self, bit_length=64, e=65537, seed=None):
        self.bit_length = bit_length
        self.rng = np.random.default_rng(seed)
        self.n, self.e, self.d, self.p, self.q, self.phi_n = self._key_gen(bit_length, e)
    
    def _key_gen(self, bit_length, e):
        """
        Generate RSA key pair.
        
        Returns
        -------
        tuple
            (n, e, d, p, q, phi_n)
        """
        prime_bits = bit_length // 2
        
        while True:
            p = generate_prime(prime_bits, self.rng)
            q = generate_prime(prime_bits, self.rng)
            
            # Ensure p != q
            while p == q:
                q = generate_prime(prime_bits, self.rng)
            
            n = p * q
            phi_n = (p - 1) * (q - 1)
            
            # Check that e is coprime to phi(n)
            if math.gcd(e, phi_n) == 1:
                d = mod_inverse(e, phi_n)
                return n, e, d, p, q, phi_n
    
    def encrypt(self, m):
        """
        Encrypt message m: C = M^e mod n.
        
        Parameters
        ----------
        m : int
            Plaintext message (0 <= m < n).
        
        Returns
        -------
        int
            Ciphertext.
        """
        if not (0 <= m < self.n):
            raise ValueError(f'Message must be in [0, {self.n - 1}]')
        return mod_pow(m, self.e, self.n)
    
    def decrypt(self, c):
        """
        Decrypt ciphertext c: M = C^d mod n.
        
        Parameters
        ----------
        c : int
            Ciphertext (0 <= c < n).
        
        Returns
        -------
        int
            Decrypted plaintext.
        """
        return mod_pow(c, self.d, self.n)
    
    def sign(self, m):
        """
        Sign message m: sig = M^d mod n.
        
        In textbook RSA, signing is the same operation as decryption
        (exponentiation with the private key d).
        
        Parameters
        ----------
        m : int
            Message to sign (0 <= m < n).
        
        Returns
        -------
        int
            Digital signature.
        """
        return mod_pow(m, self.d, self.n)
    
    def verify(self, m, sig):
        """
        Verify signature: check that sig^e mod n == m.
        
        Parameters
        ----------
        m : int
            Original message.
        sig : int
            Signature to verify.
        
        Returns
        -------
        bool
            True if the signature is valid.
        """
        return mod_pow(sig, self.e, self.n) == m
    
    def public_key(self):
        """Return the public key (n, e)."""
        return (self.n, self.e)
    
    def private_key(self):
        """Return the private key (n, d)."""
        return (self.n, self.d)
    
    def __repr__(self):
        return (f'RSA(bit_length={self.bit_length}, '
                f'n={self.n}, e={self.e})')


# --- Demo: small RSA ---
rsa_small = RSA(bit_length=64, seed=42)
print(f'RSA instance: {rsa_small}')
print(f'  p = {rsa_small.p}')
print(f'  q = {rsa_small.q}')
print(f'  n = p*q = {rsa_small.n}')
print(f'  phi(n) = {rsa_small.phi_n}')
print(f'  e = {rsa_small.e}')
print(f'  d = {rsa_small.d}')
print(f'  e*d mod phi(n) = {(rsa_small.e * rsa_small.d) % rsa_small.phi_n}')
print()

# Encrypt and decrypt a message
message = 123456789
ciphertext = rsa_small.encrypt(message)
decrypted = rsa_small.decrypt(ciphertext)
print(f'Message:    {message}')
print(f'Ciphertext: {ciphertext}')
print(f'Decrypted:  {decrypted}')
print(f'Correct:    {decrypted == message}')

RSA instance: RSA(bit_length=64, n=7739571339188281783, e=65537)
  p = 2332050503
  q = 3318783761
  n = p*q = 7739571339188281783
  phi(n) = 7739571333537447520
  e = 65537
  d = 6986245341553753153
  e*d mod phi(n) = 1

Message:    123456789
Ciphertext: 6580020594073266128
Decrypted:  123456789
Correct:    True

import numpy as np

# Extensive correctness testing
rng = np.random.default_rng(2024)
n_tests = 200
all_passed = True

# Test with RSA-64
rsa_test = RSA(bit_length=64, seed=100)

for i in range(n_tests):
    m = int(rng.integers(0, min(rsa_test.n, 2**62)))
    c = rsa_test.encrypt(m)
    d = rsa_test.decrypt(c)
    if d != m:
        print(f'FAILED at message {m}: decrypted to {d}')
        all_passed = False
        break

print(f'RSA-64 encrypt/decrypt: {n_tests} random messages --- '
      f'{"ALL PASSED" if all_passed else "FAILED"}')

# Test signing and verification
all_sig_passed = True
for i in range(n_tests):
    m = int(rng.integers(0, min(rsa_test.n, 2**62)))
    sig = rsa_test.sign(m)
    valid = rsa_test.verify(m, sig)
    if not valid:
        print(f'FAILED signature verification at message {m}')
        all_sig_passed = False
        break
    # Also verify that a wrong message fails
    m_wrong = (m + 1) % rsa_test.n
    if rsa_test.verify(m_wrong, sig):
        print(f'FAILED: wrong message accepted at {m_wrong}')
        all_sig_passed = False
        break

print(f'RSA-64 sign/verify:     {n_tests} random messages --- '
      f'{"ALL PASSED" if all_sig_passed else "FAILED"}')

# Edge cases: m = 0 and m = 1
for m_edge in [0, 1]:
    c_edge = rsa_test.encrypt(m_edge)
    d_edge = rsa_test.decrypt(c_edge)
    print(f'Edge case m={m_edge}: encrypt={c_edge}, decrypt={d_edge}, correct={d_edge == m_edge}')

RSA-64 encrypt/decrypt: 200 random messages --- ALL PASSED
RSA-64 sign/verify:     200 random messages --- ALL PASSED
Edge case m=0: encrypt=0, decrypt=0, correct=True
Edge case m=1: encrypt=1, decrypt=1, correct=True

25.4 Experiments

We now explore the RSA cryptosystem through a series of experiments that illustrate its properties, performance characteristics, and vulnerabilities.

Experiment 1: RSA Key Generation and Encryption Demo

We generate RSA keys of different sizes and demonstrate the complete encrypt/decrypt cycle, including string-to-integer encoding.

import numpy as np

def text_to_int(text):
    """Convert a text string to an integer via UTF-8 byte encoding."""
    return int.from_bytes(text.encode('utf-8'), byteorder='big')

def int_to_text(number):
    """Convert an integer back to a text string."""
    length = (number.bit_length() + 7) // 8
    return number.to_bytes(length, byteorder='big').decode('utf-8')

# --- RSA-64 demo ---
print('=== RSA-64 Key Generation ===')
rsa64 = RSA(bit_length=64, seed=7)
print(f'  Public key:  (n={rsa64.n}, e={rsa64.e})')
print(f'  Private key: (n={rsa64.n}, d={rsa64.d})')
print(f'  Primes:      p={rsa64.p}, q={rsa64.q}')
print()

msg64 = 42
ct64 = rsa64.encrypt(msg64)
pt64 = rsa64.decrypt(ct64)
print(f'  Plaintext:  {msg64}')
print(f'  Ciphertext: {ct64}')
print(f'  Decrypted:  {pt64}')
print(f'  Correct:    {pt64 == msg64}')
print()

# --- RSA-128 demo ---
print('=== RSA-128 Key Generation ===')
rsa128 = RSA(bit_length=128, seed=13)
print(f'  Public key:  (n={rsa128.n}, e={rsa128.e})')
print(f'  Private key: d={rsa128.d}')
print(f'  n has {rsa128.n.bit_length()} bits')
print()

# Encrypt a short string
short_msg = 'RSA'
msg_int = text_to_int(short_msg)
print(f'  Text message: "{short_msg}"')
print(f'  As integer:   {msg_int}')

if msg_int < rsa128.n:
    ct128 = rsa128.encrypt(msg_int)
    pt128 = rsa128.decrypt(ct128)
    print(f'  Ciphertext:   {ct128}')
    print(f'  Decrypted int: {pt128}')
    print(f'  Decrypted text: "{int_to_text(pt128)}"')
    print(f'  Correct: {pt128 == msg_int}')
else:
    print(f'  Message too large for this key (need n > {msg_int})')

# --- RSA-128 signing demo ---
print()
print('=== RSA-128 Digital Signature ===')
sig_msg = 987654321
signature = rsa128.sign(sig_msg)
is_valid = rsa128.verify(sig_msg, signature)
is_forged = rsa128.verify(sig_msg + 1, signature)
print(f'  Message:   {sig_msg}')
print(f'  Signature: {signature}')
print(f'  Valid:     {is_valid}')
print(f'  Forged:    {is_forged}')

=== RSA-64 Key Generation ===
  Public key:  (n=15735851041015516589, e=65537)
  Private key: (n=15735851041015516589, d=10752683473678500677)
  Primes:      p=4023425387, q=3911058247

  Plaintext:  42
  Ciphertext: 839615484402748615
  Decrypted:  42
  Correct:    True

=== RSA-128 Key Generation ===
  Public key:  (n=177883233883319147748770692165062540419, e=65537)
  Private key: d=115762392619795865699488702873183040273
  n has 128 bits

  Text message: "RSA"
  As integer:   5395265
  Ciphertext:   43698729225894564193827363633759945291
  Decrypted int: 5395265
  Decrypted text: "RSA"
  Correct: True

=== RSA-128 Digital Signature ===
  Message:   987654321
  Signature: 32353165266846112940753651477304309360
  Valid:     True
  Forged:    False

Experiment 2: Key Generation Timing vs. Bit Length

The dominant cost in RSA key generation is finding large primes. By the Prime Number Theorem, a random \(k\)-bit integer is prime with probability approximately \(1/(k \ln 2)\), so we expect to test roughly \(k \ln 2\) candidates. Each candidate requires a Miller–Rabin test costing \(O(k^3)\) bit operations, giving an overall key-generation cost of roughly \(O(k^4)\).

Show code cell source Hide code cell source

import numpy as np
import matplotlib.pyplot as plt
import math
from collections import OrderedDict
import time

bit_lengths = [32, 48, 64, 80, 96, 112, 128, 160, 192, 256]
n_trials = 5
timing_results = OrderedDict()

for bl in bit_lengths:
    times = []
    for trial in range(n_trials):
        t0 = time.perf_counter()
        _ = RSA(bit_length=bl, seed=trial * 100 + bl)
        t1 = time.perf_counter()
        times.append(t1 - t0)
    timing_results[bl] = times
    avg = np.mean(times)
    print(f'  RSA-{int(bl):>3d}: avg {float(avg*1000):.2f} ms  '
          f'(min {float(np.min(times)*1000):.2f}, max {float(np.max(times)*1000):.2f})')

# Plot
fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(13, 5))

means = [np.mean(timing_results[bl]) * 1000 for bl in bit_lengths]
stds = [np.std(timing_results[bl]) * 1000 for bl in bit_lengths]

ax1.errorbar(bit_lengths, means, yerr=stds, fmt='o-', color='#1565C0',
             linewidth=2, markersize=7, capsize=4, capthick=1.5,
             ecolor='#90CAF9', label='Measured')
ax1.set_xlabel('RSA Modulus Bit Length', fontsize=12, fontweight='bold')
ax1.set_ylabel('Key Generation Time (ms)', fontsize=12, fontweight='bold')
ax1.set_title('RSA Key Generation Time (linear scale)', fontsize=13, fontweight='bold')
ax1.grid(True, alpha=0.3)
ax1.legend(fontsize=10)

# Log-log plot to check polynomial scaling
ax2.loglog(bit_lengths, means, 'o-', color='#C62828', linewidth=2, markersize=7,
           label='Measured')

# Fit a power law: log(t) = a * log(bits) + b
log_bits = np.log(np.array(bit_lengths, dtype=float))
log_times = np.log(np.array(means))
coeffs = np.polyfit(log_bits, log_times, 1)
fitted = np.exp(np.polyval(coeffs, log_bits))
ax2.loglog(bit_lengths, fitted, '--', color='#388E3C', linewidth=2,
           label=f'Power law fit: $O(k^{{{float(coeffs[0]):.2f}}})$')

ax2.set_xlabel('RSA Modulus Bit Length', fontsize=12, fontweight='bold')
ax2.set_ylabel('Key Generation Time (ms)', fontsize=12, fontweight='bold')
ax2.set_title('RSA Key Generation Time (log-log scale)', fontsize=13, fontweight='bold')
ax2.grid(True, alpha=0.3, which='both')
ax2.legend(fontsize=10)

plt.tight_layout()
plt.savefig('fig_25_1_rsa_keygen_timing.png', dpi=150, bbox_inches='tight', facecolor='white')
plt.show()

print(f'\nPower-law exponent: {float(coeffs[0]):.2f}')
print(f'Expected ~3--4 due to O(k^3) Miller-Rabin with O(k) expected candidates.')

  RSA- 32: avg 0.13 ms  (min 0.09, max 0.18)
  RSA- 48: avg 0.16 ms  (min 0.09, max 0.25)
  RSA- 64: avg 0.29 ms  (min 0.23, max 0.37)
  RSA- 80: avg 0.36 ms  (min 0.24, max 0.46)
  RSA- 96: avg 0.57 ms  (min 0.32, max 0.93)
  RSA-112: avg 0.70 ms  (min 0.46, max 1.26)
  RSA-128: avg 1.06 ms  (min 0.84, max 1.42)
  RSA-160: avg 1.78 ms  (min 0.83, max 2.32)
  RSA-192: avg 3.11 ms  (min 2.30, max 4.70)
  RSA-256: avg 6.50 ms  (min 4.65, max 9.87)

Power-law exponent: 1.94
Expected ~3--4 due to O(k^3) Miller-Rabin with O(k) expected candidates.

Experiment 3: Textbook RSA Malleability

Textbook RSA has the multiplicative homomorphic property: given ciphertexts \(C_1 = M_1^e \bmod n\) and \(C_2 = M_2^e \bmod n\), an adversary can compute

\[ C_1 \cdot C_2 \bmod n = (M_1 M_2)^e \bmod n = E(M_1 M_2 \bmod n)\]

without knowing the private key. This means textbook RSA is malleable: an adversary can manipulate ciphertexts in a meaningful way.

Show code cell source Hide code cell source

import numpy as np
import matplotlib.pyplot as plt

# Demonstrate multiplicative homomorphism
rsa_mall = RSA(bit_length=128, seed=99)
n = rsa_mall.n

rng = np.random.default_rng(42)
n_demo = 10

print('Textbook RSA Multiplicative Homomorphism')
print('=' * 65)
print(f'{"M1":>12s} {"M2":>12s} {"M1*M2 mod n":>18s} '
      f'{"D(C1*C2)":>18s} {"Match":>6s}')
print('-' * 65)

results = []
for _ in range(n_demo):
    m1 = int(rng.integers(2, min(n, 10**15)))
    m2 = int(rng.integers(2, min(n, 10**15)))
    
    c1 = rsa_mall.encrypt(m1)
    c2 = rsa_mall.encrypt(m2)
    
    # Adversary multiplies ciphertexts (no private key needed!)
    c_product = (c1 * c2) % n
    
    # Decrypt the product ciphertext
    m_product_decrypted = rsa_mall.decrypt(c_product)
    
    # Expected: (m1 * m2) mod n
    m_product_expected = (m1 * m2) % n
    
    match = m_product_decrypted == m_product_expected
    results.append(match)
    
    print(f'{int(m1):>12d} {int(m2):>12d} {int(m_product_expected):>18d} '
          f'{int(m_product_decrypted):>18d} {str(match):>6s}')

print(f'\nAll matches: {all(results)}')
print()
print('Attack scenario: Eve intercepts C = E(price) and wants to double it.')
price = 5000
c_price = rsa_mall.encrypt(price)
c_two = rsa_mall.encrypt(2)
c_doubled = (c_price * c_two) % n
doubled_price = rsa_mall.decrypt(c_doubled)
print(f'  Original price:  {price}')
print(f'  Manipulated:     {doubled_price}')
print(f'  Equals 2*price:  {doubled_price == 2 * price}')

# Visualize: scatter plot showing that D(C1*C2) = M1*M2 mod n
rsa_vis = RSA(bit_length=64, seed=55)
n_vis = rsa_vis.n
rng_vis = np.random.default_rng(0)
n_points = 200

expected_products = []
decrypted_products = []

for _ in range(n_points):
    m1 = int(rng_vis.integers(2, min(n_vis // 2, 10**9)))
    m2 = int(rng_vis.integers(2, min(n_vis // 2, 10**9)))
    c1 = rsa_vis.encrypt(m1)
    c2 = rsa_vis.encrypt(m2)
    c_prod = (c1 * c2) % n_vis
    d_prod = rsa_vis.decrypt(c_prod)
    expected_products.append((m1 * m2) % n_vis)
    decrypted_products.append(d_prod)

fig, ax = plt.subplots(figsize=(7, 7))
ax.scatter(expected_products, decrypted_products, alpha=0.5, s=15,
           color='#1565C0', edgecolors='none')

# y = x line
lim = max(max(expected_products), max(decrypted_products))
ax.plot([0, lim], [0, lim], 'r--', alpha=0.7, linewidth=1.5, label='$y = x$')

ax.set_xlabel('$(M_1 * M_2) \; \mathrm{mod} \; n$', fontsize=12, fontweight='bold')
ax.set_ylabel('$D(C_1 * C_2 \; \mathrm{mod} \; n)$', fontsize=12, fontweight='bold')
ax.set_title('Figure 25.2: RSA Multiplicative Homomorphism\n'
             '$D(E(M_1) * E(M_2)) = M_1 * M_2 \; \mathrm{mod} \; n$',
             fontsize=12, fontweight='bold')
ax.legend(fontsize=11)
ax.set_aspect('equal')

plt.tight_layout()
plt.savefig('fig_25_2_rsa_malleability.png', dpi=150, bbox_inches='tight', facecolor='white')
plt.show()

Textbook RSA Multiplicative Homomorphism
=================================================================
          M1           M2        M1*M2 mod n           D(C1*C2)  Match
-----------------------------------------------------------------
773956048555963 438878439752053 339672623026905213766414642039 339672623026905213766414642039   True
858597919911382 697368029059364 598758739163070126923697281048 598758739163070126923697281048   True
94177347887651 975622351636756 91881525617062943819050100156 91881525617062943819050100156   True
761139701990353 786064305276954 598304751063754632674701224762 598304751063754632674701224762   True
128113632675547 450385937895568 57700578609784522370513275696 57700578609784522370513275696   True
370798024232582 926764988848601 343642626792992140600809317782 343642626792992140600809317782   True
643865120080665 822761613270830 529747504926384615984091501950 529747504926384615984091501950   True
443414198827332 227238721784778 100760875762744331649687952296 100760875762744331649687952296   True
554584787015835 63817256104177 35392079384469997605708642795 35392079384469997605708642795   True
827631171992582 631664399122065 522785146951384740497492521830 522785146951384740497492521830   True

All matches: True

Attack scenario: Eve intercepts C = E(price) and wants to double it.
  Original price:  5000
  Manipulated:     10000
  Equals 2*price:  True

<>:79: SyntaxWarning: invalid escape sequence '\;'
<>:80: SyntaxWarning: invalid escape sequence '\;'
<>:82: SyntaxWarning: invalid escape sequence '\;'
<>:79: SyntaxWarning: invalid escape sequence '\;'
<>:80: SyntaxWarning: invalid escape sequence '\;'
<>:82: SyntaxWarning: invalid escape sequence '\;'
/var/folders/z7/wp7m8p7x1250jzvklw5z24mm0000gn/T/ipykernel_7284/877131995.py:79: SyntaxWarning: invalid escape sequence '\;'
  ax.set_xlabel('$(M_1 * M_2) \; \mathrm{mod} \; n$', fontsize=12, fontweight='bold')
/var/folders/z7/wp7m8p7x1250jzvklw5z24mm0000gn/T/ipykernel_7284/877131995.py:80: SyntaxWarning: invalid escape sequence '\;'
  ax.set_ylabel('$D(C_1 * C_2 \; \mathrm{mod} \; n)$', fontsize=12, fontweight='bold')
/var/folders/z7/wp7m8p7x1250jzvklw5z24mm0000gn/T/ipykernel_7284/877131995.py:82: SyntaxWarning: invalid escape sequence '\;'
  '$D(E(M_1) * E(M_2)) = M_1 * M_2 \; \mathrm{mod} \; n$',

Observation

Every point lies exactly on the line \(y = x\), confirming the multiplicative homomorphism \(D(E(M_1) \cdot E(M_2) \bmod n) = M_1 \cdot M_2 \bmod n\). This property is devastating for textbook RSA in applications where an adversary can manipulate ciphertexts. For example, in an auction protocol, an adversary who sees \(C = E(\text{bid})\) can submit \(C \cdot E(2) \bmod n\) to double the bid without knowing its value.

Experiment 4: Visualizing the RSA Permutation

For a small RSA modulus, the encryption function \(f(M) = M^e \bmod n\) acts as a permutation on \(\mathbb{Z}_n^*\) (the integers coprime to \(n\)). We visualize this permutation to gain intuition about its structure — or more precisely, its apparent lack of structure, which is what makes RSA hard to invert.

Show code cell source Hide code cell source

import numpy as np
import matplotlib.pyplot as plt
import math

# Use small primes for visualization
p_small, q_small = 23, 29
n_small = p_small * q_small  # n = 667
phi_small = (p_small - 1) * (q_small - 1)  # phi = 22 * 28 = 616
e_small = 3  # Small e for clear visualization
assert math.gcd(e_small, phi_small) == 1
d_small = mod_inverse(e_small, phi_small)

print(f'Small RSA parameters: p={p_small}, q={q_small}, n={n_small}')
print(f'phi(n)={phi_small}, e={e_small}, d={d_small}')
print(f'e*d mod phi(n) = {(e_small * d_small) % phi_small}')
print()

# Compute the RSA permutation for all M in [0, n-1]
messages = np.arange(n_small)
ciphertexts = np.array([pow(int(m), e_small, n_small) for m in messages])

# Verify it is a permutation on Z_n* (elements coprime to n)
coprime_mask = np.array([math.gcd(int(m), n_small) == 1 for m in messages])
coprime_messages = messages[coprime_mask]
coprime_ciphertexts = ciphertexts[coprime_mask]
is_permutation = len(set(coprime_ciphertexts)) == len(coprime_ciphertexts)
print(f'Number of elements in Z_n*: {len(coprime_messages)} (= phi(n) = {phi_small})')
print(f'RSA encryption is a permutation on Z_n*: {is_permutation}')
print()

# Four-panel visualization
fig, axes = plt.subplots(2, 2, figsize=(13, 11))

# Panel 1: Scatter plot of M vs C = M^e mod n
ax1 = axes[0, 0]
ax1.scatter(messages, ciphertexts, s=1.5, alpha=0.6, color='#1565C0')
ax1.set_xlabel('Plaintext $M$', fontsize=11)
ax1.set_ylabel('Ciphertext $C = M^e \; \mathrm{mod} \; n$', fontsize=11)
ax1.set_title(f'RSA Permutation ($n={n_small}$, $e={e_small}$)', fontsize=12, fontweight='bold')
ax1.set_xlim(0, n_small)
ax1.set_ylim(0, n_small)

# Panel 2: Histogram of ciphertexts (should be roughly uniform)
ax2 = axes[0, 1]
ax2.hist(ciphertexts, bins=50, color='#388E3C', alpha=0.7, edgecolor='black', linewidth=0.3)
ax2.set_xlabel('Ciphertext value', fontsize=11)
ax2.set_ylabel('Frequency', fontsize=11)
ax2.set_title('Distribution of Ciphertexts', fontsize=12, fontweight='bold')

# Panel 3: Fixed points (M such that M^e = M mod n)
ax3 = axes[1, 0]
fixed_points = messages[ciphertexts == messages]
print(f'Fixed points (M^e = M mod n): {len(fixed_points)}')
if len(fixed_points) <= 20:
    print(f'  Values: {fixed_points}')

ax3.scatter(messages, ciphertexts, s=1.5, alpha=0.3, color='#BBDEFB')
ax3.scatter(fixed_points, fixed_points, s=30, color='#C62828', zorder=5,
            label=f'{len(fixed_points)} fixed points', edgecolors='black', linewidth=0.5)
ax3.plot([0, n_small], [0, n_small], 'k--', alpha=0.3, linewidth=1)
ax3.set_xlabel('Plaintext $M$', fontsize=11)
ax3.set_ylabel('Ciphertext $C$', fontsize=11)
ax3.set_title('Fixed Points of RSA Encryption', fontsize=12, fontweight='bold')
ax3.legend(fontsize=10)
ax3.set_xlim(0, n_small)
ax3.set_ylim(0, n_small)

# Panel 4: Cycle structure
# Find all cycles in the RSA permutation (on Z_n* only)
visited = set()
cycle_lengths = []
for m in coprime_messages:
    m_int = int(m)
    if m_int in visited:
        continue
    cycle = []
    current = m_int
    while current not in visited:
        visited.add(current)
        cycle.append(current)
        current = pow(current, e_small, n_small)
    cycle_lengths.append(len(cycle))

ax4 = axes[1, 1]
unique_lengths, counts = np.unique(cycle_lengths, return_counts=True)
ax4.bar(unique_lengths, counts, color='#F57C00', edgecolor='black', linewidth=0.5)
ax4.set_xlabel('Cycle Length', fontsize=11)
ax4.set_ylabel('Number of Cycles', fontsize=11)
ax4.set_title('Cycle Structure of RSA Permutation', fontsize=12, fontweight='bold')

print(f'\nCycle structure: {len(cycle_lengths)} cycles')
for cl, cnt in zip(unique_lengths, counts):
    print(f'  Length {cl}: {cnt} cycle(s)')

fig.suptitle(f'Figure 25.3: RSA Permutation Analysis ($p={p_small}$, $q={q_small}$, '
             f'$n={n_small}$, $e={e_small}$)',
             fontsize=13, fontweight='bold', y=1.01)

plt.tight_layout()
plt.savefig('fig_25_3_rsa_permutation.png', dpi=150, bbox_inches='tight', facecolor='white')
plt.show()

<>:38: SyntaxWarning: invalid escape sequence '\;'
<>:38: SyntaxWarning: invalid escape sequence '\;'
/var/folders/z7/wp7m8p7x1250jzvklw5z24mm0000gn/T/ipykernel_7284/1506004912.py:38: SyntaxWarning: invalid escape sequence '\;'
  ax1.set_ylabel('Ciphertext $C = M^e \; \mathrm{mod} \; n$', fontsize=11)

Small RSA parameters: p=23, q=29, n=667
phi(n)=616, e=3, d=411
e*d mod phi(n) = 1

Number of elements in Z_n*: 616 (= phi(n) = 616)
RSA encryption is a permutation on Z_n*: True

Fixed points (M^e = M mod n): 9
  Values: [  0   1 115 116 231 436 551 552 666]

Cycle structure: 42 cycles
  Length 1: 4 cycle(s)
  Length 2: 2 cycle(s)
  Length 5: 8 cycle(s)
  Length 6: 8 cycle(s)
  Length 10: 4 cycle(s)
  Length 30: 16 cycle(s)

Observation

The scatter plot of \(M\) vs. \(M^e \bmod n\) appears pseudorandom, which is precisely the property that makes RSA hard to invert. The cycle structure reveals that the permutation decomposes into cycles of various lengths; fixed points (\(M^e \equiv M\)) always include \(M \in \{0, 1\}\) and potentially others depending on \(e\) and \(n\).

Experiment 5: Square-and-Multiply Step Count

We instrument the square-and-multiply algorithm to count the number of multiplications and squarings, verifying that the cost is \(O(\log e)\).

Show code cell source Hide code cell source

import numpy as np
import matplotlib.pyplot as plt
import math
import random as _rnd


def mod_pow_instrumented(base, exp, mod):
    """
    Square-and-multiply with operation counting.
    
    Returns
    -------
    tuple
        (result, n_squarings, n_multiplications)
    """
    if mod == 1:
        return 0, 0, 0
    result = 1
    base = base % mod
    n_sq = 0
    n_mul = 0
    while exp > 0:
        if exp % 2 == 1:
            result = (result * base) % mod
            n_mul += 1
        exp = exp >> 1
        if exp > 0:  # Don't count the final unnecessary squaring
            base = (base * base) % mod
            n_sq += 1
    return result, n_sq, n_mul


# Analyze for various exponent sizes
rng = np.random.default_rng(42)
exp_bit_lengths = list(range(4, 65, 2))
n_trials_per = 20

avg_squarings = []
avg_multiplications = []
avg_total = []

test_mod = 2**64 + 13  # A large prime modulus

for bits in exp_bit_lengths:
    sq_list = []
    mul_list = []
    for _ in range(n_trials_per):
        exp_val = _rnd.randrange(2**(bits-1), 2**bits)
        base_val = _rnd.randrange(2, test_mod)
        _, sq, ml = mod_pow_instrumented(base_val, exp_val, test_mod)
        sq_list.append(sq)
        mul_list.append(ml)
    avg_squarings.append(np.mean(sq_list))
    avg_multiplications.append(np.mean(mul_list))
    avg_total.append(np.mean(sq_list) + np.mean(mul_list))

fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(13, 5))

ax1.plot(exp_bit_lengths, avg_squarings, 's-', color='#1565C0', linewidth=2,
         markersize=5, label='Squarings')
ax1.plot(exp_bit_lengths, avg_multiplications, 'o-', color='#C62828', linewidth=2,
         markersize=5, label='Multiplications')
ax1.plot(exp_bit_lengths, avg_total, '^-', color='#388E3C', linewidth=2,
         markersize=5, label='Total operations')

# Theoretical: squarings = bits-1, multiplications ~ bits/2 (Hamming weight)
theory_sq = np.array(exp_bit_lengths) - 1
theory_mul = np.array(exp_bit_lengths) / 2
ax1.plot(exp_bit_lengths, theory_sq, '--', color='#1565C0', alpha=0.4, label='Theory: $k-1$ sq.')
ax1.plot(exp_bit_lengths, theory_mul, '--', color='#C62828', alpha=0.4, label='Theory: $k/2$ mult.')

ax1.set_xlabel('Exponent Bit Length $k$', fontsize=12, fontweight='bold')
ax1.set_ylabel('Number of Operations', fontsize=12, fontweight='bold')
ax1.set_title('Square-and-Multiply: Operation Count', fontsize=12, fontweight='bold')
ax1.legend(fontsize=9)
ax1.grid(True, alpha=0.3)

# Ratio of total operations to bit length
ratios = np.array(avg_total) / np.array(exp_bit_lengths)
ax2.plot(exp_bit_lengths, ratios, 'o-', color='#6A1B9A', linewidth=2, markersize=5)
ax2.axhline(y=1.5, color='gray', linestyle='--', alpha=0.5, label='Expected ratio $\\approx 1.5$')
ax2.set_xlabel('Exponent Bit Length $k$', fontsize=12, fontweight='bold')
ax2.set_ylabel('Total Operations / Bit Length', fontsize=12, fontweight='bold')
ax2.set_title('Operations per Bit (should be ~1.5)', fontsize=12, fontweight='bold')
ax2.legend(fontsize=10)
ax2.grid(True, alpha=0.3)
ax2.set_ylim(1.0, 2.0)

fig.suptitle('Figure 25.4: Square-and-Multiply Algorithm Analysis',
             fontsize=13, fontweight='bold', y=1.01)

plt.tight_layout()
plt.savefig('fig_25_4_square_multiply.png', dpi=150, bbox_inches='tight', facecolor='white')
plt.show()

print(f'Average ratio (total ops / bit length): {float(np.mean(ratios)):.3f}')
print(f'Expected: ~1.5 (k-1 squarings + k/2 multiplications for random exponents)')

Average ratio (total ops / bit length): 1.475
Expected: ~1.5 (k-1 squarings + k/2 multiplications for random exponents)

Experiment 6: Comparing RSA Encryption with Different Public Exponents

Common choices for the public exponent \(e\) are \(3\), \(17\), and \(65537 = 2^{16} + 1\) (a Fermat prime). Smaller \(e\) gives faster encryption but requires more care with padding to avoid attacks.

Show code cell source Hide code cell source

import numpy as np
import matplotlib.pyplot as plt
import time
import math

# Generate keys with different public exponents
exponents = [3, 17, 257, 65537]
bit_length = 128
n_timing_trials = 100

enc_times = {}
dec_times = {}

for e_val in exponents:
    try:
        rsa_e = RSA(bit_length=bit_length, e=e_val, seed=e_val)
    except Exception:
        print(f'  Skipping e={e_val} (incompatible with generated primes)')
        continue
    
    rng_t = np.random.default_rng(0)
    e_times = []
    d_times = []
    
    for _ in range(n_timing_trials):
        m = int(rng_t.integers(2, min(rsa_e.n, 2**62)))
        
        t0 = time.perf_counter()
        c = rsa_e.encrypt(m)
        t1 = time.perf_counter()
        e_times.append(t1 - t0)
        
        t0 = time.perf_counter()
        _ = rsa_e.decrypt(c)
        t1 = time.perf_counter()
        d_times.append(t1 - t0)
    
    enc_times[e_val] = np.mean(e_times) * 1e6  # microseconds
    dec_times[e_val] = np.mean(d_times) * 1e6
    
    print(f'  e={int(e_val):>6d} ({int(e_val.bit_length()):>2d} bits, '
          f'Hamming wt={bin(e_val).count("1")}): '
          f'enc={float(enc_times[e_val]):.1f} us, dec={float(dec_times[e_val]):.1f} us')

# Bar chart
fig, ax = plt.subplots(figsize=(10, 5.5))

e_labels = [str(e) for e in enc_times.keys()]
x = np.arange(len(e_labels))
width = 0.35

bars_enc = ax.bar(x - width/2, list(enc_times.values()), width,
                  label='Encryption', color='#1565C0', edgecolor='black', linewidth=0.5)
bars_dec = ax.bar(x + width/2, list(dec_times.values()), width,
                  label='Decryption', color='#C62828', edgecolor='black', linewidth=0.5)

ax.set_xlabel('Public Exponent $e$', fontsize=12, fontweight='bold')
ax.set_ylabel('Time ($\\mu$s)', fontsize=12, fontweight='bold')
ax.set_title('Figure 25.5: RSA-128 Encryption vs. Decryption Time\n'
             'for Different Public Exponents', fontsize=12, fontweight='bold')
ax.set_xticks(x)
ax.set_xticklabels(e_labels, fontsize=11)
ax.legend(fontsize=11)
ax.spines['top'].set_visible(False)
ax.spines['right'].set_visible(False)

plt.tight_layout()
plt.savefig('fig_25_5_rsa_exponent_timing.png', dpi=150, bbox_inches='tight', facecolor='white')
plt.show()

print()
print('Note: Encryption with small e is fast because square-and-multiply')
print('uses O(log e) operations. Decryption with d is always slow because')
print('d is typically close to n in bit length regardless of e.')

  e=     3 ( 2 bits, Hamming wt=2): enc=1.1 us, dec=53.6 us
  e=    17 ( 5 bits, Hamming wt=2): enc=1.8 us, dec=50.9 us
  e=   257 ( 9 bits, Hamming wt=2): enc=2.7 us, dec=49.0 us
  e= 65537 (17 bits, Hamming wt=2): enc=5.0 us, dec=49.8 us

Note: Encryption with small e is fast because square-and-multiply
uses O(log e) operations. Decryption with d is always slow because
d is typically close to n in bit length regardless of e.

Observation

Encryption time grows with \(\log_2 e\) (and the Hamming weight of \(e\)), while decryption time remains roughly constant because \(d\) is always close to \(n\) in size regardless of \(e\). The standard choice \(e = 65537 = 2^{16} + 1\) has Hamming weight 2 (only two set bits), making encryption very efficient while being large enough to resist certain small-exponent attacks.

25.5 Exercises

---

Exercise 25.1 (Toy RSA by Hand). Let \(p = 61\) and \(q = 53\).

(a) Compute \(n\) and \(\varphi(n)\).
(b) Verify that \(e = 17\) is a valid public exponent.
(c) Compute the private exponent \(d = e^{-1} \bmod \varphi(n)\) using the extended Euclidean algorithm.
(d) Encrypt the message \(M = 65\) and then decrypt the resulting ciphertext.
(e) Sign the message \(M = 100\) and verify the signature.

Hint

\(n = 61 \times 53 = 3233\) and \(\varphi(n) = 60 \times 52 = 3120\). Since \(\gcd(17, 3120) = 1\), the exponent \(e = 17\) is valid. Apply the extended Euclidean algorithm to find \(d\) such that \(17d \equiv 1 \pmod{3120}\). You should find \(d = 2753\). Then \(C = 65^{17} \bmod 3233\) and \(M = C^{2753} \bmod 3233\). Use repeated squaring to make the computation manageable.

---

Exercise 25.2 (Fixed Points of RSA). A fixed point of RSA encryption is a message \(M\) such that \(M^e \equiv M \pmod{n}\).

(a) Prove that \(M = 0\) and \(M = 1\) are always fixed points.
(b) For \(n = pq\), prove that \(M = n - 1\) is a fixed point if and only if \(e\) is odd (which it always is in RSA).
(c) Show that the number of fixed points of the RSA permutation is exactly \((1 + \gcd(e-1, p-1))(1 + \gcd(e-1, q-1))\), using the Chinese Remainder Theorem.

Hint

By CRT, \(M^e \equiv M \pmod{n}\) if and only if \(M^e \equiv M \pmod{p}\) and \(M^e \equiv M \pmod{q}\). The equation \(M^e - M \equiv M(M^{e-1} - 1) \equiv 0 \pmod{p}\) has solutions \(M \equiv 0\) and \(M^{e-1} \equiv 1 \pmod{p}\). The number of solutions to \(x^{e-1} \equiv 1 \pmod{p}\) in \(\mathbb{Z}_p^*\) is \(\gcd(e-1, p-1)\) by Lagrange’s theorem. So modulo \(p\) there are \(1 + \gcd(e-1, p-1)\) solutions. Similarly for \(q\). By CRT, the total count is the product.

---

Exercise 25.3 (Small Message Attack). Suppose Alice encrypts a message \(M < n^{1/e}\) using textbook RSA with \(e = 3\).

(a) Show that the ciphertext \(C = M^3\) (as an integer, without reduction modulo \(n\)). This means the message can be recovered by computing \(M = \lfloor C^{1/3} \rfloor\).
(b) Implement this attack. Generate an RSA-256 key with \(e = 3\), encrypt a small message, and recover it by taking the integer cube root.
(c) Explain why OAEP padding prevents this attack.

Hint

If \(M < n^{1/3}\), then \(M^3 < n\), so the modular reduction \(\bmod n\) has no effect: \(C = M^3 \bmod n = M^3\). To find \(M\), compute the integer cube root of \(C\). In Python, you can use a binary search or Newton’s method. For part (c), note that OAEP expands the message to fill the full range \([0, n-1]\), so the padded message is never small enough for this attack to apply.

---

Exercise 25.4 (Common Modulus Attack). Suppose two users share the same RSA modulus \(n\) but have different public exponents \(e_1\) and \(e_2\) with \(\gcd(e_1, e_2) = 1\). A message \(M\) is encrypted to both users: \(C_1 = M^{e_1} \bmod n\) and \(C_2 = M^{e_2} \bmod n\).

(a) Show that an adversary who knows \(C_1\), \(C_2\), \(e_1\), \(e_2\), and \(n\) can recover \(M\) without knowing either private key.
(b) Implement this attack and demonstrate it with a concrete example.

Hint

Since \(\gcd(e_1, e_2) = 1\), the extended Euclidean algorithm finds integers \(a, b\) such that \(a e_1 + b e_2 = 1\). Then:

\[ C_1^a \cdot C_2^b \equiv M^{a e_1} \cdot M^{b e_2} = M^{a e_1 + b e_2} = M^1 = M \pmod{n}.\]

If \(a\) or \(b\) is negative (say \(b < 0\)), compute \(C_2^{-1} \bmod n\) first, then raise to the power \(|b|\).

---

Exercise 25.5 (Wiener’s Attack on Small \(d\)). If the private exponent \(d\) is small (\(d < \frac{1}{3} n^{1/4}\)), Wiener’s attack can recover \(d\) from the public key \((n, e)\) alone.

(a) Explain why \(e/n\) is a good approximation to \(k/d\) for some integer \(k\), and why the convergents of the continued fraction expansion of \(e/n\) will include \(k/d\).
(b) Implement the continued fraction expansion algorithm.
(c) Implement Wiener’s attack: generate an RSA key with artificially small \(d\), then recover \(d\) from \((n, e)\) using continued fractions.

Hint

From \(ed \equiv 1 \pmod{\varphi(n)}\), we get \(ed = 1 + k\varphi(n)\) for some \(k\). Dividing: \(\frac{e}{\varphi(n)} = \frac{k}{d} + \frac{1}{d \cdot \varphi(n)}\). Since \(\varphi(n) \approx n\) (the difference is \(O(\sqrt{n})\)), we have \(\frac{e}{n} \approx \frac{k}{d}\), and the error is small enough that \(k/d\) appears among the convergents of the continued fraction expansion of \(e/n\). Check each convergent \((k_i, d_i)\): if \(d_i\) is odd, \(\varphi_i = (e d_i - 1) / k_i\) is an integer, and \(n - \varphi_i + 1\) has a perfect square discriminant, then \(d_i\) is the private key.

25.6 Summary

Concept	Key Point
Key generation	Choose primes \(p, q\); compute \(n = pq\), \(\varphi(n) = (p-1)(q-1)\), public \(e\), private \(d = e^{-1} \bmod \varphi(n)\)
Encryption	\(C = M^e \bmod n\) (fast with small \(e\))
Decryption	\(M = C^d \bmod n\) (slow; \(d \approx n\) in size)
Correctness	Follows from Euler’s theorem + CRT
Security assumption	Factoring \(n = pq\) is computationally hard
Textbook RSA	Deterministic, malleable, homomorphic — not secure
Padded RSA	OAEP provides IND-CCA2 security in the random oracle model
Standard exponent	\(e = 65537 = 2^{16} + 1\) (fast, safe)
Square-and-multiply	\(O(\log e)\) modular multiplications for encryption

The RSA cryptosystem remains one of the most widely deployed public-key algorithms, though it is gradually being supplemented by elliptic curve cryptography (which offers equivalent security with shorter keys) and will eventually be replaced by post-quantum algorithms once large-scale quantum computers become practical.

Tip

Looking ahead. In Chapter 26 we will study attacks on RSA in detail: factoring algorithms (trial division, Pollard’s \(\rho\), the quadratic sieve, and the general number field sieve), Wiener’s continued fraction attack on small private exponents, and Coppersmith’s method for exploiting small public exponents. These attacks will motivate the parameter choices used in modern RSA deployments.

25.7 References

1. R. L. Rivest, A. Shamir, and L. Adleman, “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems,” Communications of the ACM, 21(2), pp. 120–126, February 1978.
   The foundational RSA paper. Describes key generation, encryption, decryption, and digital signatures. Includes a discussion of the security of the system based on the difficulty of factoring large integers.

2. W. Diffie and M. Hellman, “New Directions in Cryptography,” IEEE Transactions on Information Theory, IT-22(6), pp. 644–654, November 1976.
   The paper that introduced the concept of public-key cryptography and the Diffie–Hellman key exchange protocol. This work provided the conceptual framework that RSA realized as a concrete system.

3. C. C. Cocks, “A Note on Non-Secret Encryption,” CESG internal memorandum, 1973 (declassified 1997).
   Cocks’s classified discovery of an RSA-equivalent scheme at GCHQ, four years before Rivest, Shamir, and Adleman. The memorandum was declassified in 1997 and is now available from GCHQ’s historical archives.

4. D. Boneh, “Twenty Years of Attacks on the RSA Cryptosystem,” Notices of the AMS, 46(2), pp. 203–213, 1999.
   An excellent survey of attacks on RSA, including small exponent attacks, Wiener’s attack, timing attacks, and fault attacks. Essential reading for understanding RSA’s security landscape.

5. A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone, Handbook of Applied Cryptography, CRC Press, 1996 (Chapter 8).
   Comprehensive reference for public-key cryptography including RSA key generation, padding schemes, and implementation considerations.

6. M. Bellare and P. Rogaway, “Optimal Asymmetric Encryption — How to Encrypt with RSA,” EUROCRYPT ‘94, LNCS 950, pp. 92–111, 1994.
   Introduces the OAEP padding scheme that makes RSA provably IND-CCA2 secure in the random oracle model, addressing the vulnerabilities of textbook RSA.