前言

本来以为这是一道很简单的题,但是我太菜了犯了几个十分低级的错误(快哭了),感谢dbt给我指点迷津,膜拜大佬。

题目代码

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
import math
import sympy
from Crypto.Util.number import *
e = 65537
def get_p():
x = 11124440021748127159092076861405454814981575144744508857178576572929321435002942998531420985771090167262256877805902135304112271641074498386662361391760451
y = 11124440021748127159092076861405454814981575144744508857178576572929321435002942998531420985771090167262256877805902135304112271641074498386662361391661439
value_p = sympy.nextprime((math.factorial(y)) % x) # Hint:这里直接计算会溢出,请你仔细观察 x 和 y 的特征
return value_p
def get_q():
value = [getPrime(256)]
for i in range(1, 10):
value.append(sympy.nextprime(value[i - 1]))
print("value[-1] = ", value[-1])
# value[-1] = 80096058210213458444437404275177554701604739094679033012396452382975889905967
n = 1
for i in range(10):
n = n * value[i]
q = getPrime(512)
value_q = pow(q, e, n)
print("value_q = ", value_q)
# value_q = 5591130088089053683141520294620171646179623062803708281023766040254675625012293743465254007970358536660934858789388093688621793201658889399155357407224541324547522479617669812322262372851929223461622559971534394847970366311206823328200747893961649255426063204482192349202005330622561575868946656570678176047822163692259375233925446556338917358118222905050574458037965803154233167594946713038301249145097770337253930655681648299249481985768272321820718607757023350742647019762122572886601905212830744868048802864679734428398229280780215896045509020793530842541217790352661324630048261329493088812057300480085895399922301827190211956061083460036781018660201163819104150988531352228650991733072010425499238731811243310625701946882701082178190402011133439065106720309788819
return sympy.nextprime(q)
# this destroyes the rsa cryptosystem
p = get_p()
q = get_q()
m = int.from_bytes(open("flag.txt", "rb").read(), "big")
c = pow(m, e, p * q)
print("c = ", c)
# c = 110644875422336073350488613774418819991169603750711465190260581119043921549811353108399064284589038384540018965816137286856268590507418636799746759551009749004176545414118128330198437101472882906564195341277423007542422286760940374859966152871273887950174522820162832774361714668826122465471705166574184367478

解题思路

对于这道题,在已知p和q的情况下其实不难,所以解题中心放在对p和q的求解上。

阶乘求模(威尔逊定理的应用)

在对p的求取过程中,遇到了一个棘手的问题,就是y的阶乘模上x,其中x和y都是非常大的数,但是有一个比较重要的细节就是x-y=99012,不妨可以试着逆推求模,这里用到了一个定理

威尔逊定理:当P 为质数的时候,**( P − 2 ) ! = 1(modp)** 即 (p−1)!≡−1(modp)

image-20211029003443721

我们可以想到将阶乘运算转化成余数的运算,由于y与x的大小十分接近,故可以从 (x-1)! ≡ x-1 (modx)往前逆推,

由于 x-1可以写成-1,x-2可以写成-2,以此类推,我们所求的y!的余数即为(-1)*(-2)*...*(-99011)即为 -(99011)!。于是我们可以得到 -99011 * K ≡ x-1 (modx) 用拓展欧几里得定理很容易求出我们所需要的K。

对nextPrime的逆推

已知一个素数L,求其及其前九个素数。本来我一开始的思路是定义一个num从1递增,一直循环到L-num用for循环十次nextPrime得到素数L停止,乍看感觉没什么问题,但是我忽视了所求到的 L-num并不能保证一定为素数,况且这样计算的时间复杂度很高,遇到很大的数时计算很麻烦。

质数分布密度:素数分布越来越稀疏,但1e18内任意两个质数的差不会很大,好像有个人证明了不会超过246。

DBT告诉我可以定义一个起始量L-10000(更精确具体的话可以设置为L-2460),在L-10000到L内肯定含有超过10个素数,只需要将其添加进列表中,只取后10个即可,想法比我的要好得多。

解题代码

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
import gmpy2
from Crypto.Util.number import *
import sympy
import math
c = 110644875422336073350488613774418819991169603750711465190260581119043921549811353108399064284589038384540018965816137286856268590507418636799746759551009749004176545414118128330198437101472882906564195341277423007542422286760940374859966152871273887950174522820162832774361714668826122465471705166574184367478
e = 65537
list = []
value_q = 5591130088089053683141520294620171646179623062803708281023766040254675625012293743465254007970358536660934858789388093688621793201658889399155357407224541324547522479617669812322262372851929223461622559971534394847970366311206823328200747893961649255426063204482192349202005330622561575868946656570678176047822163692259375233925446556338917358118222905050574458037965803154233167594946713038301249145097770337253930655681648299249481985768272321820718607757023350742647019762122572886601905212830744868048802864679734428398229280780215896045509020793530842541217790352661324630048261329493088812057300480085895399922301827190211956061083460036781018660201163819104150988531352228650991733072010425499238731811243310625701946882701082178190402011133439065106720309788819
a = 80096058210213458444437404275177554701604739094679033012396452382975889905967
for i in range(a-2460,a+1):
if sympy.isprime(i):
list.append(i)
n_q = 1
phi_q = 1
for i in range(1,11):
n_q = n_q * list[-i]
for i in range(1,11):
phi_q = phi_q * (list[-i] - 1)
q = pow(value_q, gmpy2.invert(e, phi_q), n_q)
q = sympy.nextprime(q)
x = 11124440021748127159092076861405454814981575144744508857178576572929321435002942998531420985771090167262256877805902135304112271641074498386662361391760451
y = 11124440021748127159092076861405454814981575144744508857178576572929321435002942998531420985771090167262256877805902135304112271641074498386662361391661439
ooo = (-1 * math.factorial(99011)) % x
p = sympy.nextprime((gmpy2.invert(ooo, x) * (x-1) ) % x)
print(long_to_bytes(pow(c, gmpy2.invert(e, (p-1)*(q-1)), p*q)))

题目答案

b’flag{CRYPT0_1s_Interesting!}’