Twin

Common Modulus Attack

4KB

twin.zip

archive

so from the challenge the description we can notice that alice and bob use the same modulus N and this makes RSA vulnerabale to an attack called Common Modulus Attack

this is a resource where you can study this vulnerability and understand it mathematically

• https://cryptohack.gitbook.io/cryptobook/untitled/common-modulus-attack

Exploitation

from Crypto.PublicKey import RSA
from Crypto.Util.number import long_to_bytes, bytes_to_long 
import gmpy2
import base64

#importing both RSA public keys
key1 = RSA.import_key (open('key1.pem', 'rb').read()) 
key2 = RSA.import_key (open('key2.pem', 'rb').read())

print("{key1.e=}") 
print (f" {key2.e=}") 
print("{key1.n=}")
print(f" {key2.n=}")

#making sure that both rsa public keys uses the same modulus N 
assert key1.n == key2.n

#those cipher text exist in the ciphers.txt file 
ct1 = 198851474377165718028112972842265639215206348877016608622627311171042209963702835769614338398847455363946863082762173236373502223802847244557769309152020719377009343678096323767255545133734392981272835212545353488715110156427711111525743585480758640009319505322315888005188276904901023280620051538053743929669167795850860335549768969166461593906239357372330505433946129717041834475732372670961026001478227254999273718196250867204510681064391880099449164629711720021122445665846890550815079811041241824128791656795460007230003283109669795738520458565694688073372232365469969279979269172335621053156518588065204669164636568515585968088715299221616098448196835007486026306834585857385394379932580809203103023106229424720660096661585932612179471986633721231396764156601845262479014417201866703796806022479395694033815788446795158605478744234679438921219482709321859861288988156224563399413134218092016216147313958327131507901433719054874275160651556856183380492151746510052730242685874618761355215984376265719715473363476986957901445315504092719499838417381325617015369293491930133307630128865051357500960150518954750856507501366553062420719464692404538472137892443679198526541754483324903275970820090884602410278644781399298682978387326
ct2 = 541940109836125333895781430104885967485013462238357425709353944075428304212181613346342168833632915771850317706081582413750750719712828061669251836467513116815496399077435572514863813419820177695716122433176805528532535188403726732767914692088563121640407878586264559446821905465347721083017105647280563402969518765808190495949892463753148040234604183497869168213134441134251591933907135463336654029223065998877557269475470179804195639035481928376550039377473960558788269310431313825888988908660191302311385846641723702093086996138971258640836061285893970041520552244977929645483977290602241276584136088984907441193129409236710662584843118801800457934169438121910252362434716190064236551302755562358860534549136237814085075287652312464795604230258140807652348468032431267225399615168922885291236301151723996369977845223020976025668767146139688511344868583917521559162297134719274102553947904603784500638033579530233721139319885875767560434666844423652986065991855466499543496592686627509183766091917402747468665062914322631033890742828511915046161646985793301031872822709060588586773552581644418553383314263000798086024158809854568189418235663070035600457464233007552461215491869285368208456103672933515573777187729174614608959934215

# calculating the greatest common divisor of e1 and e2
print ( f"{gmpy2.gcd(key1.e, key2.e)=}" )

# gcd(e1, e2) == g =>  Thus using Bezout's Theorem we can get: a1 * e1 + a2 * el == g
# then we get this => m^(e1) = ct2 m^(e2) = ct1
g, a1, a2 = gmpy2.gcdext (key1.e, key2.e)
print ( f"{g=}\n{a1=}\n{a2=}" )

m = pow(ct1, a1, key1.n) * pow(ct2, a2, key1.n) % key1.n
# => m = m^g

# if gcd(key1.e, key2.e) ≠ 1 => we need to do this iroot
# if gcd(key1.e, key2.e) = 1 => then iroot is not needed
m = gmpy2.iroot (m, g) [0]

print (long_to_bytes (m).decode())

let's run this script and we get the flag