Spooky RSA - HackTheBox

Spooky RSA - HackTheBox

Flag : HTB{cu570m_83475_73x7800k_3v32y_71m3}

• Difficulty: Easy

We got the Python source code used to encrypt the flag:

from Crypto.Util.number import bytes_to_long, getStrongPrime
from random import randint

FLAG = b'HTB{????????????????????????????????????????????}'


def key_gen(bits):
    p, q = getStrongPrime(bits), getStrongPrime(bits)
    N = p * q
    return N, (p, q)


def encrypt(m, N, f):
    e1, e2 = randint(2, N - 2), randint(2, N - 2)
    c1 = (pow(f, e1, N) + m) % N
    c2 = (pow(f, e2, N) + m) % N
    return (e1, c1), (e2, c2)


def main():
    N, priv = key_gen(1024)

    m = bytes_to_long(FLAG)

    (e1, c1), (e2, c2) = encrypt(m, N, priv[0])

    with open('out.txt', 'w') as f:
        f.write(f'N = {N}\n(e1, c1) = ({e1}, {c1})\n(e2, c2) = ({e2}, {c2})\n')  


if __name__ == "__main__":
    main()

and we also have the output of the encryption:

N = 23252667157599516940129524769090828719982590926217686828297820221246528288024986185770032891432071416316776607472816043745785945382619303771286924656092974519197669053189283351571920071432553222222811904112119520974410020093306071010335958643236508606549664330684556056421228904824554943559829654154540793885983689462338911148618911233437943092856313175212883771802928968521215461427230178865304889974060408714941809216551397552099050566216607216463931428967751885004128977314044993037370392135272264982092147566078177173327860726953745529225163314733863792635537495622731398807790511518482833382759873192115192207209
(e1, c1) = (13130317383799359924397818711045172877651070470639872331555061566871077024416132122821689879197166729443692993224787531055068053553245916779683406195947939469930710138275745308571705318328750438377477058341710049450433868075025011970534711610887418427142999431981800104300319735079412330836192720430158369804693687507459455621592955618266507196962663247417904680299143606004651444970274693793668715761929296821908860947834841947073379537992600397854852337772316114987249254395674689638512533430273885970458183044843553777077752747556298072797820716079692849044148071698585069757021266842594074685187380985522959676924, 3276033314700994933236715546269096681595964054694634317877930652961630783669009686295177734678226788913957176667505963284895192875563765999040362544244408645923937742131293085082421535485813399270056524297324864682622089578866968706269063489779845211872503005591066652086230371845356855417702566514946373846876609725394545339840695130518357770158558391396835218039249572390662833461220605497534710914935522013573314984887838699014465554643808438475560847600079478934259045848291858470555503523718530137358192672530066755416937024529536303824075068992110042077005432280129307864841939511235555989308133055235385105960)
(e2, c2) = (20883594128285008437725229014478679601366127938823960100219581029154081635436411892478004501333834114219976189312792835720670788637746570550119467812230092062199251164946197959206350494458367692847308442685450722126282132876286895613925612558140177853699821618151096670620765409968557233259334756429446973833981043722454375455334033442236036896820634662734963958738789068654435207820624411915045062084652483285735900502029367176441696762291709434815865847363600312665970290960775666366786471564595838531305478536744797611070398211876965476639913075928103807981832916853895307250848232566714169131101439494532639396872, 18023359039022070922496207692467909272905633400500071646677663883848372907925575359795644502829612958089930556811098737564701111791300315722656180784065385762079524349557515732188405944474314448560602595952205309214787356604461723684793632495397765839132359663293143446639091410994479947265462557919856471699351934094395015205994443217852376256039110600437586852484006845325143039405449700872936218023776566918818003785468900212143526790175840288515458337112681822830546618062507825380629100313042086810588864941567987823223444256356108148388871548275890051441470007397336976314029406010035567308845594636823378393001)

Source code analysis

The script generates a pair of primes $p$ and $q$ and calculates the modulus $N = p \times q$. The flag is encrypted using two random exponents $e_1$ and $e_2$ and the public key $f = p$. The ciphertexts $c_1$ and $c_2$ are calculated as follows: \(c_1 = (f^{e_1} + m) \mod{N}\) \(c_2 = (f^{e_2} + m) \mod{N}\)

Solution

First, we saw that the public key $f$ is equal to $p$. We can calculate the $c_1 - c_2 = p^{e_1} - p^{e_2} = p \cdot (p^{e_1 - 1}- p^{e_2 - 1}) \mod{N}$

We can calculate the greatest common divisor (GCD) of $N$ and $c_1 - c_2$ to find the common factor $p$:

Once we have $p$, we can calculate $m = c_1 - p^{e_1} \mod{N}$

Solve script

N = 23252667157599516940129524769090828719982590926217686828297820221246528288024986185770032891432071416316776607472816043745785945382619303771286924656092974519197669053189283351571920071432553222222811904112119520974410020093306071010335958643236508606549664330684556056421228904824554943559829654154540793885983689462338911148618911233437943092856313175212883771802928968521215461427230178865304889974060408714941809216551397552099050566216607216463931428967751885004128977314044993037370392135272264982092147566078177173327860726953745529225163314733863792635537495622731398807790511518482833382759873192115192207209
(e1, c1) = (13130317383799359924397818711045172877651070470639872331555061566871077024416132122821689879197166729443692993224787531055068053553245916779683406195947939469930710138275745308571705318328750438377477058341710049450433868075025011970534711610887418427142999431981800104300319735079412330836192720430158369804693687507459455621592955618266507196962663247417904680299143606004651444970274693793668715761929296821908860947834841947073379537992600397854852337772316114987249254395674689638512533430273885970458183044843553777077752747556298072797820716079692849044148071698585069757021266842594074685187380985522959676924, 3276033314700994933236715546269096681595964054694634317877930652961630783669009686295177734678226788913957176667505963284895192875563765999040362544244408645923937742131293085082421535485813399270056524297324864682622089578866968706269063489779845211872503005591066652086230371845356855417702566514946373846876609725394545339840695130518357770158558391396835218039249572390662833461220605497534710914935522013573314984887838699014465554643808438475560847600079478934259045848291858470555503523718530137358192672530066755416937024529536303824075068992110042077005432280129307864841939511235555989308133055235385105960)
(e2, c2) = (20883594128285008437725229014478679601366127938823960100219581029154081635436411892478004501333834114219976189312792835720670788637746570550119467812230092062199251164946197959206350494458367692847308442685450722126282132876286895613925612558140177853699821618151096670620765409968557233259334756429446973833981043722454375455334033442236036896820634662734963958738789068654435207820624411915045062084652483285735900502029367176441696762291709434815865847363600312665970290960775666366786471564595838531305478536744797611070398211876965476639913075928103807981832916853895307250848232566714169131101439494532639396872, 18023359039022070922496207692467909272905633400500071646677663883848372907925575359795644502829612958089930556811098737564701111791300315722656180784065385762079524349557515732188405944474314448560602595952205309214787356604461723684793632495397765839132359663293143446639091410994479947265462557919856471699351934094395015205994443217852376256039110600437586852484006845325143039405449700872936218023776566918818003785468900212143526790175840288515458337112681822830546618062507825380629100313042086810588864941567987823223444256356108148388871548275890051441470007397336976314029406010035567308845594636823378393001)
from math import gcd
p = gcd(N, c1 - c2)
m = (c1 - pow(p, e1, N)) % N
flag = bytes.fromhex(hex(m)[2:]).decode()
print(flag)