Weak RSA

Prerequisites

• Kali Linux.
• First, we are given a download link and a password for the ZIP file. After downloading and opening it, we find the following files.

Understanding the challenge

We appear to have a public key and a message. Decrypting the message should give us the flag.

How does RSA encryption work?

RSA encryption uses very large prime numbers. It relies on a calculation being easy in one direction but extremely difficult in reverse. For example, if you were told that 701,111 is the product of two prime numbers, could you work out which two numbers they are? Even with a calculator or computer, most of us would not know where to begin, let alone find the answer. Turning the calculation around makes it much easier.

Key generation

RSA keys are generated as follows:

• Choose two prime numbers, p and q.
  • For security, p and q should be selected randomly. They should be similar in size, but differ in length by a few digits to make factoring harder.
• Calculate n = pq.
  • n is used as the modulus for both the public and private keys.

Decryption

We will use RsaCtfTool to decrypt the message. First, clone the tool:

git clone https://github.com/Ganapati/RsaCtfTool

Put the encrypted flag, the public key, and the tool in the same directory, as shown below.

Run:

./RsaCtfTool/RsaCtfTool.py --publickey key.pub --uncipherfile flag.enc

This gives us the flag.