战绩展示与几道 Crypto 题解

原材料中包含一张战绩截图，但图片没有保留。下面只整理截图旁的三道题目和解法。

题目索引

• Find the lattices
• Cross wires
• Bringing It All Together

Find the lattices

题目分析

题目中的公钥为 (q, h)，私钥为 (f, g)，并满足：

因此存在整数 k 使：

也就是：

向量 (f, g) 是由 (1, h) 和 (0, q) 生成的二维格中的短向量。使用 Gaussian Lattice Reduction 可以恢复它。

解法框架

from Crypto.Util.number import inverse


def gaussian_reduce(v1, v2):
    while True:
        if sum(x * x for x in v2) < sum(x * x for x in v1):
            v1, v2 = v2, v1
        quotient = round(
            sum(a * b for a, b in zip(v1, v2))
            / sum(a * a for a in v1)
        )
        if quotient == 0:
            return v1, v2
        v2 = [b - quotient * a for a, b in zip(v1, v2)]


q, h = public_key
encrypted = ciphertext
(f, g), _ = gaussian_reduce((1, h), (0, q))

a = f * encrypted % q
message = (a * inverse(f, g)) % g
print(message)

原始材料没有保留公钥、密文和最终输出，因此只记录攻击原理。

Cross wires

题目分析

题目使用同一个 N 和自己的私钥 d，先后使用 5 个朋友的公钥指数对 flag 进行 RSA 加密。已知 d 可以先分解 N，再从最后一个朋友开始逆向解密。

已知私钥分解 N

令：

不断取出 k 的 2 因子，并计算：

遇到非平凡因子即可得到 p、q。

from math import gcd

from Crypto.Util.number import long_to_bytes
from sympy import nextprime


N, d = private_key
g = 2
t = 65537 * d - 1

while True:
    while t % 2 == 0:
        candidate = gcd(pow(g, t // 2, N) - 1, N)
        if 1 < candidate < N:
            p = candidate
            q = N // p
            break
        t //= 2
    if "p" in locals():
        break
    g = nextprime(g)
    t = 65537 * d - 1

phi = (p - 1) * (q - 1)
for _, exponent in reversed(friend_keys):
    ciphertext = pow(ciphertext, pow(exponent, -1, phi), N)

print(long_to_bytes(ciphertext).decode())

原始材料中的 private_key、朋友公钥和密文没有完整保留，最终 flag 待补充。

Bringing It All Together

这道题给出 AES-128 的 key、ciphertext 和一份手写 AES 实现。解密流程由四部分组成：

1. 使用 Rijndael 密钥调度生成 11 轮密钥。
2. 从最后一轮开始执行逆行移位和逆字节代换。
3. 执行轮密钥加和逆列混合。
4. 最后一轮跳过逆列混合，拼接状态矩阵得到明文。

核心结构如下：

def decrypt(key, ciphertext):
    round_keys = expand_key(key)
    state = bytes2matrix(ciphertext)
    add_round_key(state, round_keys[N_ROUNDS])

    for index in range(N_ROUNDS - 1, 0, -1):
        inv_shift_rows(state)
        inv_sub_bytes(state)
        add_round_key(state, round_keys[index])
        inv_mix_columns(state)

    inv_shift_rows(state)
    inv_sub_bytes(state)
    add_round_key(state, round_keys[0])
    return matrix2bytes(state)

将题目给出的 key 和 ciphertext 代入即可得到 flag。完整 S-Box 与逆变换实现属于题目附件，原始材料没有记录程序最终输出。