POSTS

My first CTF: 'Decrypting RSA'

I rushed back to my room and, once again, started going through Vivek Ramachandran’s tutorial videos. This had become a norm for me. Everytime I watched him speak with elegance and style, I was filled with hope and amazement. I have curiousity; and, Vivek’s videos seem to provide just the right amount of guidance that I have always craved for.

It was 6:00pm and I glanced at my phone. I was about to reach for my phone, when it started ringing. It was Riyaz on the other side, and I was filled with respect for him. He called me just on time, as was promised earlier that day. I had questions that were troubling me, and he seemed to have answers to all my queries. And, that’s when he mentions about Nullcon’s CTF challenge that was to be held tonight. I was already aware of this upcoming challenge, but Riyaz’s recommendation filled me with new energy. I decided to play for “the flag” inspite of the fact that I was travelling tonight.

I rushed for my fitness class at 8:00pm, as that’s one thing I cannot miss willingly. It has always helped me to unwind my day in the most uplifting way. After a sweaty workout, I returned to my room.

Still an hour to go. I started packing my bags.

When I thought I was almost done, I checked the clock. It was already 20 minutes past 10. Bam!!! I grabbed my laptop and logged in to the site. It was time to taste a new experience. The challenge was on, and I said to myself, “let’s capture the flag”!

All challenges looked doable and daunting at the same time. I felt overwhelmed. I took a pause, and contemplated the consequences. I decided to not let it go in vain. I must break at least one seemingly daunting challenge. That’s when I decided to “Decrypt RSA”.

Except the term “RSA”, I wasn’t familiar with any of the RSA intricacies. Moreover, few hours from now, I must leave for the airport. But, before I board the plane, I wanted to solve this puzzle. I mustered all the courage and plunged in.

To start with, this is what I had:

The content of the encrypt.txt file somewhat looked Chinese to me:

And, I had no clue what to do with the remaining two “.key” files.

In minutes, I was frantically searching over the internet, and reading voraciously. I started getting a hang of RSA. I felt I was close. I was very close to cracking the case. I was almost done. But, Ouch!! The final output looked gibberish. It didn’t look anything like “a flag” for sure.

I said to myself, “I must have missed something”. I went back to the sources and tried understanding the concepts once again. This time, I went a bit slower. What was I missing?

A simple ‘cat’ command on the two ‘.key’ files revealed the following:

After spending some good effort, I was able to decode the public keys. It felt like a first glimpse of success. I was all pumped up and my fingers were moving faster on my keyboard.

I used an online tool to decode my certificates. New set of information popped onto my screen:

It looked daunting indeed!!!

Now, in order to make good use of this newly found information, one has to understand the way RSA works. The major portion of my effort was spent on understanding the RSA public-key cryptosystem.

In simple terms, RSA is an asymmetric cryptographic algorithm which is used to encrypt and decrypt messages using two different keys. Yes! We are talking about private and public keys.

An RSA public key is used to encrypt messages, while the corresponding private key is used to decrypt the public-key encrypted message.

  1. The public-private key pairs are generated by choosing two distinct, large, and random prime numbers (say, p and q).
  2. Modulus (say, n) is calculated as the product of the chosen prime numbers, i.e., n = (p * q)
  3. Calculate the value of following expression: f(n) = (p-1)(q-1)
  4. Choose a public key exponent (say, e) such that:
    • 1 < e < f(n)
    • e and f(n) share no factors other than 1, i.e., gcd(e, f(n)) = 1
  5. Compute the private key exponent (say, d). [If you are wondering “how?”, just be curious and do not lose hope, yet.]

The security of RSA is based on keeping p and q secret. One interesting observation to keep in mind is that gcd(p, q) is always 1 if p and q are prime.

What if a prime number has been re-used between two different RSA public keys? In this case, it would be easy to derive the secret private key. And, once we have the private key, we could start decrypting the secret messages.

I hope I haven’t confused you enough! Taking our current example into consideration, let’s see the process of breaking the RSA encryption, in action. I am using python and a few online resources to do the required calculations.

Here we go…

Feed the values of n, d and e to RSA calculator:

Lastly, convert the hexadecimal output to ASCII value.

Challenge Solved!!!