线性同余生成器（LCG）学习记录
前言
foreword
简介
brief
|
|
目的 |
公式 |
|
No.1 |
Xn+1反推出Xn |
Xn=(a-1 (Xn+1 - b))%m |
|
No.2 |
求a |
a=((Xn+2-Xn+1)(Xn+1-Xn)-1)%m |
|
No.3 |
求b |
b=(Xn+1 - aXn)%m |
|
No.4 |
求m |
tn=Xn+1-Xn，m=gcd((tn+1tn-1 - tntn) , (tntn-2 - tn-1tn-1)) |
具体公式推导见以下链接：
https://blog.csdn.net/superprintf/article/details/108964563
例题
from Crypto.Util.number import *f = open('flag.txt', 'r')flag = f.read()f.close()assert flag[:8] == "Dest0g3{"class LCG:def __init__(self):self.a = getRandomNBitInteger(32)self.b = getRandomNBitInteger(32)self.m = getPrime(32)self.seed = getRandomNBitInteger(32)def next(self):self.seed = (self.a * self.seed + self.b) % self.mreturn self.seed 16def output(self):print("a = {}nb = {}nm = {}".format(self.a, self.b, self.m))print("state1 = {}".format(self.next()))print("state2 = {}".format(self.next()))lcg = LCG()lcg.output()c = b''.join([long_to_bytes(ord(flag[i]) ^ (lcg.next() % 10))for i in range(len(flag))])print(bytes_to_long(c))'''a = 3939333498b = 3662432446m = 2271373817state1 = 17362state2 = 20624600017039001091357643174067454938198067935635401496485588306838343558125283178792619821966678282131419050878'''
分析：
from Crypto.Util.number import *f = open('flag.txt', 'r')flag = f.read()f.close()assert flag[:8] == "Dest0g3{"#读取名为 'flag.txt' 的文件，并确保文件内容的前8个字符是 "Dest0g3{"class LCG:def __init__(self):self.a = getRandomNBitInteger(32)self.b = getRandomNBitInteger(32)self.m = getPrime(32)self.seed = getRandomNBitInteger(32)#定义了一个名为LCG的类，通过调用 getRandomNBitInteger(32) 方法生成一个32位的随机整数，赋值为lcg的基本模数a，b，m，seeddef next(self):self.seed = (self.a * self.seed + self.b) % self.mreturn self.seed 16#根据线性同余生成器的公式计算下一个伪随机数，并返回该伪随机数的右移16位后的值def output(self):print("a = {}nb = {}nm = {}".format(self.a, self.b, self.m))print("state1 = {}".format(self.next()))print("state2 = {}".format(self.next()))#定义了output()方法，打印a，b，m的值，使用 format() 方法将这些值插入到相应的字符串中。调用生成器的 next() 方法，计算并打印生成器的下一个状态值 state1。使用 format() 方法将该值插入到相应的字符串中。再次调用生成器的 next() 方法，计算并打印生成器的下一个状态值 state2。同样使用format() 方法将该值插入到相应的字符串中lcg = LCG()#创建一个 LCG 类的实例对象 lcglcg.output()#调用 output() 方法输出生成器的参数值和两个连续状态值c = b''.join([long_to_bytes(ord(flag[i]) ^ (lcg.next() % 10))for i in range(len(flag))])#使用列表推导式和位运算符计算变量 c 的值：遍历字符串 flag 的每个字符，将其转换为 ASCII 码，并与生成器的下一个状态值进行位异或运算。将位异或结果通过取余运算限制在 0-9 的范围内。将每个限制后的结果转换为字节类型，并将它们合并为一个字节序列print(bytes_to_long(c))#使用 bytes_to_long() 函数将字节序列 c 转换为一个长整数
可以总结为四个步骤：
1. LCG对象的初始化：LCG类的构造函数使用了随机生成的参数a、b、m和seed来初始化LCG对象的属性。这些参数决定了随机数生成器的行为。
2. 生成随机数：LCG类的next()方法使用线性同余公式来生成下一个随机数。每次调用next()方法都会更新seed的值，并返回右移16位后的结果。
3. 对flag进行加密：代码使用LCG对象生成一个长度与flag相同的随机数序列，然后将每个flag字符与（lcg.next() % 10）进行异或操作，并将结果转换为字节类型。
4. 将加密后的结果转换为整数：使用 bytes_to_long() 函数将加密后的字节序列转换为一个大整数。
代码如下：
for i in range(65536):bin1 = bin(17362)[2:]bin2 = bin(i)[2:].ljust(16, '0')seed = int(bin1 + bin2, 2)seed2 = (a * seed + b) % mif seed2 >> 16 == 20624:init_seed = seedprint(seed)
from Crypto.Util.number import *a = 3939333498b = 3662432446m = 2271373817init_seed = 0for i in range(65536):bin1 = bin(17362)[2:]bin2 = bin(i)[2:].ljust(16, '0')seed = int(bin1 + bin2, 2)seed2 = (a * seed + b) % mif seed2 16 == 20624:init_seed = seedprint(seed)# 1137870862class LCG:def __init__(self):self.a = aself.b = bself.m = mself.seed = init_seeddef next(self):self.seed = (self.a * self.seed + self.b) % self.mreturn self.seed 16def output(self):print("a = {}nb = {}nm = {}".format(self.a, self.b, self.m))print("state = {}".format(self.next()))lcg = LCG()lcg.output()c =600017039001091357643174067454938198067935635401496485588306838343558125283178792619821966678282131419050878c_string=long_to_bytes(m)m = ''for a in c_string:m_char = a^(lcg.next()%10)m += chr(m_char)print(m)
END
原文始发于微信公众号（火炬木攻防实验室）：线性同余生成器（LCG）学习记录
免责声明:文章中涉及的程序(方法)可能带有攻击性，仅供安全研究与教学之用，读者将其信息做其他用途，由读者承担全部法律及连带责任，本站不承担任何法律及连带责任；如有问题可邮件联系(建议使用企业邮箱或有效邮箱,避免邮件被拦截，联系方式见首页)，望知悉。
- 左青龙
- 微信扫一扫
-
- 右白虎
- 微信扫一扫
-
评论