仿射密码解密（Affine Cipher）

本文主要是介绍仿射密码解密（Affine Cipher），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

仿射密码解密（Affine Cipher）

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

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

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

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

#欧几里德算法求最大公约数
def get_gcd(a, b):
k = a // b
remainder = a % b
	while remainder != 0:
a = b 
b = remainder
k = a // b
remainder = a % b
	return b
	
#改进欧几里得算法求线性方程的x与y
def get_(a, b):
	if b == 0:
		return 1, 0
	else:
k = a // b
remainder = a % b		
x1, y1 = get_(b, remainder)
x, y = y1, x1 - k * y1			
	return x, y
 
a = 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。

解密过程：

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

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

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

这篇关于仿射密码解密（Affine Cipher）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---