仿射函数（仿射密码的加密与解密）

简介

仿射密码为单表加密的一种，字母系统中所有字母都藉一简单数学方程加密，对应至数值，或转回字母。它是一种替换密码，利用加密函数一个字母对一个字母的加密.

加密函数

加密函数是 E(x)= (ax + b) (mod m)，其中，a和m互质，m是字符集的大小。

（例如，26即是以26个字母作为编码，当m是26时，a必须是1，3，5，7，9，11，15，17，19，21，23，25其中之一）

解密函数

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

很容易通过加密函数来推导：

a⋅x+b ≡ y mod m

a⋅x ≡ (y−b) mod m

x ≡ a^−1 ⋅(y−b) mod m

乘法逆元

群G中任意一个元素a，都在G中有唯一的逆元a`，具有性质aa` = a`a = e，其中e为群的单位元。

例如：7 * 15 = 1 mod 26

15就是7的乘法逆元

例题

假设密钥K= (7,3), 使用仿射密码体制加密单词hot并对得到的密文进行解密。

加密：

加密函数： E(x)= (7x + 3) (mod 26)

根据上面英文字母编码表得到X

解密：

解密函数：

求得a的乘法逆元为15

D(x) = 15(x - 3) (mod 26)

代码（python版）

''' 仿射密码K = (a,b) 加密函数是E(x)= (ax + b) (mod 26) 解密函数为D(x) = (a^-1)(x - b) (mod 26)，其中a^-1是a的乘法逆元 ''' # 加密 def enc(a, b, e): c = [] for i in e: temp = ((ord(i) - 97) * a + b) % 26 + 97 # a的ascii码是97 c.append(chr(temp)) print(''.join(c).upper()) # 遍历得到a的乘法逆元 def get_multiplicative_inverse(a): for i in range(1, 27): if a * i % 26 == 1: return i # 解密 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)