The RSA Algorithm

The keys

Both parts of an RSA key-pair are transmitted with a product $n$ of two large, distinct, random, secret primes $p$ and $q$. This $n = pq$ is called the modulus.

The public key consists of a random integer $e$ with $1 < e < \phi\left(n\right)$

Note that $\phi\left(n\right) = \left(p-1\right)\left(q-1\right)$ and the public key will be transmitted as $(n, e)$.

The private key $d$ is $e^{-1}$, or the unique integer such that $ed \equiv 1\ (mod\ \phi\left(n\right))$.

$d$ is generally calculated with the Extended Euclidean Algorithm (which you don't need to know)

Encryption and Decryption

Encrypting a message $m$ is done by calculating $m^e\ mod\ n$ (for which we have relatively quick algorithms).

A cipher text $c$ is decrypted as $c^d\ mod\ n$.

The message and cipher space $M=C=\{0,...,n-1\}$.

Explanation

This works as $$c^d = \left(m^e\right)^d \equiv m^{ed}$$ $$ed=1+k\phi\left(n\right)$$ $$m^{ed}\equiv m^{1+k\phi\left(n\right)} \equiv mm^{k\phi\left(n\right)} \equiv m\ \left(mode\ n\right)$$

This works because of Fermat's Theorem

Remarks

Back to Computer Security