如何基于C语言rand()重实现完成Python信息安全作业的明文恢复？

问题描述 #

本周Python课程的信息安全作业要求还原加密文件的明文，加密流程基于glibc风格的线性同余生成器（LCG）实现的rand()函数：

• LCG状态更新规则：next = ((next * 1103515245) + 12345) & 0x7fffffff（等价于模2^31运算）
• 加密时，先调用byte_rand(16)生成16字节的AES-CBC初始向量（IV），再调用byte_rand(16)生成16字节AES密钥，最后对文件进行加密并保存IV和密文
• 挑战任务是在没有密钥文件的情况下，仅通过.enc文件还原明文，需要补全solve_challenge函数的代码

作业提供的完整代码如下：

import os
import os.path
import sys
import struct
import argparse

from util import check_challenge

from crand import rand, srand
from Cryptodome.Cipher import AES
from Cryptodome.Util.Padding import pad, unpad  # pkcs7 is standard


def byte_rand(numbytes):
    calls = (numbytes + 3) // 4
    randbytes = b''
    for i in range(calls):
        r = rand()
        randbytes += struct.pack('<I', r)

    return randbytes[:numbytes]


def enc_file(fname):
    iv = byte_rand(16)
    key = byte_rand(16)

    cipher = AES.new(key=key, mode=AES.MODE_CBC, iv=iv)
    f = open(fname, 'rb')
    ct = cipher.encrypt(pad(f.read(), 16))
    f.close()

    with open(fname + '.enc', 'wb') as f:
        f.write(iv)
        f.write(ct)

    with open(fname + '.key', 'wb') as f:
        f.write(key)


def dec_file(fname):
    with open(fname + '.key', 'rb') as f:
        key = f.read()

    with open(fname + '.enc', 'rb') as f:
        iv = f.read(16)
        ct = f.read()

    cipher = AES.new(key=key, mode=AES.MODE_CBC, iv=iv)

    try:
        pt = unpad(cipher.decrypt(ct), AES.block_size, style='pkcs7')
    except ValueError:
        print(fname + ': decryption failed, invalid padding')

    with open(fname, 'wb') as f:
        f.write(pt)


def solve_challenge(fname):
    with open(fname + '.enc', 'rb') as f:
        iv = f.read(16)
        ct = f.read()

    key = bytes(16)
    
#######################################################################
    #[enter your code here
########################################################################

    cipher = AES.new(key=key, mode=AES.MODE_CBC, iv=iv)
    try:
        pt = unpad(cipher.decrypt(ct), AES.block_size, style='pkcs7')
    except ValueError:
        print(fname + ': decryption failed, invalid padding')
        return

    with open(fname, 'wb') as f:
        f.write(pt)


def main():
    parser = argparse.ArgumentParser()
    subparsers = parser.add_subparsers(dest='command', title='command')
    subparsers.required = True
    parser_e = subparsers.add_parser('e', help='encrypt')
    parser_e.add_argument('file', nargs='+')
    parser_d = subparsers.add_parser('d', help='decrypt')
    parser_d.add_argument('file', nargs='+')
    parser_c = subparsers.add_parser('c', help='challenge')
    parser_c.add_argument(
        'file',
        nargs='*',
        default=['challenge.enc'],
        help='default: challenge.enc')
    args = parser.parse_args()

    files = [
        t for t in args.file if (
            os.path.isfile(t) and not t.endswith('.key'))]

    rng_seed = struct.unpack('<I', os.urandom(4))[0]
    srand(rng_seed)

    if args.command == 'e':
        # we don't encrypt already encrypted files
        files = [t for t in files if not t.endswith('.enc')]
        if len(files) == 0:
            print('No valid files selected')
            return

        for f in files:
            enc_file(f)

        return

    if args.command == 'd':
        # we only want encrypted files
        files = [t[:-4] for t in files if t.endswith('.enc')]
        if len(files) == 0:
            print('No valid files selected')
            return

        for f in files:
            dec_file(f)

        return

    # challenge: decrypt without having the key
    if args.command == 'c':
        # we only want encrypted files
        files = [t[:-4] for t in files if t.endswith('.enc')]
        if len(files) == 0:
            print('No valid files selected')
            return

        for f in files:
            solve_challenge(f)
            check_challenge(f)

        return


if __name__ == "__main__":
    sys.exit(main())

核心思路 #

glibc的LCG是线性同余生成器，其数学特性决定了：只要获得连续的几个输出值，就能反推出内部状态，进而预测后续所有输出。

在本次加密流程中：

1. 生成IV时，byte_rand(16)会调用4次rand()，每次输出32位值，按小端序打包成字节，取前16字节作为IV
2. 生成密钥时，byte_rand(16)紧接着调用下4次rand()，同样打包成16字节作为AES密钥

因此，我们可以从IV中提取出4个连续的LCG输出值，反推出LCG的初始状态，再正向生成密钥对应的4个输出值，从而得到AES密钥。

补全后的solve_challenge函数 #

def solve_challenge(fname):
    with open(fname + '.enc', 'rb') as f:
        iv = f.read(16)
        ct = f.read()

    # 从IV中解析出4个rand()的输出（小端序32位无符号整数）
    iv_rands = []
    for i in range(4):
        chunk = iv[i*4 : (i+1)*4]
        rand_val = struct.unpack('<I', chunk)[0]
        iv_rands.append(rand_val)

    # LCG的核心参数
    MULTIPLIER = 1103515245
    INCREMENT = 12345
    MODULUS = 0x80000000  # 2^31，对应&0x7fffffff的模运算

    # 扩展欧几里得算法求模逆元
    def extended_gcd(a, b):
        if a == 0:
            return (b, 0, 1)
        else:
            g, y, x = extended_gcd(b % a, a)
            return (g, x - (b // a) * y, y)

    def modinv(a, m):
        g, x, y = extended_gcd(a, m)
        if g != 1:
            raise ValueError("乘法逆元不存在")
        return x % m

    # 计算乘法因子在模2^31下的逆元
    inv_multiplier = modinv(MULTIPLIER, MODULUS)

    # 从IV的最后一个rand值倒推出生成IV之前的LCG状态
    current_state = iv_rands[-1]
    # 倒推4次，回到生成第一个IV rand值前的初始状态
    for _ in range(4):
        current_state = (current_state - INCREMENT) * inv_multiplier % MODULUS

    # 正向生成密钥对应的4个rand值
    key_rands = []
    for _ in range(4):
        current_state = (current_state * MULTIPLIER + INCREMENT) % MODULUS
        key_rands.append(current_state)

    # 将rand值打包成16字节小端序的密钥
    key = b''
    for r in key_rands:
        key += struct.pack('<I', r)
    key = key[:16]

    cipher = AES.new(key=key, mode=AES.MODE_CBC, iv=iv)
    try:
        pt = unpad(cipher.decrypt(ct), AES.block_size, style='pkcs7')
    except ValueError:
        print(fname + ': decryption failed, invalid padding')
        return

    with open(fname, 'wb') as f:
        f.write(pt)

关键步骤解释 #

1. 解析IV中的LCG输出：IV由4个rand()输出按小端序拼接而成，每4字节解析为一个32位无符号整数，得到连续的LCG输出序列。
2. 计算模逆元：LCG的正向公式是next = (state * MULT + INC) mod MOD，逆运算需要求解state = (next - INC) * inv(MULT) mod MOD，因此用扩展欧几里得算法计算乘法因子在模2^31下的逆元。
3. 倒推初始状态：从IV的最后一个LCG输出值开始，逆推4次，回到生成第一个IV输出前的LCG内部状态。
4. 生成密钥：用倒推得到的初始状态，正向运行LCG4次，得到生成密钥的4个输出值，打包成16字节即为AES密钥。
5. 解密验证：用得到的密钥和已知IV进行AES-CBC解密，去除PKCS7填充后得到明文。

内容的提问来源于stack exchange，提问作者wendyLei0620