LCG和仿射密码(萌新总结)
|
密码
|
352

1010 字
|
5 分钟

LCG(线性同余生成器)

定义

LCG本质是一种伪随机数生成器和流密码的一种，简而言之是一种生成伪随机数的方法。

                          Xn+1=(a*Xn+b)mod m

参数解析：

1.乘数a:必须是一个与m互素的正整数。
2.增量b:必须是一个与m互素的正整数。
3.模数m:必须一个大于0的正整数。一般是一个比较大的素数或者是2的幂，以便提供较长的周期长度。
4.Xn是第n个随机数，X0被称作种子值，全部的X由X0得来。

 

常用公式

公式一.由Xn+1反推Xn

其实就是把上面的式子移项处理，就可以得到Xn=((Xn+1-b)*a-1) mod m,a-1指的是模逆元。

 

公式二.求a

已知Xn+1=(a*Xn+b)mod m，Xn=(a*Xn-1)mod m
那么我们就可以直接联合求解，得到a=((Xn+1-Xn)*(Xn-Xn-1)-1)mod m

 

公式三.求b

把最上面的式子变形一下就好了，b=(Xn+1-a*Xn)mod m

 

公式四.求m

怎么说呢，构造一个等比数列就可以去求m了。

tn=Xn+1-Xn=(a*Xn+b)-(a*Xn-1+b)=a*(Xn-Xn-1)=a*tn-1 mod m

Tn=tn+1*tn-1-tn*tn=a*a*tn-1*tn-1-a*tn-1*a*tn-1=0 mod m

那么Tn就是m的倍数，那么gcd(Tn,Tn-1)就是m

 

常见题型

LCG_1.已知a,b,m，实际上就是由Xn+1推Xn

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(f'a = {lcg.a}')
print(f'b = {lcg.b}')
print(f'm = {lcg.m}')
print(lcg.generate())


'''
a = 113439939100914101419354202285461590291215238896870692949311811932229780896397
b = 72690056717043801599061138120661051737492950240498432137862769084012701248181
m = 72097313349570386649549374079845053721904511050364850556329251464748004927777
9772191239287471628073298955242262680551177666345371468122081567252276480156
'''
这种类型的题就是最简单，主要是问题是反推多少项的问题，但是有了’NSSCTF{‘就直接查找就好了

import gmpy2
import libnum

a = 113439939100914101419354202285461590291215238896870692949311811932229780896397
b = 72690056717043801599061138120661051737492950240498432137862769084012701248181
m = 72097313349570386649549374079845053721904511050364850556329251464748004927777
c=9772191239287471628073298955242262680551177666345371468122081567252276480156

# c=(a*c0+b)%m
a_1=gmpy2.invert(a,m)

for i in range(2**16):
    c = (c - b) * a_1 % m
    #print(c)
    flag=libnum.n2s(int(c))
    if b'NSSCTF{' in flag:
        print(flag)
        break

 

LCG_2.已知a,m，未知b，实际上就是先求b再求flag

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(f'a = {lcg.a}')
print(f'm = {lcg.m}')
print(lcg.generate())
print(lcg.generate())

'''
a = 83968440254358975953360088805517488739689448515913931281582194839594954862517
m = 77161425490597512806099499399561161959645895427463118872087051902811605680317
43959768681328408257423567932475057408934775157371406900460140947365416240650
8052043336238864355872102889254781281466728072798160448260752595038552944808
'''
把上面的公式敲出来就好了

import gmpy2
import libnum
from Crypto.Util.number import isPrime

a = 83968440254358975953360088805517488739689448515913931281582194839594954862517
m = 77161425490597512806099499399561161959645895427463118872087051902811605680317
c1=43959768681328408257423567932475057408934775157371406900460140947365416240650
c2=8052043336238864355872102889254781281466728072798160448260752595038552944808

b=(c2-a*c1) % m
#print(b)
#print(gmpy2.gcd(b,m))
a_1 = gmpy2.invert(a,m)
c = c1

for i in range(2**16):
    c = (c-b) * a_1 % m
    flag = libnum.n2s(int(c))

    if b'NSSCTF' in flag:
        print(flag)
        break

 

LCG_3.只知道m，先求a，b，再求flag

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(f'm = {lcg.m}')
print(lcg.generate())
print(lcg.generate())
print(lcg.generate())

'''
m = 96343920769213509183566159649645883498232615147408833719260458991750774595569
10252710164251491500439276567353270040858009893278574805365710282130751735178
45921408119394697679791444870712342819994277665465694974769614615154688489325
27580830484789044454303424960338587428190874764114011948712258959481449527087
'''

 

脚本

import gmpy2
import libnum

m = 96343920769213509183566159649645883498232615147408833719260458991750774595569
c1 = 10252710164251491500439276567353270040858009893278574805365710282130751735178
c2 = 45921408119394697679791444870712342819994277665465694974769614615154688489325
c3 = 27580830484789044454303424960338587428190874764114011948712258959481449527087

a = (c3-c2) * gmpy2.invert(c2-c1,m) % m
# print(gmpy2.gcd(a,m))
a_1 = gmpy2.invert(a,m)
b = (c2-a*c1) % m
# print(gmpy2.gcd(b,m))
c = c1
for i in range(2**16):
    c = (c-b) * a_1 % m
    flag = libnum.n2s(int(c))

    if b'NSSCTF{' in flag:
        print(flag)
        break

 

LCG_4.abm都未知，只给了多组输出

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

'''
47513456973995038401745402734715062697203139056061145149400619356555247755807
57250853157569177664354712595458385047274531304709190064872568447414717938749
30083421760501477670128918578491346192479634327952674530130693136467154794135
38739029019071698539301566649413274114468266283936163804522278316663267625091
42506270962409723585330663340839465445484970240895653869393419413017237427900
'''

 

思路就是先求出m，然后就是LCG_3

import gmpy2
import libnum
from Crypto.Util.number import GCD, isPrime, long_to_bytes

c=[47513456973995038401745402734715062697203139056061145149400619356555247755807,
   57250853157569177664354712595458385047274531304709190064872568447414717938749,
   30083421760501477670128918578491346192479634327952674530130693136467154794135,
   38739029019071698539301566649413274114468266283936163804522278316663267625091,
   42506270962409723585330663340839465445484970240895653869393419413017237427900]

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

m = 0
for i in range(1,len(t)-1):
    m = GCD(t[i+1]*t[i-1]-t[i]**2, m)
# print(isPrime(m))       False

m//=2
# print(isPrime(m))


a = (c[3]-c[2])*gmpy2.invert(c[2]-c[1],m) % m
b = (c[2]-a*c[1]) % m
# print(gmpy2.gcd(a,m))
# print(gmpy2.gcd(b,m))
a_1=gmpy2.invert(a,m)

for i in range(2**16):
    c[1] = (c[1]-b) * a_1 % m
    flag = long_to_bytes(c[1])

    if b'NSSCTF{' in flag:
        print(flag)
        break

 

LCG_5.

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

 

与LCG_4不同的点在于

self.seed = self.a * (self.seed - self.b) % self.m

 

这个时候，把右边拆开，就可以认为ab是一项，那么我们的式子还是可以认为ax+b，那么就和LCG_4差不多了

import gmpy2
from Crypto.Util.number import GCD, isPrime, long_to_bytes

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

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

m = 0
for i in range(1,len(t)-1):
    m = GCD(t[i+1]*t[i-1]-t[i]**2, m)
print(isPrime(m))   # False m的倍数
print(m)

for i in range(1,100):
    if isPrime(m//i):
        print(i)   # i是4
        m//=i
        break

a = (c[3]-c[2])*gmpy2.invert(c[2]-c[1],m) % m
b = (c[2]-a*c[1]) % m
# print(gmpy2.gcd(a,m))
# print(gmpy2.gcd(b,m))
a_1=gmpy2.invert(a,m)

for i in range(2**16):
    c[1] = (c[1]-b) * a_1 % m
    flag = long_to_bytes(c[1])

    if b'NSSCTF{' in flag:
        print(flag)
        break

 

LCG_6.

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

特殊点就是进行了两次加密，思路还是先求m，再求a，去构造等比数列

import gmpy2
from Crypto.Util.number import GCD, isPrime, long_to_bytes

c = [25445927935559969212648839062255651208014967526951331344342413906051118248013,
81572970970116732975667604095930675262596098540738447440566868976253289440293,
6956793925625110803779114150160476498676179542815207353218944386232051429289,
88042506866508011592456777776490262927213783361334741921985316105965255450508,
5652832125321707726481846809536180176877263519327268361130605456255558285092]

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

for i in range(1,len(t)-1):
   m = GCD(t[i+1]*t[i-1]-t[i]**2, m)
a = (c[3]-c[2])*gmpy2.invert(c[2]-c[1],m) % m
b = (c[2]-a*c[1]) % m 

a_1=gmpy2.invert(a,m)

for i in range(2**16):
   c[1] = (c[1]-b) * a_1 % m
   flag = long_to_bytes(c[1])
   if b'NSSCTF{' in flag:
      print(flag)
      break

 

 

 

 

 

仿射密码

一.定义

说实话，第一次遇到这个词的时候还以为是高中的几何变换和坐标变换，了解了以后发现还真有一点点相似，感觉挺好玩的，就写一下。

仿射密码是一种单表加密，让字母系统中所有的字母都按着一个简单的数学方程去加密，再去对应到数值，或者是转成字符。本质就是进行了一次替换。

 

二.解释

例如一个用来加密的式子e(x)=(11x+6)mod 26。这就是前面说到的数学方程。

更加普遍的式子就是E(x)=(ax+b)mod m =c

那么解密直接式子变换就可以得到x=a^-1(c-b)mod m

（a^-1是a的乘法逆元）

关键点：在加密和求解时，用数组存储，所以下标会变，要注意这个点。

 

三.代码

解密

def dec(a, b, d):
a_mul_inv = get_multiplicative_inverse(a)
p = []
for i in d:
temp = (((ord(i) – 97) – b) * a_mul_inv) % 26 + 97
p.append(chr(temp))
print(”.join(p).upper())

if __name__ == “__main__”:
a, b = 7, 3
e = ‘hot’
# d = ‘axg’
enc(a, b, e)
# dec(a, b, d)mx

 

 

心如草木，向阳而生
密码笔记
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																				
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇