知识点

本篇就是最简单的 RSA 入门类型题目，只需要知道 RSA 的最基本的加解密过程和基本原理就可。
攻击方式包括：直接分解模数 $n$，质因数 $p$ 或者 $q$ 泄漏，解密指数 $d$ 泄漏和 $\varphi(n)$ 泄漏造成的模数分解。

  1. 欧拉定理。
  2. 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$​ 。

例题

例题1：模数 n 可分解(已知分解结果)

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from secret import flag
from Crypto.Util.number import bytes_to_long, getPrime

p = getPrime(128)
q = getPrime(128)

e = 65537

n = p * q

m = bytes_to_long(flag)

c = pow(m, e, n)

print(n)
print(e)
print(c)

# 31344615479768915173540719256122268341192465800623830296449960072141078642261 
# 65537 
# 3476290363779523078131101220447326773638935374743120113826901434052723948231

题解

这题一看，生成的随机数很小，有很大的可能可以通过暴力进行分解。这里我们通过一个在线数据库网站即可进行分解。

也可以用 yafu，一分钟之内也可以分解出来。

yafu分解成功

解密代码如

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

p = 172989321383307954557066792282552136877
q = 181193932834246105866241884023765925193
n = 31344615479768915173540719256122268341192465800623830296449960072141078642261
e = 65537
c = 3476290363779523078131101220447326773638935374743120113826901434052723948231

phi = (p-1)*(q-1)
d = gmpy2.invert(e, phi)
m = pow(c, d, n)

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

例题2：因数 p 已知

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from secret import flag
from Crypto.Util.number import bytes_to_long, getPrime

p = 8732805609700428961977728300307834578984716107957507184236815607437365160744858849642036005621467071253904561328756761523027156570882550150725888578139489
q = getPrime(512)

e = 65537

n = p * q

m = bytes_to_long(flag)

c = pow(m, e, n)

print(n)
print(e)
print(c)

# 110620147936843490675437382107928855427899690438724954655667244500631031129926452508629309008114824770792286672878322594514725236490716999597775792160545784045599294476008935937100560954478336271256436790892545811364679284445004516901333306837700481611985117547191043331824433572019971991676051573889698729397 
# 65537 
# 65840510906473449503457590082032596011982792415848066857973316488072266076614207399890958565916768257491702823654770198180664027955377400458438818929615373300555000860875013329203093347903798438688365979399756288772085088152310582827491401438760143756158555060677308788209197795131175177830904675947999064171

题解

此题直接告诉了其中一个因数，则相当于告诉了分解模数 $n$​ 。

解密代码如下：

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

n = 110620147936843490675437382107928855427899690438724954655667244500631031129926452508629309008114824770792286672878322594514725236490716999597775792160545784045599294476008935937100560954478336271256436790892545811364679284445004516901333306837700481611985117547191043331824433572019971991676051573889698729397
p = 8732805609700428961977728300307834578984716107957507184236815607437365160744858849642036005621467071253904561328756761523027156570882550150725888578139489
q = n // p
e = 65537
c = 65840510906473449503457590082032596011982792415848066857973316488072266076614207399890958565916768257491702823654770198180664027955377400458438818929615373300555000860875013329203093347903798438688365979399756288772085088152310582827491401438760143756158555060677308788209197795131175177830904675947999064171

phi = (p-1)*(q-1)
d = gmpy2.invert(e, phi)
m = pow(c, d, n)

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

例题3：私钥 d 泄露

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from secret import flag
from Crypto.Util.number import bytes_to_long, getPrime
from gmpy2 import invert

p = getPrime(512)
q = getPrime(512)

e = 65537

n = p * q

m = bytes_to_long(flag)

c = pow(m, e, n)

print(n)
print(e)
print(c)
print(invert(e, (p-1)*(q-1)))

# 141602986834016599129980891619360975064958963767965728499941571957953305554161871397930120918818875934396152526093406011570905018737302335290924109977332265934612530354425893055738541676088469955068966218855145034196200639395962367800875462307031643041089880801817013018616504640495273845630154130726423418269 
# 65537 
# 57044913730013937794646567056447346464658747258470876447731610106315929032553175772200785945759108295301077223717974436621308969700717997203606080499049868608174558650835009538117994367530963058969153314670672899509642598482734793918027038322990918829450805698157716579738787121084287464947317631739331706158
# 62095125480610999014244180298897036214533098245686666636553715252447015400782123412806715978545488433688008719462263993874242631391295479102276088265232636628430513991348779160570519230943650004987550258033428943041746433555303850460868755994859141775363877389569651451584333403562275241930766273321755272885

题解

这题给出了 invert(e, (p-1)*(q-1)) ，事实上这个就是密钥生成时，私钥 $d$ 的生成公式。

于是解密脚本如下

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

n = 141602986834016599129980891619360975064958963767965728499941571957953305554161871397930120918818875934396152526093406011570905018737302335290924109977332265934612530354425893055738541676088469955068966218855145034196200639395962367800875462307031643041089880801817013018616504640495273845630154130726423418269
d = 62095125480610999014244180298897036214533098245686666636553715252447015400782123412806715978545488433688008719462263993874242631391295479102276088265232636628430513991348779160570519230943650004987550258033428943041746433555303850460868755994859141775363877389569651451584333403562275241930766273321755272885
c = 57044913730013937794646567056447346464658747258470876447731610106315929032553175772200785945759108295301077223717974436621308969700717997203606080499049868608174558650835009538117994367530963058969153314670672899509642598482734793918027038322990918829450805698157716579738787121084287464947317631739331706158

m = pow(c, d, n)

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

例题4： $\varphi(n)$ 泄露

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from secret import flag
from Crypto.Util.number import bytes_to_long, getPrime
from gmpy2 import invert

p = getPrime(512)
q = getPrime(512)

e = 65537

n = p * q

m = bytes_to_long(flag)

c = pow(m, e, n)

print(n)
print(e)
print(c)
print((p-1)*(q-1))

# 87897618110268424293247941925450117030644321908511327125277310242594558445767417574406439506610123256810843226899454274184858374296837361756440090555901522685638504101112242134369858480413701679118890404344783794537482694715817482359770001028898237815308988409694000541114163555205437299929085680454790939147
# 65537
# 58170563776612430128013733127102671481861563347823185804380756844371151935092015482743762338637549223809776738997081543522658816504652108911751844081323026239561694295062609331585654368007824756943795364408371563802683702288349217556256503782424483215676894385926173101967102201164582753155113655268477052789
# 87897618110268424293247941925450117030644321908511327125277310242594558445767417574406439506610123256810843226899454274184858374296837361756440090555901503884788771872580894052419102603576216008936699692554296720610481791083045747415692118748431614193373387407751440581003302782431002003940339349357103389360

题解

这个直接暴露了 $\varphi(n)$ ，于是可以直接求解。

解密脚本如下：

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

n = 87897618110268424293247941925450117030644321908511327125277310242594558445767417574406439506610123256810843226899454274184858374296837361756440090555901522685638504101112242134369858480413701679118890404344783794537482694715817482359770001028898237815308988409694000541114163555205437299929085680454790939147
c = 58170563776612430128013733127102671481861563347823185804380756844371151935092015482743762338637549223809776738997081543522658816504652108911751844081323026239561694295062609331585654368007824756943795364408371563802683702288349217556256503782424483215676894385926173101967102201164582753155113655268477052789
e = 65537

phi = 87897618110268424293247941925450117030644321908511327125277310242594558445767417574406439506610123256810843226899454274184858374296837361756440090555901503884788771872580894052419102603576216008936699692554296720610481791083045747415692118748431614193373387407751440581003302782431002003940339349357103389360

d = gmpy2.invert(e, phi)
m = pow(c, d, n)

flag = long_to_bytes(m)
print(flag)
b'flag{baby_RSA_known_phi}'

知识点2

本篇严格来讲只是考察欧拉定理的掌握和解二元一次方程的能力。其实和 RSA 并么有啥关系，但是由于原理和 RSA 的原理一样，所以计算过程非常有关，所以放到一起来讲。

  1. 欧拉定理。
  2. 解二元一次方程。
  3. 解一元二次方程。

欧拉定理

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

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

解二元一次方程

通常有代入消元法和加减消元法。

解一元二次方程

大家都是成年人了，直接求根公式吧，也可以用现成的轮子。

例题

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.Util.number import getPrime

p = getPrime(512)
q = getPrime(512)

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

flag = "flag{" + str(p) + str(q) + "}"

print(n)
print(phi)

# 114610032604823370847322751475526488576563573837378970448429708892128907737858338999931254224607838312843660783299757860732436952582990289323390277642196169278727358918555581619468741233307808207120178449820279260916804151169608404474508120216169585997156378783999861975250902462608890221976540709862001715939
# 114610032604823370847322751475526488576563573837378970448429708892128907737858338999931254224607838312843660783299757860732436952582990289323390277642196147658659530544842874173182667189964278694274126753572835170140730614726976454718569545199964811997901678328952318975367382587248995887110764557026130128960

题解

读完代码可以知道，此题先随机生成了两个 512 位的质数 $p, q$ ，然后计算了两者的乘积 $n = p \times q$​ ，计算了 $phi = (p-1) \times (q-1)$ ，很显然这就是 $\varphi(n)$ 。然后需要求的 flag 就是质数 $p, q$ 两者的拼接。

所以问题很明显了，就是需要求解质数 $p$ 和 $q$​ 。直接分解模数 $n$ 也是不现实的，所以还是应该从已知入手进行分析。

现在来考虑已知条件：

发现上面是两个方程和两个未知数，故理论上我们是可以直接进行求解的（二元一次方程组。

现在来进行变形：

于是看到这个地方，如果把 $p$ 和 $q$​​ 看作一个一元二次方程的两个根，则我们已知的恰好是两根之和和两根之积。

即韦达定理 。故 $p$ 和 $q$ 就刚好是方程 $x^2 + (\varphi(n)-n-1) \times x + n = 0$ 的两个根。

判断方程是否有解 $\Delta = (\varphi(n) - n - 1) ^ 2 - 4 \times n$ 与 $0$ 的关系。但是很显然，这里必然有解。

于是，直接求根公式可得 $x = \frac{-(\varphi(n) - n - 1) \pm \sqrt{(\varphi(n) - n - 1) ^ 2 - 4 \times n}}{2}$ 。

于是，顺利求得 $p, q$ 。

解密脚本如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import gmpy2

n = 114610032604823370847322751475526488576563573837378970448429708892128907737858338999931254224607838312843660783299757860732436952582990289323390277642196169278727358918555581619468741233307808207120178449820279260916804151169608404474508120216169585997156378783999861975250902462608890221976540709862001715939
phi = 114610032604823370847322751475526488576563573837378970448429708892128907737858338999931254224607838312843660783299757860732436952582990289323390277642196147658659530544842874173182667189964278694274126753572835170140730614726976454718569545199964811997901678328952318975367382587248995887110764557026130128960

a = 1
b = phi - n - 1
c = n

assert gmpy2.iroot(b**2-4*a*c, 2)[1]

p = (-b+gmpy2.iroot(b**2-4*a*c, 2)[0])//(2*a)
q = (-b-gmpy2.iroot(b**2-4*a*c, 2)[0])//(2*a)

assert p*q == n

print("flag{" + str(p) + str(q) + "}")
# flag{123089670751538941332343103488959348536223226360070011022835691826373621540820015713006673406968627105082149335683847299166142282321540615903397262269686099311100753219818574211975725147408675890523415689246341807206890899080477867754367274348864077136544192240113974615153603261131662180804185813109644618371}