This challenge was one of the crypto related tasks during PlaidCTF 2015. The attacker (you) is given a set of public keys and corresponding ciphertexts of the same message. The task is to recover the plaintext (flag).

A fairly trivial observation is as follows: if we succeed to find a linear combination such that , then it can be used to unravel the message, i.e.,

In fact, it suffices to find two relatively prime and . Given these exponents, we can use the Euclidian algorithm without modification to find a linear combination that is . Scanning through the list, we find that two exponents, and , are relatively prime, i.e.,

So,

This could be realized in code in the following way:

def egcd(a, b):
   if a == 0:
       return (b, 0, 1)
   else:
       g, y, x = egcd(b % a, a)
       return (g, x - (b // a) * y, y)

def modinv(a, m):
   g, x, y = egcd(a, m)
   if g != 1:
       raise Exception('modular inverse does not exist')
   else:
       return x % m

def modexp(a, n, m):
	bits = []
	while n:
		bits.append(n%2)
		n /= 2
	solution = 1
	bits.reverse()
	for x in bits:
		solution = (solution*solution)%m
		if x:
			solution = (solution*a)%m
	return solution

A = 0x6fdcbfb5cd2cacd032ef7200fd49b9f304a6dbd8399f4a91a72d1d9150f97b3b513f44dfc56f6f7c8ec41a8ef9b93a80230a1e65e29d2ef519bb83931d4b0c7a589059cfdf2d571660ab790a9c7e085e3018bf19748abd6d521952b68bc9594c1ad34726658bd9bd445d3b6381ceee57328838e8a129867e505be0ca0d1a1da5L

B = 0x8caeaa7d272f9606fee9222efd1d922143db738b95bd64746b27bc4c0fd979a2c57b4735131a4391a81bf5f0c0c8eea41d4f91bed4d17784b1956fd89882b97c98009051ac3a03964499c864524d3ddc10299c0290e91707b62ce89b118afe558151be39d61de0483def52c6cb546132ecab85143715bc593a2892b1e41b37b9L

N = 0xa5f7f8aaa82921f70aad9ece4eb77b62112f51ac2be75910b3137a28d22d7ef3be3d734dabb9d853221f1a17b1afb956a50236a7e858569cdfec3edf350e1f88ad13c1efdd1e98b151ce2a207e5d8b6ab31c2b66e6114b1d5384c5fa0aad92cc079965d4127339847477877d0a057335e2a761562d2d56f1bebb21374b729743L

exp1 = 0x6b8a5ae7
exp2 = 0x4042c3955

_,x,y = egcd(exp1,exp2)
print hex((modexp(modinv(A,N),-x, N) * modexp(B,y, N) ) % N)

from which we obtain

or in ascii ‘flag_Strength_Lies_In_Differences’.