一、原理

什么是多表代换?

多表代换加密是相对于单表代换加密而言的,
单表代换是密码学中最基础的一种加密方式。在加密时用一张自制字母表上的字母来代替明文上的字母(比如说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](modq)
若按下式加密: 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("")

我好快乐,因为我是小熊软糖,小熊软糖(>▽<)!