矩阵编制Hill密码

密码学在经济和军事方面起着极其重要的作用. 现代密码学涉及很多高深的数学知识. 这里无法展开介绍. 

图29 保密通信的基本模型

密码学中将信息代码称为密码, 尚未转换成密码的文字信息称为明文, 由密码表示的信息称为密文. 从明文到密文的过程称为加密, 反之为解密. 1929年, 希尔(Hill)通过线性变换对待传输信息进行加密处理, 提出了在密码史上有重要地位的希尔加密算法. 下面我们略去一些实际应用中的细节, 只介绍最基本的思想.

【模型准备】若要发出信息action,现需要利用矩阵乘法给出加密方法和加密后得到的密文, 并给出相应的解密方法. 

【模型假设】(1) 假定每个字母都对应一个非负整数, 空格和26个英文字母依次对应整数0~26(见下表). 

表9 空格及字母的整数代码表

【模型建立】设3维向量x为明文, 要选一个矩阵A使密文y= xA, 还要确保接收方能由y准确地解出x. 因此A必须是一个3阶可逆矩阵. 这样就可以由y = xA得x = yA1. 为了避免小数引起误差, 并且确保y也是整数向量, A和A1的元素应该都是整数. 注意到, 当整数矩阵A的行列式= 1时, A1也是整数矩阵. 因此原问题转化为

(1) 把action翻译成两个行向量: x1, x2. 

(2) 构造一个行列式= 1的整数矩阵A(当然不能取A = E).

(3) 计算x1A和x2A.

(4) 计算A1.

【模型求解】(1) 由上述假设可见x1 = (1, 3, 20), x2 = (9, 15, 14). 

(2) 对3阶单位矩阵E =进行几次适当的初等变换(比如把某一行的整数被加到另一行, 或交换某两行), 根据行列式的性质可知, 这样得到的矩阵A的行列式为1或1. 例如A =, |A| = 1. 

(3) y1 =x1A = (1, 3, 20)  = (67, 44, 43), 

y2 =Ax2 = (9, 15, 14)  = (81, 52, 43).

(4) 由(A, E) =可得

A1=. 

这就是说, 接收方收到的密文是67, 44, 43, 81, 52, 43. 要还原成明文, 只要计算(67, 44, 43)A1和(81, 52, 43)A1,再对照表9“翻译”成单词即可.

【模型分析】如果要发送一个英文句子, 在不记标点符号的情况下, 我们仍然可以把句子(含空格)从左到右每3个字符分为一组(最后不足3个字母时用空格补上). 

【模型检验】(67, 44, 43)A1=(1, 3, 20), (81, 52, 43)A1 = (9, 15, 14). 

参考文献

杨威,高淑萍, 线性代数机算与应用指导,西安: 西安电子科技大学出版社, 2009. 页码: 98-102. 

Matlab实验题

按照上面的加密方法, 设密文为: 112, 76, 57, 51, 38, 18, 84, 49, 49, 68, 41, 32, 83, 55, 37, 70, 45, 25,问恢复为原来的信息是什么?