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
rr
can be expressed as
r=(i+j)(i+j+1)2+jr=\frac{(i+j)(i+j+1)}{2}+j
where
ii
and
jj
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
ii
and
jj
from
rr
, 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)2(r-j)=(i+j)(i+j+1)
Then, we have
i+j=⌊2(rβˆ’j)βŒ‹i+j=\left \lfloor {\sqrt{2(r-j)}}\right \rfloor
I also noticed one other thing. If we start off with some value of
ii
and
jj
, then increment
jj
by
kk
while decrementing
ii
by the same amount, then we have
r=((iβˆ’k)+(j+k))((iβˆ’k)+(j+k)+1)2+(j+k)r=\frac{((i-k)+(j+k))((i-k)+(j+k)+1)}{2}+(j+k)
​
rr
is incremented by the same amount,
kk
.
r=(i+j)(i+j+1)2+j+kr=\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
ii
and
jj
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
Nk\mathbb{N^k}
to
N\mathbb{N}
.
Copy link