Challenges: Cryptosystem (TryHackMe)

In this challenge, we intercepted an encrypted communication between Cipher and three associates—Rivest, Shamir, and Adleman. The intercepted file contained an RSA-encrypted message that we were tasked to decrypt in order to reveal a secret key. The encryption used a non-standard approach where one prime factor was chosen as the next prime after the other, which left the modulus vulnerable to factorization. By analyzing the given parameters and leveraging weaknesses in prime selection, we aimed to break the RSA encryption and retrieve the hidden flag.

Cryptosystem

We intercepted a communication between Cipher and some 3 associates: Rivest, Shamir and Adleman. We were only able to retrieve a file.

ORDER: Get the secret key from the recovered file.

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

Answer the questions below

What is the flag?

I improved the initial script and used this script to find the flag

from Cryptodome.Util.number import long_to_bytes
from sympy import nextprime, gcd

# Given values from challenge
c = 3591116664311986976882299385598135447435246460706500887241769555088416359682787844532414943573794993699976035504884662834956846849863199643104254423886040489307177240200877443325036469020737734735252009890203860703565467027494906178455257487560902599823364571072627673274663460167258994444999732164163413069705603918912918029341906731249618390560631294516460072060282096338188363218018310558256333502075481132593474784272529318141983016684762611853350058135420177436511646593703541994904632405891675848987355444490338162636360806437862679321612136147437578799696630631933277767263530526354532898655937702383789647510
n = 15956250162063169819282947443743274370048643274416742655348817823973383829364700573954709256391245826513107784713930378963551647706777479778285473302665664446406061485616884195924631582130633137574953293367927991283669562895956699807156958071540818023122362163066253240925121801013767660074748021238790391454429710804497432783852601549399523002968004989537717283440868312648042676103745061431799927120153523260328285953425136675794192604406865878795209326998767174918642599709728617452705492122243853548109914399185369813289827342294084203933615645390728890698153490318636544474714700796569746488209438597446475170891
e = 0x10001

# Step 1: factor n
# n = p * q, q is next prime after p
# We can iterate primes until we find p
import gmpy2

p = gmpy2.iroot(n, 2)[0]   # approx sqrt(n)
while n % p != 0:
    p = gmpy2.next_prime(p)

q = n // p

# Step 2: compute φ(n)
phi = (p-1)*(q-1)

# Step 3: compute private key
d = gmpy2.invert(e, phi)

# Step 4: decrypt
m = pow(c, d, n)
flag = long_to_bytes(m)
print(flag)

libraries I had to install for it to run successfully

pip3 install sympy

pip3 show pycryptodome

then went ahead to run the python script

python3 script.py

Through factoring the RSA modulus nnn and computing the private key ddd, we successfully decrypted the ciphertext using Python and cryptographic libraries. The decryption process revealed the secret flag, confirming that the use of consecutive primes in RSA significantly weakens its security. This challenge demonstrated how mathematical weaknesses in cryptosystem design can be exploited to recover sensitive information, emphasizing the importance of secure key generation in cryptography.