May 22, 2023

NSSCTF 流密码工坊

LCG 流密码介绍 [公式] 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递推式) [公式] 进行移项后如下 [公式] 这样我们便得到了一个从下一项逆向递推上一项的式子。那么在题目中我们要逆向多少项呢？我们并不知道，因为中间迭代的次数是一个随机数，但是我们不用关心，因为我们知道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的参数遭到了泄露，我们便可以向前恢复或者向后预测出其他的随机数（或者专业点叫做流密钥）。

March 4, 2023

#math