Cryptosystem

Overview

Cryptosystem is an easy level TryHackMe Room on RSA.

Vulnerability Analysis

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 vulnerability lies in how $q$ is generated since primo(p) finds the next prime $p$ the difference between $p$ and $q$ will be very small This creates a scenario where.

• $p ≈ q$ (approximately equal)
• $n = p \times q$
• This makes Fermats factorisation method highlt effective.

When two prime factors are close together we can write.

• $p = a - b$
• $q = a + b$
• n = $(a-b)(a+b) = a^2 -b^2$

Where $a$ is slightly larger than $\sqrt{n}$ and $b$ is small.

We have now found $p$ and $q$ and can now calculate Eulers Totient

\[\phi(n) = (p-1) \times (q-1)\]

From here, we compute the private key $d$ as the modular inverse of $e$ modulo n.

\[d=e^{-1} \mod \phi(n)\]

.
And finally we can compute the plaintext $s$ by raising $c$ to the power $d$ modulo $n$.

\[s=c^d \mod n\]

Below is the following expressed in python.

import math
from Crypto.Util.number import bytes_to_long, long_to_bytes

def fermat_factor(n):
    a = math.isqrt(n)
    if a * a < n:
        a += 1  # round up to the ceiling of sqrt(n)

    b2 = a * a - n
    while not is_perfect_square(b2):
        a += 1
        b2 = a * a - n

    b = math.isqrt(b2)
    p = a - b
    q = a + b
    return p, q

def is_perfect_square(k):
    s = math.isqrt(k)
    return s * s == k

n = 15956250162063169819282947443743274370048643274416742655348817823973383829364700573954709256391245826513107784713930378963551647706777479778285473302665664446406061485616884195924631582130633137574953293367927991283669562895956699807156958071540818023122362163066253240925121801013767660074748021238790391454429710804497432783852601549399523002968004989537717283440868312648042676103745061431799927120153523260328285953425136675794192604406865878795209326998767174918642599709728617452705492122243853548109914399185369813289827342294084203933615645390728890698153490318636544474714700796569746488209438597446475170891

c = 3591116664311986976882299385598135447435246460706500887241769555088416359682787844532414943573794993699976035504884662834956846849863199643104254423886040489307177240200877443325036469020737734735252009890203860703565467027494906178455257487560902599823364571072627673274663460167258994444999732164163413069705603918912918029341906731249618390560631294516460072060282096338188363218018310558256333502075481132593474784272529318141983016684762611853350058135420177436511646593703541994904632405891675848987355444490338162636360806437862679321612136147437578799696630631933277767263530526354532898655937702383789647510

e = 0x10001
p,q  = fermat_factor(n)
phi_N = (p-1) * (q - 1)
d = pow(e,-1,phi_N)
s = pow(c,d,n)  
print(long_to_bytes(s).decode())

This prints the flag and we are now done