Cryptography and RSA: Number Theory in Practice

RSA is a public-key cryptosystem whose security rests on the difficulty of factoring large integers. One-line statement: Encrypt with

c = m^{e} mod n

, decrypt with

m = c^{d} mod n

, where

e d \equiv 1 (mod φ (n))

and

n = pq

is a product of two large primes. Where it applies: secure web traffic (TLS/HTTPS), digital signatures, email encryption, key exchange. Who/when: Ron Rivest, Adi Shamir, and Leonard Adleman, 1977 (publicly); Clifford Cocks, GCHQ, 1973 (classified).

RSA is an asymmetric cipher in which each party holds a public key $(n, e)$ for encryption/verification and a private decryption exponent $d$ kept secret. Its correctness is a direct application of Euler's theorem and the Chinese Remainder Theorem from elementary number theory, while its security depends on the empirical hardness of the integer factorization problem. RSA matters because it solved the central problem of classical cryptography — how two parties who have never met can communicate securely over an open channel — and because it simultaneously provides authentication via digital signatures. The surprising fact: the very same number-theoretic operation that "obviously" cannot be undone (exponentiation modulo a composite) becomes trivially reversible if and only if you know how $n$ factors — so the entire edifice of modern internet security rests on the gap between multiplying two primes (easy) and recovering them (believed hard).

The Core Insight

Modular exponentiation by $e$ is a permutation of $Z / n Z$ , and its inverse permutation is exponentiation by some $d$ . Computing $d$ from $e$ requires knowing $φ (n)$ , and computing $φ (n) = (p - 1) (q - 1)$ requires knowing the factorization $n = pq$ . Thus a trapdoor one-way function is born: easy forward (public $e$ ), easy backward with secret ( $d$ from the factorization), hard backward without it.

Formal Statement

RSA Key Generation, Encryption, Decryption

Let $p, q$ be distinct large primes and set the modulus $n = pq$ . The Euler totient of $n$ is

φ (n) = (p - 1) (q - 1) .

⟳

φ

is multiplicative for coprime factors, and

φ (p) = p - 1

for prime

p

; alternatively count integers in

[1, n]

not divisible by

p

q

via inclusion–exclusion.

Choose a public exponent $e$ with $1 < e < φ (n)$ and $g cd (e, φ (n)) = 1$ . Define the private exponent $d$ as the modular inverse

e d \equiv 1 (mod φ (n)), d = e^{- 1} mod φ (n) .

⟳

d

exists and is unique mod

φ (n)

precisely because

g cd (e, φ (n)) = 1

; compute it with the extended Euclidean algorithm.

The public key is $(n, e)$ ; the private key is $(n, d)$ (with $p, q, φ (n)$ also secret). For a message $m \in {0, 1, \dots, n - 1}$ :

c = m^{e} mod n (encryption),

⟳

m^{e}

is reduced modulo

n

via fast modular exponentiation (square-and-multiply).

m = c^{d} mod n (decryption) .

⟳substitute

c = m^{e}

to get

m^{e d} mod n

, then apply the correctness theorem below.

Symbols: $p, q$ — secret primes; $n$ — public modulus; $φ (n)$ — Euler totient (secret); $e$ — public exponent; $d$ — private exponent; $m$ — plaintext as integer; $c$ — ciphertext as integer.

RSA Correctness

With keys as above, for every $m \in {0, 1, \dots, n - 1}$ ,

m^{e d} \equiv m (mod n) .

⟳prove

m^{e d} \equiv m

separately mod

p

and mod

q

using Fermat's little theorem, then recombine by the Chinese Remainder Theorem.

Hence decryption recovers the plaintext: $(m^{e})^{d} mod n = m$ .

Why It Holds / Derivation

Correctness of RSA via CRT and Fermat

We show $m^{e d} \equiv m (mod p)$ and $m^{e d} \equiv m (mod q)$ ; the Chinese Remainder Theorem then forces congruence mod $n = pq$ .

Step 1 — Express $e d$ . Since

e d \equiv 1 (mod φ (n))

, write

e d = 1 + k (p - 1) (q - 1)

for some integer

k \geq 0

(from equation [2]). Step 2 — Work modulo $p$ . Two cases. Case (a): $p ∤ m$ . Then

g cd (m, p) = 1

, so Fermat's Little Theorem gives

m^{p - 1} \equiv 1 (mod p)

. Therefore

m^{e d} = m^{1 + k (p - 1) (q - 1)} = m \cdot (m^{p - 1})^{k (q - 1)} \equiv m \cdot 1^{k (q - 1)} \equiv m (mod p) .

⟳factor the exponent so that a multiple of

p - 1

appears, then apply

m^{p - 1} \equiv 1

Case (b): $p ∣ m$ . Then

m \equiv 0 (mod p)

and likewise

m^{e d} \equiv 0 (mod p)

, so

m^{e d} \equiv m (mod p)

trivially.

In both cases $m^{e d} \equiv m (mod p)$ .

Step 3 — Work modulo $q$ . By identical reasoning with

q

in place of

p

m^{e d} \equiv m (mod q)

. Step 4 — Recombine. We have

p ∣ (m^{e d} - m)

and

q ∣ (m^{e d} - m)

. Since

p, q

are distinct primes,

pq = n ∣ (m^{e d} - m)

, i.e.

m^{e d} \equiv m (mod n) .

⟳two distinct primes both dividing an integer means their product divides it (coprimality + CRT).

This proves equation [5], so $c^{d} = (m^{e})^{d} = m^{e d} \equiv m (mod n)$ . $■$

Note we used the full $φ (n)$ exponent argument and got correctness even when $m$ shares a factor with $n$ — a subtlety many proofs miss. The cleaner Euler-theorem version, $m^{φ (n)} \equiv 1 (mod n)$ , only holds when $g cd (m, n) = 1$ ; the CRT-by-cases proof above is strictly more general and handles the (negligibly rare) case $g cd (m, n) > 1$ .

Ron Rivest, Adi Shamir, Leonard Adleman | published 1977

At MIT, Rivest and Shamir repeatedly proposed candidate trapdoor functions which Adleman, the number theorist of the trio, repeatedly broke. The winning idea — modular exponentiation with the factorization as trapdoor — survived Adleman's attacks. Their paper, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems (1978), defined modern asymmetric cryptography. Unknown to them, Clifford Cocks at the British GCHQ had described an essentially identical scheme in a 1973 classified memo, declassified only in 1997.

Building Intuition

Think of a public mailbox with a one-way slot. Anyone can drop a letter in (encrypt with the public key $e$ ), but only the owner with the physical key can open it (decrypt with $d$ ). The number-theoretic "slot" is the map $x \mapsto x^{e} mod n$ . Because $e$ is coprime to $φ (n)$ , this map shuffles the residues ${0, \dots, n - 1}$ into a permutation with no collisions — every ciphertext comes from exactly one plaintext. Undoing the shuffle means finding the inverse exponent $d$ , and the only known efficient route to $d$ passes through $φ (n)$ , which passes through factoring $n$ . Multiplying $p \cdot q$ to build $n$ takes microseconds; reversing it for a 2048-bit $n$ would take the fastest known algorithms longer than the age of the universe.

The RSA trapdoor one-way function: easy forward and backward-with-key, hard backward-without-key

Worked Examples

Toy RSA with small primes

Given:

p = 61

q = 53

. Encrypt the message

m = 65

. Step 1 — Modulus.

n = pq = 61 \cdot 53 = 3233

. Step 2 — Totient.

φ (n) = (p - 1) (q - 1) = 60 \cdot 52 = 3120

(equation [1]). Step 3 — Public exponent. Choose

e = 17

. Check

g cd (17, 3120) = 1

. ✓ Step 4 — Private exponent. Solve

17 d \equiv 1 (mod 3120)

(equation [2]) via extended Euclid. One finds

d = 2753

since

17 \cdot 2753 = 46801 = 15 \cdot 3120 + 1

. Step 5 — Encrypt (equation [3]):

c = 6 5^{17} mod 3233

. Using square-and-multiply:

6 5^{17} mod 3233 = 2790

. Step 6 — Decrypt (equation [4]):

65 = 279 0^{2753} mod 3233

. ✓

c = 2790, decrypts back to m = 65

Computing the private key by hand

Given: public key

(n, e) = (3233, 17)

, and the attacker has factored

n = 61 \cdot 53

. Step 1 — Recover totient.

φ (3233) = 60 \cdot 52 = 3120

. Step 2 — Extended Euclidean algorithm on

(17, 3120)

3120 = 183 \cdot 17 + 9

17 = 1 \cdot 9 + 8

9 = 1 \cdot 8 + 1

8 = 8 \cdot 1

. Back-substitute:

1 = 9 - 8 = 9 - (17 - 9) = 2 \cdot 9 - 17 = 2 (3120 - 183 \cdot 17) - 17 = 2 \cdot 3120 - 367 \cdot 17

. Step 3 — Read off the inverse.

- 367 \cdot 17 \equiv 1 (mod 3120)

, so

d \equiv - 367 \equiv 3120 - 367 = 2753 (mod 3120)

d = 2753

Moral: the instant

n

is factored,

d

falls out of one Euclidean computation. Security

=

unfactorability.

Common Misconceptions

Textbook RSA is NOT secure as a real cipher. The raw map

m \mapsto m^{e} mod n

is deterministic: identical plaintexts always give identical ciphertexts (so it leaks equality), and it is malleable (

c_{1} c_{2}

decrypts to

m_{1} m_{2}

). It also leaks small-message structure. Real systems use padding schemes (OAEP for encryption, PSS for signatures) that inject randomness and structure. Never deploy "schoolbook" RSA. $e$ and $d$ are inverses mod $φ (n)$ , NOT mod $n$ . A frequent error is computing

d = e^{- 1} mod n

. The exponent arithmetic lives in the exponent group of order

φ (n)

(or

λ (n)

), not in

Z / n Z

. Mixing the two moduli yields a

d

that fails to decrypt.

Why $e$ must be coprime to $\varphi(n)$

Suppose someone naively picks $p = 7, q = 11$ , so $n = 77$ , $φ (n) = 60$ , and chooses $e = 6$ . Then $g cd (6, 60) = 6 \neq = 1$ , so $6^{- 1} mod 60$ does not exist — there is no $d$ with $6 d \equiv 1 (mod 60)$ . The encryption map $m \mapsto m^{6} mod 77$ is not a bijection: it collapses distinct plaintexts to the same ciphertext (e.g. it is six-to-one on the unit group fibers), so decryption is impossible. The coprimality condition $g cd (e, φ (n)) = 1$ is exactly what makes $x \mapsto x^{e}$ a permutation.

Connections

RSA sits at the crossroads of pure number theory and applied security. Its correctness is pure Fermat's Little Theorem and the Chinese Remainder Theorem (also used for a 4× decryption speedup via CRT recombination of computations mod $p$ and mod $q$ ). The exponent inverse uses the Extended Euclidean Algorithm. Choosing $e$ and key generation lean on Euler's Totient Function and Primality Testing (Miller–Rabin). Security relates to the Integer Factorization Problem and to the broader Discrete Logarithm Problem underlying its cousin, Diffie–Hellman. The permutation structure is best understood in Group Theory via the unit group $(Z / n Z)^{\times}$ of order $φ (n)$ .

Real-World Applications

TLS / HTTPS: historically RSA authenticated servers and encrypted the session key; modern TLS 1.3 uses RSA chiefly for signatures in certificates while key exchange moved to elliptic-curve Diffie–Hellman.
X.509 digital certificates: Certificate Authorities (DigiCert, Let's Encrypt) sign certificates with RSA-PSS or RSA-PKCS#1 to bind identities to public keys.
PGP / GPG email and file encryption: RSA encrypts the symmetric session key and signs messages.
SSH: RSA host and user keys (ssh-rsa, now often 3072–4096 bits) authenticate logins.
Code signing: Microsoft Authenticode, Apple, and Android app signing use RSA signatures to verify software provenance.
Smart cards and EMV chip payment: RSA underlies offline data authentication in chip-and-PIN cards.
Document/PDF signatures and e-government: national eID schemes and Adobe signatures rely on RSA-PSS.

Historical Development

1973 — Clifford Cocks (GCHQ) describes the RSA algorithm in a classified internal note; kept secret for 24 years.
1976 — Diffie & Hellman publish New Directions in Cryptography, introducing public-key cryptography and the trapdoor concept, but without a concrete encryption scheme.
1977 — Rivest, Shamir, and Adleman discover RSA at MIT; the famous "RSA-129" challenge cipher is posed in Martin Gardner's Scientific American column.
1978 — The RSA paper is published in Communications of the ACM.
1983 — MIT is granted U.S. Patent 4,405,829 on RSA (expired 2000).
1991 — RSA-PKCS#1 v1.5 standardized; later found vulnerable to Bleichenbacher's adaptive chosen-ciphertext attack (1998).
1994 — Peter Shor publishes a quantum algorithm factoring integers in polynomial time, theoretically breaking RSA on a future quantum computer.
1994 — RSA-129 (a 129-digit, ~426-bit challenge) is factored by a worldwide distributed effort, recovering the plaintext "THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE."
2020 — RSA-250 (829 bits) factored, the largest RSA challenge number broken to date, underscoring why ≥2048-bit keys are now mandated.

Subtleties & Limits

Is RSA equivalent to factoring? It is not proven that breaking RSA (recovering

m

from

c

without

d

) is as hard as factoring

n

. Computing

φ (n)

d

is known to be equivalent to factoring, but the RSA problem — extracting

e

-th roots mod

n

— might conceivably be easier than full factorization; no such shortcut is known, yet none is ruled out. Meanwhile, Shor's algorithm breaks RSA in polynomial time on a large fault-tolerant quantum computer, making RSA vulnerable in a post-quantum world and driving the migration to lattice-based schemes (e.g. NIST's CRYSTALS-Kyber/Dilithium). Practical sub-exponential classical factoring (the General Number Field Sieve) sets the key-size goalposts: 2048-bit keys are currently safe classically, but their long-term security is an empirical, not a proven, guarantee.