[CTF GEMA] Mod_inv

Niveau de Difficulté : Medium

Catégorie du Challenge : Crypto

Description :

not needed!

Steps to Solve

Le défi consiste à chiffrer un message à l'aide d'un système modifié basé sur l'arithmétique modulaire, les valeurs aléatoires et les opérations sur les grands nombres premiers. 
Deux grands nombres premiers, p et q, sont générés et leur produit n sert de module pour le chiffrage.
Des valeurs aléatoires (r1 à r5) sont générées et des valeurs dérivées telles que (p-1) et (q-1) sont utilisées dans les opérations d'exponentiation modulo n. Le message original est chiffré deux fois à l'aide de deux formules différentes (c1 et c2), ce qui rend le déchiffrage plus difficile. Le but du défi est de retrouver le message original (FLAG) à partir des textes chiffrés fournis (c1 et c2) et des paramètres de chiffrement donnés.

La solution repose sur l'inversion des opérations mathématiques utilisées lors du chiffrage. Comme le même message est chiffré deux fois (c1 et c2) sans blocage supplémentaire, les textes chiffrés et les paramètres fournis peuvent être utilisés pour récupérer le texte en clair original.

L'inverse de l'opération est calculé modulo n à l'aide de la fonction inverse. La valeur inverse résultante (M0) est multipliée par c1 pour récupérer le message original sous la forme d'un nombre entier (M1). Le processus est répété avec c2 en calculant l'inverse de pow(r7, r5, n) et en le multipliant par c2 pour obtenir le message sous la forme d'un autre entier (M3). Étant donné que les deux textes chiffrés représentent le même message crypté de différentes manières, le décryptage de l'un ou de l'autre produit le même texte en clair (FLAG).

• Enfin, les entiers déchiffrés sont reconvertis dans un format lisible à l'aide de la fonction long_to_bytes, qui rétablit le message original. Cette approche utilise efficacement les propriétés mathématiques de l'arithmétique modulaire pour inverser le cryptage et récupérer le texte en clair.

from Crypto.Util.number import *

n=621000805385272535596766821882257874227280104374229559040334757417667189511131063725140469035157058323676871615129517364807446817387163820001907008128507581957857117421548917348659556753932080625938823188596518058748412891756136415416429386735150425299119906465178882097600629912421083606211679330960646039226037841635559751512710437653124196175483093471444802925106254595601500126932071639557335811310914553140640825556716300175374192122387472864017150292239428121009157771295293815292859342954680468874643924137575511947495810006717608500440434903575497259463925618647701920064689124635490657003491554859211542177805639514945339797447474355574325792858876992584985047409033323700018337127085844672387817078686855839587266236676475350472073784434795133287081179146771311992066353157381367109145552378045885683044106244664428308679139203543061722504306419306258072309114660308395168398361373643359612729000300898376298115363426426255079717236031456088652939639170553843492594704028699662352881121359366376540093293446681598745418147717237362085242950405467019524983741835362440949160851226432248038821134109297277705165721299473910730134883817523157672361315480476851000995195821745727914586026502654094643489437586408000627632939287
r4=3297286259728154634305729718627060181989823179916655735255741399339140163859372878978878335053810290279591800961061175875003589728487802241229720981084283
r5=13073570498807390614042077650751198944861320223843824372459989327128373546017427363473293851008163944732325528189328384185855898000517296267561844164727338
r6=310895914754309287972320178841373744142768874651364255929610251750315256810212368377856466262023468131841656261149685449831345089530818688031418386507525923641124742233834690981099542540825024461103547950485574674121168820984711579703771386817516774519055635555298710290894041772302486654766933831860703362590472081625335627254483683353565672658158977472053749458139160327188780088368877903034232777174031986476426001067201773859895182366443802849932692290461888011764774975113984751067841580998558760453918562200497854658407705837290781201063772808235498466228065114514140518506213199690762621545982491974212261715182270109587688656479572649906930549341224767679611113544144741180777905672911223863931447908816260538655345157378041447944012081411099261861808821172443681325121329961413099013706244552360613734032349299663842278511836923769654646839827263931218498184500976375711549279277939565695054401109643019211043402649526041384202666864964888207081811412547213689130624312089447163596299078225433750188003206930381072432174328499264887323993901821244429267836371581497370680442984713800105995523900973117907066721527511948076822077538516450394113656932163464510592448204728387415776207559118583717486515326009987604212829669278
r7=197356164590918752101820567297914970496273214799917833838664369028208779637646303938341014381044621503085465566149483787888145396643252625421045150403625725712407367422295412258692829167623435046327341658345709781198451146744118074232170999916136211677625386379920423671203289050494663215944522432503385299618720759474168576370699293670256228620658865135003767165297418517229520425248032328914879940064915626035168631660305217087347608460696009248011162986793699533671940153614227379333386247599807427734061893678444518795767154899461964329418118362296349038138789552417809839948771983844134308418231110884699330217070457913947021526254479695925612167651524516895371911013280929594238578773100809958788396196149557828039356085225849282159894718218113367410396886764816991042659782687263758069279245803447053016908590878787961295850010387368625891149499986218760766317877058472363760413430921811992904338081888424612566209270765811701336920352876794573229905055803761874240736889415835303735240872032266121163409109313544216469296739427156829384749669448553822887282610574959968289602061983112192622151495361495977884094857732027447639693989266202273417781221265960807079193668858433637355411802905179350990815098521882322610227854767
c1=306392950194079833999305438855598403757940351966126402990735914585697439145189656395833670209286277715654756076818057446958092110538986829442430546182309319276923395519160221968633441525210162782023919482016158829958051875307575810836566242624148851476396265151195393251052292246450801125365121009785637797722486026872339172328830474429969924777088052553311677420030970892624420611205987817980997536248933136275718799743199166281228636609320685510425153050347493922625358346984961089922286315803579125881187022626718098411627161540088635747151821995460183674049153169028778271078233264514517204213787343132154799485969472807857057840841599554101992535465067065039848370450680587377269441204836566616520380419144496195194780068831481597903902058102285113371147136302810563639465337904869460531166809864611622052247215897684943902479372509496285803400734357434112036138021170030914803236669239584568270819848633591545367261809063429397819356797452427031220112373327613829205141013673632487893556247039227064828718274956563123946632879339160564287201062428035941289932480481474011411040197131787790919548301019675457076010637341400094907848932563388608347490184762554620668557009922770630633475109405896032338431963525051012053346018961
c2=314761649893288433390330005198571888364689580656225338692199041420413807376162895344250939326587243791598802129768342754338420757350797582504514310914901853879893549344444295210647243795636436187609116189209611011980896724132219219412512391938672437994647921104307416175211017872457308083216093838454987228393644941736316945909407050559249409486772804742111433755512063466055728906251783193099813660302371156324614399552296760159968905361006140699400467864039947102068781244566312381461632338062269613695220660937840834023848787287658943895188971130580929944322224518373291440858680254091302579686229166647094841990326512556265781217842878090557225912976510378215724272199379850351526668772734684316734417532246618633918052794657028904298954598077985524653571507724032498306568242186845379766429749318431986096656112989280009681057551961246445127182517098361987488103953337832668683954819634806945748237560318463004447622777765107138822866884118730795601304687019780987406652918145583912294476122890672143595480163670409331560703823870475569891480738456689097765708114696950966818158319638849897264307607067883613724767525914598613072935366652096252258755579920488955993141323525952684921314728454206925995009024592922744962625044925


M0=inverse(pow(r6,r4,n),n)
M1 = M0*c1 %n

M0=inverse(pow(r6,r4,n),n)
M1 = M0*c1 %n
M2 = inverse(pow(r7,r5,n),n)
M3 = M2*c2 %n
print(long_to_bytes(M1))
print(long_to_bytes(M3)) # Note : C2 is same as c1 becuase he encrypt the same message without blocking it 

Flag

FLAG{What_The_Hell}