ctf中的lcg总结

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

Xn+1=(aXn+b)mod(m)

线性同余法最重要的是定义了三个整数，乘数 a、增量 b和模数 m，其中a,b,m是产生器设定的常数。 1.Xn+1反推出Xn Xn=(a^-1 (Xn+1 - b))%m 2.求a a=((Xn+2-Xn+1)(Xn+1-Xn)^-1)%m 3.求b b=(Xn+1 - aXn)%m 4.求m tn=Xn+1-Xn，m=gcd((tn+1tn-1 - tntn) , (tntn-2 - tn-1tn-1))

这些就是简单的几个推论

然后我们通过题目来进行分析

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

首先lcg还是基于流密码类型，要考虑异或的特性，异或两次就可以变回本身，先看代码逻辑，a,b,n是随机生成的素数，定义了一个整数seed = 33477128523140105764301644224721378964069 seed通过10次lcg转换之后再和plaintext二进制异或得到ciphertext，想要得到flag就要知道plaintext 想要知道plaintext只能通过ciphertext = seed ^ plaintex这个表达式推出 而ciphertext==c我们知道，式子中的seed可以通过他给的初始seed,a,b,n运用算法lcg十次得到 然后根据异或的特性求解出plaintext，即plaintext = seed ^ ciphertext (异或特性，c=a异或b，那么a=b异或c，或者b=a异或c)

1
2
3
4
5
6
7
8
9
10
11
seed = 33477128523140105764301644224721378964069
a = 216636540518719887613942270143367229109002078444183475587474655399326769391
b = 186914533399403414430047931765983818420963789311681346652500920904075344361
n = 155908129777160236018105193822448288416284495517789603884888599242193844951
c = 209481865531297761516458182436122824479565806914713408748457524641378381493

for i in range(10):
    seed = (a*seed+b)%n
plaintext=seed^c
print(long_to_bytes(plaintext))

下一种类型

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

根据题意求flag相当于求plaintext，求plaintext相当于求初始seed，我们知道lcg算法十次之后的seed=ciphertext=c，而c我们已知，我们还知道a，b，n。所以这道题要我们从lcg十次之后的seed推算出初始seed 用公式：Xn=(a-1 (Xn+1 - b))%n

1
2
3
4
5
6
7
8
9
10
11
12
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))

下一个题目类型

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

求flag相当于求plaintext，plaintext相当于求b，然后在看看我们已知的条件，我们知道a，知道n知道10次lcg中的第6次和第7次的结果，所以我们要根据已知的信息求b 用公式：b=(Xn+1 - aXn)%n直接求出b，然后就可以轻松解决了

1
2
3
4
5
6
7
8
a =  3227817955364471534349157142678648291258297398767210469734127072571531
n =  2731559135349690299261470294200742325021575620377673492747570362484359
output1 =  56589787378668192618096432693925935599152815634076528548991768641673
output2 =  2551791066380515596393984193995180671839531603273409907026871637002460
b=(output2-a*output1)%n
plaintext=b
print(long_to_bytes(plaintext))

下一种类型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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，那么就可以依靠这个把所有需要求出来的求出来

第四题给了n和10次lcg的output序列用a=((Xn+2-Xn+1)(Xn+1-Xn)-1)%n

​ 用已知信息可以求出a 再用a，output序列，n求出b 根据output序列第一个反推出初始seed 即可求解

1
2
3
4
5
6
7
8
9
10
11
n =  714326667532888136341930300469812503108568533171958701229258381897431946521867367344505142446819
output =  [683884150135567569054700309393082274015273418755015984639210872641629102776137288905334345358223, 285126221039239401347664578761309935673889193236512702131697050766454881029340147180552409870425, 276893085775448203669487661735680485319995668779836512706851431217470824660349740546793492847822, 670041467944152108349892479463033808393249475608933110640580388877206700116661070302382578388629, 122640993538161410588195475312610802051543155060328971488277224112081166784263153107636108815824, 695403107966797625391061914491496301998976621394944936827202540832952594905520247784142392337171, 108297989103402878258100342544600235524390749601427490182149765480916965811652000881230504838949, 3348901603647903020607356217291999644800579775392251732059562193080862524671584235203807354488, 632094372828241320671255647451901056399237760301503199444470380543753167478243100611604222284853, 54758061879225024125896909645034267106973514243188358677311238070832154883782028437203621709276]
from Crypto.Util.number import *
import gmpy2
a=(output[2]-output[1])*gmpy2.invert((output[1]-output[0]),n)%n
ani=gmpy2.invert(a,n)
b=(output[1]-a*output[0])%n
seed = (ani*(output[0]-b))%n
plaintext=seed
print(long_to_bytes(plaintext))

下一个

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

设tn = Xn+1 - Xn tn = (aXn+b) - (aXn-1+b) = atn-1(mod m) tn+1tn-1 - tntn = (aatn-1tn-1 - atn-1atn-1) = 0 (mod m) 即Tn = tn+1tn-1 - tntn是m的倍数，求Tn , Tn-1最大公因数即为m m = gcd((tn+1tn-1 - tntn) , (tntn-2 - tn-1tn-1))

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 *
def gcd(a,b): 
    if(b==0): 
        return a 
    else: 
        return gcd(b,a%b) 
s =  [9997297986272510947766344959498975323136012075787120721424325775003840341552673589487134830298427997676238039214108, 4943092972488023184271739094993470430272327679424224016751930100362045115374960494124801675393555642497051610643836, 6774612894247319645272578624765063875876643849415903973872536662648051668240882405640569448229188596797636795502471, 9334780454901460926052785252362305555845335155501888087843525321238695716687151256717815518958670595053951084051571, 2615136943375677027346821049033296095071476608523371102901038444464314877549948107134114941301290458464611872942706, 11755491858586722647182265446253701221615594136571038555321378377363341368427070357031882725576677912630050307145062, 7752070270905673490804344757589080653234375679657568428025599872155387643476306575613147681330227562712490805492345, 8402957532602451691327737154745340793606649602871190615837661809359377788072256203797817090151599031273142680590748, 2802440081918604590502596146113670094262600952020687184659605307695151120589816943051322503094363578916773414004662, 5627226318035765837286789021891141596394835871645925685252241680021740265826179768429792645576780380635014113687982]
t = []
for i in range(9):
    t.append(s[i]-s[i-1]) 
all_n = []
for i in range(7):
    all_n.append(gcd((t[i+1]*t[i-1]-t[i]*t[i]), (t[i+2]*t[i]-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] #逆元计算
for n in all_n:
    n=abs(n)
    if n==1:
        continue
    a=(s[2]-s[1])*MMI((s[1]-s[0]),n)%n
    ani=MMI(a,n)
    b=(s[1]-a*s[0])%n
    seed = (ani*(s[0]-b))%n
    plaintext=seed
    print(long_to_bytes(plaintext))

最近也要一道题目，道格的招新赛题目，同时也是nssctf第四轮的

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

f = open('flag.txt', 'r')
flag = f.read()
f.close()
assert flag[:8] == "Dest0g3{"


class LCG:
    def __init__(self):
        self.a = getRandomNBitInteger(32)
        self.b = getRandomNBitInteger(32)
        self.m = getPrime(32)
        self.seed = getRandomNBitInteger(32)

    def next(self):
        self.seed = (self.a * self.seed + self.b) % self.m
        return self.seed >> 16

    def output(self):
        print("a = {}\nb = {}\nm = {}".format(self.a, self.b, self.m))
        print("state1 = {}".format(self.next()))
        print("state2 = {}".format(self.next()))


lcg = LCG()
lcg.output()
c = b''.join([long_to_bytes(ord(flag[i]) ^ (lcg.next() % 10))
              for i in range(len(flag))])
print(bytes_to_long(c))
'''
a = 3939333498
b = 3662432446
m = 2271373817
state1 = 17362
state2 = 20624
600017039001091357643174067454938198067935635401496485588306838343558125283178792619821966678282131419050878
'''
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
alpha = 2659869614
beta = 3138014669
n = 2171187379
res1 = 32421
res2 = 32382

base = pow(2,32)
i = pow(2,31)
while i <= base:
    print(i)
    if ((alpha*i+beta)%n)>>16 == res1 and ((((alpha*i+beta)%n)*alpha+beta)%n)>>16 == res2:
        print('find it',i)
        break
    i+=1
    #seed=2250883318

这样爆破出i

1
2
3
4
5
6
7
8
symbol = Symbol()
symbol.output()
flag = long_to_bytes(628427670713408045832213770914678202267468957347245535228951062583137095137644250375583786099578).decode()
c = b''.join([long_to_bytes(ord(flag[i]) ^ (Symbol.next() % 10))
              for i in range(len(flag))])
print(c)
#NSSCTF{378f571491e6559d41ffa02e7a76653e}