LCG（线性同余生成器）简记

标签（空格分隔）： LCG

LCG(线性同余生成器)

LCG属于PRNG(伪随机数生成器)和stream cipher(流密码)的一种，是一种产生伪随机数的方法。


$X_{n+1} =(a∗X_n +b) \ mod\ m$

其中，Xn代表第n个生成的随机数，X0被称为种子值。这里还定义了三个整数：a乘数、b增量、m模数，是产生器设定的常数。

1、m是随机序列的模数，必须一个大于0的正整数。一般是一个比较大的素数或者是2的幂，以便提供较长的周期长度。
2、a是乘数，必须是一个与m互素的正整数。
3、b是增量，也必须是一个与m互素的正整数。
4、$t_n$ = $X_{n+1}$ -$X_{n}$,同理$t_{n-1}$=$X_{n}$ -$X_{n-1}$

求其中参数公式如下

由$X_n$反推$X_{n+1}$

$X_{n} = a^{-1}*(X_{n+1} -b) \mod m$

Ps：**$a^{-1}$是a的逆元**

求a

求a可以表示为

$a=t_{n-1}^{-1}*t_{n} \ mod \ m$

Ps：**$t_{n-1}^{-1}$是$t_{n-1}$的逆元**


求b

$b = (X_{n+1} - a*X_{n}) \ mod \ m$

求m

$t_{n}=X_{n+1}-X_{n}=(a*X_n+b)-(a*X_{n-1}+b)=a*(X_n-X_{n-1})=a*t_{n-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 \mod m$

即$T_n = t_{n+1} t_{n-1} - t_n^2$是 m 的倍数，故$T_n 和 T_{n-1}$的最大公因数即为 m

例题

实际做题的话碰到直接给了a,b,m这些便很好解决如果是碰上别的如：

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
from secrets import randbits
from secret import FLAG, P_known


def gen():
    while True:
        m = randbits(63) | (1 << 62) | 1
        if m > 2**62:
            break
    a = randbits(62) | 3
    c = randbits(62) | 1
    s0 = randbits(62) | 5
    return m, a, c, s0

def LCG(m, a, c, s0, nblocks):
    x = s0
    out = []
    for _ in range(nblocks):
        x = (a * x + c) % m
        out.append(x)
    return out

def encrypt(m, a, c, s0, plaintext: bytes) -> bytes:
    padlen = (-len(plaintext)) % 8
    pt = plaintext + b'\x00' * padlen
    blocks = [int.from_bytes(pt[i:i+8], 'big') for i in range(0, len(pt), 8)]
    ks = LCG(m, a, c, s0, len(blocks))
    cblocks = [b ^ k for b, k in zip(blocks, ks)]
    return b''.join(cb.to_bytes(8, 'big') for cb in cblocks)

def main():
    m, a, c, s0 = gen()
    cipher  = encrypt(m, a, c, s0,  P_known + FLAG)

    C_known = cipher[:len(P_known)]
    C_flag  = cipher[len(P_known):len(P_known) + len(FLAG)]

    print("P_known =",P_known)
    print("C_known =", C_known.hex())
    print("C_flag  =", C_flag.hex())

if __name__ == "__main__":
    main()


'''

P_know = b'Insecure_linear_congruential_random_number!!!!!!'
C_known = 44e18dfa1acd14aa790fc3bac4ca54c137bcd47bdfc2209a53b83715ecad3e29249845720588cac007bfb94f8476d91a
C_flag  = 1995374a5b64c6696578c1d5bdc6fa3d1e974b813436eab4348db801fb7a6703658eaa4fefa2c6fd6792beb969df8ca70ad87a4f4aea6ca0040d65a3c1e3a5bf2655cafc1e5603a171edc9aa077c0ca264677c351907f35756c14dd7ece428cb424a3804b544ccb53e99935f9bc2d8483dd7587379c99b3542c222008a

'''

这个便是已知明文攻击，将明文和密文已知部分进行异或便能得到一部分的$X_{n}$
然后再是正常解题
exp:

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
from secrets import randbits
import sys
from functools import reduce
from math import gcd
import gmpy2
p_know = b'Insecure_linear_congruential_random_number!!!!!!'
c_know = '44e18dfa1acd14aa790fc3bac4ca54c137bcd47bdfc2209a53b83715ecad3e29249845720588cac007bfb94f8476d91a'
c_flag  =  '1995374a5b64c6696578c1d5bdc6fa3d1e974b813436eab4348db801fb7a6703658eaa4fefa2c6fd6792beb969df8ca70ad87a4f4aea6ca0040d65a3c1e3a5bf2655cafc1e5603a171edc9aa077c0ca264677c351907f35756c14dd7ece428cb424a3804b544ccb53e99935f9bc2d8483dd7587379c99b3542c222008a'

c_know = bytes.fromhex(c_know)
c_flag = bytes.fromhex(c_flag)

c_know=[int.from_bytes(c_know[i:i+8], 'big') for i in range(0, len(c_know), 8)]
p_know=[int.from_bytes(p_know[i:i+8], 'big') for i in range(0, len(p_know), 8)]

box = [p ^ c for p, c in zip(p_know, c_know)]
t = [box[i+1]-box[i] for i in range(len(box)-1)]
T1= t[3]*t[1]-t[2]*t[2]
T2= t[4]*t[2]-t[3]*t[3]

def egcd(a,b):
    if a==0 :
        return b
    else :
        return gcd(b%a,a)

m=egcd(T1,T2)
print(m)

t1=box[2]-box[1]
t0=box[1]-box[0]
a=gmpy2.divm(t1,t0,m)
print(a)

b=(box[2]-box[1]*a)%m
print(b)

def LCG(m, a, c, s0, nblocks):
    x = s0         
    out = []      
    for _ in range(nblocks):
        out.append(x)           
        x = (a * x + c) % m     
    return out

abox = LCG(m, a, b, box[0], 22)

abox = LCG(m, a, b, box[0], 22)
raw_c_know = bytes.fromhex('44e18dfa1acd14aa790fc3bac4ca54c137bcd47bdfc2209a53b83715ecad3e29249845720588cac007bfb94f8476d91a')
raw_c_flag = bytes.fromhex('1995374a5b64c6696578c1d5bdc6fa3d1e974b813436eab4348db801fb7a6703658eaa4fefa2c6fd6792beb969df8ca70ad87a4f4aea6ca0040d65a3c1e3a5bf2655cafc1e5603a171edc9aa077c0ca264677c351907f35756c14dd7ece428cb424a3804b544ccb53e99935f9bc2d8483dd7587379c99b3542c222008a')

allm = raw_c_know + raw_c_flag

keystream = b''.join(k.to_bytes(8, 'big') for k in abox)


flag = bytes([c ^ k for c, k in zip(allm, keystream)])
print(flag.decode(errors='ignore'))