Implementing RSA, AES-GCM, and a TLS 1.3 Handshake from Scratch in Python
A deep-dive into the full cryptographic stack powering every HTTPS connection — RSA-OAEP, AES-GCM, ECDHE key exchange, and a working TLS 1.3 handshake simulation, all built in pure Python from first principles.
Every time your browser connects to https://, a negotiation happens in under a hundred milliseconds that involves three distinct cryptographic systems working in sequence. An asymmetric key exchange establishes a shared secret without ever transmitting it. A key derivation function turns that secret into multiple independent encryption keys. A symmetric cipher uses those keys to encrypt every byte of actual data. And a message authentication code guarantees that none of it was tampered with in transit.
You've been on both ends of this hundreds of times today. You probably couldn't describe the internals of any of it.
We covered the foundations of RSA in the original article. That article was a clean introduction to the math — modular exponentiation, the Extended Euclidean Algorithm, key generation. But it used toy prime numbers, glossed over padding entirely, and stopped well short of anything production-relevant. Most importantly, it didn't answer the question developers actually need answered: how does RSA connect to the AES cipher that encrypts real data, and how does all of it fit into the TLS handshake protocol that runs your HTTPS connections?
This article answers that question end to end. We're building the full cryptographic stack:
- RSA done correctly — Miller-Rabin prime generation, OAEP padding, PSS signatures, timing attack awareness
- AES from first principles — S-box, SubBytes, ShiftRows, MixColumns, KeyExpansion, full AES-128
- AES-GCM — why authenticated encryption exists and how it works (GHASH + CTR mode)
- ECDHE key exchange — why TLS 1.3 killed static RSA key exchange and what replaced it
- A working TLS 1.3 handshake simulation — HKDF key derivation, encrypted handshake, the full protocol flow
Every section has working Python code you can run. None of it uses cryptographic libraries for the core implementations — the point is to understand what those libraries are doing, not to hide it behind an API call. At the end, we'll compare our from-scratch implementations to cryptography and PyCryptodome to verify correctness.
One disclaimer before we start: do not use this code in production. We're implementing these systems to understand them. Production cryptography requires constant-time implementations to prevent timing attacks, careful memory handling, hardened random number generation, and years of peer review. This is an education tool. The cryptography library exists for a reason.
With that said — let's build it.
Part 1: RSA Done Right
What the Original Article Got Wrong
Go back and look at the original RSA article. It demonstrates the core math correctly. But there are real problems with the implementation that would make it broken in practice:
Problem 1: Tiny primes. The test uses p=31337 and q=31357, giving an n of about 982 million — 30 bits. A real RSA key is 2048 or 4096 bits. The security of RSA depends entirely on the difficulty of factoring n. Factoring a 30-bit number takes milliseconds. Factoring a 2048-bit number is computationally infeasible with current hardware and algorithms.
Problem 2: No padding. Textbook RSA — c = m^e mod n — is not secure. It's deterministic: the same message always produces the same ciphertext, which leaks information. It's also vulnerable to chosen-plaintext attacks, small-message attacks, and several other issues. Real RSA uses OAEP (Optimal Asymmetric Encryption Padding) for encryption and PSS (Probabilistic Signature Scheme) for signing.
Problem 3: e=35537. The standard public exponent is 65537 (which is 2^16 + 1). This is chosen because it's prime, it's large enough to prevent certain attacks on small exponents, and its binary representation 10000000000000001 means modular exponentiation requires only 17 multiplications instead of one per bit of a random exponent. The article uses 35537, which is not the standard and lacks these properties.
Problem 4: No prime generation. The article requires you to supply primes. Real RSA requires generating cryptographically random large primes. That's non-trivial.
Let's fix all of this.
Miller-Rabin Primality Testing
Generating a large random prime works by generating a large random odd number and testing whether it's prime. The test needs to be fast — trial division up to the square root of a 2048-bit number would take longer than the universe has existed.
The Miller-Rabin test is a probabilistic primality test. It can definitively prove a number is composite, but it can only say a number is "probably prime" with a tunable probability of error. Running it with enough witnesses (values of a to test against) makes the error probability negligible for practical purposes.
The math: a number n is prime if and only if for all a coprime to n, a^(n-1) ≡ 1 (mod n) (Fermat's little theorem). Miller-Rabin strengthens this by writing n-1 = 2^r * d where d is odd, then checking whether:
a^d ≡ 1 (mod n), ORa^(2^j * d) ≡ -1 (mod n)for some0 ≤ j < r
If neither holds for some witness a, n is composite. If both hold for many witnesses, n is almost certainly prime.
import secrets
import math
def miller_rabin_test(n: int, a: int) -> bool:
"""
Single round of Miller-Rabin for witness a.
Returns True if n passes (probably prime), False if n is definitely composite.
"""
if n == a:
return True
if n % 2 == 0:
return False
# Write n-1 as 2^r * d where d is odd
r, d = 0, n - 1
while d % 2 == 0:
r += 1
d //= 2
# Compute a^d mod n
x = pow(a, d, n)
if x == 1 or x == n - 1:
return True
# Square x up to r-1 times
for _ in range(r - 1):
x = pow(x, 2, n)
if x == n - 1:
return True
return False # definitely composite
def is_prime(n: int, rounds: int = 20) -> bool:
"""
Probabilistic primality test using Miller-Rabin.
20 rounds gives false-positive probability < 4^-20 ≈ 10^-12.
For cryptographic use, deterministic witnesses exist for n < 3.3 * 10^24.
"""
if n < 2:
return False
if n == 2 or n == 3:
return True
if n % 2 == 0 or n % 3 == 0:
return False
# Quick trial division by small primes — catches most composites cheaply
small_primes = [5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
for p in small_primes:
if n == p:
return True
if n % p == 0:
return False
# Miller-Rabin with random witnesses
for _ in range(rounds):
a = secrets.randbelow(n - 3) + 2 # random a in [2, n-2]
if not miller_rabin_test(n, a):
return False
return True
def generate_prime(bits: int) -> int:
"""
Generate a random prime of the specified bit length.
Uses secrets module for cryptographically secure randomness.
"""
while True:
# Generate a random odd number with the top two bits set
# (ensuring it's exactly `bits` bits long)
candidate = secrets.randbits(bits)
candidate |= (1 << (bits - 1)) # set MSB
candidate |= (1 << (bits - 2)) # set second MSB (avoids small factor attacks)
candidate |= 1 # ensure odd
if is_prime(candidate):
return candidate
The secrets module (Python 3.6+) uses the OS's cryptographic random number generator — /dev/urandom on Linux, CryptGenRandom on Windows. Do not use random for cryptographic applications. random is a pseudorandom number generator seeded by a small state. An attacker who observes enough outputs can reconstruct the seed and predict future outputs. secrets draws from the OS entropy pool which is designed to resist this.
Notice the candidate |= (1 << (bits - 2)) line. Setting the second-most-significant bit ensures that when we multiply two bits-length primes, the product is exactly 2 * bits long. This matters for RSA because we want predictable key sizes.
Key Generation with Real Primes
def extended_gcd(a: int, b: int) -> tuple[int, int, int]:
"""
Extended Euclidean Algorithm.
Returns (gcd, x, y) such that a*x + b*y = gcd(a, b).
"""
if a == 0:
return b, 0, 1
gcd, x1, y1 = extended_gcd(b % a, a)
return gcd, y1 - (b // a) * x1, x1
def modinv(a: int, m: int) -> int:
"""
Modular inverse of a mod m using Extended Euclidean Algorithm.
Raises ValueError if the inverse doesn't exist (gcd != 1).
"""
gcd, x, _ = extended_gcd(a % m, m)
if gcd != 1:
raise ValueError(f"Modular inverse doesn't exist: gcd({a}, {m}) = {gcd}")
return x % m
def rsa_keygen(bits: int = 2048) -> dict:
"""
Generate an RSA keypair of the specified total bit length.
Each prime is bits/2 bits long, giving an n of approximately `bits` bits.
Returns a dict with 'public' and 'private' keys.
"""
half_bits = bits // 2
# Generate two distinct primes
while True:
p = generate_prime(half_bits)
q = generate_prime(half_bits)
if p != q:
break
n = p * q
# Carmichael's totient (preferred over Euler's totient for modern RSA)
# λ(n) = lcm(p-1, q-1) instead of (p-1)(q-1)
# Smaller private exponent, equivalent security
lambda_n = (p - 1) * (q - 1) // math.gcd(p - 1, q - 1)
# Standard public exponent
e = 65537
assert math.gcd(e, lambda_n) == 1, "e and λ(n) must be coprime"
# Private exponent
d = modinv(e, lambda_n)
# CRT components for faster decryption (Garner's formula)
# These allow splitting the modular exponentiation into two smaller ones
dp = d % (p - 1)
dq = d % (q - 1)
qinv = modinv(q, p)
return {
'public': (e, n),
'private': (d, n),
'crt': (p, q, dp, dq, qinv), # optional: speeds up decryption by ~4x
'key_size': bits
}
def rsa_decrypt_crt(c: int, crt: tuple) -> int:
"""
RSA decryption using Chinese Remainder Theorem.
Roughly 4x faster than naive m = pow(c, d, n).
"""
p, q, dp, dq, qinv = crt
m1 = pow(c, dp, p)
m2 = pow(c, dq, q)
# Garner's formula
h = (qinv * (m1 - m2)) % p
return m2 + h * q
Two things worth calling out here. First, we use Carmichael's totient λ(n) = lcm(p-1, q-1) instead of Euler's totient φ(n) = (p-1)(q-1). Both work mathematically for RSA, but Carmichael's totient produces a smaller private exponent d, which means faster decryption. The security properties are equivalent. The PKCS#1 v2.2 standard recommends Carmichael's.
Second, the CRT decomposition. pow(c, d, n) where d and n are both 2048 bits is expensive. CRT splits this into two exponentiations with 1024-bit numbers each, which is roughly 4x faster than the naive approach. This is how every real RSA implementation works. OpenSSL uses it. The cryptography library uses it. Now you understand why.
OAEP Padding: The Difference Between Textbook and Real RSA
Textbook RSA is deterministic and algebraically malleable. If an attacker can ask you to decrypt arbitrary ciphertexts, they can recover plaintexts in clever ways without ever factoring n. OAEP padding randomizes the encryption and adds structure that makes these attacks infeasible.
OAEP uses a Mask Generation Function (MGF1) built on top of a hash function. The padding scheme works like this:
- Start with the message
M - Concatenate a label hash, padding zeros, a
0x01separator, and the message to form a data blockDB - Generate a random seed of hash length
maskedDB = DB XOR MGF1(seed)maskedSeed = seed XOR MGF1(maskedDB)- The padded message is
0x00 || maskedSeed || maskedDB - Encrypt this padded message with textbook RSA
Decryption reverses the XOR steps to recover the original message. The randomness in the seed means the same plaintext encrypts to different ciphertexts every time — which is a fundamental security requirement called semantic security (or IND-CPA security in formal terms).
import hashlib
import os
def mgf1(seed: bytes, length: int, hash_func=hashlib.sha256) -> bytes:
"""
Mask Generation Function 1 (MGF1) as defined in RFC 8017.
Produces a pseudorandom byte string of the specified length.
"""
h_len = hash_func().digest_size
if length > (2**32) * h_len:
raise ValueError("mask too long")
T = b""
counter = 0
while len(T) < length:
C = counter.to_bytes(4, byteorder='big')
T += hash_func(seed + C).digest()
counter += 1
return T[:length]
def oaep_encode(message: bytes, n_bytes: int,
label: bytes = b"",
hash_func=hashlib.sha256) -> bytes:
"""
OAEP encoding as per RFC 8017 Section 7.1.1.
n_bytes: byte length of the RSA modulus
"""
h_len = hash_func().digest_size
m_len = len(message)
# Check message length
max_m_len = n_bytes - 2 * h_len - 2
if m_len > max_m_len:
raise ValueError(f"message too long: {m_len} > {max_m_len}")
# Hash the label (empty label is fine, its hash is still computed)
l_hash = hash_func(label).digest()
# Data block: lHash || PS || 0x01 || M
# PS is zero-padding to make DB exactly (n_bytes - h_len - 1) bytes
ps_len = n_bytes - m_len - 2 * h_len - 2
db = l_hash + (b'\x00' * ps_len) + b'\x01' + message
# Random seed of length h_len
seed = secrets.token_bytes(h_len)
# Mask the data block and seed
db_mask = mgf1(seed, len(db), hash_func)
masked_db = bytes(a ^ b for a, b in zip(db, db_mask))
seed_mask = mgf1(masked_db, h_len, hash_func)
masked_seed = bytes(a ^ b for a, b in zip(seed, seed_mask))
# Encoded message: 0x00 || maskedSeed || maskedDB
return b'\x00' + masked_seed + masked_db
def oaep_decode(encoded: bytes, n_bytes: int,
label: bytes = b"",
hash_func=hashlib.sha256) -> bytes:
"""
OAEP decoding as per RFC 8017 Section 7.1.2.
Raises ValueError on decoding failure (do not use specific errors — timing attacks).
"""
h_len = hash_func().digest_size
if len(encoded) != n_bytes or n_bytes < 2 * h_len + 2:
raise ValueError("decryption error")
l_hash = hash_func(label).digest()
# Split: Y || maskedSeed || maskedDB
y = encoded[0]
masked_seed = encoded[1:1 + h_len]
masked_db = encoded[1 + h_len:]
# Recover seed and DB
seed_mask = mgf1(masked_db, h_len, hash_func)
seed = bytes(a ^ b for a, b in zip(masked_seed, seed_mask))
db_mask = mgf1(seed, len(masked_db), hash_func)
db = bytes(a ^ b for a, b in zip(masked_db, db_mask))
# Verify: lHash || PS || 0x01 || M
recovered_l_hash = db[:h_len]
rest = db[h_len:]
# Find the 0x01 separator — scan in constant time to prevent timing leaks
# (in production you'd use a constant-time scan)
sep_index = None
for i, byte in enumerate(rest):
if byte == 0x01 and sep_index is None:
sep_index = i
elif byte != 0x00 and sep_index is None:
# Non-zero byte before separator: decoding error
raise ValueError("decryption error")
if y != 0 or recovered_l_hash != l_hash or sep_index is None:
raise ValueError("decryption error")
return rest[sep_index + 1:]
def rsa_encrypt_oaep(message: bytes, public_key: tuple) -> bytes:
"""
RSA-OAEP encryption.
"""
e, n = public_key
n_bytes = (n.bit_length() + 7) // 8
padded = oaep_encode(message, n_bytes)
padded_int = int.from_bytes(padded, byteorder='big')
ciphertext_int = pow(padded_int, e, n)
return ciphertext_int.to_bytes(n_bytes, byteorder='big')
def rsa_decrypt_oaep(ciphertext: bytes, private_key: tuple,
crt_params: tuple = None) -> bytes:
"""
RSA-OAEP decryption.
"""
d, n = private_key
n_bytes = (n.bit_length() + 7) // 8
ciphertext_int = int.from_bytes(ciphertext, byteorder='big')
if crt_params:
padded_int = rsa_decrypt_crt(ciphertext_int, crt_params)
else:
padded_int = pow(ciphertext_int, d, n)
padded = padded_int.to_bytes(n_bytes, byteorder='big')
return oaep_decode(padded, n_bytes)
The comment about constant-time scanning in oaep_decode is not academic. The Bleichenbacher attack and its variants exploit timing differences in padding verification. If your code returns an error faster when it finds a bad byte early in the padding versus late, an attacker can use those timing differences to mount a chosen-ciphertext attack and decrypt messages. This is a real attack that has been demonstrated against TLS implementations. Our OAEP decode has a subtle timing leak in the separator scan — in production code, you'd use a branch-free scan that always processes the entire buffer.
RSA-PSS Signatures
TLS 1.3 uses RSA for one thing: signing the server's certificate to prove ownership of the private key. The signature scheme is RSASSA-PSS (Probabilistic Signature Scheme), which is what RFC 8446 specifies.
def pss_encode(message: bytes, em_bits: int,
hash_func=hashlib.sha256, salt_length: int = 32) -> bytes:
"""
PSS encoding as per RFC 8017 Section 9.1.1.
em_bits: bit length of the encoded message (usually modBits - 1)
"""
h_len = hash_func().digest_size
em_len = (em_bits + 7) // 8
if em_len < h_len + salt_length + 2:
raise ValueError("encoding error")
# Hash the message
m_hash = hash_func(message).digest()
# Generate random salt
salt = secrets.token_bytes(salt_length)
# Hash M' = 0x00*8 || mHash || salt
m_prime = b'\x00' * 8 + m_hash + salt
h = hash_func(m_prime).digest()
# DB = PS || 0x01 || salt
ps_len = em_len - salt_length - h_len - 2
db = (b'\x00' * ps_len) + b'\x01' + salt
# Mask DB
db_mask = mgf1(h, len(db), hash_func)
masked_db = bytes(a ^ b for a, b in zip(db, db_mask))
# Set leftmost bits to zero (bit masking for em_bits)
leftmost_bits = 8 * em_len - em_bits
masked_db = bytes([masked_db[0] & (0xFF >> leftmost_bits)]) + masked_db[1:]
return masked_db + h + b'\xbc'
def rsa_sign_pss(message: bytes, private_key: tuple,
crt_params: tuple = None,
hash_func=hashlib.sha256) -> bytes:
"""
RSA-PSS signing.
"""
d, n = private_key
mod_bits = n.bit_length()
em_bits = mod_bits - 1
em_len = (em_bits + 7) // 8
encoded = pss_encode(message, em_bits, hash_func)
encoded_int = int.from_bytes(encoded, byteorder='big')
if crt_params:
sig_int = rsa_decrypt_crt(encoded_int, crt_params)
else:
sig_int = pow(encoded_int, d, n)
n_bytes = (n.bit_length() + 7) // 8
return sig_int.to_bytes(n_bytes, byteorder='big')
def rsa_verify_pss(message: bytes, signature: bytes, public_key: tuple,
hash_func=hashlib.sha256, salt_length: int = 32) -> bool:
"""
RSA-PSS verification. Returns True if valid, False otherwise.
Never raise exceptions for invalid signatures — return False.
"""
e, n = public_key
mod_bits = n.bit_length()
em_bits = mod_bits - 1
n_bytes = (n.bit_length() + 7) // 8
h_len = hash_func().digest_size
try:
sig_int = int.from_bytes(signature, byteorder='big')
if sig_int >= n:
return False
em_int = pow(sig_int, e, n)
em_len = (em_bits + 7) // 8
em = em_int.to_bytes(em_len, byteorder='big')
# Verify PSS structure
if em[-1] != 0xbc:
return False
h = em[em_len - h_len - 1:em_len - 1]
masked_db = em[:em_len - h_len - 1]
# Unmask DB
db_mask = mgf1(h, len(masked_db), hash_func)
db = bytes(a ^ b for a, b in zip(masked_db, db_mask))
# Clear leftmost bits
leftmost_bits = 8 * em_len - em_bits
db = bytes([db[0] & (0xFF >> leftmost_bits)]) + db[1:]
# Verify DB structure
ps_len = em_len - salt_length - h_len - 2
if db[:ps_len] != b'\x00' * ps_len or db[ps_len] != 0x01:
return False
salt = db[ps_len + 1:]
m_hash = hash_func(message).digest()
m_prime = b'\x00' * 8 + m_hash + salt
h_prime = hash_func(m_prime).digest()
return h == h_prime
except Exception:
return False
Part 2: AES — The Cipher That Actually Encrypts Your Data
Here's something that surprises a lot of developers: RSA doesn't encrypt the data in your HTTPS connection. It can't. RSA encryption is roughly 1000x slower than symmetric encryption for bulk data, and its output size scales with the key size — you can only encrypt messages smaller than your key. A 2048-bit RSA key can encrypt at most about 214 bytes with OAEP padding.
The actual data — every HTTP request and response in your HTTPS session — is encrypted with AES (Advanced Encryption Standard). RSA handles the key exchange. AES does the work.
What AES Is
AES is a symmetric block cipher. Symmetric means the same key encrypts and decrypts. Block cipher means it operates on fixed-size blocks of plaintext — AES always uses 128-bit (16-byte) blocks regardless of key size.
AES comes in three key sizes: 128, 192, or 256 bits. The key size determines the number of rounds: 10, 12, or 14 respectively. We're implementing AES-128 (10 rounds). AES-256 is identical except for the key schedule and round count.
AES was selected by NIST in 2001 from a competition. The winning algorithm, submitted by Joan Daemen and Vincent Rijmen, was originally called Rijndael. It's a substitution-permutation network: each round applies a series of invertible transformations to a 4×4 matrix of bytes called the state.
The State Matrix
Take a 16-byte block of data and arrange it column-by-column into a 4×4 grid:
Input bytes: b0 b1 b2 b3 b4 b5 b6 b7 b8 b9 b10 b11 b12 b13 b14 b15
State matrix:
col 0 col 1 col 2 col 3
row 0: b0 b4 b8 b12
row 1: b1 b5 b9 b13
row 2: b2 b6 b10 b14
row 3: b3 b7 b11 b15
Note: AES fills columns first, not rows. This is column-major order, which trips people up the first time. The standard is explicit about it.
The S-Box: Non-Linearity Through Galois Field Arithmetic
The most interesting component of AES is the S-Box (Substitution Box). Each round applies SubBytes, which replaces every byte in the state with a corresponding byte from a fixed 256-entry lookup table.
The S-Box is constructed mathematically to have optimal non-linearity properties — it resists linear cryptanalysis and differential cryptanalysis by design. The construction uses Galois Field arithmetic over GF(2^8).
Without going completely down the abstract algebra rabbit hole: GF(2^8) is a field where each element is an 8-bit polynomial. Addition is XOR. Multiplication is polynomial multiplication modulo the irreducible polynomial x^8 + x^4 + x^3 + x + 1 (0x11b in hex). For each byte value b, the S-Box value is the affine transformation of the multiplicative inverse of b in GF(2^8).
In practice, you just use the lookup table. But understanding where it comes from matters:
# AES S-Box (SubBytes lookup table)
# Generated from GF(2^8) multiplicative inverses + affine transformation
# Source: FIPS 197 Appendix A
SBOX = [
0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5, 0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab, 0x76,
0xca, 0x82, 0xc9, 0x7d, 0xfa, 0x59, 0x47, 0xf0, 0xad, 0xd4, 0xa2, 0xaf, 0x9c, 0xa4, 0x72, 0xc0,
0xb7, 0xfd, 0x93, 0x26, 0x36, 0x3f, 0xf7, 0xcc, 0x34, 0xa5, 0xe5, 0xf1, 0x71, 0xd8, 0x31, 0x15,
0x04, 0xc7, 0x23, 0xc3, 0x18, 0x96, 0x05, 0x9a, 0x07, 0x12, 0x80, 0xe2, 0xeb, 0x27, 0xb2, 0x75,
0x09, 0x83, 0x2c, 0x1a, 0x1b, 0x6e, 0x5a, 0xa0, 0x52, 0x3b, 0xd6, 0xb3, 0x29, 0xe3, 0x2f, 0x84,
0x53, 0xd1, 0x00, 0xed, 0x20, 0xfc, 0xb1, 0x5b, 0x6a, 0xcb, 0xbe, 0x39, 0x4a, 0x4c, 0x58, 0xcf,
0xd0, 0xef, 0xaa, 0xfb, 0x43, 0x4d, 0x33, 0x85, 0x45, 0xf9, 0x02, 0x7f, 0x50, 0x3c, 0x9f, 0xa8,
0x51, 0xa3, 0x40, 0x8f, 0x92, 0x9d, 0x38, 0xf5, 0xbc, 0xb6, 0xda, 0x21, 0x10, 0xff, 0xf3, 0xd2,
0xcd, 0x0c, 0x13, 0xec, 0x5f, 0x97, 0x44, 0x17, 0xc4, 0xa7, 0x7e, 0x3d, 0x64, 0x5d, 0x19, 0x73,
0x60, 0x81, 0x4f, 0xdc, 0x22, 0x2a, 0x90, 0x88, 0x46, 0xee, 0xb8, 0x14, 0xde, 0x5e, 0x0b, 0xdb,
0xe0, 0x32, 0x3a, 0x0a, 0x49, 0x06, 0x24, 0x5c, 0xc2, 0xd3, 0xac, 0x62, 0x91, 0x95, 0xe4, 0x79,
0xe7, 0xc8, 0x37, 0x6d, 0x8d, 0xd5, 0x4e, 0xa9, 0x6c, 0x56, 0xf4, 0xea, 0x65, 0x7a, 0xae, 0x08,
0xba, 0x78, 0x25, 0x2e, 0x1c, 0xa6, 0xb4, 0xc6, 0xe8, 0xdd, 0x74, 0x1f, 0x4b, 0xbd, 0x8b, 0x8a,
0x70, 0x3e, 0xb5, 0x66, 0x48, 0x03, 0xf6, 0x0e, 0x61, 0x35, 0x57, 0xb9, 0x86, 0xc1, 0x1d, 0x9e,
0xe1, 0xf8, 0x98, 0x11, 0x69, 0xd9, 0x8e, 0x94, 0x9b, 0x1e, 0x87, 0xe9, 0xce, 0x55, 0x28, 0xdf,
0x8c, 0xa1, 0x89, 0x0d, 0xbf, 0xe6, 0x42, 0x68, 0x41, 0x99, 0x2d, 0x0f, 0xb0, 0x54, 0xbb, 0x16,
]
# Inverse S-Box for decryption
INV_SBOX = [0] * 256
for i, v in enumerate(SBOX):
INV_SBOX[v] = i
Galois Field Arithmetic: Why GF(2^8) Exists in a Block Cipher
MixColumns uses arithmetic in GF(2^8) — the Galois Field with 256 elements. If you've never encountered finite field arithmetic before, this is where most AES explanations lose people. Let's fix that.
A field is a set with two operations (addition and multiplication) where every nonzero element has a multiplicative inverse. The integers are not a field — 2 has no multiplicative inverse in the integers (there's no integer x where 2*x = 1). The real numbers are a field. The integers modulo a prime p are a field (what we used in RSA).
GF(2^8) is a finite field with exactly 256 elements — one for each possible byte value. This is exactly what we need: a field where we can do arithmetic with bytes.
The elements of GF(2^8) are polynomials over GF(2) of degree less than 8. A byte 0xAB = 10101011 represents the polynomial:
x^7 + x^5 + x^3 + x + 1
Where each bit is a coefficient in GF(2) (so coefficients are either 0 or 1).
Addition in GF(2^8) is polynomial addition with coefficients mod 2. Since 1+1=0 in GF(2), addition is just XOR:
0xAB XOR 0xCD = 0x66
No carries, no borrows. This is why you can't have timing attacks based on carry propagation in GF(2^8) arithmetic — there are no carries.
Multiplication in GF(2^8) is polynomial multiplication, then reduction modulo the AES irreducible polynomial x^8 + x^4 + x^3 + x + 1 (0x11b). The irreducible polynomial plays the same role that a prime does in modular arithmetic — it ensures every nonzero element has an inverse.
The gmul function we wrote earlier implements this directly. The xtime function multiplies by x (i.e., shifts left one bit and reduces if the high bit was set). Any multiplication can be decomposed into a sequence of xtime operations and XORs.
Why does AES use GF(2^8) specifically? Because the MixColumns operation needs to be invertible (for decryption) and needs to provide diffusion across bytes in a column. The MixColumns matrix is specifically chosen so that any change to any input byte affects all four output bytes (the Maximum Distance Separable property) and so that the matrix is invertible over GF(2^8). You can't achieve this with ordinary integer arithmetic in a way that maps cleanly to byte operations — the Galois field structure is what makes it work.
The Four Round Transformations
SubBytes: Replace each byte with its S-Box lookup. Non-linear — the only non-linear step in AES. Provides confusion (obscures relationship between key and ciphertext).
ShiftRows: Cyclically shift row i of the state left by i positions. Row 0 stays unchanged, row 1 shifts 1 byte left, row 2 shifts 2 bytes left, row 3 shifts 3 bytes left. Provides diffusion within rows.
MixColumns: Multiply each column by a fixed 4×4 matrix over GF(2^8). This is where the Galois field arithmetic becomes unavoidable. The multiplication ensures that each output byte depends on all four input bytes of the column. Provides diffusion across columns.
AddRoundKey: XOR the state with the current round key. This is how the key material actually enters the cipher.
def xtime(a: int) -> int:
"""
Multiply byte a by 2 in GF(2^8).
Left shift by 1, then XOR with 0x1b if the high bit was set
(reducing modulo the AES irreducible polynomial x^8 + x^4 + x^3 + x + 1 = 0x11b).
"""
if a & 0x80:
return ((a << 1) ^ 0x1b) & 0xFF
return (a << 1) & 0xFF
def gmul(a: int, b: int) -> int:
"""
Galois Field GF(2^8) multiplication.
Used in MixColumns. Handles multiplication by arbitrary values.
"""
result = 0
for _ in range(8):
if b & 1:
result ^= a
hi_bit = a & 0x80
a = (a << 1) & 0xFF
if hi_bit:
a ^= 0x1b
b >>= 1
return result
class AES128:
"""
AES-128 block cipher implementation.
Key must be exactly 16 bytes.
"""
# Round constants for key expansion
RCON = [
0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1b, 0x36
]
def __init__(self, key: bytes):
if len(key) != 16:
raise ValueError("AES-128 requires a 16-byte key")
self.round_keys = self._key_expansion(key)
def _key_expansion(self, key: bytes) -> list[list[int]]:
"""
Rijndael key schedule.
AES-128: 10 rounds, generates 11 round keys of 16 bytes each.
"""
# Initial key as list of 4-byte words
w = []
for i in range(4):
w.append(list(key[i*4:(i+1)*4]))
for i in range(4, 44): # 11 round keys * 4 words = 44 words
temp = w[i-1][:]
if i % 4 == 0:
# RotWord: rotate bytes left
temp = temp[1:] + temp[:1]
# SubWord: apply S-Box to each byte
temp = [SBOX[b] for b in temp]
# XOR with round constant
temp[0] ^= self.RCON[i // 4 - 1]
w.append([w[i-4][j] ^ temp[j] for j in range(4)])
# Group words into 16-byte round keys
round_keys = []
for round_num in range(11):
rk = []
for word_idx in range(4):
rk.extend(w[round_num * 4 + word_idx])
round_keys.append(rk)
return round_keys
def _add_round_key(self, state: list, round_num: int) -> list:
"""XOR state with the round key."""
rk = self.round_keys[round_num]
return [state[i] ^ rk[i] for i in range(16)]
def _sub_bytes(self, state: list) -> list:
"""Replace each byte with its S-Box substitution."""
return [SBOX[b] for b in state]
def _inv_sub_bytes(self, state: list) -> list:
return [INV_SBOX[b] for b in state]
def _shift_rows(self, state: list) -> list:
"""
Shift rows cyclically.
State is stored column-major: indices [row + col*4].
"""
# Convert to row-major for easier shifting
rows = [[state[row + col*4] for col in range(4)] for row in range(4)]
# Shift row i by i positions left
for i in range(4):
rows[i] = rows[i][i:] + rows[i][:i]
# Convert back to column-major
result = [0] * 16
for row in range(4):
for col in range(4):
result[row + col*4] = rows[row][col]
return result
def _inv_shift_rows(self, state: list) -> list:
"""Shift rows cyclically to the right."""
rows = [[state[row + col*4] for col in range(4)] for row in range(4)]
for i in range(4):
rows[i] = rows[i][-i:] + rows[i][:-i] if i > 0 else rows[i]
result = [0] * 16
for row in range(4):
for col in range(4):
result[row + col*4] = rows[row][col]
return result
def _mix_columns(self, state: list) -> list:
"""
MixColumns transformation.
Multiply each column by the fixed MixColumns matrix over GF(2^8).
Matrix:
2 3 1 1
1 2 3 1
1 1 2 3
3 1 1 2
"""
result = [0] * 16
for col in range(4):
# Extract column
s0 = state[0 + col*4]
s1 = state[1 + col*4]
s2 = state[2 + col*4]
s3 = state[3 + col*4]
# Matrix multiplication in GF(2^8)
# XOR is addition in GF(2^8)
result[0 + col*4] = gmul(2, s0) ^ gmul(3, s1) ^ s2 ^ s3
result[1 + col*4] = s0 ^ gmul(2, s1) ^ gmul(3, s2) ^ s3
result[2 + col*4] = s0 ^ s1 ^ gmul(2, s2) ^ gmul(3, s3)
result[3 + col*4] = gmul(3, s0) ^ s1 ^ s2 ^ gmul(2, s3)
return result
def _inv_mix_columns(self, state: list) -> list:
"""Inverse MixColumns for decryption."""
result = [0] * 16
for col in range(4):
s0 = state[0 + col*4]
s1 = state[1 + col*4]
s2 = state[2 + col*4]
s3 = state[3 + col*4]
# Inverse MixColumns matrix: 14, 11, 13, 9 coefficients
result[0 + col*4] = gmul(14, s0) ^ gmul(11, s1) ^ gmul(13, s2) ^ gmul(9, s3)
result[1 + col*4] = gmul(9, s0) ^ gmul(14, s1) ^ gmul(11, s2) ^ gmul(13, s3)
result[2 + col*4] = gmul(13, s0) ^ gmul(9, s1) ^ gmul(14, s2) ^ gmul(11, s3)
result[3 + col*4] = gmul(11, s0) ^ gmul(13, s1) ^ gmul(9, s2) ^ gmul(14, s3)
return result
def encrypt_block(self, plaintext: bytes) -> bytes:
"""
Encrypt a single 16-byte block.
AES-128: 10 rounds of SubBytes + ShiftRows + MixColumns + AddRoundKey.
Final round omits MixColumns.
"""
if len(plaintext) != 16:
raise ValueError("AES operates on 16-byte blocks")
state = list(plaintext)
# Initial round key addition
state = self._add_round_key(state, 0)
# Rounds 1-9: all four transformations
for round_num in range(1, 10):
state = self._sub_bytes(state)
state = self._shift_rows(state)
state = self._mix_columns(state)
state = self._add_round_key(state, round_num)
# Final round: no MixColumns
state = self._sub_bytes(state)
state = self._shift_rows(state)
state = self._add_round_key(state, 10)
return bytes(state)
def decrypt_block(self, ciphertext: bytes) -> bytes:
"""Decrypt a single 16-byte block."""
if len(ciphertext) != 16:
raise ValueError("AES operates on 16-byte blocks")
state = list(ciphertext)
# Reverse final round
state = self._add_round_key(state, 10)
state = self._inv_shift_rows(state)
state = self._inv_sub_bytes(state)
# Rounds 9-1: inverse transformations in reverse order
for round_num in range(9, 0, -1):
state = self._add_round_key(state, round_num)
state = self._inv_mix_columns(state)
state = self._inv_shift_rows(state)
state = self._inv_sub_bytes(state)
# Initial round key addition
state = self._add_round_key(state, 0)
return bytes(state)
The key expansion (Rijndael key schedule) deserves attention. It takes the 16-byte key and generates 11 round keys — one for each of the 10 rounds plus an initial one. The generation is recursive: each 4-byte word w[i] depends on w[i-1] and w[i-4]. Every 4th word gets an extra transformation: rotate, substitute through S-Box, XOR with a round constant. The round constants are powers of 2 in GF(2^8), ensuring each round's key is cryptographically independent.
AES-GCM: Authenticated Encryption
A raw block cipher only provides confidentiality — an attacker who intercepts your AES-encrypted traffic can't read it. But they can flip bits in the ciphertext, and those flipped bits will silently produce garbage when decrypted on the other end. Worse, with some modes of operation (CBC without authentication), bit flipping can be done in a controlled way to produce specific modifications to the plaintext.
Authenticated Encryption with Associated Data (AEAD) solves this. AES-GCM (Galois/Counter Mode) is the AEAD mode mandated by TLS 1.3. It provides both confidentiality and integrity: if any bit of the ciphertext is modified, decryption fails with an authentication error before you process a single byte of the potentially tampered data.
GCM combines two components:
- CTR (Counter) Mode: encrypts data by XORing plaintext with an encrypted counter sequence
- GHASH: computes an authentication tag over the ciphertext (and optional associated data) using polynomial multiplication in GF(2^128)
def ghash(h: bytes, data: bytes) -> bytes:
"""
GHASH function used in AES-GCM.
Computes an authentication tag over data using key H.
H = AES(key, 0^128) — the AES encryption of all-zero block.
This is polynomial multiplication in GF(2^128) modulo
the irreducible polynomial x^128 + x^7 + x^2 + x + 1.
"""
def gf_mult(x: int, y: int) -> int:
"""Carry-less multiplication in GF(2^128)."""
result = 0
# Reduction polynomial: x^128 + x^7 + x^2 + x + 1
R = 0xE1000000000000000000000000000000 # 0xE1 shifted left 120 bits
for i in range(128):
if y & (1 << (127 - i)):
result ^= x
if x & 1:
x = (x >> 1) ^ R
else:
x >>= 1
return result
def bytes_to_int(b: bytes) -> int:
return int.from_bytes(b, 'big')
def int_to_bytes(n: int, length: int = 16) -> bytes:
return n.to_bytes(length, 'big')
h_int = bytes_to_int(h)
# Pad data to multiple of 16 bytes
padded = data + b'\x00' * ((16 - len(data) % 16) % 16)
x = 0
for i in range(0, len(padded), 16):
block = bytes_to_int(padded[i:i+16])
x = gf_mult(x ^ block, h_int)
return int_to_bytes(x)
class AESGCM:
"""
AES-GCM authenticated encryption.
Provides confidentiality + integrity + authenticity.
Nonce MUST be unique for every (key, message) pair.
Nonce reuse is catastrophic: it leaks the authentication key H
and potentially reveals the keystream, enabling plaintext recovery.
"""
TAG_LENGTH = 16 # 128-bit authentication tag
NONCE_LENGTH = 12 # 96-bit nonce (recommended by NIST SP 800-38D)
def __init__(self, key: bytes):
if len(key) not in (16, 32):
raise ValueError("AES-GCM requires 16 or 32 byte key")
# For AES-256 key, we'd need AES256 class; using AES-128 here for clarity
if len(key) != 16:
raise ValueError("This implementation supports AES-128 only")
self._aes = AES128(key)
# H = AES_K(0^128) — authentication key derived from cipher key
self._H = self._aes.encrypt_block(b'\x00' * 16)
def _ctr_encrypt(self, data: bytes, initial_counter: bytes) -> bytes:
"""
CTR mode: XOR plaintext with sequence of encrypted counter blocks.
Counter starts at initial_counter + 1 for data (initial_counter itself
is used to generate the authentication tag mask).
"""
result = bytearray()
counter_int = int.from_bytes(initial_counter, 'big')
for i in range(0, len(data), 16):
counter_int_incremented = (counter_int + 1 + i // 16) & ((1 << 128) - 1)
counter_bytes = counter_int_incremented.to_bytes(16, 'big')
keystream_block = self._aes.encrypt_block(counter_bytes)
chunk = data[i:i+16]
result.extend(bytes(a ^ b for a, b in zip(chunk, keystream_block)))
return bytes(result)
def _compute_tag(self, ciphertext: bytes, aad: bytes,
j0: bytes) -> bytes:
"""
Compute the GCM authentication tag.
GHASH is applied over: AAD || padding || ciphertext || padding || len(AAD) || len(ciphertext)
The result is then XORed with AES(K, J0) to produce the tag.
AAD (Additional Authenticated Data) is authenticated but not encrypted.
In TLS, AAD contains the record header.
"""
def pad16(b: bytes) -> bytes:
pad = (16 - len(b) % 16) % 16
return b + b'\x00' * pad
# Lengths as 64-bit big-endian integers
aad_len_bits = (len(aad) * 8).to_bytes(8, 'big')
ct_len_bits = (len(ciphertext) * 8).to_bytes(8, 'big')
data_to_auth = pad16(aad) + pad16(ciphertext) + aad_len_bits + ct_len_bits
s = ghash(self._H, data_to_auth)
# Tag = GHASH(H, A, C) XOR AES(K, J0)
e_j0 = self._aes.encrypt_block(j0)
tag = bytes(a ^ b for a, b in zip(s, e_j0))
return tag[:self.TAG_LENGTH]
def encrypt(self, nonce: bytes, plaintext: bytes,
aad: bytes = b"") -> bytes:
"""
Encrypt and authenticate.
Returns ciphertext || tag.
nonce: exactly 12 bytes, MUST be unique per (key, message) pair
aad: additional authenticated data (not encrypted, but integrity protected)
"""
if len(nonce) != self.NONCE_LENGTH:
raise ValueError(f"Nonce must be {self.NONCE_LENGTH} bytes")
# J0 = nonce || 0x00000001
j0 = nonce + b'\x00\x00\x00\x01'
ciphertext = self._ctr_encrypt(plaintext, j0)
tag = self._compute_tag(ciphertext, aad, j0)
return ciphertext + tag
def decrypt(self, nonce: bytes, ciphertext_with_tag: bytes,
aad: bytes = b"") -> bytes:
"""
Verify and decrypt.
Raises ValueError if authentication fails.
NEVER return plaintext before verifying the tag.
"""
if len(nonce) != self.NONCE_LENGTH:
raise ValueError(f"Nonce must be {self.NONCE_LENGTH} bytes")
if len(ciphertext_with_tag) < self.TAG_LENGTH:
raise ValueError("Input too short")
ciphertext = ciphertext_with_tag[:-self.TAG_LENGTH]
provided_tag = ciphertext_with_tag[-self.TAG_LENGTH:]
j0 = nonce + b'\x00\x00\x00\x01'
# Compute expected tag
expected_tag = self._compute_tag(ciphertext, aad, j0)
# Constant-time comparison to prevent timing attacks
# secrets.compare_digest does this correctly
import hmac
if not hmac.compare_digest(expected_tag, provided_tag):
raise ValueError("Authentication tag verification failed")
# Only decrypt AFTER verifying tag
return self._ctr_encrypt(ciphertext, j0)
The sequence matters in decrypt: compute the expected tag, compare it to the provided tag, then decrypt. Never decrypt first. If you decrypt before verifying, an attacker who can cause you to process malformed ciphertext might extract information through error messages or timing before you've verified the data is legitimate. The "Never return plaintext before verifying the tag" comment in the code is not paranoid — it's the difference between a secure AEAD scheme and a broken one.
The nonce reuse note is equally serious. In CTR mode, the keystream is entirely determined by the nonce and the key. Two messages encrypted with the same nonce produce ciphertexts where the difference is the difference between the plaintexts: C1 XOR C2 = P1 XOR P2. An attacker with two such ciphertexts can recover the XOR of both plaintexts, which is often enough to recover both. They can also recover the GHASH authentication key H, which allows forging authentication tags. This is called a nonce misuse attack, and it has broken real-world deployments. Generate nonces randomly or use a counter — never reuse them.
Interlude: TLS 1.2 vs TLS 1.3 — What Changed and Why
Before we get to the key exchange, it's worth being explicit about what TLS 1.2 got wrong. The comparison makes the design decisions in TLS 1.3 make sense as a coherent whole rather than arbitrary changes.
TLS 1.2 handshake: 2 round trips. The client sends a ClientHello. The server responds with its certificate, selected parameters, and a ServerHelloDone. The client then sends the key exchange message (possibly encrypted premaster secret), ChangeCipherSpec, and Finished. The server sends ChangeCipherSpec and Finished. Only then can application data flow. Two full round trips before a byte of data moves. TLS 1.3 does it in one.
TLS 1.2 allowed weak ciphers. The TLS 1.2 spec allowed dozens of cipher suites including RC4 (broken), 3DES (64-bit block size, birthday attacks), CBC mode ciphers (Lucky13, BEAST), and export-grade cryptography (40-bit keys, from Cold War era US export restrictions). Any negotiation system that allows weak fallbacks will be exploited. TLS 1.3 ships exactly five cipher suites, all requiring AEAD encryption:
- TLS_AES_128_GCM_SHA256
- TLS_AES_256_GCM_SHA384
- TLS_CHACHA20_POLY1305_SHA256
- TLS_AES_128_CCM_SHA256
- TLS_AES_128_CCM_8_SHA256
TLS 1.2 allowed static RSA key exchange. The client generated a random premaster secret, encrypted it with the server's RSA public key, and sent it. The server decrypted it with the RSA private key. This is straightforward and works — but it means that anyone who steals the server's RSA private key (or later compels the server to disclose it through a legal process) can decrypt all past sessions that used that key. No forward secrecy.
TLS 1.2's handshake was partially cleartext. The server's certificate — including its identity — was sent unencrypted. A passive observer watching a TLS 1.2 connection could determine which server the client was connecting to just from the certificate exchange. TLS 1.3 encrypts everything after ServerHello, including the certificate.
TLS 1.2 allowed renegotiation. Mid-session renegotiation to change cipher suites or add client authentication. This feature directly enabled the MITM injection attack disclosed in 2009 (CVE-2009-3555), required an RFC to patch, and was exploited in the wild. TLS 1.3 removed renegotiation entirely.
The sum of these changes explains why TLS 1.3 is not backward compatible with TLS 1.2. You can't add forward secrecy, remove weak ciphers, and encrypt the handshake while keeping the protocol structure intact. The IETF made the right call: treat it as a new protocol and let TLS 1.2 die on schedule.
NIST deprecated TLS 1.0 and 1.1 for federal government use in 2020. As of 2024, over 95% of web traffic uses TLS 1.2 or 1.3, with TLS 1.3 share growing steadily. Every major CDN and cloud provider defaults to TLS 1.3.
Part 3: ECDHE — Why TLS 1.3 Killed Static RSA
Here's something TLS 1.2 got wrong that TLS 1.3 fixed: in TLS 1.2, the server could use its RSA private key to directly decrypt the session key. The client encrypted the session key with the server's public RSA key, sent it over, and the server decrypted it.
This works. It's also a catastrophic failure mode.
If someone records your TLS 1.2 traffic today and steals the server's private RSA key tomorrow, they can decrypt every recorded session retroactively. The key agreement method gave no forward secrecy — compromise of the long-term key compromises all past sessions.
TLS 1.3 removed static RSA key exchange entirely. RFC 8446 mandates that all key exchanges provide forward secrecy. The mechanism is ECDHE — Elliptic Curve Diffie-Hellman Ephemeral.
Elliptic Curve Diffie-Hellman
The Diffie-Hellman key exchange allows two parties to establish a shared secret over a public channel without transmitting the secret. The classical version uses the discrete logarithm problem on integers mod a prime. ECDHE uses the analogous problem on elliptic curves, which provides equivalent security with much smaller keys.
An elliptic curve over a finite field is the set of points (x, y) satisfying y² = x³ + ax + b (mod p), plus a special "point at infinity." TLS 1.3 uses the P-256 curve (also called secp256r1 or NIST P-256) with parameters defined by NIST:
# NIST P-256 curve parameters
P256_P = 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF
P256_A = 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC
P256_B = 0x5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B
P256_GX = 0x6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296
P256_GY = 0x4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5
P256_N = 0xFFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551
class P256Point:
"""
A point on the NIST P-256 elliptic curve.
Uses affine coordinates (x, y) with the infinity point represented as None.
"""
def __init__(self, x, y):
self.x = x
self.y = y
@classmethod
def infinity(cls):
p = cls.__new__(cls)
p.x = None
p.y = None
return p
def is_infinity(self):
return self.x is None
def __eq__(self, other):
return self.x == other.x and self.y == other.y
def __add__(self, other):
"""
Elliptic curve point addition.
Handles all cases: both infinity, same point, inverse points.
"""
p = P256_P
if self.is_infinity():
return other
if other.is_infinity():
return self
if self.x == other.x:
if self.y != other.y:
return P256Point.infinity() # P + (-P) = infinity
return self._double()
# General addition formula
# slope = (y2 - y1) / (x2 - x1) mod p
lam = ((other.y - self.y) * pow(other.x - self.x, -1, p)) % p
x3 = (lam * lam - self.x - other.x) % p
y3 = (lam * (self.x - x3) - self.y) % p
return P256Point(x3, y3)
def _double(self):
"""Point doubling: P + P."""
p = P256_P
a = P256_A
if self.is_infinity():
return self
# slope = (3*x^2 + a) / (2*y) mod p
lam = ((3 * self.x * self.x + a) * pow(2 * self.y, -1, p)) % p
x3 = (lam * lam - 2 * self.x) % p
y3 = (lam * (self.x - x3) - self.y) % p
return P256Point(x3, y3)
def scalar_multiply(self, k: int):
"""
Scalar multiplication: compute k * self.
Uses double-and-add algorithm.
WARNING: This implementation is vulnerable to timing attacks.
Production code uses Montgomery ladder or constant-time algorithms.
"""
result = P256Point.infinity()
addend = P256Point(self.x, self.y)
while k:
if k & 1:
result = result + addend
addend = addend._double()
k >>= 1
return result
# Generator point G
P256_G = P256Point(P256_GX, P256_GY)
def ecdh_generate_keypair() -> tuple[int, P256Point]:
"""
Generate an ECDHE keypair on P-256.
Returns (private_key, public_key) where:
- private_key is a random integer in [1, n-1]
- public_key is private_key * G
"""
# Generate a random private key
while True:
private_key = secrets.randbelow(P256_N - 1) + 1
break
public_key = P256_G.scalar_multiply(private_key)
return private_key, public_key
def ecdh_compute_shared_secret(private_key: int, peer_public_key: P256Point) -> bytes:
"""
Compute the ECDH shared secret.
The shared secret is the x-coordinate of private_key * peer_public_key.
Both parties compute the same value:
client_private * server_public = client_private * (server_private * G)
= server_private * (client_private * G)
= server_private * client_public
"""
shared_point = peer_public_key.scalar_multiply(private_key)
if shared_point.is_infinity():
raise ValueError("ECDH resulted in point at infinity — invalid key")
# Use the x-coordinate as the shared secret, padded to 32 bytes
return shared_point.x.to_bytes(32, 'big')
The security of ECDH rests on the elliptic curve discrete logarithm problem: given points G and Q = k*G, finding k is computationally infeasible for large k on well-chosen curves. On P-256, the best known attacks have complexity around 2^128 operations. This is the same security level as AES-128 — matching the security level is by design.
The ephemeral part of ECDHE is the key: both client and server generate fresh keypairs for every connection. The shared secret derived from ephemeral keys is never stored. If the server's long-term RSA private key (used for authentication) is later compromised, the attacker cannot retroactively decrypt past sessions because the ephemeral ECDH keys are gone. This is forward secrecy.
Part 4: HKDF — Turning a Shared Secret into Actual Keys
The shared secret from ECDH is not directly used as an encryption key. It's a random-looking 32-byte value, but it's derived from a mathematical operation that could potentially have exploitable structure.
HKDF (HMAC-based Extract-and-Expand Key Derivation Function, RFC 5869) transforms the ECDH output into multiple independent cryptographic keys. TLS 1.3 uses it to derive the handshake encryption keys, the application data keys, and the MAC keys — all separate, all cryptographically independent.
HKDF has two steps:
Extract: PRK = HMAC-Hash(salt, IKM) — condenses input keying material (IKM) and a salt into a pseudorandom key (PRK) of uniform distribution.
Expand: derives output keying material of arbitrary length from PRK, a context string (info), and a length. Each call with different info values produces cryptographically independent keys.
import hmac as hmac_module
import hashlib
def hkdf_extract(salt: bytes, ikm: bytes,
hash_func=hashlib.sha256) -> bytes:
"""
HKDF-Extract: condenses IKM and salt into a pseudorandom key.
If salt is None, use a string of hash_length zero bytes.
"""
if salt is None:
salt = b'\x00' * hash_func().digest_size
return hmac_module.new(salt, ikm, hash_func).digest()
def hkdf_expand(prk: bytes, info: bytes, length: int,
hash_func=hashlib.sha256) -> bytes:
"""
HKDF-Expand: expand a pseudorandom key into output keying material.
"""
h_len = hash_func().digest_size
if length > 255 * h_len:
raise ValueError("Cannot expand to required length")
okm = b""
t = b""
counter = 1
while len(okm) < length:
t = hmac_module.new(prk, t + info + bytes([counter]), hash_func).digest()
okm += t
counter += 1
return okm[:length]
def hkdf_expand_label(secret: bytes, label: str, context: bytes,
length: int, hash_func=hashlib.sha256) -> bytes:
"""
TLS 1.3's HKDF-Expand-Label as defined in RFC 8446 Section 7.1.
HkdfLabel = length (2 bytes) || "tls13 " + label (length-prefixed) || context (length-prefixed)
"""
tls_label = b"tls13 " + label.encode()
# HkdfLabel encoding
hkdf_label = (
length.to_bytes(2, 'big') +
bytes([len(tls_label)]) + tls_label +
bytes([len(context)]) + context
)
return hkdf_expand(secret, hkdf_label, length, hash_func)
def derive_secret(secret: bytes, label: str, messages_hash: bytes,
hash_func=hashlib.sha256) -> bytes:
"""
TLS 1.3's Derive-Secret as defined in RFC 8446 Section 7.1.
Derive-Secret(secret, label, messages) = HKDF-Expand-Label(secret, label, Hash(messages), hash_length)
"""
hash_len = hash_func().digest_size
return hkdf_expand_label(secret, label, messages_hash, hash_len, hash_func)
Part 5: The TLS 1.3 Handshake
Now we have all the components. Let's build the actual protocol.
The TLS 1.3 handshake completes in one round trip (1-RTT). Here's the full sequence:
Client Server
------ ------
ClientHello
- client_random (32 bytes)
- supported cipher suites
- key_share: client's ECDHE public key
-------->
ServerHello
- server_random (32 bytes)
- selected cipher suite
- key_share: server's ECDHE public key
[HANDSHAKE KEYS DERIVED HERE — BOTH SIDES]
{EncryptedExtensions} (encrypted)
{Certificate} (encrypted)
{CertificateVerify} (encrypted — RSA-PSS sig)
{Finished} (encrypted — HMAC)
<--------
{Finished} (encrypted — HMAC)
-------->
[APPLICATION KEYS DERIVED]
{Application Data} <-------> {Application Data}
Everything in {} is encrypted. Everything between ServerHello and the end of the handshake is protected by handshake traffic keys. Application data is protected by separate application traffic keys. This encrypted handshake is one of TLS 1.3's biggest improvements over 1.2 — in TLS 1.2, the certificate was sent in the clear.
import hashlib
import struct
class TLS13Transcript:
"""
Maintains the running hash of all handshake messages.
TLS 1.3 derives keys from hashes of the transcript at specific points.
This ensures the key derivation is bound to the exact messages exchanged.
"""
def __init__(self, hash_func=hashlib.sha256):
self.hash_func = hash_func
self._messages = b""
def add(self, message: bytes):
"""Add a handshake message to the transcript."""
self._messages += message
def digest(self) -> bytes:
"""Return the current transcript hash."""
return self.hash_func(self._messages).digest()
def copy(self) -> 'TLS13Transcript':
"""Return a copy of the transcript at this point."""
t = TLS13Transcript(self.hash_func)
t._messages = self._messages
return t
class TLS13KeySchedule:
"""
TLS 1.3 key schedule as defined in RFC 8446 Section 7.1.
Derives all keys from the ECDH shared secret using HKDF.
The schedule is sequential — each secret is derived from the previous.
"""
def __init__(self, ecdh_shared_secret: bytes,
hash_func=hashlib.sha256):
self.hash_func = hash_func
self.hash_len = hash_func().digest_size
self._derive_secrets(ecdh_shared_secret)
def _derive_secrets(self, ecdh_shared_secret: bytes):
"""Run the full TLS 1.3 key schedule."""
zero = b'\x00' * self.hash_len
# Early secret (no PSK in our implementation, so IKM = 0)
self.early_secret = hkdf_extract(None, zero, self.hash_func)
# Derive salt for handshake secret extraction
derived_early = derive_secret(
self.early_secret, "derived",
self.hash_func(b"").digest(), # Hash of empty string
self.hash_func
)
# Handshake secret: mixes in the ECDH shared secret
self.handshake_secret = hkdf_extract(
derived_early, ecdh_shared_secret, self.hash_func
)
# Application master secret (derived after handshake completes)
derived_hs = derive_secret(
self.handshake_secret, "derived",
self.hash_func(b"").digest(),
self.hash_func
)
self.master_secret = hkdf_extract(derived_hs, zero, self.hash_func)
def handshake_traffic_secrets(self, transcript_hash: bytes) -> tuple[bytes, bytes]:
"""
Derive client and server handshake traffic secrets.
These are used to encrypt handshake messages after ServerHello.
transcript_hash: Hash(ClientHello || ServerHello)
"""
client_hs_secret = derive_secret(
self.handshake_secret, "c hs traffic",
transcript_hash, self.hash_func
)
server_hs_secret = derive_secret(
self.handshake_secret, "s hs traffic",
transcript_hash, self.hash_func
)
return client_hs_secret, server_hs_secret
def application_traffic_secrets(self, transcript_hash: bytes) -> tuple[bytes, bytes]:
"""
Derive client and server application traffic secrets.
These are used after the handshake completes.
transcript_hash: Hash(ClientHello...server Finished)
"""
client_app_secret = derive_secret(
self.master_secret, "c ap traffic",
transcript_hash, self.hash_func
)
server_app_secret = derive_secret(
self.master_secret, "s ap traffic",
transcript_hash, self.hash_func
)
return client_app_secret, server_app_secret
def traffic_key_iv(self, traffic_secret: bytes) -> tuple[bytes, bytes]:
"""
Derive the actual AES key and IV from a traffic secret.
key = HKDF-Expand-Label(traffic_secret, "key", "", key_length)
iv = HKDF-Expand-Label(traffic_secret, "iv", "", iv_length)
"""
key = hkdf_expand_label(traffic_secret, "key", b"", 16, self.hash_func)
iv = hkdf_expand_label(traffic_secret, "iv", b"", 12, self.hash_func)
return key, iv
def finished_key(self, base_key: bytes) -> bytes:
"""
Derive the Finished MAC key.
finished_key = HKDF-Expand-Label(base_key, "finished", "", hash_length)
"""
return hkdf_expand_label(
base_key, "finished", b"", self.hash_len, self.hash_func
)
class TLS13HandshakeSimulation:
"""
Simulated TLS 1.3 handshake between a client and server.
This is not a real TLS implementation — it omits certificate validation,
doesn't implement the full record layer, and skips many extensions.
The purpose is to demonstrate the cryptographic core of the protocol.
DO NOT use this for actual secure communication.
"""
def __init__(self):
# Each party gets their own RSA key for authentication
print("[Setup] Generating RSA keys for server authentication...")
print(" (Using 1024-bit keys for demo speed — production uses 2048+)")
self.server_rsa = rsa_keygen(bits=1024)
# Shared transcript — in a real protocol both sides maintain their own
self.transcript = TLS13Transcript()
self._client_state = {}
self._server_state = {}
def client_hello(self) -> dict:
"""
Client sends ClientHello.
Contains: client random, cipher suite preference, ECDHE key share.
"""
client_random = secrets.token_bytes(32)
client_private, client_public = ecdh_generate_keypair()
msg = {
'type': 'ClientHello',
'client_random': client_random,
'cipher_suite': 'TLS_AES_128_GCM_SHA256',
'key_share': {
'group': 'secp256r1',
'public_key': (client_public.x, client_public.y)
}
}
# Store client's private state
self._client_state = {
'random': client_random,
'ecdh_private': client_private,
'ecdh_public': client_public,
}
# Serialize message for transcript
msg_bytes = self._serialize_message(msg)
self.transcript.add(msg_bytes)
print(f"\n[Client] ClientHello sent")
print(f" client_random: {client_random[:8].hex()}...")
print(f" ECDHE public key x: {hex(client_public.x)[:20]}...")
return msg
def server_hello(self, client_hello_msg: dict) -> tuple[dict, dict]:
"""
Server processes ClientHello, sends ServerHello + encrypted messages.
Returns (server_hello_msg, server_encrypted_msgs).
"""
# Generate server ECDHE keypair
server_private, server_public = ecdh_generate_keypair()
server_random = secrets.token_bytes(32)
server_hello_msg = {
'type': 'ServerHello',
'server_random': server_random,
'cipher_suite': 'TLS_AES_128_GCM_SHA256',
'key_share': {
'group': 'secp256r1',
'public_key': (server_public.x, server_public.y)
}
}
# Add ServerHello to transcript
sh_bytes = self._serialize_message(server_hello_msg)
self.transcript.add(sh_bytes)
# Compute ECDH shared secret
client_pub_point = P256Point(
client_hello_msg['key_share']['public_key'][0],
client_hello_msg['key_share']['public_key'][1]
)
shared_secret = ecdh_compute_shared_secret(server_private, client_pub_point)
print(f"\n[Server] ServerHello sent")
print(f" server_random: {server_random[:8].hex()}...")
print(f" ECDHE shared secret: {shared_secret[:8].hex()}...")
# Key schedule — both sides derive same keys from same shared secret
key_schedule = TLS13KeySchedule(shared_secret)
# Derive handshake traffic keys using transcript hash up to ServerHello
transcript_hash_after_sh = self.transcript.digest()
client_hs_secret, server_hs_secret = key_schedule.handshake_traffic_secrets(
transcript_hash_after_sh
)
server_hs_key, server_hs_iv = key_schedule.traffic_key_iv(server_hs_secret)
server_hs_cipher = AESGCM(server_hs_key)
print(f"\n[Server] Handshake keys derived")
print(f" server_hs_key: {server_hs_key.hex()}")
print(f" server_hs_iv: {server_hs_iv.hex()}")
# --- EncryptedExtensions ---
encrypted_extensions = {'type': 'EncryptedExtensions', 'extensions': []}
ee_bytes = self._serialize_message(encrypted_extensions)
self.transcript.add(ee_bytes)
# --- Certificate ---
# In a real TLS implementation, this is an X.509 certificate chain.
# We simulate it with just the public key.
certificate = {
'type': 'Certificate',
'public_key': self.server_rsa['public'] # (e, n)
}
cert_bytes = self._serialize_message(certificate)
self.transcript.add(cert_bytes)
# --- CertificateVerify ---
# Server signs the transcript hash using RSA-PSS
# This proves the server owns the private key corresponding to the certificate
transcript_hash_for_sig = self.transcript.digest()
# TLS 1.3 prepends a context string to prevent cross-protocol attacks
sig_input = (
b' ' * 64 +
b'TLS 1.3, server CertificateVerify\x00' +
transcript_hash_for_sig
)
signature = rsa_sign_pss(
sig_input,
self.server_rsa['private'],
self.server_rsa['crt']
)
certificate_verify = {
'type': 'CertificateVerify',
'algorithm': 'rsa_pss_rsae_sha256',
'signature': signature
}
cv_bytes = self._serialize_message(certificate_verify)
self.transcript.add(cv_bytes)
# --- Finished ---
# HMAC over entire transcript so far, using derived finished key
finished_key = key_schedule.finished_key(server_hs_secret)
transcript_hash_for_finished = self.transcript.digest()
finished_mac = hmac_module.new(
finished_key, transcript_hash_for_finished, hashlib.sha256
).digest()
finished = {
'type': 'Finished',
'verify_data': finished_mac
}
finished_bytes = self._serialize_message(finished)
self.transcript.add(finished_bytes)
# Encrypt everything after ServerHello using server handshake key
# (In reality, each message is encrypted individually as a TLS record)
handshake_payload = ee_bytes + cert_bytes + cv_bytes + finished_bytes
nonce = server_hs_iv # In practice, nonce is XOR'd with sequence number
encrypted_hs = server_hs_cipher.encrypt(nonce, handshake_payload)
print(f"\n[Server] Encrypted handshake messages ({len(handshake_payload)} bytes)")
print(f" Encrypted payload: {encrypted_hs[:16].hex()}...")
# Store server state for later
self._server_state = {
'key_schedule': key_schedule,
'server_hs_secret': server_hs_secret,
'client_hs_secret': client_hs_secret,
'server_hs_key': server_hs_key,
'server_hs_iv': server_hs_iv,
'transcript_after_finished': self.transcript.copy()
}
return server_hello_msg, {
'encrypted_handshake': encrypted_hs,
'server_hs_key': server_hs_key, # would normally be derived independently
'server_hs_iv': server_hs_iv,
}
def client_process_server_hello(self, server_hello_msg: dict,
server_encrypted: dict) -> dict:
"""
Client processes ServerHello and encrypted server messages.
Derives the same keys and verifies the server's Finished MAC.
Sends client Finished.
"""
# Client derives ECDH shared secret
server_pub_point = P256Point(
server_hello_msg['key_share']['public_key'][0],
server_hello_msg['key_share']['public_key'][1]
)
shared_secret = ecdh_compute_shared_secret(
self._client_state['ecdh_private'],
server_pub_point
)
print(f"\n[Client] Derived same shared secret: {shared_secret[:8].hex()}...")
# Client runs same key schedule
key_schedule = TLS13KeySchedule(shared_secret)
transcript_hash_after_sh = self.transcript.digest()
client_hs_secret, server_hs_secret = key_schedule.handshake_traffic_secrets(
transcript_hash_after_sh
)
server_hs_key, server_hs_iv = key_schedule.traffic_key_iv(server_hs_secret)
server_hs_cipher = AESGCM(server_hs_key)
# Decrypt server's encrypted handshake
decrypted = server_hs_cipher.decrypt(
server_hs_iv,
server_encrypted['encrypted_handshake']
)
print(f"[Client] Successfully decrypted server handshake messages")
# In a full implementation, client would:
# 1. Parse EncryptedExtensions, Certificate, CertificateVerify, Finished
# 2. Validate the certificate chain
# 3. Verify the CertificateVerify signature against the transcript
# 4. Verify the Finished MAC
# Client derives application traffic keys
# (Uses transcript hash including server's Finished)
server_state = self._server_state
app_transcript_hash = server_state['transcript_after_finished'].digest()
client_app_secret, server_app_secret = key_schedule.application_traffic_secrets(
app_transcript_hash
)
client_app_key, client_app_iv = key_schedule.traffic_key_iv(client_app_secret)
server_app_key, server_app_iv = key_schedule.traffic_key_iv(server_app_secret)
print(f"\n[Client] Application traffic keys derived:")
print(f" client_app_key: {client_app_key.hex()}")
print(f" server_app_key: {server_app_key.hex()}")
return {
'client_app_key': client_app_key,
'client_app_iv': client_app_iv,
'server_app_key': server_app_key,
'server_app_iv': server_app_iv,
}
@staticmethod
def _serialize_message(msg: dict) -> bytes:
"""Simple deterministic serialization for transcript hashing."""
import json
# Convert any bytes/tuples to hex strings for JSON serialization
def convert(obj):
if isinstance(obj, bytes):
return obj.hex()
if isinstance(obj, tuple):
return [convert(x) for x in obj]
if isinstance(obj, dict):
return {k: convert(v) for k, v in obj.items()}
return obj
return json.dumps(convert(msg), sort_keys=True).encode()
Running the Full Handshake
def run_tls13_simulation():
"""
Full TLS 1.3 handshake simulation.
Demonstrates the complete protocol flow with key derivation.
"""
print("=" * 70)
print("TLS 1.3 Handshake Simulation")
print("=" * 70)
sim = TLS13HandshakeSimulation()
# 1. Client sends ClientHello
ch = sim.client_hello()
# 2. Server responds with ServerHello + encrypted messages
sh, server_encrypted = sim.server_hello(ch)
# 3. Client processes server messages, derives application keys
app_keys = sim.client_process_server_hello(sh, server_encrypted)
# 4. Demonstrate application data encryption
print("\n" + "=" * 70)
print("Application Data Exchange")
print("=" * 70)
# Client sends an HTTP request
http_request = b"GET / HTTP/1.1\r\nHost: example.com\r\n\r\n"
client_cipher = AESGCM(app_keys['client_app_key'])
# In TLS 1.3, the nonce is the IV XOR'd with the sequence number
# For simplicity we use the IV directly here
encrypted_request = client_cipher.encrypt(
app_keys['client_app_iv'],
http_request,
aad=b"TLS13 application record" # Simulated record header as AAD
)
print(f"\n[Client] Sending encrypted HTTP request ({len(http_request)} bytes)")
print(f" Plaintext: {http_request[:40]}")
print(f" Ciphertext: {encrypted_request[:20].hex()}...")
# Server decrypts the request
server_cipher = AESGCM(app_keys['client_app_key'])
decrypted_request = server_cipher.decrypt(
app_keys['client_app_iv'],
encrypted_request,
aad=b"TLS13 application record"
)
print(f"\n[Server] Decrypted request: {decrypted_request}")
assert decrypted_request == http_request, "Decryption mismatch!"
# Server sends response
http_response = b"HTTP/1.1 200 OK\r\nContent-Length: 13\r\n\r\nHello, World!"
server_response_cipher = AESGCM(app_keys['server_app_key'])
encrypted_response = server_response_cipher.encrypt(
app_keys['server_app_iv'],
http_response,
aad=b"TLS13 application record"
)
print(f"\n[Server] Sending encrypted HTTP response ({len(http_response)} bytes)")
print(f" Plaintext: {http_response}")
print(f" Ciphertext: {encrypted_response[:20].hex()}...")
client_response_cipher = AESGCM(app_keys['server_app_key'])
decrypted_response = client_response_cipher.decrypt(
app_keys['server_app_iv'],
encrypted_response,
aad=b"TLS13 application record"
)
print(f"\n[Client] Decrypted response: {decrypted_response}")
assert decrypted_response == http_response, "Decryption mismatch!"
print("\n" + "=" * 70)
print("Handshake and data exchange complete. All assertions passed.")
print("=" * 70)
if __name__ == "__main__":
run_tls13_simulation()
Part 6: Verifying Against Production Libraries
The real test of any from-scratch implementation is whether it produces results consistent with production-grade libraries. Let's verify our AES and RSA implementations against cryptography.
def verify_aes_implementation():
"""
Verify our AES-128 block cipher against PyCryptodome.
Requires: pip install pycryptodome
"""
try:
from Crypto.Cipher import AES as CryptoAES
except ImportError:
print("pycryptodome not installed. Run: pip install pycryptodome")
return
import os
key = os.urandom(16)
plaintext = os.urandom(16) # Single block
# Our implementation
our_aes = AES128(key)
our_ciphertext = our_aes.encrypt_block(plaintext)
our_decrypted = our_aes.decrypt_block(our_ciphertext)
# PyCryptodome in ECB mode (single block, no mode complications)
lib_cipher = CryptoAES.new(key, CryptoAES.MODE_ECB)
lib_ciphertext = lib_cipher.encrypt(plaintext)
print("AES-128 Block Cipher Verification:")
print(f" Key: {key.hex()}")
print(f" Plaintext: {plaintext.hex()}")
print(f" Our ciphertext: {our_ciphertext.hex()}")
print(f" Lib ciphertext: {lib_ciphertext.hex()}")
print(f" Match: {our_ciphertext == lib_ciphertext}")
print(f" Decrypt match: {our_decrypted == plaintext}")
print()
def verify_rsa_with_nist_vectors():
"""
Verify RSA-OAEP against known NIST test vectors.
NIST FIPS 186 test vectors: https://csrc.nist.gov/publications/detail/fips/186/5/final
"""
# NIST PKCS#1 v2.1 test vector (truncated for demonstration)
# Full vectors from: https://www.rfc-editor.org/rfc/rfc8017#appendix-C
print("RSA Component Verification:")
# Test Extended GCD
a, b = 35, 15
gcd, x, y = extended_gcd(a, b)
assert gcd == 5, f"GCD failed: expected 5, got {gcd}"
assert a * x + b * y == gcd, f"Bezout identity failed"
print(f" Extended GCD: gcd({a}, {b}) = {gcd}, verified ✓")
# Test modular inverse
a, m = 17, 3120
inv = modinv(a, m)
assert (a * inv) % m == 1, "Modular inverse failed"
print(f" Modular inverse: {a}^-1 mod {m} = {inv}, verified ✓")
# Test Miller-Rabin on known primes and composites
known_primes = [2, 3, 5, 7, 11, 13, 17, 19, 97, 541, 7919]
known_composites = [4, 6, 9, 15, 25, 100, 561, 1105] # 561 is Carmichael number!
for p in known_primes:
assert is_prime(p), f"Miller-Rabin incorrectly called {p} composite"
for c in known_composites:
assert not is_prime(c), f"Miller-Rabin incorrectly called {c} prime"
print(f" Miller-Rabin: all {len(known_primes)} primes and "
f"{len(known_composites)} composites correctly identified ✓")
# Note: 561 = 3 × 11 × 17 is a Carmichael number — composite but passes
# Fermat's primality test for all a coprime to 561. Miller-Rabin catches it.
print(f" Carmichael number 561 (passes Fermat test): "
f"is_prime={is_prime(561)} (correct: False) ✓")
print()
def run_full_verification():
"""Run all verification tests."""
print("=" * 70)
print("Verification Against Production Libraries")
print("=" * 70)
print()
verify_rsa_with_nist_vectors()
verify_aes_implementation()
# Full AES-GCM round-trip test
print("AES-GCM Authenticated Encryption Verification:")
key = secrets.token_bytes(16)
nonce = secrets.token_bytes(12)
plaintext = b"This is a secret message for testing AES-GCM"
aad = b"authenticated but not encrypted header"
gcm = AESGCM(key)
ciphertext = gcm.encrypt(nonce, plaintext, aad)
decrypted = gcm.decrypt(nonce, ciphertext, aad)
assert decrypted == plaintext, "AES-GCM round-trip failed"
print(f" Round-trip: {len(plaintext)} bytes encrypted and decrypted ✓")
# Test that tampered ciphertext fails authentication
tampered = bytearray(ciphertext)
tampered[0] ^= 0x01 # Flip one bit
try:
gcm.decrypt(nonce, bytes(tampered), aad)
print(" FAIL: tampered ciphertext should have raised ValueError")
except ValueError:
print(f" Authentication: tampered ciphertext correctly rejected ✓")
# Test that wrong AAD fails authentication
try:
gcm.decrypt(nonce, ciphertext, b"wrong aad")
print(" FAIL: wrong AAD should have raised ValueError")
except ValueError:
print(f" Authentication: wrong AAD correctly rejected ✓")
print()
print("All verification tests passed.")
Part 7: What Can Go Wrong — Production Attack Surface
Building this from scratch clarifies exactly where the landmines are in cryptographic implementations. Here's the attack surface you need to understand:
Timing Attacks on RSA Decryption
The time pow(c, d, n) takes is not constant — it depends on the value of d. Square-and-multiply algorithms take different numbers of operations depending on the bit pattern of the exponent. An attacker who can measure decryption time with high precision can extract bits of d one by one. This is not theoretical: Kocher's 1996 paper demonstrated it practically against SSL servers.
Mitigations: RSA blinding (multiply ciphertext by a random value before decryption, compensate after), Montgomery multiplication, constant-time implementations. The cryptography library implements blinding. Our implementation doesn't.
The specific attack flow: suppose you're measuring the decryption time of 1000 carefully chosen ciphertexts. For a specific bit position in d, some ciphertexts will produce a distinguishably faster or slower computation. By correlating measurement timing with the candidate bit value, you can recover d bit by bit with a few thousand measurements. The attack scales to 2048-bit keys — you just need more measurements. Against a network service you can query repeatedly, this is realistic.
OAEP Padding Oracle Attacks
The Bleichenbacher attack (1998) showed that if an RSA-PKCS#1-v1.5 decryption server returns different error messages for "bad padding" vs. "valid padding but wrong MAC," an attacker can adaptively query the server and decrypt arbitrary ciphertexts. This attack requires roughly 2^20 queries against a typical TLS 1.2 server — feasible. Variants of this attack continued to break TLS implementations for two decades. ROBOT (Return Of Bleichenbacher's Oracle Threat), published in 2017, found Bleichenbacher-vulnerable configurations in 27 of the top 100 HTTPS domains.
OAEP was specifically designed to prevent this class of attack. With OAEP, the padding structure is so complex that flipping a single bit in the ciphertext produces an output that almost certainly has invalid OAEP structure — you can't make targeted modifications. But the mitigation only holds if the implementation returns the same error in the same time regardless of where the OAEP decoding fails.
Our OAEP implementation raises the same ValueError("decryption error") in all failure cases, but the code paths have different lengths. A production implementation would process the entire buffer unconditionally in constant time before making any branching decisions.
AES-GCM Nonce Reuse
We called this out in the implementation, but it deserves reinforcement. Given two ciphertexts (N, C1, T1) and (N, C2, T2) encrypted with the same key and nonce:
C1 XOR C2 = P1 XOR P2(the ciphertexts XOR to the XOR of plaintexts)- The authentication key
H = AES(K, 0)can be recovered fromT1andT2 - With
Hrecovered, the attacker can forge valid authentication tags for arbitrary messages
The H recovery works because the authentication tag in GCM is a polynomial evaluation at H. With two equations (the two tags) and the same variable (H), you can solve for H. Once you have H, you can compute valid tags for any message. The encryption is also broken because C1 XOR C2 = P1 XOR P2 means a known P1 gives P2.
This broke real systems. In 2012, researchers found that certain WPA2-Enterprise implementations reused nonces under specific conditions, enabling session key recovery. In TLS 1.3, the nonce is IV XOR sequence_number — the IV is static (derived per session), the sequence number starts at zero and increments, so every nonce is unique. No randomness required, no state synchronization required.
The Transcript Hash Binding
One subtle security property of TLS 1.3 worth calling out: the key derivation is bound to the transcript hash. The server's Finished MAC is HMAC(finished_key, Hash(entire_transcript_so_far)). If an attacker modifies any handshake message in transit — swaps cipher suites, substitutes a certificate, modifies extensions — the transcript hash changes, the Finished MAC doesn't verify, and the connection fails.
This binding is cryptographically tight. The keys are derived from the ECDH shared secret plus the transcript hash. The MACs are derived from the keys. Change any message and the entire key schedule produces different keys, causing authentication to fail. A TLS 1.3 connection where both Finished messages verify is guaranteed to be the exact same negotiation both parties experienced.
Forward Secrecy Depends on Key Deletion
The forward secrecy guarantee of ECDHE only holds if the ephemeral private keys are actually deleted after use. If an attacker compromises your server and finds cached session secrets in memory, forward secrecy provides no protection for those sessions. Production TLS implementations should zero ephemeral key material immediately after use and should not log or persist session keys.
Why Our Implementation Is Educational, Not Production
The cryptography library (pip install cryptography) provides all of these primitives with:
- Constant-time implementations written in C with careful attention to timing channels
- RSA blinding in every decryption operation
- Hardened memory handling that zeroes sensitive data after use
- Years of peer review and security auditing
- Compliance with NIST recommendations
# This is what real RSA-OAEP looks like in production Python:
from cryptography.hazmat.primitives.asymmetric import padding, rsa
from cryptography.hazmat.primitives import hashes
private_key = rsa.generate_private_key(
public_exponent=65537,
key_size=2048,
)
public_key = private_key.public_key()
# OAEP encryption
ciphertext = public_key.encrypt(
b"secret message",
padding.OAEP(
mgf=padding.MGF1(algorithm=hashes.SHA256()),
algorithm=hashes.SHA256(),
label=None
)
)
# OAEP decryption
plaintext = private_key.decrypt(
ciphertext,
padding.OAEP(
mgf=padding.MGF1(algorithm=hashes.SHA256()),
algorithm=hashes.SHA256(),
label=None
)
)
# AES-GCM
from cryptography.hazmat.primitives.ciphers.aead import AESGCM as CryptoAESGCM
import os
key = os.urandom(32) # 256-bit key
nonce = os.urandom(12) # 96-bit nonce
aead = CryptoAESGCM(key)
ct = aead.encrypt(nonce, b"plaintext", b"aad")
pt = aead.decrypt(nonce, ct, b"aad")
Use these APIs. The educational value of building from scratch is in understanding what they're doing. The operational value is in using the hardened implementation.
Putting It All Together
Here's the full execution:
if __name__ == "__main__":
# Run verification first
run_full_verification()
print()
# Run the TLS 1.3 simulation
run_tls13_simulation()
Run this and you'll see the full stack in motion: Miller-Rabin prime testing, RSA key generation, ECDH key exchange on P-256, HKDF key derivation through the TLS 1.3 schedule, AES-GCM encryption of the handshake and application data, and the RSA-PSS signature that authenticates the server.
The output will show you exactly what the protocol is doing at each step — the random values being generated, the keys being derived, the encrypted bytes that represent the handshake messages that a Wireshark capture of a real TLS 1.3 connection would show you.
What You Actually Learned
The original RSA article covered the math. This covered the engineering. The distance between those two things is the distance between "understanding an algorithm" and "understanding a system."
The specific things that should now be clear:
RSA doesn't encrypt data. It authenticates and establishes keys. In TLS 1.3, it appears exactly once: signing the CertificateVerify message with RSA-PSS. The actual data encryption is AES.
Forward secrecy is architectural, not algorithmic. It's not a property of any single algorithm — it's a property of using ephemeral keys that are discarded after use. ECDHE provides it. Static RSA key exchange doesn't.
Authenticated encryption is not encryption + MAC bolted on. AES-GCM's authentication is integral to its design, not an afterthought. The GHASH function authenticates both the ciphertext and the associated data in a single pass. Decrypting before verifying the tag destroys the security guarantee.
The TLS key schedule is what ties everything together. HKDF takes a single shared secret (32 bytes from ECDH) and derives multiple independent keys for handshake encryption, application encryption, and MAC operations — all bound to the specific messages exchanged in this specific session.
Side channels are a first-class concern. The math being correct is necessary but not sufficient. Timing attacks on RSA decryption, padding oracle attacks on OAEP, nonce reuse attacks on AES-GCM — these all break implementations of correct algorithms. Production cryptography is as much about constant-time execution and careful memory handling as it is about the underlying mathematics.
The post-quantum question is the obvious next step. If you want to see how CRYSTALS-Kyber replaces ECDH in the migration to quantum-resistant TLS, that's the subject we covered in the post-quantum HTTPS article. The key exchange changes. The structure of everything else — the symmetric cipher, the key schedule, the authentication — stays roughly the same.
The algorithms you've built here are the ones running every HTTPS connection you make. Now you know what they're doing.