Writeup for Rivest Shamir Adleman (Crypto) House plant ctf

Rivest Shamir Adleman

A while back I wrote a Python implementation of RSA, but Python’s really slow at maths. Especially generating primes.

The was like one of the basic RSA challenge but it took me a while to figure that out.

Publickey.json
{“n”: 5215102981058174620100754813213017625443626121109099133656454487932754235228856710661075956048331662593471061936196995326042367228980357932444477256496372200491821105922086202549125972429240337409176104237690646206864286971669895986447543904638596421264915837230690039800948447210554706127145724519079487023930504508462885777797916915752532472831523596571484341342780877665593787078959178539369282442522815729401991936772080063808078804309866694041173404657777517753433918322041736500126265865045225739241983004392226366771900174432875800986183772576663590650132115754645829772406067103501861326445534174181231077263, “e”: 5}

secrets.txt.enc
0x20ba6aee3bd1c1b751082bfcb667bad8b632504336f3994606594f4ab756f66e3a24f9782da3a07280aa67cd875e6e33f2c573abf7b7901e5cd428ab8ceb6738b13536fee35a90dac7c2175e41eea5977dfbaff6e68f5b1f6fa3673cba64923b02bff899e2535f7d09afecae6774260ce8be4867f45e63571a2055c645a03dd05d9dd596eec273e1ef4352d712deffc658745d17853cbe5c3bc138574703c994be5374e3ac73279f51f23ec7e55b25b6ab904e06562025c380ce4c4d5ddffc2d649fbd1421b82090d01f24c70254187f1f435e64d7b2bf8395915da3cfdd8680187566b6a51e48146b4a40f08aebdedca8a08557ea3dc5efc2c50377b5764a8c

component.txt
88761620475672281797897005732643499821690688597370440945258776182910533850401433150065043871978311565287949564292158396906865512113015114468175188982916489347656271125993359554057983487741599275948833820107889167078943493772101668339096372868672343763810610724807588466294391846588859523658456534735572626377

Secrets was the cipher text and component was one of the prime number used to generate public key. So RSA became easy.

I was too lazy to make a script so I just did it in IDLE.

In [1]: from Crypto.PublicKey import RSA

In [2]: from Crypto.Util.number import *

In [3]: p=88761620475672281797897005732643499821690688597370440945258776182910533850401433150065043871978311565287949564292158396906865512113015114468175188982916489347656271125993359554057983487741599275948833820107889167078943493772101668339096372868672343763810610724807588466294391846588859523658456534735572626377

In [4]: n=5215102981058174620100754813213017625443626121109099133656454487932754235228856710661075956048331662593471061936196995326042367228980357932444477256496372200491821105922086202549125972429240337409176104237690646206864286971669895986447543904638596421264915837230690039800948447210554706127145724519079487023930504508462885777797916915752532472831523596571484341342780877665593787078959178539369282442522815729401991936772080063808078804309866694041173404657777517753433918322041736500126265865045225739241983004392226366771900174432875800986183772576663590650132115754645829772406067103501861326445534174181231077263

In [5]: q=n/p

In [6]: p*q==n
Out[6]: True

In [7]: ct=0x20ba6aee3bd1c1b751082bfcb667bad8b632504336f3994606594f4ab756f66e3a24f9782da3a07280aa67cd875e6e33f2c573abf7b7901e5cd428ab8ceb6738b13536fee35a90dac7c2175e41eea5977dfbaff6e68f5b1f6fa3673cba64923b02bff899e2535f7d09afecae6774260ce8be4867f45e63571a2055c645a03dd05d9dd596eec273e1ef4352d712deffc658745d17853cbe5c3bc138574703c994be5374e3ac73279f51f23ec7e55b25b6ab904e06562025c380ce4c4d5ddffc2d649fbd1421b82090d01f24c70254187f1f435e64d7b2bf8395915da3cfdd8680187566b6a51e48146b4a40f08aebdedca8a08557ea3dc5efc2c50377b5764a8c

In [8]: e=5

In [9]: d=inverse(e,(p-1)*(q-1))

In [10]: long_to_bytes(pow(ct,d,n))
Out[10]: ‘VERIFICATION-UpTheCuts-END\n . — .\n/.-. \’ — — — — — .\n\\\’-\’ . — “ — “”-”-\’\n \’ — \’\n\nrtcp{f1xed_pr*me-0r_low_e?}’

Hence we got the flag

rtcp{f1xed_pr*me-0r_low_e?}