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

\texttt{0x666c61675f53305930554b4e30575731334e33522434545434434b21},

which translates to ‘ flag_S0Y0UKN0WW13N3R$4TT4CK!’

Advertisements

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s