概要

线性同余生成器(Linear congruential generator)是一种常见的伪随机数生成器(Pseudo-randomized numbers generator)通过递归执行获得近似真随机序列,但因为表达式简单也常常被使用

它的表达式如下

S0=seedSi+1=aSn+bmodN\begin{array}{c} S_{0}=\operatorname{seed} \\ S_{i+1}=a S_{n}+b \bmod N \end{array}

其中aa为乘数,bb为增量,nn为模数,可以看出式子是一个递归式,知道前一项可以得出它的下一项.此外容易得出通过现有信息可以推出它的下一项,即不满足安全性要求

其生成代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class prng_lcg:
m = 672257317069504227 # "乘数"
c = 7382843889490547368 # "增量"
n = 9223372036854775783 # "模数"

def __init__(self, seed):
self.state = seed # the "seed"

def next(self):
self.state = (self.state * self.m + self.c) % self.n
return self.state
def test():
gen = prng_lcg(123) # seed = 123
print gen.next() # 第一个生成值
print gen.next() # 第二个生成值
print gen.next() # 第三个生成值

参数已知

需要知道想要求的值的前一项

Si+1=aSn+bmodNS_{i+1}=a S_{n}+b \bmod N

增量未知

需要知道连续两个值

Si+1aSn=bmodNS_{i+1}-a S_{n}=b \bmod N

即转化为问题1

模数已知

需要知道连续三个值

Si+1=aSn+bmodNSi+2=aSn+1+bmodN}Si+2Si+1=a(Sn+1Sn)modN\left.\begin{matrix} S_{i+1}=a S_{n}+b \bmod N \\ S_{i+2}=a S_{n+1}+b \bmod N \end{matrix}\right\} \Rightarrow S_{i+2}-S_{i+1}=a(S_{n+1}-S_{n}) \bmod N

再对aaNN的逆元即可转化为问题2

参数未知

至少需要知道连续四个值

构造序列T(n)=S(n+1)S(n)T(n) = S(n+1) - S(n)

t1=s2s1=(s1m+c)(s0m+c)=m(s1s0)=mt0modNt2=s3s2=(s2m+c)(s1m+c)=m(s2s1)=mt1modNt3=s4s3=(s3m+c)(s2m+c)=m(s3s2)=mt2modN\begin{aligned} &t 1=s 2-s 1=(s 1 * m+c)-(s 0 * m+c)=m *(s 1-s 0)=m * t 0 \bmod N\\ &t 2=s 3-s 2=(s 2 * m+c)-(s 1 * m+c)=m *(s 2-s 1)=m * t 1 \bmod N\\ &t 3=s 4-s 3=(s 3 * m+c)-(s 2 * m+c)=m *(s 3-s 2)=m * t 2 \bmod N \end{aligned}

得到下式

t2t0t1t1=(mmt0t0)(mt0mt0)=0modNt2*t0 - t1*t1 = (m*m*t0 * t0) - (m*t0 * m*t0) = 0 \bmod N

说明NN是左式的因数,则得出分解式后即转为问题3

当给出的数据不止四组的时候,因为所有式子都是模的NN,所以我们可以直接取最大公因数即可,代码如下

1
2
3
4
5
def lcg_unknow_all(states): # states 为列表
diffs = [s1 - s0 for s0, s1 in zip(states, states[1:])]
zeroes = [t2*t0 - t1*t1 for t0, t1, t2 in zip(diffs, diffs[1:], diffs[2:])]
modulus = abs(reduce(gmpy2.gcd, zeroes))
return solve3(modulus, states[0], states[1], states[2])

NCTF2019 LCG

image-20200420005313652

首先来了一个哈希碰撞,随后就是4种问题的组合,我们依次解决即可.

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114

# python2
import hashlib
import primefac
from pwn import *
from Crypto.Util.number import *

host, port = '127.0.0.1', 10000
r = remote(host, port)
# context.log_level = 'debug'

def proof_of_work():
print '[+] Proof of work...'
r.recvuntil('hexdigest() = ')
digest = r.recvline().strip()
r.recvuntil("s[:7].encode('hex') =")
prefix = r.recvline().strip().decode('hex')
# s = r.recvline().strip()
for suffix in range(256**3):
guess = prefix + long_to_bytes(suffix, 3)
if hashlib.sha256(guess).hexdigest() == digest:
print '[+] find: ' + guess.encode('hex')
break
r.recvuntil("s.encode('hex') = ")
# r.sendline(s)
r.sendline(guess.encode('hex'))

def solve1(N, a, b, n1):
return (n1 - b) * inverse(a, N) % N

def solve2(N, a, n1, n2):
b = (n2 - n1 * a) % N
return solve1(N, a, b, n1)

def solve3(N, n1, n2, n3):
a = (n3 - n2) * inverse(n2 - n1, N) % N
return solve2(N, a, n1, n2)


def solve4(n1, n2, n3, n4, n5, n6):
states = [n1, n2, n3, n4, n5, n6]
diffs = [s1 - s0 for s0, s1 in zip(states, states[1:])]
zeroes = [t2*t0 - t1*t1 for t0, t1, t2 in zip(diffs, diffs[1:], diffs[2:])]
modulus = abs(reduce(GCD, zeroes))
return solve3(modulus, states[0], states[1], states[2])


def challenge1():
print '[+] Solving challenge1...'
r.recvuntil('lcg.N = ')
N = int(r.recvline().strip())
r.recvuntil('lcg.a = ')
a = int(r.recvline().strip())
r.recvuntil('lcg.b = ')
b = int(r.recvline().strip())
r.recvuntil('lcg.next() = ')
next1 = int(r.recvline().strip())
init_seed = solve1(N, a, b, next1)
r.recvuntil('lcg.seed = ')
r.sendline(str(init_seed))

def challenge2():
print '[+] Solving challenge2...'
r.recvuntil('lcg.N = ')
N = int(r.recvline().strip())
r.recvuntil('lcg.a = ')
a = int(r.recvline().strip())
r.recvuntil('lcg.next() = ')
next1 = int(r.recvline().strip())
r.recvuntil('lcg.next() = ')
next2 = int(r.recvline().strip())
init_seed = solve2(N, a, next1, next2)
r.recvuntil('lcg.seed = ')
r.sendline(str(init_seed))


def challenge3():
print '[+] Solving challenge3...'
r.recvuntil('lcg.N = ')
N = int(r.recvline().strip())
r.recvuntil('lcg.next() = ')
next1 = int(r.recvline().strip())
r.recvuntil('lcg.next() = ')
next2 = int(r.recvline().strip())
r.recvuntil('lcg.next() = ')
next3 = int(r.recvline().strip())
init_seed = solve3(N, next1, next2, next3)
r.recvuntil('lcg.seed = ')
r.sendline(str(init_seed))

def challenge4():
print '[+] Solving challenge4...'
r.recvuntil('lcg.next() = ')
next1 = int(r.recvline().strip())
r.recvuntil('lcg.next() = ')
next2 = int(r.recvline().strip())
r.recvuntil('lcg.next() = ')
next3 = int(r.recvline().strip())
r.recvuntil('lcg.next() = ')
next4 = int(r.recvline().strip())
r.recvuntil('lcg.next() = ')
next5 = int(r.recvline().strip())
r.recvuntil('lcg.next() = ')
next6 = int(r.recvline().strip())
init_seed = solve4(next1, next2, next3, next4, next5, next6)
r.recvuntil('lcg.seed = ')
r.sendline(str(init_seed))

proof_of_work()
challenge1()
challenge2()
challenge3()
challenge4()
r.interactive()

得到flag

image-20200420005710576

评论