RSA

Background

Coprime

Integers $a$ and $b$ are said to be coprime if $gcd(a,b)=1$

Fermat’s Little Theorem

Suppose $p$ is prime and $a$ is any integer Then $a^p\equiv a(\mathrm{mod}p)$

Euler’s Totient Function

Let $\phi (n)$ equal the number of positive integers less than n that are coprime to n Suppose $n=pq$ for some primes $p$ and $q$ Then $\phi (n)=\phi (pq)=(p-1)(q-1)$

Euler’s Theorem

Suppose $a$ and $n$ are coprime positive integers Then $a^{\phi (n)}\equiv 1(\mathrm{mod}n)$

Textbook Definition

Suppose two parties, Alice and Bob, wish to communicate securely. Bob wants to send an encrypted message to Alice without exchanging a shared private key.

1. Key Generation

1. Alice and Bob agree on suitable parameters (i.e. size of the modulus and public exponent)
2. Alice chooses two distinct and large primes, $p$ and $q$, with a large difference between the two
3. She compute the modulus $n=pq$
4. She then computes Euler’s totient function, $\phi (n)=(p-1)(q-1)$
5. With public exponent $e$ such that $gcd(e,\phi (n))=1$, Alice publishes the pair $(n,e)$

3. Encryption

1. Bob encrypts message $m$ into ciphertext $c$ like so: $c=m^e(\mathrm{mod}n)$
2. Bob sends $c$ to Alice

4. Decryption

1. Alice computes the private key, $d$, as $d=e^{-1}(\mathrm{mod}\phi (n))$
   1. By the difficulty of integer factorization, Alice is the only one who knows $\phi (n)$ and is therefore the only one who can compute $d$
2. She then computes $m=c^d(\mathrm{mod}n)$ to recover Bob’s message

Attacks on Textbook RSA

1. Low Public Exponent

For small $e$, the plaintext is trivially recovered by computing the $e$th root of $c$ like as $c^{\frac{1}{e}}=(m^e{)}^{\frac{1}{e}}=m$.

2. Non-Coprime Moduli

If the same message $m$ is encrypted twice as $c_1=m^e(\mathrm{mod}{n}_1)$ and $c_2=m^e(\mathrm{mod}{n}_2)$ where $gcd(n_1,n_2)\ne 1$, then either $n_1$ or $n_2$ can be factored easily by computing $p=gcd(n_1,n_2)$ and $q=\lfloor \frac{n_1}{p}\rfloor$. $m$ can be recovered by recomputing $d$ given $p$ and $q$.

3. Håstad’s Broadcast

If the same message $m$ is encrypted using the same $e$ but a different modulus $n_i\in \{n_1,\dots ,n_k\}$, $e$ ciphertexts are needed to recover $m$.

Suppose an eavesdropper Eve intercepts $\{c_1,\dots ,c_e\}$ where each $c_i\equiv m^e(\mathrm{mod}{n}_i)$. By the Chinese Remainder Thereom (CRT), Eve may compute $c\equiv c_i(\mathrm{mod}{n}_i)$, followed by $c\equiv m^e(\mathrm{mod}{n}_1\dots n_k)$. However, since $m<n_i\forall i$, then $c=m^e$. $m$ can thus be recovered in the same manner as the low public exponent attack.

4. Common Modulus

If the same message $m$ is encrypted using a different $e$ but the same modulus $n$, only 2 ciphertexts are needed to recover $m$ if (1) $gcd(e_1,e_2)=1$, and (2) $gcd(c_2,n)=1$.

Suppose an eavesdropper Eve intercepts $c_1,c_2$ where $c_1=m^{e_1}(\mathrm{mod}n)$ and $c_2=m^{e_2}(\mathrm{mod}n)$, and knows each $(n,e_1)$ and $(n,e_2)$ since they are public information.

First, by Bézout’s identity, Eve knows there exist integers $x$ and $y$ such that $e_{1}x+e_{2}y=1$. She solves for $x$ and $y$ using the Extended Euclidean algorithm:

1. Solving for $x$: Let $y=1$ and invert $e_1$ under $\mathrm{mod}{e}_2$
   1. $e_{1}x+e_{2}y=e_{1}x+e_2=1$
   2. Since $gcd(e1,e2)=1$, $x=e_1^{-1}(\mathrm{mod}{e}_2)$
2. Solve for $y$: Since $e_1$ and $e_2$ are known, reorder
   1. $e_{1}x+e_{2}y=1\leftrightarrow y=\frac{1-e_{1}x}{e_2}$

Second, given $x$ and $y$, she recovers $m$ like so:

1. $c_1^x\cdot c_2^y\mathrm{mod}n=(m^{e_1}{)}^x\cdot (m^{e_2}{)}^y$
2. $(m^{e_1}{)}^x\cdot (m^{e_2}{)}^y=m^{e_{1}x}\cdot m^{e_{2}y}\mathrm{mod}n$
3. $m^{e_{1}x}\cdot m^{e_{2}y}\mathrm{mod}n=m^{e_{1}x+e_{2}y}\mathrm{mod}n$
4. $m^{e_{1}x+e_{2}y}\mathrm{mod}n=m^1\mathrm{mod}n$ (by Bézout’s identity)
5. $m^1\mathrm{mod}n=m\mathrm{mod}n$

However, as $y$ will be negative (given $e_{1}x>1$ and $y$‘s numerator computes $1-e_{1}x$), it will have to be applied to $c_2$‘s inverse, $c_2^{-1}$.

Thus, to recover $m$, Eve computes $c_1^x\cdot (c_2^{-1}{)}^y\mathrm{mod}n$ using public information.

5. Chosen Ciphertext Attack

Let $Enc(m)$ denote $c=m^e(\mathrm{mod}n)$ for illustrative purposes.

RSA is partially-homomorphic: for two messages $m_1$ and $m_2$,

1. $Enc(m_1)\cdot Enc(m_2)=m_1^e(\mathrm{mod}n)\cdot m_2^e(\mathrm{mod}n)$
2. $m_1^e(\mathrm{mod}n)\cdot m_2^e(\mathrm{mod}n)=m_1^e\cdot m_2^e(\mathrm{mod}n)$
3. $m_1^e\cdot m_2^e(\mathrm{mod}n)=(m_1\cdot m_2{)}^e(\mathrm{mod}n)$
4. $(m_1\cdot m_2{)}^e(\mathrm{mod}n)=Enc(m_1\cdot m_2)$

So, the product of two ciphertexts is equal to the encryption of the product of the respective plaintexts.

Suppose an attacker is given a ciphertext, $c=m^e(\mathrm{mod}n)$ and a decryption oracle that will decrypt anything except $c$. If the attacker were to supply $c^{\prime }=c\cdot k$ for some arbitrary integer $k$ to the oracle, it would happily decrypt $c^{\prime }$ since $c^{\prime }\ne c$. However, since the attacker chose $k$, they can recover $m$ by simply computing $m=\frac{c^{\prime }}{k}$.