Executive Summary: Cryptographic Primes
Modern public-key security relies on a fundamental mathematical asymmetry: multiplying primes is trivial, but factoring their product is computationally infeasible:
Multiplying two 1024-bit primes p and q takes microseconds on a laptop; finding p and q given only N = p × q would take classical supercomputers billions of years.
If gcd(a, N) = 1, then a^φ(N) ≡ 1 (mod N). For N = pq, φ(N) = (p - 1)(q - 1). This cyclical congruence powers RSA encryption decryption.
The private key d is the modular multiplicative inverse of public exponent e: e · d ≡ 1 (mod φ(N)), calculated via the Extended Euclidean algorithm.
Every time you access your bank account, send an encrypted WhatsApp message, or connect over HTTPS with TLS 1.3, your electronic privacy is guaranteed by pure number theory. Prior to 1976, encryption required a shared secret key that both parties had to exchange secretly in advance.
In 1977, MIT researchers Ron Rivest, Adi Shamir, and Leonard Adleman published RSA, creating the world's first practical public-key cryptosystem. This masterclass unpacks the exact algebraic mechanisms that make public encryption work, complete with full worked mathematical proofs.
Symmetric vs Asymmetric Ciphers & One-Way Trapdoor Functions
An asymmetric cryptosystem separates the encryption key from the decryption key:
- Public Key (e, N): Published openly to the entire world. Anyone can use it to encrypt a message.
- Private Key (d, N): Kept strictly confidential by the recipient. Only this key can decrypt the ciphertext.
This requires a one-way trapdoor function: a mathematical function f(x) that is easy to compute in the forward direction, but practically impossible to invert unless you possess a secret piece of auxiliary information (the trapdoor).
Modular Arithmetic, Coprimality & Euler's Totient Function φ(n)
Modular arithmetic computes remainders: a ≡ b (mod m) indicates that m divides (a - b).
Euler's Totient Function φ(n) counts the number of positive integers up to n that are coprime to n (sharing no common factor other than 1). If p and q are prime:
Euler's Generalization of Fermat's Little Theorem states that for any integer a coprime to n:
This exact congruence provides the mathematical trapdoor for RSA.
The Complete RSA Algorithm: Key Generation, Encryption & Decryption
Let us walk through a small numerical demonstration of the complete RSA protocol:
Step 1: Select two distinct prime numbers:
p = 61, q = 53
Step 2: Calculate modulus N:
N = p × q = 61 × 53 = 3233
Step 3: Calculate Euler's totient φ(N):
φ(N) = (p - 1)(q - 1) = 60 × 52 = 3120
Step 4: Choose public exponent e:
Select e coprime to 3120: let e = 17 (gcd(17, 3120) = 1)
Public Key: (e = 17, N = 3233)
Step 5: Compute private exponent d:
Solve 17 · d ≡ 1 (mod 3120) → d = 2753
Private Key: (d = 2753, N = 3233)
Step 6: Encryption of plaintext m = 65 (ASCII 'A'):
c = m^e mod N = 65¹⁷ mod 3233 = 2790
Step 7: Decryption of ciphertext c = 2790:
m = c^d mod N = 2790²⁷⁵³ mod 3233 = 65 (Original message restored!)
Computing the Private Exponent via Extended Euclidean Algorithm
To compute d such that e · d ≡ 1 (mod φ(n)), we rewrite the congruence as a linear Diophantine equation:
The Extended Euclidean Algorithm computes the integers d and y via backward substitution through Euclidean division remainders in O(log(φ(n))) steps, ensuring private key generation is lightning-fast even for 4096-bit primes.
Shor's Quantum Algorithm & Post-Quantum Cryptography
Classical computers factor integers using the General Number Field Sieve (GNFS), requiring sub-exponential time O(exp(c (log N)⅓ (log log N)⅔)).
However, in 1994, Peter Shor formulated a quantum algorithm using the Quantum Fourier Transform that finds the period of f(x) = aˣ mod N in polynomial time O((log N)³). A sufficiently large quantum computer running Shor's Algorithm would break RSA and Elliptic Curve Cryptography in minutes.
In response, NIST standardized Post-Quantum Cryptography (PQC) in 2024, shifting global cybersecurity toward lattice-based cryptography (such as CRYSTALS-Kyber and Dilithium), which resist both classical and quantum attacks.
❓ Cryptography FAQs
Why is public key cryptography not used to encrypt large video files or documents directly? ▼
Asymmetric modular exponentiation is computationally intensive (roughly 1,000 times slower than symmetric block ciphers like AES-256). In real-world security (HTTPS / TLS), asymmetric cryptography is used only during the initial handshake to securely negotiate a temporary symmetric session key, which then encrypts bulk streaming data at wire speed.
SolveCalc Pedagogical Insight
ALGEBRAIC ELEGANCEWhy does e = 65537 (2¹⁶ + 1) appear in almost all real-world SSL certificates?
65537 is the 4th Fermat prime. In binary, 65537 is 10000000000000001 (only two 1s!). When computing modular exponentiation via the repeated squaring algorithm, this requires only 16 squarings and 1 single multiplication, maximizing client encryption speed while remaining large enough to thwart low-exponent Coppersmith attacks.