Crypto - Raul Rosas
"I say weird stuff all the time." - mindFlayer02
Challenge
from Crypto.Util.number import *
from sympy import nextprime
p1 = bin(getPrime(1024))[2:]
p2 = p1[:605]
p2 = p2 + ('0'*(len(p1)-len(p2)))
p1 = int(p1,2)
p2 = nextprime(int(p2,2))
q1 = getPrime(300)
q2 = getPrime(300)
n1 = p1*p1*q1
n2 = p2*p2*q2
e = 65537
flag = bytes_to_long(b'REDACTED')
c1 = pow(flag,e,n1)
c2 = pow(flag,e,n2)
print(f'{n1=}')
print(f'{n2=}')
print(f'{c1=}')
print(f'{c2=}')
"""
n1=33914684861748025775039281034732118800210172226202865626649257734640860626122496857824722482435571212266837521062975265470108636677204118801674455876175256919094583111702086440374440069720564836535455468886946320281180036997133848753476194808776154286740338853149382219104098930424628379244203425638143586895732678175237573473771798480275214400819978317207532566320561087373402673942574292313462136068626729114505686759701305592972367260477978324301469299251420212283758756993372112866755859599750559165005003201133841030574381795101573167606659158769490361449603797836102692182242091338045317594471059984757228202609971840405638858696334676026230362235521239830379389872765912383844262135900613776738814453
n2=45676791074605066998943099103364315794006332282441283064976666268034083630735700946472676852534025506807314001461603559827433723291528233236210007601454376876234611894686433890588598497194981540553814858726066215204034517808726230108550384400665772370055344973309767254730566845236167460471232855535131280959838577294392570538301153645042892860893604629926657287846345355440026453883519493151299226289819375073507978835796436834205595029397133882344120359631326071197504087811348353107585352525436957117561997040934067881585416375733220284897170841715716721313708208669285280362958902914780961119036511592607473063247721427765849962400322051875888323638189434117452309193654141881914639294164650898861297303
c1=5901547799381070840359392038174495588170513247847714273595411167296183629412915012222227027356430642556122066895371444948863326101566394976530551223412292667644441453331065752759544619792554573114517925105448879969399346787436142706971884168511458472259984991259195488997495087540800463362289424481986635322685691583804462882482621269852340750338483349943910768394808039522826196641550659069967791745064008046300108627004744686494254057929843770761235779923141642086541365488201157760211440185514437408144860842733403640608261720306139244013974182714767738134497204545868435961883422098094282377180143072849852529146164709312766146939608395412424617384059645917698095750364523710239164016515753752257367489
c2=3390569979784056878736266202871557824004856366694719533085092616630555208111973443587439052592998102055488632207160968490605754861061546019836966349190018267098889823086718042220586285728994179393183870155266933282043334755304139243271973119125463775794806745935480171168951943663617953860813929121178431737477240925668994665543833309966378218572247768170043609879504955562993281112055931542971553613629203301798161781786253559679002805820092716314906043601765180455118897800232982799905604384587625502913096329061269176369601390578862509347479694697409545495592160695530037113884443071693090949908858172105089597051790694863761129626857737468493438459158669342430468741236573321658187309329276080990875017
"""
At first I thought that it might be a partial prime challenge, with 419 of 1024 bits are disclosed to us
However, the fact that the lsb of p2 has ~400 bits of 0 allows us to consider a new approach. If a number smaller than 400 bits is multiplied with p2, then the carry of the multiplication does not interfere with the remaining bits of p2 and is fully preserved in the result, which can be considered as regular multiplication.
Given n2 = p2*p2*q2 , we try to find the value of the small prime q2, after which we can find n2 and decrypt the flag.
from Crypto.Util.number import *
fact=int(bin(n2)[-314:],2)
# we get q2 on factoring fact
q2 = 1651764208712002362909070586532659043033781575172011989418709627827265240039573208353001543
a2 = n2//q2
p2=sqrt(a2)
phin = (p2)*(p2-1)*(q2-1)
print(long_to_bytes(pow(c2,pow(65537,-1,phin),n2)))
b'DEAD{Rual_R0s4s_Chiweweiner!!}'Last updated