Introducción a la criptografía moderna con Python (Anexo): Parte 2, atacando RSA

Antes de seguir con la segunda tanda de algoritmos vamos a ver como se atacaría un cifrado RSA (probablemente sea bueno volver a hecharle un vistazo para recordar los detalles), obviamente no es un ataque eficiente contra claves grandes pero sirve para entender mejor el algoritmo y por extension todos los de clave pública.

Vamos a por ello que es poca cosa :).

Atacando RSA

Lo ideal sería recuperar la clave privada así que vamos a apuntar a eso, recordemos que hay una parte de la clave pública, n,  que es el producto de dos números primos, p y q y la clave privada se puede obtener a partir de (p - 1) * (q - 1) y la segunda parte de la clave pública.

Ya tenemos por donde empezar, tenemos que obtener ese p y q, una forma sencilla de descomponerlo sería buscar un divisor y dividiendo n por él para obtener la otra parte:

from math import sqrt # Raíz cuadrada

def descomponer(n):
    if n % 2 == 0:
        return n/2, 2

    # Probamos con los valores posibles, de 3 a la raíz cuadrada
    for i in xrange(3, int(sqrt(n)) + 2, 2): 
        if n % i == 0:
            return n/i, i

    raise Exception('Es un número primo')

Para ir probando imáginemonos esta clave pública: (n: 533410509791, exponente público: 65537), si descomponemos ese n obtendremos que es igual a 812431 * 656561 , ya tenemos p y q .

Ahora tenemos que obtener phi , esto con p y q es muy sencillo:

def obtener_phi(p, q):
    return (p - 1) * (q - 1) 

Y con eso ya tenemos el phi, solo nos queda un último paso para obtener la clave privada, y es una función de las usadas en rsa [ rsa_math.py ], inverse_mod con el exponente público y phi como parámetros. Y ya está, hemos recuperado la clave privada:

$ ./rsa.py
Numero de bits: 20
Generando claves...
Pública: (802404159551, 65537)
Privada: (802404159551, 76179067073)

Probando cifrado...
Cifrando...
74825615761
Descifrando... o
�
Probando firmas...
Firmando...
Comprobando firma... False
$ ./rsa_attack.py
n: 802404159551
e: 65537
802404159551 = 943471 * 850481
phi(802404159551) = 802402365600
Exponente privado: %s 76179067073
Clave privada: (802404159551, 76179067073)

Falla el cifrado y la firma porque el número de bits de la clave no es lo suficientemente grande para albergarlos y una mayor necesita mucho más tiempo de cálculo para romperlo del que dispongo :P, pero se puede comprobar que la clave privada es la correcta, aquí está el código completo [ rsa_attack.py ] (necesita el rsa_math.py)

ps: sería una buena práctica modificar el código de la descomposición para hacerlo más rápido, aunque (por suerte para HTTPS :P) llega un punto que es imprácticable... mientras no lleguen los ordenadores cuánticos.

Verdad que era poca cosa :)?, hasta la próxima.

Introducción a la criptografía moderna con Python (1): ARC4

Introducción a la criptografía moderna con Python (2): RSA

Introducción a la criptografía moderna con Python (3): MD5

Introducción a la criptografía moderna (Anexo): Parte 1, atacando ARC4