Sending a Secret with RSA

Bob publishes n = pq and an exponent e. Alice encrypts her message m as mᵉ mod n, and only Bob, who knows p and q, can compute the private exponent d that undoes it. Pick small primes and watch a message scramble and come back.

How it works

Modular exponentiation and inverses

In one sentence

With $n = pq$ and $\varphi = (p - 1)(q - 1)$ , choose $e$ with $\gcd(e, \varphi) = 1$ and $d \equiv e^{-1} \pmod{\varphi}$ . Then $(m^e)^d \equiv m \pmod n$ for every $m$ , by Euler's theorem together with the Chinese remainder theorem.

General formula

{\htmlData{sym=0}{c}} = {\htmlData{sym=1}{m}}^{\htmlData{sym=2}{e}} \bmod {\htmlData{sym=3}{n}}, \qquad {\htmlData{sym=1}{m}} = {\htmlData{sym=0}{c}}^{\htmlData{sym=4}{d}} \bmod {\htmlData{sym=3}{n}}, \qquad {\htmlData{sym=4}{d}} = {\htmlData{sym=2}{e}}^{-1} \bmod ({\htmlData{sym=5}{p}}-1)({\htmlData{sym=6}{q}}-1)

Encryption and decryption are two exponents that multiply to one more than a multiple of φ, which mod n is the same as doing nothing.

What the symbols mean

$c$
Ciphertext
The encrypted number that gets sent.
$m$
Message
The plaintext, encoded as a number smaller than n.
$e$
Public exponent
Part of the public key.
$n$
Modulus
The public product of the two secret primes.
$d$
Private exponent
The secret key: the inverse of e modulo (p − 1)(q − 1).
$p$
First prime
Kept secret.
$q$
Second prime
Kept secret.

Bob picks primes $p$ and $q$ , publishes $n = pq$ and an exponent $e$ that shares no factor with $(p - 1)(q - 1)$ , and keeps $d = e^{-1} \bmod (p - 1)(q - 1)$ secret.
Alice turns her message into a number $m < n$ and sends $c = m^e \bmod n$ . Raising to a power mod $n$ scrambles $m$ beyond recognition.
Bob computes $c^d \bmod n$ . Because $ed = 1 + k(p - 1)(q - 1)$ , Euler's theorem gives $m^{ed} \equiv m \pmod n$ : the message comes back.
Real keys use primes hundreds of digits long, so n is far too big to factor and d stays secret; computers still encrypt quickly by repeated squaring.

Learn the math

The GCD and the Euclidean AlgorithmDiscrete · Lesson 25, Number Theory and Cryptography Modular ArithmeticDiscrete · Lesson 26, Number Theory and Cryptography Modular Inverses and the Chinese Remainder TheoremDiscrete · Lesson 27, Number Theory and Cryptography Public-Key Cryptography: RSADiscrete · Lesson 28, Number Theory and Cryptography

Learn the math

The GCD and the Euclidean AlgorithmDiscrete · Lesson 25, Number Theory and Cryptography

Modular ArithmeticDiscrete · Lesson 26, Number Theory and Cryptography

Modular Inverses and the Chinese Remainder TheoremDiscrete · Lesson 27, Number Theory and Cryptography

Public-Key Cryptography: RSADiscrete · Lesson 28, Number Theory and Cryptography