Close Enough

2 minutos de lectura

Se nos dice que una implementación de RSA utiliza un número primo y el siguiente número primo. Tenemos el texto cifrado:

4881495507745813082308282986718149515999022572229780274224400469722585868147852608187509420010185039618775981404400401792885121498931245511345550975906095728230775307758109150488484338848321930294974674504775451613333664851564381516108124030753196722125755223318280818682830523620259537479611172718588812979116127220273108594966911232629219195957347063537672749158765130948724281974252007489981278474243333628204092770981850816536671234821284093955702677837464584916991535090769911997642606614464990834915992346639919961494157328623213393722370119570740146804362651976343633725091450303521253550650219753876236656017

Y también el código fuente:

from Crypto.Util.number import getPrime, bytes_to_long  
from Crypto.PublicKey import RSA
from secret import flag, getNextPrime

p = getPrime(1024)
q = getNextPrime(p)
n = p * q
e = 65537

key = RSA.construct((n, e)).export_key().decode()

with open("key", "w") as f:
    f.write(key)

m = bytes_to_long(flag.encode())
c = pow(m, e, n)
print(f"c = {c}")

Nótese que no tenemos la función getNextPrime. Además, se nos proporciona la clave pública en formato PEM:

Podemos extraer $n$ y $e$ de este archivo (aunque ya sabemos que $e = 65537$). Luego, la idea es calcular $\sqrt{n}$, ya que sabemos que $n = p \cdot q$ y $p$ y $q$ son cercanos (podemos deducir que son números primos consecutivos).

Entonces, una vez que tengamos $\sqrt{n}$, podemos empezar a reducir el resultado hasta que tengamos un número primo. Después, solo tenemos que aumentarlo para encontrar el siguiente número primo.

Una vez que tenemos los dos números primos $p$ y $q$, el descifrado de RSA es trivial.

Aquí tenemos un script en Python que resuelve el reto:

#!/usr/bin/env python3

from Crypto.Util.number import isPrime
from Crypto.PublicKey import RSA

from gmpy2 import iroot

c = 4881495507745813082308282986718149515999022572229780274224400469722585868147852608187509420010185039618775981404400401792885121498931245511345550975906095728230775307758109150488484338848321930294974674504775451613333664851564381516108124030753196722125755223318280818682830523620259537479611172718588812979116127220273108594966911232629219195957347063537672749158765130948724281974252007489981278474243333628204092770981850816536671234821284093955702677837464584916991535090769911997642606614464990834915992346639919961494157328623213393722370119570740146804362651976343633725091450303521253550650219753876236656017  

with open('key') as f:
    key = RSA.import_key(f.read())

n = key.n
e = key.e


def get_next_prime(prime: int) -> int:
    test = prime + 2
    while not isPrime(test):
        test += 2
    return test


while True:
    p, _ = iroot(n, 2)

    while not isPrime(p):
        p -= 2

    q = get_next_prime(p)
    n = p * q
    phi_n = (p - 1) * (q - 1)
    d = pow(e, -1, phi_n)
    p = pow(c, d, n)

    if b'SEE{'.hex() in hex(p):
        print(bytes.fromhex(hex(p)[2:]).decode())
        break

$ python3 solve.py
SEE{i_love_really_secure_algorithms_b5c0b187fe309af0f4d35982fd961d7e}

El script completo se puede encontrar aquí: solve.py.