Cryptosystem Walkthrough
Challenge Statement#
Solution#
The given code contains the public key components n and e and the RSA-encrypted ciphertext c.
There is a function primo which finds the next occurring prime number. Thus, p and q are close primes, so we can use Fermat’s Factorization here.
We can write a code to compute and derive the RSA private key d.
Here’s a Python code to decrypt the ciphertext using the private key.
from Crypto.Util.number import inverse, long_to_bytes
import math
n = int("15956250162063169819282947443743274370048643274416742655348817823973383829364700573954709256391245826513107784713930378963551647706777479778285473302665664446406061485616884195924631582130633137574953293367927991283669562895956699807156958071540818023122362163066253240925121801013767660074748021238790391454429710804497432783852601549399523002968004989537717283440868312648042676103745061431799927120153523260328285953425136675794192604406865878795209326998767174918642599709728617452705492122243853548109914399185369813289827342294084203933615645390728890698153490318636544474714700796569746488209438597446475170891")
c = int("3591116664311986976882299385598135447435246460706500887241769555088416359682787844532414943573794993699976035504884662834956846849863199643104254423886040489307177240200877443325036469020737734735252009890203860703565467027494906178455257487560902599823364571072627673274663460167258994444999732164163413069705603918912918029341906731249618390560631294516460072060282096338188363218018310558256333502075481132593474784272529318141983016684762611853350058135420177436511646593703541994904632405891675848987355444490338162636360806437862679321612136147437578799696630631933277767263530526354532898655937702383789647510")
e = 0x10001 # 65537
def fermat_factor(n):
a = math.isqrt(n)
if a * a < n:
a += 1
while True:
b2 = a * a - n
b = math.isqrt(b2)
if b * b == b2:
return a - b, a + b
a += 1
# Factorize n into p and q
p, q = fermat_factor(n)
# Compute Euler's totient function
phi = (p - 1) * (q - 1)
# Compute RSA private exponent d, the secret key
d = inverse(e, phi)
# Decrypt the ciphertext using the private key d
m = pow(c, d, n)
flag_bytes = long_to_bytes(m)
flag = flag_bytes.decode()
# The flag is expected to be in the format THM{...}
print("Flag:",flag)
Adapted from harishkannan05/THM-HackfinityBattle-Writeup under MIT.