RSA-4 e 和 ɸ(n) 不互质

知识点

逆元存在的充要条件

根据裴蜀定理线性方程 $ax+by = d$ 有解的充要条件是 $\gcd(a,b)|d$ , 即 $d = k \times \gcd(a,b)$。

若 $a$ 和 $b$ 不互质，则 $\gcd(a,b)>1$ ，此时对于 $\forall (x,y)\in R^2$ ，满足 $ax+by=d$ 都有 $ax+by=d\geq\gcd(a,b)>1$。

于是，不妨可以设 $d < b$ ，因为如果 $d \geq b$ 可以通过 $y = y+1, d = d - b$ 直到满足 $d < b$ 。

再两侧同时对 $b$ 取余有：

$ax+by \equiv d \pmod b \\ ax \equiv d \pmod b$

所以对任意 $x$ 有

$1 < ax \equiv d < b \pmod b$

所以，此时 $a$ 和 $b$ 互相关于对方无逆元。

即 $a$ 和 $b$ 关于对方存在逆元从充要条件是 $\gcd(a,b) = 1$ 。

扩展欧几里得算法

扩展欧几里得算法就是在辗转相除法求最大公因数的情况下进行改进，使得该算法能够求出上面逆元分析中的线性方程的解 $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)

中国剩余定理（Chinese Remainder Theorem, CRT）

这里只做简单是介绍，更多更详细的资料可以查阅更多的相关资料。如百科， OI Wiki 等。

中国剩余定理，又称中国余数定理，是数论中的一个关于一元线性同余方程组的定理，说明了一元线性同余方程组有解的准则以及求解方法。也称为孙子定理，古有“韩信点兵”、“孙子定理”、“求一术”（宋沈括）、“鬼谷算”（宋周密）、“隔墻算”（宋周密）、“剪管术”（宋杨辉）、“秦王暗点兵”、“物不知数”之名。

一般 CRT

在数学上，中国剩余定理可用来对一元线性同余方程组求解。

设有如下方程组：

$x \equiv b_1 \pmod {m_1} \\ x \equiv b_2 \pmod {m_2} \\ \vdots \\ x \equiv b_n \pmod {m_n} \\$

其中 $m_1, m_2, \cdots, m_n$ 两两互质。

求解 $x$ （mod 意义下。

算法实现流程如下：

计算 $M = \prod_{i=1}^{n} m_i$ 。
计算 $M_{i} = M \div m_i$ 。
计算每个 $M_i$ 模 $m_i$ 意义下的逆元，$M_i^{-1}$ ，即 $M_i \times M_i^{-1} \equiv 1 \pmod {m_i}$。
则解为 $x \equiv (\sum_{i=1}^nb_i \times M_i \times M_i^{-1}) \pmod M$ 。

进阶 CRT

细心的同学可能发现了，上述要求所有模数两两互质。那要是模数不互质咋办呢？

这里简答起见，我们考虑一个只有两组方程的方程组

$x \equiv b_1 \pmod {m_1} \\ x \equiv b_2 \pmod {m_2} \\ \gcd(m_1, m_2) = d > 1$

将同余方程拆分开就是

$x = k_1m_1+b_1 \\ x = k_2m_2+b_2 \\$

于是就是有:

$x = k_1m_1+b_1=k_2m_2+b_2$ $k_1m_1-k_2m_2 = b_2-b_1$

显然上述式子中，未知量只有 $k_1, k_2$ 那么这个就和前面扩展欧几里得定理处求解很像了。

首先是根据裴蜀定理可以判断上述方程有无解 $k_1, k_2$ 。

若 $\gcd(m_1, m_2)\nmid(b_2-b_1)$ 则上述方程无解。无这样的 $k_1, k_2$ 。
否则 $\gcd(m_1, m_2) | (b_2-b_1)$ 。

不妨设 $d=\gcd(m_1, m_2), p_1=\frac{m_1}{d}, p_2=\frac{m_2}{d}$ 则显然有 $\gcd(p_1,p_2)=1$ 。于是上述的式子(8)可以改写为：

$k_1p_1d-k_2p_2d=b_2-b_1$

显然有 $d|(b_2-b_1)$ 移项：

$k_1p_1-k_2p_2=\frac{b_2-b_1}{d}$

注意，此时我们可以通过扩展欧几里得算法求得 $\lambda_1p_1+\lambda_2p_2=\gcd(p_1, p_2)=1$ 的解，。

然后我们就可以求出解 $k_1, k_2$ ：

$k_1 = \lambda_1 \frac{b_2-b_1}{d} \\ k_2 = -\lambda_2 \frac{b_2-b_1}{d} \\$

然后就可以求出一个 $x_0 = k_1m_1+b_1=k_2m_2+b_2$ 。

至此，求出了一个特解 $x_0$ 满足

$x \equiv b_1 \pmod {m_1} \\ x \equiv b_2 \pmod {m_2} \\ \gcd(m_1, m_2) = d > 1$

注意，我们扩展欧几里得在求解的时候，在最底层应有无数的解，但是我随便取了一个，所以，上述只求出了满足条件的一个特解。

那么怎么通过这个特解，求出整个系统的通解呢？

【定理】若特解 $x^$ 满足 $\left{\begin{aligned}x \equiv b_1 \pmod {m_1} \x \equiv b_2 \pmod {m_2} \\end{aligned}\right.$ ，则次方程组的通解为 $x \equiv x^ \pmod {lcm(m_1, m_2)}$ 。

于是带入算出的特解，就得到了整个系统的通解。

例题

例题1：公因数很小

题目

听说你很精通 RSA ？那就来试试看能不能做这个没逆元的？ Hint：尝试分解 n

题解

题目中给出的提示是试试分解 $n$ ，于是尝试用 yafu 分解一下。一瞬就分解成功了（考点不在这里：

得到了 $p$ 和 $q$ 问题岂不是就迎刃而解了？

1
2

p = 10976869853830541299248580771590130854083144580361242433420557921001130284636980035565212361371611364833259444556280104416743087841023122428538312427943473
q = 10976869853830541299248580771590130854083144580361242433420557921001130284636980035565212361371611364833259444556280104416743087841023122428538312427942967

但是如果按照之前的做法就会遇见下面的这个报错，提示逆元不存在：

事实上，计算一波就知道 $\gcd(e, \varphi(n)) = 2 > 1$ 确实逆元不存在。这可咋整？

根据前面的扩展欧几里得算法，可以很轻松地找出一个 $d$ 使得 $e\times d=\gcd(e, \varphi(n)) = 2$ 。

再根据 RSA 算法的基本计算原理可以得知，此时， $c^{d} \equiv m^2 \pmod n$ 。

$\because e \times d \equiv 2 \pmod {\varphi(n)} \\ \therefore e \times d = k \times \varphi(n) + 2, 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) + 2} \equiv m^2 \times ({m^{\varphi(n)}})^k \equiv m^2 \times 1^k \equiv m^2 \pmod n \\$

那么再开平方根，可以用前面的费马分解类似的方法进行求解即可，理论上会存在两个解，但是逐一尝试就可以了。

解密脚本如下：

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 = 120491671787933729108476194499163893083968394949480049348379043767491627464410199840078276245663859992488865559032791822655853112057011464674557659165084137380631278392220470111199965143379980865414123358817375632106316573096730462759256552038388575491439398156732752820948140205779064855154444424679543904391
e = 114514
c = 20100559695786380165543276753317453339114462887841359032521636408859468898264655335976093030363436298893961749986818846989274322114843486483713324869965481532264205834518440113655367569454640827971202315045567994694492715253960421748489855434739974419985803248970262223208108796427123217251097716080236041732

p = 10976869853830541299248580771590130854083144580361242433420557921001130284636980035565212361371611364833259444556280104416743087841023122428538312427943473
q = 10976869853830541299248580771590130854083144580361242433420557921001130284636980035565212361371611364833259444556280104416743087841023122428538312427942967

phi = (p-1)*(q-1)

_, d, __ = ex_gcd(e, phi)
d %= phi # 取正的

assert e*d % phi == gmpy2.gcd(e, phi)

m2 = pow(c, d, n)

# format 
# 这个阈值也是随便设的 能爆出来就行 所以尽量大
for i in range(1<<30):
    r = gmpy2.iroot(m2+i*n, 2)
    if r[1]:
        # print(r[0])
        break
m = r[0]

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

例题2：公因数不是那么小

题目

听说你完成了没有逆元的 RSA，那再来看看这个!

题目数据如下

n1 = 145902412361478782344770381873783700413638083575664796147183684992615987925480426688706400688307583005196450858827113757408777361940584125700594767997877530445777012630266331221234501260829837820315200747919668506933176146599166089445798737129024362167061966283411487243534460764772316650320961711082540676899
e1 = 1027642
c1 = 145599749068981747615735527132763322497511927333435440286556586440700880156616855875705194707404376786136517540004760807637963195264918622629767468410395993222984750343835317265657642066985400345308564185485762783798378213615456853641873967743113774281508530109771993747380075137571629299980431535183973047761 

n2 =149099187170511972630955070342575714830336629001429055523308641067867185643738492089983321303377141971663123411968339764579768625561000509534051657156505686277638053591553620131562538158327446457847814787147698749502556552831112070838138070024147578824279983531049306936118687161116949990664307619657857322083
e2 = 2072238
c2 = 120008213052657974749407574322061865802530371140787421373712117963589562586158574291255627693566218561032563852324558823021648758372467762769424392909644546747637434681882739238686051912069497299223106307867125393298991125534662447166531892395781655435572658429514851281851805554254667625969745870072913201081

题解

根据题目提示，我们通过 factordb 查询到了 $n$ 的分解。我们根据求公因数完成对 $n_1, n_2$ 的分解。

PS: 这个部分将在下一部分中详细介绍：公因子唯密文攻击

1 2	In [1]: gmpy2.gcd(n1, n2) Out[1]: mpz(12120327527644543811107783655014863098833219936714394976342507913322405566177432644931575840816861543106701611662013978324877080018872656490603706071067111)

于是就可以完成分解

p = 12120327527644543811107783655014863098833219936714394976342507913322405566177432644931575840816861543106701611662013978324877080018872656490603706071067111
q1 = 12037827528067911684278967221392433256129944002157200272548317200308481572950474775891360447285969682243206009995242277136633522897723532096467191105943909

p = 12120327527644543811107783655014863098833219936714394976342507913322405566177432644931575840816861543106701611662013978324877080018872656490603706071067111
q2 = 12301580698247665838432962460247894405698817646605188562297985838079356879336309758823376086396761749681729993573203954506346863479448531269351981555913253

那岂不是一瞬就可以完成了，但是显然不是。这里也是没有逆元存在的， $\gcd(e, \varphi(n)) = 14$ 。(两组都是)

In [1]: gmpy2.gcd(e1, (p1-1)*(q1-1))
Out[1]: mpz(14)
    
In [2]: gmpy2.gcd(e2, (p2-1)*(q2-1))
Out[2]: mpz(14)

那岂不是可以和前面一样，先用扩展欧几里得来求一个解，再开方？ $14$ 次方，可有点不敢恭维。（虽然也不是不能开，因为理论上会开出来 $\gcd(e, \varphi(n)) = 14$ 个根，再一一试，很不优雅。

那这里和前面有些许不同，这里是有两组等式的，换言之，写出来如下：

$m^{14} \equiv a_1 \pmod {n_1} \\ m^{14} \equiv a_2 \pmod {n_2} \\$

其中， $a_1, a_2$ 就是按照前面的方式求出来的需要开 $14$ 次方的值。那么看着这两个方程是不是和前面的 CRT 很像呢？只是刚刚好不互质。

使用上面的公式计算一组特解 $x_0$，这里 $b_1=a_1, b_2=a_2, d = \gcd(n_1,n_2) = p, p_1=q_1, p_2=q_2$ 。

但是 $m^{14} \equiv x_0 \pmod {pq_1q_2}$ ，并不是关于 $n_1$ 或者 $n_2$ 的。

此时问题转化为求解一个新的 RSA 问题了：

1
2
3

e = 14
c = x0
n = p*q1*q2

但是新的 $\gcd(e’,\varphi(pq_1q_2)) = 14 = e$ !!!! 搞了半天求了个寂寞。

不过别慌，因为 $m^{14} \equiv x_0 \pmod {pq_1q_2}$

所以： $m^{14} \equiv x_0 \pmod {pq_1} \equiv m^{14} \equiv x_0 \pmod {pq_2} \equiv m^{14} \equiv x_0 \pmod {q_1q_2}$

前两组就是本题中的 $n_1, n_2$ 所以不予考虑，不妨来考虑第三组，此时的 RSA 问题是：

1
2
3

e = 14
c = x0
n = q1*q2

再计算一下，发现 $\gcd(e’, \varphi(q_1q_2)) = 2$ ，好的，这就可以用前面的方法，开方进行解决了。

解密代码如下：

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)


n1 = 145902412361478782344770381873783700413638083575664796147183684992615987925480426688706400688307583005196450858827113757408777361940584125700594767997877530445777012630266331221234501260829837820315200747919668506933176146599166089445798737129024362167061966283411487243534460764772316650320961711082540676899
e1 = 1027642
c1 = 145599749068981747615735527132763322497511927333435440286556586440700880156616855875705194707404376786136517540004760807637963195264918622629767468410395993222984750343835317265657642066985400345308564185485762783798378213615456853641873967743113774281508530109771993747380075137571629299980431535183973047761 

n2 =149099187170511972630955070342575714830336629001429055523308641067867185643738492089983321303377141971663123411968339764579768625561000509534051657156505686277638053591553620131562538158327446457847814787147698749502556552831112070838138070024147578824279983531049306936118687161116949990664307619657857322083
e2 = 2072238
c2 = 120008213052657974749407574322061865802530371140787421373712117963589562586158574291255627693566218561032563852324558823021648758372467762769424392909644546747637434681882739238686051912069497299223106307867125393298991125534662447166531892395781655435572658429514851281851805554254667625969745870072913201081

p = 12120327527644543811107783655014863098833219936714394976342507913322405566177432644931575840816861543106701611662013978324877080018872656490603706071067111
q1 = 12037827528067911684278967221392433256129944002157200272548317200308481572950474775891360447285969682243206009995242277136633522897723532096467191105943909
q2 = 12301580698247665838432962460247894405698817646605188562297985838079356879336309758823376086396761749681729993573203954506346863479448531269351981555913253

phi1 = (p-1)*(q1-1)
phi2 = (p-1)*(q2-1)


# 求 a1 a2
_, d1, __ = ex_gcd(e1, phi1)
_, d2, __ = ex_gcd(e2, phi2)

d1 %= phi1 # 取正的
d2 %= phi2 # 取正的

a1 = pow(c1, d1, n1)
a2 = pow(c2, d2, n2)

# 通过求 k 求特解
gcd_, lambda1, lambda2 = ex_gcd(q1, q2)
assert gcd_ == lambda1*q1+lambda2*q2
assert (a1-a2) % p == 0
k1 = lambda1*(a2-a1) // p
k2 = lambda2*(-(a2-a1)) // p
assert (k1*n1+a1)%(p*q1*q2) == (k2*n2+a2)%(p*q1*q2)

# 特解 c = x0 = m^14
m14 = (k1*n1+a1)%(p*q1*q2)
# e = 14
e = 14
# phi
phi = (q1-1)*(q2-1)
# n
n = q1 * q2
_, d, __ = ex_gcd(e, phi)
d %= phi # 取正的

# m^2
m2 = pow(m14, d, n)

# format 
# 这个阈值也是随便设的 能爆出来就行 所以尽量大
for i in range(1<<30):
    r = gmpy2.iroot(m2+i*n, 2)
    if r[1]:
        # print(r[0])
        break
m = r[0]

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