仿射密码(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