What Are We Working With

So the story here is that we intercepted a communication between a group of 4 attackers and managed to grab a file from them. The file is a Python script and it looks like this:

from Crypto.Util.number import *
from flag import FLAG

def primo(n):
    n += 2 if n & 1 else 1
    while not isPrime(n):
        n += 2
    return n

p = getPrime(1024)
q = primo(p)
n = p * q
e = 0x10001
d = inverse(e, (p-1) * (q-1))
c = pow(bytes_to_long(FLAG.encode()), e, n)
#c = 3591116664311986976882299385598135447435246460706500887241769555088416359682787844532414943573794993699976035504884662834956846849863199643104254423886040489307177240200877443325036469020737734735252009890203860703565467027494906178455257487560902599823364571072627673274663460167258994444999732164163413069705603918912918029341906731249618390560631294516460072060282096338188363218018310558256333502075481132593474784272529318141983016684762611853350058135420177436511646593703541994904632405891675848987355444490338162636360806437862679321612136147437578799696630631933277767263530526354532898655937702383789647510
#n = 15956250162063169819282947443743274370048643274416742655348817823973383829364700573954709256391245826513107784713930378963551647706777479778285473302665664446406061485616884195924631582130633137574953293367927991283669562895956699807156958071540818023122362163066253240925121801013767660074748021238790391454429710804497432783852601549399523002968004989537717283440868312648042676103745061431799927120153523260328285953425136675794192604406865878795209326998767174918642599709728617452705492122243853548109914399185369813289827342294084203933615645390728890698153490318636544474714700796569746488209438597446475170891

The challenge is to get the secret key out of this thing.

Reading the Script

Before doing anything I just sat and stared at it for a bit. I have done cryptography challenges before and the moment I saw n, e, d, p, and q all in the same place, I recognized it immediately. This is RSA encryption.

Here is what the script is actually doing:

p gets generated as a random 1024 bit prime number. Normal so far.

Then q gets generated by a function called primo. That function takes p and just… finds the very next prime number after it. Not a random prime. Not a distant one. The one right next door.

Then n = p * q. Which is just those two primes multiplied together.

The flag gets encrypted using RSA math and the result is c. That encrypted value is what we need to crack.

So the weakness here is that p and q are extremely close to each other. In proper RSA they are supposed to be two completely unrelated large primes. Here they are basically neighbours. That turns out to be a big problem for whoever set this up.

Finding p and q (2 methods)

Now to actually break this, I need to find p and q from n. Normally that is basically impossible with big numbers. But because these two are so close together, there is a shortcut.

I will be honest, my first instinct was not the mathematical approach. I just copied the n value and dropped it into https://factordb.com/ and it handed me p and q right away.

The website just had it in the database already. This is the easy and fast way of getting p and q.

But I wanted to actually understand what TryHackMe was trying to teach here, so I looked into the proper method too.

The intended approach is something called Fermat’s factorization. The idea is that if two prime factors of a number are close together, you can find them by searching near the square root of n. Here is how it works:

Start with a = ceil(√n)

Compute b² = a² - n

Check if b² is a perfect square

If yes, then p = a + b and q = a - b and you are done

If no, add 1 to a and try again

I will not pretend I fully understand every piece of the math here. I read a few explanations and followed along. The key point that makes this work for this specific challenge is that because p and q are so close, a barely has to move at all before it finds a perfect square. It basically solves on the first or second try. That is why this is such a nasty weakness.

Here is the script for that:

from math import isqrt

n = 15956250162063169819282947443743274370048643274416742655348817823973383829364700573954709256391245826513107784713930378963551647706777479778285473302665664446406061485616884195924631582130633137574953293367927991283669562895956699807156958071540818023122362163066253240925121801013767660074748021238790391454429710804497432783852601549399523002968004989537717283440868312648042676103745061431799927120153523260328285953425136675794192604406865878795209326998767174918642599709728617452705492122243853548109914399185369813289827342294084203933615645390728890698153490318636544474714700796569746488209438597446475170891

a = isqrt(n) + 1
while True:
    b2 = a*a - n
    b = isqrt(b2)
    if b * b == b2:
        p = a + b
        q = a - b
        break
    a += 1

print(p)
print(q)

Run it and you get the same p and q as the website gave me earlier. So both methods check out.

Decrypting the Flag

Now that I have p and q, decrypting the flag is just standard RSA math. I wrote a script that looks almost identical to the original one from the challenge, just with the actual values plugged in and the decryption step added at the end:

from Crypto.Util.number import *
from math import isqrt

n = 15956250162063169819282947443743274370048643274416742655348817823973383829364700573954709256391245826513107784713930378963551647706777479778285473302665664446406061485616884195924631582130633137574953293367927991283669562895956699807156958071540818023122362163066253240925121801013767660074748021238790391454429710804497432783852601549399523002968004989537717283440868312648042676103745061431799927120153523260328285953425136675794192604406865878795209326998767174918642599709728617452705492122243853548109914399185369813289827342294084203933615645390728890698153490318636544474714700796569746488209438597446475170891
e = 0x10001
c = 3591116664311986976882299385598135447435246460706500887241769555088416359682787844532414943573794993699976035504884662834956846849863199643104254423886040489307177240200877443325036469020737734735252009890203860703565467027494906178455257487560902599823364571072627673274663460167258994444999732164163413069705603918912918029341906731249618390560631294516460072060282096338188363218018310558256333502075481132593474784272529318141983016684762611853350058135420177436511646593703541994904632405891675848987355444490338162636360806437862679321612136147437578799696630631933277767263530526354532898655937702383789647510

a = isqrt(n) + 1
while True:
    b2 = a*a - n
    b = isqrt(b2)
    if b * b == b2:
        p = a + b
        q = a - b
        break
    a += 1

d = inverse(e, (p-1) * (q-1))
m = pow(c, d, n)
print(long_to_bytes(m).decode())

Run it and you get the flag printed out clean.

Flag: THM{Just_s0m3_small_amount_of_RSA!}

The takeaway here is pretty simple. RSA is considered secure because factoring a huge number into two primes is normally a nightmare. But the moment someone gets lazy and picks two primes that are close to each other, the whole thing falls apart embarrassingly fast. Fermat’s factorization just demolishes it. Or you know, you could also just Google the number. Either works.