SECCON Finals 14

2026/03/20

#CTF#SECCON

2026年の2月28日から3月1日に開催されたSECCON 14 Domestic FinalsにTPCというチームとして参加して優勝した。 JeopardyではCryptoの問題は4問出題されたが、すべて（ほとんど）AIの力で解けてしまった。

https://x.com/Yu_212_MC/status/2028081612655890609 で

Cryptoは全問upsolveしてwriteupを書きます

と言ったので、約束通りCryptoの問題をすべて人力で解き、理解し、writeupを書いた。KotHの問題についてもできればコンテスト中の全体の最高スコアを越してwriteupを書きたいが、それができるかは不明……。

crypto

back2back

問題

問題文（クリックで展開）

def chall():
    params = Params(l_primes, l_exps, q_primes, q_exps, g0, g1, f)
 
    alice = User(params, role='alice')
    alice_pk = alice.keygen()
    bob = User(params, role='bob')
    bob_pk = bob.keygen()
    print(alice_pk)
    print(bob_pk)
 
    tmp = sha256(str(alice._sk).encode()).digest()
    key = tmp[:16]
    iv = tmp[16:]
    print(f"enc: {AES.new(key, AES.MODE_CBC, iv=iv).encrypt(pad(FLAG, AES.block_size)).hex()}")
 
 
 
    while True:
        bob_pk_list_R = ast.literal_eval(input("bob pk list R: "))
        bob_pk_list_S = ast.literal_eval(input("bob pk list S: "))
 
        bob_pk_R = (bob_pk_list_R[1] * params.i + bob_pk_list_R[0], bob_pk_list_R[3] * params.i + bob_pk_list_R[2])
        bob_pk_S = (bob_pk_list_S[1] * params.i + bob_pk_list_S[0], bob_pk_list_S[3] * params.i + bob_pk_list_S[2])
 
        bob_pk = PublicKey(bob_pk.E, bob_pk.E(bob_pk_R), bob_pk.E(bob_pk_S))
        shared = alice.shared_key(bob_pk)
        print(shared)

入力した $R$ , $S$ に対して $E/\langle m R + n S \rangle$ の $j$ -不変量が何度でも得られ、 $(m, n)$ を求められるとフラグが得られる。

解法

kernelが定数倍されても終域は同じなので、 $m R + n S$ ではなく $R + n m^{-1} S$ だと思うことができる。

$R$ , $S$ として $k$ -torsionとなる点を入力すると、終域の候補は $k$ 通り程度まで絞られ、手元で全探索して $j$ -不変量が一致するものを選ぶことによって $R + n m^{-1} S$ 、つまり $n m^{-1} \bmod k$ が求められる。 $A$ と $B$ が小さい素因数しか持たず、 $E$ の位数は $5 A B = 2^3 3^3 5^4 7^3 11^3 13^3 17^3 19^3 23^3 29^3 31^3 37^3 41^3 43^3 47^3 53^3 59^3 61^3 67^3 71^3 73^3 79^3 83^3 89^3 97^3 101^3 103^3 107^3 109^3 127^3 131^3$ とsmoothな値であることから、これを各素冪因子に対して繰り返すことによって $n m^{-1} \bmod {5 A B}$ が求まる。あとは $m$ と $n$ が小さいことを使って $m$ , $n$ を求める。これにはSageMathのrational_reconstructionを使うと簡単。ソルバは以下の通り。

ソルバ（クリックで展開）

params = Params(l_primes, l_exps, q_primes, q_exps, g0, g1, f)
 
sc = process(["sage", "chall.sage"])
 
sc.recvuntil(b"E = ")
E_alice = EllipticCurve(params.Fp2, [*sage_eval(sc.recvline().decode(), locals={"i": params.i})])
sc.recvuntil(b"R = ")
R_alice = E_alice(*sage_eval(sc.recvline().decode(), locals={"i": params.i}))
sc.recvuntil(b"S = ")
S_alice = E_alice(*sage_eval(sc.recvline().decode(), locals={"i": params.i}))
 
sc.recvuntil(b"E = ")
E_bob = EllipticCurve(params.Fp2, [*sage_eval(sc.recvline().decode(), locals={"i": params.i})])
sc.recvuntil(b"R = ")
R_bob = E_bob(*sage_eval(sc.recvline().decode(), locals={"i": params.i}))
sc.recvuntil(b"S = ")
S_bob = E_bob(*sage_eval(sc.recvline().decode(), locals={"i": params.i}))
 
alice_pk = PublicKey(E_alice, R_alice, S_alice)
bob_pk = PublicKey(E_bob, R_bob, S_bob)
sc.recvuntil(b"enc: ")
flag_enc = bytes.fromhex(sc.recvline().decode())
 
o = params.B * params.A * 5
 
rs = []
ms = []
for p, e in tqdm(factor(o)):
    v = 0
    for j in range(1, e+1):
        t = p**j
 
        r = bob_pk.E.gen(0) * (o // t)
        s = bob_pk.E.gen(1) * (o // t)
 
        sc.sendlineafter(b"R: ", str(r.x().list() + r.y().list()).encode())
        sc.sendlineafter(b"S: ", str(s.x().list() + s.y().list()).encode())
        shared = sage_eval(sc.recvline().decode(), locals={"i": params.i})
        fnd = []
        for i in range(p):
            nv = v + p**(j-1)*i
            R_img = r + nv * s
            if shared == bob_pk.E.isogeny(R_img, algorithm="factored").codomain().j_invariant():
                v = nv
                break
    rs.append(v)
    ms.append(p**e)
v = crt(rs, ms)
v = Zmod(o)(v).rational_reconstruction()
tmp = sha256(str((v.denominator(), v.numerator())).encode()).digest()
key = tmp[:16]
iv = tmp[16:]
flag = AES.new(key, AES.MODE_CBC, iv=iv).decrypt(flag_enc)
print(flag)

crypto

dualrand

問題

問題文（クリックで展開）

#!/usr/bin/env python3
 
import random
 
r1 = random.SystemRandom()
r2 = random.Random(int(input('seed: ')))
 
ans = [r1.randint(0, 0xdeadbeef) for _ in range(80)]
key = [r2.randint(0, 0xdeadbeef) for _ in range(80)]
r1.shuffle(key)
 
print("hint:", [a ^ b for a, b in zip(ans, key)])
if list(map(int, input('answer: ').split(','))) == ans:
    print("flag:", open("flag.txt", "r").read())
else:
    print("nope.")

解法

最初の80個の出力が0になるようなseedを見つけることができれば、他の要素は無視してhintをそのままanswerとして入力することでフラグが得られる。ただし、int_max_str_digitsに引っかかるため、 $10^{4300}$ 未満のseedしか入力できない。

`random.seed` の内部動作

random.seedは、与えられたseedをもとに、init_by_array関数を使って以下のようにして内部状態を初期化する。

init_by_arrayは以下のようになっている。

def seed_num_to_array(num):
    b = []
    while num > 0:
        b.append(num & 0xffffffff)
        num >>= 32
    return b
 
def init_by_array(init_key):
    mt = [0] * 624
    mt[0] = 19650218
    for i in range(1, 624):
        mt[i] = (0x6c078965 * (mt[i-1] ^ (mt[i-1] >> 30)) + i) & 0xffffffff
    i = 1
    j = 0
    for _ in range(max(624, len(init_key))):
        mt[i] = ((mt[i] ^ (mt[i-1] ^ (mt[i-1] >> 30)) * 1664525) + init_key[j] + j) & 0xffffffff
        i += 1
        j += 1
        if i >= 624:
            mt[0] = mt[623]
            i = 1
        if j >= len(init_key):
            j = 0
    for _ in range(623):
        mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1566083941)) - i & 0xffffffff
        i += 1
        if i >= 624:
            mt[0] = mt[623]
            i = 1
    mt[0] = 0x80000000
    return mt
 
def random_seed(seed):
    init_key = seed_num_to_array(seed)
    mt = init_by_array(init_key)
    return mt

seedをinit_by_arrayの第2ループでinit_key[j] + jとして使われる624個の値からなる配列とする。init_keyの長さが624未満であればループする。

このseed配列は、init_by_array直後の内部状態stateから以下のように逆算できる（ただし、これは一意に定まるわけではない）。

MASK = 0xffffffff
 
f = lambda x: (x ^ (x >> 30)) * 0x19660d
g = lambda x: (x ^ (x >> 30)) * 0x5d588b65
h = lambda x: (x >> 1) ^ ((x & 1) * 0x9908b0df)
 
MT = [0] * 624
MT[0] = 19650218
for i in range(1, 624):
    MT[i] = (0x6c078965 * (MT[i - 1] ^ (MT[i - 1] >> 30)) + i) & MASK
 
def ith_seed(state, i):
    if i == 0:
        return -(MT[1] ^ f(MT[0])) & MASK
    if i == 1:
        a = ((state[1] + 1) ^ g(state[623])) & MASK
        b = ((state[2] + 2) ^ g(a)) & MASK
        return (b - MT[2]) & MASK
    if i == 2:
        a = ((state[1] + 1) ^ g(state[623])) & MASK
        b = ((state[2] + 2) ^ g(a)) & MASK
        c = ((state[3] + 3) ^ g(state[2])) & MASK
        return (c - (MT[3] ^ f(b))) & MASK
    if 3 <= i <= 622:
        p = ((state[i] + i) ^ g(state[i-1])) & MASK
        q = ((state[i+1] + i+1) ^ g(state[i])) & MASK
        return (q - (MT[i+1] ^ f(p))) & MASK
    if i == 623:
        a = ((state[1] + 1) ^ g(state[623])) & MASK
        z = ((state[623] + 623) ^ g(state[622])) & MASK
        return (a - f(z)) & MASK

int_max_str_digitsの制限のため、init_keyの長さは446以下である必要がある。ここでは長さを $K=313$ とする（他の長さでも解けるが簡単のため）

stateに関する条件を整理する。twistした後の列の最初の80個の値が0である必要があることと、seedがループする必要があることの2つを式として表すと、

\begin{cases} \mathrm{state}[0] = \texttt{0x80000000} & & \cdots (1) \\ \mathrm{ith\_seed}(\mathrm{state}, i) = \mathrm{ith\_seed}(\mathrm{state}, i+313) & (0 \leq i < 311) & \cdots (2) \\ \mathrm{state}[i+397] \oplus h((\mathrm{state}[i] \mathbin{\&} \texttt{0x80000000}) \mid (\mathrm{state}[i+1] \mathbin{\&} \texttt{0x7fffffff})) = 0 & (0 \leq i < 80) & \cdots (3) \end{cases}

の3つを満たせばよい（前述の通りstateからseedは一意に決まらないため、これは必要条件より少し強い条件を言っている）。

以下の順番でstateを決めていく。

state[0:86]とstate[477:624]を決める
$(3)$ を満たすようにstate[397:477]を決める
$(2)$ を満たすようにstate[312:397]を決める
$(2)$ を満たすようにstate[86:312]を決める

1. `state[0:86]`と`state[477:624]`を決める

まず

state[0] = 0x80000000
state[1:86] = [0] * 85
state[477:624] = [0] * 147

とする。この後に他の値を適切に計算することによってすべての条件を満たすことができるため、state[1:86]とstate[477:624]は任意の値にしてよい。

2. 出力条件から `state[397:477]` を埋める

state[0:81]が確定しているため、 $(3)$ から、

\mathrm{state}[i+397] = h((\mathrm{state}[i] \mathbin{\&} \texttt{0x80000000}) \mid (\mathrm{state}[i+1] \mathbin{\&} \texttt{0x7fffffff})) \qquad (0 \le i < 80)

がそのまま計算できる。

3. 周期条件を後ろ向きに使って `state[312:397]` を埋める

ith_seed(state, i)の通常ケース（ $3 \leq i \leq 622$ ）は、state[i-1], state[i], state[i+1]の3語だけで決まる。したがって、state[i+1], state[i+2]と目標値ith_seed(state, i+1)が分かっていれば、逆向きにstate[i]を1つずつ復元できる。

state[0:86]が確定しているため、 $\mathrm{ith\_seed}(\mathrm{state}, i+1) = \mathrm{ith\_seed}(\mathrm{state}, i-312) \quad (312 \leq i < 397)$ の条件からith_seed(state, i+1)もすでに確定している。

以下のようにして計算できる。

def f_inv(x):
    x = (x * pow(0x19660d, -1, 0x100000000)) & MASK
    return x ^ (x >> 30)
def g_inv(x):
    x = (x * pow(0x5d588b65, -1, 0x100000000)) & MASK
    return x ^ (x >> 30)
def seed_prev(t1, s1, s2, i):
    q = ((s2 + i+1) ^ g(s1)) & MASK
    p = f_inv(((q - t1) & MASK) ^ MT[i+1])
    return g_inv((p ^ (s1 + i)) & MASK)
for i in reversed(range(312, 397)):
    key = ith_seed(state, i-312)
    state[i] = seed_prev(key, state[i+1], state[i+2], i+1)

逆順に計算すると、毎回必要なstate[i+1], state[i+2]が既知なので、一つずつstate[312:397]を求めることができる。

4. 周期条件を前向きに使って `state[86:312]` を埋める

3と同様に、次はstate[i-2], state[i-1]と目標値ith_seed(state, i-1)からstate[i]を求める。

state[397:624]とstate[1]が確定しているため、 $\mathrm{ith\_seed}(\mathrm{state}, i-1) = \mathrm{ith\_seed}(\mathrm{state}, i+312) \quad (86 \leq i < 312)$ の条件からith_seed(state, i-1)もすでに確定している。

以下のようにして計算できる。

def seed_next(t1, s0, s1, i):
    p = ((s1 + i) ^ g(s0)) & MASK
    q = (t1 + (MT[i+1] ^ f(p))) & MASK
    return ((q ^ g(s1)) - (i+1)) & MASK
for i in range(86, 312):
    key = ith_seed(state, i+312)
    state[i] = seed_next(key, state[i-2], state[i-1], i-1)

前から順に計算すると、毎回必要なstate[i-2], state[i-1]が既知なので、state[86:312]までを埋めることができる。

seed の再構成

以上でstateがすべて決まるので、ith_seed(state, i)からinit_key[i]を取り出して実際にrandom.seedに渡すseedを計算する。

seed = 0
for i in range(313):
    x = ith_seed(state, i) - i
    seed += x << (32 * i)

得られるseedは10進3016桁で、int_max_str_digitsの制限に収まる。

この値でrandom.seedすると、最初の80個のgetrandbits(32)がすべて0になる。したがってkeyも80個とも0で、hint = ans ^ keyはそのままansになり、hintをanswerとして返せばフラグが得られる。

ソルバ（クリックで展開）

MASK = 0xffffffff
 
f = lambda x: (x ^ (x >> 30)) * 0x19660d
g = lambda x: (x ^ (x >> 30)) * 0x5d588b65
h = lambda x: (x >> 1) ^ ((x & 1) * 0x9908b0df)
 
MT = [0] * 624
MT[0] = 19650218
for i in range(1, 624):
    MT[i] = (0x6c078965 * (MT[i - 1] ^ (MT[i - 1] >> 30)) + i) & MASK
 
def ith_seed(state, i):
    if i == 0:
        return -(MT[1] ^ f(MT[0])) & MASK
    if i == 1:
        a = ((state[1] + 1) ^ g(state[623])) & MASK
        b = ((state[2] + 2) ^ g(a)) & MASK
        return (b - MT[2]) & MASK
    if i == 2:
        a = ((state[1] + 1) ^ g(state[623])) & MASK
        b = ((state[2] + 2) ^ g(a)) & MASK
        c = ((state[3] + 3) ^ g(state[2])) & MASK
        return (c - (MT[3] ^ f(b))) & MASK
    if 3 <= i <= 622:
        p = ((state[i] + i) ^ g(state[i-1])) & MASK
        q = ((state[i+1] + i+1) ^ g(state[i])) & MASK
        return (q - (MT[i+1] ^ f(p))) & MASK
    if i == 623:
        a = ((state[1] + 1) ^ g(state[623])) & MASK
        z = ((state[623] + 623) ^ g(state[622])) & MASK
        return (a - f(z)) & MASK
 
def f_inv(x):
    x = (x * pow(0x19660d, -1, 0x100000000)) & MASK
    return x ^ (x >> 30)
def g_inv(x):
    x = (x * pow(0x5d588b65, -1, 0x100000000)) & MASK
    return x ^ (x >> 30)
def seed_next(t1, s0, s1, i):
    p = ((s1 + i) ^ g(s0)) & MASK
    q = (t1 + (MT[i+1] ^ f(p))) & MASK
    return ((q ^ g(s1)) - (i+1)) & MASK
def seed_prev(t1, s1, s2, i):
    q = ((s2 + i+1) ^ g(s1)) & MASK
    p = f_inv(((q - t1) & MASK) ^ MT[i+1])
    return g_inv((p ^ (s1 + i)) & MASK)
 
state = [0] * 624
state[0] = 0x80000000
for i in range(397, 477):
    state[i] = h((state[i-397] & 0x80000000) | (state[i-396] & 0x7fffffff))
for i in reversed(range(312, 397)):
    key = ith_seed(state, i-312)
    state[i] = seed_prev(key, state[i+1], state[i+2], i+1)
for i in range(86, 312):
    key = ith_seed(state, i+312)
    state[i] = seed_next(key, state[i-2], state[i-1], i-1)
 
seed = 0
for i in range(313):
    x = ith_seed(state, i) - i
    seed += x << (32 * i)
 
random.seed(seed)
assert all(random.getrandbits(32) == 0 for _ in range(80))

ちなみに、この問題をもうちょっと強化した問題をDreamhackに出題しているのでぜひ解いてみてほしい。

crypto

monologue

問題

問題文（クリックで展開）

def main():
    k = KeyGenerator.KeyPair(gen=True)
 
    while True:
 
        choice = input("1. sign\n2. verify\n3. public key\n4. challenge\n> ")
        if choice == "1":
            m = bytes.fromhex(input("message(hex) > "))
            print(sign(k, m).encode().hex())
        elif choice == "2":
            m = bytes.fromhex(input("message(hex) > "))
            sig = bytes.fromhex(input("signature(hex) > ")).decode()
            print(verify(k, m, sig))
        elif choice == "3":
            print(public_key(k).encode().hex())
        elif choice == "4":
            challenge(k)
            exit()
        else:
            print("invalid choice")
            exit()

解法

import_signatureは以下のように実装されている。 $s$ の次数のチェックなどもなく任意の $r$ と $s$ を受け入れている。

def import_signature(sig: str):
    """
    Import the signature from a string.
    """
    c = 0
    while sig[c] != '\n':
        c += 1
    c += 1
    coeff = []
    nb = ""
    while sig[c] != '\n':
        if sig[c] == "|":
            coeff += [int(nb)]
            nb = ""
        else:
            nb += sig[c]
        c += 1
    coeff += [int(nb)]
    s = Polynomial(N=len(coeff))
    s.coeff = np.array(coeff)
    nb = ""
    c += 3
    while sig[c] != '\n':
        nb += sig[c]
        c += 1
    r = int(nb)
 
    return r, s

署名の検証は以下のように実装されている。

def NTRUNorm(P, Q, mod=(0, 0)):
    """
    Definition of the Centered
    Euclidean Norm
    """
    Pc, Qc = P.coeff, Q.coeff
    if mod[0] != 0 and mod[0]:
        q = abs(mod[0])
        Pc = Pc % q
    if mod[1] != 0 and mod[1]:
        q = abs(mod[1])
        Qc = Qc % q
    res_p = np.sqrt(np.sum(np.square(Pc)) - np.square(np.sum(Pc))/len(Pc))
    res_q = np.sqrt(np.sum(np.square(Qc)) - np.square(np.sum(Qc))/len(Qc))
    return np.sqrt(res_p**2 + res_q**2)
 
def Verifying(D, r, s, N_bound, k: KeyPair):
    """
    Verify if the document D was signed by the
    key k and boundary N_bound.
    """
    m = H(D+r.to_bytes(10, 'big'), k.N)
    b = NTRUNorm(s, s.star_multiply(k.pub) - m, (0, k.q))
    if b < N_bound:
        return True
    return False

$s$ として次数0の多項式 $128$ を与えると、Pcは[128]に、Qcはs.star_multiply(k.pub)の部分は% qで消えて-mとなる。 mはDとrから計算されたsha1ハッシュのhexを整数に変換したもので、各係数は $[48,57] \cup [97,102]$ という狭い範囲に含まれる。

このことから、NTRUNormで計算される値は非常に小さくなり、実際に実験すると $400$ 程度とN_boundより小さくなる。よって、\n128\n\n\n0\nをhexにした値、0a3132380a0a0a300aをchallengeに投げるとフラグが得られる。

crypto

pairs again

問題

問題文（クリックで展開）

# https://gist.github.com/maple3142/8933b70e6011043b65849314563fba55
 
# BLS12-381
# https://hackmd.io/@benjaminion/bls12-381
x = var("x")
q = 0x1A0111EA397FE69A4B1BA7B6434BACD764774B84F38512BF6730D2A0F6B0F6241EABFFFEB153FFFFB9FEFFFFFFFFAAAB
r = 0x73EDA753299D7D483339D80809A1D80553BDA402FFFE5BFEFFFFFFFF00000001
Fq = GF(q)
Fq2 = GF(q ^ 2, "i", x ^ 2 + 1)
i = Fq2.gen()
u6 = 1 / (1 + i)
b = 4
 
 
E1 = EllipticCurve(Fq, (0, b))
E2 = EllipticCurve(Fq2, (0, b / u6))
G1 = E1.lift_x(
    3685416753713387016781088315183077757961620795782546409894578378688607592378376318836054947676345821548104185464507
)
G2 = E2.lift_x(
    352701069587466618187139116011060144890029952792775240219908644239793785735715026873347600343865175952761926303160
    + i
    * 3059144344244213709971259814753781636986470325476647558659373206291635324768958432433509563104347017837885763365758
)
assert r * G1 == 0
assert r * G2 == 0
 
 
u, i = polygens(Fq, "u,i")
mod = ((1 + i) * u ^ 6 - 1).sylvester_matrix(i ^ 2 + 1, i).det().univariate_polynomial()
Fq12 = GF(q ^ 12, "u", mod)
u = Fq12.gen()
E3 = EllipticCurve(Fq12, [0, 4])
i_in_fq12 = Fq2.modulus().change_ring(ZZ)(polygen(Fq12)).roots(multiplicities=False)[1]
assert i_in_fq12**2 + 1 == 0
 
 
def fp2_to_fq12(el):
    return el.polynomial()(i_in_fq12)
 
 
G1x = E3(G1)
G2x = E3(u ^ 2 * fp2_to_fq12(G2[0]), u ^ 3 * fp2_to_fq12(G2[1]))
assert r * G1x == 0
assert r * G2x == 0
 
# ------------------------------
 
import ast
import signal
 
with open("flag.txt", "r") as f:
    FLAG = f.read()
 
def pairing(P, Q):
    return (P._miller_(Q, 1337 * r)) ^ ((q ^ 12 - 1) // r)
 
signal.alarm(30)
 
Px = int(input("Px: "))
Py = int(input("Py: "))
P = E3(Fq(Px), Fq(Py))
Q = randrange(1, r) * G2x
t = pairing(P, Q)
assert t != 1
print("pairing(P, Q) =", t)
 
Qx = Fq12(ast.literal_eval(input("guess Qx: ")))
Qy = Fq12(ast.literal_eval(input("guess Qy: ")))
Q_ = E3(Qx, Qy)
 
if t == pairing(P, Q_):
    print(FLAG)

ペアリングの問題。Pが与えられ、pairing(P, Q) == pairing(P, Q_)となるようなQ_をもとめることができればフラグが得られる。

解法

以下、P.miller_(Q, m)を $f_{m,P}(Q)$ と表す。pairing関数は $f_{1337 r,P}(Q)^{e}$ と表せる。（ここで、 $e = \frac{q^{12} - 1}{r}$ ）

Miller 関数は $f_{m n,P} = {f_{m,P}}^n \cdot f_{n,m P}$ が常に成り立つことを使って式変形を進めると、

\begin{align*} f_{1337 r,P}(Q)^{e} &= (f_{1337,P}(Q)^{r} \cdot f_{r,1337 P}(Q))^{e} \\ &= f_{1337,P}(Q)^{r e} \cdot f_{r,1337 P}(Q)^{e} \\ &= f_{1337,P}(Q)^{q^{12}-1} \cdot f_{r,1337 P}(Q)^{e} \\ &= f_{r,1337 P}(Q)^{e} \end{align*}

となる。ここで、 $P$ として11-torsionとなるような点をとる。すると、除数公式 $\mathrm{div}(f_{n,A}) = n[A]-[nA]-(n-1)[O]$ と $r P = P$ を用いれば、 $u = \frac{r - 1}{11}$ として、

\begin{align*} \mathrm{div}(f_{r,1337 P}) &= r[1337 P]-[r 1337 P]-(r-1)[O] \\ &= r[1337 P]-[1337 P]-(r-1)[O] \\ &= (r - 1)[1337 P - O] \\ &= u (11[1337 P - O]) \\ \end{align*}

また、

\begin{align*} \mathrm{div}(f_{11,1337 P}) &= 11[1337 P]-[11 1337 P]-(11-1)[O] \\ &= 11[1337 P]-[O]-10[O] \\ &= 11[1337 P - O] \\ \end{align*}

よって、 $\mathrm{div}(f_{r,1337 P}) = u \cdot \mathrm{div}(f_{11,1337 P})$ であり、ここから $f_{r,1337 P}(Q) = c \cdot f_{11,1337 P}(Q)^{u}$ がわかる。また、 $c = 1$ が実験よりわかる。ここから、

\begin{align*} f_{1337 r,P}(Q)^{e} &= f_{11,1337 P}(Q)^{u e} \end{align*}

ここで、 $f_{11,1337 P}$ を $x_Q, y_Q$ の式として表すと、分母が9次、分子が10次の有理関数となる。これを $\frac{m_\mathrm{num}(x_Q, y_Q)}{m_\mathrm{den}(x_Q, y_Q)}$ と表す。

$m_\mathrm{num}(x_Q, y_Q) - \mathrm{pairing}(P, Q) ^ {(u e)^{-1} \bmod r} \cdot m_\mathrm{den}(x_Q, y_Q) \equiv 0 \pmod {q^{12}}$

となるような $Q$ を求めればよい。この式と $y(Q)^2 - x(Q)^3 - 4 \equiv 0 \pmod {q^{12}}$ を連立させて解けば、Q_を求めることができる。

ソルバ（クリックで展開）

Rxy = PolynomialRing(Fq12, names=("X", "Y"))
X, Y = Rxy.gens()
Frac = Rxy.fraction_field()
Xf = Frac(X)
Yf = Frac(Y)
 
def line_eval(Rp, Sp):
    if Rp == -Sp:
        return Xf - Frac(Rp[0])
    x1 = Frac(Rp[0])
    y1 = Frac(Rp[1])
    if Rp != Sp:
        x2 = Frac(Sp[0])
        y2 = Frac(Sp[1])
        lam = (y2 - y1) / (x2 - x1)
    else:
        lam = (Frac(3) * x1 * x1) / (Frac(2) * y1)
    return (Yf - y1) - lam * (Xf - x1)
 
def vert_eval(Tp):
    if Tp.is_zero():
        return Frac(1)
    return Xf - Frac(Tp[0])
 
def miller_symbolic(Pbase, m):
    bits = list(reversed(Integer(m).digits(2)))
    T = Pbase
    f = Frac(1)
    for bit in bits[1:]:
        T2 = Integer(2) * T
        f = f * f * line_eval(T, T) / vert_eval(T2)
        T = T2
        if bit == 1:
            Tp = T + Pbase
            f = f * line_eval(T, Pbase) / vert_eval(Tp)
            T = Tp
    return f
 
P = E3(E1.random_element() * (E1.order() / 121))
u = (r - 1) // 11
exp = ((q ** 12 - 1) // r)
d = pow(u * exp, -1, r)
miller = miller_symbolic(1337 * P, Integer(11))
scale = ((1337 * P)._miller_(G2x, Integer(11))) / pairing(P, G2x)
m_num = miller.numerator()
m_den = miller.denominator()
 
sc = process(["sage", "chal.sage"])
 
sc.sendlineafter(b"Px: ", str(P.x()).encode())
sc.sendlineafter(b"Py: ", str(P.y()).encode())
sc.recvuntil(b" = ")
t = sage_eval(sc.recvline().decode(), locals={"u": Fq12.gen()})
 
target = t ** d
fn1 = m_num - target * m_den
fn2 = Y*Y - X*X*X - 4
fn3 = fn1.resultant(fn2, Y)
 
for xr, _ in fn3.univariate_polynomial().roots():
    for yr in (xr*xr*xr+4).sqrt(all=True):
        assert yr * yr == xr*xr*xr + 4
        if m_den(xr, yr) != 0 and miller(xr, yr) == target:
            Q_ = E3(xr, yr)
            assert t == pairing(P, Q_)
            sc.sendlineafter(b"Qx: ", str(Q_.x().list()).encode())
            sc.sendlineafter(b"Qy: ", str(Q_.y().list()).encode())
            print(sc.recvline())

Writeups

crypto

back2back

問題

解法

dualrand

問題

解法

random.seed の内部動作

1. state[0:86]とstate[477:624]を決める

2. 出力条件から state[397:477] を埋める

3. 周期条件を後ろ向きに使って state[312:397] を埋める

4. 周期条件を前向きに使って state[86:312] を埋める

seed の再構成

monologue

問題

解法

pairs again

問題

解法

`random.seed` の内部動作

1. `state[0:86]`と`state[477:624]`を決める

2. 出力条件から `state[397:477]` を埋める

3. 周期条件を後ろ向きに使って `state[312:397]` を埋める

4. 周期条件を前向きに使って `state[86:312]` を埋める