SekaiCTF2026

TL; DR#

在期末周的间隙打了 SekaiCTF, ~~作为Leo/need吃~~ 看到 STAGE OF SEKAI 的时候还是很惊喜的）

oneline6ryp7o#

how hard can six seven be

assert __import__('re').match('SEKAI{[67]{67}}$',flag:=input()) and not int.from_bytes(flag.encode())%~(6+~7)**67

python

模数

~{(6+~7)**67} = 2^67 - 1

python

令最小为 "SEKAI{" + "6" * 67 + "}"

从 base 往上搜索，从低位往上每轮从 6 加到 7 ，然后算增量能否得出即可

M = 2**67 - 1

base = "SEKAI{" + "6" * 67 + "}"
target = (-int.from_bytes(base.encode())) % M

body = ""
for i in range(67):
    bit_position = (8 * (67 - i)) % 67
    body += "7" if (target >> bit_position) & 1 else "6"

flag = f"SEKAI{{{body}}}"

assert __import__('re').match('SEKAI{[67]{67}}$', flag)
assert not int.from_bytes(flag.encode()) % ~(6 + ~7) ** 67

print(flag)

# SEKAI{6777676667666666677676776776777766777777777776777767777776677666666}

python

orbital-strike#

An orbital strike is an attack directed at a planetary surface from a weapon system stationed in space (orbit).

from Crypto.Util.number import getPrime, getRandomRange
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad

FLAG = open('flag.txt','rb').read()

def lcg(a,b,p,x):
    while 1: yield (x := (a*x+next(b)) % p)

P, p = getPrime(256), getPrime(0x137)
X, A, B, a, b = [getRandomRange(0,m) for m in (P,P,p,p,p)]

# what's better than one lcg? TWO lcgs!
moons = lcg(a,iter([b]*14),p,B)
planets = lcg(A,moons,P,X)
orbit = [next(planets) for _ in range(14)]
star = AES.new(X.to_bytes(32),AES.MODE_ECB).encrypt(pad(FLAG,16)).hex()

print(f"{orbit = }")
print(f"{star = }")

双重 LCG 第一眼想到了今年 karmalCTF 的 RBG 系列

先用参数 a, b, p, B 生成 moons ，再在模 P 下用一次 LCG 混淆 moons，得到外层 orbit 要求恢复内层的planets 种子 X，解密 FLAG

代数结构梳理#

moons

m_i\equiv am_{i−1}+b\mod p

LCG 增量层是常数 b

planets

x_i\equiv Ax_{i-1}+m_i\mod P

我们知道 $[x_1,\cdots,x_{14}]$ 要去恢复 $x_0$

变量太多，先消元

$M_i=m_i-m_{i-1}\to M_i\equiv aM_{i-1}\mod p$

$D_i\equiv x_i-x_{i-1}\to D_i\equiv AD_{i-1}+M_i \mod P$

syzygy#

结合这里的变量命名和线性系统关系，找到了如下的一个处理思路

syzygy定理是什么 ↗

化用本题中，这里模 p P 下的线性关系可以如此整理：先进行差分，再

$H=\begin{bmatrix}D_0 & D_1 & \cdots & D_{10}\\ D_1 & D_2 & \cdots & D_{11}\\ D_2 & D_3 & \cdots & D_{12}\end{bmatrix}$

找 $r=(r_0,r_1,\dots,r_{10}) \to Hr=0$

那么满足 $r_0D_0+r_1D_1+\cdots+r_{10}D_{10}=0\quad r_0D_1+r_1D_2+\cdots+r_{10}D_{11}=0 \quad r_0D_2+r_1D_3+\cdots+r_{10}D_{12}=0$

带入

\sum r_iM_{i+1}=\sum r_i(D_{i+1}-AD_{i})=0\mod P

而 $M_{i+1}\equiv aM_{i}\to M_i\equiv a^iM_0 \mod p$ 而一般 $M_0$ 不会整除 p ，那么我们针对规约的 $r_i$ ，得到了一组

$\sum r_{j}a^{j}\equiv 0 \mod p$ 从而建立一个 $f_{r}(T)=\sum r_{j}T^{j}$ 多取一组结果做 Resultant ，GCD 即可恢复 p, 恢复 p 后再对多项式做一个 GCD 即可恢复公共根 a ;

此时我们可以精确地针对 $M_i$ 进行建模了

后续先考虑一个一个类似的思路，我们用 syzygy 恢复内层后，再考虑外层的差分 $S_i=D_i-D_{i-1}$ 再 $S_i=AS_{i-1}+L_i\mod P\to L_i=M_i-M_{i-1} \mod p$

这里就发现， $L_i$ 相关的差分，还涉及到模 p 下的关系，Lift 处理比较麻烦。

回看我们已有的数据， $r_i$ 获取了相关 $M_i$ 的信息，又因为 $M_{i}\equiv aM_{i+1}\mod p$

展开 $M_{i+1}-aM_i-pn_i=0$ ，针对 $v=(M_0,M_1,\dots,M_{12},n_0,n_1,\dots,n_{11})$ 利用方程组 $\sum_j r_jM_{j+1}=0$

$\sum_j r_jM_{j+2}=0$

$M_{i+1}-aM_i-pn_i=0$ 进行规约，即可简单地恢复 $M_i$ ，再一个 $R_i=D_i-M_i$ 那么就 $R_iD_{j-1}-R_jD_{i-1}\equiv0\pmod P$ 恢复 P，求逆元恢复 A，然后逆推 X 即可

SEKAI{orbital_strike_like_miku_miku_beam!!!}#!/usr/bin/env sage
from sage.all import *

from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad

orbit = [
    46157012221654917396851254347154820393060391878580715960476654689260395468184,
    36926194633341127588542680684095293820802193681748458943524916140809713523560,
    16005201943847263206512436577001283414470030273089746675203830598137794555134,
    28937919714389596084610407023450127584695575606301484773390370819366639643218,
    11459012353705334109041842799942754581703065868230253271729711591416155557180,
    31030059279554219046464541926833857543445131889728181065565033726460506326840,
    20987315604501021667042879662101693092441980938033961081037347214532349371248,
    76741461130245451493723909055453557280102065396647043801270629949855565452326,
    84258885183671683674472390974667571532577240974449641001706593550302243268268,
    59535034089467707172052245359810812420431903279354584714432674122159502991956,
    7115679899033391144975170596669540596311296590450661546000723388170577963715,
    35572951991838484594163260879328705523576344587262461128887804475450813563036,
    85569022704397114858282741078883377190544624744955636482627379979792474136036,
    5047270986830280372910174287287823507537624765267582560460157826800286170460,
]
star = bytes.fromhex(
    "1664ff83cbca2643b357bcdc8c3d6e1548615a18cec73e734a82e163b32a9b0c367c61bab01140a04ac8eda8b007d1d6"
)

def max_bits(row):
    return max(abs(ZZ(x)).nbits() for x in row)

def recover_short_syzygies(D):
    H = Matrix(ZZ, [D[:11], D[1:12], D[2:13]])
    rels = [list(r) for r in H.right_kernel_matrix().LLL().rows()]
    short = [r for r in rels if max_bits(r) <= 96]
    if len(short) < 2:
        raise RuntimeError("not enough short syzygies")
    return rels, short

def recover_inner_modulus_and_multiplier(short):
    R = PolynomialRing(ZZ, "T")
    T = R.gen()
    polys = [R(sum(ZZ(c) * T**i for i, c in enumerate(rel))) for rel in short]

    g = ZZ(0)
    for i in range(len(polys)):
        for j in range(i + 1, len(polys)):
            res = abs(ZZ(polys[i].resultant(polys[j])))
            if res:
                g = res if g == 0 else gcd(g, res)

    large_primes = [ZZ(q) for q, _ in factor(g) if ZZ(q).nbits() > 300 and is_prime(q)]
    if not large_primes:
        raise RuntimeError("resultant gcd did not expose the 311-bit prime")
    p = max(large_primes, key=lambda q: q.nbits())

    Rp = PolynomialRing(GF(p), "T")
    gp = Rp(polys[0])
    for poly in polys[1:]:
        gp = gcd(gp, Rp(poly))
    gp = gp.monic()
    if gp.degree() != 1:
        raise RuntimeError(f"expected a linear gcd over GF(p), got degree {gp.degree()}")
    a = ZZ(-gp[0])
    return p, a

def recover_inner_differences(D, short, p, a):
    # Variables are E_1..E_13 and quotient witnesses n_1..n_12 for
    # E_{i+1} - a*E_i = p*n_i.
    rows = []
    for rel in short:
        row = [ZZ(0)] * 25
        for k, c in enumerate(rel):
            row[k + 1] = ZZ(c)
        rows.append(row)

        row = [ZZ(0)] * 25
        for k, c in enumerate(rel):
            row[k + 2] = ZZ(c)
        rows.append(row)

    for i in range(12):
        row = [ZZ(0)] * 25
        row[i + 1] = 1
        row[i] = -a
        row[13 + i] = -p
        rows.append(row)

    reduced = Matrix(ZZ, rows).right_kernel_matrix().LLL()
    for basis_row in reduced.rows():
        base = [ZZ(x) for x in basis_row[:13]]
        for sign in (1, -1):
            E = [sign * x for x in base]
            if not any(E) or not all(-p < x < p for x in E):
                continue
            if not all((E[i + 1] - a * E[i]) % p == 0 for i in range(12)):
                continue

            g = ZZ(0)
            for i in range(1, 13):
                for j in range(i + 1, 13):
                    val = (D[i] - E[i]) * D[j - 1] - (D[j] - E[j]) * D[i - 1]
                    if val:
                        g = abs(val) if g == 0 else gcd(g, abs(val))

            if g.nbits() == 256 and is_prime(g) and max(orbit) < g < 2**256:
                return E, g

    raise RuntimeError("could not identify the inner difference vector and outer modulus")

def recover_outer_multiplier(D, E, P):
    vals = []
    for i in range(1, 13):
        vals.append(((D[i] - E[i]) * inverse_mod(D[i - 1], P)) % P)
    if len(set(vals)) != 1:
        raise RuntimeError("outer multiplier candidates disagree")
    return ZZ(vals[0])

def decrypt_flag(p, a, P, A, E):
    x1, x2 = ZZ(orbit[0]), ZZ(orbit[1])
    y2_mod_p = (x2 - A * x1) % P
    e1_residue = (inverse_mod(a, p) * E[1]) % p

    for E1 in (ZZ(e1_residue), ZZ(e1_residue) - p):
        y1_mod_p = (y2_mod_p - E1) % P
        X = ((x1 - y1_mod_p) * inverse_mod(A, P)) % P
        try:
            flag = unpad(AES.new(int(X).to_bytes(32, "big"), AES.MODE_ECB).decrypt(star), 16)
        except ValueError:
            continue

        # Verify the recovered key/state against the first outer recurrence.
        if (A * X + y1_mod_p) % P == x1:
            return X, flag

    raise RuntimeError("AES decryption failed for both E1 lifts")

def main():
    D = [ZZ(orbit[i + 1]) - ZZ(orbit[i]) for i in range(len(orbit) - 1)]
    rels, short = recover_short_syzygies(D)
    print("[+] ZZ kernel basis max coefficient bits:", [max_bits(r) for r in rels])
    print("[+] using short syzygies:", [max_bits(r) for r in short])

    p, a = recover_inner_modulus_and_multiplier(short)
    print("[+] p =", p)
    print("[+] a =", a)

    E, P = recover_inner_differences(D, short, p, a)
    A = recover_outer_multiplier(D, E, P)
    print("[+] P =", P)
    print("[+] A =", A)

    X, flag = decrypt_flag(p, a, P, A, E)
    print("[+] X =", X)
    print("[+] flag =", flag.decode())

if __name__ == "__main__":
    main()
# SEKAI{orbital_strike_like_miku_miku_beam!!!}

python

iihash#

Fast hash is good hash. A secret seed makes it even better, right?

import random
import signal

signal.alarm(600)
import xxhash

MIN_PAYLOAD_LEN = 256
TARGET_DIGEST = b"Give me the flag"


class XXH3Challenge:
    def __init__(self):
        self.seed = random.getrandbits(64)

    def _read_hex_data(self, prompt: str) -> bytes:
        try:
            hex_str = input(prompt).strip()
            return bytes.fromhex(hex_str)
        except ValueError:
            print("[-] Invalid hex format.")
            return b""

    def hash_mode(self):
        data = self._read_hex_data("[*] Enter data (hex): ")
        if not data:
            return
        if len(data) <= MIN_PAYLOAD_LEN:
            print(
                f"[-] Data length must be strictly greater than {MIN_PAYLOAD_LEN} bytes."
            )
            return

        h = xxhash.xxh3_128(data, seed=self.seed).hexdigest()
        print(f"[+] Hash: {h}")

    def flag_mode(self):
        data = self._read_hex_data("[*] Enter data (hex): ")
        if not data:
            return
        if len(data) <= MIN_PAYLOAD_LEN:
            print(
                f"[-] Payload length must be strictly greater than {MIN_PAYLOAD_LEN} bytes."
            )
            return

        if xxhash.xxh3_128(data, seed=self.seed).digest() == TARGET_DIGEST:
            print("[+] Target verified.", open("flag.txt").read())
            exit()
        else:
            print("[-] Verification failed. Digest does not match target.")

    def run(self):
        while True:
            print("  1. Hash")
            print("  2. Get Flag")
            print("  3. Exit")
            choice = input("> ").strip()
            if choice == "1":
                self.hash_mode()
            elif choice == "2":
                self.flag_mode()
            elif choice == "3":
                print("[*] Goodbye.")
                break
            else:
                print("[-] Invalid choice.")


if __name__ == "__main__":
    challenge = XXH3Challenge()
    challenge.run()

python

##needle-in-a-multivariate-sekai

TL; DR#

oneline6ryp7o#

orbital-strike#

代数结构梳理#

syzygy#

iihash#

*apbq-rsa-iv#