Rather Secure Attachment

3 minutes to read

We are given the Python source code used to encrypt the 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}")

And the output of the above script:

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

RSA background

Let’s review how RSA works: $n = p q$, where $p$ and $q$ are some large prime numbers. The exponent $e$ is used to encrypt a message $m$ as follows:

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

The decryption process needs $\phi(n) = (p - 1) (q - 1)$ and $d = e^{-1} \mod{\phi(n)}$. Then to decrypt the ciphertext $c$ we can compute:

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

Analyzing the output values

So, $c$ is the encrypted flag and $n$ is the public modulus (we also know that $e = 65537$).

Then we have $f$ and $l$. We can see that $l$ is a large prime number and $f = p^d \mod{l}$, where $p$ is a private prime number for the RSA cryptosystem and $d = 2^k \mod{n}$, where $k$ is a 4-bit prime number.

The only possible values of $k$ are $11$ and $13$:

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

Therefore, $d \in \{2^{11}, 2^{13}\} = \{2048, 8192\}$, and $f \in \{p^{2048}, p^{8192}\} \mod{l}$.

Cipolla’s Algorithm

There are some algorihms to find $x$ from $y$ such that $x^2 \equiv y \pmod{p}$. For instance, Tonelli-Shanks or Cipolla. This time, we will be using the Cipolla’s Algorithm 11 times and 13 times. On those steps, we could have $p$, so we could decrypt RSA trivially:

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

And we obtain the flag:

$ python3 solve.py
ictf{brOken_bY_aLb3rTo_t0NelLi_aNd_dAni3L_sHankS_s1nCe_tHe_18and1900s}

The full script can be found in here: solve.py.