RSA and public-key cryptography concepts (intro) - Discrete Math

SECTION 1

Historical Context & Motivation

For centuries, the practice of cryptography depended on a single, seemingly inescapable requirement: both the sender and receiver of a secret message had to share the same key in advance. This arrangement, known as symmetric-key cryptography, worked well for diplomats who could exchange codebooks through trusted couriers, but it posed a fundamental logistical problem—the key distribution problem. How can two parties who have never met establish a shared secret over an insecure channel, such as the open internet, without an eavesdropper intercepting that secret? This question drove decades of research and ultimately gave rise to one of the most elegant applications of number theory in modern computing.

1874 • Jevons's Number-Theoretic Intuition

William Stanley Jevons observed in The Principles of Science that multiplying two large primes is easy, but recovering the factors from the product is extremely difficult—an early hint of the one-way function concept.

1976 • Diffie–Hellman Key Exchange

Whitfield Diffie and Martin Hellman published New Directions in Cryptography, introducing the revolutionary concept of public-key cryptography and a practical key-agreement protocol based on discrete logarithms.

1977 • RSA Algorithm Published

Ron Rivest, Adi Shamir, and Leonard Adleman at MIT described the first practical public-key encryption and signature scheme, which they named RSA. Its security relies on the difficulty of factoring large semiprimes.

1997 • GCHQ's Prior Discovery Declassified

The British government declassified work showing that James Ellis, Clifford Cocks, and Malcolm Williamson at GCHQ had independently conceived both public-key cryptography and an RSA-equivalent scheme several years before the academic publications.

2002 • RSA Patent Expires & Open Adoption

The RSA patent expired, enabling unrestricted use. RSA had already become the backbone of SSL/TLS, securing virtually all e-commerce and internet communications worldwide.

The invention of public-key cryptography resolved the key distribution problem by introducing a fundamentally asymmetric model: a user publishes one key for anyone to use when encrypting messages, while keeping a mathematically related but computationally distinct key private for decryption. Understanding how RSA achieves this requires diving into the number-theoretic machinery—prime factorization, modular exponentiation, and Euler's theorem—that makes the scheme both secure and practical.

SECTION 2

Core Principles of Public-Key Cryptography

Public-key cryptography rests on several interlocking principles that distinguish it from classical symmetric systems. Rather than treating encryption as a single shared operation, it separates the ability to encrypt from the ability to decrypt, producing a pair of keys with complementary roles. The mathematical foundation guarantees that knowledge of the public key does not feasibly reveal the private key, provided certain computational problems remain intractable.

Asymmetric Key Pairs

Each participant generates two keys: a public key (shared openly) and a private key (kept secret). Messages encrypted with one can only be decrypted with the other.

One-Way Functions

The scheme depends on a mathematical operation that is efficient in one direction—such as multiplying two large primes—but computationally infeasible to reverse without special knowledge, known as the trapdoor.

Trapdoor Information

The private key acts as the trapdoor: it provides the extra piece of information (e.g., the prime factors of a large semiprime) needed to efficiently invert the one-way function.

Computational Security

RSA is not unconditionally secure; its strength is based on the assumption that no polynomial-time algorithm exists for factoring large integers. Security is quantified by key length, with 2048-bit keys currently standard.

Digital Signatures

By "encrypting" a message hash with the private key, the sender produces a signature that anyone can verify using the public key, ensuring both authentication and non-repudiation.

✦

KEY TAKEAWAY

Think of public-key cryptography like a special mailbox with a slot. Anyone can walk up and drop a letter through the slot (encrypt with the public key), but only the person who holds the unique key to the mailbox door can open it and read the contents (decrypt with the private key). The crucial insight is that knowing how to deposit mail tells you nothing about how to retrieve it—this is the real-world analogue of a trapdoor one-way function.

SECTION 3

How Public-Key Encryption Works — A Visual Overview

The diagram traces the full RSA communication flow. Bob generates a key pair and publishes his public key (e, n). Alice encrypts plaintext M using Bob's public key to produce ciphertext C = M^e mod n. The ciphertext travels over an insecure channel. Bob decrypts using his private key: M = C^d mod n. Eve observes (e, n) and C but cannot recover M without factoring n.

The diagram above illustrates the central asymmetry of RSA. The public key (e, n) is broadcast to the world—it can be posted on a website, included in a digital certificate, or transmitted over an insecure channel. Anyone who possesses this key can encrypt a message, but only the holder of the corresponding private key d can reverse the process. The eavesdropper Eve sees the same public information and the ciphertext, yet recovering the plaintext requires factoring the modulus n into its prime constituents p and q—a task believed to be computationally infeasible for sufficiently large primes. This is the engine that powers modern secure communications, from HTTPS to encrypted email.

SECTION 4

Mathematical Framework of RSA

RSA derives its correctness from Euler's theorem, which generalizes Fermat's little theorem to composite moduli. The key generation process carefully constructs a modulus and exponents such that encryption followed by decryption returns the original message, all within modular arithmetic. We begin with the essential number-theoretic ingredients.

EULER'S TOTIENT FUNCTION

φ(n) = (p − 1)(q − 1)

For n = pq where p, q are distinct primes, φ(n) counts the integers in {1, …, n − 1} that are coprime to n. Since p and q are prime, the formula simplifies as shown.

EULER'S THEOREM

a^φ(n) ≡ 1 (mod n), for gcd(a, n) = 1

This theorem guarantees that raising any integer a coprime to n to the power φ(n) yields 1 modulo n. RSA exploits this by choosing exponents e and d whose product is congruent to 1 modulo φ(n).

RSA KEY RELATIONSHIP

e × d ≡ 1 (mod φ(n))

The encryption exponent e and decryption exponent d are modular inverses with respect to φ(n). Knowing φ(n) makes computing d from e trivial via the extended Euclidean algorithm; without knowing p and q, computing φ(n) from n is as hard as factoring n.

RSA ENCRYPTION / DECRYPTION

C = M^e mod n · M = C^d mod n

Correctness: C^d = (M^e)^d = M^ed = M^{1 + kφ(n)} = M × (M^φ(n))^k ≡ M × 1^k ≡ M (mod n), by Euler's theorem.

⚠

Why factoring is the linchpin

An attacker who factors n into p × q immediately computes φ(n) = (p − 1)(q − 1) and then derives d from e via the extended Euclidean algorithm. Therefore, the entire security of RSA reduces to the hardness of the integer factorization problem. With current classical algorithms, factoring a 2048-bit integer would require astronomical time, but a sufficiently powerful quantum computer running Shor's algorithm could factor n in polynomial time—motivating ongoing research into post-quantum cryptographic alternatives.

SECTION 5

RSA Key Generation — Step by Step

The RSA key generation procedure transforms two randomly chosen large primes into a public/private key pair. Each step leverages a specific number-theoretic operation, and understanding the rationale behind each choice is essential for appreciating both the scheme's elegance and its potential pitfalls.

The RSA key generation pipeline produces two outputs: the public key (e, n) and the private key (d, n). After generation, the intermediate values p, q, and φ(n) must be securely destroyed to prevent compromise.

Several practical details deserve attention. The encryption exponent e = 65537 (= 2¹⁶ + 1) is favored because its binary representation has only two 1-bits, making modular exponentiation via repeated squaring very efficient. The primes p and q must be of comparable size—if one is much smaller, trial division or factoring heuristics become more effective. Modern implementations typically use primes of 1024 bits each to produce a 2048-bit modulus, though 4096-bit keys are increasingly recommended for high-security applications.

SECTION 6

Worked Example — RSA with Small Primes

To build concrete intuition, we walk through a complete RSA encryption and decryption using intentionally small primes. In practice, these primes would be hundreds of digits long, but the algebraic structure is identical.

RSA Encryption & Decryption with p = 61, q = 53

1
Step 1 — Choose primes and compute modulus

Let p = 61 and q = 53. Compute the modulus: n = p × q = 61 × 53.

n = 3233
2
Step 2 — Compute Euler's totient

φ(n) = (p − 1)(q − 1) = 60 × 52.

φ(3233) = 3120
3
Step 3 — Select encryption exponent e

Choose e = 17. We verify gcd(17, 3120) = 1 by noting that 3120 = 183 × 17 + 9, then 17 = 1 × 9 + 8, 9 = 1 × 8 + 1, confirming the gcd is 1. So e = 17 is coprime to φ(n) and is a valid choice.

e = 17, Public key = (17, 3233)
4
Step 4 — Compute decryption exponent d

We need d such that 17d ≡ 1 (mod 3120). Using the extended Euclidean algorithm: from the computations above, back-substituting gives 1 = 17 × 2753 − 3120 × 15 (verify: 17 × 2753 = 46801 = 15 × 3120 + 1). Therefore d = 2753.

d = 2753, Private key = (2753, 3233)
5
Step 5 — Encrypt a message

Let the plaintext message be M = 65 (representing, say, the letter 'A' in some encoding). Compute C = M^e mod n = 65¹⁷ mod 3233. Using repeated squaring: 65² = 4225 ≡ 992 (mod 3233); 65⁴ ≡ 992² = 984064 ≡ 984064 mod 3233 ≡ 2149; continuing the chain of squarings and multiplications yields C = 2790.

C = 65¹⁷ mod 3233 = 2790
6
Step 6 — Decrypt the ciphertext

Bob receives C = 2790 and computes M = C^d mod n = 2790²⁷⁵³ mod 3233. Despite the enormous exponent, repeated squaring makes this feasible: the algorithm performs at most 2 × ⌈log₂ 2753⌉ ≈ 24 modular multiplications. The result is M = 65, recovering the original plaintext.

M = 2790²⁷⁵³ mod 3233 = 65 ✓

💡

Note on repeated squaring

Computing M^e mod n naïvely by multiplying M by itself e times would be catastrophically slow for 2048-bit exponents. The square-and-multiply algorithm reduces the number of modular multiplications to O(log e), making RSA encryption and decryption practical even for enormous keys.

SECTION 7

Symmetric vs. Public-Key Cryptography

RSA does not replace symmetric-key cryptography; in practice, the two complement each other. RSA is computationally expensive—modular exponentiation with 2048-bit numbers is orders of magnitude slower than the block cipher operations in AES. For this reason, modern protocols like TLS use a hybrid approach: RSA (or another public-key scheme) securely exchanges a symmetric session key, and all subsequent bulk data is encrypted with the fast symmetric cipher. Understanding when and why each type is used is crucial for any practitioner.

Property	Symmetric (e.g., AES)	Asymmetric (e.g., RSA)
Number of keys	One shared secret key	Key pair: public + private
Key distribution	Must be shared via secure channel	Public key can be shared openly
Speed	Very fast (hardware-optimized)	100–1000× slower for equivalent security
Typical key size	128 or 256 bits	2048 or 4096 bits
Digital signatures	Not natively supported	Natively supported
Primary use	Bulk data encryption	Key exchange, authentication, signatures
Security basis	Confusion & diffusion (Shannon)	Computational hardness of number-theoretic problem

Key differences between symmetric and asymmetric cryptosystems

✦

KEY TAKEAWAY

In engineering terms, RSA and AES serve complementary roles much like a combination lock on a warehouse and the forklift inside it. RSA is the combination lock—slow to operate but solves the access control problem. Once inside, the forklift (AES) does the heavy lifting of moving bulk data. This hybrid design captures the best of both worlds: RSA's key-distribution elegance and AES's speed.

SECTION 8

Connections to Advanced Theory & Future Directions

The introductory RSA framework presented here opens the door to a rich landscape of more advanced topics. Several active areas of research extend, refine, or challenge the assumptions underlying RSA, and a college-level student of discrete mathematics should be aware of the broader ecosystem into which this material fits.

Introductory RSA Concept	Advanced Extension
Textbook RSA (direct exponentiation)	Padded RSA (OAEP) — adds randomized padding to prevent deterministic ciphertext attacks and ensure CCA2 security
Euler's totient φ(n)	Carmichael's function λ(n) = lcm(p−1, q−1) — produces a smaller valid exponent, used in modern implementations
Integer factorization hardness	Shor's algorithm — polynomial-time quantum factoring; motivates post-quantum cryptography (lattice-based, code-based schemes)
RSA for encryption	Elliptic Curve Cryptography (ECC) — achieves equivalent security with far smaller keys using the discrete log problem on elliptic curves
Single user key pair	Public Key Infrastructure (PKI) — certificate authorities, certificate chains, and trust models that scale RSA to billions of users

From introductory RSA to advanced topics

Perhaps the most significant contemporary development is the threat posed by quantum computing. Peter Shor demonstrated in 1994 that a quantum computer with sufficiently many stable qubits could factor n in polynomial time, rendering RSA insecure. While large-scale fault-tolerant quantum computers remain an engineering challenge, the cryptographic community is actively standardizing post-quantum algorithms (e.g., NIST's ML-KEM, based on lattice problems) to prepare for a post-RSA era. Nonetheless, RSA remains foundational—both as a pillar of current infrastructure and as the paradigmatic example of how abstract number theory translates into practical security.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

Explain why the public key (e, n) can be published openly without compromising the security of RSA. Specifically, what computational barrier prevents an adversary from deriving the private key d from the publicly available information?

Show answer

To compute d from e and n, an adversary must first determine φ(n) = (p − 1)(q − 1), which requires knowing the prime factors p and q of the modulus n. Computing φ(n) directly from n is computationally equivalent to factoring n. For sufficiently large primes (e.g., 1024 bits each), no known classical algorithm can factor n in feasible time. Therefore, while e and n are public, the factorization barrier ensures that d remains computationally inaccessible to anyone who does not know p and q.

Question 2: BASIC CALCULATION

Given primes p = 11 and q = 13, compute n, φ(n), and verify that e = 7 is a valid encryption exponent. Then compute the decryption exponent d.

Show answer

First, n = 11 × 13 = 143 and φ(n) = (11 − 1)(13 − 1) = 10 × 12 = 120. To verify e = 7 is valid, check gcd(7, 120): 120 = 17 × 7 + 1, so gcd(7, 120) = 1, confirming e = 7 is coprime to φ(n). Now find d such that 7d ≡ 1 (mod 120). Since 120 = 17 × 7 + 1, we have 1 = 120 − 17 × 7, giving 7 × (−17) ≡ 1 (mod 120). Converting: d = −17 + 120 = 103. Verification: 7 × 103 = 721 = 6 × 120 + 1 ≡ 1 (mod 120). Therefore d = 103.

Question 3: INTERMEDIATE

Using the key pair from Problem 2 (public key (7, 143), private key (103, 143)), encrypt the plaintext M = 9 and then decrypt the resulting ciphertext to confirm you recover M. Show the repeated squaring steps for the encryption.

Show answer

Encryption: C = 9⁷ mod 143. Using repeated squaring: 9¹ = 9; 9² = 81; 9⁴ = 81² = 6561, and 6561 mod 143 = 6561 − 45 × 143 = 6561 − 6435 = 126; so 9⁴ ≡ 126. Then 9⁷ = 9⁴ × 9² × 9¹ ≡ 126 × 81 × 9 mod 143. First, 126 × 81 = 10206, and 10206 mod 143 = 10206 − 71 × 143 = 10206 − 10153 = 53. Then 53 × 9 = 477, and 477 mod 143 = 477 − 3 × 143 = 477 − 429 = 48. So C = 48. Decryption: M = 48¹⁰³ mod 143. Computing this via repeated squaring (working modulo 143 at each step) yields M = 9, confirming correctness.

Question 4: APPLIED

A web server generates RSA keys with p = 7, q = 19, and e = 5. A client wants to send the numeric message M = 4. An attacker intercepts the ciphertext C. (a) Compute the ciphertext C. (b) Show exactly how the attacker could derive the private key if they managed to factor n. (c) Explain why this key size is completely insecure in practice.

Show answer

(a) n = 7 × 19 = 133 and C = 4⁵ mod 133 = 1024 mod 133 = 1024 − 7 × 133 = 1024 − 931 = 93. (b) The attacker factors n = 133 = 7 × 19, then computes φ(133) = 6 × 18 = 108, and finally uses the extended Euclidean algorithm to find d = 5⁻¹ mod 108. Since 5 × 65 = 325 = 3 × 108 + 1, d = 65. The attacker then computes M = 93⁶⁵ mod 133 = 4, recovering the plaintext. (c) This key is insecure because n = 133 is trivially factorable by trial division—any number below √133 ≈ 11.5 could be tested. In practice, n must be at least 2048 bits (≈ 617 decimal digits) so that the best known factoring algorithms (e.g., the General Number Field Sieve) require infeasible computational resources.

Question 5: CRITICAL THINKING

Textbook RSA (without padding) is deterministic: encrypting the same plaintext M with the same public key always produces the same ciphertext C. Explain why this property is a serious security vulnerability. Describe a concrete attack scenario, and explain at a high level how OAEP (Optimal Asymmetric Encryption Padding) addresses this weakness.

Show answer

Deterministic encryption allows a chosen-plaintext attack: if an adversary suspects the plaintext is one of a small set of possibilities (e.g., 'YES' or 'NO' in an encrypted vote), they can encrypt each candidate under the public key and compare the results to the intercepted ciphertext. This immediately reveals the plaintext without factoring n. More generally, deterministic encryption leaks equality—if the same message is sent twice, identical ciphertexts reveal this fact. OAEP (Optimal Asymmetric Encryption Padding), introduced by Bellare and Rogaway, solves this by prepending random padding to the plaintext before encryption. The padding incorporates a random seed processed through hash functions, ensuring that even identical plaintexts produce different ciphertexts each time. OAEP has been proven to provide IND-CCA2 security (indistinguishability under adaptive chosen-ciphertext attack) in the random oracle model, which is the strongest standard notion of security for public-key encryption.

SUMMARY

RSA and Public-Key Cryptography — Summary

Summary

Public-key cryptography solved the centuries-old key distribution problem by introducing asymmetric key pairs: a freely published public key for encryption and a secret private key for decryption. The RSA algorithm realizes this paradigm using the machinery of modular arithmetic: the modulus n = pq is the product of two large primes, Euler's totient function φ(n) governs the relationship between the encryption exponent e and the decryption exponent d, and Euler's theorem guarantees that decryption recovers the original plaintext.

RSA's security depends entirely on the computational hardness of integer factorization—recovering p and q from n is believed to be infeasible for sufficiently large primes using classical computers. In practice, RSA operates within a hybrid framework alongside fast symmetric ciphers like AES, handling key exchange and digital signatures while the symmetric cipher handles bulk encryption. Looking ahead, the advent of quantum computing threatens RSA's factorization assumption, driving the development of post-quantum cryptographic schemes—but RSA remains the foundational example of how pure number theory powers the security of the digital world.