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}.

Last updated