仿射密码解密（Affine Cipher）

news/2024/11/8 2:41:41/

仿射密码是一种表单代换密码，字母表的每个字母相应的值使用一个简单的数学函数对应一个数值，再把对应数值转换成字母。

A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z
0	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

加密函数：E(x) = (ax + b) (mod m)，~~其中 a与b互质~~，其中 a与m互质，m是编码系统中字母的个数（通常都是26）。

解密函数：D(x) = $a^{-1}$ (x - b) (mod m)，其中 $a^{-1}$ 是 a 在 $Z_{m}$ 群的乘法逆元。

下面就要介绍一下什么叫做乘法逆元：emmmmmm，好吧，我也不会，没看懂。

这是网上关于使用欧几里得算法求解乘法逆元——Python的代码：（我是一个勤劳的搬运工，不要夸我^_^）

#欧几里德算法求最大公约数
def get_gcd(a, b):k = a // bremainder = a % bwhile remainder != 0:a = b b = remainderk = a // bremainder = a % breturn b#改进欧几里得算法求线性方程的x与y
def get_(a, b):if b == 0:return 1, 0else:k = a // bremainder = a % b		x1, y1 = get_(b, remainder)x, y = y1, x1 - k * y1			return x, ya = input('a:')
b = input('b:')
a, b = int(a), int(b)#将初始b的绝对值进行保存
if b < 0:m = abs(b)
else:m = b
flag = get_gcd(a, b)#判断最大公约数是否为1，若不是则没有逆元
if flag == 1:	x, y = get_(a, b)	x0 = x % m #对于Python '%'就是求模运算，因此不需要'+m'print("所求的逆元:",x0) #x0就是所求的逆元
else:print("Do not have!")

比如求5关于模26的乘法逆元

下面举个例子，求解仿射密码（搬运工上线...）：

我们以 E(x)=(5x+8) mod 26函数为例子进行介绍，加密字符串为 AFFINECIPHER，这里我们直接采用字母表26个字母作为编码系统

密文就是IHHWVCSWFRCP。

解密过程：

先求解5关于模26的乘法逆元，为21
解密函数就是D(x) = 21(x - 8) mod 26
解密如下

下面是关于求仿射密码的python3脚本（自己写的，有错请指正）：

#仿射密码解密
#改进欧几里得算法求线性方程的x与y
def get(a, b):if b == 0:return 1, 0else:k = a //bremainder = a % bx1, y1 = get(b, remainder)x, y =y1, x1 - k * y1return x, ys = input("请输入解密字符：").upper()
a = int(input("请输入a："))
b = int(input("请输入b："))#求a关于26的乘法逆元
x, y = get(a, 26)
a1 = x % 26l= len(s)
for i in range(l):cipher = a1 * (ord(s[i])- 65 - b) % 26res=chr(cipher + 65)print(res, end='')