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

鄭靜 王騰

摘要：在對比現(xiàn)有的加密軟件和古典密碼學(xué)常見的加密算法后，結(jié)合文本加密的現(xiàn)狀及發(fā)展趨勢，該文將基于動(dòng)態(tài)Huffman編碼和S-DES算法相結(jié)合，彌補(bǔ)兩者的缺點(diǎn)，達(dá)到對文本信息的最佳加密及解密效果。

關(guān)鍵詞：混合算法；動(dòng)態(tài)Huffman編碼；S-DES算法；加密

中圖分類號：TP18 文獻(xiàn)標(biāo)識碼：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

隨著互聯(lián)網(wǎng)新技術(shù)的發(fā)展，黑客攻擊的手段也花樣翻新，使得信息安全面臨著新的威脅，特別是計(jì)算機(jī)中的數(shù)據(jù)，面臨著兩方面的問題：一是知識產(chǎn)權(quán)保護(hù)問題，防止用戶的非法復(fù)制和傳播；另一個(gè)是保密通信的問題，提高私密消息的機(jī)密性，提高信息安全保護(hù)的水平。要解決這兩方面的問題，只靠傳統(tǒng)加密技術(shù)是不夠的。黑客攔截加密數(shù)據(jù)后得到的會(huì)是一堆亂碼，無疑是在告訴黑客這是經(jīng)過加密的信息，反而暴露了私密消息的存在性，使其有針對性地進(jìn)行破解或破壞。所以怎樣才能防止或者降低私密消息在傳輸過程中被攻擊或竊取的幾率應(yīng)成為我們關(guān)心的問題。

1 Huffman和S-DES混合加密算法與現(xiàn)有及傳統(tǒng)加密算法的比較

文本加密技術(shù)是保障信息安全最基本、最核心的技術(shù)措施，主要通過對數(shù)據(jù)的加密和數(shù)字簽名來實(shí)現(xiàn)。其中對數(shù)據(jù)的加密處理主要是為了防止數(shù)據(jù)不會(huì)被竊聽。數(shù)據(jù)的加密方式有兩種，一種是傳統(tǒng)的對稱密鑰加密，就是加密方用一把密鑰對數(shù)據(jù)進(jìn)行加密，而解密方用同樣一把密鑰對數(shù)據(jù)進(jìn)行解密。第二種是非對稱密鑰加密，如果使用這種算法，可以保證對發(fā)送方和接收方身份的確認(rèn)。而數(shù)字簽名實(shí)際上是由生成摘要和生成數(shù)字簽名兩部分構(gòu)成。其中摘要可以防止文件被篡改，保證信息的完整性；而數(shù)字簽名則是為了保障在商務(wù)活動(dòng)中數(shù)據(jù)的不可否認(rèn)性，從而使數(shù)據(jù)具有法律意義。

目前在文檔安全管理市場上，加密可分為：文檔格式轉(zhuǎn)換加解密、核心層加解密、應(yīng)用層加解密。常見的加密軟件有：1） 記事本加密器Ncrypt TX，它預(yù)設(shè)了多種加密算法，包括DES、3DES、Rijndael、Polyalphabetic、ROT13、Vigenrre、Playfair等。當(dāng)然不同的加密算法支持不同的數(shù)據(jù)編碼格式，如Hex、Base64、Text、Word等。在工具欄中也可以相應(yīng)地設(shè)置所需的密碼。2） 超級密碼本Super Code有兩個(gè)特色：第一是多重加密功能；第二是密碼自動(dòng)生成，通過創(chuàng)建密鑰文件，擺脫記憶密碼的煩惱。Super Code內(nèi)置了TripleDES、DES、Rijndael、RC2等加密算法。Super Code的特點(diǎn)是允許你以上述加密算法為依據(jù)，自由組合，創(chuàng)建自己獨(dú)有的加密算法序列，例如可以選擇兩種TripleDES算法，一種DES算法，三種RC2算法，五種Rijndael算法，而且可以靈活排列其先后順序。

對稱密鑰密碼系統(tǒng)，歷史悠久，加/解密速度快是其優(yōu)點(diǎn)，但因加密密鑰與解密密鑰為同一把密鑰，信息的傳送方如何在加密之后，將密鑰以安全的方式傳送給接收方，如何使雙方能共享該密鑰，是此密碼系統(tǒng)的一大問題，因此，對稱密鑰密碼系統(tǒng)不適合多人使用的應(yīng)用。

非對稱式加密就是加密和解密使用的不是同一個(gè)密鑰，通常有兩個(gè)密鑰，稱為“公鑰”和“私鑰”，它們必須配對使用，否則不能打開加密文件?！肮€”是指可以對外公布的，“私鑰”則只能由持有人知道。它的優(yōu)越性在于，對稱式的加密方法如果是在網(wǎng)絡(luò)上傳輸加密文件就很難把密鑰告訴對方，不管用什么方法都有可能被別人竊聽到，而非對稱式加密方法有兩個(gè)密鑰，“公鑰”可以公開，收件人解密時(shí)只要用自己的私鑰即可，這樣就很好地避免了密鑰的傳輸安全性問題。

非對稱式密碼系統(tǒng)也稱為“公開密鑰密碼系統(tǒng)”，它彌補(bǔ)了對稱密鑰密碼系統(tǒng)的缺點(diǎn)，但運(yùn)算速度較慢是公開密鑰密碼系統(tǒng)的缺點(diǎn)。

DES算法運(yùn)算速度較慢，但在此基礎(chǔ)上改進(jìn)的S-DES算法，是一個(gè)對稱分組加密的簡化模型，有利于研究和實(shí)現(xiàn)，再結(jié)合Huffman編碼對文本信息進(jìn)行壓縮編碼，即Huffman編碼和S-DES算法相結(jié)合的混和加密算法就應(yīng)運(yùn)而生了。

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

2.1 Huffman編碼原理分析

哈夫曼編碼是一種變長編碼，是哈夫曼樹的一個(gè)應(yīng)用。哈夫曼樹又稱最優(yōu)二叉樹，是一種帶權(quán)路徑長度最短的二叉樹。

哈夫曼編碼根據(jù)字符出現(xiàn)的概率來構(gòu)造平均長度最短的編碼。在編碼中，若各碼字長度嚴(yán)格按照碼字所對應(yīng)符號出現(xiàn)概率的大小的逆序排序，則編碼的平均長度是最小的。其中，碼字是明文字符，是通過哈夫曼編碼后得到的編碼，其長度由明文中字符出現(xiàn)的概率決定，出現(xiàn)概率大的編碼長度短，出現(xiàn)概率小的編碼長度長。

哈夫曼編碼對需要編碼的數(shù)據(jù)進(jìn)行兩遍掃描：第一遍統(tǒng)計(jì)原數(shù)據(jù)中各字符出現(xiàn)的頻率，利用得到的頻率值創(chuàng)建哈夫曼樹，并把樹的信息保存起來，以便解壓時(shí)創(chuàng)建同樣的哈夫曼樹進(jìn)行解壓；第二遍則根據(jù)第一遍掃描得到的哈夫曼樹進(jìn)行編碼，并把編碼后得到的碼字存儲起來。

哈夫曼編碼的缺點(diǎn)：一、對于過短的文件進(jìn)行編碼的意義不大，因?yàn)榇鎯蚵鼧涞男畔⒕托枰^大的存儲空間；二、存儲編碼信息時(shí)，編碼速度慢，效率低下。

2.2 S-DES算法分析

S-DES加密算法是以8位明文和10位密鑰作為輸出。其解密算法用同一密鑰對8位密文分組產(chǎn)生原來的明文分組，如圖1所示，它描述了S-DES的算法流程。

解密算法的數(shù)學(xué)表示：明文=IP-1（fk1（SW（fk2（IP（密文）））））

S-DES加密算法涉及五個(gè)函數(shù)

1） 初始置換IP（initial permutation），IP=，將8bit數(shù)按照IP函數(shù)進(jìn)行移位；

2） 復(fù)雜函數(shù)fk1，它是依賴于子密鑰K1，包含置換和替換的運(yùn)算；

3） 置換函數(shù)SW，將8bit數(shù)的左4bit和右4bit交換位置；

4） 復(fù)雜函數(shù)fk2，它是依賴于子密鑰K2，包含置換和替換的運(yùn)算；

5） 初始置換IP的逆置換IP-1，IP-1=，將8bit數(shù)按照IP-1函數(shù)進(jìn)行移位。

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

3.1 混合加密過程

用數(shù)據(jù)流方式讀入將要加密的文本文件信息，輸入密鑰并保存，經(jīng)過第一次哈夫曼編碼加密后轉(zhuǎn)化為0/1字符串，在進(jìn)行第二次加密之前要將0/1字符串分組，每8位一組，將其作為第二次加密S-DES算法的明文輸入，經(jīng)過S-DES算法得到最終的密文，將其保存到另一個(gè)TXT文本文件中?；旌纤惴ǖ募用苓^程如圖2所示。

3.2 混合解密過程

解密過程首先要進(jìn)行身份認(rèn)證，輸入密鑰，身份認(rèn)證成功后將進(jìn)行解密，否則將不會(huì)解密。首先將最終的密文進(jìn)行分組，每8位一組，經(jīng)過S-DES算法進(jìn)行第一次解密，得到0/1字符串，將其作為Huffman算法的編碼進(jìn)行第二次解密，即可得到最終的明文。其混合算法的解密過程如圖3所示。

4 Huffman和S-DES混合算法的實(shí)現(xiàn)

4.1 Huffman編碼的實(shí)現(xiàn)

Huffman算法主要涉及到5個(gè)核心函數(shù)，分別為獲取權(quán)值數(shù)組GetWeightArray、構(gòu)建哈夫曼樹CreateHuffmanTree、創(chuàng)建哈夫曼編碼字典CreateHuffmanDict、哈夫曼編碼StringToHuffmanCode以及哈夫曼編碼的解碼ToHuffmanCode。

1）獲取權(quán)值數(shù)組GetWeightArray（string str）

將文本信息中的每種字符出現(xiàn)的次數(shù)進(jìn)行統(tǒng)計(jì)，并將其作為哈夫曼樹的權(quán)值。

2）構(gòu)建哈夫曼樹CreateHuffmanTree（Node[] sources）

按“左走0，右走1”的原則創(chuàng)建哈夫曼樹。

3）創(chuàng)建哈夫曼編碼字典CreateHuffmanDict（Node hTree）

創(chuàng)建哈夫曼編碼字典，在數(shù)組中實(shí)現(xiàn)“左走0，右走1”。

4）哈夫曼編碼StringToHuffmanCode（out Dictionary key， string str）

由創(chuàng)建的哈夫曼樹，得到哈夫曼編碼。

5）哈夫曼編碼的解碼ToHuffmanCode（string source， Dictionary hfdict）

將哈夫曼編碼還原成哈夫曼樹，得到每個(gè)字符出現(xiàn)的次數(shù)，將其還原成原文本信息。

4.2 S-DES算法的實(shí)現(xiàn)

S-DES算法中涉及的核心算法為P10置換；P8置換；IP函數(shù)；FK函數(shù)；SW函數(shù)；IP-1函數(shù)。

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函數(shù) IP（string mingwen）

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

4）FK函數(shù) 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 } }； （下轉(zhuǎn)第5916頁）

（上接第5904頁）

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

while （varstr.Length < 8）

{ varstr = ‘0 + varstr； }

5）SW函數(shù) sw（string mingwen）

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

6）IP-1函數(shù) NIP（string mingwen）

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

5 結(jié)束語

該混和加密算法結(jié)合了Huffman算法的平均最短編碼和S-DES算法的分組加密，能對文本信息進(jìn)行有效的加密，由于加密的過程是由兩次加密算法混合組成，所以增強(qiáng)了密文的安全性。

但Huffman算法在統(tǒng)計(jì)文本信息中字符出現(xiàn)的次數(shù)，并將該次數(shù)作為權(quán)值時(shí)，降低了程序的運(yùn)行效率。且S-DES算法每次運(yùn)算8bit數(shù)，增加了循環(huán)次數(shù)，也降低了程序的運(yùn)行效率。

本文主要是對TXT文件中的字符進(jìn)行混合加密，對于其他各種文件，如二進(jìn)制文件等，雖然能夠進(jìn)行有效的加密，但是其安全性和運(yùn)行效率無法估計(jì)，這也是后續(xù)研究中應(yīng)該加以改善的。