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 (F_n = 2²ⁿ + 1;  F₄ = 2²⁴ + 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.