# 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

- RSA is a reversible
public-key encryption scheme; RSA digital signatures make use of this.
- RSA is often used with randomization (salting with a random appendix)
to prevent chosen-plaintext and other attacks.
- RSA is very popular and hence is the most widely cryptanalysed PK
algorithm.

Back to Computer Security