<- IMAGINARYCTF

Rather Secure Attachment

3 minutos de lectura

Se nos proporciona el código fuente en Python utilizado para cifrar la flag:

from Crypto.Util.number import getPrime, bytes_to_long  

with open('flag.txt','rb') as f:
    m = bytes_to_long(f.read())

e = 0x10001
k = getPrime(4)
l = getPrime(512)
p = getPrime(512)
q = getPrime(512)
n = p*q
c = pow(m, e, n)
d = pow(2, k, n)
f = pow(p, d, l)

print(f"c = {c}")
print(f"n = {n}")
print(f"f = {f}")
print(f"l = {l}")

Y la salida del script anterior:

c = 15569903606447382190452764402941339626308156309636986531698075641473107888825711160984364441586276963257479852352024439669272637068620013057407377137911637080205270783751875254649182246877011645122001841598989475397059021324194631682020792613902300372771482794281500616138614387516591907166918187664621666490  
n = 81283896599045813695615008896209080391755326673500780817417128377398664124888617077128749041782926115197934608675318169630210349202663592403103605147532439239684659375112943455710243781419720100154056981849800941526147131241755497543856521554758965632640670209200105067782461743490004986695348945897409335607
f = 2010730668992923175885112531238039994491180143490780125531231868948774097426456118161798553618093102828248541236857807034323904737818411561255591866642850
l = 11080271608353917802026380896429927782165433472385279241830041700541865655511778460984708585966037382475401275633561847042649902895681873118114821383377947

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} $$

Analizando los valores de salida

Tenemos que $c$ es la flag cifrada y $n$ es el módulo público (también sabemos que $e = 65537$).

Luego tenemos $f$ y $l$. Vemos que $l$ es un número primo grande y $f = p^d \mod{l}$, donde $p$ es un número primo privado del criptosistema RSA y $d = 2^k \mod{n}$, donde $k$ es un número primo de 4 bits.

Los únicos valores posibles para $k$ son $11$ y $13$:

$ python3 -q
>>> from Crypto.Util.number import getPrime  
>>> { getPrime(4) for _ in range(1000) }
{11, 13}

Por tanto, $d \in \{2^{11}, 2^{13}\} = \{2048, 8192\}$, y $f \in \{p^{2048}, p^{8192}\} \mod{l}$.

Algoritmo de Cipolla

Existen algoritmos para hallar $x$ a partir de $y$ tal que $x^2 \equiv y \pmod{p}$. Por ejemplo, Tonelli-Shanks o Cipolla. Esta vez, estaremos usando el Algoritmo de Cipolla 11 veces y 13 veces. En ambos pasos, podríamos tener $p$, de manera que podemos descifrar RSA de manera trivial:

def try_solve_rsa(p, e, n, c):
    q = n // p
    phi_n = (p - 1) * (q - 1)
    d = pow(e, -1, phi_n)
    m = bytes.fromhex(hex(pow(c, d, n))[2:])

    if b'ictf{' in m:
        print(m.decode())


def main():
    c = 15569903606447382190452764402941339626308156309636986531698075641473107888825711160984364441586276963257479852352024439669272637068620013057407377137911637080205270783751875254649182246877011645122001841598989475397059021324194631682020792613902300372771482794281500616138614387516591907166918187664621666490  
    n = 81283896599045813695615008896209080391755326673500780817417128377398664124888617077128749041782926115197934608675318169630210349202663592403103605147532439239684659375112943455710243781419720100154056981849800941526147131241755497543856521554758965632640670209200105067782461743490004986695348945897409335607
    f = 2010730668992923175885112531238039994491180143490780125531231868948774097426456118161798553618093102828248541236857807034323904737818411561255591866642850
    l = 11080271608353917802026380896429927782165433472385279241830041700541865655511778460984708585966037382475401275633561847042649902895681873118114821383377947
    e = 65537

    p_8192 = f

    for p_4096 in cipolla(p_8192, l):
        for p_2048 in cipolla(p_4096, l):
            for p_1024 in cipolla(p_2048, l):
                for p_512 in cipolla(p_1024, l):
                    for p_256 in cipolla(p_512, l):
                        for p_128 in cipolla(p_256, l):
                            for p_64 in cipolla(p_128, l):
                                for p_32 in cipolla(p_64, l):
                                    for p_16 in cipolla(p_32, l):
                                        for p_8 in cipolla(p_16, l):
                                            for p_4 in cipolla(p_8, l):
                                                try_solve_rsa(p_4, e, n, c)
                                                try_solve_rsa(p_4 + l, e, n, c)
                                                for p_2 in cipolla(p_4, l):
                                                    for p_1 in cipolla(p_2, l):
                                                        try_solve_rsa(p_1, e, n, c)
                                                        try_solve_rsa(p_1 + l, e, n, c)

Flag

Y así conseguimos la flag:

$ python3 solve.py
ictf{brOken_bY_aLb3rTo_t0NelLi_aNd_dAni3L_sHankS_s1nCe_tHe_18and1900s}

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