多表代换加解密基本实现

发表于 更新于 分类于
密码先生的作业罢了

多表代换加解密基本实现

hill逆矩阵.ppt 下载

第1章 密码学概述.ppt 下载

markdown中公式编辑教程 - 简书 (jianshu.com)

原理

多表代换密码首先将明文M分为由n个字母构成的分组M1,M2,M3,…,Mj ,对每个分组Mi的加密为：
$$
C_i \equiv\ AM_i + B\pmod n , i = 1,2,3,\ldots,j
$$
其中(A,B)是密钥,A是n*n的可逆矩阵，满足
$$
gcd(\begin{vmatrix}A\end{vmatrix},N)=1 (\begin{vmatrix}A\end{vmatrix}是行列式)
$$
其中：
$$
\begin{array}{}
B=(B_1,B_2,B_3,\ldots,B_n)^T \
C=(C_1,C_2,C_3,\ldots,C_n)^T \
M=(M_1,M_2,M_3,\ldots,M_n)^T \
\end{array}
$$
对密文分组Ci的解密为：
$$
M_i \equiv\ A^{-1} (C_i-B) \pmod n , i = 1,2,3,\ldots,j
$$

准备

需要对矩阵进行转置，求行列式，求逆矩阵，求伴随矩阵，取模等，用到了numpy库的函数。安装：

1
pip install numpy

矩阵必是二维的，所以使用的np.matrix对象存储数据，我在前面提到了array对象的各种用法，matrix和array对象大同小异，在个别方法的调用上有所不同。

下面简单介绍一下代码用到的函数，主要是matrix提供了矩阵乘运算，与array的按位乘有所不同。

  • np.linalg.det(matrix) 求伴随矩阵
  • np.transpose(matrix) 求转置矩阵，相当于matrix.T
  • matrix.I 求逆矩阵

方法变换返回的矩阵元素都是浮点数

  • np.round(array)求四舍五入，此外： np.floor() 、np.ceil()、np.trunc() ：向上，向下，截断

方法对矩阵元素取整

关键点

解密算法中，需要在mod26的情况下于对矩阵求逆，我们根据公式：

$$
\begin{bmatrix}M_n\end{bmatrix}^{-1}
\equiv\
\cfrac 1 {\begin{vmatrix}Mn\end{vmatrix}}
{\begin{vmatrix}M_n\end{vmatrix}}^*
\pmod n
$$
单纯的调用matix.I是不行的，数学方法里求逆矩阵，中间的1/mn是直接对行列式求倒，算法里这一步应该是求取行列式的逆元，也就是说
$$
\cfrac 1 {\begin{vmatrix}M_n\end{vmatrix}}\pmod n
$$
在数学和密码学里的意义是不同的，numpy没有直接求伴随矩阵的函数，所以我们需要反过来利用matrix.I和np.linalg.det(matrix)按位乘求出伴随矩阵，再对其乘法逆元后，这才是密码学要的 1/mn (mod26)

1
2
3
4
5
6
7
def inv(a:np.matrix)->np.matrix:
    a_inv = a.I
    a_det = np.linalg.det(a)
    a_adju = np.round((a_det * a_inv)).astype(np.int16)  # 求伴随矩阵
    a_det_inv = ex_gcd(int(round(np.linalg.det(a))), mod)  # 求行列式的mod26逆元
    get_inv = np.round((a_det_inv * a_adju)).astype(np.int16) % mod  # 相乘取模
    return get_inv

代码

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
import numpy as np
import math

mod=26
def ex_gcd(a, mod):
    """扩展欧几里德算法，内置"""
    if math.gcd(a, mod) != 1:
        return None
    u1, u2, u3 = 1, 0, a
    v1, v2, v3 = 0, 1, mod
    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 % mod
choose = input("加密E/解密D\n > ")
# eval("5*5") > 25 运算一个字符串表达式
a = np.mat(eval(input("输入矩阵A：（例二重矩阵格式为：[[a,b] , [c,d]]）:\n > ")),dtype=int)
b = np.mat(eval(input("输入矩阵B：（例二重矩阵格式为：[[e,f]]）:\n > ")),dtype=int)
if math.gcd(int(np.linalg.det(a)),mod)!=1:
    # a的行列式值需要与mod值互素，这一点在课本的定义里有提到，但是课本后的题目里并未体现
    print("a行列式的值",int(np.linalg.det(a)),mod,"不互素,gcd=",math.gcd(int(np.linalg.det(a)),mod))
    exit("a输入的行列式值不与26互素")
if np.linalg.det(a)==0:
    exit("a没有逆矩阵")
b = np.transpose(b)
get_m = input("输入加密或解密字符,小写字母：").strip().lower()
if not get_m.islower():
    print(get_m)
    exit("你的明文不是小数字母，不能还原")
m_ord=[]
for i in get_m:
    m_ord.append(ord(i)-97)
m_list=np.array(m_ord)
m_list.resize((len(get_m)//a.shape[0],a.shape[0],1))
def encode():
    c_list=[]
    for i in range(len(m_list)):
        m=m_list[i]
        c=((np.dot(a,m))+b)%26
        c_list.append(c)
    text=[]
    #print(c_list)
    c_list=np.array(c_list)
    for i in c_list.flatten():
        text.append(chr(i+97))
    return ''.join(text)
def inv(a:np.matrix)->np.matrix:
    a_inv = a.I
    a_det = np.linalg.det(a)
    a_adju = np.round((a_det * a_inv)).astype(np.int16) # 求伴随矩阵
    a_det_inv = ex_gcd(int(round(np.linalg.det(a))), mod) # 求行列式的mod26逆元
    get_inv = np.round((a_det_inv * a_adju)).astype(np.int16)%mod # 相乘取模
    return get_inv
def decode():
    c_list = []
    for i in range(len(m_list)):
        m = m_list[i]
        c = (np.dot(inv(a), (m-b))) % 26
        c_list.append(c)
    text = []
    #print(c_list)
    c_list = np.array(c_list)
    for i in c_list.flatten():
        text.append(chr(i+97))
    return ''.join(text)
if __name__ == "__main__":
    if choose == "E" or choose == "e":
        print(encode())
    elif choose == "D" or choose == "d":
        print(decode())
# e
# [[11,13,17],[5,7,2],[3,8,3]]
# [[1,1,1]]
# mednightf
# cremeauxf

总结

这次作业还有很多需要完善的地方，为了方便，只能对小写字母进行加密，而且当输入的m不是a阶数的倍数时应该会有异常。其实原来我只是想找一份代码水一水就提交的，参考了这个博主的代码： python实现多表代换加密与解密 - 朱鱼鱼的小本本朱鱼鱼的小本本 (zuicy.party)，然后发现些许逻辑错误和待完善地方，看得出来作者本来想对明文进行分组的，从这里：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 商业转载请联系作者获得授权，非商业转载请注明出处。
# For commercial use, please contact the author for authorization. For non-commercial use, please indicate the source.
# 协议(License)：署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)
# 作者(Author)：zuicy
# 链接(URL)：https://www.zuicy.party/2019/python%E5%AE%9E%E7%8E%B0%E5%A4%9A%E8%A1%A8%E4%BB%A3%E6%8D%A2%E5%8A%A0%E5%AF%86%E4%B8%8E%E8%A7%A3%E5%AF%86/
# 来源(Source)：朱鱼鱼的小本本

# 原文与矩阵转换
e = input("输入原文：")
elist = list(e)
for i in range(len(elist)):
    elist[i] = ord(elist[i]) - 97
x = np.zeros((3, int(len(elist) / 3)), dtype=int)
m = np.mat(x)
i = 0
h = 0
for i in range(int(len(elist) / 3)):
    j = 0
    for j in range(3):
        m[j, int(h / 3)] = elist[h]
        h = h + 1

博主对e进行了分组，但是后面直接一个c = np.dot(a,m) + b完事了，导致程序一次运行只能加密一个单元的m（m=3或者m=9），而对矩阵的手动循环赋值也显得很难受。但是博主的欧几里得法求逆元和求逆矩阵的函数还是很有参考价值。自己写这个作业时，就直接贴进代码里了。

多表代换对参数a的判断很严格，需要a的行列式和26互素，课本出的例题似乎并未满足这个条件。