TokyoWesterns CTF 4th 2018 Writeup — Part 4
09/09/2018 01:33 AM UTC+2

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

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.

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.

N = 16809924442712290290403972268146404729136337398387543585587922385691232205208904952456166894756423463681417301476531768597525526095592145907599331332888256802856883222089636138597763209373618772218321592840374842334044137335907260797472710869521753591357268215122104298868917562185292900513866206744431640042086483729385911318269030906569639399362889194207326479627835332258695805485714124959985930862377523511276514446771151440627624648692470758438999548140726103882523526460632932758848850419784646449190855119546581907152400013892131830430363417922752725911748860326944837167427691071306540321213837143845664837111
e = 65537And 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:
q = OpenSSL::BN.new(e).mod_inverse(p)It means that:
q = mod_inverse(p)After a day of analyzing and trying to find a good math solution, here is my last math solution:
q = mod_inverse(p)
q = e ^ (-1) mod p
q * e = 1 mod p
q * e = k * p + 1 # k is multiplierNow, let’s multiply the above equation with q.
q * q * e = q * (k * p + 1)
(q ^ 2) * e = (k * p * q) + q
(q ^ 2) * e = (k * N) + q # N = p * q
((q ^ 2) * e) - q = k * N
q = ((k * N) / e) ^ 2The 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:



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:

