RSA

Named after Ronald Rivest, Adi Shamir, Leonard Adleman. A block cipher over $\mathbb{Z}_n$ used for both encryption and digital signatures.

Security rests on the integer factorization problem: given $n = pq$ for 2 large equal-size primes, finding $p, q$ is computationally intractable. The interactive guide to RSA steps through key generation, encryption, and why factoring $n$ is hard.

Key Pair Generation

• Choose 2 large, distinct, equal-size primes $p, q$, kept secret.
• Compute $n = pq$, public, its bit length is the RSA key length.
• Compute $\phi(n) = (p-1)(q-1)$, kept secret.
• Choose $e$ with $1 < e < \phi(n)$ and $\gcd(e, \phi(n)) = 1$, public.
• Compute $d \equiv e^{-1} \pmod{\phi(n)}$, secret.

Public key: $\{e, n\}$. Private key: $\{d\}$. $p$, $q$, and $\phi(n)$ must be destroyed after generation.

Primality Testing

$p$ and $q$ are found by drawing random odd integers of the target bit length and testing each for primality until one passes.

Trial division by the first few hundred small primes rejects most candidates in a few operations. Survivors go to the Miller-Rabin probabilistic test.

Miller-Rabin tests an odd $n > 2$. Write $n - 1 = 2^s m$ with $m$ odd. Pick a random base $a$ with $2 \le a \le n - 2$. Then $n$ passes base $a$ iff $a^m \equiv 1 \pmod n$ or $a^{2^r m} \equiv -1 \pmod n$ for some $r$ with $0 \le r < s$.

A composite $n$ passes at most $1/4$ of the bases. Running $k$ independent random bases bounds the probability of accepting a composite by $4^{-k}$. $k$ around $40$ is standard.

Each base costs 1 modular exponentiation, $O\!\left((\log n)^3\right)$ bit operations with schoolbook multiplication. So a candidate is classified in time polynomial in the key length.

Encryption and Decryption

Encryption cost is a single exponentiation with a small exponent $e$. Decryption cost is a single exponentiation with an exponent up to the full length of $n$, far more expensive.

Hybrid Encryption

RSA is not used to encrypt large data directly, since modular exponentiation on large numbers is slow and the message must be smaller than $n$. Instead:

• The sender picks a random symmetric session key $k$ and encrypts the file with a symmetric cipher such as AES under $k$.
• The sender encrypts $k$ with the receiver’s RSA public key and sends both the encrypted file and the encrypted key.
• The receiver recovers $k$ with their RSA private key, then decrypts the file.

Key Length

RSA-1024 provides less than 112 bits of security strength. It is not acceptable for new encryption, key transport, or signature generation.

Use an RSA modulus of at least 2048 bits where RSA is required. The larger modulus increases the cost of modular exponentiation, so resource-constrained systems should use a standard modern protocol and an appropriate authenticated key-establishment algorithm rather than weakening RSA.

Correctness

Worked Examples

Given $n = 221$ and base $a = 137$, determine whether Miller-Rabin identifies $n$ as composite.

Given $p = 17$, $q = 11$, and $m = 88$, generate an RSA key pair. Encrypt and decrypt $m$.