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 $n$ y de $e$:

$ 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 $e$.

Contexto de RSA

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

$$ c = m^e \mod{n} $$

El proceso de descifrado necesita $\phi(n) = (p - 1) (q - 1)$ y $d = e^{-1} \mod{\phi(n)}$. Luego para descifrar el texto cifrado $c$ podemos calcular:

$$ m = c^d \mod{n} $$

Ataque de módulo común

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

$$ c_1 = m^{e_1} \mod{n} $$

$$ c_2 = m^{e_2} \mod{n} $$

Por la identidad de Bezout, dados dos enteros $a, b$ no nulos, existen enteros $u, v$ tales que

$$ u \cdot a + v \cdot b = \gcd{(a, b)} $$

Como $\gcd{(e_1, e_2)} = 1$, podemos encontrar valores $u, v$ tales que

$$ u \cdot e_1 + v \cdot e_2 = 1 $$

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

$$ c_1^u \cdot c_2^v = (m^{e_1})^u \cdot (m^{e_2})^v = m^{u \cdot e_1} \cdot m^{v \cdot e_2} = m^{u \cdot e_1 + v \cdot e_2} = m \mod{n} $$

Los valores $u, v$ 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.