# PlaidCTF 2015 : Strength

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

$\left\{ \begin{array}{ccc} c_1 & = & m^{e_1} \bmod{N} \\ c_2 & = & m^{e_2} \bmod{N} \\ & \vdots & \\ c_k & = & m^{e_k} \bmod{N}\end{array} \right.$

A fairly trivial observation is as follows: if we succeed to find a linear combination such that $\sum_{i=1}^k a_ie_i = 1, a_i \in \mathbb{Z}$, then it can be used to unravel the message, i.e.,

$\prod_{i=1}^k(m^e_i)^{a_i} = m^{\sum_{i=1}^k a_ie_i} = m$

In fact, it suffices to find two relatively prime $e_i$ and $e_j$. Given these exponents, we can use the Euclidian algorithm without modification to find a linear combination that is $\pm 1$. Scanning through the list, we find that two exponents, $\texttt{0x6b8a5ae7}$ and $\texttt{0x4042c3955}$, are relatively prime, i.e.,

$-a_ie_i + a_je_j = \texttt{-0xe860d9d9*0x6b8a5ae7 + 0x184e2990*0x4042c3955} = 1.$

So,

$(m^{e_i})^{-a_i}\cdot (m^{e_j})^{a_j} = (c_i^{-1})^{a_i}\cdot(c_j)^{a_j} = m.$

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

$\texttt{0x666c61675f537472656e6774685f4c6965735f496e5f446966666572656e636573L},$

or in ascii ‘flag_Strength_Lies_In_Differences’.