Chonky E
Category: Crypto
Points: 100
Description:
E
Note: P>Q
Author: AC
Given: ChonkyE.txt
Writeup
From the text file given, we see two different cryptosystems in play: RSA and Schmidt-Samoa. We are given the ciphertext encrypted by the Schmidt-Samoa cryptosystem and the n and e from the RSA cryptosystem. I have given links to the Wiki pages for both cryptosystems below.
Schmidt Samoa encryption is very similar to RSA encryption. The main two differences is the e (encryption key) and n.
I’m not sure about any other ways to get this information, but I used RsaCtfTool to get the p, q, and d for the respective e and n.
Here is the output of the program:
~/ctfs/hsctf2020/crypto/samoa$ python3 ~/tools/RsaCtfTool/RsaCtfTool.py -n 156749047558583013960513267351769479915110440411448078412590565797031533622509813352093119636835511977253033854388466854142753776146092587825440445182008237325262012698034419137157047927918635897378973846177552961727126115560551970797370239385129543828686170774323306933202481728884019420422360360849592983818405154473369790181636472137741865440233383956571081122982223602667853668754338360008279002325576495573847568301584365514417593244726435632222027817410359417329310347952169273512510934251453361933794586716533950489973436393834189505450956622286216819440777162804798432330933357058175885674184582816364542591313 -e 91043118409828550796773745518585981151180206101005135117565865602978722878478494447048783557571813980525643725323377488249838860897784683927029906188947001149632101513367258267329961684034661252866484981926055087386190015432964608927947646476193251820354738640453947833718397360834701566765504916472450194494897616371452996381159817427887623703639133290358520498419049175941584678802701606995099241245926884172985004839801270005583030514286561971825047719421487004569752638468907609110285739083279629747310953086535889932550905065172805818862336335628248528993024112446002398466115161473573451161053837400091893285717 --private
[*] Testing key /tmp/tmpgs29c3l6.
Can't load boneh_durfee because sage is not installed
Can't load ecm because sage is not installed
Can't load ecm2 because sage is not installed
Can't load qicheng because sage is not installed
Can't load roca because sage is not installed
Can't load smallfraction because sage is not installed
[*] Performing comfact_cn attack on /tmp/tmpgs29c3l6.
[*] Performing cube_root attack on /tmp/tmpgs29c3l6.
[*] Performing factordb attack on /tmp/tmpgs29c3l6.
[*] Performing fermat attack on /tmp/tmpgs29c3l6.
[*] Performing londahl attack on /tmp/tmpgs29c3l6.
[*] Performing mersenne_primes attack on /tmp/tmpgs29c3l6.
[*] Performing noveltyprimes attack on /tmp/tmpgs29c3l6.
[*] Performing partial_q attack on /tmp/tmpgs29c3l6.
[*] Performing pastctfprimes attack on /tmp/tmpgs29c3l6.
[*] Performing pollard_p_1 attack on /tmp/tmpgs29c3l6.
[*] Performing primefac attack on /tmp/tmpgs29c3l6.
[*] Performing siqs attack on /tmp/tmpgs29c3l6.
[!] Warning: Modulus too large for SIQS attack module
[*] Performing smallq attack on /tmp/tmpgs29c3l6.
[*] Performing wiener attack on /tmp/tmpgs29c3l6.
Results for /tmp/tmpgs29c3l6:
Private key :
-----BEGIN RSA PRIVATE KEY-----
MIIEXwIBAAKCAQEE2bEPIRfdrVNyfmzmWZaB9ydQSeEAV+BqZicqXDhPj2wfJZg2
r1BGm2bFYOfWmZ7XBxzPX/jhmeKGrRgRjSoom3aGG3Pxvrs7Ld6c7uPitwJpXMvX
akLyyfBfeZ4vi2kusdxmw7OuPqnoLYC7neO7LHjfNGQdxLkU5kjbie2RWb2n9opJ
HYoJsNLeB7SysRUWrh4PSyerquUzBnipxATHXdWkUo2IU6XsxJUSLLmdMO9m9B3e
/B7EiNGADI4SYf0+1DgiatfsI4sG72N7MHc7uosPotJP4fm+bUBa3GvBiZjF1ijF
HF3Ysfc0WRWlHryJktKdbHiS7vOGORXuZ/iBUQKCAQEC0TNOpXV3GyrNfiwp0CyX
jUhp9t4ZDkSyKQmykstZ4rI2sGBk1Va9CfuQdz2pgObbN3/I8EVdn0L1k2+hkeUa
7VArlFTAd/2TQmVK9kcqqZPzRSQ0U1zh9nqJB8WGq4C7MtJ1jKPYLi5A9EhyJb18
TEQ5vWreS5D/zaRmcVPyGFFizV2eu5rhWRe8WMbin63tCckmwbo24Dsg/9UHs/8r
EuuKXa6gjTrsvnh8a6xcSkOLo8WwhTrW+M/+BnW/BuMaYLeAid4Pk1UWDTrFceP/
kUUA1x/iPafhvo5FnHZT8aJ/bUAl9CqK1h7wjSz5ArnSiCXR3l9Mjy5e1q7VOYHD
VQJAW67Pb58KG9KV6WULShC0pxfbAwIj6AP46WShirm8/AlUqPQQzAAXetn2oNWB
4Sxt/QZy3W5cPvN+EI6R05uk/QKBgQHiep/6oT3VUgLU1e+048tZqumrGHhQzOzr
E60AVmh1uNwGazrIyM+fWvItgXveXJA60gFCBUyz6nn8r8j3jKiPrtGZTZ8zN6qW
66Y3sWSXB3JjI/OiHHIaFM2sJl9lqYCRZDVWz8M3gx3bE4IeFp47fjcd83J/36hq
f1vVWTg7iQKBgQKS1TtgUTN8XMo4qHP0sf161qhoBj5ICe/2WL+q6To9uYeZ/7BQ
R7cwvlpB7J9ViGrLe5HBDiomprMo5ABY4K0biQ4udRCMB9LxvlUpkRhnTWbKVlD1
aVjrXX06zoc0o56T/YxnaPpZeO0d2KzEBergGrqMgSVlD/Xl3SM0u+k9iQJAW67P
b58KG9KV6WULShC0pxfbAwIj6AP46WShirm8/AlUqPQQzAAXetn2oNWB4Sxt/QZy
3W5cPvN+EI6R05uk/QJAW67Pb58KG9KV6WULShC0pxfbAwIj6AP46WShirm8/AlU
qPQQzAAXetn2oNWB4Sxt/QZy3W5cPvN+EI6R05uk/QKBgQHbAH/3Q83q2VcaB1MF
uroXJsMXRHbDwBLofgBb480QW1MFsoPS4Ac0O6OgvYh6agstMle5CYyf1qJtncXR
hV+4FqmRF+30r8uH/475p9pLNIN8rTXIQO/sG8Qw0A+AHYGjKVCr530Ncwf6m/Om
KAdcdl95Bui9gj9QyqDAwCDf2Q==
-----END RSA PRIVATE KEY-----
From the private key, we can get our d, p and q:
~/ctfs/hsctf2020/crypto/samoa$ python3 ~/tools/RsaCtfTool/RsaCtfTool.py --dumpkey --key priv.key
private argument is not set, the private key will not be displayed, even if recovered.
n: 156749047558583013960513267351769479915110440411448078412590565797031533622509813352093119636835511977253033854388466854142753776146092587825440445182008237325262012698034419137157047927918635897378973846177552961727126115560551970797370239385129543828686170774323306933202481728884019420422360360849592983818405154473369790181636472137741865440233383956571081122982223602667853668754338360008279002325576495573847568301584365514417593244726435632222027817410359417329310347952169273512510934251453361933794586716533950489973436393834189505450956622286216819440777162804798432330933357058175885674184582816364542591313
e: 91043118409828550796773745518585981151180206101005135117565865602978722878478494447048783557571813980525643725323377488249838860897784683927029906188947001149632101513367258267329961684034661252866484981926055087386190015432964608927947646476193251820354738640453947833718397360834701566765504916472450194494897616371452996381159817427887623703639133290358520498419049175941584678802701606995099241245926884172985004839801270005583030514286561971825047719421487004569752638468907609110285739083279629747310953086535889932550905065172805818862336335628248528993024112446002398466115161473573451161053837400091893285717
d: 4801820624110300567381264152630360984400101198006662778338105999190025449039653722546363948393959163699344836724430590700225590643966670154013435626235133
p: 338808278305491368568107597536870102903517054340801660200304926784154444523223906451699772927968482815828890482348342203845897909840260655384526983598744312581591533978845446602589686620835190303243711955190856932946979670202446096542521271004217036632261094082852110229243380763789393081471800046961479400329
q: 462648222004918001013626929700851985161214529015962355517097297750332107059692278343607439888140451722661722449586909096508950271217838478793469222136256780856060573039970361424138955569021582604733404145398646735820327194382610835536537670219091779958808528053471059443883883244638910795974245528935198178697
From the note at the beginning of this problem, we see that P>Q, meaning we need to switch our P and Q here.
Since we know the ciphertext is encrypted with the Schmidt-Samoa cryptosystem, we have to calculate a new N and e for this system. The N and e will be the exact same in this cryptosystem.
My script calculates the encryption key, then uses modular inverse to find the decryption key and uses it on the cipher text:
~/ctfs/hsctf2020/crypto/samoa$ python3 samoa-crypto.py
[*] Decrypting Schmidt-Samoa Ciphertext
[+] flag: flag{remarkably_superb_acronym}
Flag
flag{remarkably_superb_acronym}
Resources
Unexpected
Category: Crypto
Points: 100
Description:
Alice, Bob, and Carol are really close friends; in fact, they are so close, they even share the same primes in their RSA public keys! Alice > has N = PQ, Bob has N = QR, and Carol has N = PR, where P,Q,R are 1024 bit primes. All three also use the same public exponent e = 65537. Can you recover the three plaintexts?
Author: AC
Given: unexpected.txt
Writeup
From the description and the text file given, we can see that this is some twisted version of RSA. If you are unfamiliar with RSA, hang on because this isn’t too easy if you don’t understand it yet. I encourage you to read the Wiki I put in the resources as well as other websites giving examples.
Basically, RSA usually has an N = P*Q, but this is a little different. We have three different ciphertexts and three different N’s to deal with.
So I am assuming that the following below matches respectively to the .txt file given.
Since we have three equations and three knowns, we can probably work this out. Here’s the math:
Following these steps to isolate P and Q can give us similar answers. You also could divide the second N by R to get Q and the third N by R to get P.
I fiddled around with the math in Wolfram Alpha and Python to get the exact P, Q, and R. I had troubles formatting in Python for a while, so I don’t have my implementations on how I got P, Q, and R, but I will include them in my script.
Since we had the P’s, Q’s, N’s, C’s, and E for all three parts, all we have to do is find the decryption key (D), which found by modular arithmetic:
In my script, I copied and pasted a few functions to help find the modular inverse.
Here is the output to my script:
-----------------------------------------------------------------------------------------------------------------
phi: 3895738302299059518129198422310169628530536557191890566210939781698372336257482186582163630847612416277492034959243510457939210010336159061758606919109259916143600981918456942199762738624796190838889500238780675229383463267807384154074134251073572174392024892486431125499446924573006208711810847272390619510267715478341382535579105584675673997982203778973283813503737131926142658191419941161164257547319794943883811280878885096660672763345495601914053572772464688944398278968911503771601753848356268487278305957060424301523898709351034955902146951194283368812207947125965045248566943026323694697043787381033801270628
d: 905024881402920200245922852429502915824304119554549855357455455336034893564248688385392088128155073284172547297778086374446869286164579118898863090215275069400282663986885376886207603270862596785359303006476277223055117387923881528690338190222242952150976989915710421376155140250911996698617882260740454736161648658891123321241312274389842937871416948210449762128177942743420082868675230849424383495703860079354120981298823955882306831590325625816584000571597340268527149507937159847454669916859547854171112626397988311804039822540999850521235139416405454783799471977551883881005107154367429875680785859533387618373
flag 1: flag{n0_0n3_3xp
-----------------------------------------------------------------------------------------------------------------
phi: 3036683903819675505741091164945461947189004916494633766372176282409409694958701211748277050499101511956962003835932755555293255586827283990400451317444723234406968971873530093281591689832798646915816609347861047534121792409030834659241904646743453387504496246791081682741245482378149293399372654558929658581960048798293605082264581070963505109295072607249172619834489529823110742182685123132307321795995115486491236524357398246542818317495137394745528263555605271324314200817069662802883230041385249726748989486591785200139057355527310020359454945749706230370552400570507369464671540537160407575553116627107873474612
d: 1949006439818224984329272283917496465883563693829650123058926270152539786670855380468556350994761842889447072147807185207169998775481270831564065852353287355369643649601237412663130617047423737510413873674398877617647511392054320433826574837968931746015252843870993008852175240326412465145762118630884206309916314945795869670190809368569478545131431696274195460703085785021430751307357436780967131188564361241867660740101701976659452933286509364712775307840447755126335172939994220462909155213555514583460377264362272622693275089576044698206810708196437022873743772604746196527037841366168396842249275137495437416461
flag 2: 3ct5_th3_sp4nis
-----------------------------------------------------------------------------------------------------------------
phi: 4793455677299549137382284585015750073239112414361680529255951318217960300841340399094743130287927996565298160174555422185410320841942637374406558835150138631140265626020072464652973386772727192540062051929655235552439145036105501434801984612127808829810146844869487529177642676245549299371487478280457673839585943066849022337520545603509204219821850868445721914238164436588614152654669526278241319272348057855708723349268650822215550667738881235874405982991956631703034012350958220927976873112789326373350047289917675374669209722838179591673306110922540875421581379673701918694867142296015241867468105452451023716116
d: 2833344309736941490820680535488962362285987102057506146792148590340225309885894141937106663123025996474457483998991835827371179772879043694550578698384821860828411581561035249335900072581929383167018993357202565189593475447589223104221421180472207431667385880900166438886179135334240028671631016580380081010694420900004538311348870036601302364579685657595715023784396813167672231648329769580031314005404871526228611701847338076979202614811004185655473075806680440040162527586728406279017472735145534965757268900267496355706484066150501259170247831376434509240295092631641132892896582972413116857072790469765899518057
flag 3: h_inquisiti0n!}
-----------------------------------------------------------------------------------------------------------------
Flag
flag{n0_0n3_3xp3ct5_th3_sp4nish_inquisiti0n!}
Resources
RSA Info: https://en.wikipedia.org/wiki/RSA_(cryptosystem)
LCM and GCD functions: https://gist.github.com/endolith/114336/eff2dc13535f139d0d6a2db68597fad2826b53c3
Wolfram Alpha: https://www.wolframalpha.com/