RSA Common Modulus

A Python 3 script to describe the RSA Common Modulus Attack. Supports various output formats.

The RSA Common Modulus Attack can be explained in the following way. If a single plaintext has been encrypted to two ciphertexts by keys with the same modulus but different exponent, this plaintext can be recovered if gcd(e1, e2) = 1 and gcd(ct2, n)=1.

This is a script originally written by Andreas Pogiatzis in 2018 https://infosecwriteups.com/rsa-attacks-common-modulus-7bdb34f331a5

Maxim Masiutin ported this script in 2021 to Python 3 and added the option to configure the output format, and the code to check that the plaintexts from both decrypted messages to be the same.

This cript can be used as a CTF (capture the flag) tool.

Copyright 2018 Andreas Pogiatzis

Copyright 2021 Maxim Masiutin

References

1. John M. Delaurentis, "A further weakness in the common modulus protocol for the RSA cryptoalgorithm", Cryptologia (1984), vol. 8, nr. 3, pag. 253-259, doi 10.1080/0161-118491859060, Taylor & Francis;
2. Wen-Guey Tzeng "Common modulus and chosen-message attacks on public-key schemes with linear recurrence relations", Information Processing Letters (1999), Volume 70, Issue 3, Pages 153-156, ISSN 0020-0190;
3. Hinek, M. and Charles C. Y. Lam. “Common modulus attacks on small private exponent RSA and some fast variants (in practice)." J. Math. Cryptol (2010).
4. Andreas Pogiatzis "RSA Attacks: Common Modulus" https://infosecwriteups.com/rsa-attacks-common-modulus-7bdb34f331a5 InfoSec Write-ups (2018).

Usage

./rsa-common-modulus.py --help
usage: rsa-common-modulus.py [-h] -n MODULUS -e1 E1 -e2 E2 -ct1 CT1 -ct2 CT2 [-q] [-of {decimal,hex,base64,quoted,ascii,utf-8,raw}]

RSA Common modulus attack

optional arguments:
  -h, --help            show this help message and exit
  -q, --quiet
  -of {decimal,hex,base64,quoted,ascii,utf-8,raw}, --outputformat {decimal,hex,base64,quoted,ascii,utf-8,raw}

required named arguments:
  -n MODULUS, --modulus MODULUS
                        Common modulus
  -e1 E1, --e1 E1       First exponent
  -e2 E2, --e2 E2       Second exponent
  -ct1 CT1, --ct1 CT1   First ciphertext
  -ct2 CT2, --ct2 CT2   Second ciphertext

Example

./rsa-common-modulus.py --modulus 796046976267140048752546154932638141846809271157348899883513224231800801281663713220563870148648793624678323381906728725898725928596680500518940746271853482399810210057091502861196533147931022318338354016009757865001297647739055103452118365721808573406783257552507598416632103904961723220298888384909045631416360650009712451135751460352325210129820833126923032425811340496558451833220669001419079718864899011790430656615142855746464852636907672485399576242763589278180782846695340454647765013827286929492245836970042543924374020806604208920381413470658412254252313745393586853102421084806582171223689438354423203696273836093192343584415041273242933998254743962387377506504630373856105264327665064425098235259803036512713908344911145980472783106259442452695987247891976470720584209522481276089143563659276889288760838263527249718303354354985647212777831233150083801152848890274854787868372570876535365082610567569544515309682528365198976054322533155982861471385263909944837022698608946832219181966844378167787320014527202050782745964264950257437650664172903256012399501034389493852412114178775305195605979357801391371049021592219897438567947933506927811351524206748949809481325267401087053562324767143004720403230355108394877334594537 --e1 3 --ct1 677857017311763186860567982654337032650834586690095258338235412812228467611035329090649921205228953198535625711022945876204650198045325847258301676934646614423616990415191913570666093383913463001326454280361403407607686684102465371942022713121890433591998561871665682397006511651344750053237409941064414645886555685688807651570672751381738598840430594975227190501615345745968967821285535616165986198671691377028117465961830219713461759558403414387177246415440645361044504400569481118995297580096967835695317416763301434554234397996433246180679748610090981124894668706889506848323747962564526137972614875972972192302984597297033318488280486242895302087407899762837918262857934652018585335691953378174052229396432060930635228202890687717669316718285891145998140984357560231897920371005520716264899681852382730051852536731165421684996451077286546319712195872602906040467326577101221528456760828093900950948924996262543470972266061604840215505501324963605312049988678793296255515350112037056850966041404320745982460944124895847690169173071342857962130341858069349579000988755992128058090484640749963821143833617833092376598840161724626184224231427547414797678750003926356112407360212430895514105702539975372169078233219887553101433335602 --e2 65537 --ct2 601493407681258706301212630371765836712721516357379153126698448772913425755345373351999455599901568863042774784324341707841847122358382150282504389439056511519686005360296830238200195273474230656920328120382410437160773992539168170515583065306690635876671099815962152574746595359020588218425821146026424091959891161038474251609850097088428613776150745093068163650599039268705169928544257629196036395723688306589693107849524168534065583580416117896076008373939909579394873734384325582130831618451047746994700561212550082896774358800607404111522726538759945496629353415486600135366163874217209193871194941929100356674029050257188585093783810176568282311040557522199191440171182944993026000270466496742474802742191655785689816067597013490901316714778352360497468496802839081281516379780261364759673395148301698227177891788409350246379001987106189634459880154186726453955464522247586980820756844797563354106237653450878182817038606284704207734571556349546696404450285952964373070003985784193530200066892492507584269300913364353481177558967552102028899262770099108137431061854533014285495170981660277007574290701113043938264140999960781912992109537395204348175518480070455875063031760931523801264329168728292571703126346128217668563673827 --outputformat ascii --quiet