RSAgain
3 minutos de lectura
Se nos proporciona el código fuente utilizado para cifrar la flag:
from Crypto.Util.number import getPrime
from secrets import randbelow
flag = b'ictf{???????????????}'
m = int.from_bytes(flag, 'big')
p, q = getPrime(1024), getPrime(1024)
n = p*q
e1 = 7*randbelow(n)
e2 = 7*randbelow(n)
c1 = pow(m, e1, n)
c2 = pow(m, e2, n)
print('n =', n)
print('e =', [e1, e2])
print('c =', [c1, c2])
Y la salida del script anterior:
n = 13761685901869725143768331354410331722080881206892978316226355274731948923788116922997132633408042821072846131527848521009073675634635614838798409359054501234184243307064644162477264359675732802892743867662331151938667918459410404673473173649215468906981810925676420598006739662864501852090661953622948938870414604397215114998121635153443376761422254645059647616441054621053792673427510353100668664861428374057353161172637671266095296358943110920490442118842860397633084527337550938542697953483620271948205306390349644786873542968679812523808277314879159441909502558166069319615649241027566862990490220961067181937669
e = [176102760168508342366248560703991436320546222245646770978202319048411166429566382514628949532380311738047680739422807353850798607282412088644610303686988373545251970947896120364153937039760741931013881201304685285276800581219089376477570281711773721947249912869605837122685995085027900352995492083277384406401003380587567849080200688516195340372450525399311095577291241729818923687928903049024986910768913495050369506538600090893434395973537955406795607398026050382337136405732255493959814072239958699297858559423614495730987219798816735202147878946461603285288373867465864345098892545645132818258947898456430424006, 3573981821831492277529738650073504616174769536804810418010981678130362702872320797121521713323943777400757776843305922735161754061510443680673867557929082126015295854646693109385804251924239205353662684744351670833911869748673257355076814511174326199099866635753979773946343291340766410907901834068770274767020404800822067211027120846913766665910218577234432145411130775944881987043775179494758158033064351482298980282644264138853891021708458121104223946012736356102642750591504966939159058542007824839461238347551623770276126868717421123099282388441377112476606520160468063905419246868567792524706613954405034280745]
c = [2442003451487395252876121378320580564808335180996151717051522763081890537479875202133875395729806314814096885940653943728394923611282999540770370852775313679101585158491964936530361527619836260073209497935763771182203301056707656219921717552895243715201530990757549283670161276843945223662108755382731302991164300014685362347621843020642892430217171795396599343678165183180757721956247558358291103649246073117361482130651740512048690900488267309376415549379476398675385332885750364853460566103195169529710541031930399449866328356546569547859848315600711606485060302078139530732323306248727557394224647978798154455432, 5877775554635189664514035705193818872462952989637173497670868665060589927366277311749438728976759716021062894771294263103329901952516874052114135886783478914172913186895498679544398990747998647492211189869428581232686408690719184490347471496179923775491153260487724884204595180798615723157844735887389748026739587255981069056269993158062939424519078722321933831961667178045072850177889672933456786971303039062246151676207874781304093381264675070371899409850042467776910769703994219307749656616821280706978085046384421702389657326825914608919485710624515946600476275010829782060955742590243380095470169814313117059260]
El tipo de cifrado es RSA, pero la implementación es incorrecta porque el mensaje m se está cifrando dos veces con diferentes exponentes públicos (e[0] y e[1]) y el mismo módulo público n. Por lo tanto, podemos realizar un ataque de módulo común.
Contexto de RSA
Vamos a recordar cómo funciona RSA: $n = p q$, donde $p$ y $q$ son números primos grandes. El exponente $e$ se utiliza para cifrar un mensaje $m$ como se muestra:
$$ c = m^e \mod{n} $$
El proceso de descifrado necesita $\phi(n) = (p - 1) (q - 1)$ y $d = e^{-1} \mod{\phi(n)}$. Luego para descifrar el texto cifrado $c$ podemos calcular:
$$ m = c^d \mod{n} $$
Ataque de módulo común
Aquí tenemos dos textos cifrados que utilizan el mismo módulo pero distintos exponentes ($e_1$ y $e_2$), pero el mensaje $m$ es el mismo para ambos. Por tanto:
$$ c_0 = m^{e_0} \mod{n} $$
$$ c_1 = m^{e_1} \mod{n} $$
Por la identidad de Bezout, dados dos enteros $a, b$ no nulos, existen enteros $u, v$ tales que
$$ u \cdot a + v \cdot b = \gcd{(a, b)} $$
Los valores $u, v$ se calculan usando el GCD extendido (Algoritmo de Euclides Extendido).
Realizando el ataque
En este reto, $\gcd{(e_0, e_1)} = 7$, por lo que podemos encontrar valores $u, v$ tales que
$$ u \cdot e_1 + v \cdot e_2 = 1 $$
La idea es hallar estos valores para calcular el mensaje $m^7$ de esta manera:
$$ c_0^u \cdot c_1^v = (m^{e_0})^u \cdot (m^{e_1})^v = m^{u \cdot e_0} \cdot m^{v \cdot e_1} = m^{u \cdot e_0 + v \cdot e_1} = m^7 \mod{n} $$
Si $m^7 < n$, podemos simplemente calcular la raíz séptima para encontrar $m$ sobre los números enteros (no módulo $n$).
Flag
En Python, se puede hacer lo siguiente:
$ python3 -q
>>> n = 13761685901869725143768331354410331722080881206892978316226355274731948923788116922997132633408042821072846131527848521009073675634635614838798409359054501234184243307064644162477264359675732802892743867662331151938667918459410404673473173649215468906981810925676420598006739662864501852090661953622948938870414604397215114998121635153443376761422254645059647616441054621053792673427510353100668664861428374057353161172637671266095296358943110920490442118842860397633084527337550938542697953483620271948205306390349644786873542968679812523808277314879159441909502558166069319615649241027566862990490220961067181937669
>>> e = [176102760168508342366248560703991436320546222245646770978202319048411166429566382514628949532380311738047680739422807353850798607282412088644610303686988373545251970947896120364153937039760741931013881201304685285276800581219089376477570281711773721947249912869605837122685995085027900352995492083277384406401003380587567849080200688516195340372450525399311095577291241729818923687928903049024986910768913495050369506538600090893434395973537955406795607398026050382337136405732255493959814072239958699297858559423614495730987219798816735202147878946461603285288373867465864345098892545645132818258947898456430424006, 3573981821831492277529738650073504616174769536804810418010981678130362702872320797121521713323943777400757776843305922735161754061510443680673867557929082126015295854646693109385804251924239205353662684744351670833911869748673257355076814511174326199099866635753979773946343291340766410907901834068770274767020404800822067211027120846913766665910218577234432145411130775944881987043775179494758158033064351482298980282644264138853891021708458121104223946012736356102642750591504966939159058542007824839461238347551623770276126868717421123099282388441377112476606520160468063905419246868567792524706613954405034280745]
>>> c = [2442003451487395252876121378320580564808335180996151717051522763081890537479875202133875395729806314814096885940653943728394923611282999540770370852775313679101585158491964936530361527619836260073209497935763771182203301056707656219921717552895243715201530990757549283670161276843945223662108755382731302991164300014685362347621843020642892430217171795396599343678165183180757721956247558358291103649246073117361482130651740512048690900488267309376415549379476398675385332885750364853460566103195169529710541031930399449866328356546569547859848315600711606485060302078139530732323306248727557394224647978798154455432, 5877775554635189664514035705193818872462952989637173497670868665060589927366277311749438728976759716021062894771294263103329901952516874052114135886783478914172913186895498679544398990747998647492211189869428581232686408690719184490347471496179923775491153260487724884204595180798615723157844735887389748026739587255981069056269993158062939424519078722321933831961667178045072850177889672933456786971303039062246151676207874781304093381264675070371899409850042467776910769703994219307749656616821280706978085046384421702389657326825914608919485710624515946600476275010829782060955742590243380095470169814313117059260]
>>>
>>> def extended_gcd(a, b):
... if a % b:
... u, v, d = extended_gcd(b, a % b)
... return v, (d - a * v) // b, d
... return 0, 1, b
...
>>> import sys
>>> sys.setrecursionlimit(1000000000)
>>>
>>> u, v, d = extended_gcd(e[0], e[1])
>>> m7 = pow(c[0], u, n) * pow(c[1], v, n) % n
>>>
>>> from gmpy2 import iroot
>>> iroot(m7, 7)
(mpz(547208350880355831437019552015402109), True)
>>>
>>> m = iroot(m7, 7)[0]
>>> bytes.fromhex(hex(m)[2:])
b'ictf{XGCD>XKCD}'