Mamor's Blog
0%

流密码之LCG-01

发表于 更新于 分类于
本文字数： 15k 阅读时长 ≈ 13 分钟

LCG简介

LCG算法，线性同余生成器（Linear congruential generator），一种产生为随机数的方法。

作为流密码（stream cipher）中常用的伪随机数生成器（pseudo random number generator），其随机性能取决于参数和种子的选择。

Xn+1 = (aXn +b) mod m，其中a为乘数、b为增量、m为模数。a/b/m 为产生器设定的常数。

LCG公式推导

由以上公式可推得一下4个公式:

目的 公式
①Xn+1推出Xn Xn=(a^-1 (Xn+1 - b))%m
②求a a=((Xn+2-Xn+1)(Xn+1-Xn)^-1)%m
③求b b=(Xn+1 - aXn)%m
④求m tn=Xn+1-Xn，m=gcd((tn+1tn-1 - tntn) , (tntn-2 - tn-1tn-1))

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.Xn=(a^-1 (Xn+1 - b))%m

2.a=((Xn+2-Xn+1)(Xn+1-Xn)^-1)%m

3.b=(Xn+1 - aXn)%m

4.tn=Xn+1-Xn，m=gcd((tn+1tn-1 - tntn) , (tntn-2 - tn-1tn-1))

LCG基础题目

题目来源 https://blog.csdn.net/superprintf/article/details/108964563

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

题目分析

已知 a b n c=seed^m 求m

m=seed^c 可以求得，而c为已知项，seed 已知

for i in range(10):

seed = (a*seed+b)%n

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

seed =  33477128523140105764301644224721378964069
a =  216636540518719887613942270143367229109002078444183475587474655399326769391
b =  186914533399403414430047931765983818420963789311681346652500920904075344361
n =  155908129777160236018105193822448288416284495517789603884888599242193844951
c =  209481865531297761516458182436122824479565806914713408748457524641378381493
for i in range(10):
    seed = (a*seed+b)%n
m = seed^c
print(m)
print(long_to_bytes(m))
# 147424144810829416246263598495658483373775464141840154829404726417260880253
# b'Spirit{0ops!___you_know__LCG!!}'

LCG2

题目描述
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

题目分析

已知 a b n 已知密文c 为最终seed

求 m m为初始seed

循环十次 最终得到初始seed

Xn=(a^-1 (Xn+1 - b))%m

对应公式为 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,n)

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

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

# 这两种都可以去求 逆元
# 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,n)
ani = gmpy2.invert(a,n)
seed=c
for i in range(10):
    seed = (ani*(seed-b))%n
print(seed)
print(long_to_bytes(seed))
# 41496207727216587746731918844219889152464603755197286927180022389268761169026372950106493
# b'Spirit{Orzzz__number_the0ry_master!!}'

LCG3

题目描述
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

题目分析

已知 a n 已知an6 an7

b = m 求b

b=(Xn+1 - aXn)%m

b = (an7 - a*an6)%n

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

from gmpy2 import gmpy2
a =  3227817955364471534349157142678648291258297398767210469734127072571531
n =  2731559135349690299261470294200742325021575620377673492747570362484359
output1 =  56589787378668192618096432693925935599152815634076528548991768641673
output2 =  2551791066380515596393984193995180671839531603273409907026871637002460

# b=(Xn+1 - aXn)%m
b = (output2 - a*output1)%n
print(b)
print(long_to_bytes(b))
# 2249513928387900043419621487136593156497460191283027871178330274556029
# b'Spirit{Y0u_@r3_g00d_at__math}'

LCG-4

题目描述
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]
题目分析

已知 n an[]，求 m

m为初始化seed 所以求出seed0即可

可以通过推导公式2 求得 a

在通过公式3 求得 b

seed = (a*seed+b)%n

seed1 = (a * seed0 +b )%n

通过公式1 Xn=(a^-1 (Xn+1 - b))%m 推得seed0 即明文

seed0 = ( (seed1 - b) * (a^-1) )%n

seed1 = output[0]

所以 seed0 = ((output[0]-b)*ani )%n

WP
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 *
from gmpy2 import gmpy2

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

# 求a a=((Xn+2-Xn+1)(Xn+1-Xn)^-1)%m
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 = (output[3]-output[2]) * MMI((output[2]-output[1]),n)%n
print(a)

# 这两种方法都可以求 逆元
# ani=MMI(a,n)
ani=gmpy2.invert(a,n)

# 求b b=(Xn+1 - aXn)%m
b = (output[2] - a*output[1])%n
print(b)

# 求明文m
seed0  = ((output[0]-b)*ani )%n
print(seed0)
print(long_to_bytes(seed0))
# 65863586327872307178215811859890622391386702699190067821678721759311822315235571722857932007760
# 580530341837176922585879619790971707330065277035664726870365931385222825590112557483074386629351
# 696190840220381770483412363798400195080823210401430601069787735566362644430227092882973263012221
# b'Spirit{Gr3at__J0b!_You_can_be___better!}'

LCG-5

题目描述
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]
题目分析

已知 seed数组，求明文plaintext ，而plaintext=seed0

需要先求模数n，利用推导公式4 然后求 a，再求 b，最后求出seed0 。

和题目4相比 多了求模数n一步

1
2
3
4
5
6
7
8
all_t = []
all_n = []
t[i] = output[i]-output[i-1]
for i in range(9):
   all_t.append(output[i]-output[i-1])
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]) ))

会得到一些列的模数n

进行遍历 for n in all_n: 但是得到的模数中存在负数及1 需要取绝对值并将1跳过

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

def gcd(a,b):
    if(b==0):
        return a
    else:
        return gcd(b,a%b)

output =  [9997297986272510947766344959498975323136012075787120721424325775003840341552673589487134830298427997676238039214108, 4943092972488023184271739094993470430272327679424224016751930100362045115374960494124801675393555642497051610643836, 6774612894247319645272578624765063875876643849415903973872536662648051668240882405640569448229188596797636795502471, 9334780454901460926052785252362305555845335155501888087843525321238695716687151256717815518958670595053951084051571, 2615136943375677027346821049033296095071476608523371102901038444464314877549948107134114941301290458464611872942706, 11755491858586722647182265446253701221615594136571038555321378377363341368427070357031882725576677912630050307145062, 7752070270905673490804344757589080653234375679657568428025599872155387643476306575613147681330227562712490805492345, 8402957532602451691327737154745340793606649602871190615837661809359377788072256203797817090151599031273142680590748, 2802440081918604590502596146113670094262600952020687184659605307695151120589816943051322503094363578916773414004662, 5627226318035765837286789021891141596394835871645925685252241680021740265826179768429792645576780380635014113687982]
# print(len(output))
# 10
t = []
all_n = []

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

for i in range(len(output)-3):
    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]) ))

print(all_n)
# 求出来的 模数n 有正有负 需要取绝对值 然后如果模数为1 pass掉
for n in all_n:
    n = abs(n)
    if n ==1 :
        continue
    # 求a a=((Xn+2-Xn+1)(Xn+1-Xn)^-1)%m
    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 = (output[3] - output[2]) * MMI((output[2] - output[1]), n) % n
    # print(a)
    ani = MMI(a, n)

    # 求b b=(Xn+1 - aXn)%m
    b = (output[2] - a * output[1]) % n
    # print(b)

    # 求明文m
    seed0 = ((output[0] - b) * ani) % n
    print(seed0)
    print(long_to_bytes(seed0))

'''
[-2, -1, -393916182865583204167593579626567099983463054572651446294350689155749034982777402793379583263905054399035065243497725, -393916182865583204167593579626567099983463054572651446294350689155749034982777402793379583263905054399035065243497725, -15756647314623328166703743185062683999338522182906057851774027566229961399311096111735183330556202175961402609739909, -47269941943869984500111229555188051998015566548718173555322082698689884197933288335205549991668606527884207829219727, 47269941943869984500111229555188051998015566548718173555322082698689884197933288335205549991668606527884207829219727]
1
b'\x01'
211188662731758863427946381877198496775371670862648580138469143303016383244049847985679632443910715787648463257824063
b'\x05\\\x1e\xd4u*\xe0\xf3w\xc6\x0c\xc4r\xbbh^\\\xafL\x91\xa7f\xf2\xe6\x1cH=\x9e\x19\xfd)\xc2S\xcc7\xe6\x80#0N*\xfd\xa3S\x08\xa8ik?'
211188662731758863427946381877198496775371670862648580138469143303016383244049847985679632443910715787648463257824063
b'\x05\\\x1e\xd4u*\xe0\xf3w\xc6\x0c\xc4r\xbbh^\\\xafL\x91\xa7f\xf2\xe6\x1cH=\x9e\x19\xfd)\xc2S\xcc7\xe6\x80#0N*\xfd\xa3S\x08\xa8ik?'
12842454256006200840327330825396197845927483635849122825220513270564143733836993752723210090679333406611887619653501
b'Spirit{final__lcg__is__co0m1ing__are_you_ready?}'
44355748885252857173734817195521565844604528001661238528768568403024066532459185976193576751791737758534692839133319
b'\x01 /c\xbe \xe2\xbf\xb7\xee\xdc\x85(\x15\xab\xb4=0)?\x01\x8cwY<\t\x10e\xb4\x80\x9b\x88\xe1\xb5.\xf9\xf8{[?\x05\xbd\x1e\x08\xd0\x1a\xc0\x90\x87'
44355748885252857173734817195521565844604528001661238528768568403024066532459185976193576751791737758534692839133319
b'\x01 /c\xbe \xe2\xbf\xb7\xee\xdc\x85(\x15\xab\xb4=0)?\x01\x8cwY<\t\x10e\xb4\x80\x9b\x88\xe1\xb5.\xf9\xf8{[?\x05\xbd\x1e\x08\xd0\x1a\xc0\x90\x87'
'''

对于稍微难些的LCG后续再去学习 二元LCG 三元LCG等 最近没太多时间 先留个坑 ：）

欢迎关注我的其它发布渠道

------------- 💖 🌞 本 文 结 束 😚 感 谢 您 的 阅 读 🌞 💖 -------------