Public Key Construction and Theory
Contents
1. Constructing a Public/Private Key Pair (RSA)
- Pick two large primes \(p, q\). Compute: $$n = p \cdot q$$
$n$ is the modulus, part of both public and private keys.
Compute Euler’s totient
$$\varphi(n) = (p-1)(q-1)$$Choose a public exponent $e$
- Typically $65537$ (a prime, chosen for efficiency).
- Must satisfy: $$\gcd(e, \varphi(n)) = 1$$
Compute the private exponent $d$
$$d \cdot e \equiv 1 \pmod{\varphi(n)}$$Keys:
- public key: $(e, n)$
- private key: $(d, n)$
2. The Theory
Fermat’s Little Theorem
If $p$ is a prime and $gcd(a, p) = 1$, then:
$$a^{p-1} \equiv 1 \pmod p$$Euler’s Theorem (generalization)
If $gcd(a, n) = 1$, then:
$$a^{\varphi(n)} \equiv 1 \pmod{n}$$This extends Fermat’s theorem to any modulus $n$, using Euler’s totient function $\varphi(n)$.
Connection to RSA
Suppose message $m$ with $gcd(m, n) = 1$
Encryption
$$c = m^e \pmod{n}$$Decryption
$$m' = c^d \pmod{n}$$Since $d \cdot e \equiv 1 \pmod{\varphi(n)}$, or
$$d \cdot e = 1 + k\varphi(n)$$So:
$$m' = (m^e)^d \equiv m^{ed} \equiv m^{1 + k\varphi(n)} \pmod{n}$$By Euler’s Theorem:
$$m ^ {\varphi(n)} \equiv 1 \pmod n$$Thus:
$$m' \equiv m \pmod n$$