大家好，欢迎来到IT知识分享网。
LCG(线性同余生成器)
参数选择
LCG的性质与参数的选择密切相关，不同的参数可能导致不同的随机序列。一般按照如下要求选择参数：
1、m是随机序列的模数，必须一个大于0的正整数。一般是一个比较大的素数或者是2的幂，以便提供较长的周期长度。
2、a是乘数，必须是一个与m互素的正整数。
3、b是增量，也必须是一个与m互素的正整数。
常用公式
公式一：由Xn+1反推Xn
X n = ( ( X n + 1 − b ) ∗ a − 1 ) m o d m ， 这 里 a − 1 是 模 逆 元 X_{n}=((X_{n+1}-b)*a^{-1})\textbf{ }mod\textbf{ }m，这里a^{-1}是模逆元 Xn=((Xn+1−b)∗a−1) mod m，这里a−1是模逆元
公式二：求a
{ X n + 1 = ( a ∗ X n + b ) m o d m X n = ( a ∗ X n − 1 ) m o d m ⇒ a = ( ( X n + 1 − X n ) ∗ ( X n − X n − 1 ) − 1 ) m o d m \left\{\begin{matrix} X_{n+1} & = &(a*X_{n}+b) &mod &m \\ X_{n} & = &(a*X_{n-1}) & mod &m \end{matrix}\right.\Rightarrow a=((X_{n+1}-X_{n})*(X_{n}-X_{n-1})^{-1}\textup{ })mod\textbf{ }m {
Xn+1Xn==(a∗Xn+b)(a∗Xn−1)modmodmm⇒a=((Xn+1−Xn)∗(Xn−Xn−1)−1 )mod m
公式三：求b
b = ( X n + 1 − a ∗ X n ) m o d m b=(X_{n+1}-a*X_{n})\textbf{ }mod\textbf{ }m b=(Xn+1−a∗Xn) mod m
公式四：求m
t n = X n + 1 − X n , t n = ( a ∗ X n + b ) − ( a ∗ X n − 1 + b ) = a ( X n − X n − 1 ) = a ∗ t n − 1 m o d m . t_{n}=X_{n+1}-X_{n},t_{n}=(a*X_{n}+b)-(a*X_{n-1}+b)=a(X_{n}-X_{n-1})=a*t_{n-1}\textbf{ } mod\textbf{ }m. tn=Xn+1−Xn,tn=(a∗Xn+b)−(a∗Xn−1+b)=a(Xn−Xn−1)=a∗tn−1 mod m.
∴ t n + 1 t n − 1 − t n t n = a ∗ a ∗ t n − 1 ∗ t n − 1 − a ∗ t n − 1 ∗ a ∗ t n − 1 = 0 m o d m \therefore t_{n+1}t_{n-1}-t_{n}t_{n}=a*a*t_{n-1}*t_{n-1}-a*t_{n-1}*a*t_{n-1}=0\textup{ }mod\textup{ }m ∴tn+1tn−1−tntn=a∗a∗tn−1∗tn−1−a∗tn−1∗a∗tn−1=0 mod m
即 T n = t n + 1 t n − 1 − t n t n 是 m 的 倍 数 ， 故 T n 和 T n − 1 的 最 大 公 因 数 即 为 m 即T_{n}=t_{n+1}t_{n-1}-t_{n}t_{n}是m的倍数，故T_{n}和T_{n-1}的最大公因数即为m 即Tn=tn+1tn−1−tntn是m的倍数，故Tn和Tn−1的最大公因数即为m
常见六种题型
LCG_1:a、b、m都知道，此类题相当于由Xn+1反推Xn.
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 = 0 b = 0 m = 0 ''' 有一个问题就是，我们需要反推多少项呢？我们并不知道，因为迭代的次数(getPrime(16))是一个随机数。但是这并不妨碍我们求解flag。因为flag的格式(b’NSSFCT{’)我们已经知道，只需要不断反推，直至找到符合格式的flag为止 。
脚本：
import gmpy2 import libnum a = 0 b = 0 m = 0 c= # c=(a*c0+b)%m a_1=gmpy2.invert(a,m) for i in range(216): c = (c - b) * a_1 % m #print(c) flag=libnum.n2s(int(c)) if b'NSSCTF{' in flag: print(flag) break LCG_2:不知道b,要先求出b,之后操作就和LCG_1没什么区别了
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'm = {
lcg.m}') print(lcg.generate()) print(lcg.generate()) ''' a = 00 m = 0 ''' 脚本：
import gmpy2 import libnum from Crypto.Util.number import isPrime a = 00 m = c1=0 c2= b=(c2-a*c1) % m #print(b) #print(gmpy2.gcd(b,m)) a_1 = gmpy2.invert(a,m) c = c1 for i in range(216): c = (c-b) * a_1 % m flag = libnum.n2s(int(c)) if b'NSSCTF' in flag: print(flag) break LCG_3:a、b都不知道，先求出a,之后操作同LCG_2
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'm = {
lcg.m}') print(lcg.generate()) print(lcg.generate()) print(lcg.generate()) ''' m = ''' 脚本
import gmpy2 import libnum m = c1 = c2 = c3 = a = (c3-c2) * gmpy2.invert(c2-c1,m) % m # print(gmpy2.gcd(a,m)) a_1 = gmpy2.invert(a,m) b = (c2-a*c1) % m # print(gmpy2.gcd(b,m)) c = c1 for i in range(216): c = (c-b) * a_1 % m flag = libnum.n2s(int(c)) if b'NSSCTF{' in flag: print(flag) break LCG_4：a、b、m都不知道，给出多组输出，让我们恢复初始种子。
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(lcg.generate()) print(lcg.generate()) print(lcg.generate()) print(lcg.generate()) print(lcg.generate()) ''' 0 0 0 0 ''' 首先，我们要先求出m，才能LCG_3的操作。
脚本：
import gmpy2 import libnum from Crypto.Util.number import GCD, isPrime, long_to_bytes c=[0, , 0, 0, 0] t=[] for i in range(1,len(c)): t.append(c[i]-c[i-1]) m = 0 for i in range(1,len(t)-1): m = GCD(t[i+1]*t[i-1]-t[i]2, m) # print(isPrime(m)) False m//=2 # print(isPrime(m)) a = (c[3]-c[2])*gmpy2.invert(c[2]-c[1],m) % m b = (c[2]-a*c[1]) % m # print(gmpy2.gcd(a,m)) # print(gmpy2.gcd(b,m)) a_1=gmpy2.invert(a,m) for i in range(216): c[1] = (c[1]-b) * a_1 % m flag = long_to_bytes(c[1]) if b'NSSCTF{' in flag: print(flag) break 这里需要解释一下代码中为什么要进行 m//=2 这样的操作？
我们虽然得到了m的倍数，通过求解 GCD 也确实能得到 m。但是在数据不够多的情况下，我们可能得到的是 km (不信的话，你可以输出一下 isPrime(m) 发现 m 确实不是素数) ,这时就需要我们遍历一些小数，手动去除 k 。*
LCG_5:本题给出信息和LCG_4一样需要我们恢复参数。
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(lcg.generate()) print(lcg.generate()) print(lcg.generate()) print(lcg.generate()) print(lcg.generate()) ''' ''' 需要注意的是，这里所给的LCG递归式是
self.seed = self.a * (self.seed - self.b) % self.m 我们只需要把 -ab 看成一个整体，这样我们就可以转化为标准式 ax+b 的形式。因为这里我们只需要恢复初始种子 m，所以代码和LCG_4没什么区别。
脚本：
import gmpy2 from Crypto.Util.number import GCD, isPrime, long_to_bytes c=[, , , , ] t=[] for i in range(1,len(c)): t.append(c[i]-c[i-1]) m = 0 for i in range(1,len(t)-1): m = GCD(t[i+1]*t[i-1]-t[i]2, m) print(isPrime(m)) # False m的倍数 print(m) for i in range(1,100): if isPrime(m//i): print(i) # i是4 m//=i break a = (c[3]-c[2])*gmpy2.invert(c[2]-c[1],m) % m b = (c[2]-a*c[1]) % m # print(gmpy2.gcd(a,m)) # print(gmpy2.gcd(b,m)) a_1=gmpy2.invert(a,m) for i in range(216): c[1] = (c[1]-b) * a_1 % m flag = long_to_bytes(c[1]) if b'NSSCTF{' in flag: print(flag) break LCG_6:同样需要恢复参数
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 self.seed = (self.a * self.seed + self.b) % self.m return self.seed lcg = LCG(bytes_to_long(flag), getPrime(255), getPrime(255), getPrime(256)) for i in range(getPrime(16)): lcg.generate() print(lcg.generate()) print(lcg.generate()) print(lcg.generate()) print(lcg.generate()) print(lcg.generate()) 这里进行了两次加密，我们得到的并不是连续的输出，而是隔位输出，比如是 X2,X4,X6,X8,X10
self.seed = (self.a * self.seed + self.b) % self.m self.seed = (self.a * self.seed + self.b) % self.m 
脚本：
import gmpy2 from Crypto.Util.number import GCD, isPrime, long_to_bytes c = [, 0, , , 0] t=[] for i in range(1,len(c)): t.append(c[i]-c[i-1]) m = 0 for i in range(1,len(t)-1): m = GCD(t[i+1]*t[i-1]-t[i]2, m) # print(isPrime(m)) # true a = (c[3]-c[2])*gmpy2.invert(c[2]-c[1],m) % m b = (c[2]-a*c[1]) % m # 把(a+1)*b当成b就可以了 # print(gmpy2.gcd(a,m)) # print(gmpy2.gcd(b,m)) a_1=gmpy2.invert(a,m) for i in range(216): c[1] = (c[1]-b) * a_1 % m flag = long_to_bytes(c[1]) if b'NSSCTF{' in flag: print(flag) break 最后附上我参考的文章：
ctf之lcg算法
LCG(线性同余生成器)
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/136935.html
