Spooky RSA

3 minutos de lectura

Se nos proporciona el siguiente código en Python para cifrar la 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()

También tenemos la salida del script:

N = 25458200992030509733740123651871827168179694737564741891817013763410533831135578900317404987414083347009443171337016804117994550747038777609425522146275786823385218489896468142658492353321920860029284041857237273061376882168336089921980034356731735024837853873907395117925738744950932927683784527829300499629044776530663084875991411120648155572219472426590747952180037566734905079883718263249789131313731453855593891997376222635496337534679814697188141565730768050813250191975439504290665602928172394124501396491438097237093345376202142503439944034846839870643057174427346860377971316738504003909365471892007511334129
(e1, c1) = (22255763231110249841946619835451544743470788953822278626567823902873888725104180401047359514978597528256727783972109939326623409435352523707077685530090905587264556011558283062584063790610407522064244766804545192800000203519996147931257064951519705687708204481851413899370853107413015511963924826116255617048471033727588623329910848658324118717242497443676679226618430348230146770121025920211016222285978389380202889753020268614144716241830764562717015776308425373054119742788593926393822433887270639369774139542440755201713961244129409678232953199572105700556795757766046717275157050721726002297647024020428198870290, 19074438470072195427966520314234457847008607427606084653244579403273587717215359437848959151287968653813774451872243596539852961112790372328452176435310940366312355444995843216994547119328105950997441430508803799696108202263077660206667410037895728991246260073976495701990246589717169815787627260333746927676703415397948299928151669728670970891826725671026488571268125861689964688240713660432174319415041362820791863237794347031803574182264640071528640168842529541888996148513070006266317160300336104047046565614107490019016833308549850299600989228190163831642944507973854553499903518264459385900876967183424703346566)  
(e2, c2) = (23295046285127774160603234291301851851887586336491694096135804083341667982196486623010787985772884401302006627480506928365762168889259124596656609547973623161028214128429382170008181185180817200188852310143707964673736007253037970626819969310508212349854949150027746456459910448148518206090222496335254237639366458956363901115228820515207791697374943745570543635069929211464017776268424656451494147324386568859163866168248303418756480467046005765139197217754018136577337642795325944222997798231137981998354508181409469926672642302422740898720854693114056342834487668008885129303781190655860432910789997267090661459286, 17147905252678781157626731164660022679389951402035723790864177724472811805536492684462105274963820085525923148442586230016346022360533813239980197823588694113614328942373594914090007235565086360669401527248700861049825216638433673668883632064731716051799766945737234155585371938261291032941617911654796216200373195747432329591657679097825944679339369336644061159658436125778459206858632826310294115276289447751653250081978372776233383658861171699105292372718533428579168281346425439711770636421673291051002416067073005799659684303566722822458673952580001750804105442227754799536262315625088085767607467446614116889593)

Explicación de RSA

RSA funciona de la siguiente manera: Se cogen dos números primos grandes $p$ y $q$ y se toma $N = p \cdot q$ como módulo. Luego, se coge un exponente $e$ (típicamente $e = 65537$) y se cifra el mensage $m$ en formato decimal:

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

La clave pública es la tupla $(N, e)$, y la clave privada está compuesta por los dos números primos. Para descifrar, se necesita calcular $\phi(N) = (p - 1) (q - 1)$ para calcular el inverso de $e$ respecto a la multiplicación, que es $d = e^{-1} \mod{\phi(N)}$. Luego, el texto cifrado $c$ se descifra como:

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

Y esto funciona debido a que

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

Encontrando fallos en la implementación RSA

Este vez, tenemos una implementación personalizada de RSA:

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

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

Ya conocemos $N$, $e_1$, $e_2$, $c_1$ y $c_2$. Además, $N = p \cdot q$, donde $p$ y $q$ son números primos grandes.

Nótese que

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

Entonces, $c_1 - c_2$ y $N$ comparten un factor $p$. Por tanto, podemos encontrar $p$ usando el Máximo Común Divisor (GCD).

Una vez que tenemos $p$, es trivial hallar la flag:

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

Flag

Todas las operaciones anteriores se pueden hacer en Python. Al final, solamente tenemos que expresar $m$ en formato 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}'