PlaidCTF 2015: Curious

This challenge was a bit different from Strength in the sense that the moduli of the intercepted ciphertexts were different. There is an attack called Wiener’s attack which is based on the following theorem:

Wiener’s theorem
Let N = pq with q<p<2p and d < \frac{1}{3} N^{\frac{1}{4}}. Given  N and e with ed = 1 (\bmod \phi (N)) , the attacker can efficiently recover d.

So by running the attack on all the instances, we hope that at least one satisfies the constraints in Wiener's theorem. After running implementation here on a few of the instances, we find the exponent

e = \texttt{23974584842546960047080386914966001070087596246662608796022581200084145416583}

and can recover


which translates to ‘ flag_S0Y0UKN0WW13N3R$4TT4CK!’

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s