RSA cryptosystem

Example

The RSA cryptosystem is an example of public-key cryptography. To make the keys, choose two distinct primes $p$ and $q$, and put $n = pq$ and $\varphi(n) = (p - 1)(q - 1)$, the value of Euler's totient function. Choose an integer $e$ with $1 < e < \varphi(n)$ and $\gcd(e, \varphi(n)) = 1$. Let $d$ be the inverse of $e$ modulo $\varphi(n)$. The public key is $(n, e)$, and the private key is $d$. To encrypt a message $m$ with $0 \le m < n$, compute $c = m^e \bmod n$. To decrypt, compute $c^d \bmod n$, which is equal to $m$. A small case: $p = 5$, $q = 11$, $n = 55$, $\varphi(n) = 40$, $e = 3$ and $d = 27$, since $3 \cdot 27 = 81 \equiv 1 \pmod{40}$. The message $m = 2$ gives $c = 2^3 = 8$, and $8^{27} \equiv 2 \pmod{55}$.

Remarks

Decryption works by Euler's theorem: $ed = 1 + k \varphi(n)$, so $m^{ed} \equiv m \pmod n$ when $\gcd(m, n) = 1$. The general case follows from the Chinese remainder theorem. The security rests on the belief that it is hard to factor $n$ when $p$ and $q$ are large. Ron Rivest, Adi Shamir and Leonard Adleman described the system publicly in 1977.

Explanations

L1 human

Anyone can raise a message to the power $e$ modulo $n$. To undo this, you need $d$, and to find $d$ you need the factors of $n$. Multiplying two large primes is easy, but recovering them from the product is believed to be very hard.