# 1n\_jection

## Problem

COVID: \*exists\*\
vaccine jokes: \*challenge\_name\*

## Solution

We are given the source code and the output:

```python
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:

```python
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.

```python
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}$$.

![](/files/XYhwUFhJeXlIefY2aYe0)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://ctf.zeyu2001.com/2021/zh3ro-ctf-v2/1n_jection.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.