RSA-6 共模攻击

知识点

欧拉定理

欧拉定理是一个关于同余的定理，其数学表达式如下所示：

$$assumption:\ a, n \in N^+ , gcd(a, n) = 1 \\ then:\ a^ {\varphi(n)}\equiv 1 \pmod n$$

这里只做应用，证明请参考 欧拉定理)。

扩展欧几里得算法

扩展欧几里得算法就是在辗转相除法求最大公因数的情况下进行改进，使得该算法能够求出上面逆元分析中的线性方程的解 $x,y$ 。进一步，也就可以通过这个来求解逆元。

辗转相除法

这个比较简单，核心思想就是 $\gcd(a,b) = \gcd(a, b\%a)$ 。

代码如下：

def gcd(a, b):
    while b:
        a, b = b, a%b
    return a

扩展欧几里得算法

上述在求解的过程中抛弃了商，只保留了余数，如果我们将商也利用起来，则可以顺便得到方程组的解 $x,y$ 。

考虑上述算法的终止条件 $b_n == 0$​​ ，我们用下标来区分，第 $i$​ 轮 while 迭代中的参数为 $a_i,b_i$​​ ，终止时为第 $n$​ 轮， 设 $\gcd(a_0, b_0) = d$ 。

此时方程 $a_nx_n+b_ny_n = d$​​ 即是 $d \times x_n + 0 = d$​​ 显然这个解是 $x_n = 1, y_n \in R$​​ 不妨取 $y_n=0$ 计算更简单​ 。

而两层迭代之间有 $a{i+1} = b_i, b{i+1}=a_i \%b_i = a_i- \lfloor \frac{a_i}{b_i} \rfloor \times b_i$​ 。所以对于第 $i-1$​​ 轮的解为：

$$a_ix_i+b_iy_i=d \\ b_{i-1}x_i+(a_{i-1}- \lfloor \frac{a_{i-1}}{b_{i-1}} \rfloor \times b_{i-1})y_i = d \\ a_{i-1}y_i+b_{i-1}(x_i-\lfloor \frac{a_{i-1}}{b_{i-1}} \rfloor \times y_i) = d$$

再观察上述式子与 $aix_i+b_iy_i = d$ 的关系，显然有 $(y_i, x_i-\lfloor \frac{a{i-1}}{b{i-1}} \rfloor \times y_i)$ 为 $(x{i-1}, y_{i-1})$ 的一组解。

于是就构建出了 $xi, y_i$ 与 $x{i-1}, y_{i-1}$ 之间的递推关系。

由于已知 $x_n=1, y_n = 0$ ，于是可以得到最初的 $x_0, y_0$ 使得 $a_0x_0+b_0y_0 = d$ 。（事实上，中间的任意一组方程都是求出对应的解了

代码如下：

def ex_gcd(a, b):
    if b == 0:
        return a, 1, 0
    d, x, y = ex_gcd(b, a%b)
    return d, y, x - y*(a//b)

RSA 加解密过程

密钥生成

随机生成两个大质数 $p$​ 和 $q$​ ，计算出 $n = p \times q$​ 和 $\varphi(n) = (p-1) \times (q-1)$​ ，随机选取一个数 $e$​ 满足 $gcd(e, \varphi(n)) = 1$​ ，如此可以计算出一个 $e$​ 关于 $\varphi(n)$​ 单独唯一乘法逆元 $d$​ ，即 $e \times d \equiv 1 \pmod {\varphi(n)}$​​ 。销毁生成的质数 $p$​​ ， $q$​ 和 $\varphi(n)$​ ，同时严格保密 $d$​ 。

则 $(e, n)$ 组成了公钥，$(d, n)$​ 组成了私钥。如果不泄漏额外的信息、不使用过小的质数、不做一些高风险的生成，则只根据公钥 $(e, n)$ 想要计算出私钥 $(d, n)$ 是计算不可行的。

加密过程

将需要加密的消息按某种格式转化为一个或多个数字， CTF 中一般就将 flag 转化为一个数字 $m$ ，然后计算密文 $c = m ^ e \mod n$ 。

考虑到有可能会存在 $m|n$ 的情况，而由于 $n = p \times q$ ，故此时必有 $m|p$ 或者 $m|q$ 。由于 $p$ 和 $q$ 都是质数，所以 $m=p$ 或者 $m=q$ 。一方面这个概率是很小的。另一方面，如果真的这么巧， $m=p$ 或者 $m=q$ 那就按照前面的法则再次重新生成一组 $p$ 和 $q$ ，然后再构建即可。

解密过程

设需要解密的密文为 $c$​ ，则明文对应的数字 $m = c ^ d \mod n$​ 。

$$\because e \times d \equiv 1 \pmod {\varphi(n)} \\ \therefore e \times d = k \times \varphi(n) + 1, k \in Z \\ \because gcd(m, n) = 1 \\ \therefore m^{\varphi(n)}\equiv 1 \pmod n \ ······\ Euler's\ theorem\\ \because c = m^e \mod n \\ \therefore c^d \equiv (m^e)^d \equiv m ^ {e \times d} \equiv m^{k \times \varphi(n) + 1} \equiv m \times ({m^{\varphi(n)}})^k \equiv m \times 1^k \equiv m \pmod n \\$$

例题

题目

听说你已经搞定了公因子的攻击？那试试这个吧！我方截获对方两次传输的同一明文对应相关数据如下：

n = 14082895340069750195624496854826339506625112043886407716057400491975763565682615324358599521625943482701682587973818614203535242089852507027219502943551439252395834102385713543422992240035766976798628201210682884172910499397950881894189484531458713368702071779515768387560603074195395231205546053377847977139139962281575255410172053491593716534864194443759866533036698178736529157047325842162534702172234710695219385028317480472433012068095732654401548088593201500066504115851050999663052585253401233559592019995006329067999264988201573694387666742725409090282654650800657212428121182797924769468859485888967582628541
e1 = 65537
e2 = 37159
c1 = 13009703418163109373321914570115521381403485281783311795242037913039315126523948223129761997127645627347586595396141359433450959404871247085063786749595168530701825217743170898426652413008097051001059817113689223728045313047332075969929714074171740778296240189642191942886403696899687044463240870277420044873161146083136586380177925936704620270083639141298242171005518242731754941966213419920739701127842240668375649495224688441070399226051484108155389663623144311883458198369973969457470264786247714727523335718783691657654080675464242515965165340881784658696669925545872015487868902519660850831515420276431220296736
c2 = 3692283612689059440081375135711031778848493864899592806098356933852789514162967663651536808442384134613229523108178571281384247817506851663461955108379005042949882416677112039143309629447920374686721982170003553224142515425912829759034853560407046073567227732900175222535340761860333622950267964440376530811338924747686238062908491225290659701340052698131249733745141464571152188170685350781480321937119997210865576176634508385180136273005590149166425288610875311913556458314369476146274680002728861488726481332603206399522896249943088802479282744648523869255988194575047125603946974139732005590297112491485254902056

题解

题目中给出的数据很明显是用两个不同的指数 $e_1, e_2$ 和相同的模数 $n$ 去加密了同一组明文 $m$​ 。这是很典型的共模攻击的特征。

回顾 RSA 加解密原理中，最后一步是 $c^d \equiv (m^e)^d \equiv m ^ {e \times d} \equiv m^{k \times \varphi(n) + 1} \equiv m \times ({m^{\varphi(n)}})^k \equiv m \times 1^k \equiv m \pmod n$ 。其中的核心无非就是 $ed \equiv 1 \pmod {\varphi(n)}$ 。

这里给了两组加密。

$$c_1 \equiv m^{e_1} \pmod n \\ c_2 \equiv m^{e_2} \pmod n \\$$

而且很容易可以判断出， $gcd(e_1, e_2) = 1$​ ，所以根据裴蜀定理，我们可以通过知道方程 $(xe_1+ye_2 = 1)$ 有解。

而我们可以很容易利用扩展欧几里得算法求出上述的方程的一组解 $(x,y)$ 。

然后计算:

$$c_1^x \equiv (m^{e_1})^x \equiv m^{e_1x} \pmod n \\ c_2^y \equiv (m^{e_2})^y \equiv m^{e_2y} \pmod n$$

然后讲上述两式左右分别相乘有

$$c_1^x \times c_2^y \equiv m^{e_1x} \times m^{e_2y} \equiv m^{e_1x+e_2y} \equiv m \pmod n$$

于是乎 $c_1^xc_2^y$​ 就是需要求解的明文。

但此时还有一个问题，方程 $(xe_1+ye_2 = 1)$​ 的解 $x,y$ 中必有一个负数，在不知 $\varphi(n)$ 的情况下无法进行幂次。

不妨设 $y<0, x>0$ ，$m \equiv c_1^xc_2^y \equiv c_1^x(c_2^{-y})^{-1} \pmod n$ 而 $c_2^{-y}$ 的逆元显然存在。

解密脚本如下：

import gmpy2
from Crypto.Util.number import long_to_bytes

def ex_gcd(a, b):
    if b == 0:
        return a, 1, 0
    d, x, y = ex_gcd(b, a%b)
    return d, y, x - y*(a//b)

n = 14082895340069750195624496854826339506625112043886407716057400491975763565682615324358599521625943482701682587973818614203535242089852507027219502943551439252395834102385713543422992240035766976798628201210682884172910499397950881894189484531458713368702071779515768387560603074195395231205546053377847977139139962281575255410172053491593716534864194443759866533036698178736529157047325842162534702172234710695219385028317480472433012068095732654401548088593201500066504115851050999663052585253401233559592019995006329067999264988201573694387666742725409090282654650800657212428121182797924769468859485888967582628541
e1 = 65537
e2 = 37159
c1 = 13009703418163109373321914570115521381403485281783311795242037913039315126523948223129761997127645627347586595396141359433450959404871247085063786749595168530701825217743170898426652413008097051001059817113689223728045313047332075969929714074171740778296240189642191942886403696899687044463240870277420044873161146083136586380177925936704620270083639141298242171005518242731754941966213419920739701127842240668375649495224688441070399226051484108155389663623144311883458198369973969457470264786247714727523335718783691657654080675464242515965165340881784658696669925545872015487868902519660850831515420276431220296736
c2 = 3692283612689059440081375135711031778848493864899592806098356933852789514162967663651536808442384134613229523108178571281384247817506851663461955108379005042949882416677112039143309629447920374686721982170003553224142515425912829759034853560407046073567227732900175222535340761860333622950267964440376530811338924747686238062908491225290659701340052698131249733745141464571152188170685350781480321937119997210865576176634508385180136273005590149166425288610875311913556458314369476146274680002728861488726481332603206399522896249943088802479282744648523869255988194575047125603946974139732005590297112491485254902056

_, x, y = ex_gcd(e1, e2)
assert _ == 1

if x < 0:
    x, y = y, x

m = (pow(c1, x, n)*gmpy2.invert(pow(c2, -y, n), n))%n

flag = long_to_bytes(m)
print(flag)
# b'flag{baby_RSA_common_mode_attack}'