from fpylll import IntegerMatrix, LLL
M = IntegerMatrix(n + 2, n + 1)
for i in range(n): M[i, i] = q          # g_j = (n·e_j, 0)
for i in range(n): M[n, i] = A[i]       # g_a = (a, 0)
for i in range(n): M[n+1, i] = B[i]     # g_b = (b, C)
M[n+1, n] = C
LLL.reduction(M)
# 然后按 5.3 扫描基

from Crypto.Cipher import ChaCha20_Poly1305
cipher = ChaCha20_Poly1305.new(key=key, nonce=nonce)
cipher.update(aad)
pt = cipher.decrypt_and_verify(ct[:-16], ct[-16:])   # 末16字节是 tag

#!/usr/bin/env python3
"""
攻击链：
  FROST nonce 高位泄漏(152/256 bits) -> Hidden Number Problem -> LLL/CVP-embedding
  -> 恢复分片 s1,s2 -> 合成门限私钥 sk(2*s1-s2 mod q)
  -> 重建确定性 BIP340 签名(aux=0) -> SHA256("cold-forge/release/v1"||sig)
  -> ChaCha20-Poly1305 解封 -> flag
"""
import json, hashlib, base64
from fpylll import IntegerMatrix, LLL
from Crypto.Cipher import ChaCha20_Poly1305

# ---------- secp256k1 ----------
q = int("fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141",16)
p = int("fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f",16)
Gx = int("79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798",16)
Gy = int("483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8",16)
G = (Gx, Gy)

def point_add(P, Q):
    if P is None: return Q
    if Q is None: return P
    x1,y1=P; x2,y2=Q
    if x1==x2 and (y1+y2)%p==0: return None
    lam=((3*x1*x1)*pow(2*y1,-1,p) if P==Q else (y2-y1)*pow(x2-x1,-1,p))%p
    x3=(lam*lam-x1-x2)%p
    return (x3,(lam*(x1-x3)-y1)%p)

def point_mul(k, P=G):
    R=None
    for b in bin(k)[2:]:
        R=point_add(R,R)
        if b=='1': R=point_add(R,P)
    return R

def bytes_from_int(x): return x.to_bytes(32,'big')
def tagged_hash(tag,msg):
    th=hashlib.sha256(tag.encode()).digest()
    return hashlib.sha256(th+th+msg).digest()
def has_even_y(P): return P[1]%2==0
def xonly(P): return bytes_from_int(P[0])
def centered(x):
    x%=q
    return x-q if x>q//2 else x

# ---------- Step 1&2: HNP 恢复分片 ----------
DISCARD=104; DRIFT=1<<106

def recover_share(signer, transcripts, lam):
    n=len(transcripts); A=[]; B=[]
    for t in transcripts:
        c=int(t["challenge"],16); z=int(t["z"],16); tm=int(t["nonce_msb"],16)
        A.append((lam*c)%q)                        # a_j = λ·c_j
        B.append((z-tm*(1<<DISCARD))%q)            # b_j = z_j - t_j·2^104
    C=1<<DISCARD
    M=IntegerMatrix(n+2,n+1)
    for i in range(n): M[i,i]=q                    # (n·e_i, 0)
    for i in range(n): M[n,i]=A[i]                 # (a, 0)
    for i in range(n): M[n+1,i]=B[i]               # (b, C)
    M[n+1,n]=C
    LLL.reduction(M)
    cands=set()
    for r in range(M.nrows):
        row=[M[r,c] for c in range(M.ncols)]
        if abs(row[-1])!=C or not all(abs(x)<DRIFT for x in row[:-1]): continue
        for sgn in (+1,-1):                        # LLL 可能给出 ±u
            p0=(B[0]+sgn*row[0])%q
            cands.add((p0*pow(A[0],-1,q))%q)
    for x in cands:
        if all(abs(centered(a*x-b))<DRIFT for a,b in zip(A,B)): return x
    return None

tele=json.load(open("frost_telemetry.json"))
lam={1:int(tele["lagrange_coefficients"]["1"],16),
     2:int(tele["lagrange_coefficients"]["2"],16)}
shares={s:recover_share(s,[t for t in tele["transcripts"] if t["signer"]==s],lam[s])
        for s in (1,2)}
print(f"s1 = {shares[1]:064x}\ns2 = {shares[2]:064x}")

# ---------- Step 3: 合成门限私钥 + 验证 ----------
sk=(lam[1]*shares[1]+lam[2]*shares[2])%q
P=point_mul(sk)
print(f"sk = {sk:064x}")
print("sk·G == group_public:", P==(int(tele["group_public"]["x"],16),
                                    int(tele["group_public"]["y"],16)))

# ---------- Step 4: 确定性 BIP340 签名 ----------
msg=bytes.fromhex(tele["message_hex"])
d0=sk; Pk=point_mul(d0)
d=d0 if has_even_y(Pk) else q-d0
aux=b"\x00"*32
t=bytes(a^b for a,b in zip(bytes_from_int(d),tagged_hash("BIP0340/aux",aux)))
# 关键: nonce preimage 是 t || bytes(P) || m (公钥! 不是私钥)
k0=int.from_bytes(tagged_hash("BIP0340/nonce",t+xonly(Pk)+msg),'big')%q
R=point_mul(k0)
k=k0 if has_even_y(R) else q-k0
e=int.from_bytes(tagged_hash("BIP0340/challenge",xonly(R)+xonly(Pk)+msg),'big')%q
sig=xonly(R)+bytes_from_int((k+e*d)%q)
print("sig =",sig.hex())

# ---------- Step 5: KDF + 解封 ----------
kdf_key=hashlib.sha256(b"cold-forge/release/v1"+sig).digest()
seal=json.load(open("sealed_release.json"))
nonce=base64.b64decode(seal["nonce"]); aad=base64.b64decode(seal["aad"])
ct=base64.b64decode(seal["ciphertext"])
cipher=ChaCha20_Poly1305.new(key=kdf_key,nonce=nonce)
cipher.update(aad)
pt=cipher.decrypt_and_verify(ct[:-16],ct[-16:])    # 末16字节是 Poly1305 tag
print("FLAG:",pt.decode())

F = sample_sparse_ternary(N, df, rng, avoid_zero=True)   # df=7, 系数 ±1，非零
G = sample_sparse_ternary(N, dg, rng)                    # dg=7, 系数 ±1，非零
f = [0]*N; f[0] = 1
f = poly_add(f, [p*x for x in F], N)      # f = 1 + 3*F
g = [p*x for x in G]                      # g = 3*G

#!/usr/bin/env sage
from sage.all import *
import re, ast

N = 127
p = 3
q = 12289
CHUNK = 24

def mod_center(x, mod):
    x %= mod
    if x > mod//2:
        x -= mod
    return x

def poly_mul(a, b, mod=None):
    out = [0]*N
    for i, ai in enumerate(a):
        if ai == 0: continue
        for j, bj in enumerate(b):
            if bj == 0: continue
            out[(i+j) % N] += ai * bj
    if mod is not None:
        out = [x % mod for x in out]
    return out

def decrypt(c, f):
    t = poly_mul(f, c, q)
    lifted = [mod_center(x, q) for x in t]
    return [x % p for x in lifted]

def blocks_to_bytes(blocks):
    raw = bytearray()
    for blk in blocks:
        v = 0
        for coeff in reversed(blk):
            v = v*3 + (coeff % 3)
        raw.extend(int(v).to_bytes(CHUNK, 'little'))
    if len(raw) < 2:
        raise ValueError("Missing length prefix")
    size = int.from_bytes(raw[:2], 'big')
    return bytes(raw[2:2+size])

def is_sparse(poly, nonzero_count, allowed_vals):
    if len(poly) != N:
        return False
    cnt = 0
    for x in poly:
        if x != 0:
            cnt += 1
            if x not in allowed_vals:
                return False
    return cnt == nonzero_count

def recover_candidates(B):
    Bred = B.LLL()
    candidates = []
    for row in Bred:
        # 尝试第二部分作为 f，如果不行则尝试第一部分
        for block in [row[N:], row[:N]]:
            for sign in (1, -1):
                f_cand = [sign * block[i] for i in range(N)]
                # 检查 f = 1 + 3F
                if abs(f_cand[0]) != 1:
                    continue
                ok = True
                for i in range(1, N):
                    if f_cand[i] not in (-3, 0, 3):
                        ok = False
                        break
                if not ok:
                    continue
                if sum(1 for x in f_cand if x) != 8:
                    continue
                # 验证 g = f*h mod q 是否稀疏
                g = poly_mul(f_cand, h, q)
                g_centered = [mod_center(x, q) for x in g]
                if not is_sparse(g_centered, 7, (-3, 0, 3)):
                    continue
                if f_cand not in candidates:
                    candidates.append(f_cand)
    return candidates

# 读取公钥
with open("public_key.txt", "r") as f:
    pub_data = f.read()
match = re.search(r"h\s*=\s*(
$$
.*?
$$
)\s*", pub_data, re.DOTALL)
h = ast.literal_eval(match.group(1))
assert len(h) == N

# 读取密文
with open("output.txt", "r") as f:
    out_data = f.read()
match = re.search(r"ciphertexts\s*=\s*(
$$
.*
$$
)\s*", out_data, re.DOTALL)
ciphertexts = ast.literal_eval(match.group(1))
print(f"[+] Loaded {len(ciphertexts)} ciphertext blocks")

# 构造循环矩阵 H
H = matrix(ZZ, N, N)
for i in range(N):
    for j in range(N):
        H[i, j] = h[(j - i) % N]

I = identity_matrix(ZZ, N)
Z = zero_matrix(ZZ, N, N)

candidates = []
# 尝试两种格基
print("[*] Trying lattice B = [[qI, H], [0, I]] ...")
B = block_matrix(ZZ, [[q*I, H], [Z, I]])
candidates = recover_candidates(B)

if not candidates:
    print("[*] Trying lattice B = [[qI, 0], [H, I]] ...")
    B = block_matrix(ZZ, [[q*I, Z], [H, I]])
    candidates = recover_candidates(B)

if not candidates:
    # 使用 BKZ 作为后备
    print("[*] Trying BKZ (block size 20) ...")
    Bbkz = B.BKZ(block_size=20)
    # 简化检查
    for row in Bbkz:
        for block in [row[N:], row[:N]]:
            for sign in (1, -1):
                f_cand = [sign * block[i] for i in range(N)]
                # ... 同前面检查
                # (省略完整代码，见完整脚本)
                pass

if not candidates:
    raise RuntimeError("No candidate f found.")

print(f"[+] Found {len(candidates)} candidate(s).")

for idx, f in enumerate(candidates):
    print(f"[*] Testing candidate #{idx+1} ...")
    blocks = []
    for c in ciphertexts:
        blocks.append(decrypt(c, f))
    try:
        plain = blocks_to_bytes(blocks)
        if plain.startswith(b"flag{"):
            print("[+] Flag found!")
            print(plain.decode())
            exit(0)
    except:
        continue