CTF之线性同余算法与赛题-EW帮帮网

概念

什么是线性同余算法(LCG)？
线性同余法(LCG,Linear Congruential Generator)是一种最简单、最常见的伪随机数生成算法
它使用一个递推公式，通过线性变换生成一系列的伪随机数

特点

计算简单，适合快速生成伪随机数
适用于硬件和软件环境
生成的随机数序列具有周期性（如果参数选择不当，周期可能较短）
安全性低，参数和种子易被破解，不适用于密码学

核心公式

$X_{n+1}=(a\cdot X_{n}+c)\bmod m$

参数

参数介绍

$X_{n}$ ：当前随机数（种子、前一个值）
$a$ ：乘数(Multiplier)，决定序列的跨度
$c$ ：增量(Increment)，若 $c$ ≠ 0，称为"混合线性同余法”
$m$ ：模数(Modulus)，决定取值范围 ( 0 ≤ $X_{n}$ < $m$ )
生成的随机数序列周期性重复，周期长度由参数组合决定，理想情况下可达 $m$

参数要求

$X_{n}$ ：可取任意非负整数，不同种子生成不同序列
$a$ ：需满足 $a - 1$ 能被 $m$ 的所有质因数整除，若 $m$ 为4的倍数，则 $a - 1$ 也需是4的倍数，以最大化周期
$c$ ：通常取与 $m$ 互质的非零值，避免序列出现固定偏移
$m$ ：需足够大（如2的幂或大质数）以延长周期

生成序列示例

选择 $m=9,a=2,c=0,X_{0}=1$ ，生成序列

$X_{1}=(2\times1+0)\bmod9=2\\X_{2}=(2\times2+0)\bmod9=4\\X_{3}=(2\times4+0)\bmod9=8\\X_{4}=(2\times8+0)\bmod9=7\\X_{5}=(2\times7+0)\bmod9=5\\X_{6}=(2\times5+0)\bmod9=1$

周期开始重复，周期为6

注意点

周期长度明显小于模数 $m$ ,说明参数选择不当
若调整参数（如 $a = 4, c = 1, m = 9$ )，可能得到更长的周期

CTF例题

题面

在一次情报传输中，WNCP 团队使用了一种简单的加密方法对一段秘密消息进行了加密
你截获了该密文文件，并知道消息的部分内容（即固定的开头部分）
请分析加密算法，利用已知明文攻击恢复出完整的明文，并找出其中隐藏的 flag

密文

13539cbb0b53c45070dd0957527c8ca8204c1c67267056f41db6fc5d0de576bd38cb2e4e17de5c6e2e27fbf2634b9ac05c6e8b1b46efa74e21273fef02c9865354098c11343d8e295a40b3511185313c300f2fa13f493ac71fdb18807e9301301df3c43e0987e79869d332af6656eb2c1f06a3201c94b4751d5459dc304970fd4da5d7d82a187bda5c123c2a127b04884c614dd63b932ec07a6d80952aff8ee4140d2ace

已知明文开头

-----BEGIN SECRET MESSAGE-----

加密过程采用如下步骤：

（1）明文分块
将明文转换为字节后，每 4 个字节分为一块
如果最后一块不足 4 字节，则使用 0x00 填充至 4 字节

（2）伪随机密钥流生成
使用线性同余发生器，LCG 的参数为：

种子：未知
乘数：a = 1103515245
增量：c = 12345
模数：m = 2^31

（3）异或加密
（4）输出密文

加解密流程分析

加密

明文数据 —> 转换为字节 —> 16进制数据
16进制数据进行分割 ----> 每4字节/每8位16进制数为一组 —> 不足4字节补齐0x00
每组数据与密钥进行异或加密
输出密文

解密

将已知明文开头转换为转换为字节，即16进制数据
明文开头与密文进行异或运算得到密钥的开始部分，注意密文同样需转为字节才能进行异或
根据线性同余算法，已知乘数、增量和模数，即可推出种子，进而生成完整密钥
密文与密钥进行异或得出完整密文

解密脚本

1. 定义已知参数与有用函数

import binascii

def hex_to_bytes(h):
    return binascii.unhexlify(h)

def xor_bytes(a, b):
    return bytes(x ^ y for x, y in zip(a, b))

plaintext_head = "-----BEGIN SECRET MESSAGE-----\n"  # 已知明文开头
ciphertext_hex = "13539cbb0b53c45070dd0957527c8ca8204c1c67267056f41db6fc5d0de576bd38cb2e4e17de5c6e2e27fbf2634b9ac05c6e8b1b46efa74e21273fef02c9865354098c11343d8e295a40b3511185313c300f2fa13f493ac71fdb18807e9301301df3c43e0987e79869d332af6656eb2c1f06a3201c94b4751d5459dc304970fd4da5d7d82a187bda5c123c2a127b04884c614dd63b932ec07a6d80952aff8ee4140d2ace"  # 你的密文（16进制字符串）

a = 1103515245  # 乘数
c = 12345       # 增量
m = 2**31       # 模数

2. 明文开头转换

# 步骤1: 将已知明文开头转换为转换为字节，即16进制数据
block0_plain = plaintext_head[:4].encode('utf-8')

3. 解出密钥开始部分

# 步骤2: 明文开头与密文进行异或运算得到密钥的开始部分
ciphertext_bytes = hex_to_bytes(ciphertext_hex)
block0_cipher = ciphertext_bytes[:4]
known_key_bytes = xor_bytes(block0_plain, block0_cipher)

# 将4字节密钥转换为整数，即为加密时第0块使用的种子，即X_{0}
state = int.from_bytes(known_key_bytes, 'big')
print("已知加密时第0块使用的种子为: ", state)

4. 解出完整密钥，并与密文异或得到明文

# 每4字节为一个块进行解密，不足4字节的块填充0
decrpted = b""
num_blocks = len(ciphertext_bytes) // 4
if len(ciphertext_bytes) % 4 != 0:
    num_blocks += 1

for i in range(num_blocks):
    # 步骤3: 使用线性同余生成器生成密钥
    if i == 0:
        # 如果是第一个块，使用已知的密钥前几字节
        key = known_key_bytes
    else:
        state = (a * state + c) % m
        key = state.to_bytes(4, 'big')  # 每次生成4字节
    start = i * 4
    end = start + 4
    block = ciphertext_bytes[start:end]

    # 如果最后一个块不足4字节，填充0
    if len(block) < 4:
        block += b'\x00' * (4 - len(block))

    # 步骤4: 使用密钥对密文块进行异或解密得到明文
    plaintext_block = xor_bytes(block, key)
    decrpted += plaintext_block

plaintext = decrpted.decode('utf-8', errors='replace')
print("解密结果: ", plaintext)

解密结果

执行解密脚本，成功完成解密，拿到flag{wncp_0956}

参考链接

CTF之线性同余算法与赛题

概念

特点