lunes, 28 de enero de 2019

Criptografía (CXXVII): Solución Reto 26

El  enunciado del reto de criptografía que formulé en este post era el siguiente:

"Y como no hay dos sin tres, otro reto en el que se nos viene a recordar que el tamaño sí importa. Supón que interceptas tres criptogramas, que sabes que se corresponden con un mismo texto en claro (m) y que dichos criptogramas han sido enviados a tres personas diferentes, ¿puedes obtener el texto en claro (m)?.

Nota: en el archivo asociado al reto se indican los valores en decimal correspondientes al módulo (n) y al exponente público (e) de las respectivas claves de las tres personas y los valores en decimal de los criptogramas remitidos a éstas".


Solución: Decía en la primera pista que puse para ayudar a resolver este reto que como en el enunciado se establece que los tres criptogramas se corresponden con un mismo texto en claro (m1 = m2 = m3 = m) y en el archivo asociado al reto (reto_26.txt) vemos que los tres exponentes públicos son iguales a 3 (e1 = e2 = e3 = 3), si los módulos (n1, n2, n3) son primos entre sí, coprimos o primos relativos dos a dos, es decir, si el mcd(ni, nj) = 1 para todo i distinto de j, entonces quizás el teorema chino del resto pueda ayudarnos a calcular m.

Por tanto, en primer lugar lugar creo un script en python para comprobar si los módulos (n1, n2 y n3) son coprimos dos a dos, es decir, si el máximo común divisor de ellos tomados de dos en dos es igual a 1:

import gmpy2

n1 = gmpy2.mpz("141237893326188574204627692926236597832923906875563312407296586270187098500830977089086198296698274977259945744931269328582013379088128599997921784764795876512664274811704263719810554438911212375275389637307533676792707072305650179551138270208913948697352662887831274626962574428552932203244712293494591555511")
n2 = gmpy2.mpz("123540448208108190442413152518982095069440783769340903005935077787457590335172518758985701753251638030875882695636036396466435248787871355571628582178196705443476117178179250809139797395693806996196479271907692595838139580204715620363875721843078735275575567535802910937573265882011978734919390275028927498651")
n3 = gmpy2.mpz("129764663185510756371105783443119016055267527773132919526587344357374102887540763282339924512254838799749899518844225166115902370305244996180768430247896711901844141296135907974189994271244431528747412109545908983450918905491684446582713912788850397046516711871065128208507799172858171575837210017773451264069")

print ''
if gmpy2.gcd(n1, n2)!=1 or gmpy2.gcd(n1, n3)!=1 or gmpy2.gcd(n2, n3)!=1:
   print '[-] Los modulos n1, n2 y n3 no son primos entre si, coprimos o primos relativos dos a dos.'
else:
   print '[+] Los modulos n1, n2 y n3 son primos entre si, coprimos o primos relativos dos a dos.'

Tras ejecutar este script, podemos afirmar que, efectivamente, los módulos de las claves son coprimos dos a dos:
Y, por tanto, el teorema chino del resto nos puede ayudar a obtener el texto en claro (m) que se corresponde con los tres criptogramas (c1, c2 y c3) que se enviaron, respectivamente, a las tres personas.

En este caso, como el texto en claro correspondiente a los tres criptogramas es el mismo (m1 = m2 = m3 = m) y los exponentes públicos de las tres claves son iguales a 3 (e1 = e2 = e3 = 3), el cifrado se ha realizado de la siguiente manera:

c1 = m^3 mod n1
c2 = m^3 mod n2
c3 = m^3 mod n3

Por tanto, tengo el siguiente sistema de congruencias simultáneas:

m^3   c1 mod n1
m^3 ≡ c2 mod n2
m^3 ≡ c3 mod n3

Es decir, se trata de hallar un número (m^3) que dividido entre n1 dé como resto c1, que dividido entre n2 dé como resto c2 y que dividido entre n3 dé como resto c3, y esto puede resolverse utilizando el teorema chino del resto (ver ejemplo en este post).

Una vez que calculo ese número (m^3), lógicamente, el mensaje en claro (m) es la raíz cúbica del mismo.

Para obtener m creo el siguiente script en python:

import gmpy2
import binascii

e = 3
c1 = gmpy2.mpz("37050595107607215425728862670311169686501715648529655096852022500961331010583163575464647323975465331340563969499827140101447214847555787027687021816122499851981434087708434429330112796102295773537370473348683587834276525448296670045256125366626288277440736754846403151338632769822829343206702099866719381340")
n1 = gmpy2.mpz("141237893326188574204627692926236597832923906875563312407296586270187098500830977089086198296698274977259945744931269328582013379088128599997921784764795876512664274811704263719810554438911212375275389637307533676792707072305650179551138270208913948697352662887831274626962574428552932203244712293494591555511")
c2 = gmpy2.mpz("29448590570339337019846906819372551561193767416448894862618308297222578491963152380884360258445115263084004692906639292433283570505453988598060990964248465596120682287756617715751129758488463897763244247700203105329378047389157194907729114086283485641777376575040271414336675879220483713989496496481639193284")
n2 = gmpy2.mpz("123540448208108190442413152518982095069440783769340903005935077787457590335172518758985701753251638030875882695636036396466435248787871355571628582178196705443476117178179250809139797395693806996196479271907692595838139580204715620363875721843078735275575567535802910937573265882011978734919390275028927498651")
c3 = gmpy2.mpz("59230107217036032019940650579150530277946966690389133886396754469356281025902289554077581971768082168768214384534406164927205095184494909622994804896955185141556382755419648502790626246194221204969871419277083672288347576620879291907671233882681829121454526629083136356495332711948312285534940375019766634305")
n3 = gmpy2.mpz("129764663185510756371105783443119016055267527773132919526587344357374102887540763282339924512254838799749899518844225166115902370305244996180768430247896711901844141296135907974189994271244431528747412109545908983450918905491684446582713912788850397046516711871065128208507799172858171575837210017773451264069")

N = n1*n2*n3
mcubo = (c1 * N/n1 * gmpy2.invert(N/n1,n1) + c2 * N/n2 * gmpy2.invert(N/n2,n2) + c3 * N/n3 * gmpy2.invert(N/n3,n3)) % N

m, exact = gmpy2.iroot(mcubo,e)
if exact:
   print ''
   print '[+] Texto en claro (m) ............', binascii.unhexlify(gmpy2.digits(m,16))

Y tras ejecutar este script:
Ya puedo ver la solución al reto: H4574D5 BR04DC457 4774CK.

******** PRÓXIMO RETO
Reto 27: "Un poco de ti es mucho".

sábado, 26 de enero de 2019

Gimnasia mental (XXXII): los siete ladrones

Siete ladrones roban un cargamento de lingotes de oro y a la hora de repartir el botín a partes iguales sobran 6 lingotes.

Como no se ponen de acuerdo en la forma de repartir los lingotes sobrantes, se pelean entre ellos y mueren dos ladrones. Tras realizar de nuevo el reparto entre los supervivientes sobran dos lingotes, por lo que se vuelve a desatar una pelea entre ellos y muere otro ladrón. Ahora sí, el reparto de los lingotes se realiza a partes iguales entre los ladrones que quedan vivos.

a) ¿Cuál es el número mínimo de lingotes que han robado los ladrones para que pueda ser cierto el enunciado?.
b) ¿Cuál es el siguiente número de lingotes que podría hacer cierto el enunciado?. 

Si eres capaz de resolver este problema, sin duda, podrás resolver también este reto de criptografía.


Solución: utilizo lo que he entendido del teorema chino del resto para resolver este problema.

Tenemos el siguiente sistema de congruencias lineales simultáneas:

X ≡ 6 (mod 7)
X ≡ 2 (mod 5)
X ≡ 0 (mod 4)

Es decir, buscamos el número X que dividido entre 7 da como resto 6, que dividido entre 5 da como resto 2 y que dividido entre 4 da como resto 0.

Como los módulos son primos entre sí dos a dos, es decir, el máximo común divisor de ellos tomados dos a dos es igual a 1, podemos utilizar el teorema chino del resto para resolverlo:

mcd(7, 5) = 1
mcd(7, 4) = 1
mcd(5, 4) = 1

Lo primero que tenemos que hacer para calcular X es obtener el módulo (N), que sería el producto de los módulos de las tres congruencias:

N = 7 * 5 * 4 = 140

Lo segundo que tenemos que hacer es dividir el nuevo módulo (N) entre los módulos de las tres congruencias:

N1 = 140 / 7 = 20
N2 = 140/ 5 = 28
N3 = 140 / 4 = 35

Lo tercero que tenemos que hacer es calcular el inverso mutiplicativo modular de los valores obtenidos en el paso anterior, es decir:

20 * s1 ≡ 1 (mod 7)
28 * s2 ≡ 1 (mod 5)
35 * s3 ≡ 1 (mod 4)

Cuando los números son pequeños, como es el caso, podemos utilizar la fuerza bruta para calcular el inverso multiplicativo modular, es decir, basta con ir probando todos los números (1, 2, …), uno detrás de otro, hasta encontrarlo.

s1 = 6
s2 = 2
s3 = 3

Finalmente encontramos la solución particular:

6 * 20 * 6 + 2 * 28 * 2 + 0 * 35 * 3 = 720 + 112 + 0 = 832

832 X (mod 140)

X = 132

Y la solución general sería:

X = 132 + 140 Y

Para Y = 1: X = 132 + 140 * 1= 272
Para Y = 2: X = 132 + 140 * 2= 412

Por tanto, la respuesta a la primera pregunta es que los ladrones han robado como mínimo 132 lingotes de oro y a la segunda, es decir, el siguiente número de lingotes robados que podría hacer cierto el enunciado, es 272.


Este mismo teorema se puede utilizar para resolver también este reto de criptografía.

Dejo un pequeño script en python que resuelve el problema planteado en este post y que puede servir, con pequeñas variaciones, para resolver el citado reto de criptografía.

import gmpy2

a1 = 6
n1 = 7
a2 = 2
n2 = 5
a3 = 0
n3 = 4

N = n1*n2*n3
X = (a1 * N/n1 * gmpy2.invert(N/n1,n1) + a2 * N/n2 * gmpy2.invert(N/n2,n2) + a3 * N/n3 * gmpy2.invert(N/n3,n3)) % N

print ''
print '[+] Respuesta pregunta 1: los ladrones han robado como minimo', X, 'lingotes de oro.'
print ''
print '[+] Respuesta pregunta 2: el siguiente numero de lingotes robados que podria hacer cierto el enunciado es', X+N,'.'

miércoles, 23 de enero de 2019

Criptografía (CXXVI): Reto 26

Otro reto de dificultad media sobre criptografía, relacionado con el anterior y, por tanto, en el que también se ve involucrado el criptosistema RSA.

Como siempre, se admiten soluciones en forma de comentarios a esta entrada. Pasado un tiempo iré proporcionando pistas para su resolución, un máximo de tres, y posteriormente actualizaré este post con la solución.

Reto 26: "El tamaño sí importa (III)".

Y como no hay dos sin tres, otro reto en el que se nos viene a recordar que el tamaño sí importa. Supón que interceptas tres criptogramas, que sabes que se corresponden con un mismo texto en claro (m) y que dichos criptogramas han sido enviados a tres personas diferentes, ¿puedes obtener el texto en claro (m)?.

Nota: en el archivo asociado al reto se indican los valores en decimal correspondientes al módulo (n) y al exponente público (e) de las respectivas claves de las tres personas y los valores en decimal de los criptogramas remitidos a éstas.

Dificultad:
Tipo:           Criptografía.

Recursos:   reto_26.txt.

******** 26/01/2019
Pista 1:     Como en el enunciado se dice que los tres criptogramas se corresponden con un mismo texto en claro (m1 = m2 = m3 = m) y en el archivo asociado al reto vemos que los tres exponentes públicos son iguales a 3 (e1 = e2 = e3 = 3), si los módulos (n1, n2, n3) son primos entre sí, coprimos o primos relativos dos a dos, es decir, si el mcd(ni, nj) = 1 para todo i distinto de j, entonces quizás el teorema chino del resto pueda ayudarnos a calcular m.

******** 27/01/2019
Pista 2:     Ver este post donde se explica un ejemplo de aplicación del teorema chino del resto y se deja un pequeño script en python que, con pequeñas modificaciones, puede servir para resolver este reto.

******** 28/01/2019
Solución.

******** PRÓXIMO RETO
Reto 27:   "Un poco de ti es mucho".

martes, 22 de enero de 2019

Criptografía (CXXV): Solución Reto 25

El  enunciado del reto de criptografía que formulé en este post era el siguiente:

"El primer reto que puse en este blog con este mismo título, "El tamaño sí importa", era un reto de esteganografía, pero como en él decía creo que el tamaño importa en muchos ámbitos de nuestra vida, y la criptografía no es una excepción. Dados los archivos asociados al reto, con la clave pública y el criptograma, ¿puedes descifrar este último?".

Solución: En primer lugar creo un script en python para obtener los parámetros de la clave pública (public_key.pem) que nos dan como recurso asociado al reto:

from Crypto.PublicKey import RSA

# Obtener parametros de la clave publica

pubkey = open('public_key.pem', 'r')
param_pubkey = RSA.importKey(pubkey.read())
print ''
print '   n  ...:', param_pubkey.n
print '   e  ...:', param_pubkey.e
pubkey.close()

Tras ejecutar este script veo el módulo (n) y el exponente de la clave pública (e):
Como se observa en la figura anterior, el exponente de la clave pública (e) es 3. El que sea tan pequeño presenta como ventaja el que se agiliza el tiempo del cifrado de los mensajes en claro (m), pero si estos últimos son cortos (otra vez vemos que el tamaño sí importa) se podrían descifrar de forma muy fácil sin disponer del exponente de la clave privada (d), ya que para ello bastaría con calcular la raíz cúbica del criptograma (c).

¿Por qué ocurre esto?. Muy fácil, recuerdo que el cifrado en RSA se realiza de la siguiente manera:

c = m^e mod n

Por tanto, si e = 3 y m < n^(1/3) entonces: c = m^3 y, en consecuencia, la raíz cúbica del criptograma (c) nos daría el mensaje en claro (m), es decir: m = c^(1/3).

Compruebo si en este caso el criptograma (c) es los suficientemente corto como para descifrarlo de la forma que se ha indicado anteriormente. Para ello creo el siguiente script en python:

#!/usr/bin/env python

#
# Ataque exponente publico bajo
#

import gmpy2
import binascii

n = 25358708488728181547379765072637472261822866039782321290930545283699835785844177134795501427697386547523791810191564809603212812573582763202006937344282814899554035096947429817448213415956367329710417740775992913107881882863330779615693984157953732370112680698175512130953235440345474556520766813072401642619809013843857569878005633859523035343481070924471866175937749288550580672605895380631590884330443015408874300766985932923428115805390406727912357891382757381978366684003693502532684457914223908684664564959071411555168826004659130324369048267651740694589068661464981037950639216053381207201710576480024833267099
e = 3
criptograma = open('criptograma.enc', 'rb')
c  = criptograma.read()
c = binascii.b2a_hex(c)
c = int(c,16)
criptograma.close()

print ''
print 'Modulo (n) ....................', n
print ''
print 'exponente clave publica (e) ...', e
print ''
print 'Criptograma (c) ...............', c

m,exacta = gmpy2.iroot(c,e)

if exacta:
   print ''
   print 'Texto en claro (m) ............', binascii.unhexlify(gmpy2.digits(m,16))

Y tras ejecutar este script confirmo que, efectivamente, el criptograma (c) puede descifrarse sin más que calcular la raíz cúbica del mismo:
Por tanto, la solución de este reto es: N0 35 UN4 BU3N4 1D34 U71L1Z4R 3 C0M0 3XP0N3N73 D3 L4 CL4V3 PUBL1C4.

******** PRÓXIMO RETO
Reto 26: "El tamaño sí importa (III)".

sábado, 19 de enero de 2019

Criptografía (CXXIV): Reto 25

Continúo con un reto fácil sobre criptografía. En esta ocasión se ve involucrado el criptosistema moderno de cifrado asimétrico más utilizado actualmente, RSA.

Como siempre, se admiten soluciones en forma de comentarios a esta entrada. Pasado un tiempo iré proporcionando pistas para su resolución, un máximo de tres, y posteriormente actualizaré este post con la solución.

Reto 25: "El tamaño sí importa (II)".

El primer reto que puse en este blog con este mismo título, "El tamaño sí importa", era un reto de esteganografía, pero como en él decía creo que el tamaño importa en muchos ámbitos de nuestra vida, y la criptografía no es una excepción. Dados los archivos asociados al reto, con la clave pública y el criptograma, ¿puedes descifrar este último?.

Dificultad:
Tipo:           Criptografía.

Recursos:   public_key.pem.
                   criptograma.enc.

******** 20/01/2019
Pista 1:     Como habrás observado el exponente de la clave pública (e) es igual a 3. Un número muy pequeño cuya utilización presenta como ventaja el agilizar el tiempo de cifrado de los mensajes en claro (m), pero que tiene claros inconvenientes. Por ejemplo: ¿Qué ocurre cuando e = 3 y m < n^(1/3)?.

******** 22/01/2019
Solución.

******** PRÓXIMO RETO
Reto 26:   "El tamaño sí importa (III)".

Criptografía (CXXIII): Solución Reto 24

El  enunciado del reto de criptografía que puse en este post era el siguiente:

"Para descifrar el contenido del archivo asociado al reto y así obtener la solución necesitarás la clave: U0FNVUVM".

SoluciónEn la primera pista que puse para ayudar a resolver este reto decía que si sabías o averiguabas quién es la persona que aparece en la imagen que ilustra este post entonces también sabrías el criptosistema involucrado en este reto. Pues bien, busco con Google imágenes y obtengo: "Consulta más probable para esta imagen: Georges Painvin"y la Wikipedia nos cuenta que éste fue un criptoanalista francés cuyo principal logro fue romper el cifrado ADFGVX utilizado por el ejército alemán durante la Primera Guerra Mundial.
Con lo que, como también decía, puedo concluir que el criptosistema involucrado en este reto es el ADFGVX (ya escribí en su día varios posts sobre él en este blog. Ver primero de ellos).

Además, en el post en el que planteé el enunciado de este reto decía que el criptosistema involucrado está muy relacionado con el código morse (las letras ADFGVX, que son las únicas que aparecen en los criptogramas cifrados mediante este método, fueron elegidas porque son muy diferentes entre sí en código morse y ésto evitaba errores en la transmisión de los mensajes), mientras que en la segunda pista decía que el archivo de audio asociado al reto (reto24.wav) contiene precisamente una señal en código morse.

Esto último es fácilmente comprobable escuchando el archivo de audio y viendo el espectrograma de la señal:
Si decodifico esta señal enseguida reconozco y, por tanto, se confirma que el criptosistema empleado es el ADFGVX, y obtengo el criptograma.
Ahora ya, mediante la clave que se proporciona en el enunciado del reto ("U0FNVUVM"), debería estar en disposición de revertir la fase de transposición de columnas realizada en el cifrado del texto en claro, pero ésta ni parece ser muy adecuada para este criptosistema (en principio debería contener sólo letras y ésta contiene el número 0) ni parece tener nada que ver con el código morse, tal y como se afirma en la primera pista dada para ayudar a resolver este reto.

Veo si la clave dada está codificada de alguna manera, para lo que, en primer lugar, pruebo a ver si está codificada en base64:
Bastante mejor :) (ver Samuel Morse).

Utilizando como clave "SAMUEL" revierto la fase de transposición de las columnas realizada en el cifrado del texto en claro, de la siguiente manera:

1.- El criptograma tiene 442 caracteres de largo y la clave 6. Divido 442 entre 6 y obtengo que el cociente es 73 y el resto 4, por lo que tendría una tabla de 6 columnas, 4 de ellas con 74 caracteres y 2 con 73.

2.- El orden de las 6 columnas de la tabla (de izquierda a derecha) se correspondería con el orden alfabético de los 6 caracteres de la clave, es decir, sería: "A", "E", "L", "M", "S", "U".

3.- Dispongo debajo de cada una de estas columnas (por columna, de arriba a abajo y de izquierda de derecha) los caracteres del criptograma, ya he dicho que 4 de esas columnas tendrían 74 caracteres y las otras 2 tendrían 73, pero, ¿cuáles de ellas 74 y cuáles 73?. Si repaso el primer post que escribí sobre este método veo que las 4 columnas de 74 caracteres serían las correspondientes a los 4 primeros caracteres de la clave en su posición original ("S", "A", "M", "U"), mientas que la 2 columnas de 73 caracteres se corresponden con las del resto de ellos ("E" y "L"). Es decir:
4.- Y finalmente, ordeno las columnas conforme a la posición original de los caracteres de la clave utilizada (en este caso: "S","A","M","U","E", "L") y leo los caracteres de la tabla resultante por fila, de izquierda a derecha y de arriba a abajo:
Con lo que ya habría revertido la fase de transposición de columnas y lo único que faltaría para obtener el texto en claro es realizar un análisis de frecuencias de los pares de caracteres obtenidos con relación a los caracteres del idioma en el que esté escrito el mensaje en claro (en nuestro caso el español). De esta forma resolvería la fase de sustitución monoalfabética realizada como primera fase en el proceso de cifrado del texto en claro.  

Podríamos realizar el análisis de frecuencias manualmente, pero es mucho más cómodo y rápido hacerlo utilizando una herramienta on-line especializada. Para ello, sustituyo cada par de caracteres obtenido hasta ahora por un carácter arbitrario (da igual por cuál, pero yo voy a sustituir cada uno de ellos por la letra que más probablemente le correspondería conforme a la frecuencia de aparición de éstas en un texto en claro escrito en español):
Incluyo como texto cifrado en la herramienta el resultado de la sustitución realizada en el paso anterior:
Y obtengo el siguiente texto en claro (salvo pequeño error que es muy fácil de detectar y subsanar):

LOS ALEMANES CREIAN QUE EL CIFRADO ADFGVX ERA INVULNERABLE AL CRIPTOANALISIS YA QUE COMBINABA SUSTITUCION Y TRANSPOSICION Y NO ERA POSIBLE REALIZAR UN ANALISIS DE FRECUENCIAS SIN EMBARGO GEORGES PAINVIN CONSIGUIO ROMPERLO Y SU NOMBRE ES LA SOLUCION DE ESTE RETO

Por tanto, la solución es: "GEORGES PAINVIN".

******** PRÓXIMO RETO
Reto 25: "El tamaño sí importa (II)".

domingo, 13 de enero de 2019

Criptografía (CXXII): Solución Reto backdoor "rsalot"

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

Este reto tiene el título "rsalot" y mi valoración sobre su dificultad es: .

Su enunciado dice lo siguiente:


The flag is encrypted using a system that makes use of prime factorization of large numbers. Decrypt the flag from this.

Solución: lo primero que se me ocurrió fue crear un script en python para obtener el módulo y el exponente (n y e, respectivamente) de las 100 claves públicas que nos dan como recursos asociados al reto.

from Crypto.PublicKey import RSA

i = 1
print ''
print '[+] Obteniendo el modulo (n) y el exponente publico (e) de las 100 claves'
while i < 101:
    pubkeyi = open(str(i)+'.pem', 'r')
    publickeyi = RSA.importKey(pubkeyi.read())
    ni = publickeyi.n
    ei = publickeyi.e
    print ''
    print 'n'+str(i)+' ...', ni
    print 'e'+str(i)+' ...', ei
    pubkeyi.close()
    i+=1
Por lo que veo todas las claves dadas tienen el mismo exponente público, el número de Fermat para n = 4 (Fn = 22n + 1;  F4 = 224 + 1 = 65537), y a simple vista no veo nada que me pueda revelar alguna vulnerabilidad de estas claves que me permita intentar atacar el criptograma (c) que se nos proporciona como recurso asociado al reto en el archivo flag.enc.

Lo siguiente que se me ocurrió fue completar el script anterior para comprobar si algunos de los módulos (n) comparten factores primos, ya que si ésto es así podría factorizar muy fácilmente dichos módulos y obtener después las claves privadas correspondientes. Es decir, si el máximo común divisor (MCD) de los módulos (n) de dos claves públicas es diferente de 1 entonces dichos módulos comparten como factor ese  MCD y el otro factor de los respectivos módulos puede ser obtenido dividiendo cada uno de ellos entre este último, con lo que ya estaríamos en disposición de calcular el exponente privado (d) de ambas claves.

from fractions import gcd
from Crypto.PublicKey import RSA

primo_compartido = 0
i = 1
print ''
print '[+] Comprobando si los modulos de las claves publicas comparten algun factor primo'
while i < 100:
    pubkeyi = open(str(i)+'.pem', 'r')
    publickeyi = RSA.importKey(pubkeyi.read())
    ni = publickeyi.n
    ei = publickeyi.e
    j = i+1
    while j < 101:
        pubkeyj = open(str(j)+'.pem', 'r')
        publickeyj = RSA.importKey(pubkeyj.read())
        nj = publickeyj.n
        ej = publickeyj.e
        if gcd(ni,nj) != 1:
           primo_compartido = 1
           print '[+] Los modulos n'+str(i)+' y n'+str(j)+' comparten un factor primo'
        pubkeyj.close()
        j+=1
    pubkeyi.close()
    i+=1

if primo_compartido == 1:
   print '[+] Se han encontrado modulos que comparten algun factor primo'
else:
   print '[-] No se han encontado modulos que compartan algun factor primo.'
A la vista de los resultados sabemos que los módulos (n) de las claves públicas 64 y 87 (64.pem y 87.pem, respectivamente) comparten un factor primo, por lo que podemos calcular el exponente privado (d) de cada una de sus correspondientes claves privadas. Alguna de estas últimas puede ser que descifre el criptograma (c) que contiene el archivo flag.enc.

Para realizar todo ello, completo el script anterior de la siguiente manera:

from fractions import gcd
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
from base64 import b64decode

def calcular_d(e, fi):
    a, b, u = 0, fi, 1
    while e > 0:
        q = b // e
        e, a, b, u = b % e, u, e, a - q * u 
    if b == 1:
       return a % fi
    print '[-] Error al calcular el exponente de la clave privada'

rsakeys = []

i = 1
print ''
print '[+] Comprobando si los modulos de las claves publicas comparten algun factor primo'
while i < 100:
    pubkeyi = open(str(i)+'.pem', 'r')
    publickeyi = RSA.importKey(pubkeyi.read())
    ni = publickeyi.n
    ei = publickeyi.e
    j = i+1
    while j < 101:
        pubkeyj = open(str(j)+'.pem', 'r')
        publickeyj = RSA.importKey(pubkeyj.read())
        nj = publickeyj.n
        ej = publickeyj.e
        if gcd(ni,nj) != 1:
           print '[+] Los modulos n'+str(i)+' y n'+str(j)+' comparten un factor primo'
           pi = ni/gcd(ni,nj)
           qi = gcd(ni,nj)
           di = calcular_d(ei, (pi-1)*(qi-1))
           print '[+] Construyendo clave privada a partir de n'+str(i)+', e'+str(i)+', d'+str(i)+', p'+str(i)+', q'+str(i)
           rsakeys.append(RSA.construct((ni, ei, di, pi, qi, )))
           pj = nj/gcd(ni,nj)
           qj = gcd(ni,nj)
           dj = calcular_d(ej, (pj-1)*(qj-1))
           print '[+] Construyendo clave privada a partir de n'+str(j)+', e'+str(j)+', d'+str(j)+', p'+str(j)+', q'+str(j)
           rsakeys.append(RSA.construct((nj, ej, dj, pj, qj, )))
        pubkeyj.close()
        j+=1
    pubkeyi.close()
    i+=1

if rsakeys != []:
   print '[+] Se han encontrado modulos que comparten algun factor primo'
   flag = open('flag.enc', 'rb')
   c = flag.read()
   flag.close()
   print '[+] Intentando el descifrado con las claves privadas construidas'
   for rsakey in rsakeys:
       try:
           rsakey = PKCS1_OAEP.new(rsakey)
           m = rsakey.decrypt(b64decode(c)) 
           print ""
           print 'texto en claro (m) ...', m
       except:
           pass
else:
   print '[-] No se han encontado modulos que compartan algun factor primo.'  

Y tras ejecutarlo ya podemos ver el texto en claro (m) y la flag contenida en él:
Por tanto, la flag es: b767b9d1fe02eb1825de32c6dacf4c2ef78c738ab0c498013347f4ea1e95e8fa.

domingo, 6 de enero de 2019

Criptografía (CXXI): Solución Reto backdoor "complex-rsa"

En este post la solución a uno de los retos de criptografía de backdoorctf17.

Este reto tiene el título "complex-rsa" y mi valoración sobre su dificultad es: .

Su enunciado dice lo siguiente:


noob heard that single RSA encryption can be cracked sometimes due to bad implementation, so he encrypted the message twice. See if you can break it.

Y como recursos asociados al reto nos dan los siguientes:

- pubkey1.
- pubkey2.
- flag.enc.

Solución: creo un script en python para obtener el módulo y el exponente (n y e, respectivamente) de ambas claves públicas.

from Crypto.PublicKey import RSA

# Obtener parametros de ambas claves publicas

print ''
print 'pubkey1:'

pubkey1 = open('pubkey1', 'r')
param_pubkey1 = RSA.importKey(pubkey1.read())
n1 = param_pubkey1.n
e1 = param_pubkey1.e
print '   n1  ...:', n1
print '   e1  ...:', e1
pubkey1.close()

print ''
print 'pubkey2:'

pubkey2 = open('pubkey2', 'r')
param_pubkey2 = RSA.importKey(pubkey2.read())
n2 = param_pubkey2.n
e2 = param_pubkey2.e
print '   n2  ...:', n2
print '   e2  ...:', e2
pubkey2.close()

Ejecuto este script y obtengo lo siguiente:
Como se observa en la figura anterior el módulo (n) es el mismo en ambos casos, en decimal:

554264859105764813308660999731057971935100899008191382001838196926947542874512190874402841957978974562758951331436856029517893995971179950228409634742368823490858553015862605452077729540463185207987338059905256552215054036643656077780363670065154151957507791559734841291875379738678210733333998195096643491711

Mientras que el exponente público de la primera clave en decimal es:

37507589401

y el exponente público de la segunda clave en decimal es:

4268405784672563577566143285906824408738650526784746749170468318123056940297449811287105187623419766934370809781249030117023876215912795037797160740003478418767197450012472858547143622542113157392499087427939336504102036205305906052998841826136038160560099357503377453502865716581429205507834478651

Tal y como se puede ver el exponente público de la segunda clave es muy grande, por lo que el exponente de la clave privada (d) podría estar expuesto (ver ataque de Wiener), ya que en consecuencia éste sería pequeño.

Por otra parte, en el enunciado se nos dice que el mensaje en claro (m) se cifró dos veces, es decir, entiendo que el criptograma (c2) que contiene el archivo flag.enc se obtuvo de la siguiente manera:

c1 = m^e1 mod n

c2 = c1^e2 mod n

Por lo que:

c2 = (m^e1 mod n) ^e2 mod n = m^(e1*e2) mod n 

Dicho todo esto creo el siguiente script en python para obtener la flag:

import owiener
import hashlib

# Ataque de Wiener

print('')
print ('*** Ataque de Wiener')

e1 = 37507589401
e2 = 4268405784672563577566143285906824408738650526784746749170468318123056940297449811287105187623419766934370809781249030117023876215912795037797160740003478418767197450012472858547143622542113157392499087427939336504102036205305906052998841826136038160560099357503377453502865716581429205507834478651
e  = e1*e2
n  = 554264859105764813308660999731057971935100899008191382001838196926947542874512190874402841957978974562758951331436856029517893995971179950228409634742368823490858553015862605452077729540463185207987338059905256552215054036643656077780363670065154151957507791559734841291875379738678210733333998195096643491711
d  = owiener.attack(e, n)

print ('d ...........:', d)

# Descifrado

print('')
print ('*** Descifrado')

flag = open('flag.enc', 'rb')
c  = flag.read()
c  = int(c.hex(),16)

m  = pow(c, d, n)

print ('c ...........:', c)
print('')
print ('m ...........:', m)

mh = hex(m)

print('')
print ('m (hex) .....:', mh)

# Representacion ascii del texto en claro en hexadecimal

print('')
print ('*** Flag')

ma = bytearray.fromhex(mh[2:]).decode()

print('m (ascii) ...:', ma)

# Hash SHA256 de la flag

print('')
print ('*** Hash SHA256 de la flag')

ms = hashlib.sha256(ma.encode('utf-8')).hexdigest()

print('m (SHA256) ...:', ms)

Y tras ejecutarlo obtengo la flag y el hash SHA256 de la misma para introducirlo como solución al reto: