[Tokyo Westerns/MMA CTF 2nd 2016] – Twin Primes, ESPer

Here is my solution idea for Twin Primes and ESPer, two crypto challenges in Tokyo Westerns/MMA CTF 2nd 2016.

[Twin Primes]

Link: OfficialMirror

Look at the “encrypt.py” file, we know that the flag was encrypted by RSA cryptosystem twice, first with n1 = p*q and second with n2 = (p+2)*(q+2). By doing a simple math, we know p+q = (n2 – n1 -4)/2 and p*q = n1, so that we can get p and q by solving a simple quadratic equation “find two numbers when know their sum and product.”

[ESPer]

 nc cry1.chal.ctf.westerns.tokyo 37992 

After connecting and bypassing the boring proof_of_work, the server will generate a RSA private key, and let us choose to encrypt, decrypt, see about or exit. Choose About to know what they want us to do and how it works.


============================= About ===============================
You are very good ESPer, so that you can change any local variable
value to 2048 bit random integer.

You should specify the ESP string as the line number and variables'
name to change separated by colon.

For example, if the source code is below and your input is "2:x",
the line 2 works the same as "x = rand(2 ** 2048); puts x". So the
output is random number.
+---+-------------------------------------------------------------------------+
| 1| x = 3 |
| 2| puts x |
+---+-------------------------------------------------------------------------+
Encryption Source code is here.
+---+-------------------------------------------------------------------------+
| 1| n, e = read_publickey(ARGV[0]) |
| 2| print "Message m: " |
| 3| STDOUT.flush |
| 4| m = STDIN.gets.to_i |
| 5| c = encrypt(m, e, n) |
| 6| puts "Encrypted: #{c}" |
| 7| STDOUT.flush |
+---+-------------------------------------------------------------------------+

Decryption Source code is here
+---+-------------------------------------------------------------------------+
| 1| p, q, dp, dq, qinvp = read_privkey(ARGV[0]) |
| 2| print "Encrypted Message c: " |
| 3| STDOUT.flush |
| 4| c = STDIN.gets.to_i |
| 5| m1 = decrypt(c, dp, p) |
| 6| m2 = decrypt(c, dq, q) |
| 7| m = merge(m1, m2, p, q, qinvp) |
| 8| puts "Decrypted: #{m}" |
| 9| STDOUT.flush |
+---+-------------------------------------------------------------------------+

As it describes, we can overwrite any variable to a random 2048 bit integer. My first thought is change e, and use Wiener attack to solve it, but it failed because they don’t print e out 😥

But luckily, there is a simple way to have p and q. Because the decryption is based on RSA-CRT, and we can control message c, so what would happen if we change m1 and/or m2 to force the server print wrong m? If we input c =1 and change m2, then m = random + hq; force it to do more, we can recover q by compute gcd(result1 -1, result2 -1), and do it again with m1 we got p! With p and q we have all things to decrypt the flag!

The server is still alive, so you can do it yourself! Good luck!

#The flag is TWCTF{I_don’t_Lik3_ESPer_problems!}

[0CTF 2016 Quals] – equation (Crypto 2 pts)

After 48 hours “fighting”, our team CLGT-meepwn was ranked 12th. Here is my idea for solution of a 2-point cryptography task – equation.
We was given a zip file contain a “mask” RSA private key photo, and a encoded flag.

Screenshot 2016-03-15 at 04.50.02

Instead of trying to retype the private key (or using some OCR tools), I recognize that there is a private key which was hidden in the photo. Use binwalk to extract it.
Screenshot 2016-03-15 at 04.35.42
Based on the format of normal RSA private key, we can recover something from the given key: some LSBs of q, dp, dq and qinv.

CodeCogsEqn

CodeCogsEqn (1)

CodeCogsEqn (2)

If we multiple the second equation with exponent e, it becomes:

CodeCogsEqn (3)

From above equation and assuming that e = 65537 (default value), we know k(q – 1). We also know q is prime number, so q – 1 is an even number. Try to factorize k(q – 1) and note that k < e, we can recover q. Do this again with p or using the “coefficient” qinv, we recover p.

Having p and q, now we easily decrypt the flag.

The flag is 0ctf{Keep_ca1m_and_s01ve_the_RSA_Eeeequati0n!!!}.