RSA 總整理

RSA 是一個著名的非對稱式加密系統，其安全性建立在大數分解的難度上
目前 RSA 僅能透過旁通道攻擊(Side-Channel Attack)

---

RSA 基本內容

接下來我們需要先介紹 RSA 所需的數學知識

尤拉函數 Eular Function

我們會以

$\varphi$ (念作 phi) 表示尤拉函數
定義

$\varphi (p)$ 為在所有的正整數當中，有多少

$<p$ 的數字與

$p$ 互質的數字

在這個定義之下，如果說

$p$ 是一個質數的話，那麼所有

$<p$ 的正整數也必定與之互質，因此此時的

$\varphi (p)=p-1$
這也就是費馬小定理

在 RSA 當中，我們會取兩個質數

$p,q$，並計算

$n=p\times q$
此時的

$\varphi (n)=\varphi (p)\times \varphi (q)=(p-1)\times (q-1)$

模反元素 Modular Inverse

一個整數

$a$ 在模(mod)

$n$ 的模反元素是指能滿足以下式子的整數

$b$

$$a^{-1}\equiv b(modn)$$
或是表示成

$$ab\equiv 1(modn)$$

就如同要找到一個數

$a$ 的乘法反元素，等同找到一個數字

$b$ 滿足

$$ab=1$$
此時的

$b=\frac{1}{a}$，也就是我們常見的倒數

在 RSA 當中，我們會去找某個數字

$e$ 在模(mod)

$\varphi (n)$ 下的模反元素

$d$

$$\begin{array}{rl}& e^{-1}\equiv d(mod\varphi (n))\\ \to & ed\equiv 1(mod\varphi (n))\\ \to & edmod\varphi (n)=1\end{array}$$

$$e^{-1}\ne \frac{1}{e}$$
由於是在模底下運作，這個是不成立的!

這裡還有一個重要的性質

$$gcd(e,\varphi (n))=1$$
因為唯有這個條件成立，才會存在模反元素

$d$

如果不知道為什麼，不妨舉幾個數字來試試看，例如

• $e=2$ 且
  $\varphi (n)=4$
• $e=6$ 且
  $\varphi (n)=8$

會發現到無論如何都不會找到解，這裡先不寫證明

在 python 當中要求模反元素，可以使用 python 的 modules 輕鬆達成

• gmpy2
  ​>>> from gmpy2 import invert
  ​>>> invert(3, 7)
  ​mpz(5)
  

• PyCryptodome
  ​>>> 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,\varphi (n))=1$
3. $c=m^{e}modn$

RSA Decryption

RSA 解密流程如下

1. 嘗試將
   $n$ 分解出兩質數
   $p,q$
2. 計算
   $\varphi (n)=(p-1)\times (q-1)$
3. 找出解密指數
   $d$ 使得
   $ed\equiv 1(mod\varphi (n))$
4. $m=c^{d}modn$

第一步的分解可以透過下列的工具協助

• factordb
• alpetron
• yafu
• SageMath

驗證 RSA 解密的正確性

證明

$m=c^d\mathrm{\%}n$

已知

$m<n$
要證明

$m=c^d\mathrm{\%}n$ 等同於證明

$c^d\mathrm{\%}n-m=0$

$$\begin{array}{rl}{c}^d\mathrm{\%}n-m& =0\\ & =(m^e\mathrm{\%}n{)}^d\mathrm{\%}n-m(c=m^e\mathrm{\%}n)\\ & =m^{ed}\mathrm{\%}n-m\\ & =m^{k(p-1)(q-1)+1}\mathrm{\%}n-m(ed\equiv 1mod\varphi (n)\Rightarrow ed=k\varphi (n)+1,k\in \mathbb{R})\\ & =m(m^{k(p-1)(q-1)}-1)\mathrm{\%}n\end{array}$$

根據費馬小定理可知

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

$p$ 為質數)

$$\begin{array}{rl}& \Rightarrow (m^{k(p-1)}{)}^{q-1}\equiv 1(modq)\\ & \Rightarrow (m^{k(q-1)}{)}^{p-1}\equiv 1(modp)\\ & \Rightarrow m^{k(p-1)(q-1)}\equiv 1(modpq)\\ & \Rightarrow m^{k(p-1)(q-1)}\equiv 1(modn)\end{array}$$

因此

$$\begin{gathered} m(m^{k(p-1)(q-1)}-1)\mathrm{\%}n \\ =m(1-1)\mathrm{\%}n=0◼ \end{gathered}$$

Convert

要做 RSA encryption 運算必須要是一串數字
做完 RSA decryption 後會得到的是一串數字
因此我們須要有可以將字串跟數字之間做轉換的工具，以下使用 pyCryptodome

• 字串轉為數字
  ​>>> from Crypto.Util.number import long_to_bytes
  ​>>> long_to_bytes(1567694910997846802713134265455563233695200125)
  ​b'FLAG{long_to_bytes}'
  

• 數字轉為字串
  ​>>> 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$ 在模

$\varphi (n)$ 下的模反元素
先求

$\varphi (n)$

因為這題的

$n$ 還不大，可以透過上述的工具先做分解，可以得到

• $p=670839939121655241517135431571$
• $q=955576010440355093873649387901$

則

$\varphi (n)=(p-1)\times (q-1)$

$d$ 就可以透過

$e,\varphi (n)$ 計算出來

sol.py

#!/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)))

---

RSA Side-Channels

RSA Little e

當

$n$ 過大且

$e$ 過小使得

$m^e<n$，此時只要對

$c$ 開

$e$ 次方根就可以得到

$m$

先看一下 RSA encryption

$$c=m^e\mathrm{\%}n$$

如果

$m^e<n$，就意味著

$\mathrm{\%}n$ 這個操作根本沒做
也就是說

$c=m^e$，倒過來說

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

---

範例題目

n = 5489682192316422625434821656898117285064026279334711820823698107520079986854633408581065889926979914843916643565952889381426707291132831900665471049142135375628581051708437366655536056332623163988398065066438737021804605433412757434719710964824708642384163317493038636229777958794272501125366402189914988842955471879476018505743333
e = 5
c = 8695825648499005816846784896009806853240301482143432878264036921549622676046441329661491555770611113772567007417487958975920139817671636465013430373715241659378827911749003801125730213937874981663934259422055079597638258783093392939657595833683452469465273839501

可以使用 Python 開多次方根的工具

>>> from gmpy2 import iroot
>>> iroot(27, 3)
(mpz(3), True)

輸出的結果第一個值會告訴我們結果，第二個值會告訴我們是否可以完全開

$n$ 次方號
如果我們只要取數字的話

>>> from gmpy2 import iroot
>>> iroot(27, 3)[0]
mpz(3)

sol.py

#!/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{n}_2=(p+2)\times (q+2)$$
其中

$p,p+2$ 以及

$q,q+2$ 皆為孿生質數

那麼

$$\begin{gathered} n_1=p\times q \\ {n}_2=(p+2)\times (q+2)=pq+2p+2q+4 \end{gathered}$$

可以藉此得到

$\varphi (n_1)$ 以及

$\varphi (n_2)$

$$\begin{array}{rl}\varphi (n_1)& =(p-1)\times (q-1)=pq-(p+q)+1\\ \varphi (n_2)& =(p+1)\times (q+1)=pq+(p+q)+1\end{array}$$

而

$p+q$

$$\frac{n_2-n_1-4}{2}=p+q$$

因此，在不分解

$n_1,n_2$ 的前提下，我們就可以得到

$\varphi (n_1)$ 以及

$\varphi (n_2)$，並藉此進一步得到

$d$，然後解出原文

$m$

---

範例題目

n1 = 3593874939884522738360081188589590942537982121904663270426462920730452822866381549106050173717138442489161338601666460445680189833995562392260726330939659090382885163937026571902869123413995198480029534611435826740336455815556935256575605610959114838074076799488081282449
n2 = 3593874939884522738360081188589590942537982121904663270426462920730452822866381549106050173717138442489161338601666460449137123359408777399863055172836432363160566421893035214503585639512339952271274564675355484330533094284391934282566872891805164209109744997389364339953
e = 65537
c2 = 1452263324646172405378479278086175738198155482064889627046654734720235493221282450178456894139596530399913842093175193746761395688114601838969755236143605806012997830096042176122993514497200279356143322897735756185292885577845775294136832076476786425175672990487855382256

根據前面的敘述，可以分得到

$$\begin{array}{rl}\varphi (n_1)& =(p-1)\times (q-1)=pq-(p+q)+1\\ \varphi (n_2)& =(p+1)\times (q+1)=pq+(p+q)+1\\ p+q& =\frac{n_2-n_1-4}{2}\end{array}$$

有了

$\varphi$ 以及

$e$ 就可以得到

$d$，也就可以解密了

sol.py

#!/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$，因此得到

$\varphi (n)$ 以及明文

接下來我們需要先介紹 Wiener Attack 所需的數學知識

連分數 Continued fraction

在數學當中連分數以下列方式表達:

$$x=a_0+\frac{1}{a_1+\frac{1}{a_2+\frac{1}{a_3+\frac{1}{\ddots }}}}{a}_i\in {\mathbb{Z}}^{+}\mathtt{\text{ for all }}i$$

並且也可以用 list 的方式表達，我們會稱呼為 continued fraction expansion

$$x=[a_0,a_1,a_2,a_3,\dots ,a_n]$$

並且可以保證所有的有理數都有有限的連分數展開式

以

$\frac{73}{95}$ 舉例來說

$$\begin{array}{rl}& \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{array}$$

從範例當中可以發現，我們會不斷的透過倒數以及商數使得連分數不斷擴張，直到商數為

$0$ 結束

# 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{array}{rl}{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{array}$$

也就是一個不斷逼近於

$\frac{73}{95}$ 的數列

同樣的，對於一個小數也可以寫成連分數的型態
以

$2.875$ 舉例來說

$$\begin{array}{rl}& 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{array}$$

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{array}{rl}\varphi (n)& =(p-1)(q-1)\\ & =pq-p-q+1\\ & =n-p-q+1\\ & =n-p-\frac{n}{p}+1\end{array}$$

接下來同乘以

$p$ 並移項

$$\begin{array}{rl}& p\varphi (n)=pn-p^2-n+p\\ \Rightarrow & p^2+p(\varphi (n)-n-1)+n=0\end{array}$$

從觀察一可以發現，只要有

$\varphi (n)$ 就可以透過解一元二次方程式的根得到

$p,q$

觀察二

我們知道

$ed\equiv 1mod\varphi (n)$
所以

$ed=k\varphi (n)+1\mathtt{\text{ for some }}k$

$$\varphi (n)=\frac{ed-1}{k}$$

從觀察二可以發現，只要知道

$k,d$ 就可以解出

$\varphi (n)$

---

Wiener Attack

從上面的兩個觀察當中可以得知，只要解出

$k,d$ 就可以解出

$p,q$，也就可以解密
而 Wiener Attack 其實就是提供我們一種猜

$k,d$ 的方式

回顧觀察二並將式子同除以

$d\varphi (n)$ 做整理

$$\begin{array}{rl}ed-k\varphi (n)& =1\\ \frac{e}{\varphi (n)}-\frac{k}{d}& =\frac{1}{d\varphi (n)}\end{array}$$

由於

$d\varphi (n)$ 很大，可以將

$\frac{1}{d\varphi (n)}$ 視為

$0$
整理式子後會發現

$$\frac{k}{d}=\frac{e}{\varphi (n)}$$

而

$\varphi (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$ 之後回推

$\varphi (n)$ 只需要

$O(1)$

$$\varphi (n)=\frac{ed}{k}$$
知道

$\varphi (n)$ 之後解方程式的根也只需要

$O(1)$

$$p,q=\frac{-(\varphi (n)-n-1)\pm \sqrt{(\varphi (n)-n-1{)}^2-4n}}{2}$$

而計算 continued fraction expansion 實際上就是在做輾轉相除法
所以嘗試所有的 convergents 需要

$O(log(min(e,n)))$
並且

$e<\varphi (n)<n$，因此時間複雜度計為

$O(log(e))$

總時間複雜度為

$O(log(e))$

---

範例題目

task.py

#!/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

n = 68126437388977012491646508485989748986441131328587518477687317430610358060299259889270096202942172667026765693121007244799277906816721129879871839668534245685223273320285357819059314305041568152938631311930694380458197864770594205779250872221180313165818499006934672425382344026926216633834392646021142886769
e = 15950795120525802915045576886792784828953195706868419082039089065630551280007920240748167126298220976040006667069839541710102987502293373955109113066554922904845606595280968695858510227233594594345712943776826231898942926115077969092158946886802684295287362659572633661590452939636520740933192957991470727487
c = 64084228016799140236089362630474537548271913453940735254127977713219774643382144415063040580056793784702386932065587548669067894646547290107939535980687043376839097247039277684116912998816751608587498829246494557174907620772811870282348713591834440433602622206371153329743437983172303794473772691521200966081

根據前面的推論，先將 convergents of the continued fraction expasion 算出來
接著對於每一組 convergents 去猜測

$k,d$
最後求出

$\varphi (n),p,q$ 並確認

$pq=n$ 是否成立即可

sol.py

#!/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
• 同
  $n$ 不同
  $e$
  • Common Modulus
• 同
  $e$ 不同
  $n$
  • Håstad's Broadcast

tags: Crypto