# 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

B = 0x8caeaa7d272f9606fee9222efd1d922143db738b95bd64746b27bc4c0fd979a2c57b4735131a4391a81bf5f0c0c8eea41d4f91bed4d17784b1956fd89882b97c98009051ac3a03964499c864524d3ddc10299c0290e91707b62ce89b118afe558151be39d61de0483def52c6cb546132ecab85143715bc593a2892b1e41b37b9L


$\texttt{0x666c61675f537472656e6774685f4c6965735f496e5f446966666572656e636573L},$