> For the complete documentation index, see [llms.txt](https://ctf.zeyu2001.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://ctf.zeyu2001.com/2021/zh3ro-ctf-v2/1n_jection.md).

# 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
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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, and the optional `goal` query parameter:

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

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

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.