Primary Knowledge - Crypto

Task

Surrounded by an untamed forest and the serene waters of the Primus river, your sole objective is surviving for 24 hours. Yet, survival is far from guaranteed as the area is full of Rattlesnakes, Spiders and Alligators and the weather fluctuates unpredictably, shifting from scorching heat to torrential downpours with each passing hour. Threat is compounded by the existence of a virtual circle which shrinks every minute that passes. Anything caught beyond its bounds, is consumed by flames, leaving only ashes in its wake. As the time sleeps away, you need to prioritise your actions secure your surviving tools. Every decision becomes a matter of life and death. Will you focus on securing a shelter to sleep, protect yourself against the dangers of the wilderness, or seek out means of navigating the Primus’ waters?

Solution

We get two files source.py and output.txt. The first one contains the flag encryption code:

import math
from Crypto.Util.number import getPrime, bytes_to_long
from secret import FLAG

m = bytes_to_long(FLAG)

n = math.prod([getPrime(1024) for _ in range(2**0)])
e = 0x10001
c = pow(m, e, n)

with open('output.txt', 'w') as f:
    f.write(f'{n = }\n')
    f.write(f'{e = }\n')
    f.write(f'{c = }\n')

The content of the Python script indicates that ciphertext is calculated in the standard for the RSA algorithm way. Let's take a look at the output.txt file. In this file, we can find the values of N, e, and c. The last one is a ciphertext and contains an encrypted flag. The values contained in this file are as follows:

n = 144595784022187052238125262458232959109987136704231245881870735843030914418780422519197073054193003090872912033596512666042758783502695953159051463566278382720140120749528617388336646147072604310690631290350467553484062369903150007357049541933018919332888376075574412714397536728967816658337874664379646535347
e = 65537
c = 15114190905253542247495696649766224943647565245575793033722173362381895081574269185793855569028304967185492350704248662115269163914175084627211079781200695659317523835901228170250632843476020488370822347715086086989906717932813405479321939826364601353394090531331666739056025477042690259429336665430591623215

The value of e is a standard one. Let's make sure the value of N is a composite number. We can check it using factor.db:

The given value of N turns out to be a prime number. RSA security is based on the problem of factoring N and therefore N should never be a prime number. Knowing that N is a prime number, we should be able to calculate the private key and decrypt the message.

We know from the way the RSA algorithm works that N should be computed as:

$$N=p\cdot q$$

where p and q are two different prime numbers. In the RSA algorithm, the value of Euler's totient function $φ(N)$ is:

$$φ(N)= φ(p)\cdotφ(q)=(p-1)\cdot(q-1)$$

The private key $d$ must meet the following assumptions:

$$d\cdot e = 1 \;mod\;φ(N)$$

Message decryption is performed using the private key in the following way:

$$m = c^{d}\;mod\;N$$

Let's explain how it works Euler’s totient function works. For example $φ(a)$ is equal:

$$φ(a)=a-1$$

and $φ(a\cdot b)$ can be computed as:

$$φ(a\cdot b)=φ(a)\cdotφ(b)=(a-1)(b-1)$$

φ(N) calculation in the RSA algorithm is based on this transformation. Based on the above formulas and knowing that N is a prime number then:

$$N=N\cdot 1$$

So we can calculate the Euler’s Totient Function for prime N as:

$$φ(N)=(N-1)$$

After substituting into the formula we get:

$$e\cdot d=1\;mod\;φ(N) =1\;mod\;(N-1)$$

It follows that we can calculate the public key as:

$$d=\dfrac{1}{e}\;mod\;(N-1)= e^{-1}\;mod\;(N-1)$$

We will use that transformation to calculate the private key. A simple Python script that calculates the value of the private key and decrypts the message:

from Cryptodome.Util.number import long_to_bytes

n = 144595784022187052238125262458232959109987136704231245881870735843030914418780422519197073054193003090872912033596512666042758783502695953159051463566278382720140120749528617388336646147072604310690631290350467553484062369903150007357049541933018919332888376075574412714397536728967816658337874664379646535347
e = 65537
c = 15114190905253542247495696649766224943647565245575793033722173362381895081574269185793855569028304967185492350704248662115269163914175084627211079781200695659317523835901228170250632843476020488370822347715086086989906717932813405479321939826364601353394090531331666739056025477042690259429336665430591623215

l = n-1 
d = pow(e,-1,l)
m = pow(c, d,n)
print(long_to_bytes(m))

After executing the script, we receive a flag.

Flag:

HTB{0h_d4mn_4ny7h1ng_r41s3d_t0_0_1s_1!!!}