数学建模实验 IV 矩阵密码问题

QUST Data Science Research Association

数学建模实验 IV 矩阵密码问题

Author: `sandyzikun`

Problem Description

Problem Analysis

Modeling

Solving

Validation

Extra

References

青岛科技大学数据科学研究协会

Author: `sandyzikun`

Problem Description

Problem Analysis

Modeling

Solving

Validation

Extra

References

Naive Solution

`Hill` Cipher

Naive Solution

`Hill` Cipher

2022-03-22

简单介绍Hill加密算法.

一种矩阵密码问题:

密码学在经济和军事方面起着极其重要的作用.
1929年, Hill(希尔)通过线性变换对传输信息进行加密处理, 提出了Hill加密算法.
请结合Hill加密算法的基本思想, 建立数学模型回答下面问题:

任意设计一段明文, 求出这段明文的Hill(m)密文(明文字符至少包含数字, 大写英文, 小写英文及标点符号等);
给出对应的模r倒数表;
假设你已经获取了通信双方的密文及密钥信息, 请编程实现解密过程;

根据题目要求, 使用Hill加密算法 ¹ ² 完成任务.

先审察古典密码的基本理论.
对于正整数r, 记集合 $ Z_r = \{ 0, 1, 2, \cdots, r - 1 \} $.

Definition 4.1: 对于一个元素属于集合 $ Z_r $ 的m阶方阵A, 如若存在一个元素属于集合 $ Z_r $ 的方阵B, 使得

$AB = BA = E \pmod{r},$

称A为模r可逆, B为A的模r逆矩阵, 记为 $ B = A^{-1} (\bmod{r}) $;

$ E (\bmod{r}) $ 的意义为, 每一个元素加减r的整数倍后, 可以化成单位矩阵.
例如

$\begin{bmatrix} 27 & 52 \\ 26 & 53 \\ \end{bmatrix} (\bmod{26}) = E.$

Definition 4.2: 对于 $ Z_r $ 的一个整数a, 如若存在 $ Z_r $ 的一个整数b, 使得 $ a b = 1 (\bmod{r}) $, 称b为a的模r倒数或乘法逆, 记作 $ b = a^{-1} (\bmod{r}) $;

Theorem 4.1: 元素属于 $ Z_r $ 的方阵A模r可逆的等价条件为, r与|A|互素;

一般的加密过程为明文=>编码器=>密文=>普通信道=>解码器=>明文, 但在其中=>普通信道=>解码器=>这个环节容易为他人截获并加以分析.

在Hill加密算法中, 运用的数学手段是矩阵运算, 编码过程如下:

根据明文字母表值, 把明文信息用数字表示, 设明文信息只需要26个字母, 通信双方给出26个字母表值为{ "A": 0, "B": 1, "C": 2, ..., "X": 23, "Y": 24, "Z": 25 };
选择一个三阶可逆整数方阵A, 称为 $ {Hill}_3 $ (也写作Hill(3)) 编码的密钥矩阵, 这是整个加密算法的Key(这也是加密算法的关键, 仅有通信的双方掌握);
把明文字母逐对分组: Hill(3)密码的编码矩阵为三阶矩阵, 则明文字母每3个为一组(扩展至Hill(m)密码时每m个明文字母为一组).
如若最后一组不足3个字母, 则补充无实义的哑字母, 使每一组皆由3个明文字母组成.
查出每个明文字母的表值, 构成一个三维列矢量 $ \alpha $;
$ \forall \alpha $, 得到新的三维列矢量 $ \beta = A \alpha $, 查表得到密文字母;

以上为Hill(3)密码的编码过程, 解码即为上述的逆过程.

但需要注意的是! 由于某些原因, 我们这里不把词组存储为列矢量而存储为行矢量, 因此将采用矩阵右乘而非左乘.

现在, 我们将对原文Telling and Sharing the World, which Entrusts and Expresses Love and Feelings of VOCALOID进行有损加密, 并采用可逆矩阵

$Q = \begin{bmatrix} 1 & 2 & 8 \\ & 3 & 9 \\ & & 1 \\ \end{bmatrix}$

作为密钥矩阵

首先, 我们使用正则表达式(也称规则表达式)以及Python中的正则表达式模块re以及其他字符串操作去除明文中的非字母部分, 并全部转化为大写字母, 这一步操作会使得到的明文相比待编码的原文产生少量损失, 可视为一步有损压缩.
需要用到的正则表达式为[^A-Za-z], 我们会把这一部分所匹配不到的部分全部删除, 即转化为长度为零的空字符串.
我们先用变量rawtext存储待编码的文字然后进行如下操作

Python

import re

rawtext = "Telling and Sharing the World, which Entrusts and Expresses Love and Feelings of VOCALOID"
pattern = re.compile(r"[^A-Za-z]") # 编译我们所需要用到的正则表达式
plaintext = pattern.sub("", rawtext).upper()

现在我们查看得到的明文

Python

>>> plaintext
'TELLINGANDSHARINGTHEWORLDWHICHENTRUSTSANDEXPRESSESLOVEANDFEELINGSOFVOCALOID'

>>> len(plaintext)
75

被有损压缩为了TELLINGANDSHARINGTHEWORLDWHICHENTRUSTSANDEXPRESSESLOVEANDFEELINGSOFVOCALOID, 它有75个字母.

由于我们使用Hill(3)的原则进行加密, 所以我们现在要把字母数量用字母K补齐至3的整倍数(虽然在本例中目前的字母数量75就是3的整倍数), 需要注意的是这一步也会造成少量损失

Python

1
2
3

strlen_r = len(plaintext) % 3 # 计算字符串模3的余项的长度
if strlen_r: # 如若长度余0则不需要补全, 否则补全余项
    plaintext += "K" * (3 - strlen_r)

此刻的明文

Python

>>> plaintext
'TELLINGANDSHARINGTHEWORLDWHICHENTRUSTSANDEXPRESSESLOVEANDFEELINGSOFVOCALOID'

>>> len(plaintext)
75

现在切割明文字符串, 在此之前我们先写出把字母转为对应数字的函数alp2num与数字转义回字母的函数num2alp

Python

1 2	alp2num = lambda x : (ord(x) - ord("A")) % 26 num2alp = lambda x : chr(x + ord("A"))

然后每3个一组, 每组编成一个3维矢量, 存入列表然后转化为以行矢量为元素的矩阵mat_origin

Python

import numpy as np

vectors = []
for k in range(len(plaintext) // 3):
    current = []
    for l in range(3):
        current.append(alp2num(plaintext[k * 3 + l]))
    vectors.append(np.array(current))
mat_origin = np.array(vectors)

(其实想要压行的话上面那一段二重循环可以借助语法糖写如下)

Python

1	mat_origin = np.array([ [ (lambda x : (ord(x) - ord("A")) % 26)(plaintext[k * 3 + l]) for l in range(3) ] for k in range(len(plaintext) // 3) ])

然后声明我们的密钥矩阵

Python

keymat = np.array([
    [ 1 , 2 , 8 ],
    [ 0 , 3 , 9 ],
    [ 0 , 0 , 1 ],
    ])

于是加密后的矩阵便为

Python

1	mat_new = (mat_origin @ keymat) % 26

查看其值

Python

>>> mat_new
array([[19, 24, 17],
       [11, 20, 17],
       [ 6, 12,  9],
       [ 3,  8, 11],
       [ 0, 25,  5],
       [13, 18, 21],
       [ 7,  0, 10],
       [14,  1, 16],
       [ 3, 20, 21],
       [ 8, 22, 11],
       [ 4, 21, 12],
       [17, 16, 22],
       [19, 14,  2],
       [13,  9,  5],
       [23, 13, 24],
       [ 4, 10,  4],
       [ 4, 10, 23],
       [14, 13, 19],
       [ 0, 13, 16],
       [ 5, 22,  2],
       [11, 20, 17],
       [ 6, 14, 16],
       [ 5, 21,  9],
       [ 2,  4,  1],
       [14,  0,  5]], dtype=int32)

现在使用刚才定义的转义函数, 便可得到密文并存入变量cryptograph

Python

1	cryptograph = "".join(num2alp(eachnum) for eachnum in mat_new.flatten())

查看变量cryptograph可知密文为TYRLURGMJDILAZFNSVHAKOBQDUVIWLEVMRQWTOCNJFXNYEKEEKXONTANQFWCLURGOQFVJCEBOAF.

由于选取的字母集的长度r = 26, 故方阵A可逆的等价条件为|A| (mod r)不为2或13所整除.
如若A满足上述定理4.1的条件, 不难验证 $ A^{-1} = \frac{1}{|A|} A^\ast $, 其中 $ \frac{1}{|A|} $ 为 $ |A| (\bmod{26}) $ 的倒数.
显然, $ |A| (\bmod{26}) $ 是 $ Z_{26} $ 中的数, $ Z_{26} $ 中有模26倒数的整数及其倒数可见下表

从上表中我们可以得知 $ 3^{-1} = 9 (\bmod{26}) $, 因此可以反演求得

$\begin{align*} Q^{-1}(\bmod{26}) &= \frac{1}{|Q|} Q^\ast (\bmod{26}) \\ &= 3^{-1} \begin{bmatrix} 3 & -2 & -6 \\ 0 & 1 & -9 \\ 0 & 0 & 3 \\ \end{bmatrix} (\bmod{26}) \\ &= 9 \begin{bmatrix} 3 & -2 & -6 \\ 0 & 1 & -9 \\ 0 & 0 & 3 \\ \end{bmatrix} (\bmod{26}) \\ &= \begin{bmatrix} 27 & -18 & -54 \\ 0 & 9 & -81 \\ 0 & 0 & 27 \\ \end{bmatrix} (\bmod{26}) \\ &= \begin{bmatrix} 1 & 8 & 24 \\ 0 & 9 & 3 \\ 0 & 0 & 1 \\ \end{bmatrix} = \begin{bmatrix} 1 & 8 & 24 \\ & 9 & 3 \\ & & 1 \\ \end{bmatrix} \\ \end{align*}$

这便是解码时所需要用到的密钥矩阵的逆.
解码的过程也非常简单, 使用求得密钥矩阵的逆左乘(我们这里是右乘)密文所对应的矢量组, 然后取模, 转义回字母, 便可以得到解出的信息.

Python

keydet = np.linalg.det(keymat).astype(int) # 计算密钥矩阵的行列式值,
assert 26 % keydet, "" # 并且为了使其有(模26意义下)倒数, 需要保证其不为26的素因子所整除

keydet_inv = 1 # 计算密钥矩阵的行列式值(模26意义下)的倒数
for k in range(26):
    if (k + 1) * keydet % 26 == 1:
        keydet_inv = k + 1
        break

key_adjugate = (np.linalg.inv(keymat) * keydet).astype(int) # 计算密钥矩阵的伴随矩阵 Q* = |Q|Q^(-1)
key_inv = key_adjugate * keydet_inv % 26 # 计算密钥矩阵的模逆
mat_recover = (mat_new @ key_inv) % 26 # 计算解密后的矩阵

现在我们查看密钥矩阵的模逆和解密后的矩阵

Python

>>> key_inv
array([[ 1,  8, 24],
       [ 0,  9, 23],
       [ 0,  0,  1]], dtype=int32)

>>> mat_recover
array([[19,  4, 11],
       [11,  8, 13],
       [ 6,  0, 13],
       [ 3, 18,  7],
       [ 0, 17,  8],
       [13,  6, 19],
       [ 7,  4, 22],
       [14, 17, 11],
       [ 3, 22,  7],
       [ 8,  2,  7],
       [ 4, 13, 19],
       [17, 20, 18],
       [19, 18,  0],
       [13,  3,  4],
       [23, 15, 17],
       [ 4, 18, 18],
       [ 4, 18, 11],
       [14, 21,  4],
       [ 0, 13,  3],
       [ 5,  4,  4],
       [11,  8, 13],
       [ 6, 18, 14],
       [ 5, 21, 14],
       [ 2,  0, 11],
       [14,  8,  3]], dtype=int32)

最后我们把矩阵转义回字母

Python

1	>>> textrecover = "".join(num2alp(eachnum) for eachnum in mat_recover.flatten())

查看变量textrecover得到解出的信息为TELLINGANDSHARINGTHEWORLDWHICHENTRUSTSANDEXPRESSESLOVEANDFEELINGSOFVOCALOID.

Python

1 2	>>> textrecover == plaintext True

验证无误.

感兴趣的朋友可以看看兽音译者什么的.

¹. 百度百科词条 Hill密码, 在网络上可以找到相关工具例如bugku提供的Hill Cipher Tool, 并参考其他文章 ² ³ ⁴ ⁵ ↩

². zhangliu的博客园文章 Hill密码 ↩

³. qq_25968195的CSDN博客 Hill 加密算法 ↩

⁴. 信管网文章信息安全技术知识：Hill 密码、Hillm 密码加密过程 ↩

⁵. 0zcl的博客园文章信息安全－2：python之hill密码算法 ↩

$ a^{-1} $

$ a^{-1} $