RSA

RSA is a public-key encryption and signature system and makes use of large prime numbers. The asymmetry is based on the fact that computing a product is fast, but factoring takes much longer.

Operation

The RSA algorithm involves the steps key generation, encryption and decryption. It can also be used for cryptographic signatures.

Key generation

The first step to setup an RSA system, is to generate the public and the private key. This is done in the following way:

1. Pick two distinct prime numbers $p$ and $q$ with bit-length $\lambda$.
2. Compute $n = p \cdot q$, this will be part of both the public and the private key.
3. Compute $\varphi(n) = (p - 1)(q - 1)$, where $\varphi$ is Euler’s totient function.
4. Choose an interger $e$ such that $1 < e < \varphi(n)$ and $\gcd(e, \varphi(n)) = 1$ (this means that $e$ and $\varphi(n)$ must be coprime). This will be part of the public key.
5. Compute $d$ as the modular inverse of $e$, so $d \equiv e^{-1} \pmod{\varphi(n)}$. For example by using Euler’s theorem. This will be part of the private key.
6. This results in:
   • Public key: $(e, n)$
   • Private key $(d, n)$

Encryption

To encrypt a message $m$, where $0 \le m < n$, perform the following computation:

$$c \equiv m^e \pmod{n}$$

Where $e$ is the public key and $c$ is the resulting ciphertext.

Decryption

To decrypt ciphertext $c$ with the private key $d$, perform the following computation:

$$c^d \equiv m \pmod{n}$$

Signatures

To sign a message $m$, compute the hash of $m$ and sign it with the private key $d$:

$$s \equiv \left( H(m) \right)^d \pmod{n}$$

To verify the signature $s$ for the message $m$, use the public key to check that:

$$H(m) \equiv s^e \pmod{n}$$

RSA is exceptional in the fact that signing is the inverse of the encryption.

Remarks

Don’t use this schoolbook version RSA in practice, it has too much mathematical structure which gives it certain vulnerabilities. An example is the fact that this version of RSA is homomorphic, so two ciphertexts can be concatenated into a valid single ciphertext.

$$(m_1)^e \cdot (m_2)^e = (m_1 \cdot m_2)^e$$

This can be used as an attack vector, so in practice some padding is used like Optimal Asymmetric Encryption Padding (OAEP).

Optimizations

For efficiency many popular crypto libraries use the following optimization for decryption and signing based on the Chinese remainder theorem. The following values are precomputed and stored as part of the private key:

• The primes from the key generation $p$ and $q$.
• The value $d_p \equiv d \pmod{p - 1}$
• The value $d_q \equiv d \pmod{q - 1}$
• The inverse of one of the primes mod the other prime: $u \equiv p^{-1} \pmod{q}$

Instead of computing $m \equiv c^d \pmod{p\cdot q}$, the ciphertext $c$ can then by decryption by computing

$$\begin{aligned} m_p &\equiv c^{d_p} \pmod{p} \\ m_q &\equiv c^{d_q} \pmod{q} \\ m &\equiv m_p + p \cdot u \cdot (m_q - m_p) \pmod {p \cdot q} \end{aligned}$$