Rivest-Shamir-Adleman Algorithm

cryptography

Definition

Rivest-Shamir-Adleman Algorithm

The Rivest-Shamir-Adleman algorithm (RSA) is an asymmetric encryption scheme whose security relies on the hardness of the integer factorisation problem.

Algorithm

Let $N$ be the modulus consisting of two large prime numbers $p,q$, with:

• Public key $(e,N)$ where $e$ is the public exponent
• Private key $(d,N)$ where $d$ is the private exponent

Cryptographic Hardness

Security depends on the size $p,q$:

• Primes are typically between $1024$ and $2048$ bits long
  The larger, the better (but also slower)

Key Generation

Key Generation: Generate two large prime numbers $p,q$ and compute the modulus $N=p\cdot q$. Choose a public exponent $e<N$ coprime to $\phi (N)$. The private exponent $d$ is the multiplicative inverse of $e$ modulo $\phi (N)$:

• If the inverse exists, $ed\equiv 1(\mathrm{mod}\phi (N))$

• The extended Euclidean algorithm can be used for this purpose.

Speedup encryption, $e$ is typically a small number (e.g., $65537=2^{16}+1$).

To speed-up

Generation of Large Prime Numbers

1. Randomly generate an odd number of the desired bit length.
2. Test if small prime numbers (e.g. those smaller than 1000) divide the generated number.
3. Iterate the Miller-Rabin test on the generated number to ensure primality.

• If the test says that the number is not prime, the answer is always correct.
• If the test says that the number is prime, the answer might be wrong (probability $\le \frac{1}{4}$)
• Iterating the test $r$ times reduces the probability of mistakes to $(\frac{1}{4}{)}^r$.

Encryption Scheme

RSA can be used as an asymmetric encryption scheme. Encryption uses the public key; decryption uses the private key.

Encryption

Let $m<N$ be the plaintext and $c$ be the corresponding ciphertext, then:

$$c=\mathsf{Enc}(\underset{\text{public}}{\underbrace{(e,N)}},m)=m^e(\mathrm{mod}N)$$

Decryption

Let $m<N$ be the plaintext and $c$ be the corresponding ciphertext, then:

$$m=\mathsf{Dec}(\underset{\text{private}}{\underbrace{(d,N)}},c)=c^d(\mathrm{mod}N)$$

Signature Scheme

RSA can also be used as an asymmetric signature scheme. The roles of the keys are reversed compared to encryption.

Malleability

The malleability of RSA can be used to generate valid signatures for new messages from signatures of other messages. If $s_1=m_1^d\mathrm{mod}N$ and $s_2=m_2^d\mathrm{mod}N$ are valid signatures, then

$$s_1\cdot s_2\mathrm{mod}N=(m_1\cdot m_2{)}^d\mathrm{mod}N$$

is a valid signature for the message $m_1\cdot m_2$.

Furthermore, if the private key’s owner is willing to sign only some messages, an attacker can obtain arbitrary signatures. To sign a message $m$, the attacker chooses $r$ with $0<r<N$, asks for a signature $s^{\prime }$ on $m^{\prime }=m\cdot r^e\mathrm{mod}N$, and computes

$$s=s^{\prime }\cdot r^{-1}\mathrm{mod}N$$

This $s$ is a valid signature for $m$, since

$$s^e\equiv s^{\prime e}\cdot r^{-e}\equiv m^{\prime }\cdot r^{-e}\equiv m\cdot r^e\cdot r^{-e}\equiv m(\mathrm{mod}N)$$

Signing

Let $m<N$ be the message and $\sigma$ be the signature, then:

$$\sigma =\mathsf{Sign}(\underset{\text{private}}{\underbrace{(d,N)}},m)=m^d(\mathrm{mod}N)$$

Verification

Let $m<N$ be the message and $\sigma$ be the signature, then:

$$\mathsf{Verify}(\underset{\text{public}}{\underbrace{(e,N)}},m,\sigma )=\{\begin{array}{ll}1& \text{if }{\sigma }^e\equiv m(\mathrm{mod}N)\\ 0& \text{otherwise}\end{array}$$

Correctness

Theorem

For all positive integer messages $m<N$, it holds that

$$m^{ed}\equiv m(\mathrm{mod}N)$$

Proof

By construction of $d$, we have $ed=k\cdot \phi (N)+1$ for some $k\ge 0$. Then

$$m^{ed}\equiv m^{k\cdot \phi (N)+1}\equiv m\cdot (m^{\phi (N)}{)}^k(\mathrm{mod}N)$$

Case $\gcd (m,N)=1$: By Euler’s theorem, $m^{\phi (N)}\equiv 1(\mathrm{mod}N)$, so

$$m\cdot (m^{\phi (N)}{)}^k\equiv m\cdot 1^k\equiv m(\mathrm{mod}N)$$

Case $\gcd (m,N)>1$: Since $m<N=pq$, either $\gcd (m,N)=p$ or $\gcd (m,N)=q$. Assume $\gcd (m,N)=p$ (the other case is symmetric). Then $m=jp$ for some $j\ge 0$.

Since $\gcd (m,q)=1$, Euler’s theorem gives $m^{\phi (q)}\equiv 1(\mathrm{mod}q)$. Hence

$$m^{\phi (N)}=m^{\phi (p)\cdot \phi (q)}=(m^{\phi (q)}{)}^{\phi (p)}\equiv 1^{\phi (p)}\equiv 1(\mathrm{mod}q)$$

Therefore $m^{\phi (N)}=wq+1$ for some $w$, and

$$m\cdot (m^{\phi (N)}{)}^k\equiv m(wq+1)\equiv wq\cdot jp+m\equiv wj\cdot N+m\equiv m(\mathrm{mod}N)$$

Issues

Determinism

If the same message is encrypted multiple times with the same public key, the produced ciphertexts are the same. Textbook RSA is deterministic.

Small Messages and Public Exponents

Given a ciphertext $c=m^e\mathrm{mod}N$, it holds that $c+kN=m^e$ for some $k\ge 0$. When both $m$ and $e$ are small, $m^e$ is not much larger than $N$, and the plaintext can be reconstructed by brute-forcing the possible values of $k$ and computing the $e$\textsuperscript{th} root:

$$m=\sqrt[e]{c+kN}$$

Padding

The plaintext $m$ is extended with randomly generated components to bring it to the size of the modulus $N$. The padded plaintext is then encrypted as usual. Usage of padding prevents both previous attacks (determinism and small messages).

PKCS#1 v. 1.5

Simple, but vulnerabilities are known.

Definition

Optimal Asymmetric Encryption Padding

Optimal Asymmetric Encryption Padding (OAEP) is a padding algorithm for RSA encryption. It is recommended for new applications.

Link to original