• 解压缩得Do_you_really_know_what_RSA_Is? .py
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
from Crypto.Util.number import *
m = bytes_to_long(b'flag{******}') 
#将字节字符串b'flag{******}'转换为长整数m，这是要加密的原始消息（flag）。
p = getPrime(512)
q = getPrime(512)
r = getPrime(512)
#随机生成大素数p、q、r
h1 = 1*p + 1*q + 1*r
h2 = 2*p + 3*q + 3*r
h3 = 9*p + 9*q + 6*r
print( "hint_of_pqr=" , h1 , h2 , h3 )
#思路 ：把p、q、r公式变形用h1、h2、h3表示
e = getPrime(64)
a_big_prime = getPrime( 512 )
hint = pow(a_big_prime,e,2**512)
print( "the big prime is: " , c )
print( "hint is:" , hint )

n = p*q*r
c = pow( m , e , n )
print( "c=" , c )

'''
hint_of_pqr= 26205997351166240405785097231436009350807507606268828636742615246287109077466822241186639293389573242216311668227098054599788791116215571416316140409352427 66860315641471130491119218972922785980480599406983109647358601581641695642878472456945137024883369147959034865118793676633880997281324220353834323524635144 213473629205254382083617791480463504155040467378518856042962121442859026373709762896295778597714884481459316375098621436229734548467857563069831689551454946
the big prime is:  11557301053448817361014126921662226367639845395602185765021724910056663884113570410496382266851427507275779260616871464855286322325118092388982283547918921
hint is: 10271913433365953528187318472631779008104540530202414129752768330046395509900224800993688431964630907432047820727638055487310601524087956924122431108238505
c= 116569284047193403361251336983936346094224289856857789287062750599584928427772025697885153355908857327470083147465892652988245017837819503727301904206404536314951181113506280048949514352483259762138034268916332027429633274027588317302925270485836816591363962835119659624022139707163858477460375467148571163549410771927644341667962740112294140641187548649921303016157469076294782957230926056116058301134087751871726212821846406513780951057663400249479830993970711
'''
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from Crypto.Util.number import long_to_bytes #导入必要的库：long_to_bytes：将长整数转换为字节串
from sympy.ntheory import discrete_log  #discrete_log：计算离散对数
h1 = 26205997351166240405785097231436009350807507606268828636742615246287109077466822241186639293389573242216311668227098054599788791116215571416316140409352427
h2 = 66860315641471130491119218972922785980480599406983109647358601581641695642878472456945137024883369147959034865118793676633880997281324220353834323524635144
h3 = 213473629205254382083617791480463504155040467378518856042962121442859026373709762896295778597714884481459316375098621436229734548467857563069831689551454946
thebigprime = 11557301053448817361014126921662226367639845395602185765021724910056663884113570410496382266851427507275779260616871464855286322325118092388982283547918921
hint = 10271913433365953528187318472631779008104540530202414129752768330046395509900224800993688431964630907432047820727638055487310601524087956924122431108238505
modulus = 2**512
c = 116569284047193403361251336983936346094224289856857789287062750599584928427772025697885153355908857327470083147465892652988245017837819503727301904206404536314951181113506280048949514352483259762138034268916332027429633274027588317302925270485836816591363962835119659624022139707163858477460375467148571163549410771927644341667962740112294140641187548649921303016157469076294782957230926056116058301134087751871726212821846406513780951057663400249479830993970711
e = discrete_log(modulus, hint, thebigprime) #计算离散对数：找到满足 g^e ≡ h (mod modulus) 的指数 e。
#这实际上是求解 h = g^e mod modulus 中的 e。
print(f"e = {e}")
p = 3 * h1 - h2
qr_sum = h1 - p 
q = (h3 - 9*p - 6*qr_sum) // 3
r = qr_sum - q
n = p * q * r
phi = (p-1) * (q-1) * (r-1)
d = pow(e, -1, phi) #计算 RSA 私钥 d，即 e 关于模 φ(n) 的模逆元，满足 e*d ≡ 1 mod φ(n)
m = pow(c, d, n) #使用私钥 d 解密密文 c，得到明文 m = c^d mod n。
flag = long_to_bytes(m)
print(f"Flag: {flag.decode()}") #将解密得到的整数 m 转换为字节串，然后解码为字符串，输出 flag。
  • 解得e = 18082004992516475581
  • 解得flag{we1c0me_2_SPC_enj0y_rs4!}
  • tips：要善于运用库，能极大改善求解效率。本题运用了sympy来求解离散对数。
  • 因为 2512 是 2 的幂，模运算在这里有一些数论特性（例如，当 a_big_prime_a___big___prime_ 是奇数时，它与 2 互素，欧拉定理在模 2k下需要稍微调整形式）。