= RSA cryptosystem
{c}
{title2=$c=m^e\bmod N,\quad m=c^d\bmod N$}
{wiki}
= RSA
{c}
{synonym}
In the two-prime RSA cryptosystem, choose distinct odd <prime numbers> $p,q$, set $N=pq$, and choose an <integer> $1<e<\varphi(N)$ coprime to $\varphi(N)=(p-1)(q-1)$. A private exponent $d$ satisfies $ed\equiv1\pmod{\varphi(N)}$. The <public key> is $(N,e)$; the <private key> permits the inverse modular exponentiation. For a message representative $0\leq m<N$,
$$
c\equiv m^e\pmod N,\qquad m\equiv c^d\pmod N.
$$
Correctness holds even when $m$ is not coprime to $N$: modulo each <prime> the zero case is immediate, while the nonzero case follows from <Fermat's little theorem>; the <Chinese remainder theorem> recombines the two congruences.
For example, $p=5$, $q=11$, $e=3$ and $d=27$ give $ed\equiv1\pmod{40}$; $m=2$ encrypts to $c=8$ and decrypts back to $2$. These tiny parameters only illustrate the arithmetic. The raw deterministic exponentiation is textbook RSA; practical <encryption> uses an encoding scheme rather than encrypting an unencoded message directly.<Handbook of Applied Cryptography by Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone>[Chapter 8, section 8.2, Algorithms 8.1 and 8.3, with the correctness proof following Algorithm 8.3]{ref}
Back to article page