Applied and computational mathematics

Cryptography

Using number theory and algebra to secure information, from RSA to modern encryption schemes.

IntuitionLocking a Message So Only the Right Person Can Open It

Imagine a padlock that anyone can snap shut, but that only one specific key can open. If everyone publishes their own padlock (but keeps their key secret), then anyone can lock a message for you, yet only you can read it back — no meeting in advance, no secret handshake needed. This is the core idea of public-key cryptography: the "locking" operation is easy to compute in one direction and, without the secret key, computationally infeasible to undo, even though the padlock design itself is public.

Modular multiplication

x \mapsto a x \bmod m

\mathbb{Z}/17\mathbb{Z}

: forward evaluation is instant, while inverting discrete-log / RSA power maps over large moduli is the basis of public-key cryptography.

SchoolModular Arithmetic: The Building Block

Definition: Congruence and modular exponentiation

Two integers $a$ and $b$ are congruent modulo $n$ , written $a \equiv b \pmod{n}$ , when $n \mid (a-b)$ : their difference is an exact multiple of $n$ . Modular exponentiation is repeatedly multiplying a base by itself modulo $n$ , which is exactly the operation cryptographic schemes like RSA and Diffie-Hellman are built on, because it is fast to compute forward but hard to invert.

a \equiv b \pmod{n} \iff n \mid (a-b)

Here $n \mid (a-b)$ means $n$ divides $a-b$ exactly, so $a \equiv b \pmod{n}$ is really a statement about remainders: $a$ and $b$ leave the same remainder when divided by $n$ . Euler's theorem below extends Fermat's little theorem and is the engine behind why RSA decryption recovers the original message.

a^{\phi(n)} \equiv 1 \pmod n \quad \text{whenever} \quad \gcd(a,n)=1

Three cryptographic schemes compared
Scheme	Hard problem it relies on	Typical key size (2026)
RSA	Factoring $n=pq$ into primes	2048-4096 bits
Diffie-Hellman	Discrete logarithm modulo a prime	2048-3072 bits
Elliptic-curve cryptography (ECC)	Discrete logarithm on an elliptic curve group	256-384 bits

UndergraduateWhy RSA Works, and How Diffie-Hellman Creates a Shared Secret

Theorem: RSA Decryption Correctness

Let $n = pq$ be a product of two distinct primes, and let $e$ and $d$ satisfy $ed \equiv 1 \pmod{\phi(n)}$ . Then for every message $m$ with $0 \le m < n$ , encrypting with $e$ and decrypting with $d$ recovers the original message: $(m^e)^d \equiv m \pmod n$ .

Why is it true?

This is the theorem that makes RSA actually usable: it guarantees that whatever the sender encrypts with the public exponent, the holder of the private exponent can always decrypt, for every possible message, not just most of them — the proof has to handle the edge case where a message accidentally shares a factor with the modulus.

Proof

Since $ed \equiv 1 \pmod{\phi(n)}$ , by definition of modular congruence there is a non-negative integer $k$ with $ed = 1 + k\phi(n)$ .

Case 1: $\gcd(m,n)=1$ . Euler's theorem gives $m^{\phi(n)} \equiv 1 \pmod n$ , so raising both sides to the power $k$ and multiplying by $m$ gives $m^{ed} = m \cdot (m^{\phi(n)})^{k} \equiv m \cdot 1^{k} \equiv m \pmod n$ .

Case 2: $\gcd(m,n) \ne 1$ . Since $n = pq$ , this means $p$ divides $m$ or $q$ divides $m$ (not both, since $m$ is smaller than $n$ ). Working modulo $p$ : if $p$ divides $m$ then both $m$ and $m^{ed}$ are congruent to $0$ modulo $p$ ; otherwise $\gcd(m,p)=1$ and Fermat's little theorem gives $m^{p-1} \equiv 1 \pmod p$ , and since $(p-1)$ divides $\phi(n)$ the same computation as Case 1 shows $m^{ed} \equiv m \pmod p$ . The identical argument modulo $q$ shows $m^{ed} \equiv m \pmod q$ .

By the Chinese Remainder Theorem, a congruence that holds modulo $p$ and modulo $q$ separately also holds modulo their product $n=pq$ , so $(m^e)^d \equiv m \pmod n$ holds for every message $m$ , not just those coprime to $n$ .

Theorem: Diffie-Hellman Shared Secret Agreement

Fix a prime $p$ and a base $g$ . If Alice picks a secret $a$ and sends $A = g^a \bmod p$ , and Bob picks a secret $b$ and sends $B = g^b \bmod p$ , then computing $B^a \bmod p$ and $A^b \bmod p$ both yield the same value $g^{ab} \bmod p$ , even though neither $a$ nor $b$ was ever transmitted.

Why is it true?

This is what lets two parties agree on a secret key over a public channel that an eavesdropper is watching: the eavesdropper sees the base, the modulus, and both public values, but recovering the shared secret from these requires solving a discrete logarithm, believed to be computationally hard for well-chosen parameters.

Proof

By definition $A = g^a \bmod p$ and $B = g^b \bmod p$ are the results of modular exponentiation, so Bob receives $A$ and computes $B^a = (g^b)^a \bmod p$ , while Alice receives $B$ and computes $A^b = (g^a)^b \bmod p$ .

Modular exponentiation obeys the same law of exponents as ordinary exponentiation, because repeated multiplication modulo $p$ composes exactly like repeated multiplication of integers, only reduced modulo $p$ at each step: $(g^b)^a = g^{ba} = g^{ab} = (g^a)^b$ as exponents of $g$ , and this equality survives reduction modulo $p$ at every stage.

Therefore $B^a \bmod p = g^{ab} \bmod p = A^b \bmod p$ : Alice and Bob independently compute the same quantity $g^{ab} \bmod p$ from their own secret exponent and the other party's public value, without either secret $a$ or $b$ ever appearing on the channel.

The security argument is separate from this correctness argument: correctness only shows both parties land on the same number; hardness of computing $a$ from $g$ , $p$ , and $A$ (the discrete logarithm problem) is what keeps that shared number secret from an observer.

UndergraduateReal-World Applications and Worked Examples

Every HTTPS connection, secure messaging app, and cryptocurrency wallet relies on the theorems above: TLS handshakes use Diffie-Hellman (or its elliptic-curve variant) to agree on a session key, banking systems and software updates use RSA or ECDSA signatures to guarantee authenticity, and blockchain wallets use elliptic-curve discrete logarithms to make a private key computationally infeasible to derive from a public address. The two worked examples below carry out RSA and Diffie-Hellman by hand on small numbers so every step is checkable.

Example: RSA by hand with small primes

Using primes $p=5$ and $q=11$ , with public exponent $e=3$ and message $m=2$ , find the ciphertext and verify that decryption recovers the message.

Solution

Step 1: Compute the modulus $n = 5 \times 11 = 55$ and $\phi(n) = (5-1)(11-1) = 40$ .

Step 2: Check $\gcd(3,40)=1$ , so $e=3$ is a valid public exponent.

Step 3: Find the private exponent $d$ with $3d \equiv 1 \pmod{40}$ . Testing $d=27$ gives $3 \times 27 = 81 = 2 \times 40 + 1$ , so $d=27$ works.

Step 4: Encrypt $m=2$ : the ciphertext is $c = 2^3 \bmod 55 = 8 \bmod 55 = 8$ .

Step 5: Decrypt by computing $c^{27} \bmod 55 = 8^{27} \bmod 55$ . Using repeated squaring modulo 55: $8^2 = 64 \equiv 9$ , $8^4 \equiv 9^2 = 81 \equiv 26$ , $8^8 \equiv 26^2 = 676 \equiv 16$ , $8^{16} \equiv 16^2 = 256 \equiv 36$ . Since $27 = 16+8+2+1$ , multiply $8^{16} \cdot 8^{8} \cdot 8^{2} \cdot 8^{1} \equiv 36 \cdot 16 \cdot 9 \cdot 8 \pmod{55}$ , which reduces step by step to $2$ .

Step 6: The decrypted value is $2$ , exactly the original message, confirming the RSA correctness theorem on this concrete instance.

Example: Diffie-Hellman key exchange by hand

With prime $p=23$ and base $g=5$ , Alice picks secret $a=6$ and Bob picks secret $b=15$ . Compute the shared secret both ways and verify they match.

Solution

Step 1: Alice computes $A = 5^6 \bmod 23$ . Stepping through powers of 5 mod 23: $5^2=25\equiv2$ , $5^3\equiv10$ , $5^4\equiv4$ , $5^5\equiv20$ , $5^6\equiv8$ . So $A=8$ .

Step 2: Bob computes $B = 5^{15} \bmod 23$ . Using $5^6\equiv8$ from above, $5^{12}\equiv8^2=64\equiv18$ , and $5^{15}=5^{12}\cdot5^3\equiv18\cdot10=180\equiv19$ . So $B=19$ .

Step 3: Alice computes the shared secret as $B^a \bmod p = 19^6 \bmod 23$ . Since $19\equiv-4$ , $19^6\equiv(-4)^6=4^6=4096$ , and $4096 = 178\times23+2$ , so this equals $2$ .

Step 4: Bob computes the shared secret as $A^b \bmod p = 8^{15} \bmod 23$ . Writing $8=2^3$ gives $8^{15}=2^{45}$ ; since $2^{11}\equiv1 \pmod{23}$ (a direct check: $2^{11}=2048=89\times23+1$ ), and $45=4\times11+1$ , this reduces to $2^{1}=2$ .

Step 5: Both computations give $2$ , confirming Alice and Bob agree on the same shared secret without ever transmitting $a=6$ or $b=15$ over the channel.

Research frontier as of 2026

The biggest open threat to RSA, Diffie-Hellman, and elliptic-curve cryptography is Shor's 1994 quantum algorithm, which factors integers and computes discrete logarithms in polynomial time on a sufficiently large fault-tolerant quantum computer — no such machine exists yet, but the risk has already driven a global transition. In 2024 NIST finalized the first post-quantum cryptography standards (FIPS 203, a lattice-based key-encapsulation mechanism now called ML-KEM, derived from CRYSTALS-Kyber, and FIPS 204 for digital signatures), whose security rests on the conjectured hardness of lattice problems believed to resist quantum attack. A cautionary lesson from 2022 is that not every "post-quantum" candidate survives scrutiny: the isogeny-based SIKE scheme, a NIST finalist, was broken by a classical (non-quantum) attack, underscoring that this area is still actively being tested rather than settled.

In RSA with $n=55$ , $\phi(n)=40$ , and public exponent $e=3$ , which value of $d$ satisfies $3d \equiv 1 \pmod{40}$ ?

What underlying computational problem does the security of Diffie-Hellman key exchange rest on?

If $\gcd(a,n)=1$ , Euler's theorem states that $a^{\phi(n)} \equiv 1 \pmod n$ where $\phi(n)$ counts which of the following?

A bank wants to sign software updates so customers can verify they truly came from the bank and were not tampered with. Which cryptographic tool directly provides this guarantee?

References

Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone (1996). Handbook of Applied Cryptography
Peter W. Shor (1994). Algorithms for Quantum Computation: Discrete Logarithms and Factoring · arXiv:quant-ph/9508027
National Institute of Standards and Technology (2024). Module-Lattice-Based Key-Encapsulation Mechanism Standard (FIPS 203)