THM – Cryptosystem

Link to Lab: https://tryhackme.com/room/hfb1cryptosystem

Given a problem with the following code.

Where c is the ciphertext and n = p * q.

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

There are multiple unknown variables. Such as p, q, d. Where d is the private exponent. In order to decrypt the ciphertext the private exponent is necessary.

The cipher text was calculated with c = plaintext^e mod n

The plaintext can be recovered with ptxt = ciphertext^d mod n

To calculate d, the factor of n should be found.

By using the sympy.factorint() function:

n = 159562...70891

factors = factorint(n)
p, q = factors.keys()

Calculating d by using the result of: p, q:

d = inverse(e, (p-1) * (q-1))

By using the formula to decrypt the ciphertext in python:

ptxt = pow(c,d,n)
print(long_to_bytes(ptxt).decode())

The following flag was given

THM{Just_*****_RSA!}

Full Code Solution:

from Crypto.Util.number import *
from sympy import factorint

e = 0x10001
c = 3591116664311986976882299385598135447435246460706500887241769555088416359682787844532414943573794993699976035504884662834956846849863199643104254423886040489307177240200877443325036469020737734735252009890203860703565467027494906178455257487560902599823364571072627673274663460167258994444999732164163413069705603918912918029341906731249618390560631294516460072060282096338188363218018310558256333502075481132593474784272529318141983016684762611853350058135420177436511646593703541994904632405891675848987355444490338162636360806437862679321612136147437578799696630631933277767263530526354532898655937702383789647510
n = 15956250162063169819282947443743274370048643274416742655348817823973383829364700573954709256391245826513107784713930378963551647706777479778285473302665664446406061485616884195924631582130633137574953293367927991283669562895956699807156958071540818023122362163066253240925121801013767660074748021238790391454429710804497432783852601549399523002968004989537717283440868312648042676103745061431799927120153523260328285953425136675794192604406865878795209326998767174918642599709728617452705492122243853548109914399185369813289827342294084203933615645390728890698153490318636544474714700796569746488209438597446475170891

#factor n
factors = factorint(n)
p, q = factors.keys()
#reverse d using inverse phi
d = inverse(e, (p-1) * (q-1))
ptxt = pow(c,d,n)
print(long_to_bytes(ptxt).decode())