RSA

RSA is a public key cryptosystem based on the fact that multiplying large primes is easy, while factoring their product is hard.

Key Generation

Choose distinct large primes $p$ and $q$ , and let

n = pq

Then

ϕ (n) = (p - 1) (q - 1)

Choose an integer $e$ such that

g cd (e, ϕ (n)) = 1

and choose $d$ so that

e d \equiv 1 (mod ϕ (n))

The public key is $(n, e)$ and the private key is $d$ .

If the plaintext is an integer $m$ with $0 \leq m < n$ , then the ciphertext is

c \equiv m^{e} (mod n)

These modular powers are computed efficiently using Binary Exponentiation.

To decrypt, compute

m \equiv c^{d} (mod n)

Since $e d \equiv 1 (mod ϕ (n))$ , there is some integer $k$ such that

e d = 1 + k ϕ (n)

If $g cd (m, n) = 1$ , then Euler’s theorem gives

m^{ϕ (n)} \equiv 1 (mod n)

m^{e d} = m^{1 + k ϕ (n)} = m (m^{ϕ (n)})^{k} \equiv m (mod n)

The security idea is that the public key reveals $n = pq$ , but recovering $ϕ (n)$ or $d$ requires factoring $n$ into $p$ and $q$ .