CRYPTO -- LCG
起因:
之前师兄让我学LCG,自己也想补充一下这方面的内容,但因为当时期末考试+※CTF+冬令营+回家摸了一天鱼(不是,是休息了一天_(:з」∠)_)耽误到今天。
前置知识:
1.随机数
随机数在密码技术中扮演着十分重要的角色。
随机数应用:
用到随机数的场景:
-
生成密钥
用于对称密码和消息认证
-
生成密钥对
用于公钥密码和数字签名
-
生成初始化向量
用于分组密码的CBC、CFB和OFB模式
-
生成nonce
用于防御重放攻击以及分组密码的CTR模式等
-
生成salt
用于基于口令的密码(PBE)
随机数性质:
-
随机性(弱伪随机数)
一堆杂乱无章的数(能被看穿)
-
不可预测性(强伪随机数)
在知道过去生成的伪随机数列的前提下,依然无法预测出下一个生成的伪随机数。
其中,不可预测性是使用其他的密码技术来实现的,如sha-1
-
不可重现性(真随机数)
在理论下,使用计算机软件生成的数列,在某个时刻一定会出现重复,这个时间或长或短,由于计算机的内存是有限,这个时刻肯定会出现。所以软件生成的数列,肯定是具有周期性(会重复出现),所以不具备该性质。由硬件生成的数列,一般则具有该性质。
由硬件生成的随机数列,根据传感器收集的热量、声音的变化等事实上无法预测的和重现自然现象信息来生成的,像这样的硬件设备,称为随机数生成器。
而LCG就是一个伪随机数生成器。之所以称为伪随机数生成器,是由于它是由软件生成的。
2.模运算
模运算,就是一个取余运算。如 23 mod 7 = 2 , 可以写成 23%7=2.
一些性质:
(a + b) % p = (a % p + b % p) % p
(a - b) % p = (a % p - b % p) % p
(a * b) % p = (a % p * b % p) % p
(a ^ b) % p = ((a % p) ^ b ) % p
模运算的结合律:
((a + b) % p + c) % p= (a + (b + c) % p) % p
((a * b) % p * c) % p = (a * (b * c) % p ) % p
交换律:
(a + b) % p = (b+a) % p
(a * b) % p = (b * a) % p
分配律:
((a +b) % p * c) % p = ((a * c) % p + (b * c) % p) % p
3.模逆运算
逆元是指指数学领域群G中任意一个元a,都在G中有唯一的逆元a‘,具有性质a×a'=a'×a=e,其中e为该群的单位元。在模运算中,e=1。
第一种方法是循环求解法
第二种方法是扩展欧几里得算法:欧几里得算法的依据是最大公约数定理:对任意的非负整数a和任意正整数b,gcd(a,b) = gcd(b,a mod b).
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] #逆元计算
第三种方法是调用库:
import gmpy2
d=gmpy2.invert(a,b)#gmpy2库
from Crypto.Util.number import inverse
d=inverse(a,b)#Crypto库
LCG:线性同余法
简单的介绍:
表达式:
组成的线性同余发生器:
a对b取模
其中xn是seed.
a,b,m是设定的常量。
结合图和表达式可知,就是把种子传入发生器中,乘上a再加上c然后对m取模得到第一个伪随机数,然后返回到发生器中作为seed,在进行上一步的操作得到第二个,然后再传入发生器中。
举个例子:假设 a=3 b=0,m=7,seed=6
R1=(a*seed+b)mod m=(3*6+0) mod 7 = 4
R2=(a*seed+b)mod m=(3*4+0) mod 7 = 5
R3=(a*seed+b)mod m=(3*5+0) mod 7 = 1
R4=(a*seed+b)mod m=(3*1+0) mod 7 = 3
R5=(a*seed+b)mod m=(3*3+0) mod 7 = 2
R6=(a*seed+b)mod m=(3*2+0) mod 7 = 6
R7=(a*seed+b)mod m=(3*6+0) mod 7 = 4
同时也可以发现,伪随机数是对m取模后的值,其范围为 0~m-1,也就是 其周期。
同时也证明了其不具备不可预测性。所以线性同余法得到的是弱伪随机数。
攻击手段:
上图的变形都是基于原始表达式变形的。
1:Xn+1 = aXn + b (mod m)
aXn = Xn+1 - b (mod m)
Xn = a` (Xn+1 - b) (mod m)
2:Xn+2 = aXn+1 + b (mod m)
Xn+1 = aXn + b (mod m)
Xn+2 - Xn+1 = a(Xn+1-Xn) (mod m)
a = (Xn+2 - Xn+1)(Xn+1 - Xn)-1 (mod m)
3:Xn+1 = aXn + b (mod m)
b = Xn+1 - aXn (mod m)
4:
题目复现:
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
由题可知,plaintext是flag转整数得到。而其与线性同余产生的10个伪随机逐个进行了异或。所以解密也很简单。求出10个伪随机数,异或回去即可。
脚本如下:
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))
#Spirit{0ops!___you_know__LCG!!}
2.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
由题可知,plaintext是flag转整数得到。且seed=plaintext,即初始化的seed即为我们要求出来的目标。倒过来求,先求出逆元。
脚本如下
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.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
由题可知,plaintext是flag转整数得到。且b=plaintext,
即b未知,用已知条件求b
已知两个生成的伪随机数。利用3。
脚本如下:
a=3227817955364471534349157142678648291258297398767210469734127072571531
n=2731559135349690299261470294200742325021575620377673492747570362484359
output1=56589787378668192618096432693925935599152815634076528548991768641673
output2=2551791066380515596393984193995180671839531603273409907026871637002460
b=(output2-a*output1)%n
plaintext=b
print(long_to_bytes(plaintext))
#Spirit{Y0u_@r3_g00d_at__math}
4.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]
由题可知,plaintext是flag转整数得到。且seed=plaintext.即目标为求出seed。类似题二。但没有给出a,b,即由转化为求,a,b。
a用法二求,
b用法3求
再由法一,求逆元根据已知伪随机数倒推回去得到初始化的seed。
脚本如下:
import gmpy2
n = 714326667532888136341930300469812503108568533171958701229258381897431946521867367344505142446819
output = [683884150135567569054700309393082274015273418755015984639210872641629102776137288905334345358223, 285126221039239401347664578761309935673889193236512702131697050766454881029340147180552409870425, 276893085775448203669487661735680485319995668779836512706851431217470824660349740546793492847822, 670041467944152108349892479463033808393249475608933110640580388877206700116661070302382578388629, 122640993538161410588195475312610802051543155060328971488277224112081166784263153107636108815824, 695403107966797625391061914491496301998976621394944936827202540832952594905520247784142392337171, 108297989103402878258100342544600235524390749601427490182149765480916965811652000881230504838949, 3348901603647903020607356217291999644800579775392251732059562193080862524671584235203807354488, 632094372828241320671255647451901056399237760301503199444470380543753167478243100611604222284853, 54758061879225024125896909645034267106973514243188358677311238070832154883782028437203621709276]
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))
#Spirit{Gr3at__J0b!_You_can_be___better!}
5.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]
只给出了生成的伪随机数,根据法4求出模数m
再求出a,b,此时方法同例题4.
from Crypto.Util.number import *
from gmpy2 import gcd,invert
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])))
for n in all_n:
n=abs(n)
if n==1:
continue
a=(s[2]-s[1])*invert((s[1]-s[0]),n)%n
ani=invert(a,n)
b=(s[1]-a*s[0])%n
seed = (ani*(s[0]-b))%n
plaintext=seed
print(long_to_bytes(plaintext))
6.华为AI冬令营一道类似题
题目:
import random
from sympy import nextprime
from Crypto.Util.number import *
from gmpy2 import *
from typing import *
flag = b'DASCTF{********************************}'
def lcg(seed,params):
(m,c,n)=params
s = seed % n
while True:
s = (m * s + c) % n
yield s
seed = getPrime(128)
m = getPrime(128)
c = getPrime(128)
n = getPrime(129)
key_stream = lcg(seed,(m,c,n))
num=[]
for _ in range(6):
num.append(next(key_stream))
secret = next(key_stream)
e = nextprime(secret)
p = getPrime(1024)
q = getPrime(1024)
r = getPrime(1024)
flag = bytes_to_long(flag)
flag ^= flag >> 10
print(p)
print(p*q*r)
print(pow(flag,e,p*q*r))
num = [58605992502479537155943965904595921273, 525605798656979919420608964379033982804, 607738431135489138748992347244318940466, 631747898536603358381419028993140907216, 13450658701001781564543219325486287717, 407826262741495712819054543462943222370]
p = 138092450043978032187397495330379791355629274237204650898232878263413301988536751004632087169676028049236253598677819980191406826529664613957150122788435561338344715937422320958238628877093605040078776555586363593650646481242888908171897232624141894446324625781720275455534977357099473212936612966142541689717
newN = 3373500409784821814490131118443028295231446638918191872866826078664586857545499510115664725311697632345156866795088640886074708893049896293408277232121045205172588091316164743124173177747110069553394872128870505076277498830601152723565030932360665298864122468812389923295873644041292977470736981439616767671752225297169001703767163460419431015014012924743881828753765788455996503018031103917461875346904941302752301152097427368052588291798732671143344833211267818507324812463058368199324367285019651028003000765054679485233317767201747568717493732406861626561470103436488978595267326521876995116542475030869904228103019888619123275263009931569375612626796485751453790231029224398879558668919940829341599982045260085645733137064910612640851525128951165660322666651603943749615559507563880191545144231282875004494643666234781231448702811026047613232622993307630737999918058511598922102840862761604680588858313364100914751476403
c = 40522976224675404992818282038409183193065303107530049168092540620105120083552580372904554927069109321998620410524986748598618388761467715127564839742806614159382512978830563949967053562802375030363283879451081474764301602860367140250483857874335594802704634427276762179861996608105102610424633434334897307449739846880323406404392707133580686043181007091235341464802410874449708870610192494627811013526751435468963111672237058189288520084494533786573065843704621915085789731723587760910378534773137633519620193203450046994466154848079413319979993890764583887936777316159487010002407093187269512820453207591173395762513970799972839858119501585885277954258269483363133460240339866272358522431904252286259542327658731232568465990008278265227086114042064326334937705758042097987623388556184022737180944807660792992413039097516526454455063218161704505837882378018400687043158628503465274374703624257222504948612055237771581019005
脚本如下:
from Crypto.Util.number import *
def gcd(a,b):
if(b == 0):
return a
else:
return gcd(b,a % b)
s = [58605992502479537155943965904595921273, 525605798656979919420608964379033982804, 607738431135489138748992347244318940466, 631747898536603358381419028993140907216, 13450658701001781564543219325486287717, 407826262741495712819054543462943222370]
t = []
all_n = []
for i in range(6):
t.append(s[i] - s[i - 1])
for i in range(4):
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
m = (s[2] - s[1]) * MMI((s[1] - s[0]), n) % n
ani = MMI(m,n)
c = (s[1] - m * s[0]) % n
seed = (ani * (s[0] - c)) % n
print("n = ",n)
print("m = ",m)
print("c = ",c)
print("seed = ",seed)
# n = 658483278832814360413959491304994965751
# m = 304895213771629215412875483024241040557
# c = 332633353219222389093389121471714482887
# seed = 233122372118782757817692638408531340431
接下来就是简单的rsa题分析了。
根据e = nextprime(secret),且secret = next(key_stream)可知,e为lcg的第7个数。
import random
from sympy import nextprime
from Crypto.Util.number import *
from gmpy2 import *
n = 658483278832814360413959491304994965751
m = 304895213771629215412875483024241040557
c = 332633353219222389093389121471714482887
seed = 233122372118782757817692638408531340431
def lcg(seed,params):
(m,c,n)=params
s = seed % n
while True:
s = (m * s + c) % n
yield s
key_stream = lcg(seed,(m,c,n))
num=[]
for _ in range(6):
num.append(next(key_stream))
secret = next(key_stream)
e = nextprime(secret)
# e = 176683449265430137948016253982177600477
解密过程如下(手写。。。不会用电脑写公式。。。。。下次学。。。。。。。
exp:
import gmpy2
p = 138092450043978032187397495330379791355629274237204650898232878263413301988536751004632087169676028049236253598677819980191406826529664613957150122788435561338344715937422320958238628877093605040078776555586363593650646481242888908171897232624141894446324625781720275455534977357099473212936612966142541689717
c = 40522976224675404992818282038409183193065303107530049168092540620105120083552580372904554927069109321998620410524986748598618388761467715127564839742806614159382512978830563949967053562802375030363283879451081474764301602860367140250483857874335594802704634427276762179861996608105102610424633434334897307449739846880323406404392707133580686043181007091235341464802410874449708870610192494627811013526751435468963111672237058189288520084494533786573065843704621915085789731723587760910378534773137633519620193203450046994466154848079413319979993890764583887936777316159487010002407093187269512820453207591173395762513970799972839858119501585885277954258269483363133460240339866272358522431904252286259542327658731232568465990008278265227086114042064326334937705758042097987623388556184022737180944807660792992413039097516526454455063218161704505837882378018400687043158628503465274374703624257222504948612055237771581019005
phi = p - 1
e = 176683449265430137948016253982177600477
d = gmpy2.invert(e, phi)
m = pow(c, d, p)
#m=569987504250336203008383799281952855095298052417061158522700484233183317916824291767569080757872
又因为flag=flag>>10.
m的前10位其实是明文的前10位,而m的10-20
位则是明文的前10
位和10-20
位的异或,由于我们知道明文的前10位,因此很容易恢复明文的10-20`位以此类推,可以恢复所有明文的比特位。
exp:
# from Crypto.Util.number import *
#enc=569987504250336203008383799281952855095298052417061158522700484233183317916824291767569080757872
# shift = 10
# def inverse_right(res, shift, bits=32):
# tmp = res
# for i in range(bits // shift):
# tmp = res ^ tmp >> shift
# return tmp
# flag = inverse_right(enc,shift,enc.bit_length())
# print(bytes.fromhex(hex(flag)[2:].strip("0xL")))
#DASCTF{b19998fb5acd197e441029b37bc246d7}
参考:
《图解密码学》12章 --[日]结城浩著
https://blog.****.net/superprintf/article/details/108964563
https://blog.****.net/lion19930924/article/details/61926019
https://blog.****.net/u014634338/article/details/40210435
原文地址:https://www.cnblogs.com/pupububu/p/14339135.html
下一篇: SAS 常用函数和使用实例分析
推荐阅读
-
1-29 Metaverse Daily:华纳将推出虚拟音乐会;詹姆斯与 Crypto 签约;披头士 NFT 开始发售
-
也许多亏了 Crypto 案,电子证物的程序正义问题终于得到了保障
-
CTF-Crypto 必须具备自动解密魔法 python-Ciphey (详细安装介绍)
-
CTF-Crypto 必须拥有自动解密神器 - Ciphey
-
crypto/x509/pkix (crypto/x509/pkix) - [ Go 中文开发者手册 ] - 本地在线手册 - php中文网
-
Crypto 背后的人回来了:上次是厕所,这次是灵鸽
-
SM4 javax.crypto.BadPaddingException: pad block corrupted
-
crypto/cipher (加密/密码) - [ Go 中文开发手册 ] - 在线原生手册 - php中文网
-
crypto/x509 (encryption/x509) - [ Go 中文开发手册 ] - 本地在线手册 - php中文网
-
buuctf-Crypto rsarsa 1