知识点

小加密指数，指在加密的过程种选择的加密指数 $e$ 过小，这样虽然可以加快加密速度，但是太小的加密指数 $e$ 会降低安全性。

此攻击也不需要太多额外的知识，只需要对 RSA 的加解密过程清楚，同时知道 中国剩余定理 即可。

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$​ 。

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

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

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

一般 CRT

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

设有如下方程组：

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

求解 $x$ （mod 意义下。

算法实现流程如下：

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

进阶 CRT

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

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

将同余方程拆分开就是

于是就是有:

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

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

  1. 若 $\gcd(m_1, m_2)\nmid(b_2-b_1)$ 则上述方程无解。无这样的 $k_1, k_2$ 。
  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)可以改写为：

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

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

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

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

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

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

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

【定理】若特解 $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：很小加密指数

题目

这个加密够特殊吧？

1
2
3
e = 3
n = 162267107684520680616658268214653425403947694895807450296602255544899362088961545552140132476002338448697265870219623488852210492256482800532269570833622882699957743751935461061652686516411581455645846579846565715792357964591513209682801551321626641705585244453085108971211505680760057227078304773181670565603
c = 26548780750232836191381626267424083813723091734642456301506977315374618183483185631675083084982874420604304953873935170099488802810441932441779600028188109144370711070652399962736553819451031221793618501074481710410646849454236457143723293071714603969128409669018999111386858378040955543431625668156530617967

题解

这个题一看就发现不对，其特征就是加密指数 $e$ 很小，这很容易导致计算之后 $m^e<n$ 或者 $m^e<kn$ 其中 $k$ 在可枚举范围内。

于是可以轻松直接对密文 $c$ 进行开方，就能直接得到明文 $m$ 。

所以很简单的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
import gmpy2
from Crypto.Util.number import long_to_bytes

n = 162267107684520680616658268214653425403947694895807450296602255544899362088961545552140132476002338448697265870219623488852210492256482800532269570833622882699957743751935461061652686516411581455645846579846565715792357964591513209682801551321626641705585244453085108971211505680760057227078304773181670565603
c = 26548780750232836191381626267424083813723091734642456301506977315374618183483185631675083084982874420604304953873935170099488802810441932441779600028188109144370711070652399962736553819451031221793618501074481710410646849454236457143723293071714603969128409669018999111386858378040955543431625668156530617967

for i in range(1<<30):
    m = gmpy2.iroot(c+i*n, e)
    if m[1]:
        print(long_to_bytes(m[0]))
        break

#b'flag{baby_RSA_little_e_attack_panddinnnnng}'

例题2：小加密指数广播攻击

题目

再试试这个

1
2
3
4
5
6
7
8
9
10
11
[{"c": 7366067574741171461722065133242916080495505913663250330082747465383676893970411476550748394841437418105312353971095003424322679616940371123028982189502042, "e": 10, "n": 25162507052339714421839688873734596177751124036723831003300959761137811490715205742941738406548150240861779301784133652165908227917415483137585388986274803},
{"c": 21962825323300469151795920289886886562790942771546858500842179806566435767103803978885148772139305484319688249368999503784441507383476095946258011317951461, "e": 10, "n": 23976859589904419798320812097681858652325473791891232710431997202897819580634937070900625213218095330766877190212418023297341732808839488308551126409983193},
{"c": 6569689420274066957835983390583585286570087619048110141187700584193792695235405077811544355169290382357149374107076406086154103351897890793598997687053983, "e": 10, "n": 18503782836858540043974558035601654610948915505645219820150251062305120148745545906567548650191832090823482852604346478335353784501076761922605361848703623},
{"c": 4508246168044513518452493882713536390636741541551805821790338973797615971271867248584379813114125478195284692695928668946553625483179633266057122967547052, "e": 10, "n": 23383087478545512218713157932934746110721706819077423418060220083657713428503582801909807142802647367994289775015595100541168367083097506193809451365010723},
{"c": 22966105670291282335588843018244161552764486373117942865966904076191122337435542553276743938817686729554714315494818922753880198945897222422137268427611672, "e": 10, "n": 31775649089861428671057909076144152870796722528112580479442073365053916012507273433028451755436987054722496057749731758475958301164082755003195632005308493},
{"c": 17963313063405045742968136916219838352135561785389534381262979264585397896844470879023686508540355160998533122970239261072020689217153126649390825646712087, "e": 10, "n": 22246342022943432820696190444155665289928378653841172632283227888174495402248633061010615572642126584591103750338919213945646074833823905521643025879053949},
{"c": 1652417534709029450380570653973705320986117679597563873022683140800507482560482948310131540948227797045505390333146191586749269249548168247316404074014639, "e": 10, "n": 25395461142670631268156106136028325744393358436617528677967249347353524924655001151849544022201772500033280822372661344352607434738696051779095736547813043},
{"c": 15585771734488351039456631394040497759568679429510619219766191780807675361741859290490732451112648776648126779759368428205194684721516497026290981786239352, "e": 10, "n": 32056508892744184901289413287728039891303832311548608141088227876326753674154124775132776928481935378184756756785107540781632570295330486738268173167809047},
{"c": 8965123421637694050044216844523379163347478029124815032832813225050732558524239660648746284884140746788823681886010577342254841014594570067467905682359797, "e": 10, "n": 52849766269541827474228189428820648574162539595985395992261649809907435742263020551050064268890333392877173572811691599841253150460219986817964461970736553},
{"c": 13560945756543023008529388108446940847137853038437095244573035888531288577370829065666320069397898394848484847030321018915638381833935580958342719988978247, "e": 10, "n": 30415984800307578932946399987559088968355638354344823359397204419191241802721772499486615661699080998502439901585573950889047918537906687840725005496238621}]

题解

从上述的给出的已知条件可以知道，这个是必然是一种广播攻击——对同一个明文使用多个密钥进行了多组加密。

又由于都是使用的相同的加密指数 $e$ 同时比较小，所以，是 小加密指数广播攻击。

首先可以判断一下，这些 $n$​ 之间是否具有公因素，尝试看看能否进行分解。脚本如下：

1
2
3
4
for i in range(len(ns)):
    for i in range(i+1, len(ns)):
        if gcd(ns[i], ns[j]) > 1:
            print(i, j)

不出所料，给出的所有 $n$ 中是没有公因数的，（即以上的 $n$ 是两两互质的，因此无法利用公因数来进行分解。

那接下来我们来分析一下已知之间的关系：

发现什么了吗？如果还没有那就再换一个写法:

这不就是中国剩余定理刚好能解决的问题吗？轻轻松松求到 $x$ 满足的解。而且前面已经判断了上述的模数 $n_i$ 之间两两互质。

那么可以直接写出求出的解 $m^e \equiv (\sum_{i=1}^nb_i \times M_i^{-1}) \pmod M$​​​ 。​

然后再对 $m^e$ 按照第一种进行开方求解，即可得到明文 $m$ 。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
s = [{"c": 7366067574741171461722065133242916080495505913663250330082747465383676893970411476550748394841437418105312353971095003424322679616940371123028982189502042, "e": 10, "n": 25162507052339714421839688873734596177751124036723831003300959761137811490715205742941738406548150240861779301784133652165908227917415483137585388986274803},
{"c": 21962825323300469151795920289886886562790942771546858500842179806566435767103803978885148772139305484319688249368999503784441507383476095946258011317951461, "e": 10, "n": 23976859589904419798320812097681858652325473791891232710431997202897819580634937070900625213218095330766877190212418023297341732808839488308551126409983193},
{"c": 6569689420274066957835983390583585286570087619048110141187700584193792695235405077811544355169290382357149374107076406086154103351897890793598997687053983, "e": 10, "n": 18503782836858540043974558035601654610948915505645219820150251062305120148745545906567548650191832090823482852604346478335353784501076761922605361848703623},
{"c": 4508246168044513518452493882713536390636741541551805821790338973797615971271867248584379813114125478195284692695928668946553625483179633266057122967547052, "e": 10, "n": 23383087478545512218713157932934746110721706819077423418060220083657713428503582801909807142802647367994289775015595100541168367083097506193809451365010723},
{"c": 22966105670291282335588843018244161552764486373117942865966904076191122337435542553276743938817686729554714315494818922753880198945897222422137268427611672, "e": 10, "n": 31775649089861428671057909076144152870796722528112580479442073365053916012507273433028451755436987054722496057749731758475958301164082755003195632005308493},
{"c": 17963313063405045742968136916219838352135561785389534381262979264585397896844470879023686508540355160998533122970239261072020689217153126649390825646712087, "e": 10, "n": 22246342022943432820696190444155665289928378653841172632283227888174495402248633061010615572642126584591103750338919213945646074833823905521643025879053949},
{"c": 1652417534709029450380570653973705320986117679597563873022683140800507482560482948310131540948227797045505390333146191586749269249548168247316404074014639, "e": 10, "n": 25395461142670631268156106136028325744393358436617528677967249347353524924655001151849544022201772500033280822372661344352607434738696051779095736547813043},
{"c": 15585771734488351039456631394040497759568679429510619219766191780807675361741859290490732451112648776648126779759368428205194684721516497026290981786239352, "e": 10, "n": 32056508892744184901289413287728039891303832311548608141088227876326753674154124775132776928481935378184756756785107540781632570295330486738268173167809047},
{"c": 8965123421637694050044216844523379163347478029124815032832813225050732558524239660648746284884140746788823681886010577342254841014594570067467905682359797, "e": 10, "n": 52849766269541827474228189428820648574162539595985395992261649809907435742263020551050064268890333392877173572811691599841253150460219986817964461970736553},
{"c": 13560945756543023008529388108446940847137853038437095244573035888531288577370829065666320069397898394848484847030321018915638381833935580958342719988978247, "e": 10, "n": 30415984800307578932946399987559088968355638354344823359397204419191241802721772499486615661699080998502439901585573950889047918537906687840725005496238621}]

import gmpy2
from Crypto.Util.number import long_to_bytes

ns = [s[i]['n'] for i in range(len(s))]
cs = [s[i]['c'] for i in range(len(s))]
e = 10

M = 1
for i in ns:
    M *= i

Mi = [M//ns[i] for i in range(len(ns))]
    
c = 0
for i in range(len(cs)):
    c += (cs[i]*gmpy2.invert(Mi[i], ns[i])*Mi[i])
    c %= M

for i in range(len(ns)):
    assert c%ns[i] == cs[i], "CRT is Wrong"
    
for i in range(1<<30):
    m = gmpy2.iroot(c+i*M, e)
    if m[1]:
        print(long_to_bytes(m[0]))
        break
# b'flag{wo0_th3_tr4in_i5_leav1ng_g3t_on_it}'

思考

这里为什么要用一次 CRT 之后，再进行开方枚举答案，而不是在一开始随便取一组就开方枚举答案呢？

这里我想到的一个解释就是， CRT 之后的 $m^e \equiv c \pmod n$ 虽然和前面长得一样，但是此时的模数 $n$ 要大得多有木有？CRT 之后的 $n$ 是原来所有的 $n_i$​ 的乘积。

这样在同样的加密指数 $e$ 的前提下， 同一个 $m^e > n_i$ 是比较可能的，但是由于 $n \gg n_i$ 则 $m^e$ 开方之后，我们枚举的范围就更精确。

你想哈，假如对 $m^e$​ 开方之后的部分为 $r_0$​ 我们是不是要去枚举一个 $i$​ 不断判断 $r_0+i \times n_i$​ 但是当模数变大之后，一瞬就能从 $n_i$​ 提升至 $n$​ 。 此时当我们的枚举参数 $i$ 从 $0$ 变到 $1$ 时，我们的跨度是 $n$ ，而原来不论选择谁都需要枚举 $n \div n_i$ 次才能到这里。这节约的倍数是相等客观的。