RSAisEasy Writeup

原题地址：HackTheBox - RSAisEasy

之前做过这个题，是与另一位朋友一起分析的，但是当时没有写 writeup，于是再梳理一遍。

从标题可以看出，这道题与 RSA 有点相关，因此会用到一部分基于 RSA 公式的数学分析。（说实话，在拉着咱朋友一起来分析数学部分之前，是有那么一点不敢做这题的……）

0. 题目内容

题目提供了一个 zip 文件，解压后有两个文件

# output.txt

n1: 101302608234750530215072272904674037076286246679691423280860345380727387460347553585319149306846617895151397345134725469568034944362725840889803514170441153452816738520513986621545456486260186057658467757935510362350710672577390455772286945685838373154626020209228183673388592030449624410459900543470481715269
c1: 92506893588979548794790672542461288412902813248116064711808481112865246689691740816363092933206841082369015763989265012104504500670878633324061404374817814507356553697459987468562146726510492528932139036063681327547916073034377647100888763559498314765496171327071015998871821569774481702484239056959316014064
c2: 46096854429474193473315622000700040188659289972305530955007054362815555622172000229584906225161285873027049199121215251038480738839915061587734141659589689176363962259066462128434796823277974789556411556028716349578708536050061871052948425521408788256153194537438422533790942307426802114531079426322801866673
(n1 * E) + n2: 601613204734044874510382122719388369424704454445440856955212747733856646787417730534645761871794607755794569926160226856377491672497901427125762773794612714954548970049734347216746397532291215057264241745928752782099454036635249993278807842576939476615587990343335792606509594080976599605315657632227121700808996847129758656266941422227113386647519604149159248887809688029519252391934671647670787874483702292498358573950359909165677642135389614863992438265717898239252246163

# RSAisEasy.py

#!/usr/bin/env python3
from Crypto.Util.number import bytes_to_long, getPrime
from secrets import flag1, flag2
from os import urandom

flag1 = bytes_to_long(flag1)
flag2 = bytes_to_long(flag2)

p, q, z = [getPrime(512) for i in range(3)]

e = 0x10001

n1 = p * q
n2 = q * z

c1 = pow(flag1, e, n1)
c2 = pow(flag2, e, n2)

E = bytes_to_long(urandom(69))

print(f'n1: {n1}')
print(f'c1: {c1}')
print(f'c2: {c2}')
print(f'(n1 * E) + n2: {n1 * E + n2}')

1. 眼盯侦！

首先观察提供的代码，注意到 flag1 和 flag2 两个变量，那我们接下来的目标就是还原这两个变量了。

接下来生成了 3 个质数，分别是 p, q, z，e 使用的是老熟人 0x10001。

然后使用 p, q, z 计算了 n1, n2。使用 n1, n2 分别加密了 flag1, flag2，得到 c1, c2。

最后生成了一个随机数 E，并输出了 n1, c1, c2, (n1 * E) + n2。

2. RSA 公式

这部分就来自 RSA加密算法 - 维基百科，自由的百科全书 了，当时咱也是从 Wiki 上现学的。注意这里省略了一些过程。

加密算法

$$
c = n^e \pmod N
$$

解密算法

$$
n = c^d \pmod N
$$

密钥相关的公式

$$
N = pq,
$$

$$
r = (p-1)(q-1)
$$

$$
ed \equiv 1 \pmod r
$$

从公式可以看出，要解密 c1 和 c2，需要知道 d1, d2，而 d1, d2 是由 e, r1, r2 计算逆元得到的。e 是已知的，现在要求的就是 r1, r2 了。

3. r?

观察代码，发现

$$
n1 = pq, n2 = qz
$$

由 $p, q, z \in \mathbb{P}$ 得

$$
q = \gcd(n1, n2)
$$

$$
p = \frac{n1}{q}, z = \frac{n2}{q}
$$

这样，拿到 p, q, z 后，就可以计算出 r1, r2 了。

4. d!

有了 r1, r2 后，就可以计算出 d1, d2 了。逆元有几种求法，这里我们选择 扩展欧几里得算法。

# 输入 a=e, b=r, 输出 x=d
def exgcd(a, b):
    if b == 0:
        x = 1
        y = 0
        return x, y
    x1, y1 = exgcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    return x, y

5. n2

上面的过程需要一个值 n2，而 n2 不是题目直接给出的，我们需要想办法找出来。

注意到题目提供了 E 和 (n1 * E) + n2，我们可以通过这个值来找到 n2。

为方便展示过程，我们将 (n1 * E) + n2 记为 nE。

$$
n2 \equiv nE \pmod {n1}
$$

即

$$
\def\mod{\text{ mod }}
n2 = nE \mod n1 + n1 \cdot k
$$

其中 k 是未知的，你可以直接猜测 k = 0 即 n2 = nE % n1，但我还是想证明它。

注意到 n2 是两个 getPrime(512) 相乘，因此 0 < k < 2^1024。接下来用代码测试 k 可以的取值。

n1 = 101302608234750530215072272904674037076286246679691423280860345380727387460347553585319149306846617895151397345134725469568034944362725840889803514170441153452816738520513986621545456486260186057658467757935510362350710672577390455772286945685838373154626020209228183673388592030449624410459900543470481715269
ne = 601613204734044874510382122719388369424704454445440856955212747733856646787417730534645761871794607755794569926160226856377491672497901427125762773794612714954548970049734347216746397532291215057264241745928752782099454036635249993278807842576939476615587990343335792606509594080976599605315657632227121700808996847129758656266941422227113386647519604149159248887809688029519252391934671647670787874483702292498358573950359909165677642135389614863992438265717898239252246163

for k in (-1, 0, 1): 
    n2 = ne % n1 + n1 * k
    print(k, 0 < n2 < 2**1024, n2)

得到运行结果：

-1 False -1165705193327509223646449377936290710713049039655470307166720571005763031384300382036555332312895310759950336222328427276047951088897538178479073322538390413188948373749356597618939249379728523681999077958826657180398342840434533058980374881243302617523598758343538175613136045714345227586034384136094220432
0 True 100136903041423020991425823526737746365573197640035952973693624809721624428963253203282593974533722584391447008912397042291986993273828302711324440847902763039627790146764630023926517236880457533976468679976683705170312329736955922713306570804595070537102421450884645497775455984735279182873866159334387494837
1 False 201439511276173551206498096431411783441859444319727376254553970190449011889310806788601743281380340479542844354047122511860021937636554143601127955018343916492444528667278616645471973723140643591634936437912194067521023002314346378485593516490433443691728441660112829171164048015184903593333766702804869210106

因此 k = 0 而 n2 = nE % n1。

6. 结束了？

按照上述流程编写代码：

from math import gcd

e = 0x10001
n1 = 101302608234750530215072272904674037076286246679691423280860345380727387460347553585319149306846617895151397345134725469568034944362725840889803514170441153452816738520513986621545456486260186057658467757935510362350710672577390455772286945685838373154626020209228183673388592030449624410459900543470481715269
ne = 601613204734044874510382122719388369424704454445440856955212747733856646787417730534645761871794607755794569926160226856377491672497901427125762773794612714954548970049734347216746397532291215057264241745928752782099454036635249993278807842576939476615587990343335792606509594080976599605315657632227121700808996847129758656266941422227113386647519604149159248887809688029519252391934671647670787874483702292498358573950359909165677642135389614863992438265717898239252246163
c1 = 92506893588979548794790672542461288412902813248116064711808481112865246689691740816363092933206841082369015763989265012104504500670878633324061404374817814507356553697459987468562146726510492528932139036063681327547916073034377647100888763559498314765496171327071015998871821569774481702484239056959316014064
c2 = 46096854429474193473315622000700040188659289972305530955007054362815555622172000229584906225161285873027049199121215251038480738839915061587734141659589689176363962259066462128434796823277974789556411556028716349578708536050061871052948425521408788256153194537438422533790942307426802114531079426322801866673

n2 = ne % n1  # 用前面的推导计算 n2

q = gcd(n1, n2)  # 计算 p, q, z
p, z = n1 // q, n2 // q

r1, r2 = (p - 1) * (q - 1), (q - 1) * (z - 1)  # 计算 r1, r2

def exgcd(a, b):  # 用来求逆元的扩展欧几里得算法
    if b == 0:
        x = 1
        y = 0
        return x, y
    x1, y1 = exgcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    return x, y

d1, d2 = exgcd(e, r1)[0], exgcd(e, r2)[0]
d1, d2 = d1 % r1, d2 % r2  # exgcd 算出来可能是负数，所以再 mod 一次

flag1, flag2 = pow(c1, d1, n1), pow(c2, d2, n2)

# 一个比较拙劣但是能跑的 int to bytes
flag_hex = hex(flag1)[2:] + hex(flag2)[2:]
flag = bytes.fromhex(flag_hex).decode()
print(flag)

运行上述代码，得到 flag：

HTB{1_m1ght_h4v3_m3ss3d_uP_jU$t_4_l1ttle_b1t?}

参考资料

1. RSA加密算法 - 维基百科，自由的百科全书
2. 乘法逆元 - OI Wiki