1n_jection

# Problem

COVID: *exists* vaccine jokes: *challenge_name*

# Solution

We are given the source code and the output:
1
from secret import flag
2
3
def nk2n(nk):
4
l = len(nk)
5
if l==1:
6
return nk[0]
7
elif l==2:
8
i,j = nk
9
return ((i+j)*(i+j+1))//2 +j
10
return nk2n([nk2n(nk[:l-l//2]), nk2n(nk[l-l//2:])])
11
12
print(nk2n(flag))
13
#2597749519984520018193538914972744028780767067373210633843441892910830749749277631182596420937027368405416666234869030284255514216592219508067528406889067888675964979055810441575553504341722797908073355991646423732420612775191216409926513346494355434293682149298585
Copied!
By studying the code, we can see that this is basically a recursive algorithm that divides the bytestring into two halves at each layer, until the base case where there are either 1 or 2 characters left. We can clearly see that at each layer, the result
$r$
can be expressed as
$r=\frac{(i+j)(i+j+1)}{2}+j$
where
$i$
and
$j$
are the results of calling the function on the lower and upper half of the input respectively. For each layer, if we are able to recover
$i$
and
$j$
from
$r$
, then we would be able to repeat this all the way until the base case, where we would be able to recover the ASCII characters.
Rearranging,
$2(r-j)=(i+j)(i+j+1)$
Then, we have
$i+j=\left \lfloor {\sqrt{2(r-j)}}\right \rfloor$
I also noticed one other thing. If we start off with some value of
$i$
and
$j$
, then increment
$j$
by
$k$
while decrementing
$i$
by the same amount, then we have
$r=\frac{((i-k)+(j+k))((i-k)+(j+k)+1)}{2}+(j+k)$
$r$
is incremented by the same amount,
$k$
.
$r=\frac{(i+j)(i+j+1)}{2}+j+k$
Using this knowledge, I implemented the following:
1
def get_i_j(nk):
2
j = Decimal(1)
3
nk = Decimal(nk)
4
sq = 2 * (nk - j)
5
i_plus_j = int(sq.sqrt())
6
i = i_plus_j - j
7
8
test = ((i+j)*(i+j+1)) // 2 + int(j)
9
gap = nk - test
10
11
if gap < 0:
12
i = abs(gap) - 2
13
j = i_plus_j - i - 1
14
15
else:
16
j = gap + 1
17
i = i_plus_j - j
18
19
assert ((i+j)*(i+j+1))//2 +j == nk
20
return i, j
Copied!
Then, since
$i$
and
$j$
are essentially the outputs of the "previous" layer, we can create a recursive function that terminates at the base case where we have reduced the output to its original ASCII characters.
1
def recover_string(nk):
2
if nk < 200:
3
char = chr(int(nk))
4
print(char, end='')
5
else:
6
i, j = get_i_j(nk)
7
recover_string(i)
8
recover_string(j)
9
10
recover_string(2597749519984520018193538914972744028780767067373210633843441892910830749749277631182596420937027368405416666234869030284255514216592219508067528406889067888675964979055810441575553504341722797908073355991646423732420612775191216409926513346494355434293682149298585)
Copied!
Here's the output. This probably wasn't the intended solution, since the flag talks about a bijection from
$\mathbb{N^k}$
to
$\mathbb{N}$
.