sábado, 4 de agosto de 2018

Criptografía (CIX): Solución Reto CTFLearn "Skynet Is (Almost) Taking Over"

En este post la solución a otro de los retos de criptografía de la plataforma CTFLearn.

Este reto tiene el título "Skynet Is (Almost) Taking Over" y mi valoración sobre su dificultad es: .

Su enunciado dice lo siguiente:


Skynet is using a very small list of primes for RSA style encryption purposes. In fact their list is only the size of the smallest odd prime. One of the robots sent a message to three other robots. These are futuristic robots with the ability to use quantum computing and so they don't mind prime factoring huge numbers.You can't do that though. Find out what message the robot sent to his friends. Flag is in flag{} format.

Y nos dan los siguientes datos:


e: 65537

c1: 5024836662627906750454817701922271080214720765897113783786369197810770999608528443597447448508876214100063962982376037712548944474807897847869334582773452689962992522987755069402952836848501053684233233850594080254869
n1: 10603199174122839808738169357706062732533966731323858892743816728206914395320609331466257631096646511986506501272036007668358071304364156150345138983648630874220488837685118753574424686204595981514561343227316297317899

c2: 130884437483098301339042672379318680582507704056215246672305503902799253294397268030727540524911640778691710963573363763216872030631281953772411963153320471648783848323158455504315739311667392161460121273259241311534
n2: 5613358668671613665566510382994441407219432062998832523305840186970780370368271618683122274081615792349154210168307159475914213081021759597948038689876676892007399580995868266543309872185843728429426430822156211839073

c3: 40136988332296795741662524458025734893351353026652568277369126873536130787573840288544348201399567767278683800132245661707440297299339161485942455489387697524794283615358478900857853907316854396647838513117062760230880
n3: 43197226819995414250880489055413585390503681019180594772781599842207471693041753129885439403306011423063922105541557658194092177558145184151460920732675652134876335722840331008185551706229533179802997366680787866083523

Solución: Evidentemente, el enunciado del reto nos dice que los módulos que nos dan comparten factores no triviales entre sí ("...is using a very small list of primes for RSA style encryption purposes"). Por tanto, descifrar los criptogramas será un asunto trivial, ya que si un atacante puede encontrar dos módulos RSA distintos, n1 y n2, que comparten un factor primo pero tienen diferentes segundos factores primos, puede factorizar fácilmente y de forma muy eficiente ambos módulos calculando su MCD para obtener el factor primo compartido y dividiendo cada uno de ellos entre este último para encontrar el otro factor primo de cada uno de ellos, con lo que el atacante puede entonces calcular ambas claves privadas.

Veámoslo. Para ello utilizo el software "Fortaleza de Cifrados" (Herramientas > Cálculo del MCD):
mcd(n1, n2) = 1173821128899717744763168991586024137475923012574062580049287532012184965219319828285650431646942194944437493
mcd(n1, n3)
= 9033062119150775356115605417902072538098631081058159551678022048966520848600866260935959311606867286026034943
mcd(n2,n3) = 4782124405899304514745349491894350894228449009067812460621545024973542842784947583120716593095450482771264061

Con lo que queda claro que lo que decía el enunciado es cierto ("In fact their list is only the size of the smallest odd prime"), para calcular las claves se han utilizado sólo esos 3 números primos diferentes.

Descifro ahora los tres criptogramas. Para ello utilizo el software "ExpoCrip" (Criptosistemas > RSA):

p1 = 1173821128899717744763168991586024137475923012574062580049287532012184965219319828285650431646942194944437493

q1 = n1 / p1 = 9033062119150775356115605417902072538098631081058159551678022048966520848600866260935959311606867286026034943
d1 = 4058813459285894720262057382498008693884059743178992752830677789043240634075531780497947803398409616647168596996375898813393632803863008293266814189602127894014263466865909580208566775955662894025240267470669009026537

c1 = 5024836662627906750454817701922271080214720765897113783786369197810770999608528443597447448508876214100063962982376037712548944474807897847869334582773452689962992522987755069402952836848501053684233233850594080254869
m1149691910197864237420173554223426538596418158029693

En hexadecimal:
666C61677B77696C6C5F68655F62655F6261636B7D

ASCII:
flag{will_he_be_back}

Con lo que ya sabemos la flag para pasar este reto, pero descifro los dos últimos criptogramas.

p2 = 4782124405899304514745349491894350894228449009067812460621545024973542842784947583120716593095450482771264061

q2 = n2 / p2 = 1173821128899717744763168991586024137475923012574062580049287532012184965219319828285650431646942194944437493
d2 = 761957958351811574665908973055198601684911845712156707315390608408869221581643107249417210892016022838062099282438454813702653752551827888703014635138157271543974622958219283063532121046162838351879479076989192389633

c2 = 130884437483098301339042672379318680582507704056215246672305503902799253294397268030727540524911640778691710963573363763216872030631281953772411963153320471648783848323158455504315739311667392161460121273259241311534
m2 = 149691910197864237420173554223426538596418158029693

En hexadecimal:
666C61677B77696C6C5F68655F62655F6261636B7D

ASCII:
flag{will_he_be_back}

Y finalmente el último criptograma.

p3 = 9033062119150775356115605417902072538098631081058159551678022048966520848600866260935959311606867286026034943

q3 = n3 / p3 = 4782124405899304514745349491894350894228449009067812460621545024973542842784947583120716593095450482771264061
d3 = 34778852757328807131051299342491994341058130963838199538975252386805579197756200373810293576383442829820831731234905058826980321999439169115820880963749482420614868325205813650296015377675722669359309160247107758432873

c3 = 40136988332296795741662524458025734893351353026652568277369126873536130787573840288544348201399567767278683800132245661707440297299339161485942455489387697524794283615358478900857853907316854396647838513117062760230880
m3 = 149691910197864237420173554223426538596418158029693

En hexadecimal:
666C61677B77696C6C5F68655F62655F6261636B7D

ASCII:
flag{will_he_be_back}


Por tanto, lo que ya sabíamos descifrando el primer criptograma, la solución es: flag{will_he_be_back}.

No hay comentarios:

Publicar un comentario