LCG算法

Crypto学习记录 LCG

Created At : 2023-04-27 20:18

Count:1.8k Views 👀 :

LCG
计算公式
例题
1. LCG1
2. LCG2
3. LCG3
4. LCG4
5. LCG5
6. LCG6
二元LCG
三元LCG

LCG

LCG（线性同余方法），用于产生伪随机数。定义了三个整数乘数a，增量b，模数m。

在LCG算法中，生成的随机数序列是有限的，并且会不断地重复这个序列，即为周期。周期最大为m，但大部分情况都会少于m。要令LCG达到最大周期，应符合以下条件：

b、m互质
m的所有质因数都能整除a-1
若m是4的倍数，a-1也是
a,b,$X_0$都比m小
a，b是正整数

参考：线性同余方法 - 维基百科，自由的百科全书 (wikipedia.org)

计算公式

$X_{n+1} = (aX_n+b) \space mod \space m$

给了一个随机数是$X_n$，可通过此公式计算下一个随机数。

各参数计算公式：

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

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

求a

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

求b

$b = (X_{n+1}-aX_n) \space mod \space m$

求m

$t=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}))$

例题

找些题目来帮助理解：

LCG1

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

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

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

seed = 33477128523140105764301644224721378964069
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 =  33477128523140105764301644224721378964069
# a =  216636540518719887613942270143367229109002078444183475587474655399326769391
# b =  186914533399403414430047931765983818420963789311681346652500920904075344361
# n =  155908129777160236018105193822448288416284495517789603884888599242193844951
# c =  209481865531297761516458182436122824479565806914713408748457524641378381493

seed、a、b、n都给了，按顺序求出10轮后的seed，再与ciphertext异或即可。

LCG2

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

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 =  59398519837969938359106832224056187683937568250770488082448642852427682484407513407602969
# b =  32787000674666987602016858366912565306237308217749461581158833948068732710645816477126137
# n =  43520375935212094874930431059580037292338304730539718469760580887565958566208139467751467
# c =  8594514452808046357337682911504074858048299513743867887936794439125949418153561841842276

不知道初始seed（明文），但知道10轮LCG后的结果，利用$X_{n+1}反推X_{n}$公式求明文，注意求出a的逆元：

a = ...
b = ...
n = ...
c = ...

a_ni = inverse(a,n)
seed = c
for i in range(10):
    seed = (a_ni*(seed-b))%n
print(long_to_bytes(seed))

LCG3

from Crypto.Util.number import *
flag = b'Spirit{*********************}'
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 =  3227817955364471534349157142678648291258297398767210469734127072571531
# n =  2731559135349690299261470294200742325021575620377673492747570362484359
# output1 =  56589787378668192618096432693925935599152815634076528548991768641673
# output2 =  2551791066380515596393984193995180671839531603273409907026871637002460

同样10轮LCG，不过只给了中间第7和第8轮的结果，有下面的关系：

$X_7 = (aX_6+b)mod n$

$\Rightarrow b = (X_7-aX_6)modn$

a =  ...
n =  ...
output1 = ...
output2 = ...
b = (output2-a*output1)%n
print(long_to_bytes(b))

LCG4

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

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 =  714326667532888136341930300469812503108568533171958701229258381897431946521867367344505142446819
# output =  [683884150135567569054700309393082274015273418755015984639210872641629102776137288905334345358223, 285126221039239401347664578761309935673889193236512702131697050766454881029340147180552409870425, 276893085775448203669487661735680485319995668779836512706851431217470824660349740546793492847822, 670041467944152108349892479463033808393249475608933110640580388877206700116661070302382578388629, 122640993538161410588195475312610802051543155060328971488277224112081166784263153107636108815824, 695403107966797625391061914491496301998976621394944936827202540832952594905520247784142392337171, 108297989103402878258100342544600235524390749601427490182149765480916965811652000881230504838949, 3348901603647903020607356217291999644800579775392251732059562193080862524671584235203807354488, 632094372828241320671255647451901056399237760301503199444470380543753167478243100611604222284853, 54758061879225024125896909645034267106973514243188358677311238070832154883782028437203621709276]

知道每一轮LCG的结果，利用公式$a = ((X_{n+2}-X_{n+1})(X_{n+1}-X_{n})^{-1}) \space mod \space m$，任意选取三个seed求解a，接着求出b，最后解flag：

n = ...
output = [...]

a = inverse((output[0]-output[1]),n)*(output[1]-output[2]) % n
b = inverse(a,n)*output[1]-output[0] % n

flag = (inverse(a,n)*output[0]-b) % n
print(long_to_bytes(flag))

LCG5

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

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 =  [9997297986272510947766344959498975323136012075787120721424325775003840341552673589487134830298427997676238039214108, 4943092972488023184271739094993470430272327679424224016751930100362045115374960494124801675393555642497051610643836, 6774612894247319645272578624765063875876643849415903973872536662648051668240882405640569448229188596797636795502471, 9334780454901460926052785252362305555845335155501888087843525321238695716687151256717815518958670595053951084051571, 2615136943375677027346821049033296095071476608523371102901038444464314877549948107134114941301290458464611872942706, 11755491858586722647182265446253701221615594136571038555321378377363341368427070357031882725576677912630050307145062, 7752070270905673490804344757589080653234375679657568428025599872155387643476306575613147681330227562712490805492345, 8402957532602451691327737154745340793606649602871190615837661809359377788072256203797817090151599031273142680590748, 2802440081918604590502596146113670094262600952020687184659605307695151120589816943051322503094363578916773414004662, 5627226318035765837286789021891141596394835871645925685252241680021740265826179768429792645576780380635014113687982]

只知道每一轮LCG的结果，利用公式

$t=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}))$直接求模数：

output = ...

t = []
for i in range(len(output)-1):
    t.append(output[i+1] - output[i])
n_list = []

i = 2
while i<len(t)-1:
    n_list.append(gcd((t[i+1]*t[i-1]-t[i]*t[i]), (t[i]*t[i-2]-t[i-1]*t[i-1])))
    i+=1

有了n，就用LCG4一样的解法了，会有一样的n，遍历所有的结果，选出正确的：

for n in n_list:
    a = inverse((output[0] - output[1]), n) * (output[1] - output[2]) % n
    b = inverse(a, n) * output[1] - output[0] % n

    flag = (inverse(a, n) * output[0] - b) % n
    if b'{' in long_to_bytes(flag):
        print(long_to_bytes(flag))

参考：(6条消息) ctf之lcg算法_ctf lcg_小健健健的博客-CSDN博客

LCG6

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

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 =  731111971045863129770849213414583830513204814328949766909151
# b =  456671883153709362919394459405008275757410555181682705944711
# n =  666147691257100304060287710111266554526660232037647662561651
# output =  [16985619148410545083429542035273917746612, 32633736473029292963326093326932585135645, 20531875000321097472853248514822638673918, 37524613187648387324374487657224279011, 21531154020699900519763323600774720747179, 1785016578450326289280053428455439687732, 15859114177482712954359285501450873939895, 10077571899928395052806024133320973530689, 30199391683019296398254401666338410561714, 21303634014034358798100587236618579995634]

a、b、n都有，还有每一轮得到的数进行右移64位的结果。

一开始我想构造copper解，但解不出来，后面我偶然翻到一篇讲hnp问题的文章，发现讲的例题和这道有类似的部分，看来得用到格。

浅尝 Lattice 之 HNP-安全客 - 安全资讯平台 (anquanke.com)

决定单独把这篇文章拿出来。

二元LCG

相较于普通LCG，只是多了一组生成器，本质还是一样，推出相关等式求出系数。一道例题：

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

因为data前两个数用到了seed1和seed2，这两数未知，所以我们列出其它三个数间的计算关系：

$data[2] = (adata[1] + bdata[0] + c) \space mod \space n$

$data[3] = (adata[2] + bdata[1] + c) \space mod \space n$

$data[4] = (adata[3] + bdata[2] + c) \space mod \space n$

接着我们存储相邻data相减的值，即：

$tmp[1] = data[1] - data[0]$

$tmp[2] = data[2] - data[1]$

$tmp[3] = data[3] - data[2]$

$tmp[4] = data[4] - data[3]$

对于求a，带入data化简得：

$tmp[3] = (atmp[2] + btmp[1]) \space mod \space n$，记为一式

$tmp[4] = (atmp[3] + btmp[2]) \space mod \space n$，记为二式

一式乘上$tmp[2]$，二式乘上$tmp[1]$，相减把含b的部分去掉，得到只含a的关系：

$tmp[2]tmp[3] - tmp[1]tmp[4] = a(tmp[2]tmp[2] - tmp[1]tmp[3]) \space mod \space n$

对右边那部分求逆即可，求b、c的方法类似，不写了。

wp：

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]) * invert(tmp[2] * tmp[2] - tmp[1] * tmp[3],n) % n
b = (tmp[3] - a * tmp[2]) * invert(tmp[1],n) % n
c = (data[4] - a * data[3] - b * data[2]) % n

解释下求a、b、c的式子怎么来的：

三元LCG

大差不差，贴一下：


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)

wp:

参考：Crypto-LCG（线性同余方程） | 此间的少年 (gitee.io)

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1666739907@qq.com