本文附有丰富的代码，故文章冗长，请对照目录查阅，各大板块均有上下文提示
目录
古典密码简介
移位变换：
多表代换：
加密算法思路
仿射变换加密
多表代换加密
例题：仿射变换
例题：多表代换
古典密码简介
古典密码主要有置换和代换的方法。置换：字母重新排列，字母本身不变，但其位置改变了（凯撒密码、移位变换）。代换：将明文中的字符替代成其他字符（仿射变换、多表代换）。
在线性空间的变化中，古典加密就是移动并拉伸物体，让物体变得与原来不一样；解密解释将物体移动回去拉伸回去，恢复物体的原样。
凯撒密码 移位变换 仿射变换可以理解为单表代换，这三种古典密码实质上可以归根于多表代换的特殊形式——单表代换，即一个字母一组。
在此文中，考虑到凯撒密码、移位密码的简单性，仅介绍仿射变换、多表代换加密。加密算法的详细内容请自行查阅，以下仅列出变换公式
移位变换：
加密：
解密：
其中为密钥，且满足，, 为的乘法逆元。
多表代换：
将n个字母长的明文M分成M1，M2···Mi对每个分组：
加密：
解密：
为密钥，为的可逆矩阵(即 0" src="https://latex.codecogs.com/gif.latex?%5Cleft%20%7C%20A%20%5Cright%20%7C%3E%200" />)，且满足，为密文分组。
1.加密算法基础准备
在这两种古典加密中最重要的是求逆元，即 的乘法逆元 ， 的加密逆元 。两个逆元均用扩展欧几里得法。因此将扩展欧几里得、求逆元等算法封装在 类MathUitl 中。仿射变换、多表代换等加解密算法封装在 类TransAlgor 中，以供加解密使用。另一个 类IintiDeal 用与处理密钥输入等，现在不用关心。重要的地方均有注解，没注解就是你也一定会看懂！
# 本文件名：__uitl.py
import numpy as np
class MathUtil():
def extendGcd(a, b):
"""扩展欧几里德算法"""
if b == 0:
return 1, 0
else:
x, y = MathUtil.extendGcd(b, a % b)
x, y = y, x - (a//b) * y
return x, y
def modInvElem(a:int, m=26):
"""求整数a关于1模m的乘法逆元"""
if (np.gcd(a, m) !=1):
return -1
inv_a, _ = MathUtil.extendGcd(a, m)
inv_a %= m
return inv_a
def modInvMatrix(A, m=26):
"""求矩阵A关于1模m的乘法逆元"""
detA = np.linalg.det(A)
invA = np.linalg.inv(A)
Adjoint = detA * invA
# 此处注意！求整数的乘法逆元，必须将detA搞整数
# 因为计算精度的原因，算出的detA是很接近整数的小数
inv_detA = MathUtil.modInvElem(round(detA), m)
cipher_invA = ((inv_detA % m) * Adjoint) % m
cipher_invA = np.round(cipher_invA).astype(int)
return cipher_invA
class TransAlgor():
def affine(code, A, B):
"""仿射变换1模26算法"""
return (A * code + B) % 26
def invAffine(code, invA, B):
"""仿射变换1模26逆算法"""
return invA * (code - B) % 26
def polyalphabet(code:list, A, B) -> list:
"""多表代换1模26算法"""
group_len = len(B)
code = np.mat(code).reshape(group_len,1)
C = ((np.dot(A, code) + B) % 26).reshape(-1)
C = C.tolist()[0]
return C
def invpolyalpha(code:list, invA, B) -> list:
"""多表代换1模26逆算法"""
group_len = len(B)
code = np.mat(code).reshape(group_len, 1)
M = (np.dot(invA, (code - B)) % 26).reshape(-1)
M = M.tolist()[0]
return M
class InitDeal():
def inputKey() -> list:
"""用户从键盘输入密钥
# TODO验证输入密钥的有效性
"""
key = []
keyA = [[*map(eval, input("n请输入n阶密钥方阵A:n").split())]]
N = len(*keyA)
for i in range(N-1):
keyA.append([*map(eval, input().split())])
key.append(keyA)
keyB = [[*map(eval, input("n请输入n维密钥向量B:n").split())]]
key.append(keyB)
return key
def keyPreprocess(inputkey):
"""对输入密钥进行预处理, 得到密钥逆元cipher_invA"""
A, B = inputkey
group_len = len(B)
A = np.mat(A).reshape(group_len,group_len)
B = np.mat(B).reshape(group_len,1)
cipher_invA = MathUtil.modInvMatrix(A)
keylist = [A, B, cipher_invA]
return keylist
def dealText(textstr, group_len):
"""将文本进行分组处理
textstr: 字符串文本
n: 分组长度
"""
# 文本字符串去空格, 长度用z补全, 如"abcabc"
textstr = textstr.replace(" ", "")
blank = len(textstr) % group_len
if blank != 0:
textstr = textstr + (group_len-blank) * "z"
# 统一转换成小写0~25编码列表, 如[0,1,2,0,1,2]
textlist = list(textstr.lower())
codelist = [ord(i)-97 for i in textlist]
# 将编码列表进行分组, 即编码子向量, 如[[0,1,2],[0,1,2]]
codegroup = []
for i in range(0, len(codelist), group_len):
codegroup.append(codelist[i:i+group_len])
return codegroup
