• Nom : Yet Another RSA Challenge - Part 1
• Catégorie : Crypto
• Description : "Buy an encrypted flag, get a (almost intact) prime factor for free !"
• Fichiers joins : yarsac.py , output.txt

yarsac.py :

import subprocess
p = subprocess.check_output('openssl prime -generate -bits 2048 -hex')
q = subprocess.check_output('openssl prime -generate -bits 2048 -hex')
flag = int('INSA{REDACTED}'.encode('hex'), 16)

N = int(p,16) * int(q,16)
print N
print '0x'+p.replace('9F','FC')
print pow(flag,65537,N)

output.txt :

719579745653303119025873098043848913976880838286635817351790189702008424828505522253331968992725441130409959387942238566082746772468987336980704680915524591881919460709921709513741059003955050088052599067720107149755856317364317707629467090624585752920523062378696431510814381603360130752588995217840721808871896469275562085215852034302374902524921137398710508865248881286824902780186249148613287250056380811479959269915786545911048030947364841177976623684660771594747297272818410589981294227084173316280447729440036251406684111603371364957690353449585185893322538541593242187738587675489180722498945337715511212885934126635221601469699184812336984707723198731876940991485904637481371763302337637617744175461566445514603405016576604569057507997291470369704260553992902776099599438704680775883984720946337235834374667842758010444010254965664863296455406931885650448386682827401907759661117637294838753325610213809162253020362015045242003388829769019579522792182295457962911430276020610658073659629786668639126004851910536565721128484604554703970965744790413684836096724064390486888113608024265771815004188203124405817878645103282802994701531113849607969243815078720289912255827700390198089699808626116357304202660642601149742427766381
0xDCC5A0BD3A1FC0BEB0DA1C2E8CF6B474481B7C12849B76E03C4C946724DB577D2825D6AA193DB559BC9DBABE1DDE8B5E7805E48749EF002F622F7CDBD7853B200E2A027E87E331AFCFD066ED9900F1E5F5E5196A451A6F9E329EB889D773F08E5FBF45AACB818FD186DD74626180294DCC31805A88D1B71DE5BFEF3ED01F12678D906A833A78EDCE9BDAF22BBE45C0BFB7A82AFE42C1C3B8581C83BF43DFE31BFD81527E507686956458905CC9A660604552A060109DC81D01F229A264AB67C6D7168721AB36DE769CEAFB97F238050193EC942078DDF5329A387F46253A4411A9C8BB71F9AEB11AC9623E41C14FCD2739D76E69283E57DDB11FC531B4611EE3
596380963583874022971492302071822444225514552231574984926542429117396590795270181084030717066220888052607057994262255729890598322976783889090993129161030148064314476199052180347747135088933481343974996843632511300255010825580875930722684714290535684951679115573751200980708359500292172387447570080875531002842462002727646367063816531958020271149645805755077133231395881833164790825731218786554806777097126212126561056170733032553159740167058242065879953688453169613384659653035659118823444582576657499974059388261153064772228570460351169216103620379299362366574826080703907036316546232196313193923841110510170689800892941998845140534954264505413254429240789223724066502818922164419890197058252325607667959185100118251170368909192832882776642565026481260424714348087206462283972676596101498123547647078981435969530082351104111747783346230914935599764345176602456069568419879060577771404946743580809330315332836749661503035076868102720709045692483171306425207758972682717326821412843569770615848397477633761506670219845039890098105484693890695897858251238713238301401843678654564558196040100908796513657968507381392735855990706254646471937809011610992016368630851454275478216664521360246605400986428230407975530880206404171034278692756

Première analyse et réflexion

Nous sommes face au célèbre chiffrement RSA de par le nom de l'épreuve et surtout aux variables q,p et n.
Ensuite le flag a été clairement retiré du code... Mais on peut déduire la logique du code...
p et q sont générés aléatoirement par le module openssl du système, impossible de ré-executé le code pour les obtenir... Ils font 2048 bits, sont premier (obligatoire pour RSA) et sont sous forme hexadécimale.
Ensuite le flag est d'abord encodé en hexadécimal avant d'être convertis en décimale.
n est calculé en multipliant p et q qui sont convertis à la volée en base décimale pour le calcul.
Le code nous affiche n.
On nous affiche p, mais volontairement endommagé avec replace()
Puis on affiche le résultat d'un calcul que l'on peut traduire par :
message_chiffré = (flag ^ 65537)%n
Au passage si on connaît un peu RSA on sait que dans ce calcul 65537 correspond a la variable e.
En analysant le contenu d'output.txt on fais le lien avec le code python.
On a donc en mains :

• la variable e
• la variable n
• la variable p, mais sous forme hexadécimale et endommagée dans des proportions inconnues.
• le message chiffré qui contient le flag

Réparer P !

Sans les nombres p et q, impossible de faire quelque chose. Il faut donc constater les dégâts sur p.

En python replace(x,y), remplace dans une chaîne de caractère tout les x par des y. Dans notre cas, replace() a remplacé tout les 9F par FC.
On serait tenté de dire, "ok, on remplace tous les FC par des 9F et voilà !". Oui, mais si des FC été déjà présent avant que les 9F soit transformé ?
Évaluons l'ampleur du problème via un bloc-note et un simple ctrl+f.
Notre chaîne contient 4 bloc FC. Donc 4^4 combinaisons.
Pourquoi 16 possibilités ? Car on peut avoir par exemple, une fois 9F suivis de 3 FC après, mais aussi 3 FC suivis de 1 9F, etc, etc...
Faisons une table de vérité pour y voir plus claire :

0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

Imaginez que 1 représente la position de 9F et 0 celle de FC...

Bon, je vous passe l'étape où j'ai copié 16 fois ma ligne pour changer a la main les valeurs... Oui, c'est fastidieux, mais ca m'a pris que 5 minutes... Et en CTF, le temps, c'est précieux. (En réalité, automatiser cette étape m'aurait un peu aidé pour la partie 2 que je n'ai pas pu flag...)

Une fois que c'est fais, on reconvertit tout en décimale avec int(p_fix,16).
Mais il faut vérifier lequel de ses 16 p est le bon...

Facile ! C'est une équation à une inconnue !
Si n = p * q et que p et q sont des nombres premiers alors n%p=0

Dans nos 16 possibilités, seul une combinaison donne 0. Ouf !

p = 25819261471728040800872878541553321043152462679774978922658476743054196609615260085066604058841210698540997524876908144621893909307784554414162036327648281377886327091581347296131947730522807494517124526464816238370951647893862934621121004498569156746311594099412832189045390297120305667254913052800653355550915386064296154605648963278915319806240264672354108048953297992497878897540380622959711963257886237782410901325113329109297590870937017452019018930748754331672736756917137583464384303108259463535106592418534804375728748609362332554496296532372320633175091519075027001631454173292550340940515568940345329163887

Parfais, on a retrouvé p ! Il nous manque que q !

Calcule de q

Bon la, c'est simple... q = n/p et vu qu'on a trouvé p...

q = 27869881035956015184979178092922248885674897320108269064145135676677416930908750101386898785101159450077433625380803555071301130739332256486285289470097290409044426739584302074834857801721989648648799253740641480496433764509396039330395579654527851232078667173592401475356727873045602595552393666889257027478385213547302885118341490346766830846876201911076530008127691612594913799272782226366932754058372641521481522494577124999360890113778202218378165756595787931498460866236502220175258385407478826827807650036729385244897815805427164434537088709092238894902485613707990645011133078730017425033369999448757627854563

On peut toujours contrôler que nous avons juste en faisant p * q ce qui doit donner exactement n tel qu'il nous est donné dans le fichier output.txt

Déchiffrons !

Nous avons tout ! p,q,n et e. On dégaine cryptool et on lui donne tout ça plus m qui est le message chiffré sous forme decimale.
Rappel de m :

596380963583874022971492302071822444225514552231574984926542429117396590795270181084030717066220888052607057994262255729890598322976783889090993129161030148064314476199052180347747135088933481343974996843632511300255010825580875930722684714290535684951679115573751200980708359500292172387447570080875531002842462002727646367063816531958020271149645805755077133231395881833164790825731218786554806777097126212126561056170733032553159740167058242065879953688453169613384659653035659118823444582576657499974059388261153064772228570460351169216103620379299362366574826080703907036316546232196313193923841110510170689800892941998845140534954264505413254429240789223724066502818922164419890197058252325607667959185100118251170368909192832882776642565026481260424714348087206462283972676596101498123547647078981435969530082351104111747783346230914935599764345176602456069568419879060577771404946743580809330315332836749661503035076868102720709045692483171306425207758972682717326821412843569770615848397477633761506670219845039890098105484693890695897858251238713238301401843678654564558196040100908796513657968507381392735855990706254646471937809011610992016368630851454275478216664521360246605400986428230407975530880206404171034278692756

On se retrouve à la sortie de cryptool avec :

000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000505939127013520401783003587681407753905754948958221559896863467356631933

Ok ça fais beaucoup de zéro, mais on voit qu'à la fin, on a :
505939127013520401783003587681407753905754948958221559896863467356631933

On convertit en hexadécimal:
494E53417B495F77316C6C5F7573335F4F54705F6E3378545F54314D337D

Puis on convertit en ASCII :
INSA{I_w1ll_us3_OTp_n3xT_T1M3}

On a notre flag !