仿射加密在本质上还是一个置换密码:如果说移位密码是一个常数级别的置换,那么,仿射加密是一个一次级别的置换


定义:

不妨设我们讨论的范围是所有的小写字母,其中a为0,z为25,其本质是一个Z26的整数环

假设X,Y,A,B是Z26整数环中的元素,A和B为密钥,X是原文,Y是密文

加密函数:Y=(AX+B)%26

解密函数:Y=(AX+B)%26,得到:X=(A的逆元)*(Y-B)%26


讨论:

A和B可以取值什么?

A必须满足条件:GCD(A,26)=1

因为如果不是1,那么在加密的时候,会发现多对一的情况,那么在解密的时候,会发现有元素没有对应的情况

B的值可以取任意,但是在同余的意义下,取0到25这26个值才是有意义的

所以,仿射加密的密钥空间为phi(m)*m

m为整数环中的元素个数,phi(x)为欧拉函数,表示的是1到x中,有多少个数与x互斥


注意:本质上还是一一对应的,只是偏移不同,所以在密码破译的难度上:

移位密码 < 仿射加密 < 维吉尼亚

移位密码找到一个对应关系剩下的都有,仿射加密可以统计字母频率,维吉尼亚需要爆破密钥长度,然后分密钥对应的位置来统计字母频率


光说不练假把式,拿后面的习题做一做就知道有没有理解这个了

书上24页习题1.11


已知a=7,b=22

解密以下密文:falszztysyjzyjkywjrztyjztyynaryjkyswarztyegyyj


方法一:反正是一一对应,正向暴力计算,就可以避免逆元的问题

letter = 'abcdefghijklmnopqrstuvwxyz'
word = 'falszztysyjzyjkywjrztyjztyynaryjkyswarztyegyyj'
flag = ''

a = 7
b = 22
for i in word:
	for j in range(0,len(letter)):
		if i == letter[(a*j+b)%26]:
			flag+=letter[j]
print flag

方法二:逆元,用扩展欧几里得计算啊!因为7与26互质,满足a取值的条件,可以计算
if __name__ == "__main__":
	letter = 'abcdefghijklmnopqrstuvwxyz'
	word = 'falszztysyjzyjkywjrztyjztyynaryjkyswarztyegyyj'
	flag = ''
	for i in word:
		flag += letter[modequation(7,(ord(i)-97+4)%26,26)]
	print flag

准备CTF工具,准备CTF比赛!