DASCTF2025
Crypto
lost LFSR key
1.flag 是可打印 ASCII，故最高位一定为0，相应c中每个字节的最高位一定就是key
2.把 seed 看成 64 维向量（每一位是 GF(2) 上的变量），那么：
Out = parity(seed & mask)是一个关于种子 64 位的线性函数；seed' = ((seed << 1) | Out)也是线性的；- 所以第 t 步输出
y_t可以写成：y_t = r_t ⋅ S_0其中S_0是初始 64 位种子，r_t是一个 64 维行向量（可以预先算出来，相当于M^T A^t）。
这就是一套 64 个方程、64 个未知数（种子每一位） 的线性方程组，在线性空间 GF(2) 上求解即可
from Crypto.Util.number import long_to_bytes
import numpy as np
mask = 9319439021858903464
c = 8882504877732087312989345828667663333297225833982945014279010438327750150593504327259176959316943362605442206624947923157363187067410478202161873663103506
A = np.zeros((64, 64), dtype=np.uint8)
M = np.zeros(64, dtype=np.uint8)
for j in range(64):
if (mask >> j) & 1:
A[0, j] = 1
M[j] = 1
for k in range(1, 64):
A[k, k-1] = 1
rows = []
r = M.copy()
for t in range(512 + 1):
rows.append(r.copy())
r = (r @ A) % 2
c_bytes = long_to_bytes(c, 64)
A2 = np.zeros((64, 64), dtype=np.uint8)
b2 = np.zeros(64, dtype=np.uint8)
for j in range(64):
A2[j, :] = rows[8*j]
b2[j] = (c_bytes[j] >> 7) & 1
def gf2_solve_with_nullspace(A, b):
A = A.copy().astype(int)
b = b.copy().astype(int)
m, n = A.shape
row = 0
pivot_cols = []
pivcol = [-1] * m
for col in range(n):
pivot = None
for r in range(row, m):
if A[r, col] == 1:
pivot = r
break
if pivot is None:
continue
if pivot != row:
A[[row, pivot]] = A[[pivot, row]]
b[row], b[pivot] = b[pivot], b[row]
pivot_cols.append(col)
pivcol[row] = col
for r in range(m):
if r != row and A[r, col] == 1:
A[r, :] ^= A[row, :]
b[r] ^= b[row]
row += 1
if row == m:
break
rank = row
for r in range(rank, m):
if not A[r].any() and b[r] == 1:
return None, None, None
x = np.zeros(n, dtype=int)
for r in range(rank - 1, -1, -1):
col = pivcol[r]
if col == -1:
continue
s = 0
for j in range(col + 1, n):
s ^= (A[r, j] & x[j])
x[col] = b[r] ^ s
free_cols = [c for c in range(n) if c not in pivot_cols]
null_basis = []
for fc in free_cols:
v = np.zeros(n, dtype=int)
v[fc] = 1
for r in range(rank - 1, -1, -1):
col = pivcol[r]
if col == -1:
continue
s = 0
for j in range(col + 1, n):
s ^= (A[r, j] & v[j])
v[col] = s
null_basis.append(v)
return x, null_basis, rank
x_part, null_basis, rank = gf2_solve_with_nullspace(A2, b2)
def vec_to_seed(v):
s = 0
for i in range(64):
if v[i]:
s |= (1 << i)
return s
base_seed = vec_to_seed(x_part)
seeds = [base_seed]
if null_basis:
seeds.append(base_seed ^ vec_to_seed(null_basis[0]))
def myrng_next(seed):
i = seed & mask
out = 0
while i:
out ^= i & 1
i >>= 1
seed = ((seed << 1) | out) & ((1 << 64) - 1)
return seed, out
def gen_key(seed):
st = seed
key = 0
for _ in range(64*8):
st, bit = myrng_next(st)
key = (key << 1) | bit
return key
def printable(bs):
return all(32 <= b <= 126 for b in bs)
for s in seeds:
key = gen_key(s)
m = c ^ key
flag_inner = long_to_bytes(m, 64)
if printable(flag_inner):
print("seed =", hex(s))
print("inner =", flag_inner)
print("flag = DASCTF{" + flag_inner.decode() + "}")
"""
seed = 0xd4efd8332ee448f1
inner = b'f1nd_th3_hidden_Linear_R3lat1onShip_@nd_th3n_F1nd_My_Lo5t_KEY!!!'
flag = DASCTF{f1nd_th3_hidden_Linear_R3lat1onShip_@nd_th3n_F1nd_My_Lo5t_KEY!!!}
"""MISC
DigitalSignature
计算消息的
MessageHash，对消息进行哈希操作。使用签名数据，结合
MessageHash和Signature，从签名恢复出签名者的地址。通过恢复出的地址构造 flag，这个地址就是要找的 flag。
from web3 import Web3
from eth_account.messages import encode_defunct
def RecoverSigner(Message: str, Signature: str) -> str:
Provider = Web3()
Temp = encode_defunct(text=Message)
Signer = Provider.eth.account.recover_message(Temp, signature=Signature)
return Signer
def GetFlag(SignedMessageHash: str, SignedMessageSignature: str) -> str:
# 使用 MessageHash 和 Signature 恢复签名者地址
Address = RecoverSigner(SignedMessageHash, SignedMessageSignature)
# 构建 flag
return f"DASCTF{{{Address}}}"
# 示例数据
Message = "Find out the signer. Flag is account address that wrapped by DASCTF{}."
Signature = "0x019c4c2968032373cb8e19f13450e93a1abf8658097405cda5489ea22d3779b57815a7e27498057a8c29bcd38f9678b917a887665c1f0d970761cacdd8c41fb61b"
flag = GetFlag(Message, Signature)
print(flag)
# DASCTF{0x2b2D44D5325F0d3550296686BE2a7b5Fecb952cB}