Writeup – Six Thousand Idle (TJCTF)

This weekend, I participated in TJCTF. This was an enjoyable CTF, with a good variety of challenges. Unfortunately, my lack of focus (specifically, not playing CTF to write fuzzer code and play EVE Online) cost me dearly in terms of points.

I tackled a variety of challenges, including the “six thousand idle” (I don’t have the original name – this was the Google Translate of the Chinese [?] characters presented). This challenge was presented as a single text file, containing a number of public keys as well as ciphertext.

I don’t usually do well in cryptography challenges (read: lol 0pts), so here’s some links which I’m reading to lift my game in this area:

To cut a super long story short:

  • RSA’s public key is key = prime1*prime2
  • RSA’s private key (to decrypt things) is derived from prime1 and prime2. If you know prime1, you can work out prime2.
  • RSA’s security depends on the fact that there’s no efficient way to work out prime1 and prime2. Yes, you can brute force, good luck brute forcing 2^1030 bits of keyspace or whatever it was and then doing primality checks.

The weakness in this particular challenge was that there were a large number of public keys, some of which shared the same prime factors. If for pubkey1 and pubkey2, we can calculate a greatest common divisor (which is fast), we can then derive privkey1 and privkey2, and thus decrypt the messages.

A quick python script was sufficient to do this, giving us the (very large) flag:

motherfucking huge

motherfucking huge

If you read the comments of the script, you’ll notice that where I made my first mistake, of trying to factor the keys individually.

Thankyou to the TJCTF organisers for putting on this set of challenges -I had a lot of fun tackling not just this, but also a number of challenges in the other categories.

See you all at ALICTF on the weekend!

About Norman

Sometimes, I write code. Occasionally, it even works.
This entry was posted in Bards, Computers, Jesting and tagged , , . Bookmark the permalink.

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