仿射密码(Affine Cipher)体制的加密和解密
代换密码的另一个特殊情形是仿射密码,它的加密函数定义为 e(x)=(ax+b)mod 26,其中a,b∈Z26 —— 因为这样的函数被称为仿射函数,所以这样的密码体制也被称为仿射密码(当a=1时,正好是移位密码)。
为了能对密文进行解密,必须保证所选用的仿射函数是一个单射函数,则对于任意的y∈Z26,同余方程ax+b≡y(mod 26)有唯一解x,并且等价于ax≡y-b(mod 26)。当y遍历Z26时,y-b也遍历Z26,故同余方程有唯一解的充要条件是gcd(a,26)=1。
单射:设f是由集合A到集合B的映射,如果所有x,y∈A,且x≠y,都有f(x)≠f(y),则称f为由A到B的单射 —— 百度百科
gcd:最大公约数
定理 1.1:设a∈Zm,对任意的b∈Zm,同余方程ax≡b(mod m)有唯一解x∈Zm的充要条件是gcd(a,m)=1。故当m=26,所有与26互素的数为a=1,3,5,7,9,11,15,17,19,21,23,25,b的取值可以为Z26中的任何数,因此仿射密码的密钥空间为12*26=312。(密钥空间很小,很不安全)
定理1.2:假定
这里pi均为素数且互不相同,ei>0, 1≤i≤n。则
如果m=60,则Φ(60)=2*2*4=16,所以此仿射密码的密钥空间大小为16*60=960。
根据定理1.2,60=22*3*5,98=2*72
乘法逆:设a∈Zm,若存在a'∈Zm,使得aa'≡a'a≡1(mod m),则a'称为a在上的乘法逆,将其记为a-1mod m。在m是固定的情形下,也可将其简记为a-1。根据定理1.1,定理1.2和乘法逆,有如下仿射密码的定义:
代码实现(Python 3)
def affine_cipher_encrypt(message:str, keyA=7, keyB=3): SYMBOLS = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' translated = '' message = message.upper() for symbol in message: if symbol in SYMBOLS: symbolIndex = SYMBOLS.find(symbol) translatedIndex= (keyA * symbolIndex + keyB)%26 translated = translated + SYMBOLS[translatedIndex] else: translated = translated + symbol print(translated) def affine_cipher_decrypt(message:str, keyA=7, keyB=3): SYMBOLS = 'abcdefghijklmnopqrstuvwxyz' translated = '' message = message.lower() keyA1 = multiplicative_inverse(keyA) for symbol in message: if symbol in SYMBOLS: symbolIndex = SYMBOLS.find(symbol) translatedIndex= (keyA1 * (symbolIndex - keyB))%26 translated = translated + SYMBOLS[translatedIndex] else: translated = translated + symbol print(translated) def multiplicative_inverse(key,m=26): for n in range(m): if key*n%m==1: print(f'The multiplicative_inverse of key {key} is {n}.') return n return -1