Public-key cryptography: key agreement, RSA, signatures and the post-quantum transition

Symmetric cryptography needs both parties to share a key in advance, which is impossible between strangers on the internet. Public-key cryptography, invented in the 1970s, solves this. Each party has a key pair: a public key that can be shared with anyone and a private key that never leaves its owner. With these pairs two strangers can agree on a shared secret over an open network, anyone can encrypt a message that only the owner can read, and the owner can sign data so that anyone can verify the signature. This lesson builds the mathematics from small examples, then uses real library code, and ends with the transition to post-quantum algorithms that governments in Canada and the United States have now scheduled.

Two warnings frame everything here. First, the small numbers in the examples show the arithmetic but are trivially insecure; real keys are thousands of bits long. Second, public-key primitives are notoriously easy to misuse, so production code uses vetted protocols such as TLS (Lesson 6) and maintained libraries, never hand-rolled RSA. CISSP-112 covered algorithm selection and key management policy for managers; here the goal is to understand why the mechanisms work.

One-way functions with trapdoors

Public-key cryptography rests on functions that are easy to compute in one direction and hard to reverse, unless you know a secret, the trapdoor. Multiplying two large primes is easy; factoring their product is hard. Raising a number to a power modulo a prime is easy; recovering the exponent, the discrete logarithm problem, is hard for well-chosen groups. Modular exponentiation is fast because of square-and-multiply: a 2048-bit exponent takes about 2,048 squarings, not \( 2^{2048} \) multiplications.

# Modular exponentiation is fast even for huge numbers (square-and-multiply)
def power_mod(base, exp, mod):
    result, steps = 1, 0
    base %= mod
    while exp:
        if exp & 1:
            result = result * base % mod
        base = base * base % mod
        exp >>= 1
        steps += 1
    return result, steps
r, steps = power_mod(5, 117, 19)
print("5^117 mod 19 =", r, "in", steps, "squaring steps; built-in pow agrees:", pow(5, 117, 19) == r)
big_exp = 2**2048 - 1159
r, steps = power_mod(3, big_exp, 2**3072 - 1103)
print("a 2048-bit exponent needs only", steps, "squaring steps")
# The reverse problem, the discrete logarithm, has no known fast method for well-chosen groups.
# For a toy prime we can simply try every exponent; for a 2048-bit prime that is hopeless.
print("exponents x with 5^x mod 19 = 7:", [k for k in range(1, 19) if pow(5, k, 19) == 7])

5^117 mod 19 = 1 in 7 squaring steps; built-in pow agrees: True
a 2048-bit exponent needs only 2048 squaring steps
exponents x with 5^x mod 19 = 7: [6, 15]

The hardness is an assumption backed by decades of failed attempts, not a proof. Key sizes are chosen so that the best known algorithms, such as the general number field sieve for factoring, would need far more computation than is feasible. Today a 2048-bit RSA modulus gives roughly 112 bits of security and 3072 bits roughly 128 bits; elliptic-curve keys give the same security with much smaller numbers, 256 bits for 128-bit security.

Diffie–Hellman key agreement

In 1976 Whitfield Diffie and Martin Hellman showed how two parties can agree on a secret over a public channel. They fix public values: a large prime \( p \) and a generator \( g \). Alice picks a private \( a \) and sends \( A = g^a \bmod p \); Bob picks \( b \) and sends \( B = g^b \bmod p \). Each combines their own private value with the other's public value:

An eavesdropper sees \( p \), \( g \), \( A \) and \( B \) but would need a discrete logarithm to find \( s \). The example runs the exchange with toy numbers and then with the standardized 2048-bit group from RFC 3526.

# Diffie-Hellman key agreement with toy numbers, then with a real-size group
p, g = 23, 5                      # public parameters (toy)
a, b = 6, 15                      # private values chosen by Alice and Bob (fixed for the demo)
A, B = pow(g, a, p), pow(g, b, p) # sent in the clear
print("toy:  A =", A, " B =", B, " Alice's secret =", pow(B, a, p), " Bob's secret =", pow(A, b, p))

# RFC 3526 group 14: a 2048-bit safe prime (the full hexadecimal value)
P14 = int(
 "FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD129024E088A67CC74020BBEA63B139B22514A08798E3404DD"
 "EF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7ED"
 "EE386BFB5A899FA5AE9F24117C4B1FE649286651ECE45B3DC2007CB8A163BF0598DA48361C55D39A69163FA8FD24CF5F"
 "83655D23DCA3AD961C62F356208552BB9ED529077096966D670C354E4ABC9804F1746C08CA18217C32905E462E36CE3B"
 "E39E772C180E86039B2783A2EC07A28FB5C55DF06F4C52C9DE2BCBF6955817183995497CEA956AE515D2261898FA0510"
 "15728E5A8AACAA68FFFFFFFFFFFFFFFF", 16)
a = int.from_bytes(b"alice demo private value, never fixed in real code", "big")
b = int.from_bytes(b"bob demo private value, also random in practice!!", "big")
A, B = pow(2, a, P14), pow(2, b, P14)
sa, sb = pow(B, a, P14), pow(A, b, P14)
print("real: prime has", P14.bit_length(), "bits; shared secrets equal:", sa == sb)
print("      first 16 hex digits of the shared secret:", hex(sa)[2:18])

toy:  A = 8  B = 19  Alice's secret = 2  Bob's secret = 2
real: prime has 2048 bits; shared secrets equal: True
      first 16 hex digits of the shared secret: af1ab3e3d954f4ac

Plain Diffie–Hellman has a crucial limit: it is unauthenticated. An attacker in the middle can run one exchange with Alice and another with Bob, and relay traffic between them. Real protocols therefore combine key agreement with signatures or certificates so each side knows whom it is talking to, which is exactly what the TLS handshake in Lesson 6 does. Modern protocols also use ephemeral key pairs, freshly generated for each session and then deleted. This gives forward secrecy: if a server's long-term key is stolen later, past sessions still cannot be decrypted, because their ephemeral secrets no longer exist.

RSA

RSA, published by Rivest, Shamir and Adleman in 1977, was the first practical public-key encryption and signature scheme. Key generation picks two large random primes \( p \) and \( q \), computes \( n = pq \) and \( \varphi(n) = (p-1)(q-1) \), chooses a public exponent \( e \) (almost always 65,537) and computes the private exponent \( d = e^{-1} \bmod \varphi(n) \). Encryption is \( c = m^e \bmod n \) and decryption is \( m = c^d \bmod n \); it works because of Euler's theorem. Security rests on the difficulty of factoring \( n \).

from math import gcd
# Textbook RSA with tiny primes, to show the arithmetic (never use like this)
p, q = 61, 53
n, phi = p * q, (p - 1) * (q - 1)
e = 17
assert gcd(e, phi) == 1
d = pow(e, -1, phi)               # modular inverse (Python 3.8+)
print(f"n = {n}, phi = {phi}, e = {e}, d = {d}")
m = 65
c = pow(m, e, n)
print("encrypt 65 ->", c, "; decrypt ->", pow(c, d, n))
# Why textbook RSA is unsafe: it is deterministic and multiplicative
print("same message encrypts the same way every time:", pow(65, e, n) == c)
c2 = pow(2, e, n)
print("E(65) * E(2) decrypts to", pow(c * c2 % n, d, n), "= 65 * 2: ciphertexts can be combined")

n = 3233, phi = 3120, e = 17, d = 2753
encrypt 65 -> 2790 ; decrypt -> 65
same message encrypts the same way every time: True
E(65) * E(2) decrypts to 130 = 65 * 2: ciphertexts can be combined

The output shows why textbook RSA must never be used directly. It is deterministic, so the same message always gives the same ciphertext and an observer can test guesses. It is also multiplicative: multiplying two ciphertexts gives the encryption of the product of the plaintexts. Real systems therefore use padding schemes that add randomness and structure: OAEP for encryption and PSS for signatures. The older PKCS #1 v1.5 encryption padding has caused a long series of practical failures and should not be used in new designs. In practice RSA encryption is rarely used for data at all; it, or more often an elliptic-curve key agreement, transports a symmetric key, and the data is encrypted with AES-GCM or ChaCha20-Poly1305, an arrangement called hybrid encryption.

from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.hazmat.primitives import hashes
key = rsa.generate_private_key(public_exponent=65537, key_size=3072)
pub = key.public_key()
oaep = padding.OAEP(mgf=padding.MGF1(hashes.SHA256()), algorithm=hashes.SHA256(), label=None)
secret = b"a 32-byte AES key would go here."
c1, c2 = pub.encrypt(secret, oaep), pub.encrypt(secret, oaep)
print("key size:", key.key_size, "bits; ciphertext length:", len(c1), "bytes")
print("OAEP is randomized, so two encryptions differ:", c1 != c2)
print("decrypts correctly:", key.decrypt(c1, oaep) == secret)

key size: 3072 bits; ciphertext length: 384 bytes
OAEP is randomized, so two encryptions differ: True
decrypts correctly: True

Digital signatures

A digital signature is the public-key counterpart of a MAC, with one extra property: anyone with the public key can verify, but only the private-key holder can sign. That gives non-repudiation, the basis for software signing, certificates, signed documents and secure boot. A signature scheme signs a hash of the message, so it works for inputs of any length. Today's main schemes are RSA-PSS, ECDSA on the NIST P-256 curve, and EdDSA, usually Ed25519, which is fast, uses deterministic nonces and avoids several historical pitfalls.

from cryptography.hazmat.primitives.asymmetric.ed25519 import Ed25519PrivateKey
from cryptography.exceptions import InvalidSignature
# Deterministic demo key from a fixed seed; real keys come from Ed25519PrivateKey.generate()
sk = Ed25519PrivateKey.from_private_bytes(bytes(range(32)))
pk = sk.public_key()
release = b"hsm-tool-2.4.1.tar.gz sha256=3f1c...e9"
sig = sk.sign(release)
print("signature length:", len(sig), "bytes")
def check(msg):
    try:
        pk.verify(sig, msg); return "valid"
    except InvalidSignature:
        return "INVALID"
print("original release note:", check(release))
print("tampered release note:", check(release.replace(b"2.4.1", b"2.4.2")))

signature length: 64 bytes
original release note: valid
tampered release note: INVALID

Nonces are the classic failure point of DSA and ECDSA. Each signature needs a fresh secret random number; if one is ever reused, or is merely predictable, the private key can be computed from two signatures. A famous game console signing key was exposed this way in 2010. EdDSA derives its nonce deterministically from the key and message, removing this risk, and RFC 6979 does the same for ECDSA.

Elliptic-curve cryptography

Elliptic-curve cryptography (ECC) performs Diffie–Hellman and signatures in the group of points on an elliptic curve over a finite field. Adding two points follows a geometric rule, and multiplying a point by an integer \( k \) means adding it to itself \( k \) times, computed quickly with double-and-add. The hard problem is the elliptic-curve discrete logarithm: given \( G \) and \( kG \), find \( k \). Because the best known attacks are far slower than those against factoring, a 256-bit curve matches a 3072-bit RSA key. X25519 (Curve25519 key agreement) and Ed25519 signatures are now the defaults in TLS 1.3, SSH, Signal and WireGuard.

# Points on a tiny elliptic curve y^2 = x^3 + 2x + 3 over the integers mod 97
P_, A_, B_ = 97, 2, 3
def add(Pt, Qt):
    if Pt is None: return Qt
    if Qt is None: return Pt
    (x1, y1), (x2, y2) = Pt, Qt
    if x1 == x2 and (y1 + y2) % P_ == 0: return None          # point at infinity
    if Pt == Qt: s = (3 * x1 * x1 + A_) * pow(2 * y1, -1, P_) % P_
    else:        s = (y2 - y1) * pow(x2 - x1, -1, P_) % P_
    x3 = (s * s - x1 - x2) % P_
    return (x3, (s * (x1 - x3) - y1) % P_)
def mul(k, Pt):
    R = None
    while k:
        if k & 1: R = add(R, Pt)
        Pt = add(Pt, Pt); k >>= 1
    return R
G = (87, 70)                                    # a point of order 50
assert (G[1]**2 - (G[0]**3 + A_ * G[0] + B_)) % P_ == 0
print("G =", G, " 2G =", mul(2, G), " 5G =", mul(5, G), " 50G =", mul(50, G), "(point at infinity)")
a, b = 13, 29                                   # private scalars (toy)
print("ECDH: a(bG) =", mul(a, mul(b, G)), " b(aG) =", mul(b, mul(a, G)))

G = (87, 70)  2G = (24, 95)  5G = (53, 24)  50G = None (point at infinity)
ECDH: a(bG) = (0, 10)  b(aG) = (0, 10)

The post-quantum transition

A large, fault-tolerant quantum computer running Shor's algorithm would factor RSA moduli and solve discrete logarithms, including on elliptic curves, in polynomial time, breaking every scheme in the first three rows of the table. Grover's algorithm only halves the effective strength of symmetric keys and hashes, so AES-256 and SHA-384 remain comfortable. No such quantum computer exists yet, but data recorded today could be decrypted when one does, the harvest-now, decrypt-later threat, so long-lived secrets need protection now.

After an open competition, NIST published its first post-quantum standards in August 2024: FIPS 203 (ML-KEM, from CRYSTALS-Kyber) for key encapsulation, FIPS 204 (ML-DSA, from CRYSTALS-Dilithium) and FIPS 205 (SLH-DSA, from SPHINCS+) for signatures. In March 2025 NIST selected HQC, a code-based scheme, as a backup key-encapsulation mechanism, with a draft standard expected in 2026. Browsers and major servers already negotiate hybrid key exchange, combining X25519 with ML-KEM-768, so a connection stays secure if either component holds.

In Canada, the Canadian Centre for Cyber Security published a roadmap in June 2025 for migrating federal non-classified systems to post-quantum cryptography. Departments must have migration plans by April 2026, complete high-priority systems by the end of 2031 and finish all systems by the end of 2035. The Cyber Centre encourages critical infrastructure operators and suppliers to follow similar timelines, starting with an inventory of where cryptography is used.

For developers the first steps are the same everywhere: build an inventory of where public-key cryptography is used, prefer crypto-agile designs in which algorithms are configuration rather than hard-coded constants, keep libraries current so hybrid modes arrive automatically, and protect long-lived data first.

Worked examples