单字母替换密码的破译模型

赵龙乾+陈金琼+朱严

摘 要： 本文主要以矩阵理论为基础，运用置换密码、概率分析与希尔密码算法，建立了基于希尔算法破译单字母替换式密码的数学模型，编写出了具体的自动破译程序。

关键词： 替换密码 希尔密码 置换矩阵

替换式密码，又名取代加密法，是密码学中按规律把文字加密的一种方式[1]-[5]。在密码学研究领域中，密码破译是其重要内容之一，也是信息安全研究的热点方向之一。本文主要研究单字母替换密文的破译问题。使用矩阵理论[6]，建立了希尔密码[7]破译单字母替换式密码的数学模型，得到了密文中获取正确秘钥方法，进而运用希尔密码，置换密码，概率分析，以及可拓评价法，设计出了一套算法自动破译给定单字母替换式密码，并给出了评价该破译能力的标准。

1.基于希尔算法的单字母替换式密码破译设计

基本假设：

（1）加密矩阵的阶数较小；

（2）破译的明文已获取；

（3）明文的长度在合理的范围之内足够长；

模型或算法中的记号表示如下：

P—明文；Q—暗文；A—加密矩阵；i—个数；

希尔密码是运用基本矩阵论原理的替换密码。每个字母当做26进制数字：A=0，B=1，C=2......一串字母当成n维向量，跟一个n×n的矩阵相乘，再将得出的结果MOD26。

1.2希尔算法

上节中所建立的希尔密码破译单字母替换式密码的数学模型，其本质就是进行矩阵运算，利用英文替换密码的编码的希尔算法进行求解，步骤如下：

Step1：将一串经过单字母替换式方法加密后的暗文中的a-z（或A-Z）进行26进制数编码：a—0，b—1，c—2……x—23，y—24，z—25。英文字母编码组成暗文矩阵。

Step2：通过概率分析将猜测出的加密矩阵经过模逆算法[8]进行模逆运算，然后按照（1）式与Step得到的暗文矩阵经过实矩阵相乘[9]得到P矩阵，即明文矩阵1。

Step3：将破译出的明文矩阵P进行定性评估，如果明文矩阵1不正确，再重新猜测加密矩阵A，并重新操作Step1的操作，直到得到对应的正确加密矩阵所A对应的正确明文P，即明文矩阵n。如果明文矩阵1正确，则直接输出。

2.仿真结果

输入一串字符串，本次仿真以“the banana is very big I very like”27个字母为例作为明文P。假使经过某种加密方式，可以得到暗文“ungnsdgdpagkenvqgeqfjvupgul”，则暗文矩阵Q如图1所示：

3.结语

本文利用希尔算法破译单字母替换式密码。希尔算法与概率分析相结合大大地提高了结果的准确性和可靠性。本文所设计的单字母替换式密码破译模型不仅适用于密码破译，而且可以运用于其他领域，如文件加密等，使用价值高，实用性强。

参考文献：

[1]王昭，段云所，陈钟.数据加密算法的原理与应用[J].网络安全技术与应用，2001（2）：58-64.

[2]秦志光.密码算法的现状和发展研究[J].计算机应用，2004，24（2）：1-4.

[3]许霞.数据加密算法的研究与应用[D].西安建筑科技大学，2009.

[4]张肖，王薇.替换式密码算法及其破译能力的分析[J].科学与财富，2015（27）：242-242.

[5]李振华.替换密码算法在C++中的实现[J].科技广场，2009（3）：157-158.

[6]付丽，丁慧.代数在密码学中的应用[J].通化师范学院学报，2014（2）：29-31.

[7]亓传伟.简便高效的希尔密码[J].电脑编程技巧与维护，2007（9）：77-79.

[8]陈海进.奇数模模逆算法对偶数模的推广[J].计算机应用与软件，2005，05：100-101.

[9]徐士良.C常用算法程序集[M].第三版，北京：清华大学出版社，2001-01.36-37.

基金项目：安徽省高等学校专业综合改革试点项目（2014zy138）；安徽省大学生创新训练项目（201513619003）资助