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:
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!