RSA

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$$ ...

Challenge Points: 150 Challenge Description: Mathematics and Crypto make a deadly combination! Intended solution! The challenge, as the description suggests, involves applying mathematics to solve the RSA based encryption system. The encryption script: from Crypto.Util.number import * e1 = 9 e2 = 123 def prime_gen(): while True: p = getPrime(1024) q = getPrime(1024) n = p*q phin = (p-1)*(q-1) if GCD(e1, phin) == 1 and GCD(e2, phin) == 1: return (p, q, n) p, q, n = prime_gen() print "p: ", p print "q: ", q print "n: ", n flag = bytes_to_long(open("flag.txt").read().strip()) assert flag < n assert flag**9 > n c1 = pow(flag, e1, n) c2 = pow(flag, e2, n) print "c1: ", c1 print "c2: ", c2 Two different public key exponents \(e_1 = 9\) and \(e_2 = 123\) are being used to encrypt the same message and generate ciphertexts \(c_1\) and \(c_2\) respectively. By Extended Euclidean Algorithm, we can calculate coefficients of Bezout’s identity \(a, b\) as: $$e_1*a + e_2*b = gcd(e_1, e_2)$$ $$(9*14) + (123*(-1)) = 3$$ ...

Challenge Points: 297 Challenge Solves: 9 Challenge Description: Some people think that combination of cryptographic systems will definitely improve the security. That’s your turn to prove them wrong. This is a multi-prime RSA challenge where we are given an encryption script, which has two functions: Generating public and private keys - make_pubpri Encrypting data using the public key generated from the first function - encrypt Preliminary Analysis: make_pubpri function Function generating public and private keys: ...