古典密码-仿射密码

仿射密码同样也是基于单个字符与密钥之间进行计算进行加解密,凯撒密码与密钥进行加法进行加密,而仿射加密同时使用了加法和乘法来进行加密。

章节:

  1. 仿射密码加密原理:选择有效的密钥、求最大公约数-辗转相除法、仿射密码加密流程
  2. 仿射密码解密原理:乘法加密的解密、计算逆模-扩展欧几里得算法、仿射密码解密流程
  3. 仿射密码破解原理:
  4. 仿射密码加密代码+应用
  5. 仿射密码解密代码+应用
  6. 仿射密码破解代码+应用

1 仿射密码加密原理

回顾一下,凯撒密码是如何进行加密或者解密的。凯撒密码加密时,需要加密的字符会加上密钥的值从而得到加密的字符;凯撒密码解密时,需要解密的字符会减去密钥的值从而得到解密的字符。

仿射密码同样也是基于单个字符与密钥之间进行计算进行加解密,凯撒密码与密钥进行加法进行加密,而仿射加密同时使用了加法和乘法来进行加密。

什么是乘法加密。假设存在字典如下:

如果使用密钥3对字符“C”进行乘法加密,首先在字典中找到“C”的下标为2,然后使用下标乘以密钥的方式计算密文字符的下标(即2 × 3 = 6),6在字典中对应的字符为“G”,因此字符“G”密文字符,如图 1所示。

图1 乘法加密

如果只是用乘法加密会出现一个问题,即无论密钥为多少,字符“A”的下标0乘上任意数还是0,因此字符“A”的加密字符始终为“A”字符本身。为了解决这个问题,仿射密码在完成乘法加密之后会使用第二个密钥来完成凯撒加密。

当计算得到的密文字符超过字典字符数量时,仿射密码同样使用了与凯撒密码类似的回环机制,即与字典字符总数取余来确定密文字符的下标。例如,使用密钥3(乘法加密)和密钥1(凯撒加密)对字符“J”进行仿射加密;“J”下标为9,计算密文字符下标为9 × 3 + 1= 28;因为28超过了字典字符的个数26,因此取余计算28 % 26 = 2;最终下标为2的字符“C”则为加密字符。

1.1 选择有效的密钥

需要注意的是,密钥并不能随便选择,乘法加密时的密钥必须和字符字典的长度互为质数,即他们没有除了1以外的公因子,否则字典中多个字符将会映射到同一个密文字符上。

例如,2和26存在公因子2。以2作为密钥,对26个字母进行乘法加密,映射的密文如下:

从密文字符可以看到,字符“A”和字符“N”经过密钥为2的乘法加密后,都被映射到了字符“A”上;字符“B”和字符“O”经过密钥为2的乘法加密后,都被映射到了字符“C”上,等等。这上述情况下进行解密时,对于密文字符“A”,无法判别对应的明文字符是是“A”还是“N”。

例如,11和26互质。以11作为密钥,对26个字母进行乘法加密,映射的密文如下:

从密文字符中可以看到,当密钥和字典字符长度互质的情况下,字典中的每个字符都会作为密文字符被映射到,从而不会出现两个明文字符映射到同一个加密字符的情况,如图 2所示。

图2 不互质与互质映射举例

1.2 求最大公约数-辗转相除法

在进行仿射加密时,需要使用与字典字符长度互质的数来作为乘法加密密钥,即在选取乘法密钥时,必须保证密钥一定与字典字符长度互质。

两个数互质,则表示这两个数的最大公约数是1,即我们只要找到与字典字符长度最大公约是为1的数即可。

欧几里得提出了辗转相除法来计算两个指定数之间的最大公约数,在选取密钥时使用辗转相除法计算密钥和字典字符长度的最大公约数,计算结果若为1,则表示密钥与字典字符长度互质,该密钥有效。

两个数a和b的最大公约数可写成gcd(a,b),辗转相除法的计算原理依赖于如下定理:

$$
\operatorname{gcd}(a, b)=\operatorname{gcd}(b, a \bmod b)
$$
公式1

该定理证明如下:

(还没写)

举例:辗转相除法计算过程求1997和615的最大公约数。

1.3 仿射密码加密流程

通过之前的原理部分,我们知道了仿射密码需要两个密钥:密钥A和密钥B。其中密钥A用于乘以字符对应的下标,其乘积再加上密钥B,最后对字符字典长度取模从而得到最终的密文字符下标。仿射密码加密流程如图 3所示:

图 3 仿射密码加密流程

2 仿射密码解密原理

2.1 乘法加密的解密

对仿射密码进行解密,密文字符需要乘以密钥和字典字符长度的逆模再与字典字符长度取余来进行解密。解密公式如下,其中c表示密文字符下标,i表示密钥和字典字符长度的逆模,n表示字典字符长度,m表示解密后的明文字符下标。

$$
m=(c \times i) \% n
$$
公式2

c和n逆模由如下表达式表示,其中i便是逆模。

$$
(c \times i) \bmod n=1
$$
公式3

举例说明,在之前的例子中使用了密钥11进行乘法加密,字符“J”的下标为9,因此经过乘法加密( 9 * 11 ) % 26的结果为21,21对应的字符“V”即为加密字符,如图 4所示

图 4 乘法加密

对密文字符“V”进行解密,需要将“V”的下标乘以密钥11和字典字符长度26的逆模。求11和26的逆模的一种方法为对公式 3进行暴力求解,即对如下表达式中的i进行暴力求解。

$$
(11 \times i) \bmod 26=1
$$

通过暴力求解可得到,当i等于19时候, (11 × 19) mod 26 的结果为1,那么19则为11和26的逆模。

对“V”进行解密,“V”的下标为21,根据公式 2进行计算如下:

$$
(21 \times 19) \% 26=9
$$

计算结果9即为密文“V”解密后的明文下标,对应的明文字符为“J”。解密流程如所示。

图 5 乘法解密

2.2 计算模逆- 扩展欧几里得算法

使用暴力的方法计算逆模非常的耗时,通常情况下使用扩展欧几里得算法计算逆模。

Python实现的欧几里得算法函数如下,只要传入的两个参数互质,则该函数将返回a的逆模。

# 逆模运算
def findModInverse(a,m):
    # 如果a与m不互为素数,则返回
    if gcd(a,m) != 1:
        return None
    u1,u2,u3 = 1,0,a
    v1,v2,v3 = 0,1,m
    while v3 != 0:
        q = u3 // v3 #整除
        v1,v2,v3,u1,u2,u3 = (u1 - q * v1),(u2 - q * v2),(u3 - q * v3),v1,v2,v3
    return u1 % m

2.3 仿射密码解密流程

仿射密码加密需要两个密钥:密钥A和密钥B。其中密钥A用于乘以字符对应的下标,其乘积再加上密钥B,最后对字符字典长度取模从而得到最终的密文字符下标。

与之对应的解密则使用了与加密相反的操作,即密文字符首先减去密钥B,然后乘以密钥A的逆模,乘积再对字典字符长度取模,最终得到明文。

仿射密码解密流程如图 6所示:

图 6 仿射密码加密流程

3 仿射密码破解原理

暴力破解就完事了

4 仿射密码加密代码+应用

求a和b的最大公约数函数:

# 求a和b的最大公约数
def gcd(a,b):
    while a != 0:
        a,b = b%a,a
    return b

仿射加密函数:

def affineEncrypt(text,key):
    keyA,keyB = getKeys(key)
    print("keyA:{},keyB:{}".format(keyA,keyB))
    if checkKeys(keyA,keyB,1):
        return "加密错误!"
    cipherText = ""
    for itemText in text:
        if itemText in symbols:
            itemTextIndex = symbols.find(itemText)
            cipherText += symbols[(itemTextIndex * keyA + keyB) % len(symbols)]
        else:
            cipherText += itemText
    return cipherText

应用:

生成的随机密钥分解后的KeyA和字典字符长度互质。

对“昨天的然然好可爱啊!”加密。

5 仿射密码解密代码+应用

仿射密码解密函数:

def affineDecrypt(cipherText,key):
    keyA,keyB = getKeys(key)
#     print("keyA:{},keyB:{}".format(keyA,keyB))
    if checkKeys(keyA,keyB,0):
        return "解密错误!"
    plaintText = ""
    modInverseOfKeyA = findModInverse(keyA,len(symbols))
    for itemText in cipherText:
        if itemText in symbols:
            itemTextIndex = symbols.find(itemText)
            plaintText += symbols[(itemTextIndex-keyB) * modInverseOfKeyA % len(symbols)]
        else:
            plaintText += itemText
    return plaintText

应用:

得到明文“昨天的然然好可爱啊!”

6 仿射密码破解代码+应用

仿射密码破解函数:

def affineHacker(text):
    resultList = []
    hackNum = len(symbols) ** 2
    for key in range(hackNum) :
        if key % 1000 == 0:
            print("{}/{}".format(key,hackNum))
        keyA = getKeys(key)[0]
        if gcd(keyA,len(symbols)) != 1:
            continue
        decryptText = affineDecrypt(text,key)
        result = checkEn(decryptText)
        if result >= 0.8:
            print("key:{},明文:{}".format(key,decryptText))
            resultList.append([result,key,decryptText])
    return resultList

应用:

判断解密后的单词中是正常的英语单词的比例是否超过0.6来检测破解是否成功,是我傻了才用来检测拼音。

换一个密文再试试:

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注