zh3r0 CTF V2 | in_jection

zh3ro_ctf_2021 cantor_pairing_function 対関数 pairing_function

#zh3ro_CTF_2021

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

なにやら不思議な関数を戻すやつ

f(x, y) = \frac{(x + y)(x + y + 1)}{2} + y という関数があるけど、これはCantor Pairing Function というらしい。対関数(pairing function) の一つ。

逆関数が定義できて f(x, y) = zとして w = \lfloor \frac{\sqrt{8z + 1} - 1}{2} \rfloor, t = \frac{w^2 + w}{2} とすると

x = z - t, y = w - x らしい

詳しくはwikipedia