Foreword

I remember the time that we held a capture-the-flag (CTF) competition in our school organization. It was a jeopardy-style and cryptography-focused CTF aimed for beginners.

The Challenge

I had the opportunity to contribute the most difficult and rewarding challenge in the CTF.

The challenge title was "Abandon Ship." The description of the challenge is below:

The crew found a functional spaceship named the GNFS Bonenberger-Krone in the hangar bay. Desperate to escape, they boarded it and tried to make the ship run.

The ship activated but it is asking for confirmation:

-- ACTION REQUIRED -- 520222841197FFC38BB0FBE7A641FE80E3613B93C167D82FD9615CED7A4EAA88535E1F61848A0099A2F5595ED8E37BF67C034F8C0BD2729EC72D895A95A0851897EDD54F4441F

The captain said that they need to decrypt the message so they can override the ship's controls. Can you help the crew escape the moon before everything goes to shambles?

It is deemed difficult for it requires the solver to have fundamental and mathematical knowledge about how RSA works.

The Solution

Context Clues

The first step is to look for context clues. Searching the ship's name, Bonenberger-Krone, in Google yields a critical clue immediately. According to research, RSA-170 was first factored on December 29, 2009, by D. Bonenberger and M. Kroneare. From this, we can assume that the ciphertext in the challenge is encrypted using RSA-170 as well.

RSA Primer (pun intended)

RSA algorithm relies on modular exponentiation based on two large and secret prime numbers. The formula for RSA encryption and decryption is shown below.

Encryption

$$C = M^e (mod\, n)$$

Where:

C - cipher text
M - plain text
e - encoding exponent
n - RSA modulus

The formula above can be represented in Python with the following:

C = pow(M, e, n)

Decryption

$$M = C^d (mod\, n)$$

Where:

M - plaintext
C - cipher text
d - decoding exponent
n - RSA modulus

The formula above can be represented in Python with the following:

M = pow(C, d, n)

Acquiring Co-primes

Before we can play around with the RSA formulas, let us look for the RSA modulus. It is the product of co-primes p and q.

$$n = pq$$

Going back to the challenge, let us take a look at what the discovered co-primes of RSA-170 are. This Wikipedia article conveniently shows them. The co-primes of RSA-170 are:

Brilliant! Now we know the co-primes. Knowing the co-primes of a certain RSA number makes it obsolete. If you know the co-primes of an RSA number, you can easily break anything that is encrypted with it.

Today, most of us are using RSA-2048 in our modern cryptographic systems. I think it will take a while before this RSA number can get broken.

Computing the RSA Modulus

Referring to our formula in the primer, I am using Python to script the math. Here is the code to compute the RSA modulus:

p = 3586420730428501486799804587268520423291459681059978161140231860633948450858040593963
q = 7267029064107019078863797763923946264136137803856996670313708936002281582249587494493

n = p * q

Computing the Totient

Euler's totient, integral to computing the exponents, can be computed using the formula:

$$ϕ(n) = (p - 1)(q - 1)$$

The formula above can be represented in Python (3.8 and above) with the following:

totient = (p - 1) * (q - 1)

Computing the Exponents

Encoding / Public Exponent

To compute an encoding exponent, one must choose a number such that: $$ gcd(e, ϕ(n)) = 1 $$ Commonly, the value of the encoding exponent is 65537. The reason for it being that can be read here. We can assume that the challenge is using the same value.

Decoding / Private Exponent

The formula for computing the decoding exponent is below:

$$ ed = 1 (mod, ϕ(n)) $$

$$ d = \frac{1 (mod, ϕ(n))}{e } $$ $$ d = e^{-1} (mod, ϕ(n)) $$

The formula above can be represented in Python (3.8 and above) with the following:

d = pow(e, -1, totient)

Doing the Math

Now that we have the co-primes, we can begin doing the math behind RSA. Firstly, we have to convert the hexadecimal cipher text in the challenge to decimal. We do this before we can perform mathematical operations around it.

Now, we put all of our RSA formulas together to acquire the plain text!

C = 19343524409524016220259231815381014016321004376119098223218818570283709836730106429805746795102965999398480228385798788102803617233079665199660746205653767550551926785055
totient = (p - 1) * (q - 1)
d = pow(e, -1, totient)
n = p * q

M = pow(C, d, n) # pow(base, power, modulus)
print(M)

The plain text would be a big integer. We then convert that to hexadecimal.

Convert the hexadecimal to ASCII to finally get the flag.

Closing Thoughts

I had a lot of fun in designing this challenge. I learned how RSA fundamentally works and I decided to make a challenge out of that process. We just tackled the decryption part! The encryption is left as an exercise for the reader. 😉

jgrivera.dev