# RSA 總整理
RSA 是一個著名的非對稱式加密系統，其安全性建立在大數分解的難度上
目前 RSA 僅能透過旁通道攻擊(Side-Channel Attack)
---
<center>
<strong><font size=5> RSA 基本內容 </font></strong>
</center>
</br>
接下來我們需要先介紹 RSA 所需的數學知識
#### 尤拉函數 Eular Function
我們會以 $\phi$ (念作 phi) 表示尤拉函數
定義 $\phi(p)$ 為在所有的正整數當中，有多少 $< p$ 的數字與 $p$ 互質的數字
在這個定義之下，如果說 $p$ 是一個質數的話，那麼所有 $< p$ 的正整數也必定與之互質，因此此時的 $\phi(p) = p-1$
這也就是費馬小定理
在 RSA 當中，我們會取兩個質數 $p, q$，並計算 $n = p \times q$
此時的 $\phi(n) = \phi(p) \times \phi(q) = (p-1) \times (q-1)$
#### 模反元素 Modular Inverse
一個整數 $a$ 在模(mod) $n$ 的模反元素是指能滿足以下式子的整數 $b$
$$
a^{-1} \equiv b\ (mod\ n)
$$
或是表示成
$$
ab \equiv 1\ (mod\ n)
$$
:::info
就如同要找到一個數 $a$ 的乘法反元素，等同找到一個數字 $b$ 滿足
$$
ab = 1
$$
此時的 $b = \frac{1}{a}$，也就是我們常見的倒數
:::
在 RSA 當中，我們會去找某個數字 $e$ 在模(mod) $\phi(n)$ 下的模反元素 $d$
$$
\begin{align*}
& e^{-1} \equiv d\ (mod\ \phi(n))\\
\rightarrow \ & ed \equiv 1\ (mod\ \phi(n))\\
\rightarrow \ & ed\ mod\ \phi(n) = 1
\end{align*}
$$
:::info
$$
e^{-1} \neq \frac{1}{e}
$$
由於是在模底下運作，這個是不成立的!
:::
這裡還有一個重要的性質
$$
gcd(e, \phi(n)) = 1
$$
因為唯有這個條件成立，才會存在模反元素 $d$
:::success
如果不知道為什麼，不妨舉幾個數字來試試看，例如
- $e = 2$ 且 $\phi(n) = 4$
- $e = 6$ 且 $\phi(n) = 8$
會發現到無論如何都不會找到解，這裡先不寫證明
:::
在 python 當中要求模反元素，可以使用 python 的 modules 輕鬆達成
- gmpy2
```python=
>>> from gmpy2 import invert
>>> invert(3, 7)
mpz(5)
```
- PyCryptodome
```python=
>>> from Crypto.Util.number import inverse
>>> inverse(3, 7)
5
```
---
### RSA Encryption
在 RSA 當中有幾個常用的符號
| 符號 | 意義 |
| ---- | -------- |
| $m$ | 明文 |
| $c$ | 密文 |
| $e$ | 加密指數 |
| $d$ | 解密指數 |
| $n$ | 模數 |
RSA 加密的流程如下:
1. 找兩個質數 $p, q$，並令 $n = p \times q$
需要符合以下條件才能保證其安全性
- $n > m$
- $2q > p > q$
2. 選一個加密指數 $e$，使得 $gcd(e, \phi(n)) = 1$
3. $c = m^e\ mod\ n$
### RSA Decryption
RSA 解密流程如下
1. 嘗試將 $n$ 分解出兩質數 $p, q$
2. 計算 $\phi(n) = (p-1) \times (q-1)$
3. 找出解密指數 $d$ 使得 $ed \equiv 1\ (mod\ \phi(n))$
4. $m = c^d\ mod\ n$
第一步的分解可以透過下列的工具協助
- [factordb](http://www.factordb.com/)
- [alpetron](https://www.alpertron.com.ar/ECM.HTM)
- yafu
- SageMath
:::success
<center>
<strong>驗證 RSA 解密的正確性</strong>
</center>
> 證明 $m = c^d \% n$
已知 $m < n$
要證明 $m = c^d \% n$ 等同於證明 $c^d \% n - m = 0$
</br>
$$
\begin{align*}
c^d \% n - m &= 0\\
&= (m^e \ \% \ n)^d \ \% \ n - m \quad \quad \quad (c = m^e \ \% \ n)\\
&= m^{ed} \ \% \ n - m\\
&= m^{k(p-1)(q-1)+1} \ \% \ n - m \quad \quad (ed \equiv 1\ mod\ \phi(n) \Rightarrow ed = k\phi(n) + 1, k \in \mathbb{R})\\
&= m(m^{k(p-1)(q-1)} - 1) \ \% \ n
\end{align*}
$$
</br>
根據費馬小定理可知
$a^{p-1} \equiv 1\ (mod\ p) \quad$ ($p$ 為質數)
$$
\begin{align*}
&\Rightarrow (m^{k(p-1)})^{q-1} \equiv 1\ (mod\ q)\\
&\Rightarrow (m^{k(q-1)})^{p-1} \equiv 1\ (mod\ p)\\
&\Rightarrow m^{k(p-1)(q-1)} \equiv 1\ \ (mod\ pq)\\
&\Rightarrow m^{k(p-1)(q-1)} \equiv 1\ \ (mod\ n)
\end{align*}
$$
因此
$m(m^{k(p-1)(q-1)} - 1) \% n\\
= m(1 - 1) \% n = 0 \quad \blacksquare$
:::
### Convert
要做 RSA encryption 運算必須要是一串數字
做完 RSA decryption 後會得到的是一串數字
因此我們須要有可以將字串跟數字之間做轉換的工具，以下使用 pyCryptodome
- 字串轉為數字
```python=
>>> from Crypto.Util.number import long_to_bytes
>>> long_to_bytes(1567694910997846802713134265455563233695200125)
b'FLAG{long_to_bytes}'
```
- 數字轉為字串
```python=
>>> from Crypto.Util.number import bytes_to_long
>>> bytes_to_long(b'FLAG{bytes_to_long}')
1567694910997644772753309158996360910989059965
```
---
### 範例題目
```
n = 641038552669922004650640356715638051098436533497923620822471
e = 65537
c = 537756663490573782815200170116248828935623440674192611059116
```
透過 RSA decryption 的公式 $m = c^d\ mod(n)$ 可以知道我們還缺 $d$ ，而 $d$ 為 $e$ 在模 $\phi(n)$ 下的模反元素
先求 $\phi(n)$
因為這題的 $n$ 還不大，可以透過上述的工具先做分解，可以得到
- $p = 670839939121655241517135431571$
- $q = 955576010440355093873649387901$
則 $\phi(n) = (p-1) \times (q-1)$
$d$ 就可以透過 $e, \phi(n)$ 計算出來
**sol.py**
```python=
#!/usr/bin/python3
from Crypto.Util.number import *
n = 641038552669922004650640356715638051098436533497923620822471
e = 65537
c = 537756663490573782815200170116248828935623440674192611059116
p = 670839939121655241517135431571
q = 955576010440355093873649387901
phi = (q - 1) * (p - 1)
d = inverse(e , phi)
print(long_to_bytes(pow(c , d , n)))
```
---
<center>
<strong><font size=5> RSA Side-Channels </font></strong>
</center>
## RSA Little e
當 $n$ 過大且 $e$ 過小使得 $m^{e} < n$，此時只要對 $c$ 開 $e$ 次方根就可以得到 $m$
先看一下 RSA encryption
$$
c = m^e \% n
$$
如果 $m^e < n$，就意味著 $\% n$ 這個操作根本沒做
也就是說 $c = m^e$，倒過來說
$$
m = \sqrt[e]{c}
$$
---
### 範例題目
```
n = 5489682192316422625434821656898117285064026279334711820823698107520079986854633408581065889926979914843916643565952889381426707291132831900665471049142135375628581051708437366655536056332623163988398065066438737021804605433412757434719710964824708642384163317493038636229777958794272501125366402189914988842955471879476018505743333
e = 5
c = 8695825648499005816846784896009806853240301482143432878264036921549622676046441329661491555770611113772567007417487958975920139817671636465013430373715241659378827911749003801125730213937874981663934259422055079597638258783093392939657595833683452469465273839501
```
可以使用 Python 開多次方根的工具
```python=
>>> from gmpy2 import iroot
>>> iroot(27, 3)
(mpz(3), True)
```
輸出的結果第一個值會告訴我們結果，第二個值會告訴我們是否可以完全開 $n$ 次方號
如果我們只要取數字的話
```python=
>>> from gmpy2 import iroot
>>> iroot(27, 3)[0]
mpz(3)
```
**sol.py**
```python=
#!/usr/bin/python3
from gmpy2 import *
from Crypto.Util.number import *
n = 5489682192316422625434821656898117285064026279334711820823698107520079986854633408581065889926979914843916643565952889381426707291132831900665471049142135375628581051708437366655536056332623163988398065066438737021804605433412757434719710964824708642384163317493038636229777958794272501125366402189914988842955471879476018505743333
e = 5
c = 8695825648499005816846784896009806853240301482143432878264036921549622676046441329661491555770611113772567007417487958975920139817671636465013430373715241659378827911749003801125730213937874981663934259422055079597638258783093392939657595833683452469465273839501
flag = iroot(c , 5)[0]
print(iroot(c , 5))
print(long_to_bytes(flag).decode())
```
---
## RSA TwinPrime
當 $p$ 和 $p+2$ 皆為質數時稱作孿生質數
已知
$$
n_1 = p \times q \quad n_2 = (p+2) \times (q+2)
$$
其中 $p, p+2$ 以及 $q, q+2$ 皆為孿生質數
那麼
$$
n_1 = p \times q\\
n_2 = (p+2) \times (q+2) = pq + 2p + 2q + 4\\
$$
可以藉此得到 $\phi(n_1)$ 以及 $\phi(n_2)$
$$
\begin{align*}
\phi(n_1) &= (p-1) \times (q-1) = pq - (p+q) + 1\\
\phi(n_2) &= (p+1) \times (q+1) = pq + (p+q) + 1
\end{align*}
$$
而 $p+q$
$$
\frac{n_2 - n_1 - 4}{2} = p + q
$$
因此，在不分解 $n_1, n_2$ 的前提下，我們就可以得到 $\phi(n_1)$ 以及 $\phi(n_2)$，並藉此進一步得到 $d$，然後解出原文 $m$
---
### 範例題目
```
n1 = 3593874939884522738360081188589590942537982121904663270426462920730452822866381549106050173717138442489161338601666460445680189833995562392260726330939659090382885163937026571902869123413995198480029534611435826740336455815556935256575605610959114838074076799488081282449
n2 = 3593874939884522738360081188589590942537982121904663270426462920730452822866381549106050173717138442489161338601666460449137123359408777399863055172836432363160566421893035214503585639512339952271274564675355484330533094284391934282566872891805164209109744997389364339953
e = 65537
c2 = 1452263324646172405378479278086175738198155482064889627046654734720235493221282450178456894139596530399913842093175193746761395688114601838969755236143605806012997830096042176122993514497200279356143322897735756185292885577845775294136832076476786425175672990487855382256
```
根據前面的敘述，可以分得到
$$
\begin{align*}
\phi(n_1) &= (p-1) \times (q-1) = pq - (p+q) + 1\\
\phi(n_2) &= (p+1) \times (q+1) = pq + (p+q) + 1\\
p + q &= \frac{n_2 - n_1 - 4}{2}
\end{align*}
$$
有了 $\phi$ 以及 $e$ 就可以得到 $d$，也就可以解密了
**sol.py**
```python=
#!/usr/bin/python
from Crypto.Util.number import long_to_bytes , inverse
n1 = 3593874939884522738360081188589590942537982121904663270426462920730452822866381549106050173717138442489161338601666460445680189833995562392260726330939659090382885163937026571902869123413995198480029534611435826740336455815556935256575605610959114838074076799488081282449
n2 = 3593874939884522738360081188589590942537982121904663270426462920730452822866381549106050173717138442489161338601666460449137123359408777399863055172836432363160566421893035214503585639512339952271274564675355484330533094284391934282566872891805164209109744997389364339953
e = 65537
c2 = 1452263324646172405378479278086175738198155482064889627046654734720235493221282450178456894139596530399913842093175193746761395688114601838969755236143605806012997830096042176122993514497200279356143322897735756185292885577845775294136832076476786425175672990487855382256
pq = n1
p_q = (n2 - n1 - 4) // 2
phi1 = pq - p_q + 1
phi2 = pq + p_q + 1
d1 = inverse(e , phi1)
d2 = inverse(e , phi2)
c1 = pow(c2 , d2 , n2)
flag = pow(c1 , d1 , n1)
print(long_to_bytes(flag))
```
---
## Wiener Attack
Wiener Attack 是在特定情況下提供我們猜測 $k, d$ 的方式($k$ 稍後說明)
透過猜測 $k, d$ 得到 $p, q$，因此得到 $\phi(n)$ 以及明文
接下來我們需要先介紹 Wiener Attack 所需的數學知識
### 連分數 Continued fraction
在數學當中連分數以下列方式表達:
$$
x = a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{a_3 + \frac{1}{\ddots}}}} \quad a_i \in \mathbb{Z}^{+} \texttt{ for all } i
$$
並且也可以用 list 的方式表達，我們會稱呼為 **continued fraction expansion**
$$
x = [a_0, a_1, a_2, a_3, \dots, a_n]
$$
並且可以保證所有的**有理數**都有有限的連分數展開式
以 $\frac{73}{95}$ 舉例來說
$$
\begin{align*}
& \frac{73}{95}\\
= &\ 0 + \frac{1}{\frac{95}{73}}\\
= &\ 0 + \frac{1}{1 + \frac{1}{\frac{73}{22}}}\\
= &\ 0 + \frac{1}{1 + \frac{1}{3 + \frac{1}{\frac{22}{7}}}}\\
= &\ 0 + \frac{1}{1 + \frac{1}{3 + \frac{1}{3 + \frac{1}{7}}}}\\
= &\ [0, 1, 3, 3, 7]
\end{align*}
$$
從範例當中可以發現，我們會不斷的透過倒數以及商數使得連分數不斷擴張，直到商數為 $0$ 結束
```python=
# Continued Fraction Expansion of Rationals
def cf_expansion(n, d):
e = []
q = n // d
r = n % d
e.append(q)
while r != 0:
n, d = d, r
q = n // d
r = n % d
e.append(q)
return e
```
同時也會有一個數列 $[c_0, c_1, c_2, \dots, c_n]$ 稱作 **convergents of the continued fraction expasion**
$$
\begin{align*}
c_0 = 0 &= \frac{0}{1}\\
c_1 = 0 + \frac{1}{1} &= \frac{1}{1}\\
c_2 = 0 + \frac{1}{1 + \frac{1}{3}} &= \frac{3}{4}\\
c_3 = 0 + \frac{1}{1 + \frac{1}{3 + \frac{1}{3}}} &= \frac{10}{13}\\
c_4 = 0 + \frac{1}{1 + \frac{1}{3 + \frac{1}{3 + \frac{1}{7}}}} &= \frac{73}{95}
\end{align*}
$$
也就是一個不斷逼近於 $\frac{73}{95}$ 的數列
同樣的，對於一個小數也可以寫成連分數的型態
以 $2.875$ 舉例來說
$$
\begin{align*}
& 2.875\\
= &\ 2 + 0.875\\
= &\ 2 + \frac{1}{\frac{1}{0.875}}\\
= &\ 2 + \frac{1}{1 + \frac{1}{\frac{1}{0.14285714285714}}}\\
= &\ 2 + \frac{1}{1 + \frac{1}{7 + \frac{1}{\frac{1}{0.00000000000014}}}}\\
= &\ 2 + \frac{1}{1 + \frac{1}{7}}
\end{align*}
$$
```python=
def convergents(e):
n = [] # Nominators
d = [] # Denominators
for i in range(len(e)):
if i == 0:
ni = e[i]
di = 1
elif i == 1:
ni = e[i]*e[i-1] + 1
di = e[i]
else: # i > 1
ni = e[i]*n[i-1] + n[i-2]
di = e[i]*d[i-1] + d[i-2]
n.append(ni)
d.append(di)
yield (ni, di)
```
---
接下來是關於 Wiener Attack 的觀察
### 觀察一
$$
\begin{align*}
\phi(n) &= (p-1)(q-1)\\
&= pq - p - q + 1\\
&= n - p - q + 1\\
&= n - p - \frac{n}{p} + 1
\end{align*}
$$
接下來同乘以 $p$ 並移項
$$
\begin{align*}
&p\phi(n) = pn - p^2 - n + p\\
\Rightarrow\ &p^2 + p(\phi(n) - n - 1) + n = 0
\end{align*}
$$
從觀察一可以發現，只要有 $\phi(n)$ 就可以透過解一元二次方程式的根得到 $p, q$
### 觀察二
我們知道 $ed \equiv 1 \ mod\ \phi(n)$
所以 $ed = k\phi(n) + 1 \texttt{ for some }k$
$$
\phi(n) = \frac{ed-1}{k}
$$
從觀察二可以發現，只要知道 $k, d$ 就可以解出 $\phi(n)$
---
### Wiener Attack
從上面的兩個觀察當中可以得知，只要解出 $k, d$ 就可以解出 $p, q$，也就可以解密
而 Wiener Attack 其實就是提供我們一種猜 $k, d$ 的方式
回顧觀察二並將式子同除以 $d\phi(n)$ 做整理
$$
\begin{align*}
ed - k\phi(n) &= 1\\
\frac{e}{\phi(n)} - \frac{k}{d} &= \frac{1}{d\phi(n)}
\end{align*}
$$
由於 $d\phi(n)$ 很大，可以將 $\frac{1}{d\phi(n)}$ 視為 $0$
整理式子後會發現
$$
\frac{k}{d} = \frac{e}{\phi(n)}
$$
而 $\phi(n) \approx n$
$$
\frac{k}{d} \approx \frac{e}{n}
$$
得到這個結論後，我們就可以透過尋找 $\frac{e}{n}$ 的 **convergents of the continued fraction expansion** 猜看看 $k, d$
每猜一次就帶回去求 $p, q$，然後檢查 $pq = n$ 是否成立，不是就再找下一個
### 限制
- $d < \frac{1}{3}n^{\frac{1}{4}}$
- $q < p < 2p$
### 時間複雜度
知道 $k, d$ 之後回推 $\phi(n)$ 只需要 $O(1)$
$$
\phi(n) = \frac{ed}{k}
$$
知道 $\phi(n)$ 之後解方程式的根也只需要 $O(1)$
$$
p, q = \frac{-(\phi(n) - n - 1) \pm \sqrt{(\phi(n) - n - 1)^2 - 4n}}{2}
$$
而計算 continued fraction expansion 實際上就是在做輾轉相除法
所以嘗試所有的 convergents 需要 $O(log(min(e, n)))$
並且 $e < \phi(n) < n$，因此時間複雜度計為 $O(log(e))$
總時間複雜度為 $O(log(e))$
---
### 範例題目
**task.py**
```python=
#!/usr/bin/python3
from random import SystemRandom
from gmpy2 import isqrt, c_div , invert
from Crypto.Util.number import getPrime , bytes_to_long
urandom = SystemRandom()
def create_keypair(size):
while True:
p = getPrime(size // 2)
q = getPrime(size // 2)
if q < p < 2 * q:
break
n = p * q
phi = (p - 1) * (q - 1)
max_d = c_div(isqrt(isqrt(n)) , 3)
max_d_bits = max_d.bit_length() - 1
while True:
d = urandom.getrandbits(max_d_bits)
try:
e = int(invert(d, phi))
if (e * d) % phi == 1:
break
except:
continue
return n , e , d , p , q
n , e , d , p , q = create_keypair(1024)
from secret import flag
m = bytes_to_long(flag)
c = pow(m , e , n)
a = """n = {}
e = {}
c = {}""".format(n , e , c)
with open("output.py" , "w") as f:
f.write(a)
```
**output.py**
```python=
n = 68126437388977012491646508485989748986441131328587518477687317430610358060299259889270096202942172667026765693121007244799277906816721129879871839668534245685223273320285357819059314305041568152938631311930694380458197864770594205779250872221180313165818499006934672425382344026926216633834392646021142886769
e = 15950795120525802915045576886792784828953195706868419082039089065630551280007920240748167126298220976040006667069839541710102987502293373955109113066554922904845606595280968695858510227233594594345712943776826231898942926115077969092158946886802684295287362659572633661590452939636520740933192957991470727487
c = 64084228016799140236089362630474537548271913453940735254127977713219774643382144415063040580056793784702386932065587548669067894646547290107939535980687043376839097247039277684116912998816751608587498829246494557174907620772811870282348713591834440433602622206371153329743437983172303794473772691521200966081
```
根據前面的推論，先將 convergents of the continued fraction expasion 算出來
接著對於每一組 convergents 去猜測 $k, d$
最後求出 $\phi(n), p, q$ 並確認 $pq = n$ 是否成立即可
**sol.py**
```python=
#!/usr/bin/python3
from Crypto.Util.number import long_to_bytes
from gmpy2 import iroot
n = 68126437388977012491646508485989748986441131328587518477687317430610358060299259889270096202942172667026765693121007244799277906816721129879871839668534245685223273320285357819059314305041568152938631311930694380458197864770594205779250872221180313165818499006934672425382344026926216633834392646021142886769
e = 15950795120525802915045576886792784828953195706868419082039089065630551280007920240748167126298220976040006667069839541710102987502293373955109113066554922904845606595280968695858510227233594594345712943776826231898942926115077969092158946886802684295287362659572633661590452939636520740933192957991470727487
c = 64084228016799140236089362630474537548271913453940735254127977713219774643382144415063040580056793784702386932065587548669067894646547290107939535980687043376839097247039277684116912998816751608587498829246494557174907620772811870282348713591834440433602622206371153329743437983172303794473772691521200966081
def cf_expansion(n, d):
e = []
q = n // d
r = n % d
e.append(q)
while r != 0:
n, d = d, r
q = n // d
r = n % d
e.append(q)
return e
def convergents(e):
n = [] # Nominators
d = [] # Denominators
for i in range(len(e)):
if i == 0:
ni = e[i]
di = 1
elif i == 1:
ni = e[i]*e[i-1] + 1
di = e[i]
else: # i > 1
ni = e[i]*n[i-1] + n[i-2]
di = e[i]*d[i-1] + d[i-2]
n.append(ni)
d.append(di)
yield (ni, di)
def solve(phi, n):
b = (phi - n - 1)
D = iroot(pow(phi - n - 1, 2)-4*n, 2)[0]
return ((-b + D) // 2, (-b - D) // 2)
exp_lst = cf_expansion(e, n)
for i in convergents(exp_lst):
k, d = i
if(k == 0):
continue
phi = e*d//k
p, q = solve(phi, n)
if(p*q == n):
print(long_to_bytes(pow(c, d, n)))
break
```
---
### RSA Side-Channel(待補充內容)
這邊我們只詳細介紹了 little e 以及 twin prime ，不過還有其他有趣的部份可以繼續研究
- $d$ 過小
- [Boneh-Durfee Attack](https://eprint.iacr.org/2016/353)
- 同 $n$ 不同 $e$
- [Common Modulus](https://eprint.iacr.org/2009/037.pdf)
- 同 $e$ 不同 $n$
- [Håstad's Broadcast](https://en.wikipedia.org/wiki/Coppersmith's_attack)
###### tags: `Crypto`
Sign in with Wallet
Connect another wallet