LCG

笔记
发布时间 :
字数:928 阅读 :
  1. LCG-1
  2. LCG-2
  3. LCG-3
  4. LCG-4

线性同余法（LCG）是一种产生伪随机数的方法。

\(x_{n+1} = (ax_n + b)\ \%\ p\)

主要的求解公式：

求解 公式
\(x_n\) \(x_n = a^{-1} (x_{n+1} - b)\ \%\ p\)
a \(a = (x_{n+2} - x_{n+1}) \cdot (x_{n+1} - x_n)^{-1}\ \%\ p\)
b \(b = (x_{n+1} - ax_n)\ \%\ p\)
p \(t_n = x_{n+1} - x_n\)，\(p = \gcd (t_{n+1} t_{n-1} - t_n^2,\ t_n t_{n-2} - t_{n-1}^2)\)

根据lcg算法主要有4种ctf题型：

LCG-1

已知a，b，p，最后的seed

from Crypto.Util.number import *

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

a = 155971836487521127413178805566278019291810483723477332740305259
b = 202084599085918621034388670259032014348708452871335919618754423
p = 199296574393235855574369935471815490856316662404539770651985589

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

print("seed =", seed)
# seed = 68551282599199125993658805253274162071651594471901897411266172

解题脚本

from Crypto.Util.number import *

a = 155971836487521127413178805566278019291810483723477332740305259
b = 202084599085918621034388670259032014348708452871335919618754423
p = 199296574393235855574369935471815490856316662404539770651985589

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]  #逆元计算
ani = MMI(a, p)
seed = 68551282599199125993658805253274162071651594471901897411266172

for i in range(10):
    seed = (ani * (seed - b)) % p

print(long_to_bytes(seed))
# b'flag{This_is_a_test_flag!}'

LCG-2

已知a，p，output[]的至少连续2个元素

from Crypto.Util.number import *

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

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

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

print("output6 =", output[6])
print("output7 =", output[7])
# output6 = 45745972511051576017008610408791747592523694924890977868463767
# output7 = 47022551472047051529936224993657475046232093691394911203042968

解题脚本

from Crypto.Util.number import *

a = 164031293329341681517343090279314923560076759098650542522957107
# b = getPrime(length)
p = 205493536419436317448904933834796929859527270820306334380668191

output6 = 45745972511051576017008610408791747592523694924890977868463767
output7 = 47022551472047051529936224993657475046232093691394911203042968
gift = [output6, output7]

#求b
b = (gift[1] - a * gift[0]) % p

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]  #逆元计算
ani = MMI(a, p)
seed = gift[0]

for i in range(7):
    seed = (ani * (seed - b)) % p

print(long_to_bytes(seed))
# b'flag{This_is_a_test_flag!}'

LCG-3

已知p，output[]的至少连续3个元素

from Crypto.Util.number import *

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

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

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

print("output6 =", output[6])
print("output7 =", output[7])
print("output8 =", output[8])
# output6 = 158657126406132303164720900786306081992669207557561976396601882
# output7 = 173086776808844203987690862148966917477329732513213152207487530
# output8 = 177076590008214173673645268154603521522421695802860665456135973

解题脚本

from Crypto.Util.number import *

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

output6 = 158657126406132303164720900786306081992669207557561976396601882
output7 = 173086776808844203987690862148966917477329732513213152207487530
output8 = 177076590008214173673645268154603521522421695802860665456135973
gift = [output6, output7, output8]

#求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(7):
    seed = (ani * (seed - b)) % p

print(long_to_bytes(seed))
# b'flag{This_is_a_test_flag!}'

LCG-4

已知output[]的至少连续5个元素（尽量多）

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]

解题脚本

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!}'
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以邮件至 skatexu@qq.com

文章标题:LCG

字数:928

本文作者:skateXu

发布时间:2023-10-14, 10:18:47

最后更新:2023-11-21, 13:21:23

原始链接:http://example.com/2023/10/14/LCG/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

©2023- skateXu

Built with Hexo and 3-hexo theme