古典密码之仿射密码

一杯敬故乡，一杯敬远方

算法分析

1. 仿射密码结合了移位密码和乘数密码的特点，是移位密码和乘数密码的组合。
2. 仿射密码的加密算法就是一个线性变化，即对明文字符x，对应的密文字符为y=ax+b(mod26)其中，a, b属于Z26且gcd(a,b)=1
3. 实现过程：

• 选取a，b两个参数，其中gcd(a, 26)＝1
• 加密变换： c＝ a∗𝑚＋b 𝑚𝑜𝑑 26
a=1时，移位密码
  b=1时，乘数密码
• 解密变换： 𝑚＝ (c−b)∗a^(−1) 𝑚𝑜𝑑 26

---

算法实现

# 暴力破解
la = [1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25]
lb = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13,
      14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]

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

# 加密
def encrypt(m, c, a, b):
    for i in range(len(m)):
        # 加密成相应的大写字母
        c.append(chr(((ord(m[i]) - 97) * a + b) % 26 + 65))
    d = ''.join(c)
    print(d)

# 求逆元
def niyuan(a, b):
    ny = 1
    while (a * ny) % b != 1:
        ny += 1
    return ny

# 解密
def decrypt(c, k, b):
    mw = []
    for i in range(len(c)):
        tem = ord(c[i]) - 65 - b
        if tem < 0:
            tem += 26
        mw.append(chr((k * tem) % 26 + 97))
    print("k=" + str(k) + ", b=" + str(b) + "时，解密后的明文为：")
    res = ''.join(mw)
    print(res)

#实现
if __name__ == "__main__":
    # 明文
    m = 'ifnottothesunforsmilingwarmisstillinthesuntherebutwewilllaughmoreconfidentcalmifturnedtofoundhisownshadowappropriateescapethesunwillbethroughtheheartwarmeachplacebehindthecornerifanoutstretchedpalmcannotfallbutterflythenclenchedwavingarmsgivenpowerificanthavebrightsmileitwillfacetothesunshineandsunshinesmiletogetherinfullbloom'
    # 密文
    c = []
    x, y = input("请输入a和b: ").split()
    a = int(x)
    b = int(y)
    while gcd(a, b) != 1:
        x, y = input("a和b不互素，请重新输入a和b: ").split()
        a = int(x)
        b = int(y)
    print("明文内容为：")
    print(m)
    print("加密后的密文为：")
    encrypt(m, c, a, b)
    print("知道密钥破解：")
    k = niyuan(a, 26)
    decrypt(c, k, b)
    print("不知道秘钥破解，暴力破解如下： ")
    for i in range(0, 12):
        for j in range(0, 26):
            decrypt(c, la[i], lb[j])

---

加密与解密

• 加密：输入a = 3, b = 4时，加密结果如图所示：

• 解密：知道秘钥k = 9, b = 4 （k为a的逆元）时，解出相应明文。

---

正确性

由于算法的前提要求gcd(a,26)==1, 从而使加密函数c＝ a∗𝑚＋b 𝑚𝑜𝑑 26是一个单射函数，故其解必然是唯一的。即，gcd(a,26)==1保证了仿射加密函数是一个双射函数，故算法正确。

---

安全性分析

1. 此密码算法安全性较弱。由算法的实现可知，此算法的秘钥空间大小为12*26 – 1 ==311（去除a = 1, b = 0时的情况）且a = 1,3,5,7,9,11,15,17,19,21,23,25 故很容易便能够通过暴力破解获得明文。

1. 还可以通过统计分析破解：代码如下

#统计破解仿射密码

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

if __name__ == "__main__":
    # a = 3， b = 4时的密文
    m = "CTRUJJUJZQGMRTUDGOCLCRWSEDOCGGJCLLCRJZQGMRJZQDQHMJSQSCLLLEMWZOUDQKURTCNQRJKELOCTJMDRQNJUTUMRNZCGUSRGZENUSEXXDUXDCEJQQGKEXQJZQGMRSCLLHQJZDUMWZJZQZQEDJSEDOQEKZXLEKQHQZCRNJZQKUDRQDCTERUMJGJDQJKZQNXELOKERRUJTELLHMJJQDTLYJZQRKLQRKZQNSEPCRWEDOGWCPQRXUSQDCTCKERJZEPQHDCWZJGOCLQCJSCLLTEKQJUJZQGMRGZCRQERNGMRGZCRQGOCLQJUWQJZQDCRTMLLHLUUO"
    # 根据统计而得出的实际各字母出现的概率
    reality = dict(a=0.082, b=0.015, c=0.028, d=0.043, e=0.127, f=0.022, g=0.02, h=0.061, i=0.07,
                   j=0.002, k=0.008, l=0.04, m=0.024, n=0.067, o=0.075, p=0.019, q=0.001, r=0.06,
                   s=0.063, t=0.091, u=0.028, v=0.01, w=0.023, x=0.001, y=0.02, z=0.001)
    # 对字典中各字母出现的概率进行降序排序
    order = dict(sorted(reality.items(), key = lambda x:x[1], reverse = True))
    print("统计中各字母出现的概率从小到大如下： ")
    print(order)
    # 统计密文中各字母出现的次数
    example = {}
    for i in m:
      example[i] = m.count(i)
    # 对字典中各字母出现的次数进行降序排序
    result = dict(sorted(example.items(), key = lambda x:x[1], reverse = True))
    print("计算得的密文中个字母的出现的次数从大到小如下： ")
    print(result)

    # #从结果可推测：Q由e加密而得，J由t加密而得，进行验算。
    # (a*4+b)%26==16
    # (a*19+b)%26==9
    # 从而计算出a=3,b=4
    # (a*K)%26==1,求得k=9
    # 用k=9,b=4进行解密可得出明文
    print("根据统计分析，加密所用的a, b可能为：")
    for i in range(1,26):
        for j in range(1,26):
            if (i*4+j)%26==16 and (i*19+j)%26==9:
                if gcd(i, j)==1:
                    print("a="+str(i), "b="+str(j))

运行结果为（此处以破解a=3, b=4时得出的密文）：

如图所示，正确解出a, b再用(a*k)%26==1,求得k=9用k=9,b=4进行解密可得出明文。

1. 还可以通过差分分析进行破解。对于仿射密码来说，“差分”是模26减法，那么，在不知道两对明密文对（M1，C1）（M2, C2）的情况下，只需要知道M1-M2和C1-C2便可以确定a。因为

   C1 = aM1 + b(mod26)
   C2 = aM2 + b(mod26)
   易得，a = (C1 – C2)/(M1 – M2) (mod26)

得到a 后，进一步找到b就很容易了。

---