rsa-tls-certificates.ipynb

Kernel: SageMath 10.0

Connect: RSA in TLS Certificates

Module 04 | Real-World Connections

Trace how RSA from Module 04 authenticates web servers in TLS.

Introduction

When you visit an HTTPS website, your browser verifies the server's identity before exchanging any sensitive data. This verification relies on digital certificates signed with RSA.

Every concept from Module 04 is at work in this process:

• Prime generation (Notebook 04e) creates the CA's key pair

• Modular exponentiation (Notebook 04f) performs signing and verification

• Euler's theorem (Notebook 04c) guarantees correctness

• The extended Euclidean algorithm (Notebook 04b) computes the private key

Let's trace exactly how this works.

The Certificate Chain

TLS uses a chain of trust:

1. Root CA (Certificate Authority): A trusted entity whose public key is pre-installed in your browser. Examples: DigiCert, Let's Encrypt, GlobalSign.

2. Intermediate CA: Signed by the root CA. The root CA delegates signing authority.

3. Server certificate: Signed by an intermediate CA. Contains the server's public key and domain name.

Your browser verifies: Root CA signature on Intermediate CA, then Intermediate CA signature on Server Certificate. Each signature is RSA (or ECDSA).

Let's build a toy version of this chain.

# === Step 1: Generate key pairs for our toy PKI ===

import hashlib

def generate_rsa_keypair(bits=30):
    """Generate a small RSA key pair for demonstration."""
    p = random_prime(2^bits, lbound=2^(bits-1))
    q = random_prime(2^bits, lbound=2^(bits-1))
    while p == q:
        q = random_prime(2^bits, lbound=2^(bits-1))
    n = p * q
    phi_n = (p - 1) * (q - 1)
    e = 65537
    while gcd(e, phi_n) != 1:
        e = next_prime(e)
    d = inverse_mod(e, phi_n)
    return {'n': n, 'e': e, 'd': d, 'p': p, 'q': q}

set_random_seed(2024)

# Root CA key pair (trusted, pre-installed in browsers)
root_ca = generate_rsa_keypair(bits=32)
print('=== Root CA ===')
print(f'Public key:  (n={root_ca["n"]}, e={root_ca["e"]})')
print(f'Private key: d={root_ca["d"]}  (kept in a vault)')
print()

# Intermediate CA key pair
intermediate_ca = generate_rsa_keypair(bits=32)
print('=== Intermediate CA ===')
print(f'Public key:  (n={intermediate_ca["n"]}, e={intermediate_ca["e"]})')
print()

# Web server key pair
server = generate_rsa_keypair(bits=32)
print('=== Web Server (example.com) ===')
print(f'Public key:  (n={server["n"]}, e={server["e"]})')

RSA Signatures: Signing and Verification

An RSA signature works as follows:

Signing (by the CA, using its private key $d$):

1. Compute a hash of the data: $h = \text{Hash}(\text{data})$

2. Compute the signature: $s = h^d \bmod n$

Verification (by the browser, using the CA's public key $e$):

1. Compute the hash of the data: $h' = \text{Hash}(\text{data})$

2. Recover the hash from the signature: $h'' = s^e \bmod n$

3. Check: $h' = h''$?

This works because $s^e = (h^d)^e = h^{de} = h^{1 + k\varphi(n)} = h$ by Euler's theorem (Notebook 04c).

# === RSA signature functions ===

def hash_data(data_str, modulus):
    """Hash a string and reduce modulo n (toy version)."""
    h = hashlib.sha256(data_str.encode()).hexdigest()
    return Integer(int(h, 16)) % modulus

def rsa_sign(message_hash, d, n):
    """Sign a hash: s = h^d mod n."""
    return power_mod(message_hash, d, n)

def rsa_verify(message_hash, signature, e, n):
    """Verify a signature: check s^e mod n == h."""
    recovered_hash = power_mod(signature, e, n)
    return recovered_hash == message_hash

# Quick demonstration
test_data = 'Hello, TLS!'
test_hash = hash_data(test_data, root_ca['n'])
test_sig = rsa_sign(test_hash, root_ca['d'], root_ca['n'])
test_valid = rsa_verify(test_hash, test_sig, root_ca['e'], root_ca['n'])

print(f'Data:       "{test_data}"')
print(f'Hash:       {test_hash}')
print(f'Signature:  s = hash^d mod n = {test_sig}')
print(f'Verify:     s^e mod n == hash? {test_valid}')
print()
print('The signature proves the Root CA created this message.')
print('Only someone with d (the private key) could produce s.')

Step-by-Step: Building the Certificate Chain

Let's simulate the full certificate chain:

1. Root CA signs the Intermediate CA's certificate

2. Intermediate CA signs the server's certificate

3. Browser verifies the entire chain

# === Build the certificate chain ===

# Certificate = subject info + public key, signed by the issuer

# 1. Root CA creates a self-signed certificate
root_cert_data = f'Subject: Root CA | PublicKey: n={root_ca["n"]},e={root_ca["e"]}'
root_cert_hash = hash_data(root_cert_data, root_ca['n'])
root_cert_sig = rsa_sign(root_cert_hash, root_ca['d'], root_ca['n'])

print('=== Root CA Certificate (self-signed) ===')
print(f'Data: {root_cert_data}')
print(f'Signed by: Root CA (itself)')
print(f'Signature: {root_cert_sig}')
print()

# 2. Root CA signs the Intermediate CA's certificate
inter_cert_data = f'Subject: Intermediate CA | PublicKey: n={intermediate_ca["n"]},e={intermediate_ca["e"]}'
inter_cert_hash = hash_data(inter_cert_data, root_ca['n'])
inter_cert_sig = rsa_sign(inter_cert_hash, root_ca['d'], root_ca['n'])

print('=== Intermediate CA Certificate ===')
print(f'Data: {inter_cert_data}')
print(f'Signed by: Root CA')
print(f'Signature: {inter_cert_sig}')
print()

# 3. Intermediate CA signs the server's certificate
server_cert_data = f'Subject: example.com | PublicKey: n={server["n"]},e={server["e"]}'
server_cert_hash = hash_data(server_cert_data, intermediate_ca['n'])
server_cert_sig = rsa_sign(server_cert_hash, intermediate_ca['d'], intermediate_ca['n'])

print('=== Server Certificate ===')
print(f'Data: {server_cert_data}')
print(f'Signed by: Intermediate CA')
print(f'Signature: {server_cert_sig}')

# === Browser verification: walk the chain ===

print('=== Browser Verification ===')
print()

# Step 1: Verify intermediate cert using Root CA's public key
inter_hash_check = hash_data(inter_cert_data, root_ca['n'])
step1 = rsa_verify(inter_hash_check, inter_cert_sig, root_ca['e'], root_ca['n'])
print(f'Step 1: Verify Intermediate CA cert with Root CA public key')
print(f'  Recompute hash of cert data: {inter_hash_check}')
print(f'  Recover hash from signature: sig^e mod n = {power_mod(inter_cert_sig, root_ca["e"], root_ca["n"])}')
print(f'  Valid: {step1}')
print()

# Step 2: Verify server cert using Intermediate CA's public key
server_hash_check = hash_data(server_cert_data, intermediate_ca['n'])
step2 = rsa_verify(server_hash_check, server_cert_sig, intermediate_ca['e'], intermediate_ca['n'])
print(f'Step 2: Verify Server cert with Intermediate CA public key')
print(f'  Recompute hash of cert data: {server_hash_check}')
print(f'  Recover hash from signature: sig^e mod n = {power_mod(server_cert_sig, intermediate_ca["e"], intermediate_ca["n"])}')
print(f'  Valid: {step2}')
print()

# Step 3: Trust decision
print(f'Step 3: Is Root CA trusted? Yes (pre-installed in browser)')
print()
if step1 and step2:
    print('RESULT: Certificate chain is VALID')
    print('The browser trusts that example.com owns the server\'s public key.')
else:
    print('RESULT: Certificate chain is INVALID')
    print('The browser would show a security warning.')

PKCS#1 v1.5 Signature Format

In practice, RSA signatures don't just sign the raw hash. The PKCS#1 v1.5 standard specifies a padding format:

0x00 0x01 [0xFF padding] 0x00 [DigestInfo] [Hash]

where DigestInfo is an ASN.1 structure that identifies the hash algorithm (SHA-256, etc.).

The padded message is then signed with RSA: $s = \text{padded}^d \bmod n$.

This padding serves two purposes:

1. Unambiguity: the verifier knows which hash algorithm was used

2. Security: prevents certain forgery attacks on raw RSA signatures

# === Toy PKCS#1 v1.5 signature ===

def pkcs1_v15_pad(hash_value, key_size_bytes):
    """Simplified PKCS#1 v1.5 signature padding."""
    # DigestInfo for SHA-256 (simplified: just a tag byte)
    digest_info_tag = 0x30  # ASN.1 tag (simplified)
    hash_bytes = int(hash_value).to_bytes(8, 'big')  # Truncated hash for toy demo
    
    # Padding: 0x00 0x01 [0xFF...] 0x00 [tag] [hash]
    content = bytes([digest_info_tag]) + hash_bytes
    pad_len = key_size_bytes - len(content) - 3  # 3 = 0x00 + 0x01 + 0x00
    padded = bytes([0x00, 0x01]) + bytes([0xFF] * pad_len) + bytes([0x00]) + content
    
    return Integer(int.from_bytes(padded, 'big'))

# Demonstrate the padding
test_hash = hash_data('example.com certificate data', root_ca['n'])
key_bytes = (root_ca['n'].nbits() + 7) // 8
padded = pkcs1_v15_pad(test_hash, key_bytes)

print(f'Hash value:     {test_hash}')
print(f'Key size:       {key_bytes} bytes ({root_ca["n"].nbits()} bits)')
print(f'Padded message: {hex(int(padded))}')
print()
print('Structure: 00 01 [FF padding] 00 [DigestInfo tag] [hash bytes]')
print()

# Sign the padded message
padded_mod = padded % root_ca['n']  # Ensure it fits
sig = power_mod(padded_mod, root_ca['d'], root_ca['n'])
recovered = power_mod(sig, root_ca['e'], root_ca['n'])
print(f'Signed (padded):  s = padded^d mod n = {sig}')
print(f'Verified: s^e mod n = {recovered}')
print(f'Match: {recovered == padded_mod}')

Concept Map: Module 04 in TLS

Module 04 Concept	TLS Application
Prime generation (04e)	CA generates RSA key pair for signing
Extended Euclidean algorithm (04b)	Computes $d = e^{-1} \bmod \varphi(n)$ during key generation
Modular exponentiation (04f)	Signing ($h^d \bmod n$) and verification ($s^e \bmod n$)
Euler's theorem (04c)	Guarantees $(h^d)^e \equiv h \pmod{n}$
CRT (04d)	RSA-CRT optimization for fast signing on the server
GCD / coprimality (04a)	Choosing $e$ coprime to $\varphi(n)$

Every browser tab running HTTPS executes the number theory from Module 04.

# === What happens if the chain is broken? ===

# Attacker tries to forge a certificate for evil.com
evil_cert_data = f'Subject: evil.com | PublicKey: n={server["n"]},e={server["e"]}'

# The attacker doesn't have the Intermediate CA's private key,
# so they try to forge a signature
evil_hash = hash_data(evil_cert_data, intermediate_ca['n'])

# They can't compute hash^d mod n without d!
# Best they can do: pick a random "signature"
fake_sig = ZZ.random_element(intermediate_ca['n'])

# Verification fails
is_valid = rsa_verify(evil_hash, fake_sig, intermediate_ca['e'], intermediate_ca['n'])

print('=== Attempted Certificate Forgery ===')
print(f'Attacker wants to sign a cert for evil.com')
print(f'Needs: hash^d mod n (requires Intermediate CA private key)')
print(f'Has:   only the public key (n, e)')
print()
print(f'Fake signature: {fake_sig}')
print(f'Verification:   {is_valid}')
print()
print('Without the private key d, forging a signature requires')
print('computing e-th roots modulo n, which is equivalent to factoring n.')
print('This is the RSA problem --- the foundation of TLS security.')

Summary

Concept	Key idea
Certificate chain	TLS uses a chain of trust: Root CA signs Intermediate CA, which signs the server certificate. Your browser walks the chain to verify the server's identity
RSA signatures	Signing computes $s = h^d \bmod n$ (private key). Verification checks $s^e \bmod n = h$ (public key). Euler's theorem guarantees correctness
Certificate forgery	Without the private key $d$, forging a signature requires computing $e$-th roots modulo $n$, which is equivalent to factoring $n$
PKCS#1 v1.5 padding	Signatures use a standardized padding format that identifies the hash algorithm and prevents certain forgery attacks
Module 04 in every browser tab	Prime generation, extended GCD, modular exponentiation, Euler's theorem, and CRT all run behind the scenes whenever you visit an HTTPS site

The number theory from Module 04 runs billions of times per day across the internet.

---

Back to Module 04: Number Theory and RSA