Ir al contenido principal

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

Imagen
De
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
m1 = 149691910197864237420173554223426538596418158029693

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}.
Etiquetas:

Comentarios

Publicar un comentario

Entradas populares de este blog

Criptografía (I): cifrado Vigenère y criptoanálisis Kasiski

De
Hace unos días mi amigo Iñaki Regidor ( @Inaki_Regidor ), a quien dedico esta entrada :), compartió en las redes sociales un post titulado "Criptografía: el arte de esconder mensajes"  publicado en uno de los blogs de EiTB . En ese post se explican ciertos métodos clásicos para cifrar mensajes , entre ellos el cifrado de Vigenère , y , al final del mismo, se propone un reto consistente en descifrar un mensaje , lo que me ha animado a escribir este post sobre el método Kasiski  para atacar un cifrado polialfabético ( conociendo la clave descifrar el mensaje es muy fácil, pero lo que contaré en este post es la forma de hacerlo sin saberla ). El mensaje a descifrar es el siguiente: LNUDVMUYRMUDVLLPXAFZUEFAIOVWVMUOVMUEVMUEZCUDVSYWCIVCFGUCUNYCGALLGRCYTIJTRNNPJQOPJEMZITYLIAYYKRYEFDUDCAMAVRMZEAMBLEXPJCCQIEHPJTYXVNMLAEZTIMUOFRUFC Como ya he dicho el método de Vigenère es un sistema de sustitución polialfabético , lo que significa que, al contrario que en un sistema de
103 comentarios
Leer más

Criptografía (XXIII): cifrado de Hill (I)

De
En este post me propongo explicar de forma comprensible lo que he entendido sobre el cifrado de Hill , propuesto por el matemático Lester S. Hill , en 1929, y que se basa en emplear una matriz como clave  para cifrar un texto en claro y su inversa para descifrar el criptograma correspondiente . Hay tres cosas que me gustan de la criptografía clásica, además de que considero que ésta es muy didáctica a la hora de comprender los sistemas criptográficos modernos: la primera de ellas es que me "obliga" a repasar conceptos de matemáticas aprendidos hace mucho tiempo y, desgraciadamente, olvidados también hace demasiado tiempo, y, por consiguiente, que, como dice  Dani , amigo y coautor de este blog, me "obliga" a hacer "gimnasia mental"; la segunda es que, en la mayoría de las ocasiones, pueden cifrarse y descifrase los mensajes, e incluso realizarse el criptoanálisis de los criptogramas, sin más que un simple lápiz y papel, es decir, para mi es como un pasat
5 comentarios
Leer más

¿Qué significa el emblema de la profesión informática? (I)

De
Todas o muchas profesiones tienen un emblema que las representa simbólicamente y en el caso de la  informática: " es el establecido en la resolución de 11 de noviembre de 1977  para las titulaciones universitarias superiores de informática, y  está constituido por una figura representando en su parte central  un  núcleo toroidal de ferrita , atravesado por  hilos de lectura,  escritura e inhibición . El núcleo está rodeado por  dos ramas : una  de  laurel , como símbolo de recompensa, y la otra, de  olivo , como  símbolo de sabiduría. La  corona  será la  de la casa real  española,  y bajo el escudo se inscribirá el acrónimo de la organización. ". Veamos los diferentes elementos tomando como ejemplo el emblema del COIIE/EIIEO (Colegio Oficial de Ingenieros en Informática del País Vasco/ Euskadiko Informatikako Ingeniarien Elkargo Ofiziala ) . Pero no sólo el COIIE/EIIEO adopta el emblema establecido en dicha resolución, sino que éste se adopta también como im
Publicar un comentario
Leer más