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: