2022ctfshow 卷王杯
from Crypto.Util.number import bytes_to_long
from secrets import p,q,r,s,t,flag
n = p * q * r * s * t
e = 2
m = bytes_to_long(os.urandom(500) + flag)
c = pow(m,e,n)
print(p,q,r,s,t,sep='\n')
print(c)
不互素且$gcd(e,phi)==e$，可以在不同的域下对c开e次方，将得到的根进行组合进行CRT。
p = 145332367700944303747548912160113939198078051436029477960348968315913956664143693347226702600438608693933768134575289286283267810723137895903153829001826223446477799895493265422562348917012216790077395795861238257357035152687833639085415763850743538206986781418939737511715957738982536382066693822159860701263
q = 116660458253067608044065523310547233337730583902133756095473339390057738510707447906971188577217274861047379404014140178165569604404468897712846876108444468370709141219302291601408652742006268186059762087155933131837323952675627966299810891805398890428420575425160696531236660480933905879208166090591482794763
r = 157931722402853245421436270609912823260313730941283152856444641969403238646482562190531038393124087232554754746464603598717356255570166081501573727336977292059427220330169044611674973569766966838498453232642731737958791706086957762244686953294662693939604300864961637325536379321027705854708492453330690705531
s = 100973451687449518854742673778783266158999451072058606348222018797891147675959983616210003484476577612134482311993701677242007759556951494382833070563369964294544839433671087037596159753825249018950693369209927951667775267086896180395776150188902057785214767230658487267587289809918132337927575673868568976679
t = 93960345071948255233882121683650797512129333868351496468898834736770441398743300745703393838320587998953678254272245400344928586394089488734271897540051673996675973642347859306921527430850673334243441180183460927865980713929789963587608547554858491264614271309608925634272282292964002897650355047792764365447
c = 9144597920381774885442906257311149465702295057238600973973598305004391534618770363098565074541384771979931799878381439264848137810353858418200992191234142740194489573540381681161219332611454834544291634628456257670178843484698324641739324687497388018406214041657278323855749902661752448796122517061920880552011343608609622885787617238758769398972009949575526258430282648817039091284796330585349957724522615105102735930258969562103112238020133587096826386028128471852377225525357348919204333121695432662339443004327748973224423132988376298843862056631045488285859621661802413201793962883794915513510467912312842687601478117040419013468059983777273699192408773551806581458197324620065210523913467414181480875280203580147077789063808832356486197271376615883221558265591069223727607585313240243619515521180600435114131162272519949101464089935441251751426683447701142156416866113627126765919641034042927519834229168536331952275698122511502745177547569813354280565828372968703810158857859460406828090199683324760956105682902577189283246483314689365570862217407333103243336691401424548702387876409228977278498691200028282744239512091373110111792177228979867318546462714521296256938374618636206565791541769138267080789842400796973226733816939794717596194090232425688504890234304977612220790858557639246367437740975495450011676714198668471438814299689325208882261918460708833888406187912527346628912894921059735420931656953236560178909180587372589456926690219114173193202048332172538564489660440225377822914097420807957784201785024166011709377791129
n = p*q*r*s*t
e = 2
phi = (p-1)*(q-1)*(r-1)*(s-1)*(t-1)
R.<x> = Zmod(p)[]
f = x ^ e - c
res_p = f.monic().roots()
#其它的相同，换下参数即可
res_p=[(105759306796604458734616988025041070894254086177961955152266241983599552436038417164589781800548170263137744573303899679801944648323570236444662118586389843689723523559621259451179955280920984411241370317372577352603546061045989233542252380860541664590826871711240796449926428967356180623320755399312333855914, 1), (39573060904339845012931924135072868303823965258067522808082726332314404228105276182636920799890438430796023561271389606481323162399567659458491710415436379756754276335872005971382393636091232378836025478488660904753489091641844405543163382990201873616159909707698941061789528771626355758745938422847526845349, 1)]
res_q=[(61271467210118412966724984292095335317733695256090878426560686891756079924997989716821358995235922204013829340494037064720729099316872761029080019202081517084920407823716674786308109091176385109278967641331532338629650874309430534283470953619914746783509470375167910894276568010726761673444218996017135114156, 1), (55388991042949195077340539018451898019996888646042877668912652498301658585709458190149829581981352657033550063520103113444840505087596136683766856906362951285788733395585616815100543650829883076780794445824400793207673078366197432016339938185484143644911105049992785636960092470207144205763947094574347680607, 1)]
res_r=[(81494645874260988911158916071880589359987692444861294147300186590570368369310500749798165469954243389790515045742691754565984336157619549494162814548778978629336604244757475768337171648672659348063737408489515868219005399374680983335675188997145621903581258458582232536740517461870029388465524596256244426733, 1), (76437076528592256510277354538032233900326038496421858709144455378832870277172061440732872923169843842764239700721911844151371919412546532007410912788198313430090616085411568843337801921094307490434715824153215869739786306712276778909011764297517072036023042406379404788795861859157676466242967857074446278798, 1)]
res_s=[(51144823034893467516049830013634908954947282240108395637750270980709555996962447979999247978745025424678021661508447789536796050829892155378538642362300766072138752230839087308843963081621082317370683937461997061050952181636902197426079036843036405576746588315389276602207691439303029900209974821989735900029, 1), (49828628652556051338692843765148357204052168831950210710471747817181591678997535636210755505731552187456460650485253887705211708727059339004294428201069198222406087202831999728752196672204166701580009431747930890616823085449993982969697113345865652208468178915269210665379598370615102437717600851878833076650, 1)]
res_t=[(56637279121653393183765926394036757622063751326302092068920147262287397466384343814073144226967254272339029262947175891947262297560109802237295059464880607159848782193114481656026708061277319588698540513237321988174311640122032153576262583677645331084360321934219426057528705181800937189748999636758570257615, 1), (37323065950294862050116195289614039890065582542049404399978687474483043932358956931630249611353333726614648991325069508397666288833979686496976838075171066836827191449233377650894819369573353745544900666946138939691669073807757810011345963877213160180253949375389499576743577111163065707901355411034194107832, 1)]
找正确的根：
for i in res_p:
for j in res_q:
for k in res_r:
for l in res_s:
for m in res_t:
mi = libnum.solve_crt([i[0],j[0],k[0],l[0],m[0]], [p,q,r,s,t])
flag = long_to_bytes(mi)
if b'ctfshow' in flag:
print(flag)
#b'ctfshow{D0_y0u_R3aLly_Kn0w_Ra8IN_alg0RI7HM?}'
（●´3｀●）Goooood (tsuppari404.github.io)
special_rsa
from Crypto.Util.number import *
def getPrime1(bitLength, e):
while True:
i = getPrime(bitLength)
if (i - 1) % e ** 2 == 0:
return i
flag=b'DASCTF{????????????????????}'
m = bytes_to_long(flag)
lenth = ((len(bin(m)) - 2) // 2) + 9
e=113
p = getPrime1(lenth, e)
q = getPrime1(lenth, e)
n=p*q
print(f"n = {n}")
c1 = pow(m, e, n)
for i in range(26):
lenth = ((len(bin(c)) - 2) // 2) + 9
p = getPrime1(lenth, e)
q = getPrime1(lenth, e)
n=p*q
print(f"n = {n}")
c=pow(c,e,n)
print(f"e = {e}")
print(f"c = {c}")
首先对flag进行RSA加密，然后进行26次RSA加密，每次加密得到的密文是下次加密的明文。
观察p、q的生成过程可以知道$e|(p-1)、e|(q-1)$，故e与phi不互素。 e=113，需要从113个中筛选。
论文：https://arxiv.org/pdf/1111.4877.pdf
AMM：https://lazzzaro.github.io/2020/05/06/crypto-RSA/
from Crypto.Util.number import *
import re
e = 113
c = 1028324919038104683475485759234995158466543298184637219012354053883391759172761125802189697762778242175407876548832454351014064525118465877297277847501477586955680645311999174005606833294172830817159
ps = [953730950786751671162019537171974567, 232079231415308325450092906880606082069, 88067722275537586769787599991567203589751, 24335212484189159197840692460327461505035059, 7832299017937880395583715032476962329929226581, 1656848589754467667368312855929759764100120657831, 385788223643735590500185001710758495904528462058461, 135813272566456906193934636644217527100917542578856697, 37185691759470013533730603170661686570987787098353146897, 6623023178993627032758350846838617937710601663528839184727, 954412804126450754097808991490470782833291028309980575506163, 350121371461894793578110243222665782247737840410076591434903787, 66882708962198932251728043152245270662769508317424500666902658099, 43449898447639409732732812916430042263570178747794530133229640125923, 11136261905010083405430254612464029672882837025885682392810368001188527, 2623629589005115152329094552749299711026240699896424120660145647226563547, 262775599542220820608778738911414710660835549772895468394761119434220071003, 102366458668689911004027849640392002821642295855327735994412634235696717329671, 15874438801602936764330936047390981280096007684699625987478211613419079727910193, 4479430800690915874719403516331677127806963529247809966024777708496270901092401687, 1328165608715012145707239303399129070657427496129541416861187541092152796676371237057, 368461902207817023013078031477042541053987571003677386333567043030477451518424731838173, 206721456778089912780641186795393376537372828449722520397829606593267585681448641482345737, 43870497594014737833600078975099212558645315030912084285417550950854483979406797450479252891, 14702310219802004876082313481498680940324963613770096574742182597840558294030859405666549879531, 5952590790902091635268726673538951527433355660839816621733964706901441977862333411532558667717227, 978009050697262759337388871320370165458800566798280419667959552859180906066907114053826258140106617]
def get_roots(ii, ci):
pi, qi = ps[ii], qs[ii]
R.<x> = Zmod(pi)[]
f = x ^ e - ci
f = f.monic()
res1 = f.roots()
R.<x> = Zmod(qi)[]
f = x ^ e - ci
f = f.monic()
res2 = f.roots()
sol = []
for x in res1:
for y in res2:
mi = crt([int(x[0]), int(y[0])], [pi, qi])
if ii != 0 and mi < ns[ii - 1]:
sol.append(mi)
print(f'No.{ii} x = {x}, y = {y}')
elif long_to_bytes(mi).startswith(b'DASCTF'):
print(long_to_bytes(mi))
return
if not sol:
return
for jj in sol:
get_roots(ii - 1, jj)
ns = []
qs = []
with open('output.txt', 'r') as fp:
regex = r'[n] = (\d+)'
output = fp.readlines()
for i in range(len(output)):
if re.findall(regex, output[i]):
ns.append(int(re.findall(regex, output[i])[0]))
qs.append(ns[i] // ps[i])
assert False not in [ps[i] * qs[i] == ns[i] for i in range(len(ns))]
get_roots(len(ns) - 1, c)
读取文件内容这部分值得学习。
20220423-DASxFATE-CryptoSecPartWriteUp | 4XWi11’s Blog
(6条消息) 2022DASCTF Apr X FATE 防疫挑战赛WP_Harry0597的博客-CSDN博客
这里还没用到AMM，因为e还不算特别大。
当e特别大就需要用了。
抄的模板😬：
from Crypto.Util.number import *
import gmpy2
import time
import random
from tqdm import tqdm
e =
p =
q =
n = p * q
c =
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 onemod(p,r):
t=p-2
while pow(t,(p-1) // r,p)==1:
t -= 1
return pow(t,(p-1) // r,p)
def solution(p,root,e):
g = onemod(p,e)
may = set()
for i in range(e):
may.add(root * pow(g,i,p)%p)
return may
cp = c % p
cq = c % q
mp = AMM(cp,e,p)
mq = AMM(cq,e,q)
mps = solution(p,mp,e)
mqs = solution(q,mq,e)
for mpp in tqdm(mps):
for mqq in mqs:
ai = [int(mpp),int(mqq)]
mi = [p,q]
m = CRT_list(ai,mi)
flag = long_to_bytes(m)
if b'NCTF' in flag:
print(flag)
exit(0)
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1666739907@qq.com