Public Key Cryptography and RSA

Public key cryptography (PKC) uses a key pair, a public key and a private key, rather than a single shared secret key. It is based on Number Theory, not substitution-permutation networks, and is asymmetric.

Motivation

• Key distribution
  Symmetric cryptography requires either a pre-shared key or a trusted key distribution center (KDC), which must itself be trusted with confidentiality.
• Digital signatures
  Electronic documents need a signature scheme that is easy to sign and verify, but difficult to forge, with universal verifiability.

PKC Framework

A key pair’s public key is known to everyone. The private key is known only to its owner. Given the public key and the algorithm, it is computationally infeasible to derive the private key.

• Confidentiality
  Sender encrypts with the receiver’s public key. Only the receiver, holding the private key, can decrypt.
• Authentication
  Signer encrypts a fingerprint (authenticator) of the message with their private key. Anyone can verify it using the signer’s public key. The authenticator must be infeasible to forge without changing the message.

Groups Over Finite Sets

Number-theoretic PKC computes over finite groups, since infinite groups ($\mathbb{Q}, \mathbb{Z}, \mathbb{R}$) are unusable for computation.

• $\mathbb{Z}_n$
  The group of integers modulo $n$: $\{0, 1, \dots, n-1\}$.
• $\mathbb{Z}_n^*$
  The subgroup of $\mathbb{Z}_n$ relatively prime to $n$, excluding 0 by convention.

If $n$ is prime, every nonzero element of $\mathbb{Z}_n$ is coprime to $n$, so $\mathbb{Z}_n^* = \{1, \dots, n-1\}$.

The order of a group is its number of elements. $|\mathbb{Z}_n| = n$, and for prime $p$, $|\mathbb{Z}_p| = p$.

Example: $\mathbb{Z}_{10}^* = \{1, 3, 7, 9\}$, removing multiples of the prime factors 2 and 5 from $\mathbb{Z}_{10}$.

Euler’s Totient Function

$\phi(n)$: the number of positive integers less than $n$ relatively prime to $n$.

• $\phi(p) = p - 1$ for prime $p$.
• $\phi(pq) = \phi(p)\phi(q) = (p-1)(q-1)$ for distinct primes $p, q$.

Fermat’s Theorem

For prime $p$ and integer $a$ not divisible by $p$:

Euler’s Theorem

Generalizes Fermat’s theorem to any modulus. For $a, n$ relatively prime:

For $n = pq$ (distinct primes) and $0 < m < n$:

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.