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: , donde y son números primos grandes. El exponente se utiliza para cifrar un mensaje como se muestra:

El proceso de descifrado necesita y . Luego para descifrar el texto cifrado podemos calcular:

Ataque de módulo común

Aquí tenemos dos textos cifrados que utilizan el mismo módulo pero distintos exponentes ( y ), pero el mensaje es el mismo para ambos. Por tanto:

Por la identidad de Bezout, dados dos enteros no nulos, existen enteros tales que

Los valores se calculan usando el GCD extendido (Algoritmo de Euclides Extendido).

Realizando el ataque

En este reto, , por lo que podemos encontrar valores tales que

La idea es hallar estos valores para calcular el mensaje de esta manera:

Si , podemos simplemente calcular la raíz séptima para encontrar sobre los números enteros (no módulo ).

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}'