Sekai CTF Permutation Group Cryptography

Sekai CTF 2024 - Some Trick


Bob and Alice found a futuristic version of opunssl and replaced all their needs for doofy wellmen.

ncat --ssl sometrick.chals.sekai.team 1337
nacl@NaClPC /m/c/U/13945> ncat --ssl sometrick.chals.sekai.team 1337
oPUN_SASS_SASS_l version 4.0.65301948145452297989971584538947390413463913978292170266124541495148077646081
bob says 23365910707507555761796827123403544378712635346042887256237285624214230193940901036273205672421695122491956034272817588948864056165757226907127153422665053683095690662257307989188179934107165122516785135861711119109591769387647528205828028583270207859801122348184198651797970742597327973438362953266460325417
alice says 222300335588888213283202508862211398602290174248292389406051294005095589113859718309049812063610457183606586386560883156166481563215996403666148964009555481886261590599875961057281034223895103574929241960948261073745253899707702272319945173750961685694500844936156409221656308275209563870532814779362137881871
bob says 222688973010813723577185031027249067320731413335083381801227496823970304379579095498511952647053147889517176817189477031735102980421161653437419657849827488221299431541481967418684331158904034587375854723059363010036416814115738854444089240392096171206284945979350566638266254313834119687502753926815714550847
import random
from secrets import randbelow, randbits
from Crypto.Util.number import*
CIPHER_SUITE=65301948145452297989971584538947390413463913978292170266124541495148077646081
b1=23365910707507555761796827123403544378712635346042887256237285624214230193940901036273205672421695122491956034272817588948864056165757226907127153422665053683095690662257307989188179934107165122516785135861711119109591769387647528205828028583270207859801122348184198651797970742597327973438362953266460325417
a1=222300335588888213283202508862211398602290174248292389406051294005095589113859718309049812063610457183606586386560883156166481563215996403666148964009555481886261590599875961057281034223895103574929241960948261073745253899707702272319945173750961685694500844936156409221656308275209563870532814779362137881871
b2=222688973010813723577185031027249067320731413335083381801227496823970304379579095498511952647053147889517176817189477031735102980421161653437419657849827488221299431541481967418684331158904034587375854723059363010036416814115738854444089240392096171206284945979350566638266254313834119687502753926815714550847

random.seed(CIPHER_SUITE)
GSIZE = 8209
GNUM = 79
LIM = GSIZE**GNUM
def gen(n):
    p, i = [0] * n, 0
    for j in random.sample(range(1, n), n - 1):
        p[i], i = j, j
    return tuple(p)

def gexp(g, e):
    res = tuple(g)
    while e:
        if e & 1:
            res = tuple(res[i] for i in g)
        e >>= 1
        g = tuple(g[i] for i in g)
    return res

def enc(k, m, G):
    if not G:
        return m
    mod = len(G[0])
    return gexp(G[0], k % mod)[m % mod] + enc(k // mod, m // mod, G[1:]) * mod

def inverse(perm):
    res = list(perm)
    for i, v in enumerate(perm):
        res[v] = i
    return res

G = [gen(GSIZE) for i in range(GNUM)]

def b8209(v):
    s=[]
    while(v):
        s.append(v%8209)
        v//=8209
    return s

def i8209(res):
    s=0
    for i in res:
        s=s*8209+i
    return s

def dec(k, res, G):
    if(not G):
        return [0]
    mod = len(G[0])
    mm=gexp(G[0], k % mod)
    return dec(k//mod,res[1:],G[1:])+[mm.index(res[0])]

res=b8209(a1)
alice_key=i8209(dec(b1,res,G))
res=b8209(b2)
bob_key=i8209(dec(a1,res,[inverse(i) for i in G]))
def dec2(res,m,G):
    if(not G):
        return m
    mod=len(G[0])
    for i in range(mod):
        g=gexp(G[0],i)
        if(g[m%mod]==res[0]):
            print(i)
            return dec2(res[1:],m//mod,G[1:])+[i]

res=b8209(b1)
rrr=dec2(res,bob_key,G)
FLAG=i8209(rrr)
for i in range(8):
    flag=long_to_bytes(FLAG>>i)
    if(b'SEKAI' in flag):
        print(flag)
#SEKAI{7c124c1b2aebfd9e439ca1c742d26b9577924b5a1823378028c3ed59d7ad92d1}
Back