Huffman和S—DES混合加密算法的研究

郑静 王腾

摘要：在对比现有的加密软件和古典密码学常见的加密算法后，结合文本加密的现状及发展趋势，该文将基于动态Huffman编码和S-DES算法相结合，弥补两者的缺点，达到对文本信息的最佳加密及解密效果。

关键词：混合算法；动态Huffman编码；S-DES算法；加密

中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2014）25-5902-03

Analysis of Huffman and S-DES of Mixed Encryption Algorithm

ZHENG Jing ， WANG Teng

（Yangtze University college of arts and sciences， Jingzhou 434023， China）

Abstract： In contrast to the existing common encryption software and classical cryptography， combined with the present situation and development of the current text encryption， this paper will be based on dynamic Huffman coding and S-DES algorithm， make up for the shortcomings of the two， achieve the best effect on text information encryption.

Key words： mixed algorithm； dynamic Huffman coding； S - DES encryption algorithm； encryption

随着互联网新技术的发展，黑客攻击的手段也花样翻新，使得信息安全面临着新的威胁，特别是计算机中的数据，面临着两方面的问题：一是知识产权保护问题，防止用户的非法复制和传播；另一个是保密通信的问题，提高私密消息的机密性，提高信息安全保护的水平。要解决这两方面的问题，只靠传统加密技术是不够的。黑客拦截加密数据后得到的会是一堆乱码，无疑是在告诉黑客这是经过加密的信息，反而暴露了私密消息的存在性，使其有针对性地进行破解或破坏。所以怎样才能防止或者降低私密消息在传输过程中被攻击或窃取的几率应成为我们关心的问题。

1 Huffman和S-DES混合加密算法与现有及传统加密算法的比较

文本加密技术是保障信息安全最基本、最核心的技术措施，主要通过对数据的加密和数字签名来实现。其中对数据的加密处理主要是为了防止数据不会被窃听。数据的加密方式有两种，一种是传统的对称密钥加密，就是加密方用一把密钥对数据进行加密，而解密方用同样一把密钥对数据进行解密。第二种是非对称密钥加密，如果使用这种算法，可以保证对发送方和接收方身份的确认。而数字签名实际上是由生成摘要和生成数字签名两部分构成。其中摘要可以防止文件被篡改，保证信息的完整性；而数字签名则是为了保障在商务活动中数据的不可否认性，从而使数据具有法律意义。

目前在文档安全管理市场上，加密可分为：文档格式转换加解密、核心层加解密、应用层加解密。常见的加密软件有：1） 记事本加密器Ncrypt TX，它预设了多种加密算法，包括DES、3DES、Rijndael、Polyalphabetic、ROT13、Vigenrre、Playfair等。当然不同的加密算法支持不同的数据编码格式，如Hex、Base64、Text、Word等。在工具栏中也可以相应地设置所需的密码。2） 超级密码本Super Code有两个特色：第一是多重加密功能；第二是密码自动生成，通过创建密钥文件，摆脱记忆密码的烦恼。Super Code内置了TripleDES、DES、Rijndael、RC2等加密算法。Super Code的特点是允许你以上述加密算法为依据，自由组合，创建自己独有的加密算法序列，例如可以选择两种TripleDES算法，一种DES算法，三种RC2算法，五种Rijndael算法，而且可以灵活排列其先后顺序。

对称密钥密码系统，历史悠久，加/解密速度快是其优点，但因加密密钥与解密密钥为同一把密钥，信息的传送方如何在加密之后，将密钥以安全的方式传送给接收方，如何使双方能共享该密钥，是此密码系统的一大问题，因此，对称密钥密码系统不适合多人使用的应用。

非对称式加密就是加密和解密使用的不是同一个密钥，通常有两个密钥，称为“公钥”和“私钥”，它们必须配对使用，否则不能打开加密文件。“公钥”是指可以对外公布的，“私钥”则只能由持有人知道。它的优越性在于，对称式的加密方法如果是在网络上传输加密文件就很难把密钥告诉对方，不管用什么方法都有可能被别人窃听到，而非对称式加密方法有两个密钥，“公钥”可以公开，收件人解密时只要用自己的私钥即可，这样就很好地避免了密钥的传输安全性问题。

非对称式密码系统也称为“公开密钥密码系统”，它弥补了对称密钥密码系统的缺点，但运算速度较慢是公开密钥密码系统的缺点。

DES算法运算速度较慢，但在此基础上改进的S-DES算法，是一个对称分组加密的简化模型，有利于研究和实现，再结合Huffman编码对文本信息进行压缩编码，即Huffman编码和S-DES算法相结合的混和加密算法就应运而生了。

2 Huffman和S-DES加密算法原理分析

2.1 Huffman编码原理分析

哈夫曼编码是一种变长编码，是哈夫曼树的一个应用。哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。

哈夫曼编码根据字符出现的概率来构造平均长度最短的编码。在编码中，若各码字长度严格按照码字所对应符号出现概率的大小的逆序排序，则编码的平均长度是最小的。其中，码字是明文字符，是通过哈夫曼编码后得到的编码，其长度由明文中字符出现的概率决定，出现概率大的编码长度短，出现概率小的编码长度长。

哈夫曼编码对需要编码的数据进行两遍扫描：第一遍统计原数据中各字符出现的频率，利用得到的频率值创建哈夫曼树，并把树的信息保存起来，以便解压时创建同样的哈夫曼树进行解压；第二遍则根据第一遍扫描得到的哈夫曼树进行编码，并把编码后得到的码字存储起来。

哈夫曼编码的缺点：一、对于过短的文件进行编码的意义不大，因为存储哈夫曼树的信息就需要较大的存储空间；二、存储编码信息时，编码速度慢，效率低下。

2.2 S-DES算法分析

S-DES加密算法是以8位明文和10位密钥作为输出。其解密算法用同一密钥对8位密文分组产生原来的明文分组，如图1所示，它描述了S-DES的算法流程。

解密算法的数学表示：明文=IP-1（fk1（SW（fk2（IP（密文）））））

S-DES加密算法涉及五个函数

1） 初始置换IP（initial permutation），IP=，将8bit数按照IP函数进行移位；

2） 复杂函数fk1，它是依赖于子密钥K1，包含置换和替换的运算；

3） 置换函数SW，将8bit数的左4bit和右4bit交换位置；

4） 复杂函数fk2，它是依赖于子密钥K2，包含置换和替换的运算；

5） 初始置换IP的逆置换IP-1，IP-1=，将8bit数按照IP-1函数进行移位。

3 Huffman和S-DES算法混合加/解密过程

3.1 混合加密过程

用数据流方式读入将要加密的文本文件信息，输入密钥并保存，经过第一次哈夫曼编码加密后转化为0/1字符串，在进行第二次加密之前要将0/1字符串分组，每8位一组，将其作为第二次加密S-DES算法的明文输入，经过S-DES算法得到最终的密文，将其保存到另一个TXT文本文件中。混合算法的加密过程如图2所示。

3.2 混合解密过程

解密过程首先要进行身份认证，输入密钥，身份认证成功后将进行解密，否则将不会解密。首先将最终的密文进行分组，每8位一组，经过S-DES算法进行第一次解密，得到0/1字符串，将其作为Huffman算法的编码进行第二次解密，即可得到最终的明文。其混合算法的解密过程如图3所示。

4 Huffman和S-DES混合算法的实现

4.1 Huffman编码的实现

Huffman算法主要涉及到5个核心函数，分别为获取权值数组GetWeightArray、构建哈夫曼树CreateHuffmanTree、创建哈夫曼编码字典CreateHuffmanDict、哈夫曼编码StringToHuffmanCode以及哈夫曼编码的解码ToHuffmanCode。

1）获取权值数组GetWeightArray（string str）

将文本信息中的每种字符出现的次数进行统计，并将其作为哈夫曼树的权值。

2）构建哈夫曼树CreateHuffmanTree（Node[] sources）

按“左走0，右走1”的原则创建哈夫曼树。

3）创建哈夫曼编码字典CreateHuffmanDict（Node hTree）

创建哈夫曼编码字典，在数组中实现“左走0，右走1”。

4）哈夫曼编码StringToHuffmanCode（out Dictionary key， string str）

由创建的哈夫曼树，得到哈夫曼编码。

5）哈夫曼编码的解码ToHuffmanCode（string source， Dictionary hfdict）

将哈夫曼编码还原成哈夫曼树，得到每个字符出现的次数，将其还原成原文本信息。

4.2 S-DES算法的实现

S-DES算法中涉及的核心算法为P10置换；P8置换；IP函数；FK函数；SW函数；IP-1函数。

1）P10置换 p10（string miyao）

numbers = miyao.ToCharArray（）；

miyao = “”；

miyao = miyao + numbers[2] + numbers[4] + numbers[1] + numbers[6] + numbers[3] + numbers[9] + numbers[0] + numbers[8] + numbers[7] + numbers[5]；

2）P8置换 p8（string ls1， string ls2）

miyao = miyao + numbers1[2] + numbers1[3] + numbers1[4] + ls2

miyao = miyao + numbers[3] + numbers[0] + numbers[4] + numbers[1] + numbers[5] + numbers[2] + numbers[7] + numbers[6]；

3）IP函数 IP（string mingwen）

mingwen = mingwen + numbers[1] + numbers[5] + numbers[2] + numbers[0] + numbers[3] + numbers[7] + numbers[4] + numbers[6]；

4）FK函数 fk（string mingwen， string key）

int[，] s0 = new int[，] { { 1， 0， 3， 2 }， { 3， 2， 1， 0 }， { 0， 2， 1， 3 }， { 3， 1， 3， 2 } }；

int[，] s1 = new int[，] { { 0， 1， 2， 3 }， { 2， 0， 1， 3 }， { 3， 0， 1， 0 }， { 2， 1， 0， 3 } }； （下转第5916页）

（上接第5904页）

varstr = Convert.ToString（Convert.ToInt32（lstr， 2） ^ Convert.ToInt32（varstr， 2）， 2） + rstr；

while （varstr.Length < 8）

{ varstr = ‘0 + varstr； }

5）SW函数 sw（string mingwen）

mingwen = mingwen + numbers[4] + numbers[5] + numbers[6] + numbers[7] + numbers[0] + numbers[1] + numbers[2] + numbers[3]；

6）IP-1函数 NIP（string mingwen）

mingwen = mingwen + numbers[3] + numbers[0] + numbers[2] + numbers[4] + numbers[6] + numbers[1] + numbers[7] + numbers[5]；

5 结束语

该混和加密算法结合了Huffman算法的平均最短编码和S-DES算法的分组加密，能对文本信息进行有效的加密，由于加密的过程是由两次加密算法混合组成，所以增强了密文的安全性。

但Huffman算法在统计文本信息中字符出现的次数，并将该次数作为权值时，降低了程序的运行效率。且S-DES算法每次运算8bit数，增加了循环次数，也降低了程序的运行效率。

本文主要是对TXT文件中的字符进行混合加密，对于其他各种文件，如二进制文件等，虽然能够进行有效的加密，但是其安全性和运行效率无法估计，这也是后续研究中应该加以改善的。