LCG笔记

LCG，全称线性同余方发生器（Linear congruential generator），是一种伪随机序列生成器算法，生成器由下式定义：

$$X_{n+1}\equiv aX_n+b\ (mod\ p)$$

在CTF中，一般有以下题型：

一.求逆

所谓求逆，其实即为已知a,b,p,c后求解方程：

$$c\equiv(ax+b)\ (mod\ p)$$

由数论知识我们很容易可以知道：

$$x\equiv(c-b)a^{-1}\ (mod\ p)$$

对于这类题目，我们只需利用以上公式即可快速解出。

二.求参数a,b后求逆

这类题型一般都会给出一列连续经过几次线性同余的数据后得出的数据和p，我们需要通过这些有限的数据来求解原来的数据，在此之前我们需要先求解a和b，大致过程如下：

假设已知$x_{n},x_{n+1},x_{n+2}$，我们有：

$$x_{n+1}\equiv ax_n+b\ (mod\ p)\\ x_{n+2}\equiv ax_{n+1}+b\ (mod\ p)$$

所以我们有：

$$x_{n+2}-x_{n+1}\equiv a(x_{n+1}-x_n)\ (mod\ p)$$

所以：

$$a\equiv (x_{n+2}-x_{n+1})(x_{n+1}-x_n)^{-1}\ (mod\ p)(假定(x_{n+1}-x_n)与p互质)$$

那么我们有：

$$b\equiv x_{n+1}-ax_n\ (mod\ p)$$

这样我们就可以得到a,b，再通过求逆得出原来的数据即可。

例：[Newstar CTF2023]Week3 babyrandom

加密代码：

#!/usr/bin/python3
from secret import flag
from Crypto.Util.number import *
from random import randrange

p = 64999433139797068147576269731948390094958654326970231465808792590598519729077

a = randrange(2, p)
b = randrange(2, p)
x = bytes_to_long(flag)
menu = '''

Random as a Service with LCG backend

Enter your option
1. Reset
2. Get
3. Exit
'''

def GetRandom():
    global x
    nx = (a*x + b) % p
    print(nx)
    x = nx
    
while True:
    print(menu)
    opt = input('> ')
    try:
        opt = int(opt)
        if opt == 1:
            x = bytes_to_long(flag)
        elif opt == 2:
            GetRandom()
        elif opt == 3:
            break
        else:
            print('invalid option')
    except Exception as e:
        print('oh no, something wrong!')
        print(e)
        

这道题提供了靶机，可以通过靶机得出三个连续加密后数据，解密代码如下：

import pwn
from Crypto.Util.number import *
import gmpy2
x = []
p = 64999433139797068147576269731948390094958654326970231465808792590598519729077
io = pwn.remote("node4.buuoj.cn",25624)
io.recv()
io.sendline(b'1')
io.recv()
for _ in range(3):
    io.sendline(b'2')
    data = io.recvline()
    io.recv()
    x.append(int(data))
io.sendline(b'3')
a = (x[2]-x[1])*gmpy2.invert(x[1]-x[0],p)%p
b = (x[1]-a*x[0])%p
x = (x[0]-b)*gmpy2.invert(a,p)%p
print(long_to_bytes(x))

运行可得flag：

flag{lcg_1s_n0t_s3cur3#fb528ba5}

三.求参数a,b,p后求逆

与上一种形式相似，但是多了个p要求，我们假设一个数列：

$$\{x_0,x_1,x_2,\cdots,x_{n-1},x_{n},\cdots\}$$

其满足：

$$x_{n+1}\equiv ax_n+b\ (mod\ p)$$

假设有一个数列 $\{t_n\}$ 有：

$$t_n\equiv x_{n+1}-x_n\equiv a(x_n-x_{n-1})\equiv at_{n-1}\ (mod\ p)$$

所以：

$$t_{n+1}t_{n-1}\equiv a^{2}t_{n-1}^2\equiv t_n^2\ (mod\ p)$$

也就是说：

$$t_{n+1}t_{n-1}-t_n^{2}=kp\ (k\in Z)$$

同理，有：

$$t_{n+2}t_{n}-t_{n+1}^{2}=k'p\ (k'\in Z)$$

所以：

$$p=gcd(t_{n+2}t_{n}-t_{n+1}^{2},t_{n+1}t_{n-1}-t_n^{2})$$

求出p后我们就可以由上种类型继续求解。

但是要注意，上面求出的p不一定就是实际要求的p，所以需要综合多组数据求解。

例：[PCTF2023]cgl

加密代码：

from Crypto.Util.number import *
import base64
from random import *
from secrets import flag,hint,key_number

hint=bytes_to_long(hint)

a = getPrime(256)
b = getPrime(256)
n = getPrime(256)

state = hint
result = []
for _ in range(5):
    state = (state * a + b) % n
    result.append(state)

print(result)


enc=list(base64.b64encode(flag))
seed(key_number)
shuffle(enc)

print(bytes(enc))
"""
[64808739969023370119048821688797617211776674130654821075486774236651303382814, 
79259085906502785899793009961165414442137337544515472474317826031734962148580, 
47572752582229256276978761367590954300620113464013293239765792280017260371290, 
38491979589561565391093783861378040494484383004914878495301417593240442882761, 
58955289126482266943455593731576872529828229203595014577711629479455475819111]
b'QkiTMMx3St9IYTLMN2DmR0t53zd1MhmJT1hZ2YiwMZETVhwhOGYVZYcD'
"""

这道题很明显要通过上述方法来求解hint，在这里我们只求解hint，求解代码如下：

from Crypto.Util.number import *
import gmpy2
x = [64808739969023370119048821688797617211776674130654821075486774236651303382814, 
79259085906502785899793009961165414442137337544515472474317826031734962148580, 
47572752582229256276978761367590954300620113464013293239765792280017260371290, 
38491979589561565391093783861378040494484383004914878495301417593240442882761, 
58955289126482266943455593731576872529828229203595014577711629479455475819111]
t = []
for i in range(4):
    t.append(x[i+1]-x[i])
for i in range(1,2):
    p = gmpy2.gcd(t[i+2]*t[i]-t[i+1]*t[i+1],t[i+1]*t[i-1]-t[i]*t[i])
    a = (x[2]-x[1])*gmpy2.invert(x[1]-x[0],p)%p
    b = (x[1]-a*x[0])%p
    x = (x[0] - b) * gmpy2.invert(a, p) % p
    print(long_to_bytes(x))

运行可以得出hint：

key_number=randrange(999999)

要注意的是：在这种情况下，$\{x_n\}$的元素数量应该至少要有5个才能求解出p。