TwoForOne

3 minutos de lectura

Se nos proporcionan dos claves públicas en formato PEM:

Y tenemos también dos textos cifrados que están asociados a las claves públicas anteriores. Es importante mencionar que el mensaje es el mismo:

RBVdQw7Pllwb42GDYyRa6ByVOfzRrZHmxBkUPD393zxOcrNRZgfub1mqcrAgX4PAsvAOWptJSHbrHctFm6rJLzhBi/rAsKGboWqPAWYIu49Rt7Sc/5+LE2dvy5zriAKclchv9d+uUJ4/kU/vcpg2qlfTnyor6naBsZQvRze0VCMkPvqWPuE6iL6YEAjZmLWmb+bqO+unTLF4YtM1MkKTtiOEy+Bbd4LxlXIO1KSFVOoGjyLW2pVIgKzotB1/9BwJMKJV14/+MUEiP40ehH0U2zr8BeueeXp6NIZwS/9svmvmVi06Np74EbL+aeB4meaXH22fJU0eyL2FppeyvbVaYQ==

TSHSOfFBkK/sSE4vWxy00EAnZXrIsBI/Y6mGv466baOsST+qyYXHdPsI33Kr6ovucDjgDw/VvQtsAuGhthLbLVdldt9OWDhK5lbM6e0CuhKSoJntnvCz7GtZvjgPM7JDHQkAU7Pcyall9UEqL+W6ZCkiSQnK+j6QB7ynwCsW1wAmnCM68fY2HaBvd8RP2+rPgWv9grcEBkXf7ewA+sxSw7hahMaW0LYhsMYUggrcKqhofGgl+4UR5pdSiFg4YKUSgdSw1Ic/tug9vfHuLSiiuhrtP38yVzazqOZPXGxG4tQ6btc1helH0cLfw1SCdua1ejyan9l1GLXsAyGOKSFdKw==

Las claves públicas parecen muy similares. Vamos a importarlas con Python y ver los valores de y de :

$ python3 -q
>>> from Crypto.PublicKey import RSA
>>> key1 = RSA.import_key(open('key1.pem').read())
>>> key2 = RSA.import_key(open('key2.pem').read())
>>> key1.n == key2.n
True
>>> key1.e == key2.e
False
>>> key1.e
65537
>>> key2.e
343223

Vemos que los módulos son iguales y que las claves se diferencian en el exponente .

Contexto de RSA

Vamos a recordar cómo funciona RSA: , donde y son números primos grandes. El exponente se utiliza para cifrar un mensaje como se muestra:

El proceso de descifrado necesita y . Luego para descifrar el texto cifrado podemos calcular:

Ataque de módulo común

Aquí tenemos dos textos cifrados que utilizan el mismo módulo pero distintos exponentes ( y ), pero el mensaje es el mismo para ambos. Por tanto:

Por la identidad de Bezout, dados dos enteros no nulos, existen enteros tales que

Como , podemos encontrar valores tales que

La idea es hallar estos valores para calcular el mensaje de esta manera:

Los valores se calculan usando el GCD extendido (Algoritmo de Euclides Extendido).

Este es un script en Python para resolver el reto:

#!/usr/bin/env python3

from base64 import b64decode
from Crypto.PublicKey import RSA


def extended_gcd(a, b):
    if a % b:
        u, v, d = extended_gcd(b, a % b)
        return v, (d - a * v) // b, d

    return 0, 1, b


def main():
    c1 = int(b64decode(open('message1').read()).hex(), 16)
    c2 = int(b64decode(open('message2').read()).hex(), 16)

    key1 = RSA.importKey(open('key1.pem').read())
    key2 = RSA.importKey(open('key2.pem').read())

    n = key1.n
    e1, e2 = key1.e, key2.e

    u, v, _ = extended_gcd(e1, e2)

    m = pow(c1, u, n) * pow(c2, v, n) % n

    print(bytes.fromhex(format(m, '0x')).decode())


if __name__ == '__main__':
    main()

Flag

$ python3 solve.py
HTB{C0mmon_M0dUlu5S_1S_b4D}

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