LCG

流密码介绍

$X_{n+1} = (aX_n + b) \pmod m$

LCG代码实现

Python 实现

class LCG:
    def __init__(self, seed, a, b, m):
        self.seed = seed  # 初始种子
        self.a = a  # 乘数
        self.b = b  # 增量
        self.m = m  # 模数

    def generate(self):
        self.seed = (self.a * self.seed + self.b) % self.m
        return self.seed

题面

from Crypto.Util.number import *

flag = b'NSSCTF{******}'

class LCG:
    def __init__(self, seed, a, b, m):
        self.seed = seed  # 初始种子
        self.a = a  # 乘数
        self.b = b  # 增量
        self.m = m  # 模数

    def generate(self):
        self.seed = (self.a * self.seed + self.b) % self.m
        return self.seed


lcg = LCG(bytes_to_long(flag), getPrime(256), getPrime(256), getPrime(256))

for i in range(getPrime(16)):
    lcg.generate()

print(f'a = {lcg.a}')
print(f'b = {lcg.b}')
print(f'm = {lcg.m}')
print(lcg.generate())


'''
a = 113439939100914101419354202285461590291215238896870692949311811932229780896397
b = 72690056717043801599061138120661051737492950240498432137862769084012701248181
m = 72097313349570386649549374079845053721904511050364850556329251464748004927777
9772191239287471628073298955242262680551177666345371468122081567252276480156
'''

本题给出了LCG的各个参数，然后给出了一次密文，而初始种子便是我们的flag

现在我们拥有 $X_{n+1}$ , $a$ , $b$ , $m$ , 我们进行如下操作

对第一个式子(LCG递推式)

$X_{n+1} = (aX_n + b) \pmod m$

进行移项后如下

$X_n = (X_{n+1} - b)a^{-1} \pmod m$

这样我们便得到了一个从下一项逆向递推上一项的式子。

那么在题目中我们要逆向多少项呢？我们并不知道，因为中间迭代的次数是一个随机数，但是我们不用关心，因为我们知道flag的格式，所以只需要不断的逆向，直到找到符合格式的flag为止。

exp

from Crypto.Util.number import *

a = 113439939100914101419354202285461590291215238896870692949311811932229780896397
b = 72690056717043801599061138120661051737492950240498432137862769084012701248181
m = 72097313349570386649549374079845053721904511050364850556329251464748004927777
x = 9772191239287471628073298955242262680551177666345371468122081567252276480156

inva = inverse(a, m)

for i in range(2**16):
    x = (x-b)*inva % m

    flag = long_to_bytes(x)
    if b'NSSCTF' in flag:
        print(flag)

从这里也可以看出，一旦LCG的参数遭到了泄露，我们便可以向前恢复或者向后预测出其他的随机数（或者专业点叫做流密钥）。