CSCG 2020: Intro to Crypto 3

Intercepted-messages.txt and the pubkeys german_government.pem, russian_government.pem and us_government.pem are given.

The writeup for part 2 can be found here.

Again we'll use RsaCtfTool to dump the pubkeys.

$ ./RsaCtfTool.py --key ./german_government.pem --dumpkey
 [*] n: 13368388890946686131727968139222647635627171995393331225756908262294343216259723081458150905003600322756476137516299938365001972798137046621672975975457070465770187049834603521354462199081700902700733323087201964703391196426066952717511505120664658507099276380167252844734836468387820963170177521935571096868999638202790415914397116993003197932961837711222659120426461631108658146330240545816025557486272830688061978425683447522103977339616076727857816034089500594682018085999092378789197039633371210351470521621878994691517983319668541047042031499811379908242466040735576388227260217406960791406632454767045448789863
 [*] e: 3
$ ./RsaCtfTool.py --key ./russian_government.pem --dumpkey
  [*] n: 18343717802716940630601940481023526351437486074120550591161058762020703345710367605696446334690825248791560509373517279950125583944976720622084902078751153032339436688975255343139180338681178127688700797071320999813387670292350135483485169318320316776584245519471849328634745109353977968597175721348420576770527793000136160877295577014905354451575371196006765377541964045640054268423795610241643005381587433138330817893094851452345761462684724873155990606241842996499888181450611803912139827073505685135888393196549213527418583778495818537291115829823762105372358484486446314835437285354604977091862400207219042791731
  [*] e: 3
$ ./RsaCtfTool.py --key ./us_government.pem --dumpkey
   [*] n: 14463626602170229427356167809091927075048214837573339781774138582390190263460223568524802570585480435667949138330700031482283411314199309061664373861923286634420548935259474128834717819970239283387732315996647938605905994532994027238099470750924616969478147212529380894358056424265545387574975098446117146942068553320197224781384410276446833888437566192029289304444125818681142352673878184276408904704077528699342956063922184456200815444422094356292649411256904543442078043661428831462400371961179888731725665328211651272084619341652653674440701885337593085045665899694222470709757866143325441669946933338126683188131
   [*] e: 3

We can see, that we have three pubkeys with e = 3. Because e is too small, a low exponent attack is possible. I read this wiki Beweis_Low-Exponent-Angriff and followed this ctf writeup attacking-rsa-for-fun-and-ctf-points-part-2. I converted the script to python3 and adjusted n and the cyphertext.

#!/usr/bin/python3
import gmpy

e = 3

#1 Germany
#2 Russia
#3 USA

n1 = 13368388890946686131727968139222647635627171995393331225756908262294343216259723081458150905003600322756476137516299938365001972798137046621672975975457070465770187049834603521354462199081700902700733323087201964703391196426066952717511505120664658507099276380167252844734836468387820963170177521935571096868999638202790415914397116993003197932961837711222659120426461631108658146330240545816025557486272830688061978425683447522103977339616076727857816034089500594682018085999092378789197039633371210351470521621878994691517983319668541047042031499811379908242466040735576388227260217406960791406632454767045448789863
n2 = 18343717802716940630601940481023526351437486074120550591161058762020703345710367605696446334690825248791560509373517279950125583944976720622084902078751153032339436688975255343139180338681178127688700797071320999813387670292350135483485169318320316776584245519471849328634745109353977968597175721348420576770527793000136160877295577014905354451575371196006765377541964045640054268423795610241643005381587433138330817893094851452345761462684724873155990606241842996499888181450611803912139827073505685135888393196549213527418583778495818537291115829823762105372358484486446314835437285354604977091862400207219042791731
n3 = 14463626602170229427356167809091927075048214837573339781774138582390190263460223568524802570585480435667949138330700031482283411314199309061664373861923286634420548935259474128834717819970239283387732315996647938605905994532994027238099470750924616969478147212529380894358056424265545387574975098446117146942068553320197224781384410276446833888437566192029289304444125818681142352673878184276408904704077528699342956063922184456200815444422094356292649411256904543442078043661428831462400371961179888731725665328211651272084619341652653674440701885337593085045665899694222470709757866143325441669946933338126683188131

c1 = 3999545484320691620582760666106855727053549021662410570083429799334896462058097237449452993493720397790227435476345796746350169898032571754431738796344192821893497314910675156060408828511224220581582267651003911249219982138536071681121746144489861384682069580518366312319281158322907487188395349879852550922320727712516788080905540183885824808830769333571423141968760237964225240345978930859865816046424226809982967625093916471686949351836460279672029156397296634161792608413714942060302950192875262254161154196090187563688426890555569975685998994856798884592116345112968858442266655851601596662913782292282171174885
c2 = 9343715678106945233699669787842699250821452729365496523062308278114178149719235923445953522128410659220617418971359137459068077630717894445019972202645078435758918557351185577871693207368250243507266991929090173200996910881754217374691865096976051997491208921880703490275111904577396998775470664002942232492755888378994040358902392803421017545356248082413409915177589953816030273082416979477368273328755386893089597798104163894528521114946660635364704437632205696975201216810929650384600357902888251066301913255240181601332549134854827134537709002733583099558377965114809251454424800517166814936432579406541946707525
c3 = 7156090217741040585758955899433965707162947606350521948050112381514262664247963697650055668324095568121356193295269338497644168513453950802075729741157428606617001908718212348868412342224351012838448314953813036299391241983248160741119053639242636496528707303681650997650419095909359735261506378554601448197330047261478549324349224272907044375254024488417128064991560328424530705840832289740420282298553780466036967138660308477595702475699772675652723918837801775022118361119700350026576279867546392616677468749480023097012345473460622347587495191385237437474584054083447681853670339780383259673339144195425181149815

N = n1*n2*n3
N1 = N//n1
N2 = N//n2
N3 = N//n3

u1 = gmpy.invert(N1, n1)
u2 = gmpy.invert(N2, n2)
u3 = gmpy.invert(N3, n3)

M = (c1*u1*N1 + c2*u2*N2 + c3*u3*N3) % N

m = gmpy.root(M,e)[0]

print(bytes.fromhex(hex(m)[2:]).decode())

You can also find the script here.

$ ./rsa_lowexponent.py
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACSCG{ch1nes3_g0vernm3nt_h4s_n0_pr0blem_w1th_c0ron4}