LCG

发表于 阅读次数： Waline： 本文字数： 4k 阅读时长 ≈ 15 分钟

LCG学习过程，并对常见题型进行整合

发表于2023年7月5日。于2024年7月16日进行更新

原理简介

LCG(线性同余随机数生成器)，原理就是下面这个公式
$$
X_{n+1} \equiv aX_n+b (mod \quad m)
$$

其中,$m$表示模数$(m>0)$，$a$表示系数$(0<a<m)$，$b$表示增量$(0\le b <m)$，$X_0$表示原始值，也叫种子$(0 \le X_0 < m)$

题型1:给出seed,要求若干次迭代后的值

这类题很简单，seed都给了，只需要按公式往后迭代即可

例题

task.py

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'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

思路很简单，题目把所有参数都给出了，我们只需要按照公式求出10次迭代后的seed，然后和ciphertext异或即可得到flag

exp.py

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

a =  216636540518719887613942270143367229109002078444183475587474655399326769391
b =  186914533399403414430047931765983818420963789311681346652500920904075344361
n =  155908129777160236018105193822448288416284495517789603884888599242193844951
seed = 33477128523140105764301644224721378964069
for i in range(10):
    seed = (a*seed + b)%n

c = 209481865531297761516458182436122824479565806914713408748457524641378381493
m = c ^ seed
print(long_to_bytes(m))

#Spirit{0ops!___you_know__LCG!!}

题型2:已知后项求前项

例题

task.py

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'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

题目给出10次迭代后的seed，以及$a,b,n$三个参数，要求我们求出原始的seed
$$
\because X_{n+1} \equiv aX_n + b \mod n
$$

$$
\therefore aX_n \equiv X_{n+1}-b \mod n
$$

$$
\therefore X_n \equiv (X_{n+1}+b)\times a^{-1} \mod n
$$

通过这个公式就可以往前迭代了

exp.py

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

a =  59398519837969938359106832224056187683937568250770488082448642852427682484407513407602969
b =  32787000674666987602016858366912565306237308217749461581158833948068732710645816477126137
n =  43520375935212094874930431059580037292338304730539718469760580887565958566208139467751467
c =  8594514452808046357337682911504074858048299513743867887936794439125949418153561841842276

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

print(long_to_bytes(seed))
# Spirit{Orzzz__number_the0ry_master!!}

题型3:求增量b

例题

task.py

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
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

题目给出参数$a,n$，以及两个seed的状态，要求我们计算增量b
$$
\because X_{n+1} \equiv aX_n +b \mod n
$$

$$
\therefore b \equiv X_{n+1} - aX_n \mod n
$$

exp.py

1
2
3
4
5
6
7
8
9
10
11
from Crypto.Util.number import *

a =  3227817955364471534349157142678648291258297398767210469734127072571531
n =  2731559135349690299261470294200742325021575620377673492747570362484359
output1 =  56589787378668192618096432693925935599152815634076528548991768641673
output2 =  2551791066380515596393984193995180671839531603273409907026871637002460

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

# Spirit{Y0u_@r3_g00d_at__math}

题型4:未知a,b求seed

例题

task.py

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 *
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]

题目给出了seed十个状态的值以及$n$,要求我们计算初始的seed。往前迭代需要参数$a,b$，我们先计算$a,b$

由
$$
X_{n+1} \equiv aX_n +b \mod n
$$

$$
X_{n+2} \equiv aX_{n+1} +b \mod n
$$

两式相减得到
$$
X_{n+2}-X_{n+1} \equiv a(X_{n+1}-X_n) \mod n
$$

$$
\therefore a\equiv (X_{n+2}-X_{n+1})\times (X_{n+1}-X_n)^{-1} \mod n
$$

计算出$a$之后，我们再根据$b \equiv X_{n+1}-aX_n \mod n$计算$b$

exp.py

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 long_to_bytes
import gmpy2

n =  714326667532888136341930300469812503108568533171958701229258381897431946521867367344505142446819
output =  [683884150135567569054700309393082274015273418755015984639210872641629102776137288905334345358223, 285126221039239401347664578761309935673889193236512702131697050766454881029340147180552409870425, 276893085775448203669487661735680485319995668779836512706851431217470824660349740546793492847822, 670041467944152108349892479463033808393249475608933110640580388877206700116661070302382578388629, 122640993538161410588195475312610802051543155060328971488277224112081166784263153107636108815824, 695403107966797625391061914491496301998976621394944936827202540832952594905520247784142392337171, 108297989103402878258100342544600235524390749601427490182149765480916965811652000881230504838949, 3348901603647903020607356217291999644800579775392251732059562193080862524671584235203807354488, 632094372828241320671255647451901056399237760301503199444470380543753167478243100611604222284853, 54758061879225024125896909645034267106973514243188358677311238070832154883782028437203621709276]

p1 = output[9]-output[8]
p2 = output[8]-output[7]

Ani = gmpy2.invert(p2,n)
a = p1 * Ani % n

b = (output[9] - a*output[8]) % n

ani = gmpy2.invert(a,n)

m = ani * (output[0]-b) % n

print(long_to_bytes(m))

# Spirit{Gr3at__J0b!_You_can_be___better!}

题型5:未知a,b,n求seed

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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]

这道题目比上面那道更加苛刻，只给出了10个seed的状态，却要要求我们计算初始的seed。

根据上道题的经验，我们需要先求出$n$，再计算$a,b$最后往前迭代求seed

先令$t_n = X_{n+1}-X_n$
$$
\therefore t_n \equiv a(X_n+b) -a(X_{n-1}+b) \mod n
$$
即
$$
t_n \equiv a(X_n-X_{n-1}) \mod n
$$
我们把$X_n - X_{n-1}$看成一个整体的话，就有$X_{n+}-X_{n}$和$X_n-X_{n-1}$的线性关系，即
$$
t_n \equiv at_{n-1} \mod n
$$
然后有
$$
t_{n+1} \equiv a^2t_{n-1} \mod n
$$
我们计算
$$
t_{n+1}t_{n-1} \equiv a^2t_{n-1}t_{n-1} \equiv a^2t_{n-1}^2 \equiv t_n^2 \mod n
$$

$$
\therefore t_{n+1}t_{n-1} -t_n^2 \equiv 0 \mod n
$$

再找一组这样的值，然后求公因数即可得到$n$，然后再依次求$a,b$，最后回推seed

exp.py

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
from Crypto.Util.number import *
import gmpy2

output =  [9997297986272510947766344959498975323136012075787120721424325775003840341552673589487134830298427997676238039214108, 4943092972488023184271739094993470430272327679424224016751930100362045115374960494124801675393555642497051610643836, 6774612894247319645272578624765063875876643849415903973872536662648051668240882405640569448229188596797636795502471, 9334780454901460926052785252362305555845335155501888087843525321238695716687151256717815518958670595053951084051571, 2615136943375677027346821049033296095071476608523371102901038444464314877549948107134114941301290458464611872942706, 11755491858586722647182265446253701221615594136571038555321378377363341368427070357031882725576677912630050307145062, 7752070270905673490804344757589080653234375679657568428025599872155387643476306575613147681330227562712490805492345, 8402957532602451691327737154745340793606649602871190615837661809359377788072256203797817090151599031273142680590748, 2802440081918604590502596146113670094262600952020687184659605307695151120589816943051322503094363578916773414004662, 5627226318035765837286789021891141596394835871645925685252241680021740265826179768429792645576780380635014113687982]

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

T = []
for i in range(1,len(t)-1):
    T.append(t[i+1]*t[i-1] - t[i]**2)

N = []
for i in range(len(T)-1):
    n = gmpy2.gcd(T[i],T[i+1])
    N.append(int(n))

for n in N:
    try:
        a = gmpy2.invert(t[0],n) * t[1] % n
        b = output[1] - a*output[0] % n
        a_ = gmpy2.invert(a,n)

        seed = a_ * (output[0] - b) % n
        flag = long_to_bytes(seed)
        if b'Spirit' in flag:
            print(flag)
    except:
        pass

由于求公因数可能带有小因子，需要对n进行一些处理

例题

来源应该是NSS上面的，忘了叫什么名字

task.py

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
from Crypto.Util.number import *

flag = b'NSSCTF{******}'

class LCG:
    def __init__(self, seed, a, b, m):
        self.seed = seed  # 初始种子
        self.a = a  # 乘数
        self.b = b  # 增量
        self.m = m  # 模数

    def generate(self):
        self.seed = self.a * (self.seed - self.b) % self.m
        return self.seed


lcg = LCG(bytes_to_long(flag), getPrime(256), getPrime(256), getPrime(256))

for i in range(getPrime(16)):
    lcg.generate()

print(lcg.generate())
print(lcg.generate())
print(lcg.generate())
print(lcg.generate())
print(lcg.generate())

'''
57648351648792284446777383544515312078150027665462203747924668509833442797796
90378879763416486117626477831653213918315023665514305359005153448529276829825
21826576702665114807208181233864324586557058567478767825970403161758214940301
47594460970742467761038407996122637655856234121180714918606854365482948918701
11871076497267630136796123094001159466754095580273018347962555675375123133730
'''

可以看到这题只给出了seed连续的五个状态，但在此之前有若干次迭代，但并不影响恢复参数$a,b,n$

我们只需要恢复$a,b,n$，然后往回迭代即可

exp.py

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
from Crypto.Util.number import *
import gmpy2

output = [57648351648792284446777383544515312078150027665462203747924668509833442797796,
90378879763416486117626477831653213918315023665514305359005153448529276829825,
21826576702665114807208181233864324586557058567478767825970403161758214940301,
47594460970742467761038407996122637655856234121180714918606854365482948918701,
11871076497267630136796123094001159466754095580273018347962555675375123133730]

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

T = []
for i in range(1,len(t)-1):
    T.append(t[i+1]*t[i-1] - t[i]**2)

N = []
for i in range(len(T)-1):
    n = gmpy2.gcd(T[i],T[i+1])
    N.append(int(n))

# print(N)
# 430799744310334360363379121857013767962457275253944408631590707485837972511596 = 4 * 107699936077583590090844780464253441990614318813486102157897676871459493127899

n = 107699936077583590090844780464253441990614318813486102157897676871459493127899
a = gmpy2.invert(t[0],n) * t[1] % n
b = output[1] - a*output[0] % n
a_ = gmpy2.invert(a,n)

seed = a_ * (output[0] - b) % n
for _ in range(2**16):
    seed = a_ * (seed - b) % n
    flag = long_to_bytes(seed)
    if b'NSSCTF' in flag:
        print(flag)

题型6:给出的seed并不是连续的

例题

task.py

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
from Crypto.Util.number import *

flag = b'NSSCTF{******}'

class LCG:
    def __init__(self, seed, a, b, m):
        self.seed = seed  # 初始种子
        self.a = a  # 乘数
        self.b = b  # 增量
        self.m = m  # 模数

    def generate(self):
        self.seed = (self.a * self.seed + self.b) % self.m
        self.seed = (self.a * self.seed + self.b) % self.m
        return self.seed


lcg = LCG(bytes_to_long(flag), getPrime(255), getPrime(255), getPrime(256))

for i in range(getPrime(16)):
    lcg.generate()

print(lcg.generate())
print(lcg.generate())
print(lcg.generate())
print(lcg.generate())
print(lcg.generate())

'''
25445927935559969212648839062255651208014967526951331344342413906051118248013
81572970970116732975667604095930675262596098540738447440566868976253289440293
6956793925625110803779114150160476498676179542815207353218944386232051429289
88042506866508011592456777776490262927213783361334741921985316105965255450508
5652832125321707726481846809536180176877263519327268361130605456255558285092
'''

记seed是$X_0$，那么这题给出的数据是$X_2,X_4,X_6,X_8,X_{10}$
$$
\because X_{n+1} \equiv aX_n + b \mod m
$$

$$
\therefore X_{n+2} \equiv a^2X_n+(a+1)b \mod m
$$

可以把他当作一个系数$a’ = a^2,b’=(a+1)b$的LCG

做起来和连续输出的没什么区别

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
from Crypto.Util.number import *
import gmpy2

output = [25445927935559969212648839062255651208014967526951331344342413906051118248013,
81572970970116732975667604095930675262596098540738447440566868976253289440293,
6956793925625110803779114150160476498676179542815207353218944386232051429289,
88042506866508011592456777776490262927213783361334741921985316105965255450508,
5652832125321707726481846809536180176877263519327268361130605456255558285092]
t = []
for i in range(1,len(output)):
    t.append(output[i]-output[i-1])

T = []
for i in range(1,len(t)-1):
    T.append(t[i+1]*t[i-1] - t[i]**2)

m = []
for i in range(len(T)-1):
    mm = gmpy2.gcd(T[i],T[i+1])
    if isPrime(mm):
        m.append(int(mm))
    else:
        for i in range(1,100):
            if isPrime(mm // i):
                mm = mm // i
                m.append(int(mm))
                break

for i in m:
    a = gmpy2.invert(t[0],i) * t[1] % i
    b = output[1] - a*output[0] % i
    a_ = gmpy2.invert(a,i)

    seed = a_ * (output[0]-b) % i
    for _ in range(2**16):
        seed = a_ * (seed - b) % i
        flag = long_to_bytes(seed)
        if b'NSSCTF' in flag:
            print(flag)

题型7:给出seed的高位

例题

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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]

已知
$$
X_{n+1} \equiv aX_n + b \mod m
$$
把$X_n$拆为高位和低位之和，即$X_n = H_n+L_n$，于是有

$$
H_{n+1}+L_{n+1} \equiv a(H_n+L_n) + b \mod m
$$

$$
\therefore L_{n+1} \equiv aL_n+(aH_n+b-H_{n+1})\mod m
$$

$$
\because L_2 \equiv aL_1 + (aH_1+b-H_2) \mod m
$$

$$
\therefore L_3 \equiv a(aL_1 + aH_1+b-H_2)+aH_2+b-H_3 \mod m
$$

即
$$
L_3 \equiv a^2L_1+(aH_2+b-H_3+a^2H_1+b-H_2)
$$
于是能得到每个$L_i$与$L_1$的关系，则有
$$
L_{i} \equiv A_iL_1 +B_i \mod m
$$
即
$$
L_{i} = A_iL_1 + B_i + k_{i}m
$$
接下来构造格
$$
\begin{pmatrix}
k_1 & k_2 & … &k_n & L_1 & 1
\end{pmatrix}
\begin{pmatrix}
m & 0 & … & 0 & 0 & 0\\
0 & m & … & 0 & 0 & 0\\
\vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\
0 & 0 & … & m & 0 & 0\\
A_1 & A_2 & … & A_n & 1 & 0\\
B_1 & B_2 & … & B_n & 0 & K
\end{pmatrix}
=
\begin{pmatrix}
L_2 & L_3 & … & L_{n+1} & L_1 & K
\end{pmatrix}
$$
这个K根据要求的值来决定

exp.py

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
#sage
import gmpy2
from Crypto.Util.number import *

a =  731111971045863129770849213414583830513204814328949766909151
b =  456671883153709362919394459405008275757410555181682705944711
m =  666147691257100304060287710111266554526660232037647662561651
c =  [0,16985619148410545083429542035273917746612, 32633736473029292963326093326932585135645, 20531875000321097472853248514822638673918, 37524613187648387324374487657224279011, 21531154020699900519763323600774720747179, 1785016578450326289280053428455439687732, 15859114177482712954359285501450873939895, 10077571899928395052806024133320973530689, 30199391683019296398254401666338410561714, 21303634014034358798100587236618579995634]
#0是seed的高位

length = len(c)
for i in range(length):
    c[i] = c[i] << 64

A = [1]
B = [0]
# 计算A,B比较关键
for i in range(1,length-1):
    Ai = a * A[i-1] % m
    Bi = (a * B[i-1] + a * c[i] + b - c[i+1]) % m
    A.append(Ai)
    B.append(Bi)

A = A[1:]
B = B[1:]

M = Matrix(length,length)

for i in range(length-2):
    M[i,i] = m
    M[-1,i] = B[i]
    M[-2,i] = A[i]
M[-1,-1] = 2^64
M[-2,-2] = 1

for i in M.LLL():
    if i[-1] == 2^64:
        L1 = i[-2]

seed1 = c[1] + L1

inv = gmpy2.invert(a,m)
seed = inv * (seed1 - b) % m

print(long_to_bytes(int(seed)))

NPUCTF2020——BabyLCG

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
from Crypto.Util.number import *
from Crypto.Cipher import AES
from secret import flag

class LCG:
    def __init__(self, bit_length):
        m = getPrime(bit_length)
        a = getRandomRange(2, m)
        b = getRandomRange(2, m)
        seed = getRandomRange(2, m)
        self._key = {'a':a, 'b':b, 'm':m}
        self._state = seed
        
    def next(self):
        self._state = (self._key['a'] * self._state + self._key['b']) % self._key['m']
        return self._state
    
    def export_key(self):
        return self._key


def gen_lcg():
    rand_iter = LCG(128)
    key = rand_iter.export_key()
    f = open("key", "w")
    f.write(str(key))
    return rand_iter


def leak_data(rand_iter):
    f = open("old", "w")
    for i in range(20):
        f.write(str(rand_iter.next() >> 64) + "\n")
    return rand_iter


def encrypt(rand_iter):
    f = open("ct", "wb")
    key = rand_iter.next() >> 64
    key = (key << 64) + (rand_iter.next() >> 64)
    key = long_to_bytes(key).ljust(16, b'\x00')
    iv = long_to_bytes(rand_iter.next()).ljust(16, b'\x00')
    cipher = AES.new(key, AES.MODE_CBC, iv)
    pt = flag + (16 - len(flag) % 16) * chr(16 - len(flag) % 16)
    ct = cipher.encrypt(pt.encode())
    f.write(ct)


def main():
    rand_iter = gen_lcg()
    rand_iter = leak_data(rand_iter)
    encrypt(rand_iter)


if __name__ == "__main__":
    main()

这道题和上面差不多

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
59
60
61
import gmpy2
from Crypto.Cipher import AES
from Crypto.Util.number import *

a = 107763262682494809191803026213015101802
b = 153582801876235638173762045261195852087
m = 226649634126248141841388712969771891297
c = [0,7800489346663478448,11267068470666042741,5820429484185778982,6151953690371151688,548598048162918265,1586400863715808041,7464677042285115264,4702115170280353188,5123967912274624410,8517471683845309964,2106353633794059980,11042210261466318284,4280340333946566776,6859855443227901284,3149000387344084971,7055653494757088867,5378774397517873605,8265548624197463024,2898083382910841577,4927088585601943730]

length = len(c)
#0是seed的高位
for i in range(length):
    c[i] = c[i] << 64


A = [1]
B = [0]

for i in range(1,length-1):
    Ai = a*A[i-1] % m
    Bi = (a*B[i-1] + a*c[i]+b-c[i+1]) % m
    A.append(Ai)
    B.append(Bi)

A = A[1:]
B = B[1:]

M = Matrix(length,length)

for i in range(length-2):
    M[i,i] = m
    M[-1,i] = B[i]
    M[-2,i] = A[i]
M[-1,-1] = 2^64
M[-2,-2] = 1

for i in M.LLL():
    if i[-1] == 2^64:
        L1 = i[-2]

seed1 = c[1] + L1

inv = gmpy2.invert(a,m)
seed = inv * (seed1 - b) % m

s = [seed]

for i in range(23):
    s.append((a*s[i] + b)%m)

key = s[-3] >> 64
key = (key << 64) + (s[-2] >> 64)

key = long_to_bytes(key).ljust(16, b'\x00')
iv = long_to_bytes(s[-1]).ljust(16, b'\x00')


cipher = b'\xe0\xe0p,\xb7\xd6\xfc\x19\xac\xe7)\xbe\xfc\xa4\n\xf5\x01#\xf7\xa6\xed\xe1\xf3\xaeK:*\xcd{\x1d\xd87\x14s\x10X\x86\xaf\xd1WsD\x1f\xa0lej\xd6'

aes = AES.new(key, AES.MODE_CBC, iv)
print(aes.decrypt(cipher))

题型8:给出seed的低位

DragonCTF——Myencrypt

task.py

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
from Crypto.Util.number import *
from secret import flag      
import random

def getMyPrime():              
    while True:              
        r = random.getrandbits(64)              
        _p = r**6 -3*r**5 - r**4 + r**2 - r - 6
        _q = r**7 + 2*r**6 + r**5 + 4*r**4 + 7*r**2 + r + 4653
        if isPrime(_p) and isPrime(_q):              
            return _p, _q
                      
def enc(m, n):                        
    return pow(m, 65537, n)              

def LCG(s,a,b,n):
    return (a*s + b) % n


seed = bytes_to_long(flag)
P = getPrime(512)
a = random.randrange(0,P)
b = random.randrange(0,P)

def Roll():
    global seed
    seed = LCG(seed,a,b,P)
    return seed % 2**16

p, q = getMyPrime()
n = p * q              
enc_P = enc(P, n)
print(f"n = {n}")              
print(f"enc_P = {enc_P}")

out = []
for _ in range(40):
    out.append(Roll())

print(f"a = {a}")
print(f"b = {b}")
print(f"out = {out}")
"""
n = 367607216916992479389134891131114587133009740650002091628118335376181099436038275658924854657961899744575925388703268582056430009497671922059897059783536744493531958386363414826690641507109882348146032258948465904599378899099
enc_P = 211227162038542151362653759945341453010645974999544285701593405111987791484647673336926501483224994245847627668967635890647145384474656340117478284167354693220168425749272046819478800821628987855153860237420551814256627737364
a = 7376230378305251514633162470666650806131503259133111341061684684360131480889507671014885773242827018255084439517331188189053742993725204318816256672378364
b = 5981773722556023081731802026216037317284605069549134243706224312475317951748749016561131423138498251027685556438081926521018841348439714789529705763025327
out = [25783, 11709, 26891, 35047, 46512, 22000, 56358, 11248, 48000, 26572, 43378, 50007, 27114, 2580, 9672, 31526, 5988, 21755, 3106, 23580, 49957, 20013, 63262, 7781, 6006, 47733, 49170, 50836, 1138, 49760, 32897, 25724, 33682, 46027, 54211, 51060, 11396, 22616, 41795, 28660]
"""

这里我们仅讨论LCG部分，已知$P$

Roll()函数给出seed每个状态模掉$2^{16}$后的值，相当于给出低位。思路和高位一样，我们还是拆成高低位来写

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

拆成高低位之后有
$$
H_{n+1}\times 2^{16} + L_{n+1} \equiv a(H_n\times 2^{16} + L_n) +b \mod p
$$
化简得
$$
H_{n+1} \equiv aH_n + (aL_n + b -L_{n+1})\times 2^{-16} \mod p
$$
于是有
$$
H_2 \equiv aH_1 + (aL_1 + b - L_2)\times 2^{-16} \mod p
$$

$$
H_3 \equiv aH_2 + (aL_2+b-L_3) \times 2^{-16} \mod p
$$

即
$$
H_3 \equiv a^2H_1 + (a(aL_1+b-L_2) + (aL_2+b-L_3)) \times 2^{-16} \mod p
$$
将常数记为$B$

写到这里是为了后面更好理解$B_i$如何计算

回到题目，简单来写就是
$$
H_{n+1} \equiv A_nH_1 + B_n \mod p
$$
即
$$
H_{n+1} = A_mH_1 + B_n +k_np
$$
构造格
$$
\begin{pmatrix}
k_1 & k_2 & … & k_n & H_1 & 1
\end{pmatrix}
\begin{pmatrix}
P & 0 & … & 0 & 0 & 0\\
0 & P & … & 0 & 0 & 0\\
\vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\
0 & 0 & … & P & 0 & 0\\
A_1 & A_2 & … & A_n & 1 & 0\\
B_1 & B_2 & … & B_n & 0 & \frac{P}{2^{16}}
\end{pmatrix}
=
\begin{pmatrix}
H_2 & H_3 & … & H_{n+1} & H_1 & \frac{P}{2^{16}}
\end{pmatrix}
$$
ps:最后一个配上$\frac{P}{2^{16}}$是为了让目标向量的每个值和$H_i$一致

规约后我们可以得到$H_1$，即可求得$seed_1 = H_1\times 2^{16} + L_1$

再求解seed

$$
seed \equiv (seed_1 -b)\times a^{-1} \mod P
$$

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
from Crypto.Util.number import *
import gmpy2

a = 2759277675743644814124420138047586760905070650864591936190199977578763421196999718749092450720072564786874114432179104175692800471519816376692104515142375
b = 8111240578821759579875175166986910195923820191652867334412871591814076020421468033017946066268237980082938735686222173713853299600396887041341974719819186
out = [39566, 15295, 19818, 55685, 49100, 6517, 2675, 9567, 37243, 40312, 42906, 35874, 44178, 1256, 40298, 29149, 35721, 19886, 63020, 50116, 6844, 39897, 16134, 50218, 44609, 46188, 52712, 49903, 20933, 5441, 19411, 8330, 6904, 39350, 60853, 43446, 35910, 43728, 61533, 13757]
P = 10679387699123200522776360035184725927822172255453595568464894884736102462568579313264894449779104030120028056158023524486966766295648236135714849745610937

L = [0] + out
n = len(out)
A = [1]
B = [0]

for i in range(1,n):
    A.append(a*A[i-1] % P)
    B.append((a*B[i-1] + (a*L[i]+b-L[i+1])*gmpy2.invert(2^16,P))%P)

A = A[1:]
B = B[1:]

Ge = Matrix(ZZ,n+1,n+1)
for i in range(len(A)):
    Ge[i,i] = P
    Ge[-2,i] = A[i]
    Ge[-1,i] = B[i]

Ge[-2,-2] = 1
Ge[-1,-1] = P // 2^16

M = Ge.LLL()[0]
H1 = M[-2]
L1 = out[0]
seed1 = H1 * 2^16 + L1

seed = ((seed1 - b)*gmpy2.invert(a,P))%P
print(long_to_bytes(int(seed)))

题型9:线性关系

例题

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import random
from Crypto.Util.number import *
from secrets import flag
assert len(flag) == 40
flag1,flag2 = [flag[i:i + len(flag) // 2] for i in range(0,len(flag),len(flag) // 2)]
a = bytes_to_long(flag1)
b = bytes_to_long(flag2)
p = getPrime(256)
x = [random.getrandbits(256),random.getrandbits(256)]
cs = []
for i in range(40):
    c = random.getrandbits(240)
    cs.append(c)
    x += [(a * x[-2] + b * x[-1] + c) % p]

print(f'x = {x}')
print(f'p = {p}')
# x = [...]
# p = 98658574968607903088958866815944266273368824806380957165790489794472555646793

可以看到这道题不像平常的LCG，每个状态与前两个状态相关，这道题要求我们计算a,b
$$
\because X_{i+2} \equiv (aX_i + bX_{i+1} + c_i) \mod p
$$

$$
\therefore c_i = X_{i+2} - aX_i -bX_{i+1} + k_ip
$$

利用这么多组线性关系，我们可以构造格，注意到$a \approx 160bit$，$b \approx 160bit$，$c_i = 240bit$，在构造格的时候注意配平即可
$$
\begin{pmatrix}
-a&-b&1 & k_1 & k_2 &…&k_n
\end{pmatrix}
\begin{pmatrix}
2^{80} & 0 & 0 & X_1 & X_2 & … & X_{40}\\
0 & 2^{80} & 0 & X_2 & X_3 & … & X_{41}\\
0 & 0 & 2^{240} & X_3 & X_4 & … & X_{42}\\
0 & 0 & 0 & p & 0 & … & 0\\
\vdots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\
0 & 0 & 0 & 0 & 0 &… & p
\end{pmatrix}
=
\begin{pmatrix}
-a\times 2^{80} & -b\times 2^{80} & 2^{240} & c_1 & c_2 & … & c_{40}
\end{pmatrix}
$$

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
#sage
from Crypto.Util.number import *
import gmpy2

x = [x1 ... x40]
p = 98658574968607903088958866815944266273368824806380957165790489794472555646793

Ge = Matrix(ZZ,43,43)

for i in range(3,43):
    Ge[0,i] = x[i-3]
    Ge[1,i] = x[i-2]
    Ge[2,i] = x[i-1]
    Ge[i,i] = p

Ge[0,0] = 2^80
Ge[1,1] = 2^80
Ge[2,2] = 2^240

for i in Ge.LLL():
    if abs(i[2]) == 2^240:
        ka = abs(i[0])
        kb = abs(i[1])
        a = ka // 2^80
        b = ka // 2^80
        flag1 = long_to_bytes(int(a))
        flag2 = long_to_bytes(int(b))
        flag = flag1 + flag2
        print(flag)

Gröbner基

可以把这个理解为一个解同余方程组的工具

举个例子

task.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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]

记output为X，我们有这样的线性关系
$$
X_1 \equiv aX_0 +b \mod n
$$

$$
X_2 \equiv aX_1 +b \mod n
$$

$$
X_3 \equiv aX_2 + b \mod n
$$

$$
\vdots
$$

虽然只有3个未知数，但是我们越多方程，结果越正确

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
from Crypto.Util.number import *

output =  [9997297986272510947766344959498975323136012075787120721424325775003840341552673589487134830298427997676238039214108, 4943092972488023184271739094993470430272327679424224016751930100362045115374960494124801675393555642497051610643836, 6774612894247319645272578624765063875876643849415903973872536662648051668240882405640569448229188596797636795502471, 9334780454901460926052785252362305555845335155501888087843525321238695716687151256717815518958670595053951084051571, 2615136943375677027346821049033296095071476608523371102901038444464314877549948107134114941301290458464611872942706, 11755491858586722647182265446253701221615594136571038555321378377363341368427070357031882725576677912630050307145062, 7752070270905673490804344757589080653234375679657568428025599872155387643476306575613147681330227562712490805492345, 8402957532602451691327737154745340793606649602871190615837661809359377788072256203797817090151599031273142680590748, 2802440081918604590502596146113670094262600952020687184659605307695151120589816943051322503094363578916773414004662, 5627226318035765837286789021891141596394835871645925685252241680021740265826179768429792645576780380635014113687982]

R.<a,b> = PolynomialRing(ZZ)

f1 = output[0]*a + b - output[1]
f2 = output[1]*a + b - output[2]
f3 = output[2]*a + b - output[3]
f4 = output[3]*a + b - output[4]
f5 = output[4]*a + b - output[5]

F = [f1,f2,f3,f4,f5]
# 使用F构建一个理想的Ideal。
ideal = Ideal(F)
# 计算Ideal的Gröbner基I
I = ideal.groebner_basis()

a = ZZ(-I[0].univariate_polynomial()(0))
b = ZZ(-I[1].univariate_polynomial()(0))
n = ZZ(I[2])

print(a)
print(b)
print(n)

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

对于Grobner基没有了解很深，只能依葫芦画瓢利用了，有兴趣的师傅可以看下面的文章

(11 封私信) 介绍一下Grobner基的概念和应用？谢谢 - 知乎 (zhihu.com)

Groebner basis - Scholarpedia

参考：CTF秀密码挑战 个人writeup - 知乎 (zhihu.com)

-------------已经到底啦！-------------