---
title: RSA
tags: crypto
lang: zh_tw
---

* [筆記總覽](https://hackmd.io/@LJP/rkerFdnqS)

[TOC]

# RSA
## 加解密
$m$: 明文
$c$: 密文

$$
c \equiv m^e\ mod\ n
$$
$$
m \equiv c^d\ mod\ n
$$

那如何生出 $e, d, n$ 呢?
請看下一章節

## Key Generation
1. 找兩個大質數 $p, q$
2. $n = p \times q$
3. $\phi(n) = (p-1)(q-1)$
4. 任意選取一個 $e \in \{2, 3, ..., \phi(n) - 1\}$，需滿足 $gcd(e, \phi(n)) = 1$
5. 計算 $d$ 滿足 $d \times e \equiv 1\ mod\ \phi(n)$

public key: $e, n$
private key: $d$

找大質數可以使用 [Miller-Rabin Test](https://hackmd.io/@LJP/ByqGC2UIK#Miller-Rabin-Test)

## Proof
那用以上方式產生出來的 key pair, 用以上的加解密方式, 真的能正確加解密嗎? 這裡就要試圖驗證這件事情

根據 [Fermat's Little Theorem](https://hackmd.io/@LJP/ry_Ei3L8Y)

$$
a^{p-1} \equiv 1\ (mod\ p)
$$

推廣一下

$$
a^{p-1} \times a^{p-1} \equiv 1\ (mod\ p)
$$

上面的式子是對的，因為

$$
\begin{split}&(a^{p-1} \times a^{p-1})\ mod\ p \\
&= (a^{p-1}\ mod\ p) \times (a^{p-1}\ mod\ p) \\
&= 1 \times 1\\
&= 1
\end{split}
$$

再推廣成

$$
a^{k(p-1)} \equiv 1\ (mod\ p)
$$

不管 $k$ 為多少都成立，推法都可以用上面的推法如法炮製

將 $k$ 配成 $k(q-1)$，變成

$$
a^{k(p-1)(q-1)} \equiv 1\ (mod\ p)
$$

那假設 $q$ 也是質數的話，其實也可以用前面的推導推出
$$
a^{k(p-1)(q-1)} \equiv 1\ (mod\ q)
$$

將 $a^{k(p-1)(q-1)}$ 替換為 $x$，前面兩個式子表示
$$
\begin{split}
x &\equiv 1\ (mod\ p)\\
x &\equiv 1\ (mod\ q)\\
\end{split}
$$

$$
\begin{split}
x &\equiv 1\ (mod\ p)\\
x &= pu + 1
\end{split}
$$

$$
\begin{split}
x &\equiv 1\ (mod\ q)\\
pu + 1 &\equiv 1\ (mod\ q)\\
pu &\equiv 0\ (mod\ q)\\
\end{split}
$$

這表示了 $u$ 能被 $q$ 整除($p$ 無法被 $q$ 整除)
將 $u$ 改成 $kq$

$$
\begin{split}
x &= kpq + 1\\
x &\equiv 1\ (mod\ pq)\\
x &\equiv 1\ (mod\ n)\\
a^{k(p-1)(q-1)} &\equiv 1\ (mod\ n)\\
a^{1+k(p-1)(q-1)} &\equiv a\ (mod\ n)\\
\end{split}
$$

以上式子先推導到這邊，現在回來看一下加解密的方式

$$
c \equiv m^e\ mod\ n
$$

$$
\begin{split}
m &\equiv c^d\ mod\ n \\
m &\equiv (m^e\ mod\ n)^d\ mod\ n \\
m &\equiv (m^e)^d\ mod\ n \\
m &\equiv m^{ed}\ mod\ n \\
\end{split}
$$

由於我們知道
$$
ed \equiv 1\ mod\ \phi(n)
$$

可以換成這樣的形式
$$
\begin{split}
ed &= 1 + k\phi(n)\\
&= 1 + k(p-1)(q-1)
\end{split}
$$

替換一下 $ed$

$$
\begin{split}
m &\equiv m^{ed}\ mod\ n \\
&\equiv m^{1 + k(p-1)(q-1)}\ mod\ n \\
\end{split}
$$

根據前面推導的 $a^{1+k(p-1)(q-1)} \equiv a\ (mod\ n)$
證明 $m \equiv c^d\ mod\ n$ 的正確性

## 安全性
RSA 的安全性觀察完 Key generation 後
在 Client 只會拿到 $e, n$ 的情況下
若 $n$ 被質因數分解出 $p, q$, 那 Client 就能算出 $d$, 那 RSA 就被破了

所以 RSA 的安全性建構在 **$n$ 很難被質因數分解** 的問題上

## 使用中國餘式定理加速解密
參考[這篇文章](https://www.di-mgt.com.au/crt_rsa.html)
在[中國餘式定理 CRT](https://hackmd.io/@LJP/B17an2I8t)中有舉一個例子:
> 舉個例子，若已知 $(a\ mod\ 7, a\ mod\ 5)$ 系統，求在 $(4, 3)$ 座標上的數字 $x$
>
這個例子中, 得到 $(4, 3)$ 就能高速反推在 $mod\ (7 \times 5)$ 中對應的 $x$

RSA 解密式是 $m \equiv c^d\ mod\ n$

若能先得到明文在 $(a\ mod\ p, a\ mod\ q)$ 系統的座標

就能高速反推在 $mod\ (p \times q)$ (就是 $mod\ n$)中對應的 $p$

實際算法分成兩部分

第一部分是 Server 可以先準備好的, 不用每次解密都重算一遍
$$
\begin{split}
d_p &\equiv e^{-1}\ (mod\ (p-1)) \\
d_q &\equiv e^{-1}\ (mod\ (q-1)) \\
q_{inv} &\equiv q^{-1}\ (mod\ p) \\
\end{split}
$$

第二部分才是每次解密要重算的部分
$$
\begin{split}
m_1 &\equiv c^{d_p}\ (mod\ p) \\
m_2 &\equiv c^{d_q}\ (mod\ q) \\
h &\equiv q_{inv}(m_1 - m_2)\ (mod\ p) \\
m &\equiv m_2 + hq \\
\end{split}
$$

### Proof
算出明文在 $(a\ mod\ p, a\ mod\ q)$ 系統的座標
也就是求
$$
\begin{split}
m &\equiv c^d\ (mod\ p) \\
m &\equiv c^d\ (mod\ q) \\
\end{split}
$$

而 $c^d\ (mod\ p)$ 可以推導一下
將 $d$ 改寫為 $k\phi(p) + d\ mod(\phi(p))$ (也就是 $d$ 除 $\phi(p)$ 的形式)

$$
\begin{split}
c^d &\equiv c^{k\phi(p) + d\ mod(\phi(p))}\ (mod\ p) \\
&\equiv (c^{\phi(p)})^k \times c^{d\ mod(\phi(p))}\ (mod\ p) \\
\end{split}
$$

因為 $p$ 是質數, 根據[Fermat’s Little Theorem](https://hackmd.io/@LJP/ry_Ei3L8Y)可得知
$c^{\phi(p)} \equiv c^{p-1} \equiv 1\ (mod\ p)$
所以上面的推導繼續變成

$$
\begin{split}
c^d &\equiv (c^{\phi(p)})^k \times c^{d\ mod(\phi(p))}\ (mod\ p) \\
&\equiv (1)^k \times c^{d\ mod(\phi(p))}\ (mod\ p) \\
&\equiv c^{d\ mod(\phi(p))}\ (mod\ p) \\
&\equiv c^{e^{-1}\ mod(p-1)}\ (mod\ p) \\
\end{split}
$$

讓我們回顧一下第一部分
$$
\begin{split}
d_p &\equiv e^{-1}\ (mod\ (p-1)) \\
d_q &\equiv e^{-1}\ (mod\ (q-1)) \\
q_{inv} &\equiv q^{-1}\ (mod\ p) \\
\end{split}
$$

展開一下第二部分第一行
$$
\begin{split}
m_1 &\equiv c^{d_p}\ (mod\ p) \\
&\equiv c^{e^{-1}\ (mod\ (p-1))}\ (mod\ p) \\
\end{split}
$$

發現其實這就是在求明文在 $mod\ p$ 這一軸的座標
同理, 第二部分第二行就是求明文在 $mod\ q$ 這一軸的座標
得到座標後就可反推出在 $mod\ (p \times q)$ 原本的數字是什麼, 也就是明文

## 攻擊手段
### Common Factor Attacks
參考[RSA Common Factor Attacks](https://blog.louie.lu/2017/09/30/rsa-common-factor-attacks/)
若挑選質數時不夠亂
假設第一次挑 $P, Q$ 分別挑到 $A, B$
算出了 $N_1 = AB$
第二次挑 $P, Q$ 挑到 $A, C$
算出了 $N_2 = AC$

求 $N_1, N_2$ 的公因數就會得到 $A$, 就破 RSA 了

### Mathematical Attacks
這個攻擊是走分解 $n$ 的路線

找到一組 $x, y$ 符合 $x^2 \equiv y^2\ (mod\ n)$
如此就找到 $x^2 - y^2 \equiv (x+y)(x-y) \equiv 0\ (mod\ n)$
等於 0, 表示 $n$ 能整除 $(x+y)(x-y)$
表示 $p \times q$ 能整除 $(x+y)(x-y)$

計算 $d = gcd(x-y, n)$

$d$ 只會有以下四種狀況
- $d = p$
表示 $p$ 能整除 $x-y$
且 $q$ 能整除 $x+y$
- $d = q$
表示 $q$ 能整除 $x-y$
且 $p$ 能整除 $x+y$
- $d = n$
表示 $p, q$ 皆能整除 $x-y$
- $d = 1$
表示 $p, q$ 皆不能整除 $x-y$
且 $p, q$ 皆能整除 $x+y$

如此就有二分之一的機率能夠分解 $n$

但要如何尋找 $x, y$ 呢
有幾種方式
- Continued Fraction
- Quadratic Sieve
- Number Field Sieve

#### Continued Fraction
TBD

#### Quadratic Sieve
TBD

#### Number Field Sieve
TBD

### Protocol Attacks
竄改密文 $c$, 在前面乘上 $s^e$
受害者解密時
$$
(s^ec)^d \equiv sm\ mod\ n
$$

### Fault-injection Attacks
TBD

### Pollard's p – 1 Attack
參考 [Mathematical attack on RSA ](https://www.nku.edu/~christensen/Mathematical%20attack%20on%20RSA.pdf)

以下講解原理

若有一個數字 $r$ 使得 $r!$ 能被 $p-1$ 整除
那麼可以說 $r! = (p-1)j$
此時任選一個 $a, 1 < a < p-1$
因為 [Fermat’s Little Theorem](https://hackmd.io/@LJP/ry_Ei3L8Y) 所以下面式子正確
$a^{r!} \equiv a^{(p-1)j} \equiv 1\ mod\ p$
$a^{r!} - 1 \equiv 0\ mod\ p$
以上說明 $a^{r!} - 1$ 能被 $p$ 整除
而 $n = pq$ 也能被 $p$ 整除
所以 $gcd(a^{r!}-1,n) = p$
就分解 $n$ 了

若 $p-1$ 或 $q-1$ 的最大質因數過小會導致此攻擊成功

### Low Public Exponent Attack
參考 [Rsa e attack](https://wiki.x10sec.org/crypto/asymmetric/rsa/rsa_e_attack/)
若 e 選的小, 例如說 3

因為加密方式是
$c \equiv m^3\ mod\ n$
所以
$m^3 = k \times n + c$

只要對 $k \times n + c$ 開三次根就能解出 $m$

實際攻擊時 $k$ 可以暴力枚舉, 直到解出整數, 則此整數就是 $m$

### Broadcast Attack
若知道同個 $m$ 用 $e$ 個不同的 $n$ 加密的 $c$
用[中國餘式定理](https://hackmd.io/@LJP/B17an2I8t) 可以直接推回 $m$

以 $e = 3$ 為例

$m^3 \equiv c_1\ mod\ n_1$
$m^3 \equiv c_2\ mod\ n_2$
$m^3 \equiv c_3\ mod\ n_3$

用 CRT 推得 $c$
$m^3 \equiv c\ mod\ n_1n_2n_3$

因為 $m^3 < n_1n_2n_3$, 所以上式可得知 $m^3 = c$
直接對 $c$ 開三次方根就能得到明文

以上在只知道 $c_1, c_2, c_3$ 與 3 組公鑰的條件下解 $m$

### Wiener Attack
若選的 $d$ 小於 $\frac{1}{3}n^{\frac{1}{4}}$ 則以下成立
$$
\vert(\frac{e}{n} - \frac{k}{d})\vert < \frac{1}{2d^2}
$$

$\frac{k}{d}$ 會出現在 $\frac{e}{n}$ 的收斂連分數中

### LSB Oracle Attack
假設有一個解密機器叫做 Oracle
給他密文 $c$ 他會 return 明文的最後一 bit
怎麼解回對應 $c$ 的整個明文 $m$

給 Oracle 吃 $2^ec$
解密時
$$
(2^ec)^d \equiv 2m\ mod\ n
$$

若 $m$ 低於 $\frac{1}{2}n$, 則 $2m$ 低於 $n$
此時 $(2^ec)^d$ 對應的解密結果會是 $2m$
return 的最後一 bit 必為 0, 因為乘 2 了嘛

若 $m$ 高於 $\frac{1}{2}n$, 則 $2m$ 高於 $n$
此時 $(2^ec)^d$ 對應的解密結果會是 $2m - n$, 因為 $mod\ n$ 嘛, 超過 $n$ 就減 $n$
因為 $2m$ 一定是偶數, $n$ 為兩個奇數相乘所以也必為奇數, 偶數減掉奇數一定是奇數
return 的最後一 bit 必為 1

所以給 $(2^ec)^d \equiv 2m\ mod\ n$ 看 return 的 LSB
就能初步確定 $m$ 的範圍
return 0: $m$ 低於 $\frac{1}{2}n$
return 1: $m$ 高於 $\frac{1}{2}n$

繼續餵 Oracle 吃 $4^ec$
解密時
$(4^ec)^d \equiv 4m\ mod\ n$
return 0: $m$ 低於 $\frac{1}{4}n$
return 1: $m$ 高於 $\frac{1}{4}n$

以下類推

總之這就是用這種方式進行類似二分搜索的攻擊

更進一步, 假設回傳 4 bits LSB
傳送 $16^ec$, 則解密時
$$
(16^ec)^d \equiv 16m\ mod\ n
$$

:hankey: 假設回傳 0
若 server 回傳 0 (0b0000), 則表示
$$
(16m\ mod\ n)mod\ 16 \equiv 0
$$

$$
16m - kn \equiv 0\ mod\ 16
$$

☆ 推導 k 的範圍
因為 $n=pq$ 無法被 16 整除, 要滿足上式則 $k$ 一定得為 16 的倍數, 這邊改寫
$$
16m = kn + (16m\ mod\ n)
$$

$$
16m = 16un + (16m\ mod\ n)
$$

★ 推導 m 的範圍
$$
0 < m < \frac{n}{16}
$$

因為

$$
0 < 16m < n
$$

$$
16m\ mod\ n = 16m
$$

$$
16m\ mod\ 16 = 0
$$

若 $\frac{n}{16} < m < \frac{2n}{16}$, 則
$$
n < 16m < 2n
$$

$$
16m\ mod\ n = 16m - n
$$

$$
16m - n\ mod\ 16 \neq 0
$$

所以論證不能是 $\frac{n}{16} < m < \frac{2n}{16}$ 這個範圍

同樣的方式能論證 $\frac{2n}{16} < m < \frac{3n}{16}$ ... $\frac{15n}{16} < m < n$ 皆不可能

:hankey: 假設回傳 1
若 server 回傳 1 (0b0001), 則表示
$$
(16m\ mod\ n)mod\ 16 \equiv 1
$$

$$
16m - kn \equiv 1\ mod\ 16
$$

$$
16m \equiv kn + 1\ mod\ 16
$$

$$
0 \equiv kn + 1\ mod\ 16
$$

☆ 推導 k 的範圍
$$
kn + 1 = 16u
$$

$$
kn = 16u - 1
$$

$$
k = \frac{16u - 1}{n}
$$

★ 推導 m 的範圍
$$
\frac{n}{16} < m < \frac{2n}{16}
$$

因為

$$
n < 16m < 2n
$$

$$
16m\ mod\ n = 16m - n
$$

$$
(16m - n)\ mod\ 16 = 1
$$

而 $n\ mod\ 16 = 1$, 所以 $n = 16i + 1$
$$
(16m - 16i + 1)\ mod\ 16 = 1
$$

若 $\frac{2n}{16} < m < \frac{3n}{16}$, 則
$$
2n < 16m < 3n
$$

$$
16m\ mod\ n = 16m - 2n
$$

$$
16m - 2n\ mod\ 16 \neq 1
$$

$$
(16m - 2(16i + 1))\ mod\ 16 = 1
$$

$$
(16m - 32i + 2))\ mod\ 16 \neq 1
$$

所以論證不能是 $\frac{2n}{16} < m < \frac{3n}{16}$ 這個範圍

同樣的方式能論證 $\frac{3n}{16} < m < \frac{4n}{16}$ ... $\frac{15n}{16} < m < n$ 皆不可能
以及 $0 < m < \frac{n}{16}$ 也不可能

:hankey: 小結論
回傳 x, 則表示 $\frac{xn}{16} < m < \frac{(x+1)n}{16}$

:fishing_pole_and_fish: 假設第一次回傳 0
第二步根據上次送的再乘一次 $16^e$, 則解密時
$(16^{2e}c)^d \equiv 16^2m\ mod\ n$

由第一次配上前面的推導, 已經知道 $0 < m < \frac{n}{16}$
$(16^2m\ mod\ n)mod\ 16 \equiv 0$
因為 $0 < 16m < n$, 所以 $16m\ mod\ n = 16m$
乘上一個 16 後, 16m 的可能範圍又回到 $0 < 16m < n$
這次再乘上 16 後根據回傳的值 x 又能說 $\frac{xn}{16} < 16m < \frac{(x+1)n}{16}$
再除回去 $\frac{xn}{16^2} < m < \frac{(x+1)n}{16^2}$
配上 $\frac{xn}{16} < m < \frac{(x+1)n}{16}$
交集出 $m$ 的範圍

### Bleichenbacher 1998 Attack (BB98)
TBD