RSA encryption and decryption

How it works

RSA works in the integers modulo $N = pq$, a product of two large primes. The public exponent $e$ must be coprime to $\varphi(N) = (p-1)(q-1)$, and the private exponent is its inverse, $d \equiv e^{-1} \pmod{\varphi(N)}$, found with the extended Euclidean algorithm. Encryption is $c = m^e \bmod N$ and decryption is $m = c^d \bmod N$: since $ed = 1 + k\varphi(N)$, Euler’s theorem gives $m^{ed} \equiv m$ (and this holds for every $m$, also those sharing a factor with $N$).

Both exponentiations use square and multiply, so they take a number of steps proportional to the bit length of the exponent, not to its size. Decryption is usually done modulo $p$ and $q$ separately with the reduced exponents $d_p = d \bmod (p-1)$ and $d_q = d \bmod (q-1)$, and the two halves are recombined with $q^{-1} \bmod p$ (Garner’s form of the Chinese remainder theorem). This is about four times faster.

Anyone who can factor $N$ can compute $\varphi(N)$ and then $d$, so the security rests on the hardness of factoring (more precisely, of taking $e$-th roots modulo $N$). Textbook RSA as shown here is deterministic and malleable ($c_1 c_2$ decrypts to $m_1 m_2$), so it is not secure on its own: real systems pad the message randomly (RSA-OAEP) and use $N$ of at least 2048 bits.