Cryptography

RSA: Mathematics

RSA is 47 years old (1977) and still the most widely deployed asymmetric algorithm. Every HTTPS certificate uses RSA or ECDSA for authentication. Every SSH key pair is RSA or Ed25519. The mathematics behind RSA connects number theory, modular arithmetic, and computational complexity in a way that makes hard problems into security guarantees.

**TLS certificates**: every certificate signed with RSA-2048 or RSA-4096. Let's Encrypt issues millions of RSA certificates per month.
**SSH RSA keys**: generated by billions of servers. ssh-keygen -t rsa -b 4096 creates a key based on RSA key generation.
**PGP/GPG email encryption**: RSA has been the default key type since PGP 2.0 (1992). Modern versions default to Ed25519.
**Smart cards / PIV**: government CAC cards use RSA-2048. FIPS 201 mandates RSA or ECDSA for federal ID.

RSA Key Generation

RSA key generation: choose two large primes p and q, compute n=p*q, find e coprime to phi(n)=(p-1)*(q-1), compute d=e^-1 mod phi(n). Public key is (n,e), private key is (n,d). Key security depends entirely on the difficulty of factoring n.

e=65537 (2^16+1) is the standard public exponent: it's prime (good), small (fast encryption), and large enough to prevent small-exponent attacks. RSA Lab's PKCS#1 mandates e >= 65537 since 2002.

What information must remain secret in RSA?

RSA Encryption and Decryption

RSA encryption: C = M^e mod n. Decryption: M = C^d mod n. The mathematical relationship e*d ≡ 1 (mod phi(n)) ensures that (M^e)^d ≡ M (mod n) for any message M coprime to n.

Textbook RSA (no padding) is deterministic and malleable - never use it directly. Real systems use OAEP (for encryption) or PSS (for signatures). Both add randomness making the ciphertext non-deterministic.

Why is textbook RSA (M^e mod n without padding) insecure?

RSA Correctness Proof

Why does (M^e)^d ≡ M (mod n)? The answer is Euler's theorem: for gcd(M,n)=1, M^phi(n) ≡ 1 (mod n). Since e*d ≡ 1 (mod phi(n)), we have e*d = k*phi(n) + 1 for some integer k.

Chinese Remainder Theorem (CRT) is also used in RSA implementation: computing C^d mod n is faster as (C^d mod p, C^d mod q) separately then combining via CRT. This optimization (Garner's formula) gives a 4x speedup for decryption.

What mathematical theorem guarantees RSA correctness?

Euler's Theorem and Carmichael's Function

Euler's totient function phi(n) counts integers in [1,n] coprime to n. For RSA: phi(p*q) = (p-1)*(q-1). Carmichael's function lambda(n) = lcm(p-1, q-1) is a smaller value that also satisfies M^lambda(n) ≡ 1 mod n and produces smaller, equivalent private keys.

Modern RSA implementations (OpenSSL 3.0, PKCS#1 v2.2 / RFC 8017) use lambda(n) instead of phi(n) for key generation. This produces a smaller private exponent d that is mathematically equivalent but operationally identical in security.

What is the advantage of using Carmichael's lambda(n) instead of Euler's phi(n) for RSA?

Key Ideas

**Key generation**: choose primes p,q; n=p*q; phi(n)=(p-1)(q-1); e=65537; d=e^-1 mod phi(n). Security = factoring n.
**Encryption/decryption**: C=M^e mod n, M=C^d mod n. Always use OAEP padding - textbook RSA is deterministic and malleable.
**Correctness**: Euler's theorem: M^phi(n) ≡ 1 mod n. Since e*d ≡ 1 mod phi(n), M^(e*d) ≡ M mod n.
**Carmichael's lambda**: modern implementations use lambda(n)=lcm(p-1,q-1) for smaller equivalent private key d.

Вопросы для размышления

If an attacker can factor a 2048-bit RSA modulus, which specific private values can they compute and how?
Why does CRT decryption (computing mod p and mod q separately) give a 4x speedup over direct computation mod n?
RSA key generation requires two large primes. How does Python's `sympy.randprime` ensure the generated numbers are actually prime?