Cryptography and RSA: Number Theory in Practice

⚡ Key Takeaways

RSA is a public-key cryptosystem whose security rests on the difficulty of factoring large integers. One-line statement: Encrypt with $c = m^e \bmod n$ , decrypt with $m = c^d \bmod n$ , where $ed \equiv 1 \pmod{\varphi(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).

💡 The Core Insight

Modular exponentiation by $e$ is a permutation of $\mathbb{Z}/n\mathbb{Z}$ , and its inverse permutation is exponentiation by some $d$ . Computing $d$ from $e$ requires knowing $\varphi(n)$ , and computing $\varphi(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.

DefinitionRSA Key Generation, Encryption, Decryption

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

1

\quad \varphi(n) = (p-1)(q-1).

Derivation hint: $\varphi$ is multiplicative for coprime factors, and $\varphi(p)=p-1$ for prime $p$ ; alternatively count integers in $[1,n]$ not divisible by $p$ or $q$ via inclusion–exclusion. Choose a public exponent $e$ with $1 < e < \varphi(n)$ and $\gcd(e,\varphi(n)) = 1$ . Define the private exponent $d$ as the modular inverse

2

\quad e\,d \equiv 1 \pmod{\varphi(n)}, \qquad d = e^{-1} \bmod \varphi(n).

Derivation hint: $d$ exists and is unique mod $\varphi(n)$ precisely because $\gcd(e,\varphi(n))=1$ ; compute it with the extended Euclidean algorithm. The public key is $(n,e)$ ; the private key is $(n,d)$ (with $p,q,\varphi(n)$ also secret). For a message $m \in \{0,1,\dots,n-1\}$ :

3

\quad c = m^{e} \bmod n \qquad\text{(encryption)},

Derivation hint: $m^e$ is reduced modulo $n$ via fast modular exponentiation (square-and-multiply).

4

\quad m = c^{d} \bmod n \qquad\text{(decryption)}.

Derivation hint: substitute $c = m^e$ to get $m^{ed} \bmod n$ , then apply the correctness theorem below. Symbols: $p,q$ — secret primes; $n$ — public modulus; $\varphi(n)$ — Euler totient (secret); $e$ — public exponent; $d$ — private exponent; $m$ — plaintext as integer; $c$ — ciphertext as integer.

TheoremRSA Correctness

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

5

\quad m^{ed} \equiv m \pmod{n}.

Derivation hint: prove $m^{ed}\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 \bmod n = m$ .

ProofCorrectness of RSA via CRT and Fermat

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

Step 1 — Express $ed$ . Since $ed \equiv 1 \pmod{\varphi(n)}$ , write $ed = 1 + k(p-1)(q-1)$ for some integer $k \ge 0$ (from equation [2]).

Step 2 — Work modulo $p$ . Two cases. Case (a): $p \nmid m$ . Then $\gcd(m,p)=1$ , so Fermat's Little Theorem gives $m^{p-1}\equiv 1\pmod p$ . Therefore

6

\quad m^{ed} = m^{1+k(p-1)(q-1)} = m\cdot\big(m^{p-1}\big)^{k(q-1)} \equiv m\cdot 1^{k(q-1)} \equiv m \pmod p.

Derivation hint: factor the exponent so that a multiple of $p-1$ appears, then apply $m^{p-1}\equiv1$ . *Case (b): $p \mid m$ .* Then $m \equiv 0 \pmod p$ and likewise $m^{ed}\equiv 0 \pmod p$ , so $m^{ed}\equiv m \pmod p$ trivially. In both cases $m^{ed}\equiv m \pmod p$ .

Step 3 — Work modulo $q$ . By identical reasoning with $q$ in place of $p$ , $m^{ed}\equiv m \pmod q$ .

Step 4 — Recombine. We have $p \mid (m^{ed}-m)$ and $q \mid (m^{ed}-m)$ . Since $p,q$ are distinct primes, $pq=n \mid (m^{ed}-m)$ , i.e.

7

\quad m^{ed}\equiv m \pmod n.

Derivation hint: 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^{ed} \equiv m \pmod n$ . $\blacksquare$

∎

🧠 Intuition

Note we used the full $\varphi(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^{\varphi(n)}\equiv 1\pmod n$ , only holds when $\gcd(m,n)=1$ ; the CRT-by-cases proof above is strictly more general and handles the (negligibly rare) case $\gcd(m,n)>1$ .

mathematician · 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.

🧠 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 \bmod n$ . Because $e$ is coprime to $\varphi(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 $\varphi(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.

Figure

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

ExampleToy 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. $\varphi(n) = (p-1)(q-1) = 60\cdot 52 = 3120$ (equation [1]).

Step 3 — Public exponent. Choose $e = 17$ . Check $\gcd(17,3120)=1$ . ✓

Step 4 — Private exponent. Solve $17d \equiv 1 \pmod{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 = 65^{17} \bmod 3233$ . Using square-and-multiply: $65^{17}\bmod 3233 = 2790$ .

Step 6 — Decrypt (equation [4]): $65 = 2790^{2753} \bmod 3233$ . ✓

\boxed{c = 2790,\qquad \text{decrypts back to } m = 65}

ExampleComputing 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. $\varphi(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\cdot17) - 17 = 2\cdot 3120 - 367\cdot 17$ .

Step 3 — Read off the inverse. $-367\cdot 17 \equiv 1 \pmod{3120}$ , so $d \equiv -367 \equiv 3120-367 = 2753 \pmod{3120}$ .

\boxed{d = 2753}

Moral: the instant $n$ is factored, $d$ falls out of one Euclidean computation. Security $=$ unfactorability.

⚠️ Common mistake

Textbook RSA is NOT secure as a real cipher. The raw map $m\mapsto m^e \bmod 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.

⚠️ Common mistake

$e$ and $d$ are inverses mod $\varphi(n)$ , NOT mod $n$ . A frequent error is computing $d = e^{-1}\bmod n$ . The exponent arithmetic lives in the exponent group of order $\varphi(n)$ (or $\lambda(n)$ ), not in $\mathbb{Z}/n\mathbb{Z}$ . Mixing the two moduli yields a $d$ that fails to decrypt.

CounterexampleWhy

e

must be coprime to

\varphi(n)

Suppose someone naively picks $p=7,q=11$ , so $n=77$ , $\varphi(n)=60$ , and chooses $e=6$ . Then $\gcd(6,60)=6\neq 1$ , so $6^{-1}\bmod 60$ does not exist — there is no $d$ with $6d\equiv 1\pmod{60}$ . The encryption map $m\mapsto m^6\bmod 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 $\gcd(e,\varphi(n))=1$ is exactly what makes $x\mapsto x^e$ a permutation.

connection

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 $(\mathbb{Z}/n\mathbb{Z})^\times$ of order $\varphi(n)$ .

🔬 Where this appears

⏳ History

- 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.

open-problem

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 $\varphi(n)$ or $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.

Cryptography and RSA: Number Theory in Practice

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also