# 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

• 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