RSA

RSA (Rivest, Shamir, Adleman, 1977) is 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.

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.

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.

Correctness

Worked Example

$p = 17$, $q = 11$.

• $n = 187$.
• $\phi(n) = 16 \times 10 = 160$.
• $e = 7$, since $\gcd(7, 160) = 1$.
• $d = 23$, since $23 \times 7 = 161 = 160 + 1$.
• Public key $\{7, 187\}$, private key $\{23\}$.
• For $m = 88$: $c = 88^7 \bmod 187 = 11$, and $m = 11^{23} \bmod 187 = 88$.

RSA Digital Signature

Uses the same key pair as RSA encryption, with the roles of $e$ and $d$ reversed.

• With message recovery
  Applies when the message $m < n$ directly. Signature $\sigma = m^d \bmod n$, signed with the signer’s private key.
• Without message recovery
  Hashes the message first. Signature $\sigma = H(M)^d \bmod n$, sent as the pair $(M, \sigma)$.

Verification

• With recovery: compute $m' = \sigma^e \bmod n$ using the signer’s public key, and check it matches the expected message.
• Without recovery: compute $h' = H(M')$ and $h = \sigma^e \bmod n$, accept iff $h = h'$.

Signing cost is a hash plus a single exponentiation with a full-length exponent $d$. Verification cost is a hash plus a single exponentiation with the small exponent $e$, plus a comparison.