LCG学习

LCG学习

LCG属于PRNG(伪随机数生成器)和stream cipher(流密码)的一种，是一种产生伪随机数的方法。
Xn+1 = (a*Xn + b) mod m
其中，Xn代表第n个生成的随机数，X0被称为种子值。这里还定义了三个整数：a乘数、b增量、m模数，是产生器设定的常数。

参数

LCG的性质与参数的选择密切相关，不同的参数可能导致不同的随机序列。一般按照如下要求选择参数：

  • m是随机序列的模数，必须一个大于0的正整数。一般是一个比较大的素数或者是2的幂，以便提供较长的周期长度。
  • a是乘数，必须是一个与m互素的正整数。
  • b是增量，也必须是一个与m互素的正整数。

LCG 的周期最大为 M，但大部分情况都会少于 M。要令 LCG 达到最大周期，应符合以下条件：

  • B，M 互质
  • M 的所有质因数都能整除 A-1
  • 若 M 是 4 的倍数，A-1 也是
  • A,B,X0都比 M 小

常用公式

由Xn+1反推Xn：

Xn = ((Xn+1 - b) * a-1) mod m，这里a-1是模逆元

求 a：
a = ((Xn+1 - Xn) * (Xn - Xn-1)-1) mod m

求 b：
b = (Xn+1 - a * Xn) mod m

求 m:
tn = Xn+1 - Xn = a(Xn - Xn-1) = a*tn-1 mod m

tn+1tn-1 - tntn = a*a* tn-1*tn-1 - a*tn-1*a*tn-1 = 0 mod m

即Tn = tn+1tn-1 - tntn 是 m 的倍数，故Tn和Tn-1的最大公因数即为 m

python代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class LCG:
  a = 672257317069504227  # "乘数"
  b = 7382843889490547368  # "增量"
  m = 9223372036854775783  # "模数"
  def __init__(self, seed):
    self.state = seed  # "种子"
  def next(self):
    self.state = (self.state * self.a + self.b) % self.m
    return self.state
gen = LCG(123)  # seed = 123
print gen.next()  # 第一个生成值
print gen.next()  # 第二个生成值
print gen.next()  # 第三个生成值
# 7060145557346585242
# 3490819368718893392
# 6200546448603839134

常见题型

LCG_1：a，b，m都知道，相当于由Xn+1反推Xn

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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
'''

题目分析

  • 迭代的次数是getPrime(16)，我们并不知道迭代了多少次，但是我们知道flag的格式是b’NSSCTF{******}’，不断反推直到符合格式即可

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import gmpy2
import libnum

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

# c=(a*c0+b)%m
a_1=gmpy2.invert(a,m)

for i in range(2**16):
    c = (c - b) * a_1 % m
    #print(c)
    flag=libnum.n2s(int(c))
    if b'NSSCTF{' in flag:
        print(flag)
        break
#b'NSSCTF{recover_init_seed}'

LCG_2：不知道b，用a，m，Xn+1和Xn推出b就和LCG_1一样了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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 = 83968440254358975953360088805517488739689448515913931281582194839594954862517
m = 77161425490597512806099499399561161959645895427463118872087051902811605680317
43959768681328408257423567932475057408934775157371406900460140947365416240650
8052043336238864355872102889254781281466728072798160448260752595038552944808
'''

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import gmpy2
import libnum
from Crypto.Util.number import isPrime

a = 83968440254358975953360088805517488739689448515913931281582194839594954862517
m = 77161425490597512806099499399561161959645895427463118872087051902811605680317
c1=43959768681328408257423567932475057408934775157371406900460140947365416240650
c2=8052043336238864355872102889254781281466728072798160448260752595038552944808

b=(c2-a*c1) % m
#print(b)
#print(gmpy2.gcd(b,m))
a_1 = gmpy2.invert(a,m)
c = c1

for i in range(2**16):
    c = (c-b) * a_1 % m
    flag = libnum.n2s(int(c))

    if b'NSSCTF' in flag:
        print(flag)
        break
#b'NSSCTF{recover_b}'

LCG_3：a、b都不知道，先求出a,之后操作同LCG_2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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 = 96343920769213509183566159649645883498232615147408833719260458991750774595569
10252710164251491500439276567353270040858009893278574805365710282130751735178
45921408119394697679791444870712342819994277665465694974769614615154688489325
27580830484789044454303424960338587428190874764114011948712258959481449527087
'''

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import gmpy2
import libnum

m = 96343920769213509183566159649645883498232615147408833719260458991750774595569
c1 = 10252710164251491500439276567353270040858009893278574805365710282130751735178
c2 = 45921408119394697679791444870712342819994277665465694974769614615154688489325
c3 = 27580830484789044454303424960338587428190874764114011948712258959481449527087

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(2**16):
    c = (c-b) * a_1 % m
    flag = libnum.n2s(int(c))

    if b'NSSCTF{' in flag:
        print(flag)
        break
#b'NSSCTF{now_recover_a}'

LCG_4：a、b、m都不知道，给出多组输出，让我们恢复初始种子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Util.number import *

flag = b'flag{******}'
seed = bytes_to_long(flag)
length = seed.bit_length()

a = getPrime(length)
b = getPrime(length)
p = getPrime(length)

output = []
for i in range(10):
    seed = (a * seed + b) % p
    output.append(seed)

print("output =", output)
# output = [168629567557403367186885420444281063317304797350594299096453254, 37810059304430144255796769528019631599115017008645572272676848, 153467674569619182399277890239200868986878351528697622090498978, 130441867851875429652192551507870248584806009516471536255184738, 165072061865233441980188465107233439530695291179218871834569574, 169462757174386331962049136282171771458712297105156982582248590, 5733544729623964834423742564305810327645521588143518180790467, 29307267147593660845277077949962969239999900796071055310564887, 167961532214306463210330398007557832141937447147319867665370457, 18070228848659542858848007252120157475238819346210716562665302]

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
from Crypto.Util.number import *
import gmpy2
 
# a = getPrime(length)
# b = getPrime(length)
# p = getPrime(length)

output = [168629567557403367186885420444281063317304797350594299096453254, 37810059304430144255796769528019631599115017008645572272676848, 153467674569619182399277890239200868986878351528697622090498978, 130441867851875429652192551507870248584806009516471536255184738, 165072061865233441980188465107233439530695291179218871834569574, 169462757174386331962049136282171771458712297105156982582248590, 5733544729623964834423742564305810327645521588143518180790467, 29307267147593660845277077949962969239999900796071055310564887, 167961532214306463210330398007557832141937447147319867665370457, 18070228848659542858848007252120157475238819346210716562665302]

gift = output

t = []
for i in range(len(gift) - 1):
    t.append(gift[i] - gift[i-1])

all_p = []
for i in range(len(t) - 2):
    all_p.append(gmpy2.gcd((t[i+1] * t[i-1] - t[i] * t[i]), (t[i+2] * t[i] - t[i+1] * t[i+1])))

for p in all_p:
    p = abs(p)
    if p == 1:
        continue
    
    #求a
    MMI = lambda A, n, s=1, t=0, N=0 : (n<2 and t%N or MMI(n, A%n, t, s-A//n*t, N or n), -1)[n<1]  #逆元计算
    a = (gift[2] - gift[1]) * MMI((gift[1] - gift[0]), p) % p
    
    #求b
    b = (gift[1] - a * gift[0]) % p
    
    ani = MMI(a, p)
    seed = gift[0]
    
    for i in range(1):
        seed = (ani * (seed - b)) % p
    
    print(long_to_bytes(seed))

# b'\x02'
# b'\x02'
# b'\x17b\xd3\x03\xcaV\x95\x9a\xc5\xe7C\xa6\x1f\xa3\x88\xd5L\x02\xf5\xa9I\xb2\xce\x17/\xc7\xa6'
# b'\x1e\xb9I\xd93\xbd\x07\xcf\xbc\xbd\xe0\xf1\xf4\x18gB\xe8P\xfe;\x01B\xd2\xccy>'
# b'\rj5\xb4\x19\xd9\xef\xa4\xee\xb0x\x08y\xc6\x0f\x81\x91@\xaf\x16\xd5\xaf\xdb\x8c)\xca\x9e'
# b'flag{This_is_a_test_flag!}'
# b'flag{This_is_a_test_flag!}'

参考文章：LCG入门,LCG线性同余生成器
暂时只会这么多了，还有和格相关的算法，等格学明白了再补

LCG
#LCG
LCG学习
http://example.com/2024/02/28/LCG学习/
作者
John Doe
发布于
2024年2月28日
更新于
2024年9月8日
许可协议