Multi Layer RSA - InCTFi 2017
Challenge Points: 100 Challenge Description: [None] Intended Solution This is probably the easiest challenge in the Crypto section for this year’s InCTF. The encryption script: from Crypto.Util.number import * flag = open("flag.txt").read() flag = int(flag.encode("hex"),16) p = getPrime(512) q = getPrime(512) n = p*q phin = (p-1)*(q-1) encryption_keys = [34961, 3617491, 68962801, 293200159531, 1191694878666066510321450623792489136756229172407332230462797663298426983932272792657383336660801913848162204216417540955677965706955404313949733712340714861638106185597684745174398501025724130404133569866642454996521744281284226124355987843894614599718553178595963014434904833] for i in encryption_keys: assert GCD(i,phin) == 1 for i in encryption_keys: flag = pow(flag, i, n) flag = hex(flag)[2:].replace("L","") obj1 = open("ciphertext.txt",'w') obj1.write(flag) As we can see, the encryption is layered; after the message is encrypted using the first public key i.e. first element of encryption_keys, the result is then encrypted with the next public key i.e. second element of encryption_keys and so on. We can write it mathematically as: $$c_1 \equiv m_1^{e_1}\mod n$$ $$c_2 \equiv c_1^{e_2}\mod n$$ $$…$$ $$c_5 \equiv c_4^{e_5}\mod n$$ ...