RSAgain

3 minutes to read

We are given the source code used to encrypt the 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])

And the output of the above script:

n = 13761685901869725143768331354410331722080881206892978316226355274731948923788116922997132633408042821072846131527848521009073675634635614838798409359054501234184243307064644162477264359675732802892743867662331151938667918459410404673473173649215468906981810925676420598006739662864501852090661953622948938870414604397215114998121635153443376761422254645059647616441054621053792673427510353100668664861428374057353161172637671266095296358943110920490442118842860397633084527337550938542697953483620271948205306390349644786873542968679812523808277314879159441909502558166069319615649241027566862990490220961067181937669
e = [176102760168508342366248560703991436320546222245646770978202319048411166429566382514628949532380311738047680739422807353850798607282412088644610303686988373545251970947896120364153937039760741931013881201304685285276800581219089376477570281711773721947249912869605837122685995085027900352995492083277384406401003380587567849080200688516195340372450525399311095577291241729818923687928903049024986910768913495050369506538600090893434395973537955406795607398026050382337136405732255493959814072239958699297858559423614495730987219798816735202147878946461603285288373867465864345098892545645132818258947898456430424006, 3573981821831492277529738650073504616174769536804810418010981678130362702872320797121521713323943777400757776843305922735161754061510443680673867557929082126015295854646693109385804251924239205353662684744351670833911869748673257355076814511174326199099866635753979773946343291340766410907901834068770274767020404800822067211027120846913766665910218577234432145411130775944881987043775179494758158033064351482298980282644264138853891021708458121104223946012736356102642750591504966939159058542007824839461238347551623770276126868717421123099282388441377112476606520160468063905419246868567792524706613954405034280745]
c = [2442003451487395252876121378320580564808335180996151717051522763081890537479875202133875395729806314814096885940653943728394923611282999540770370852775313679101585158491964936530361527619836260073209497935763771182203301056707656219921717552895243715201530990757549283670161276843945223662108755382731302991164300014685362347621843020642892430217171795396599343678165183180757721956247558358291103649246073117361482130651740512048690900488267309376415549379476398675385332885750364853460566103195169529710541031930399449866328356546569547859848315600711606485060302078139530732323306248727557394224647978798154455432, 5877775554635189664514035705193818872462952989637173497670868665060589927366277311749438728976759716021062894771294263103329901952516874052114135886783478914172913186895498679544398990747998647492211189869428581232686408690719184490347471496179923775491153260487724884204595180798615723157844735887389748026739587255981069056269993158062939424519078722321933831961667178045072850177889672933456786971303039062246151676207874781304093381264675070371899409850042467776910769703994219307749656616821280706978085046384421702389657326825914608919485710624515946600476275010829782060955742590243380095470169814313117059260]

The encryption type is RSA, but the implementation is wrong because the message m is being encrypted two times with different public exponents (e[0] and e[1]) and the same public modulus n. Hence, we can perform a Common modulus attack.

RSA background

Let’s review how RSA works: $n = p q$, where $p$ and $q$ are some large prime numbers. The exponent $e$ is used to encrypt a message $m$ as follows:

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

The decryption process needs $\phi(n) = (p - 1) (q - 1)$ and $d = e^{-1} \mod{\phi(n)}$. Then to decrypt the ciphertext $c$ we can compute:

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

Common modulus attack

Here we have two ciphertexts that use the same modulus but different exponents ($e_0$ and $e_1$), but the message $m$ is the same for both. So:

$$ c_0 = m^{e_0} \mod{n} $$

$$ c_1 = m^{e_1} \mod{n} $$

From Bezout’s identity, given non-zero integers $a, b$ there exist integers $u, v$ such that

$$ u \cdot a + v \cdot b = \gcd{(a, b)} $$

The values $u, v$ can be calculated using the extended GCD (Extended Euclidean algorithm).

Performing the attack

In the challenge, $\gcd{(e_0, e_1)} = 7$, so we can find $u$ and $v$ such that

$$ u \cdot e_0 + v \cdot e_1 = 7 $$

The idea is find those values to calculate the value $m^7$ in this way:

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

If $m^7 < n$, we can simply compute the 7th-root to find $m$ over the integers (not modulo $n$).

Flag

In Python, we can do the following:

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