RSA 1s Fun - InCTFi 2017
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$$ ...