题目背景
本文是对强网杯2025题目“PolyEncryption”的详细分析与逆向过程。题目核心为一个由C#、Java、Python混合编写的自定义加密算法。本文将详细阐述逆向分析思路，并提供最终的纯Python解密脚本。
分析思路
整体解题思路分为四个阶段：
阶段一：各层代码解密
首先对题目提供的混淆和加密后的各层源码（C#、Java、Python）进行初步解密。此阶段主要通过逆向核心的polyencrypt.dll并分析其解密逻辑来完成，得到了可读的源码。
阶段二：AI辅助分析
使用Cursor等AI编程助手，根据解密得到的源码文件（saw.cs、saw.java、saw.py），自动为代码生成详细注释。随后，引导AI基于注释推理出在不同轮次（rr=0,1,2,3）下的数据流，从而理解算法的整体结构。
阶段三：调试与细节补全
初步根据数据流编写解密脚本后，发现解密失败。为解决细节问题，采取了以下调试手段：
- 对
polyencrypt.dll中的关键函数进行Patch。
- 修改
saw.python脚本，增加详细的日志输出。
- 修改
Hack.java，记录关键方法的调用信息。
- 构建包含调试信息的Docker环境进行动态分析。
通过对比调试日志与算法逻辑，最终锁定了所有实现细节。
阶段四：最终算法实现与还原
根据调试结果，完整还原出名为“PolyEnc”的加密算法，并编写出对应的解密脚本。该算法是一种类似AES结构的分组密码，涉及多轮迭代的S盒替换、列混合、行移位和轮密钥加操作。
加密算法Python实现
以下是该算法的完整纯Python实现，包含加密与解密功能：
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
PolyEnc 纯Python实现 - 清晰版本
不使用中间变量，直接实现加密算法
"""
import struct
# ============================================================================
# S-box (来自 saw.py)
# ============================================================================
SBOX = (
0x9b, 0xac, 0x16, 0x92, 0x5d, 0x9c, 0x1f, 0xed, 0xf8, 0x52, 0x18, 0xc4, 0xd9, 0x59, 0xa0, 0x82,
0x3c, 0x88, 0x69, 0x4a, 0x5a, 0xf6, 0x34, 0xc1, 0xba, 0x27, 0xec, 0x23, 0x10, 0x51, 0x1, 0xe5,
... # 此处为完整的256字节S盒，实际代码中已省略
)
# 构建逆S-box
INV_SBOX = [0] * 256
for i in range(256):
INV_SBOX[SBOX[i]] = i
INV_SBOX = tuple(INV_SBOX)
# ============================================================================
# AES 标准函数
# ============================================================================
def xtime(a):
"""AES xtime: GF(2^8) 乘 2"""
return (((a << 1) ^ 0x1B) & 0xFF) if (a & 0x80) else (a << 1)
def mix_column(col):
"""
AES MixColumns 标准实现
输入: [a0, a1, a2, a3] (4字节)
输出: [b0, b1, b2, b3]
"""
a0, a1, a2, a3 = col
xor_all = a0 ^ a1 ^ a2 ^ a3
b0 = a0 ^ xor_all ^ xtime(a0 ^ a1)
b1 = a1 ^ xor_all ^ xtime(a1 ^ a2)
b2 = a2 ^ xor_all ^ xtime(a2 ^ a3)
b3 = a3 ^ xor_all ^ xtime(a3 ^ a0)
return [b0, b1, b2, b3]
def apply_sbox_to_u32(value):
"""对32位整数应用S-box (小端序)"""
bytes_le = struct.pack("<I", value)
sboxed = bytes([SBOX[b] for b in bytes_le])
return struct.unpack("<I", sboxed)[0]
def rol(value, shift):
"""32位循环左移"""
value &= 0xFFFFFFFF
return ((value << shift) | (value >> (32 - shift))) & 0xFFFFFFFF
def gf_mult(a, b):
"""GF(2^8) 乘法"""
p = 0
for _ in range(8):
if b & 1:
p ^= a
hi_bit_set = a & 0x80
a = (a << 1) & 0xFF
if hi_bit_set:
a ^= 0x1B
b >>= 1
return p
def inv_mix_column(col):
"""
AES 逆 MixColumns 实现
输入: [b0, b1, b2, b3] (4字节)
输出: [a0, a1, a2, a3]
使用矩阵: [0x0E, 0x0B, 0x0D, 0x09]
"""
b0, b1, b2, b3 = col
a0 = gf_mult(0x0E, b0) ^ gf_mult(0x0B, b1) ^ gf_mult(0x0D, b2) ^ gf_mult(0x09, b3)
a1 = gf_mult(0x09, b0) ^ gf_mult(0x0E, b1) ^ gf_mult(0x0B, b2) ^ gf_mult(0x0D, b3)
a2 = gf_mult(0x0D, b0) ^ gf_mult(0x09, b1) ^ gf_mult(0x0E, b2) ^ gf_mult(0x0B, b3)
a3 = gf_mult(0x0B, b0) ^ gf_mult(0x0D, b1) ^ gf_mult(0x09, b2) ^ gf_mult(0x0E, b3)
return [a0, a1, a2, a3]
def apply_inv_sbox_to_u32(value):
"""对32位整数应用逆S-box (小端序)"""
bytes_le = struct.pack("<I", value)
inv_sboxed = bytes([INV_SBOX[b] for b in bytes_le])
return struct.unpack("<I", inv_sboxed)[0]
# ============================================================================
# PolyEnc 加密器
# ============================================================================
class PolyEnc:
def __init__(self):
"""初始化加密器"""
# 轮密钥 (10个，对应 Round 2, 4, 6, 8, 10, 12, 14, 16, 18, 20)
self.round_keys = [3207972492, 1190065579, 4165979424, 2693353696, 3628337899,
1707638109, 1003779598, 2653425729, 795752593, 2469382657,
0]
# 初始密钥状态
self.initial_key = [2427014626, # s[1] - 初始魔数
1166827919, # s[2] - 初始魔数
1240047111, # s[3] - 初始魔数
1038097261 # s[4] - 初始魔数
]
def encrypt(self, plaintext_bytes, verbose=False):
"""
加密16字节明文
算法流程:
- Round 0: 初始化
- Round 1-21: 奇数轮(SubBytes+MixColumns) + 偶数轮(AddRoundKey)
- Round 22: 输出
"""
if len(plaintext_bytes) != 16:
raise ValueError("Input must be 16 bytes")
# 将明文转为4个32位整数 (大端序)
state = list(struct.unpack('>4I', plaintext_bytes))
# 复制初始密钥
key = self.initial_key.copy()
# 轮密钥索引
key_index = 0
if verbose:
print(f"【初始状态】")
print(f" state = {[hex(s) for s in state]}")
print(f" key = {[hex(k) for k in key]}")
# Round 1-21: 主加密循环
# Round 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21 (奇数轮): SubBytes + MixColumns
# Round 2, 4, 6, 8, 10, 12, 14, 16, 18, 20 (偶数轮): ShiftRows + AddRoundKey
for rr in range(1, 23):
if rr % 2 == 1: # 奇数轮: SubBytes + MixColumns
state = self._odd_round(state, key, rr, verbose)
else: # 偶数轮: ShiftRows + AddRoundKey
state, key, key_index = self._even_round(state, key, key_index, rr, verbose)
final_state = state
# 返回密文 (大端序)
return struct.pack('>4I', *final_state)
def _odd_round(self, state, key, rr, verbose):
"""
奇数轮: SubBytes + MixColumns
返回: 16 字节数组 (4x4 矩阵，按行存储)
同时更新密钥状态 s[2], s[3], s[4]:
- s[2] = B ^ A'
- s[3] = C ^ B ^ A'
- s[4] = D ^ C ^ B ^ A'
"""
if verbose:
print(f"\n【Round {rr}】奇数轮 - SubBytes + MixColumns")
print(f" 输入 state = {[hex(s) for s in state]}")
print(f" 输入 key = {[hex(k) for k in key]}")
# 1. 密钥更新 (奇数轮)
if rr == 1:
# Round 1: 密钥保持初始值，不变
pass
else:
# Round 3, 5, 7, ..., 21: 更新 s[2], s[3], s[4]
A_prime = key[0] # 上一个偶数轮更新后的 s[1]
B = key[1]
C = key[2]
D = key[3]
# 密钥级联更新
key[1] = (B ^ A_prime) & 0xFFFFFFFF # s[2] = B ^ A'
key[2] = (C ^ B ^ A_prime) & 0xFFFFFFFF # s[3] = C ^ B ^ A'
key[3] = (D ^ C ^ B ^ A_prime) & 0xFFFFFFFF # s[4] = D ^ C ^ B ^ A'
if verbose:
print(f" 密钥更新:")
print(f" A' = {hex(A_prime)}")
print(f" s[2] = B ^ A' = {hex(key[1])}")
print(f" s[3] = C ^ B ^ A' = {hex(key[2])}")
print(f" s[4] = D ^ C ^ B ^ A' = {hex(key[3])}")
# 2. SubBytes: 对 state 的每个32位整数应用S-box
sboxed = [apply_sbox_to_u32(s) for s in state]
if verbose:
print(f" SubBytes = {[hex(s) for s in sboxed]}")
# 3. MixColumns: 对每个 32位整数拆分成 4字节，MixColumns 后得到 16字节
# 结果按倒序排列（从 Docker 日志观察到）
mixed_bytes = []
for val in sboxed: # 倒序处理
# 拆分成4字节 (大端序)
bytes_be = struct.unpack('4B', struct.pack('>I', val))
# MixColumns
mixed_col = mix_column(list(bytes_be))
mixed_bytes.extend(mixed_col)
if verbose:
print(f" MixColumns 16字节: {[hex(b) for b in mixed_bytes]}")
# 显示为 4x4 矩阵
print(f" MixColumns 4x4矩阵 (按列):")
for row in range(4):
print(f" row{row}: {[hex(mixed_bytes[col*4 + row]) for col in range(4)]}")
return mixed_bytes
def _even_round(self, state_bytes, key, key_index, rr, verbose):
"""
偶数轮: ShiftRows + 字节打包 + AddRoundKey
输入: 16 字节数组 (从奇数轮的 MixColumns 输出)
输出: 4 个 32位整数
1. ShiftRows: 对 4x4 矩阵按对角线重排
2. 字节打包: 每 4 字节打包成一个 32位整数
3. AddRoundKey: state ^= key
4. 密钥更新: s[1] = A ^ sbox(rol(D, 8)) ^ round_key[i]
"""
if verbose:
print(f"\n【Round {rr}】偶数轮 - ShiftRows + AddRoundKey")
print(f" 输入 16字节: {[hex(b) for b in state_bytes]}")
print(f" 输入 key = {[hex(k) for k in key]}")
# 1. ShiftRows: 标准 AES ShiftRows（按行存储）
# 输入: state_bytes 按列存储 [col0_row0-3, col1_row0-3, col2_row0-3, col3_row0-3]
# 需要先转换为按行存储，然后 ShiftRows，最后按列打包
# 标准 ShiftRows 索引（按行存储）:
# col0: 0, 5, 10, 15
# col1: 1, 6, 11, 12
# col2: 2, 7, 8, 13
# col3: 3, 4, 9, 14
# 将按列存储转换为按行存储
# state_bytes[0..3] = col0, state_bytes[4..7] = col1, ...
# 转换为 row0 = [0,4,8,12], row1 = [1,5,9,13], ...
row_based = []
for row in range(4):
for col in range(4):
row_based.append(state_bytes[col * 4 + row])
# ShiftRows 索引（倒序，因为 state 要倒序）
shiftrows_indices = [
[3, 4, 9, 14], # col3 (倒序第0个)
[2, 7, 8, 13], # col2 (倒序第1个)
[1, 6, 11, 12], # col1 (倒序第2个)
[0, 5, 10, 15] # col0 (倒序第3个)
]
shifted_state = []
for indices in shiftrows_indices:
# 从 row_based 按索引取4个字节，打包成32位整数
val = (row_based[indices[0]] << 24) | (row_based[indices[1]] << 16) | \
(row_based[indices[2]] << 8) | row_based[indices[3]]
shifted_state.append(val)
if verbose:
print(f" ShiftRows + 打包:")
for col in range(4):
idx0 = 0*4 + col
idx1 = 1*4 + ((col + 1) % 4)
idx2 = 2*4 + ((col + 2) % 4)
idx3 = 3*4 + ((col + 3) % 4)
print(f" state[{col}] = [{hex(state_bytes[idx0])}, {hex(state_bytes[idx1])}, "
f"{hex(state_bytes[idx2])}, {hex(state_bytes[idx3])}] = {hex(shifted_state[col])}")
# 2. AddRoundKey: state ^= key
shifted_state = shifted_state[::-1]
new_state = [(shifted_state[i] ^ key[i]) & 0xFFFFFFFF for i in range(4)]
if verbose:
print(f" AddRoundKey (state ^= key):")
for i in range(4):
print(f" state[{i}] = {hex(shifted_state[i])} ^ {hex(key[i])} = {hex(new_state[i])}")
# 3. 密钥更新: s[1] = A ^ sbox(rol(D, 8)) ^ round_key[i]
A = key[0]
D = key[3]
# rol(D, 8) - 循环左移8位
rotated = rol(D, 8)
# sbox(rotated)
sboxed = apply_sbox_to_u32(rotated)
# A' = A ^ sboxed ^ round_key[i]
round_key = self.round_keys[key_index]
A_prime = (A ^ sboxed ^ round_key) & 0xFFFFFFFF
key[0] = A_prime
key_index += 1
if verbose:
print(f" 密钥更新:")
print(f" rol(s[4], 8) = {hex(rotated)}")
print(f" sbox(rotated) = {hex(sboxed)}")
print(f" round_key[{key_index-1}] = {hex(round_key)}")
print(f" s[1] = {hex(A)} ^ {hex(sboxed)} ^ {hex(round_key)} = {hex(A_prime)}")
return new_state, key, key_index
def decrypt(self, ciphertext_bytes, verbose=False):
"""
解密16字节密文
算法流程:
1. 先正向生成所有轮的密钥状态
2. 从 Round 22 逆向到 Round 1
"""
if len(ciphertext_bytes) != 16:
raise ValueError("Input must be 16 bytes")
# 1. 正向生成所有轮密钥状态
if verbose:
print(f"\n【生成轮密钥】")
key_states = self._generate_all_round_keys()
if verbose:
print(f"生成了 {len(key_states)} 组轮密钥")
for rr in sorted(key_states.keys())[:5]: # 只显示前5个
print(f" Round {rr}: {[hex(k) for k in key_states[rr]]}")
print(f" ...")
# 2. 将密文转为4个32位整数 (大端序)
state = list(struct.unpack('>4I', ciphertext_bytes))
if verbose:
print(f"\n【解密开始】")
print(f" 密文 (bytes): {ciphertext_bytes.hex().upper()}")
print(f" 密文 (u32): {[hex(s) for s in state]}")
# 3. 逆向执行 Round 22 到 Round 1
for rr in range(22, 0, -1):
if rr % 2 == 0: # 偶数轮: 逆AddRoundKey + 逆ShiftRows
state = self._inv_even_round(state, key_states[rr], rr, verbose)
else: # 奇数轮: 逆MixColumns + 逆SubBytes
state = self._inv_odd_round(state, key_states[rr], rr, verbose)
if verbose:
print(f"\n【解密结束】")
print(f" 明文 (u32): {[hex(s) for s in state]}")
# 4. 返回明文 (大端序)
plaintext = struct.pack('>4I', *state)
if verbose:
print(f" 明文 (bytes): {plaintext.hex().upper()}")
return plaintext
def _generate_all_round_keys(self):
"""
正向生成所有轮的密钥状态
返回: 字典 {round_number: key_state}
"""
key = self.initial_key.copy()
key_index = 0
key_states = {0: key.copy()}
# 模拟加密过程中的密钥更新
for rr in range(1, 23):
if rr % 2 == 1: # 奇数轮
if rr > 1:
# Round 3, 5, 7, ..., 21: 更新 s[2], s[3], s[4]
A_prime = key[0]
B = key[1]
C = key[2]
D = key[3]
key[1] = (B ^ A_prime) & 0xFFFFFFFF
key[2] = (C ^ B ^ A_prime) & 0xFFFFFFFF
key[3] = (D ^ C ^ B ^ A_prime) & 0xFFFFFFFF
key_states[rr] = key.copy()
else: # 偶数轮
key_states[rr] = key.copy()
# 更新 s[1]
A = key[0]
D = key[3]
rotated = rol(D, 8)
sboxed = apply_sbox_to_u32(rotated)
round_key = self.round_keys[key_index]
A_prime = (A ^ sboxed ^ round_key) & 0xFFFFFFFF
key[0] = A_prime
key_index += 1
return key_states
def _inv_odd_round(self, state_bytes, key, rr, verbose):
"""
逆奇数轮: 逆MixColumns + 逆SubBytes
输入: 16 字节数组
输出: 4 个 32位整数
"""
if verbose:
print(f"\n【Round {rr} 逆向】奇数轮 - InvMixColumns + InvSubBytes")
print(f" 输入 state (16字节): {[hex(b) for b in state_bytes]}")
print(f" 输入 key = {[hex(k) for k in key]}")
# 显示为 4x4 矩阵
print(f" 输入 4x4矩阵 (按列):")
for row in range(4):
print(f" row{row}: {[hex(state_bytes[col*4 + row]) for col in range(4)]}")
# 1. 逆MixColumns: 对每个32位整数拆分成4字节，逆MixColumns后得到16字节
inv_mixed_bytes = []
for i in range(4):
# 提取4个字节（按列存储）
col_bytes = state_bytes[i*4:(i+1)*4]
# 逆MixColumns
inv_mixed_col = inv_mix_column(list(col_bytes))
inv_mixed_bytes.extend(inv_mixed_col)
if verbose:
print(f" InvMixColumns 16字节: {[hex(b) for b in inv_mixed_bytes]}")
# 显示为 4x4 矩阵
print(f" InvMixColumns 4x4矩阵 (按列):")
for row in range(4):
print(f" row{row}: {[hex(inv_mixed_bytes[col*4 + row]) for col in range(4)]}")
# 2. 重新打包成4个32位整数（大端序）
sboxed = []
for i in range(4):
bytes_4 = inv_mixed_bytes[i*4:(i+1)*4]
val = struct.unpack('>I', bytes(bytes_4))[0]
sboxed.append(val)
if verbose:
print(f" 打包成u32 (应用InvSubBytes之前): {[hex(s) for s in sboxed]}")
# 3. 逆SubBytes: 对每个32位整数应用逆S-box
state = [apply_inv_sbox_to_u32(s) for s in sboxed]
if verbose:
print(f" InvSubBytes (输出state) = {[hex(s) for s in state]}")
return state
def _inv_even_round(self, state, key, rr, verbose):
"""
逆偶数轮: 逆AddRoundKey + 逆ShiftRows
输入: 4 个 32位整数
输出: 16 字节数组
"""
if verbose:
print(f"\n【Round {rr} 逆向】偶数轮 - InvAddRoundKey + InvShiftRows")
print(f" 输入 state = {[hex(s) for s in state]}")
print(f" 使用 key = {[hex(k) for k in key]}")
# 1. 逆AddRoundKey: state ^= key (XOR是自逆的)
unkeyed_state = [(state[i] ^ key[i]) & 0xFFFFFFFF for i in range(4)]
if verbose:
print(f" InvAddRoundKey (state ^= key):")
for i in range(4):
print(f" state[{i}] = {hex(state[i])} ^ {hex(key[i])} = {hex(unkeyed_state[i])}")
# 将4个32位整数拆分成16字节
# 按加密时的打包方式逆向
inv_shiftrows_indices = [
[0, 5, 10, 15], # col0 (对应倒序第3个)
[1, 6, 11, 12], # col1 (对应倒序第2个)
[2, 7, 8, 13], # col2 (对应倒序第1个)
[3, 4, 9, 14] # col3 (对应倒序第0个)
]
# 先将4个u32解包成按行存储的16字节
row_based = []
for val in unkeyed_state:
row_based.append((val >> 24) & 0xFF)
row_based.append((val >> 16) & 0xFF)
row_based.append((val >> 8) & 0xFF)
row_based.append(val & 0xFF)
if verbose:
print(f" 解包成16字节(按行): {[hex(b) for b in row_based]}")
# 创建逆映射
unshifted_row_based = [0] * 16
for col_idx, indices in enumerate(inv_shiftrows_indices):
for byte_idx, src_idx in enumerate(indices):
unshifted_row_based[src_idx] = row_based[col_idx * 4 + byte_idx]
if verbose:
print(f" InvShiftRows后(按行): {[hex(b) for b in unshifted_row_based]}")
# 转换回按列存储
state_bytes = []
for col in range(4):
for row in range(4):
state_bytes.append(unshifted_row_based[row * 4 + col])
if verbose:
print(f" 输出 16字节(按列): {[hex(b) for b in state_bytes]}")
# 显示为 4x4 矩阵
print(f" 输出 4x4矩阵 (按列):")
for row in range(4):
print(f" row{row}: {[hex(state_bytes[col*4 + row]) for col in range(4)]}")
return state_bytes
# ============================================================================
# 主程序
# ============================================================================
if __name__ == "__main__":
# ... (此处为测试函数和主逻辑调用，代码已省略，与原脚本一致)
pass
运行结果
使用上述脚本解密题目提供的flag.enc文件，成功得到最终flag。
总结
本题的难点在于对混合语言编写的、经过混淆的加密算法进行逆向工程。解题的关键在于结合静态分析、动态调试（Docker环境）以及AI辅助代码理解，逐步厘清复杂的多轮加密数据流和密钥更新逻辑。最终，通过Python完整复现算法并成功解密。这种多层协作的逆向工程思路，对于分析复杂的现代加密挑战具有借鉴意义。
完整的题目附件以及所有阶段的分析脚本，可在原发布页面查看。
发表于 3 天前
|
查看: 10|
回复: 0
