Spooky RSA

3 minutes to read

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()

We also have the output of the script:

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

RSA background

RSA works as follows: We take two large primes $p$ and $q$ and set the modulus $N = p \cdot q$. Then we choose an exponent $e$ (typically $e = 65537$) and encrypt a message $m$ in decimal format:

$$ c = m^e \mod{N} $$

The public key is the tuple $(n, e)$, and the private key is composed of the two prime numbers. To decrypt, we need to compute $\phi(N) = (p - 1) (q - 1)$ in order to find the multiplicative inverse of $e$, which is $d = e^{-1} \mod{\phi(N)}$. Then the decryption of $c$ is:

$$ m = c^d \mod{N} $$

This works because

$$ c = m^e \mod{N} \iff c^d = (m^e)^d = m^{ed} = m \mod{N} $$

Finding RSA implementation flaws

This time we have an custom RSA implementation:

$$ c_1 = p^{e_1} + m \mod{N} $$

$$ c_2 = p^{e_2} + m \mod{N} $$

We already know $N$, $e_1$, $e_2$, $c_1$ and $c_2$. Moreover, $N = p \cdot q$, where $p$ and $q$ are big prime numbers.

Notice that

$$ c_1 - c_2 = p^{e_1} - p_{e_2} = p \cdot (p^{e_1 - 1} p^{e_2 - 1}) \mod{N} $$

Hence, $c_1 - c_2$ and $N$ share a common factor $p$. Therefore can find $p$ using the Greatest Common Divisor (GCD).

Once we have $p$, it is trivial to find the flag:

$$ m = c_1 - p^{e_1} \mod{N} $$

Flag

All of the above computations can be done in Python. At the end, we only need to parse $m$ as bytes:

$ python3 -q
>>> N = 23252667157599516940129524769090828719982590926217686828297820221246528288024986185770032891432071416316776607472816043745785945382619303771286924656092974519197669053189283351571920071432553222222811904112119520974410020093306071010335958643236508606549664330684556056421228904824554943559829654154540793885983689462338911148618911233437943092856313175212883771802928968521215461427230178865304889974060408714941809216551397552099050566216607216463931428967751885004128977314044993037370392135272264982092147566078177173327860726953745529225163314733863792635537495622731398807790511518482833382759873192115192207209
>>> (e1, c1) = (13130317383799359924397818711045172877651070470639872331555061566871077024416132122821689879197166729443692993224787531055068053553245916779683406195947939469930710138275745308571705318328750438377477058341710049450433868075025011970534711610887418427142999431981800104300319735079412330836192720430158369804693687507459455621592955618266507196962663247417904680299143606004651444970274693793668715761929296821908860947834841947073379537992600397854852337772316114987249254395674689638512533430273885970458183044843553777077752747556298072797820716079692849044148071698585069757021266842594074685187380985522959676924, 3276033314700994933236715546269096681595964054694634317877930652961630783669009686295177734678226788913957176667505963284895192875563765999040362544244408645923937742131293085082421535485813399270056524297324864682622089578866968706269063489779845211872503005591066652086230371845356855417702566514946373846876609725394545339840695130518357770158558391396835218039249572390662833461220605497534710914935522013573314984887838699014465554643808438475560847600079478934259045848291858470555503523718530137358192672530066755416937024529536303824075068992110042077005432280129307864841939511235555989308133055235385105960)
>>> (e2, c2) = (20883594128285008437725229014478679601366127938823960100219581029154081635436411892478004501333834114219976189312792835720670788637746570550119467812230092062199251164946197959206350494458367692847308442685450722126282132876286895613925612558140177853699821618151096670620765409968557233259334756429446973833981043722454375455334033442236036896820634662734963958738789068654435207820624411915045062084652483285735900502029367176441696762291709434815865847363600312665970290960775666366786471564595838531305478536744797611070398211876965476639913075928103807981832916853895307250848232566714169131101439494532639396872, 18023359039022070922496207692467909272905633400500071646677663883848372907925575359795644502829612958089930556811098737564701111791300315722656180784065385762079524349557515732188405944474314448560602595952205309214787356604461723684793632495397765839132359663293143446639091410994479947265462557919856471699351934094395015205994443217852376256039110600437586852484006845325143039405449700872936218023776566918818003785468900212143526790175840288515458337112681822830546618062507825380629100313042086810588864941567987823223444256356108148388871548275890051441470007397336976314029406010035567308845594636823378393001)  
>>> from math import gcd
>>> p = gcd(c1 - c2, N)
>>> m = c1 - pow(p, e1, N) % N
>>> bytes.fromhex(hex(m)[2:])
b'HTB{cu570m_83475_73x7800k_3v32y_71m3}'