1n_jection

# Problem

COVID: *exists* vaccine jokes: *challenge_name*

# Solution

We are given the source code and the output:
from secret import flag
def nk2n(nk):
l = len(nk)
if l==1:
return nk[0]
elif l==2:
i,j = nk
return ((i+j)*(i+j+1))//2 +j
return nk2n([nk2n(nk[:l-l//2]), nk2n(nk[l-l//2:])])
print(nk2n(flag))
#2597749519984520018193538914972744028780767067373210633843441892910830749749277631182596420937027368405416666234869030284255514216592219508067528406889067888675964979055810441575553504341722797908073355991646423732420612775191216409926513346494355434293682149298585
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:
def get_i_j(nk):
j = Decimal(1)
nk = Decimal(nk)
sq = 2 * (nk - j)
i_plus_j = int(sq.sqrt())
i = i_plus_j - j
test = ((i+j)*(i+j+1)) // 2 + int(j)
gap = nk - test
if gap < 0:
i = abs(gap) - 2
j = i_plus_j - i - 1
else:
j = gap + 1
i = i_plus_j - j
assert ((i+j)*(i+j+1))//2 +j == nk
return i, j
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.
def recover_string(nk):
if nk < 200:
char = chr(int(nk))
print(char, end='')
else:
i, j = get_i_j(nk)
recover_string(i)
recover_string(j)
recover_string(2597749519984520018193538914972744028780767067373210633843441892910830749749277631182596420937027368405416666234869030284255514216592219508067528406889067888675964979055810441575553504341722797908073355991646423732420612775191216409926513346494355434293682149298585)
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}$
.