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 = 25458200992030509733740123651871827168179694737564741891817013763410533831135578900317404987414083347009443171337016804117994550747038777609425522146275786823385218489896468142658492353321920860029284041857237273061376882168336089921980034356731735024837853873907395117925738744950932927683784527829300499629044776530663084875991411120648155572219472426590747952180037566734905079883718263249789131313731453855593891997376222635496337534679814697188141565730768050813250191975439504290665602928172394124501396491438097237093345376202142503439944034846839870643057174427346860377971316738504003909365471892007511334129
(e1, c1) = (22255763231110249841946619835451544743470788953822278626567823902873888725104180401047359514978597528256727783972109939326623409435352523707077685530090905587264556011558283062584063790610407522064244766804545192800000203519996147931257064951519705687708204481851413899370853107413015511963924826116255617048471033727588623329910848658324118717242497443676679226618430348230146770121025920211016222285978389380202889753020268614144716241830764562717015776308425373054119742788593926393822433887270639369774139542440755201713961244129409678232953199572105700556795757766046717275157050721726002297647024020428198870290, 19074438470072195427966520314234457847008607427606084653244579403273587717215359437848959151287968653813774451872243596539852961112790372328452176435310940366312355444995843216994547119328105950997441430508803799696108202263077660206667410037895728991246260073976495701990246589717169815787627260333746927676703415397948299928151669728670970891826725671026488571268125861689964688240713660432174319415041362820791863237794347031803574182264640071528640168842529541888996148513070006266317160300336104047046565614107490019016833308549850299600989228190163831642944507973854553499903518264459385900876967183424703346566)  
(e2, c2) = (23295046285127774160603234291301851851887586336491694096135804083341667982196486623010787985772884401302006627480506928365762168889259124596656609547973623161028214128429382170008181185180817200188852310143707964673736007253037970626819969310508212349854949150027746456459910448148518206090222496335254237639366458956363901115228820515207791697374943745570543635069929211464017776268424656451494147324386568859163866168248303418756480467046005765139197217754018136577337642795325944222997798231137981998354508181409469926672642302422740898720854693114056342834487668008885129303781190655860432910789997267090661459286, 17147905252678781157626731164660022679389951402035723790864177724472811805536492684462105274963820085525923148442586230016346022360533813239980197823588694113614328942373594914090007235565086360669401527248700861049825216638433673668883632064731716051799766945737234155585371938261291032941617911654796216200373195747432329591657679097825944679339369336644061159658436125778459206858632826310294115276289447751653250081978372776233383658861171699105292372718533428579168281346425439711770636421673291051002416067073005799659684303566722822458673952580001750804105442227754799536262315625088085767607467446614116889593)

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 = 25458200992030509733740123651871827168179694737564741891817013763410533831135578900317404987414083347009443171337016804117994550747038777609425522146275786823385218489896468142658492353321920860029284041857237273061376882168336089921980034356731735024837853873907395117925738744950932927683784527829300499629044776530663084875991411120648155572219472426590747952180037566734905079883718263249789131313731453855593891997376222635496337534679814697188141565730768050813250191975439504290665602928172394124501396491438097237093345376202142503439944034846839870643057174427346860377971316738504003909365471892007511334129
>>> (e1, c1) = (22255763231110249841946619835451544743470788953822278626567823902873888725104180401047359514978597528256727783972109939326623409435352523707077685530090905587264556011558283062584063790610407522064244766804545192800000203519996147931257064951519705687708204481851413899370853107413015511963924826116255617048471033727588623329910848658324118717242497443676679226618430348230146770121025920211016222285978389380202889753020268614144716241830764562717015776308425373054119742788593926393822433887270639369774139542440755201713961244129409678232953199572105700556795757766046717275157050721726002297647024020428198870290, 19074438470072195427966520314234457847008607427606084653244579403273587717215359437848959151287968653813774451872243596539852961112790372328452176435310940366312355444995843216994547119328105950997441430508803799696108202263077660206667410037895728991246260073976495701990246589717169815787627260333746927676703415397948299928151669728670970891826725671026488571268125861689964688240713660432174319415041362820791863237794347031803574182264640071528640168842529541888996148513070006266317160300336104047046565614107490019016833308549850299600989228190163831642944507973854553499903518264459385900876967183424703346566)  
>>> (e2, c2) = (23295046285127774160603234291301851851887586336491694096135804083341667982196486623010787985772884401302006627480506928365762168889259124596656609547973623161028214128429382170008181185180817200188852310143707964673736007253037970626819969310508212349854949150027746456459910448148518206090222496335254237639366458956363901115228820515207791697374943745570543635069929211464017776268424656451494147324386568859163866168248303418756480467046005765139197217754018136577337642795325944222997798231137981998354508181409469926672642302422740898720854693114056342834487668008885129303781190655860432910789997267090661459286, 17147905252678781157626731164660022679389951402035723790864177724472811805536492684462105274963820085525923148442586230016346022360533813239980197823588694113614328942373594914090007235565086360669401527248700861049825216638433673668883632064731716051799766945737234155585371938261291032941617911654796216200373195747432329591657679097825944679339369336644061159658436125778459206858632826310294115276289447751653250081978372776233383658861171699105292372718533428579168281346425439711770636421673291051002416067073005799659684303566722822458673952580001750804105442227754799536262315625088085767607467446614116889593)
>>> from math import gcd
>>> p = gcd(c1 - c2, N)
>>> m = c1 - pow(p, e1, N) % N
>>> bytes.fromhex(hex(m)[2:])
b'HTB{5h45_w4$_sUpp0s3d_50_b3_m0r3_s3cUr3_th4n_R$4}'