Challenge: Now that I have encrypted my flag with a new math function I was just researching I can know share it with my friend Cantor and no one will know how to read it except us!
For this we are given 2 files. The first one is a .txt containing the following:
flag = 4036872197130975885183239290191447112180924008343518098638033545 53589334888434826276681036070738374179472139222629149731482620127084778 4737584016
And the other one is a python file:
from sage.all import sqrt, floor
from secret import flag
def getTriNumber(n):
return n * (n + 1) // 2 # Ensure integer division
def pair(n1, n2):
S = n1 + n2
return getTriNumber(S) + n2
def pair_array(arr):
result = []
for i in range(0, len(arr), 2):
result.append(pair(arr[i], arr[i + 1]))
return result
def pad_to_power_of_two(arr):
result = arr
n = len(result)
while (n & (n - 1)) != 0:
result.append(0)
n += 1
return result
flag = [ord(f) for f in flag]
flag = pad_to_power_of_two(flag)
temp = flag
for i in range(6):
temp = pair_array(temp)
print("Encoded:", temp)
Lets start by analizing what it does.
First of all the variable containing the flag is converted to ASCII (example: “flag”->[102, 108, 97, 103]) and then pad_to_power_of_two() is called. This function just adds zeros to the right until the length is a power of 2. For example if it was [1,2,3] (length 3) it would convert it to [1,2,3,0] (lenght 4 = 2²).
flag = [ord(f) for f in flag]
flag = pad_to_power_of_two(flag)
def pad_to_power_of_two(arr):
result = arr
n = len(result)
while (n & (n - 1)) != 0:
result.append(0)
n += 1
return result
Then the variable is passed into pair_array() 6 times. This function iterates over the temp variable and and passes to the function pair() two consecutive numbers.
temp = flag
for i in range(6):
temp = pair_array(temp)
def pair_array(arr):
result = []
for i in range(0, len(arr), 2):
result.append(pair(arr[i], arr[i + 1]))
return result
Lets forget about the function pair() and dive deep into pair_array(), if we had this list [2, 4, 5, 7] what pair_array() would do is:
result = []
result.append(pair(2, 4))
result.append(pair(5, 7))
So we are converting 2 concatenate numbers into 1 and doing that 6 times. If we were to do it again with our example:
result = []
a = pair(2, 4)
b = pair(5, 7)
result.append(pair(a, b))
Like this we can convert 4 numbers into just one. Now lets look at how that unique number is calculated. First we add both numbers (S = n1 + n2) and we return the triangular number of S + n2.
def getTriNumber(n):
return n * (n + 1) // 2 # Ensure integer division
def pair(n1, n2):
S = n1 + n2
return getTriNumber(S) + n2
This is the Cantor pairing function (the statement gives us a hint). So lets take a look at how our list would work with this pairing.
result = []
result.append(pair(2, 4))
result.append(pair(5, 7))
print(f"Result: {result}")
-> Result: [25, 85]
result = []
result.append(pair(25, 85))
print(f"Result: {result}")
-> Result: [6190]
And that is how we converted 4 numbers -> 2 numbers -> 1 number, iterating 2 times.
There is a formula to reverse this pairing and this is how it looks in Python.
from sympy import *
def getTriNumber(n):
return n * (n + 1) // 2
def unpair(z):
w = floor((sqrt(8*z + 1) - 1) / 2)
t = getTriNumber(w)
n2 = z - t
n1 = w - n2
return n1, n2
def unpair_array(arr):
result = []
for z in arr:
a, b = unpair(z)
result.append(a)
result.append(b)
return result
Now with all this we just need to call unpair_array() 6 times with the number we were provided and we will have the flag.
from sympy import *
def getTriNumber(n):
return n * (n + 1) // 2
def unpair(z):
w = floor((sqrt(8*z + 1) - 1) / 2)
t = getTriNumber(w)
n2 = z - t
n1 = w - n2
return n1, n2
def unpair_array(arr):
result = []
for z in arr:
a, b = unpair(z)
result.append(a)
result.append(b)
return result
# Step 1: the number we were given
encoded_value = [4036872197130975885183239290191447112180924008343518098638033545535893348884348262766810360707383741794721392226291497314826201270847784737584016]
# Step 2: unpair 6 times
temp = encoded_value
for _ in range(6):
temp = unpair_array(temp)
# Step 3: to eliminate the zeros that were added when the
# length was converted to the power of 2 (this is not neccesary)
while temp and temp[-1] == 0:
temp.pop()
# Step 4: convert to text
flag = ''.join(chr(x) for x in temp)
print("Decoded flag:", flag)
Dawg{1_pr3f3r_4ppl3s_t0_pa1rs_4nyw2y5}