python实现多表代换加密与解密

一、原理

什么是多表代换？

多表代换加密是相对于单表代换加密而言的，

单表代换是密码学中最基础的一种加密方式。在加密时用一张自制字母表上的字母来代替明文上的字母（比如说A——Z，B——D）来达到加密。移位密码也属于单表代换，只不过比较有规律，相当于集体向前或向后。

这种加密方法最容易被破解。破解方法为统计法。在英语中，最常用的字母为E，所以在密文中代替E 的字母出现的频率也最高，由此便可破解。为了增加破译密码的难度，对于位于不同位置的同一个明文参考不同的代替表来进行替代，这样同一个明文所对应的密文也可能会是不一样的。就大大增加了破译的难度。

多表代换的数学表示

密钥为k,明文为m，加密为c，则有加密变换ek(m)=c1c2…cn，其中，ci=mi+ki mod q。

二、实例

维吉尼亚密码

在一个凯撒密码中，字母表中的每一字母都会作一定的偏移，例如偏移量为3时，A就转换为了D、B转换为了E……而维吉尼亚密码则是由一些偏移量不同的恺撒密码组成。

为了生成密码，需要使用表格法。这一表格（如图1所示）包括了26行字母表，每一行都由前一行向左偏移一位得到。具体使用哪一行字母表进行编译是基于密钥进行的，在过程中会不断地变换。
例如，假设明文为：

ATTACKATDAWN

选择某一关键词并重复而得到密钥，如关键词为LEMON时，密钥为：

LEMONLEMONLE

字母表如下：

对于明文的第一个字母A，对应密钥的第一个字母L，于是使用表格中L行字母表进行加密，得到密文第一个字母L。类似地，明文第二个字母为T，在表格中使用对应的E行进行加密，得到密文第二个字母X。以此类推，可以得到：

明文：ATTACKATDAWN密钥：LEMONLEMONLE密文：LXFOPVEFRNHR

解密的过程则与加密相反。例如：根据密钥第一个字母L所对应的L行字母表，发现密文第一个字母L位于A列，因而明文第一个字母为A。密钥第二个字母E对应E行字母表，而密文第二个字母X位于此行T列，因而明文第二个字母为T。以此类推便可得到明文。

用数字0-25代替字母A-Z，维吉尼亚密码的加密文法可以写成同余的形式：

解密方法则能写成：

博福特密码

博福特密码，是一种类似于维吉尼亚密码的替代密码，由弗朗西斯·蒲福（Francis Beaufort）发明。它最知名的应用是M-209密码机。博福特密码属于对等加密，即加密演算法与解密演算法相同。

它是按mod q减法运算的一种周期代替密码。即 ci+td=δi(mi+td)≡(ki-mi+td)(mod q)

所以，它和维吉尼亚密码类似，以ki为密钥的代替表是密文字母表为英文字母表逆序排列进行循环右移ki+1次形成的。例如，若ki=3(相当于字母D)，则明文和密文的对应关系如下：

明文：a b c d e f g h i j k l m n o p q r s t u v w x y z

密文：D C B A Z Y X W V U T S R Q P O N M L K J I H G F E

显然，博福特密码的解密变换为 mi+td≡δi(ci+td)≡(ki-ci+td)(modq)

因此，博福特密码的解密变换与加密变换相同。按博福特密码，以密钥ki加密相当于按下式的维吉尼亚加密：ci+td≡ (q-1)-mi+td

若按下式加密： ci+td≡(mi+td-ki)(modq)就得到变异的博福特密码，相应代替表示将明文字母表循环右移ki次而成。由于循环右移ki次等于循环左移(q-ki)次，即式ci+td≡(mi+td- ki)
(modq)等价于以(q-ki)为密钥的维吉尼亚密码。所以维吉尼亚密码和变异的博福特密码互为逆变换，若一个是加密运算，则另一个就是解密运算。

三、实现

实现步骤

1.秘钥生成

（1）随机生成3ⅹ3可逆矩阵A，计算其行列式并模去26，若其行列式等于零或与26不互素，则重新生成矩阵。矩阵生成后，再计算其在模26下的逆矩阵。

（2）生成3维向量B作为秘密密钥 。

2.加密

（1）输入一段英文，将其转变成0~25之间的整数，并将这些整数分为3个一组；

（2）对于 ，计算

（3）重复（2）直到所有的字母都加密完毕。

3.解密

（1）读入密文，将其转变成0~25之间的整数，并将这些整数分为3个一组；

（2）对于 ，计算

（3）重复（2）直到所有的字母都解密完毕。

实现代码

# -- coding: utf-8 --
import numpy as np
from numpy.linalg import *
import sys

# 矩阵取摸
def my_int_inv(mat, n=26):
    x = np.zeros(mat.shape, dtype=np.int16)
    for i in range(mat.shape[0]):
        for j in range(mat.shape[1]):
            x[i, j] = int(round(mat[i, j])) % n
    return x

# 欧几里德算法
def gcd(a, b):
    while a != 0:
        a, b = b % a, a
    return b

# 扩展欧几里德算法
def exgcd(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

q = input("输入矩阵A：（格式为：[[11, 2, 19], [5, 23, 25], [20, 7, 17]]）:")
a = np.mat(eval(q))
w = input("输入矩阵B：")
b = np.mat(eval(w))
# 原文与矩阵转换
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

# 加密算法
c = np.dot(a,m) + b
c = my_int_inv(c)

# 矩阵与密文转换
i = 0
h = 0
print("加密结果")
for i in range(int(len(elist) / 3)):
    j = 0
    for j in range(3):
        sys.stdout.write(chr(c[j, int(h / 3)] + 97))
        h = h + 1
print("")
# 求a的逆
a_inv = a.I
a_det = det(a)
a_adju = my_int_inv(a_det * a_inv)
a_det_inv = exgcd(int(round((det(a) % 26))), 26)
aa_inv = my_int_inv(a_det_inv * a_adju)

# 解密算法
m = (aa_inv * (c - b)) % 26

# 矩阵与原文转换
i = 0
h = 0
print("解密结果：")
for i in range(int(len(elist) / 3)):
    j = 0
    for j in range(3):
        sys.stdout.write(chr(m[j, int(h / 3)] + 97))
        h = h + 1
print("")