problem
from gmpy2 import *
from Crypto.Util.number import *
flag = '****************************'
flag = {"asfajgfbiagbwe"}
p = getPrime(2048)
q = getPrime(2048)
m1 = bytes_to_long(bytes(flag.encode()))
e1e2 = 3087
n = p*q
print()
flag1 = pow(m1,e1,n)
flag2 = pow(m1,e2,n)
print('flag1= '+str(flag1))
print('flag2= '+str(flag2))
print('n= '+str(n))
#flag1= 463634070971821449698012827631572665302589213868521491855038966879005784397309389922926838028598122795187584361359142761652619958273094398420314927073008031088375892957173280915904309949716842152249806486027920136603248454946737961650252641668562626310035983343018705370077783879047584582817271215517599531278507300104564011142229942160380563527291388260832749808727470291331902902518196932928128107067117198707209620169906575791373793854773799564060536121390593687449884988936522369331738199522700261116496965863870682295858957952661531894477603953742494526632841396338388879198270913523572980574440793543571757278020533565628285714358815083303489096524318164071888139412436112963845619981511061231001617406815056986634680975142352197476024575809514978857034477688443230263761729039797859697947454810551009108031457294164840611157524719173343259485881089252938664456637673337362424443150013961181619441267926981848009107466576314685961478748352388452114042115892243272514245081604607798243817586737546663059737344687130881861357423084448027959893402445303299089606081931041217035955143939567456782107203447898345284731038150377722447329202078375870541529539840051415759436083384408203659613313535094343772238691393447475364806171594
#flag2= 130959534275704453216282334815034647265875632781798750901627773826812657339274362406246297925411291822193191483409847323315110393729020700526946712786793380991675008128561863631081095222226285788412970362518398757423705216112313533155390315204875516645459370629706277876211656753247984282379731850770447978537855070379324935282789327428625259945250066774049650951465043700088958965762054418615838049340724639373351248933494355591934236360506778496741051064156771092798005112534162050165095430065000827916096893408569751085550379620558282942254606978819033885539221416335848319082054806148859427713144286777516251724474319613960327799643723278205969253636514684757409059003348229151341200451785288395596484563480261212963114071064979559812327582474674812225260616757099890896900340007990585501470484762752362734968297532533654846190900571017635959385883945858334995884341767905619567505341752047589731815868489295690574109758825021386698440670611361127170896689015108432408490763723594673299472336065575301681055583084547847733168801030191262122130369687497236959760366874106043801542493392227424890925595734150487586757484304609945827925762382889592743709682485229267604771944535469557860120878491329984792448597107256325783346904408
#n= 609305637099654478882754880905638123124918364116173050874864700996165096776233155524277418132679727857702738043786588380577485490575591029930152718828075976000078971987922107645530323356525126496562423491563365836491753476840795804040219013880969539154444387313029522565456897962200817021423704204077133003361140660038327458057898764857872645377236870759691588009666047187685654297678987435769051762120388537868493789773766688347724903911796741124237476823452505450704989455260077833828660552130714794889208291939055406292476845194489525212129635173284301782141617878483740788532998492403101324795726865866661786740345862631916793208037250277376942046905892342213663197755010315060990871143919384283302925469309777769989798197913048813940747488087191697903624669415774198027063997058701217124640082074789591591494106726857376728759663074734040755438623372683762856958888826373151815914621262862750497078245369680378038995425628467728412953392359090775734440671874387905724083226246587924716226512631671786591611586774947156657178654343092123117255372954798131265566301316033414311712092913492774989048057650627801991277862963173961355088082419091848569675686058581383542877982979697235829206442087786927939745804017455244315305118437
共模攻击，但只知道两个e的乘积，可分解得到：
e_fac = [3, 3, 7, 7, 7]
在多种组合方式中肯定存在不互素的情况，对应进行开方即可：
e1e2 = 3087
e_fac = [3, 3, 7, 7, 7]
fac = [3, 7, 3*3, 3*7, 7*7, 3*3*7, 3*7*7, 7*7*7, 3*3*7*7, 3*7*7*7, 3*3*7*7*7]
c1= ...
c2= ...
n= ...
for e1 in fac:
e2 = e1e2 // e1
s = gcdext(e1, e2)
m1 = pow(c1, s[1], n)
m2 = pow(c2, s[2], n)
m = (m1 * m2) % n
m = iroot(m, gcd(e1,e2))[0]
print(long_to_bytes(m))
考点
共模攻击e不互素
Chal
题目给了一个文件夹，包含了100个.pem文件和100个msgi文件（没有后缀），公钥私钥类型。
读取方法：
n = []
e = []
c = []
file_list1 = glob.glob(r'C:\Users\lenovo\Desktop\text\*.pem')
for file_path in file_list1:
public_key = RSA.importKey(open(file_path, 'rb').read())
n.append(public_key.n)
e.append(public_key.e)
file_list2 = glob.glob(rb'C:\Users\lenovo\Desktop\text\msg*')
for file_path in file_list2:
with open(file_path, 'rb') as f:
msg = bytes_to_long(f.read())
c.append(msg)
一共一百组数据，e均为65537，找下n的公因数，找到一组，但正常解RSA解不出，这属于PKCS1_OAEP模式下的RSA加密，需手动构造私钥去解密密文：
n = [...]
e = 65537
c = [...]
for i in range(len(n)):
for j in range(i+1,len(n)):
if gcd(n[i],n[j]) != 1:
p = gcd(n[i],n[j])
q = n[j] // p
phi = (p-1)*(q-1)
d = invert(e, phi)
privkey = RSA.construct((int(p * q), int(e), int(d), int(p), int(q)))
key = PKCS1_OAEP.new(privkey)
flag = key.decrypt(long_to_bytes(c[j]))
print(flag)
2021第五空间signin
from Crypto.Util.number import *
from secret import flag
p = getPrime(512)
q = getPrime(512)
n = p * q
e = 0x10001
x = (p ^ q) & ((1 << 400) - 1)
m = bytes_to_long(flag)
c = pow(m,e,n)
print("c = " + str(c))
print("e = " + str(e))
print("n = " + str(n))
print("x = " + str(x))
'''
c = 86415476382906786465939442398992406348852252355326334785583474583480585659663836032856765037225261433532613020730103955916772373674295180495452293421279237222544308971840820110279355118064931506637793547489441433938707518241461449059717326341918746156620038847745542794560335988858156929013492541794032580255
e = 65537
n = 166337085427556441543394334802135957169988266794453522153008810336368247289697353242192853337017363111987395194428553050681210209730724596529629525357502302165396675392000087988956194589350195512264427901330860811469484473725396354231555692283910488095918243519370430703255279433498479943391876108577325840381
x = 2509898544460604898497702985357222191225421344430742181152035006910161802193623236888758239071502008180363546424715261788
'''
x = (p ^ q) & ((1 << 400) - 1)
知道pq异或的低400位，可从低位开始爆破出p的低400位，然后构造copper筛选正确的p：
c = 86415476382906786465939442398992406348852252355326334785583474583480585659663836032856765037225261433532613020730103955916772373674295180495452293421279237222544308971840820110279355118064931506637793547489441433938707518241461449059717326341918746156620038847745542794560335988858156929013492541794032580255
e = 65537
n = 166337085427556441543394334802135957169988266794453522153008810336368247289697353242192853337017363111987395194428553050681210209730724596529629525357502302165396675392000087988956194589350195512264427901330860811469484473725396354231555692283910488095918243519370430703255279433498479943391876108577325840381
x = 2509898544460604898497702985357222191225421344430742181152035006910161802193623236888758239071502008180363546424715261788
def findp(p,rp):
l = len(p)
if l == 400:
rp.append(int(p,2))
else:
pp = int(p,2)
qq = (x^^pp)%2**l
if pp*qq%2**l == n%2**l:#p、q低位相乘与n的低位比较
findp('1'+p,rp)
findp('0'+p,rp)
rp=[]
findp('1',rp)
#从最低位开始爆破，通过输出bin(n)，知道n的最低位为1，那么p和q的最低位至少有一个为1
for i in range(len(rp)):
PR.<x>=PolynomialRing(Zmod(n))
f=pow(2,400)*x+rp[i]
f=f.monic()
root=f.small_roots(X=2^112,beta=0.4)
if root:
p=rp[i]+pow(2,400)*int(root[0])
q=n//p
if p*q==n:
print(p)
p出了就不说了。
2021第五空间ecc
print 'Try to solve the 3 ECC'
from secret import flag
from Crypto.Util.number import *
assert(flag[:5]=='flag{')
flag = flag[5:-1]
num1 = bytes_to_long(flag[:7])
num2 = bytes_to_long(flag[7:14])
num3 = bytes_to_long(flag[14:])
def ECC1(num):
p = 146808027458411567
A = 46056180
B = 2316783294673
E = EllipticCurve(GF(p),[A,B])
P = E.random_point()
Q = num*P
print E
print 'P:',P
print 'Q:',Q
def ECC2(num):
p = 1256438680873352167711863680253958927079458741172412327087203
#import random
#A = random.randrange(389718923781273978681723687163812)
#B = random.randrange(816378675675716537126387613131232121431231)
A = 377999945830334462584412960368612
B = 604811648267717218711247799143415167229480
E = EllipticCurve(GF(p),[A,B])
P = E.random_point()
Q = num*P
print E
print 'P:',P
print 'Q:',Q
factors, exponents = zip(*factor(E.order()))
primes = [factors[i] ^ exponents[i] for i in range(len(factors))][:-1]
print primes
dlogs = []
for fac in primes:
t = int(int(P.order()) / int(fac))
dlog = discrete_log(t*Q,t*P,operation="+")
dlogs += [dlog]
print("factor: "+str(fac)+", Discrete Log: "+str(dlog)) #calculates discrete logarithm for each prime order
print num
print crt(dlogs,primes)
def ECC3(num):
p = 0xd3ceec4c84af8fa5f3e9af91e00cabacaaaecec3da619400e29a25abececfdc9bd678e2708a58acb1bd15370acc39c596807dab6229dca11fd3a217510258d1b
A = 0x95fc77eb3119991a0022168c83eee7178e6c3eeaf75e0fdf1853b8ef4cb97a9058c271ee193b8b27938a07052f918c35eccb027b0b168b4e2566b247b91dc07
B = 0x926b0e42376d112ca971569a8d3b3eda12172dfb4929aea13da7f10fb81f3b96bf1e28b4a396a1fcf38d80b463582e45d06a548e0dc0d567fc668bd119c346b2
E = EllipticCurve(GF(p),[A,B])
P = E.random_point()
Q = num*P
print E
print 'P:',P
print 'Q:',Q
ECC1(num1)
print '=============='
ECC2(num2)
print '=============='
ECC3(num3)
#Try to solve the 3 ECC
Elliptic Curve defined by y^2 = x^3 + 46056180*x + 2316783294673 over Finite Field of size 146808027458411567
P: (119851377153561800 : 50725039619018388 : 1)
Q: (22306318711744209 : 111808951703508717 : 1)
==============
Elliptic Curve defined by y^2 = x^3 + 377999945830334462584412960368612*x + 604811648267717218711247799143415167229480 over Finite Field of size 1256438680873352167711863680253958927079458741172412327087203
P: (550637390822762334900354060650869238926454800955557622817950 : 700751312208881169841494663466728684704743091638451132521079 : 1)
Q: (1152079922659509908913443110457333432642379532625238229329830 : 819973744403969324837069647827669815566569448190043645544592 : 1)
==============
Elliptic Curve defined by y^2 = x^3 + 490963434153515882934487973185142842357175523008183292296815140698999054658777820556076794490414610737654365807063916602037816955706321036900113929329671*x + 7668542654793784988436499086739239442915170287346121645884096222948338279165302213440060079141960679678526016348025029558335977042712382611197995002316466 over Finite Field of size 11093300438765357787693823122068501933326829181518693650897090781749379503427651954028543076247583697669597230934286751428880673539155279232304301123931419
P: (10121571443191913072732572831490534620810835306892634555532657696255506898960536955568544782337611042739846570602400973952350443413585203452769205144937861 : 8425218582467077730409837945083571362745388328043930511865174847436798990397124804357982565055918658197831123970115905304092351218676660067914209199149610 : 1)
Q: (964864009142237137341389653756165935542611153576641370639729304570649749004810980672415306977194223081235401355646820597987366171212332294914445469010927 : 5162185780511783278449342529269970453734248460302908455520831950343371147566682530583160574217543701164101226640565768860451999819324219344705421407572537 : 1)
ECC1：
直接离散对数求解：
p = 146808027458411567
A = 46056180
B = 2316783294673
E = EllipticCurve(GF(p),[A,B])
P = E(119851377153561800,50725039619018388)
Q = E(22306318711744209,111808951703508717)
num1 = P.discrete_log(Q)
print(num1)
#13566003730592612
ECC2：
阶部分光滑，直接用后面给的hellman算法代码：
A = 377999945830334462584412960368612
B = 604811648267717218711247799143415167229480
E = EllipticCurve(GF(p),[A,B])
P = E(550637390822762334900354060650869238926454800955557622817950,700751312208881169841494663466728684704743091638451132521079)
Q = E(1152079922659509908913443110457333432642379532625238229329830,819973744403969324837069647827669815566569448190043645544592)
factors, exponents = zip(*factor(E.order()))
primes = [factors[i] ^ exponents[i] for i in range(len(factors))][:-1]
print(primes)
dlogs = []
for fac in primes:
t = int(int(P.order()) // int(fac))
dlog = discrete_log(t*Q,t*P,operation="+")
dlogs += [dlog]
print("factor: "+str(fac)+", Discrete Log: "+str(dlog)) #calculates discrete logarithm for each prime order
print(crt(dlogs,primes))
#16093767336603949
ECC3：
阶数与p相等，smart’s attack，套用攻击脚本：
p = 0xd3ceec4c84af8fa5f3e9af91e00cabacaaaecec3da619400e29a25abececfdc9bd678e2708a58acb1bd15370acc39c596807dab6229dca11fd3a217510258d1b
A = 0x95fc77eb3119991a0022168c83eee7178e6c3eeaf75e0fdf1853b8ef4cb97a9058c271ee193b8b27938a07052f918c35eccb027b0b168b4e2566b247b91dc07
B = 0x926b0e42376d112ca971569a8d3b3eda12172dfb4929aea13da7f10fb81f3b96bf1e28b4a396a1fcf38d80b463582e45d06a548e0dc0d567fc668bd119c346b2
E = EllipticCurve(GF(p),[A,B])
P = E(10121571443191913072732572831490534620810835306892634555532657696255506898960536955568544782337611042739846570602400973952350443413585203452769205144937861,8425218582467077730409837945083571362745388328043930511865174847436798990397124804357982565055918658197831123970115905304092351218676660067914209199149610)
Q = E(964864009142237137341389653756165935542611153576641370639729304570649749004810980672415306977194223081235401355646820597987366171212332294914445469010927,5162185780511783278449342529269970453734248460302908455520831950343371147566682530583160574217543701164101226640565768860451999819324219344705421407572537)
def SmartAttack(P,Q,p):
E = P.curve()
Eqp = EllipticCurve(Qp(p, 2), [ ZZ(t) + randint(0,p)*p for t in E.a_invariants() ])
P_Qps = Eqp.lift_x(ZZ(P.xy()[0]), all=True)
for P_Qp in P_Qps:
if GF(p)(P_Qp.xy()[1]) == P.xy()[1]:
break
Q_Qps = Eqp.lift_x(ZZ(Q.xy()[0]), all=True)
for Q_Qp in Q_Qps:
if GF(p)(Q_Qp.xy()[1]) == Q.xy()[1]:
break
p_times_P = p*P_Qp
p_times_Q = p*Q_Qp
x_P,y_P = p_times_P.xy()
x_Q,y_Q = p_times_Q.xy()
phi_P = -(x_P/y_P)
phi_Q = -(x_Q/y_Q)
k = phi_Q/phi_P
return ZZ(k)
num3 = SmartAttack(P,Q,p)
print(num3)
#19597596255129283097357413993866074145935170485891892
2021第五空间secrets
import random, hashlib
from Crypto.Util.number import *
from Crypto.Cipher import AES
from secret import flag
assert(flag[:5] == b"flag{" and flag[-1:] == b"}")
flag = flag[5:-1]
p = getPrime(512)
secrets = [getPrime(32) for i in range(3)]
a = [getPrime(511) for i in range(3)]
e = [[random.randint(0,2) for i in range(3)] for j in range(3)]
c = 0
for i in range(3):
tmp = 1
for j in range(3):
tmp *= secrets[j] ** e[i][j]
c += a[i] * tmp
c %= p
key = hashlib.sha256(str(secrets).encode()).digest()
cipher = AES.new(key, AES.MODE_ECB)
enc_flag = cipher.encrypt(flag).hex()
print(p)
print(a)
print(e)
print(c)
print(enc_flag)
'''
7920896218820943056702891053785968782942077704655549145065876361907786355057528237061821280280635146678227702121299090049267547565989625947956850127609879
[5159988341992193282580685525745512910538614629527934692498086718630359717994948104271635300443062627349528208661883545208904466234606731357843882012950859, 6335284643679900918720817621948758994408045076082703123014899812263624185305268879304513104269749790342063146501376008458665966651095670658606928517201721, 6076126683981038494289949541335915228950649182831013867715530414744306299113418155691977393469353865827225836608438360416489035800225275307683760086087019]
[[1, 2, 2], [1, 0, 2], [2, 0, 0]]
2262305826865903827781721021939132022253239409560318732728105425007767005455109451147816015758855318893496902119172860305961200859254558917933621119030425
99ff236d4f1e020e6c83cc154e20f71eb510913056d47344b44a87f98664efd3
'''
$c \equiv a_1 s_1s_2^2 s_3^2 + a_2 s_1 s_3^2 +a_3 s_1^2 \pmod p$
格基规约。要让某个线性组合变成一个小值，因为secret就32位，考虑构造成格中的最短向量，变形为：
$c a_3^{-1} = a_3^{-1} a_1 s_1s_2^2 s_3^2 + a_3^{-1} a_2 s_1 s_3^2 + s_1^2 +k p$
$a_3^{-1}c = a_3^{-1} a_1 s_1s_2^2 s_3^2 + a_3^{-1} a_2 s_1 s_3^2+s_1^2 + k p$
造格如下：
$M = \begin{bmatrix}
a_3^{-1}c &&&\
-a_3^{-1}a_1&1&& \
-a_3^{-1}a_2&&1& \
-p&&&1 \
\end{bmatrix} $
（不太能理解怎么造的）
原文：希望最后规约得到的$v = \begin{pmatrix} s_1^2,&s_1s_2^2 s_3^2,& s_1 s_3^2,&k \end{pmatrix}$考虑分量的大小，配一个平衡矩阵：
$LL = \begin{pmatrix}
2^{96}&&&\
&1&&&\
&&&2^{64}&\
&&&&1
\end{pmatrix}$
p = ...
a = [...]
c = ...
enc_flag = ...
LL=diagonal_matrix(ZZ,[2**96,1,2**64,1])
a3_ni = inverse_mod(a[2],p)
M = matrix(ZZ,4,4)
for i in range(3):
M[i+1,i+1] = 1
M[0,0] = a3_ni*c%p
M[1,0] = -a3_ni*a[0]%p
M[2,0] = -a3_ni*a[1]%p
M[3,0] = -p
L = M*LL
v = vector(ZZ,L.LLL()[0])
print(v)
s1 = isqrt(abs(v[0]//2^96))
s3 = isqrt(abs(v[2]//(2^64*s1)))
s2 = isqrt(abs(v[1]//(s1*s3^2)))
print([s1,s2,s3])
#[2328484063, 3354920123, 2829061799]
最后AES解密：
secrets=[2328484063, 3354920123, 2829061799]
key = hashlib.sha256(str(secrets).encode()).digest()
cipher = AES.new(key, AES.MODE_ECB)
c=long_to_bytes(0x99ff236d4f1e020e6c83cc154e20f71eb510913056d47344b44a87f98664efd3)
m=cipher.decrypt(c)
print(m)
找了很多wp，造的格各有各的特色，很懵。
另一种参考writeup-for-2021-第五空间 · K1rit0’s Blog
但求不出正确结果，数据不太一样，但应该没影响吧。如下：
$0 = a_1 s_1s_2^2 s_3^2 + a_2 s_1 s_3^2 + a_3s_1^2-c+k p$
造格如下：
$M = \begin{bmatrix}
1&&&&a_1\cdot R \
&1&&&a_2\cdot R \
&&1&&a_3\cdot R \
&&&1&-c\cdot R \
&&&&p\cdot R \
\end{bmatrix} $
存在向量:
$v = \begin{pmatrix}s_1s_2^2 s_3^2,& s_1 s_3^2,& s_1^2,&1,& k \end{pmatrix}$
使得$v\cdot M = \begin{pmatrix}s_1s_2^2 s_3^2,& s_1 s_3^2,& s_1^2,&1,&0 \end{pmatrix}$
$R = 2^i$，是为了调格子的det, 调到能找到目标向量为止, 找到等式右边的向量就能得到结果。
还有另一种造法：https://www.anquanke.com/post/id/253524
记录一下吧，佛了，一道题折腾了几个小时。
2021第五空间data_protection
part1和part2是基础RSA不贴了，主要看part3、4、5：
part3：
def encrypt3(msg):
q = getPrime(33)
key = [[] for i in range(34)]
for i in range(len(key)):
for j in range(len(msg)):
tmp = random.getrandbits(32)
assert(tmp<q)
key[i].append(tmp)
cipher = []
for l in key:
tmp = 0
for x,y in zip(l,msg):
tmp = (tmp+x*y)%q
cipher.append(tmp)
print (q)
print (key)
print (cipher)
msg3 = [x for x in mail]
encrypt3(msg3)
矩阵运算$c = key\cdot m \pmod q$
则m = key.solve_right(c):
key = [...]
q = ...
c = ...
key = Matrix(GF(q),key)
c = vector(GF(q),c)
m = key.solve_right(c)
m=list(m)
print(bytes(m))
part4:
def encrypt4(msg):
key = long_to_bytes(random.getrandbits(128))
a = AES.new(key,AES.MODE_ECB)
cipher = a.encrypt(msg)
print (bytes_to_long(cipher))
msg4 = address
encrypt4(msg4)
part5:
def encrypt5(msg):
q = getPrime(512)
g = random.randrange(q-1)
x = random.randrange(q-1)
h = pow(g,x,q)
y = random.randrange(q-1)
s = pow(h,y,q)
c1 = pow(g,y,q)
c2 = (msg*s)%q
print (q,g,h)
print (c1,c2)
msg5 = bytes_to_long(school)
encrypt5(msg5)
2021第五空间crypto - hash_hash - 博客园 (cnblogs.com)
SUSCTFlarge case
from Crypto.Util.number import *
from secret import e,message
def pad(s):
if len(s)<3*L:
s+=bytes(3*L-len(s))
return s
L=128
p=127846753573603084140032502367311687577517286192893830888210505400863747960458410091624928485398237221748639465569360357083610343901195273740653100259873512668015324620239720302434418836556626441491996755736644886234427063508445212117628827393696641594389475794455769831224080974098671804484986257952189021223
q=145855456487495382044171198958191111759614682359121667762539436558951453420409098978730659224765186993202647878416602503196995715156477020462357271957894750950465766809623184979464111968346235929375202282811814079958258215558862385475337911665725569669510022344713444067774094112542265293776098223712339100693
r=165967627827619421909025667485886197280531070386062799707570138462960892786375448755168117226002965841166040777799690060003514218907279202146293715568618421507166624010447447835500614000601643150187327886055136468260391127675012777934049855029499330117864969171026445847229725440665179150874362143944727374907
n=p*q*r
assert isPrime(GCD(e,p-1)) and isPrime(GCD(e,q-1)) and isPrime(GCD(e,r-1)) and e==GCD(e,p-1)*GCD(e,q-1)*GCD(e,r-1)
assert len(message)>L and len(message)<2*L
assert b'SUSCTF' in message
m=bytes_to_long(pad(message))
c=pow(m,e,n)
print(c)
'''
2832775557487418816663494645849097066925967799754895979829784499040437385450603537732862576495758207240632734290947928291961063611897822688909447511260639429367768479378599532712621774918733304857247099714044615691877995534173849302353620399896455615474093581673774297730056975663792651743809514320379189748228186812362112753688073161375690508818356712739795492736743994105438575736577194329751372142329306630950863097761601196849158280502041616545429586870751042908365507050717385205371671658706357669408813112610215766159761927196639404951251535622349916877296956767883165696947955379829079278948514755758174884809479690995427980775293393456403529481055942899970158049070109142310832516606657100119207595631431023336544432679282722485978175459551109374822024850128128796213791820270973849303929674648894135672365776376696816104314090776423931007123128977218361110636927878232444348690591774581974226318856099862175526133892
'''
求解题目关键：
- 求解e
- 解出e后，解决e与欧拉函数不互素
求解e
设$ep$是$e$与$p-1$的最大公因数，利用费马小定理：
$ a^{p-1}\equiv a^{\frac{ep\cdot(p-1)}{ep}} \equiv (a^{ep}\pmod p)^{\frac{p-1}{ep}}\equiv 1\pmod p $
又$c \equiv m^e \pmod n \equiv m^{ep\cdot eq\cdot er} \pmod {pqr}$
可得：$c \pmod p \equiv (m^{ep} \pmod p)^{\frac{p-1}{ep}\cdot eq\cdot er} \pmod p = 1 \pmod p$
用$c \pmod p$替代$m^{ep} \pmod p$，检验$c^{\frac{p-1}{ep}} \equiv 1 \pmod p$
由此依次计算出$ep、eq、er$
p_list = [2, 7, 757, 1709, 85015583, 339028665499, 149105250954771885483776047, 1642463892686572578602085475101104723805585678675707586553009837707279291648160744722745420570786735582631019452016654157586623543454908938807521637550223579103317696104438456966780396624343550451096013730928292041667133825444056448136643704677066463120079]
q_list = [2, 2, 3, 3, 66553, 81768440203, 84405986771, 38037107558208320033, 16137718604846030589135490851713, 14369576056311038198362075935199486201201115381094289671031774994452214307042971166730146897009438957078052300683916910041250723573953110349566216311685009675744215421971185909678546052934704709232060199286321405045769976194110037]
r_list = [2, 5156273, 10012111, 11607389, 68872137169799749, 9691125310820433463, 12030248809636768339, 31518759824860728158228953, 547187028373506113438510511293209786101461141918516130626947626757753454448192055890412658699775890681515562519111190252566146302544199621791901997687741038739625529014337424946054655263007302018300326403871]
for ep in p_list:
if pow(c%p,(p-1)//ep,p) == 1 and ep != 2:
print(ep)#757
break
for eq in q_list:
if pow(c%q,(q-1)//eq,q) == 1 and eq != 2:
print(eq)#66553
break
for er in r_list:
if pow(c%r,(r-1)//er,r) == 1 and er != 2:
print(er)#5156273
break
#等于2的情况无根，可用iroot验证
e = 757*66553*5156273
#259776235785533
解决e与$\phi(n)不互素$
e还是很大，采取AMM应该会很慢。
根据论文，有下面的方法：
首先
令$\phi = \frac{\phi(n)}{e} ，g = 1$
循环$g = g + 1 ，gE \equiv g^{\phi} \pmod n$
直到出现$gE \neq 1$的$gE$，代码实现：
phi = phi_n//e
g = 1
gE = pow(g,phi,n)
while gE == 1:
g += 1
gE = pow(g,phi,n)
接着
计算$d \equiv e^{-1} \pmod \phi，a \equiv c^d \pmod n$
判断a转换为字节/字符类型之后，是否有flag的信息
若没有，进行e次循环
循环体：$a \equiv a\cdot gE \pmod n$，代码实现：
d = inverse(e,phi)
a = pow(c,d,n)
for _ in range(e):
flag = a
if msg in long_to_bytes(flag):
print(long_to_bytes(flag))
break
else:
a = a*gE % n
因为e太大了，执行e次循环根本跑不完，想办法约简。
让$e = e//r$，且有$er\cdot dr \equiv 1 \pmod {\phi(n)}$相关参数也作改变，
$\phi(n) = (p-1)\cdot (q-1)$，$n = n//r$
$c \equiv m^{ep\cdot eq\cdot er} \pmod n$
$c^{dr} \equiv m^{er\cdot dr\cdot eq\cdot ep} \pmod n$
可得：$c\equiv c^{dr} \pmod n$
同时我们看到assert对明文的断言，长度在L到2L间，也就是1024bit到2048bit。那么明文至少要填充1024bit的\x00。当我们选择舍弃了r后，就需要把多余2048bit的填充的\x00除掉：
$c \equiv (m\cdot2^{1024})^e \pmod n$
$c\cdot 2^{-1024e} \equiv m^e \pmod n$
这部分代码如下：
ep = 757
eq = 66553
er = 5156273
e = 757*66553*5156273
c = c*inverse(2**(1024*e),n) % n
e = e // er
phi_n = (p - 1) * (q - 1)
n = n // r
dr = inverse(er,phi_n)
c = pow(c,dr,n)
phi = phi_n // e
g = 1
gE = pow(g,phi,n)
while gE == 1:
g = g + 1
gE = pow(g,phi,n)
d = inverse(e,phi)
a = pow(c,d,n)
for _ in tqdm(range(e)):
flag = a
if b"SUSCTF" in long_to_bytes(flag):
print()
print(long_to_bytes(flag))
break
else:
a = a * gE % n
用了近10分钟，还是挺久的。
参考：SUSCTF_Crypto_large case_复现_M3ng@L的博客-CSDN博客
也试一下AMM：
从开始到去除明文多余2048bit的填充部分的操作一样，不一样的是后面的操作。
$c \equiv m^{ep\cdot eq\cdot er} \pmod n$
$e \cdot d \equiv 1 \pmod {\phi(n)}$
分别计算模p和模q下的情况：
$ep\cdot eq\cdot er\cdot dp \equiv 1\pmod {(p-1)}$
$eq\cdot eq\cdot er\cdot dq \equiv 1\pmod {(q-1)}$
$cp \equiv c^{dp} \pmod p$
$cq \equiv c^{dq} \pmod q$
接着便是套用AMM模板了，上面的部分相同就不贴了：
import time
import random
...
def AMM(o, r, q):
start = time.time()
print('\n----------------------------------------------------------------------------------')
print('Start to run Adleman-Manders-Miller Root Extraction Method')
print('Try to find one {:#x}th root of {} modulo {}'.format(r, o, q))
g = GF(q)
o = g(o)
p = g(random.randint(1, q))
while p ^ ((q-1) // r) == 1:
p = g(random.randint(1, q))
print('[+] Find p:{}'.format(p))
t = 0
s = q - 1
while s % r == 0:
t += 1
s = s // r
print('[+] Find s:{}, t:{}'.format(s, t))
k = 1
while (k * s + 1) % r != 0:
k += 1
alp = (k * s + 1) // r
print('[+] Find alp:{}'.format(alp))
a = p ^ (r**(t-1) * s)
b = o ^ (r*alp - 1)
c = p ^ s
h = 1
for i in range(1, t):
d = b ^ (r^(t-1-i))
if d == 1:
j = 0
else:
print('[+] Calculating DLP...')
j = - discrete_log(d, a)
print('[+] Finish DLP...')
b = b * (c^r)^j
h = h * c^j
c = c^r
result = o^alp * h
end = time.time()
print("Finished in {} seconds.".format(end - start))
print('Find one solution: {}'.format(result))
return result
def findAllPRoot(p, e):
print("Start to find all the Primitive {:#x}th root of 1 modulo {}.".format(e, p))
start = time.time()
proot = set()
while len(proot) < e:
proot.add(pow(random.randint(2, p-1), (p-1)//e, p))
end = time.time()
print("Finished in {} seconds.".format(end - start))
return proot
def findAllSolutions(mp, proot, cp, p):
print("Start to find all the {:#x}th root of {} modulo {}.".format(e, cp, p))
start = time.time()
all_mp = set()
for root in proot:
mp2 = mp * root % p
all_mp.add(mp2)
end = time.time()
print("Finished in {} seconds.".format(end - start))
return all_mp
dp = inverse(eq*er,p-1)
cp = pow(c,dp,p)
dq = inverse(ep*er,q-1)
cq = pow(c,dq,q)
print(cp,cq)
mp = AMM(cp, ep, p)
mq = AMM(cq, eq, q)
p_proot = findAllPRoot(p, ep)
q_proot = findAllPRoot(q, eq)
mps = findAllSolutions(mp, p_proot, cp, p)
mqs = findAllSolutions(mq, q_proot, cq, q)
start = time.time()
print('Start CRT...')
for mpp in mps:
print(mpp)
for mqq in mqs:
solution = crt([int(mpp), int(mqq)], [p, q])
if b'SUSCTF' in long_to_bytes(solution):
print(long_to_bytes(solution))
end = time.time()
print("Finished in {} seconds.".format(end - start))
执行的时间似乎要更久。
SUSCTF 2022 - hash_hash - 博客园 (cnblogs.com)
2022 SUSCTF SU Writeup | TEAM-SU (su-team.cn)
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1666739907@qq.com