TokyoWesterns CTF 4th 2018 Writeup — Part 4

Abdelkader Belcaid
Sep 9, 2018 · 4 min read

09/09/2018 01:33 AM UTC+2

TokyoWesterns CTF 4th 2018 Writeup — Part 4

Here we go again, another Cryptography challenge i got from TokyoWesterns CTF 4th 2018 Plateform during the competition. This challenge needs math that’s why it took me a day to figure out the solution of this problem which i will explain detailed below.

Revolutional Secure Angou — 156pts

Revolutional Secure Angou

Challenge: revolutional-secure-angou.7z

They are 3 files given in this challenge; encryption text flag.encrypted and public key publickey.pem and script ruby generator.rb as generator.

Revolutional Secure Angou files

Let’s read generator and try to understand it because it’s used to encrypt the message which is the flag.

As you see, this is an implementation of OpenSSL in Ruby, we have an exponent e and two prime numbers p and q of 1024bits which is used to generate modulus then public key which is used to encrypt the flag and generate encryption text as flag.encrypted in output.

Accordingly, this is RSA algorithm applied to encrypt the message which is our goal. In order to reach it we have to decrypt flag.encrypted with RSA.

As you know the encryption in RSA requires the public key which means modulus N and public exponent e. We have e as shown in generator script above, let’s extract publickey.pem file in order to find modulus N.

extract the modulus N and the public exponent e from publickey.pem

And as you know the decryption in RSA requires the private key which means modulus N and private exponent d. We have N as shown above, and we have to calculate d. In order to do that we have to calculate the inverse modular of e and Euler’s totient function phi. phi is unknown because to calcul it you need the prime numbers p and q, and these prime numbers are unknown too. And you could not factorize N.

But we have an interesting line in generator.rb script:

It means that:

After a day of analyzing and trying to find a good math solution, here is my last math solution:

Now, let’s multiply the above equation with q.

The modulus N is known and public exponent e is known, so the idea is to bruteforce k until find the prime number q which is devides the modulus N. Then calculate q then calculate phi then the private exponent d then decrypt flag.encrypted by using private key which is modulus N and private exponent d.

Here is my script python i used to automate my math solution and bruteforce k then calculate until decrypt the flag.encrypted and find the flag:

Result:

result of rsa.py script
submitting Revolutional Secure Angou’s flag
Revolutional Secure Angou has been solved

FLAG is: TWCTF{9c10a83c122a9adfe6586f498655016d3267f195}

It was a good challenge and have too much fun especially in mathematic part. Thanks again to TokyoWesterns Team. If you are looking for other parts of my writeup here is the list:

InfoSec Write-ups

A collection of write-ups from the best hackers in the world on topics ranging from bug bounties and CTFs to vulnhub machines, hardware challenges and real life encounters. In a nutshell, we are the largest InfoSec publication on Medium. Maintained by Hackrew

Abdelkader Belcaid

Written by

I'm Bug Bounty Hunter & CTF Player

InfoSec Write-ups

A collection of write-ups from the best hackers in the world on topics ranging from bug bounties and CTFs to vulnhub machines, hardware challenges and real life encounters. In a nutshell, we are the largest InfoSec publication on Medium. Maintained by Hackrew

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade