IS IT AN RSA???

Hard | Cryptography

DESCRIPTION

The enigmatic Cyber Ninja clan devised an extraordinary encryption technique known as the RSA Art of Shadows. In this ancient cryptographic art, every element is intricately interconnected, embodying the essence of their mystical power. Legend speaks of a forbidden connection between n3, the sacred modulus of the third level, and the elusive shuriken factor, s. The Cyber Ninjas now question the resilience of their moduli amidst the shadows of uncertainty. Unravel this enigma and reveal the extent of the moduli's vulnerability to achieve enlightenment

Flag format :flag{}

Challenge files

chall.py

from Crypto.Util.number import getPrime
 
p = getPrime(1024)
q = getPrime(1024)
r = getPrime(1024)
s = getPrime(1024)
 
m = #REDACTED
n1 = p*q
n2 = q*r
n3 = #REDACTED
e = 65537
c = pow(m,e,n3)
 
with open("cipher.txt","w") as f1:
    f1.write("n1 : {n1}\nn2 : {n2}\nn3 : {n3}\nc : {c}")

cipher.txt

n1 : 20912910050796031830809673977674455857393320096113471000108476598239671823290454539099505006341181927803396230002338735454401646406475912688218923104360101493420587464070273323527567266113085620629777182230272649016079034035826193606941717409911127293033937511127232622025383267748018774971415071232112682518085465253677786075882388751252903758885822335201048783033607059125114129721962237031848160257840042749604701661351104632197268101338356585152993200499847224148428276285280947713025841594472924459330814475796519691496598976366224681227183057944078367988646669983887511386712300733007180288701194351474709451461
n2 : 23872426932563883914901983231692363805983070520331002447445050715524972251586497800571756559464721924549362084406494547280486962487511746912828373497887521440699329723182185403037889716533745183479525650184983301161183195860766723642989068462832335949332139360177109353246709886130607275469616829829377688389101875591693039721270258491641736695891769279331901855145276977713307839426340839804405968558066844316403038985679295562342379505784575994967680959855066641348711021844621460984249502783862934341287142019016182597959562535015183590583942937215422158669723160244494194242460279136853725071235733665302988209581
n3 : 623265548625163278510022487995567876890926533209308999370330362371439285305085412615456709572300610469764709333529406834419638261601983277055730634365116268494851890297910828294958809680835145062374334660144925073817009153363194356277972003823429825090687577884104803772423494559660272965942415656846093421497718789399057923632452460959329004642659416401533494734674341297334092185269456244649167294148756998182926381486263680657018086861695000390477334298652089510062786091483474947031402375475934819658393231455628207075109607210571629964456581753334227077161648968974473732063297259193869372494140348513893186441054530081786588494978099820939294808602649303543807725972018035561286998003180524519740327192105076194250531595088678296559426905737604898487332506263768448008370290928316965877252657591981473292067631778780063949433186833597022736100596242927881445173397533719063681933023690642498287147012288569648280776237679667255272112710330887407771683145839111961602721160726180735195355237690249090722802712929899425175942561146908593585556441325499980035838317170354479081502340112091530897868855495757738933924256969879209548844098392755956340797905688458571159105633325558683059168331041150880160341776229718860612253277689383592135954817820356993637153693807088618971309357852420077553044453663264289081544406697440268577543019319406136538822420767680430176862831205443049624222048932334457406735745145522789026912573894925384649250021447001861056286156729731381118654052424555045194332265401547466687129069693348919729472648603604207705967197358747234395578381797487161842286311601521051614443136409426549673744994567186673259410264138756018328704519923828130219209915417334306742146661470932320976746278374554809658219190409161811156640039813265447320394905627416336825499242467352625072411979139565787153117666316266128433664263573908420103316680637158744227670026017618721163233170430817916291320917442601841215726738107837455010696286492216875918830651149525869473057392158941139946159965059088434640307636983388935709069356519776673061113986935201719486791353927766209797128863955945018524614009681587930678131170189431123293320603504946629
c : 300765675631036702440523739351154897383328322310909427639150819891961020790689307369308441255403094732423274431969874729576538743620119420735510045406001994753894520763272198722820558323777418995706994461414667818537719413094635232811184202577172511003889024565202258024532325841442524255115720343283468219385208657431547944302686466963643630617734585172811247868088027325004294939532871542424327865040876468978611871974999372691163464294756117812578408540739824709677959432355997425868877804980417752642107595057064248851537732058086278189683557116314198234770298192400203155340277871276718988519131085372705342068348850422546040347545294934795160228629715928205702963059053926678039307251970985067503945484142259384931005122474633734569350468028096545310923922736277126500494960558901118391826970750599017736592975695396953268648137731306315298363276952213929906449212672277952655169301409708326657804508222562820866018885085111020645767177241778007313870356313737766211807671684466236765782369978681732347669091529835873174707088943878081394207743832495916408484710683636315373611964455948879147334744259927601718737189225141948942454372275019801444709829300827100970958900715300313378107547518939050666002906010324615404445192022240280315907630458853581194336155758396621241419237953860938727690588816954526361793957917189783860306310822734347040467227916427155488984237263951334309867259192368643799454225026080500451877047304229273388998226482371462690188525788808790286231420310667434427953649009749851835345643678202026126838640308587587491539165176588320928304857832498694961323661593475151903835366820810227102061312419087294682432081917413904639688299669590743900799344326135311955543328076735324152278029826551922472334486502065676931796120276566197522523087325802268044548699688695109433084891340455120679761061711197620052128458728329181321749503305859230167473247286327332162638070885298897162507611749649393208158266253582200354380719427286181196920627292677984198089607982851981186674993709576820550096457875619124681598635713218705170000750192136641170764054753456395228025468183484945388029949429676193689771416723243948217122509236756623

We are given with a RSA challenge We all know the encryption and decryption formula for RSA

General RSA formula

For encryption:

$c = m^e \mod n$

For decryption:

$phi = (p-1)(q-1)$

$d = e^{-1} \mod phi$

$m = c^d \mod n$

Gathering primes

In here :

n1 is a composite of p and q
n2 is a composite of q and r
n3 is a composite of something we need to find

In n1 and n2 q is a common factor. We can easily find q by finding the GCD of n1 and n2. And then we can find p and r by dividing n1 and n2 by q.

solve.py

from Crypto.Util.number import getPrime, inverse, GCD
q  = GCD(n1,n2)
p = n1//q
r = n2//q

Understanding the odd

We can clearly see that n1 and n2 are product of 2 primes of 1024 bits. The bit length of the n1 and n2 are

solve.py

In [19]: n1.bit_length()
Out[19]: 2048

But we cam clearly see the bit length of n3

solve.py

In [21]: n3.bit_length()
Out[21]: 7165

We can clearly say that the n3 is not a product of 2 primes. Rather is a product of some formula. Lets see how many primes are used to make n3

solve.py

In [25]: n3.bit_length() // 1024
Out[25]: 6

So 6 primes are used to make n3. Lets find them out.

Finding the primes in n3

Lets start by checking the primes we got. Lets take p first and check if it is a common factor in n3.

solve.py

In [36]: GCD(n3, p)
Out[36]: 124716128750274416177198385152601667810715797395833853677249811082727897461676570581863936449483189681198092903020904507322672470247046160304218067660413360746027028163176276250302488523199660253851031967063877633434238865709326658853456209535821692944228463233716423928577199378853127205934867872502637393289
 
In [37]: GCD(n3, p) == p
Out[37]: True

Woah! It returned True. So p is a common factor in n3. Lets check for q and r too.

solve.py

In [39]: GCD(n3, q) == q
Out[39]: True
 
In [40]: GCD(n3, r) == r
Out[40]: True

So all the primes we got are common factors in n3. So we can say that n3 is a product of p, q and r. But we know that we need 6 primes to make n3. So lets take power of p, q and r and check if they are common factors in n3.

solve.py

In [41]: GCD(n3, pow(p,2))
Out[41]: 15554112770455024809073188538206224175811264414593113182175366059064714239217731982868594528395154214503589040926321192022386529327087943668105836984894144248802929811716062351004977499092277317327435682750945950679378333316328513968686815570912101609909249735532777434594169311394393444830053129414012610779154290118258756064830193154930761680746094740683402700811866051054267358207880421125341931913522647715729864319025287613599335297701372181389837345085901714147957286234397773004089503032395509679703737568620155596320566060034098590845058738169298962154473548541218108014825076451868139246073371148360862237521
 
In [42]: GCD(n3, pow(p,3))
Out[42]: 1939848730876356370338996801398048037857833115289864412466655106145329499394865290710768988183824288367783786669567770851493282647785925841611455505081781558294896496997044625574877254224174797620982853278774443949011043479557040137446840878689584062481160823807830757953911244957060273986397049626272911274370033834958023130588937138346362888126333278236414904068076357358384772755529345232060797979278630641234996253325458285806118407613535369605310444589343355909515768427219839902629860617968036945904517248761122857453669814043915295029766761281183897648985030216003609410799182065501574859036988121149518280660908254924625797046130124228088807861184383966714604739293202906411365353640866811536975507670716344716117088336266514190134453813472104647745263079716755292365962064259348218786607048963215177888454646093802134236024571716964821004856893417319823788276084743986474314910987620355849429730140105487991409396569
 
In [43]: GCD(n3, pow(p,4))
Out[43]: 1939848730876356370338996801398048037857833115289864412466655106145329499394865290710768988183824288367783786669567770851493282647785925841611455505081781558294896496997044625574877254224174797620982853278774443949011043479557040137446840878689584062481160823807830757953911244957060273986397049626272911274370033834958023130588937138346362888126333278236414904068076357358384772755529345232060797979278630641234996253325458285806118407613535369605310444589343355909515768427219839902629860617968036945904517248761122857453669814043915295029766761281183897648985030216003609410799182065501574859036988121149518280660908254924625797046130124228088807861184383966714604739293202906411365353640866811536975507670716344716117088336266514190134453813472104647745263079716755292365962064259348218786607048963215177888454646093802134236024571716964821004856893417319823788276084743986474314910987620355849429730140105487991409396569

We can see that when power of p changed the GCD until power is 3. We can conclude the p is used 3 times. Lets check for q and r too.

solve.py

In [46]: GCD(n3, pow(q,1))
Out[46]: 167684085934635111138105189988179080219157811889011166123666499425768450437469943386621848048488343683888778929689860701092367929913492900054874870222429427988420144341251557765223160805932679793036379398755587186757197200753836874710801303907347858239825996765304285670427266939478508125758879660649717702749
 
In [47]: GCD(n3, pow(q,2))
Out[47]: 167684085934635111138105189988179080219157811889011166123666499425768450437469943386621848048488343683888778929689860701092367929913492900054874870222429427988420144341251557765223160805932679793036379398755587186757197200753836874710801303907347858239825996765304285670427266939478508125758879660649717702749
 
In [48]: GCD(n3, pow(r,1))
Out[48]: 142365489244278006781892803413026055432933017134778041033158055403993344855207744289954430149026059218584510831384838278495330431590366037642960108272941529465691976561345563726700360662176646062182458455039010325713074639851158174054530814138407924428943535979993235007619649731927022629125810819439142305169
 
In [49]: GCD(n3, pow(r,2))
Out[49]: 20267932527762636834570715204287113161225585900761807310359322800094789552775095128097769565749361520639272417327841773384586804615625083930559447693705519178206113058389457923137443793732325862829174025291870510316300125243601994386847752789140463383268011184938615549186789301031592533781992235385569762218903681758962970532218722617149001411429678575218185925192350769477548811218191422967788669795277406733302039036189187148642059812931328839417259017053311461552704414998586986456586486511050279159334908187309038019195386803085608106613964500649035501969336671755094497105445891851721805936565611011143124118561

We can see that when power of r changed the GCD until power is 2 and power of q is 1. We can conclude the r is used 2 times and q one time.

Now lets retrive value of s:

solve.py

In [51]: s = n3 // (p**3 * q * r**2)
 
In [52]: s
Out[52]: 94537466381688711393416471073496063783402005647205862752291533383699862823573459328131715074222375596202328764916181988791300341884472499184768410891857188002989053754418453471265347522791306401726333970123891529221678055718225978509054276263393148712995381833817232211120365998122345765514840710993126004369
 
In [53]: s.bit_length()
Out[53]: 1024

We got all the primes now. Lets find the eular totient of n3.

solve.py

phi = (p**3 - p**2) * (r**2 - r) * (q-1) * (s - 1)
assert GCD(phi, e) == 1

We got the phi now we can find the d and solve the challenge.

solve.py

d = inverse(e, phi)
m = pow(c, d, n3)
print(long_to_bytes(m))

Flag 🚩

output.txt

b'flag{1s_17_r34lly_an_RSA???}'

level7 Common Primes