什么是 LCG

线性同余算法，用来生成伪随机数

线性同余法最重要的是定义了三个整数，乘数 a、增量 b 和模数 m，其中 a,b,m 是产生器设定的常数。

公式

1
X[n+1] = (aX[n]+b) mod m

其中 a,b,m 是三个用来生成伪随机数的常量

举个例子，就是上一个数是 114，设 a=10，b=12，c=514，那么下一个伪随机数就是

（114 * 10 + 12）% 514 = 124

解题需要用到的公式

目的 公式
X [n+1] 反推 X [n] X[n] = (a** (-1) ( X[n+1] - b ) ) % m
求 a a = ( ( X[n+2] - X[n+1] ) ( X[n+1] - X[n] ) ** ( -1 ) ) % m
求 b b = ( X [n+1] - a X[n] ) % m
求 m t[n] = X[n+1] - X[n]，m = gcd ( ( t[n+1]t[n-1] - t[n]t[n] ) , ( t[n]t[n-2] - t[n-1]t[n-1] ) )

其中的 a**（-1）是 a 相对于模数 m 的逆元，求逆元可以用公式

1
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] #逆元计算

也可以使用 gmpy2 库中的 invert 函数

1
2
3
4
5
6
#求大整数x模m的逆元y
import gmpy2
#4*6 ≡ 1 mod 23
gmpy2.invert(4,23)

result = mpz(6)

0X01

最基本的 LCG 应用

题目

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

source=b"flag{*********}"
plaintext=bytes_to_long(source)
length=plaintext.bit_length()
a = getPrime(length)
b = getPrime(length)
n = getPrime(length)
seed = 3281857254
print("seed = ",seed)
for i in range(10):
    seed = (a*seed+b)%n
ciphertext = seed^plaintext
print("a = ",a)
print("b = ",b)
print("n = ",n)
print("c = ",ciphertext)
# seed =  3281857254
# a =  540148988578728116547540370955365641360430675811
# b =  691767495086914115399769389216940791240924902423
# n =  524988838768493801533758786071154204860765947187
# c =  210504742144537844110730225465101123460260815127

解题脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
PYTHON
from Crypto.Util.number import*
seed =  3281857254
a =  540148988578728116547540370955365641360430675811
b =  691767495086914115399769389216940791240924902423
n =  524988838768493801533758786071154204860765947187
c =  210504742144537844110730225465101123460260815127
for i in range(10):
	seed = (a*seed+b)%n
flag =  c ^ seed
print(long_to_bytes(flag))

#b'flag{this_is_A_text}'

0x02

最基本的应用，求逆元

题目

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
PYTHON
from Crypto.Util.number import *
flag = b'flag{*************}'

plaintext = bytes_to_long(flag)
length = plaintext.bit_length()

a = getPrime(length)
b = getPrime(length)
n = getPrime(length)

seed = plaintext

for i in range(10):
    seed = (a*seed+b)%n
ciphertext = seed

print("a = ",a)
print("b = ",b)
print("n = ",n)
print("c = ",ciphertext)
#a =  465177306335197714127135977948959896764918183621
#b =  410163845909545695877894071846498185255806129841
#n =  718249906296549710998813117372178964544291249457
#c =  646736161393062036124787920588578845245377036935

解题脚本

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

a =  465177306335197714127135977948959896764918183621
b =  410163845909545695877894071846498185255806129841
n =  718249906296549710998813117372178964544291249457
c =  646736161393062036124787920588578845245377036935

ans = gmpy2.invert(a,n)
seed = c 
for i in range(10):
	seed = (ans*(seed - b)) % n 
flag = long_to_bytes(seed)
print(flag)

#b'flag{this_is_A_text}'

0x03

已知 a，n，和部分输出结果，求 b

题目

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
from Crypto.Util.number import *
flag = b'flag{this_is_A_text}'
plaintext = bytes_to_long(flag)
length = plaintext.bit_length()

a = getPrime(length)
seed = getPrime(length)
n = getPrime(length)

b = plaintext

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

print("a = ",a)
print("n = ",n)
print("output1 = ",output[6])
print("output2 = ",output[7])
# a =  494311324877269551677692761875227614273720225803
# n =  427764786728052577084040376836259407659772630791
# output1 =  412452382152805199086179184644045600473964075622
# output2 =  66601521678090675310661017809404366200345559824

解题脚本

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

from Crypto.Util.number import *
import gmpy2
a =  384034973282686529400275953560424842172642566161
n =  587314812036577575451873015154343983685863117059
output1 =  269535569526296407654570962253353014418609448473
output2 =  462253203386219184253347510140136044427315093120

#已知a,n不知道b，求b

b = (output2 - a * output1) % n

flag= long_to_bytes(b)

print(flag)


#b'flag{this_is_A_text}'

0x04

只给了n和输出结果

题目

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

from Crypto.Util.number import *

flag = b'flag{this_is_a_text}'

plaintext = bytes_to_long(flag)
length = plaintext.bit_length()

a = getPrime(length)
b = getPrime(length)
n = getPrime(length)

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


print("n = ",n)
print("output = ",output)
# n =  599085896424860865145266447151777206117255140467
# output =  [148262107018120015989702198647095631526321494455, 231347411693927418373892434905684762038558461865, 183583807896830086337292220031812284985459192082, 227858979795784576456017038392323671993173062390, 462991408470822743345134052918261644084512155792, 585425514526866377483266602984762460627902467530, 413472724562253119787678819487304575640403316430, 451263931356487593291849094718423925413808148125, 577727356692871938694687227446301292442105105116, 3097076491426611077378108172275334829638750183]

解题脚本

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

from Crypto.Util.number import*
import gmpy2
n =  599085896424860865145266447151777206117255140467
output =  [148262107018120015989702198647095631526321494455, 231347411693927418373892434905684762038558461865, 183583807896830086337292220031812284985459192082, 227858979795784576456017038392323671993173062390, 462991408470822743345134052918261644084512155792, 585425514526866377483266602984762460627902467530, 413472724562253119787678819487304575640403316430, 451263931356487593291849094718423925413808148125, 577727356692871938694687227446301292442105105116, 3097076491426611077378108172275334829638750183]
#未知a,b
#求a
temp_1=output[0]
temp_2=output[1]
temp_3=output[2]
temp = gmpy2.invert((temp_2 - temp_1),n)
a = (temp * (temp_3 - temp_2)) % n
#求b
b = (temp_2 - a * temp_1) % n

ans= gmpy2.invert(a,n)

plaintext = (ans * (temp_1 - b)) % n
print(long_to_bytes(plaintext)) 

#b'flag{this_is_a_text}'

0x05

只给输出结果

题目

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

from Crypto.Util.number import *
flag = b'flag{this_is_A_text}'

plaintext = bytes_to_long(flag)
length = plaintext.bit_length()

a = getPrime(length)
b = getPrime(length)
n = getPrime(length)

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

print("output = ",output)
#output =  [330875235410894718431110656202775091085712343579, 234693776783263959790789380649992941515521805430, 510222815927277255176624160732162361050980242927, 123800185791875828119515172903572826221116611205, 691243560940009069435106080449371958830318872406, 207341909208395063698219222401985176654183050402, 322855546905894299222950360120836568655392882790, 163858819002800142966371893120381100654262121535, 132311867611529541744903332127948522496846295505, 72788827576169887542419201170791228486113534316]

解题脚本

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*
import gmpy2
from math import *
output =  [330875235410894718431110656202775091085712343579, 234693776783263959790789380649992941515521805430, 510222815927277255176624160732162361050980242927, 123800185791875828119515172903572826221116611205, 691243560940009069435106080449371958830318872406, 207341909208395063698219222401985176654183050402, 322855546905894299222950360120836568655392882790, 163858819002800142966371893120381100654262121535, 132311867611529541744903332127948522496846295505, 72788827576169887542419201170791228486113534316]
#全部未知，直接求a,b,m
t=[]
for i in range(9):
	t.append(output[i+1]-output[i])
n=[]
for i in range(7):
	n.append(gcd ( ( t[i+1]*t[i-1] - t[i]*t[i] ) , ( t[i]*t[i+2] - t[i+1]*t[i+1] ) ))
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] #逆元计算
#print(m)
for m in n:
	m=abs(m)
	if m==1:
		continue
	a = (t[3] * MMI(t[2],m)) % m
	b = (output[2] - a * output[1]) % m
	plaintext=(MMI(a,m) * (output[0] - b)) % m
	print(long_to_bytes(plaintext))
		
'''
b'\x0c'
b'flag{this_is_A_text}'
b'flag{this_is_A_text}'
b'\x01*\xbeW\xbd\xd5\x83\x1bl\t\x84@\xf4\x87\x12\xa8_c\x88\x9f.'
b"'&2\xfd|\xccI\x1aj\xf9\x8e\x14<3\x04h\xd0\xb0\xbf\xa5\xca"
b'\x13\x06\xf5\x08\x18\xea\xd3\xc5(k*\x01{\x83v\xaa"\t6N\n'
b'flag{this_is_A_text}'
'''

0x06

也是只给结果，但是每个结果都进行了右移操作，并不知道怎么做

题目

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

from Crypto.Util.number import *
flag = b'flag{this_is_A_text}'

plaintext = bytes_to_long(flag)
length = plaintext.bit_length()

a = getPrime(length)
b = getPrime(length)
n = getPrime(length)

seed = plaintext

output = []
for i in range(10):
    seed = (seed*a+b)%n
    output.append(seed>>64)
print("a = ",a)
print("b = ",b)
print("n = ",n)
print("output = ",output)
#a =  496936604787125536738760631047942358338849750293
#b =  382719908430154737899481642645092503143553910131
#n =  406958626075537886942920764299911286699616861233
#output =  [2324420989429376511089654996, 13261967696719873104065488480, 219962508547380574826562903

二元LCG：

就和正常推导一样配平消元就行，注意是在模意义下进行加减乘除

题目：

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
from Crypto.Util.number import*
from secret import flag
assert flag[:5] == b'cazy{'
assert flag[-1:] == b'}'
flag = flag[5:-1]
assert(len(flag) == 24)

class my_LCG:
    def __init__(self, seed1 , seed2):
        self.state = [seed1,seed2]
        self.n = getPrime(64)
        while 1:
            self.a = bytes_to_long(flag[:8])
            self.b = bytes_to_long(flag[8:16])
            self.c = bytes_to_long(flag[16:])
            if self.a < self.n and self.b < self.n and self.c < self.n:
                break
    
    def next(self):
        new = (self.a * self.state[-1] + self.b * self.state[-2] + self.c) % self.n
        self.state.append( new )
        return new

def main():
    lcg = my_LCG(getRandomInteger(64),getRandomInteger(64))
    print("data = " + str([lcg.next() for _ in range(5)]))
    print("n = " + str(lcg.n))

if __name__ == "__main__":
    main() 

# data = [2626199569775466793, 8922951687182166500, 454458498974504742, 7289424376539417914, 8673638837300855396]
# n = 10104483468358610819

exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from Crypto.Util.number import *
import gmpy2
data = [2626199569775466793, 8922951687182166500, 454458498974504742, 7289424376539417914, 8673638837300855396]
n = 10104483468358610819
print(getRandomInteger(64))
print(len(data))
tmp = [0]
for i in range(1,5):
    tmp.append(data[i] - data[i - 1])
a = (tmp[2] * tmp[3] - tmp[1] * tmp[4]) * gmpy2.invert(tmp[2] * tmp[2] - tmp[1] * tmp[3],n) % n
b = (tmp[3] - a * tmp[2]) * gmpy2.invert(tmp[1],n) % n
c = (data[4] - a * data[3] - b * data[2]) % n
print(a,b,c)
print(b'cazy{' + long_to_bytes(a) + long_to_bytes(b) + long_to_bytes(c) + b'}')

三阶LCG：

方法一样，回退即可。

例题：

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

from Crypto.Util.number import *
from secret import FLAG
p = getPrime(128)
step = len(FLAG) // 3
xs = [bytes_to_long(FLAG[:step]), bytes_to_long(FLAG[step:2*step]), bytes_to_long(FLAG[2*step:])]
a = getPrime(64)
b = getPrime(64)
c = getPrime(64)
a = 18038175596386287827
b = 15503291946093443851
c = 17270168560153510007
p = 307956849617421078439840909609638388517

for _ in range(10):
    new_state = (a*xs[0] + b*xs[1] + c*xs[2]) % p
    xs = xs[1:] + [new_state]
    #print(xs)
print(xs)
print(a, b, c, p)

解释：每次将新生成的xn替换到xs的第三位上，前两位分别是上一次的二三位。

依次从x8，9，10还原7 回退到 7，8，9 以此类推推出初始xs。

exp：

xbWoh8.png

变种

已知num2，num3，返回值num4，最初的num1是flag。

这里num2 = p * q(p,q已知)

1
2
3
4
5
6
7
8
def crypto01(number1, number2, number3):
    number4 = 1
    while number2 > 0:
        if number2 % 2:
            number4 = (number4 * number1) % number3
        number1 = number1 ** 2 % number3
        number2 //= 2
    return number4

思路：

  1. 计算模数：我们知道 num2 = p × q，因此可以将方程拆分为两个部分： m^num1 ≡ number4 (mod p)
    m^num1 ≡ number4 (mod q)

  2. 求解：分别在模 p 和模 q 下求解 m，然后通过中国剩余定理（CRT）合并结果。

  3. 找到 m mod p 和 m mod q：使用费马小定理来求解：

    m^num1 ≡ number4 (mod p) ⇒ m ≡ number4^(num1^(-1) (mod (p-1))) (mod p)
    m^num1 ≡ number4 (mod q) ⇒ m ≡ number4^(num1^(-1) (mod (q-1))) (mod q)

  4. 合并结果：使用中国剩余定理找到一个 m 的唯一解。

通过以上步骤，可以求出 m。

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
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def extended_gcd(a, b):
    if a == 0:
        return b, 0, 1
    g, x1, y1 = extended_gcd(b % a, a)
    x = y1 - (b // a) * x1
    y = x1
    return g, x, y


def mod_inverse(a, m):
    g, x, _ = extended_gcd(a, m)
    if g != 1:
        raise Exception('Modular inverse does not exist')
    else:
        return x % m


def chinese_remainder_theorem(a1, n1, a2, n2):
    # CRT algorithm to solve x ≡ a1 (mod n1) and x ≡ a2 (mod n2)
    M = n1 * n2
    M1 = M // n1
    M2 = M // n2
    inv1 = mod_inverse(M1, n1)
    inv2 = mod_inverse(M2, n2)

    x = (a1 * M1 * inv1 + a2 * M2 * inv2) % M
    return x


def find_initial_m(number4, num1, p, q):
    # Step 1: Compute inverses of num1 mod (p-1) and (q-1)
    num1_inv_p = mod_inverse(num1, p - 1)
    num1_inv_q = mod_inverse(num1, q - 1)

    # Step 2: Find m mod p and mod q
    m_p = pow(number4, num1_inv_p, p)
    m_q = pow(number4, num1_inv_q, q)

    # Step 3: Use CRT to find m
    initial_m = chinese_remainder_theorem(m_p, p, m_q, q)
    return initial_m

number4 = 15975320168441172285869762341064938287855372848675022103744830217232989597313267453437134835870877830933688232789859315853003181327156055541273898780260821173896629315608924504189178086614088211755647840697836478508245284386556510815441983677066863017854347953070929952765898433026656636114408831060022678053064
num1 = 6035830951309638186877554194461701691293718312181839424149825035972373443231514869488117139554688905904333169357086297500189578624512573983935412622898726797379658795547168254487169419193859102095920229216279737921183786260128443133977458414094572688077140538467216150378641116223616640713960883880973572260683
num2 = 20163906788220322201451577848491140709934459544530540491496316478863216041602438391240885798072944983762763612154204258364582429930908603435291338810293235475910630277814171079127000082991765275778402968190793371421104016122994314171387648385459262396767639666659583363742368765758097301899441819527512879933947
c = 15975320168441172285869762341064938287855372848675022103744830217232989597313267453437134835870877830933688232789859315853003181327156055541273898780260821173896629315608924504189178086614088211755647840697836478508245284386556510815441983677066863017854347953070929952765898433026656636114408831060022678053064

m = find_initial_m(number4, num1, p, q)
print(long_to_bytes(m))