RSA 總整理 - HackMD

# RSA 總整理 RSA 是一個著名的非對稱式加密系統，其安全性建立在大數分解的難度上目前 RSA 僅能透過旁通道攻擊(Side-Channel Attack) --- <center> RSA 基本內容 </center> 接下來我們需要先介紹 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> 驗證 RSA 解密的正確性 </center> > 證明 $m = c^d \% n$ 已知 $m < n$ 要證明 $m = c^d \% n$ 等同於證明 $c^d \% n - m = 0$ $$ \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*} $$ 根據費馬小定理可知 $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> RSA Side-Channels </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`

Read more

C++ 從入門到入土

ISIP SummerCamp

擴展歐基里德算法 (Extended Euclidean algorithm)

線性代數 Linear Algebra