Quantum Safe — Hackthebox Writeup

6 min readJun 28, 2022

Challenge Description

I heard Shor’s algorithm can do all sorts of nasty things to RSA, so I’ve decided to be super modern and protect my flag with cool new maffs!

This is a cryptography challenge. Given the encoded file, and the source code for the algorithm to encode.

The secret will be looped, and for each character, will be get the order, by using ord() function. Then, with 2 random integers from 0–100, will be multiplied by 3 x 3 matrix, and then, will be added by r.

Walkthrough

The hard thing about this problem is, we don’t know the value of ‘r’, and for each character, the other number will be random. To solve this, we must see how the multiplication in matrix works :

Matrix multiplication only can be calculated if the total-column of Matrix A is the same as the total-row in Matrix B. The first row of Matrix A will be multiplied to the first column in Matrix B, and it also happened for the second column, and so on.

For example, we can say that [ ord(c), randint(0,100) , randint(0,100) ] as [a b c], and for the encoded result as [x y z]. For r, since we can’t calculate between matrix and scalar, r should have the same dimension with multiplication of [a b c]. we can say r = [r1 r2 r3]

We get 3 equations:

#1 = 47a -49b + 57c + r1 = x

#2 = -77a + 78b -78c + r2 = y

#3 = -85a + 50b + 99c + r3 = z

Okay.. But, we still don’t know many variables, including a and r1 r2 r3. Without all of that, we can’t decrypt the secret. So how we can do that?

Simulation

At this point, I’m pretty stucked to solve this, so, for easy things, I will make my own case’, with a more simple number, and since I already defined all of the numbers together, we can try to figure out how to solve this.

Suppose that:

We can find x,y,z value, by calculated that

We know that r1, r2 and r3 will be constant for each iteration, so it is pretty important for us to know those values first. We also can search ‘a’ value too. The equation will be :

We can make function to output the result of x,y,z with different a, b and c, and generate enc_list with various values:

Suppose that, for searching the r, range value for a, b, c are between 0–10. Because of that, we can search all possible r, by matching the equation with different values.

After we get all dummy r , we can try to calculate each of them.

We will try each r list with values of b and c. We use divmod(), to get the division result, and the remainder. If the division makes any remainder, then, is not a correct value (because a value will always be integer). and, from the three equations, the result of the values must be the same. If those conditions are satisfied, we can add the result to truth_var, and add the r to new_possible_r, because the correct r will always make the same equation for all different x,y,z. without any remainder.

The list_r will be updated, to only obtain new_possible_r that match conditions in previous calculation.

Okay, let’s try to run that, to prove our assumption is true..

After the program is done, we check that the value [1, 2, 3] exists in the rem_list_r. We can make a function to return each value based on the rem_list_r , and we get the ‘a’ value for each enc_list. We can compare, the value is the same with what we initialize! So, in theory, we can find the real secret..

Optimize the calculation

I’ve already experimented. If I just use a plain regular process to calculate, it will take so much time to process it, and it’s not efficient. So, I optimize some parts.

Since I know, the limit of variable ‘b’ and ‘c’ (only 0–100), so I can pre-calculate that, and save it to the list (memoization). For the ‘a’ value, that will be used to find the ‘r’ I assumed that it’s only be ascii. And after I check, the lowest ascii that often been used is 32, and the highest value of ascii is 127. So, I also precalculate that. And also, the result of ‘a’ (r1), (r2), (r3) in find_a_value() will be validate, to only get value > 32 (readable ascii).

The calculation needs a long time to be processed, and something bad could happen in the middle of the calculation. So, I applied a chunk function, to get the small part of list_r. And also, for one iteration that has already been processed, I will backup the list_r value, and truth_var, So, we don’t have to wait long, if we need to stop it. I use pickles to back up the value.