二叉樹加密算法是一種利用加密二叉樹的樹形對明文信息進(jìn)行加密處理，同時還可以實現(xiàn)密鑰的多方保存。

一、加密算法與構(gòu)造二叉樹

在運用基于二叉樹的加密算法時，信息的管理者首先構(gòu)造用于加密的二叉樹，然后利用二叉樹的樹形對信息加密，將明文信息轉(zhuǎn)化為密文信息。加密之后，信息的管理者將二叉樹的前序遍歷序列和中序遍歷序列交給不同信息保存者，實現(xiàn)密鑰的多方保存。

基于二叉樹的加密算法就是利用二叉樹來對二進(jìn)制信息進(jìn)行編碼。我們定義用于加密的二叉樹為加密二叉樹Encryption_ Binary_ Tree=((To，Ti)l i=l，2，3，…，n，n>0），加密二叉樹的任意一個結(jié)點用唯一的序號t來表示，加密二叉樹是一棵樹形不確定的任意二叉樹，如圖1所示D并且約定二叉樹的左分支表示字符“O’’，右分支表示字符“1"。

首先，將需要加密的明文信息轉(zhuǎn)化為二進(jìn)制字符串，則加密過程是分解明文中的字符串，從根結(jié)點出發(fā)，按字符“0’’或“1"確定查找該結(jié)點的左孩子或右孩子，直至葉結(jié)點或者只有一個孩子的樹結(jié)點，便得到了該子串相對應(yīng)的結(jié)點序號。將結(jié)點序號按照明文的順序排列在一起，即得到基于二叉樹加密算法的密文，加密算法的密鑰即是二叉樹的前序（后序）和中序遍歷序列。

假設(shè)需要加密的明文為：

00101101001001101000

則經(jīng)過加密之后的密文為：

T3 T5 T6 T7 T7 T8 T5 T3

對密文的解密之后的明文為：

00101 101001001 101000

密文的形成是由二叉樹的樹形決定的，也就是說二叉樹的樹形對于算法的安全性有著極其重要的影響。下面我們來討論構(gòu)造二叉樹的樹形時應(yīng)該注意的問題。

使用算法對明文進(jìn)行加密前，首先構(gòu)造一棵完全二叉樹，然后隨機對二叉樹多次進(jìn)行易位和剪枝兩種處理，由此形成加密二叉樹。

對結(jié)點TiI進(jìn)行易位處理是指：交換二叉樹中分別以t和Tj兩個結(jié)點為根的子樹的位置。

對結(jié)點tk點進(jìn)行剪枝處理是指：將以tk為根的子樹任意插入到一個孩子數(shù)小于2的結(jié)點之下，作為左孩子或右孩子。

雖然加密二叉樹的構(gòu)造是任意的、隨機的，但是有些樹形是不允許的。如只存在左枝或右枝的二叉樹，這種二叉樹在編碼時，可以編碼的信息有限，編碼中包含許多連續(xù)的1，特征明顯，容易被破解。完全二叉樹也不允許，因為編碼所用的二叉樹是在完全二叉樹的基礎(chǔ)上變化而來的，破解者可能首先會嘗試用完全二叉樹來破解。

管理者在進(jìn)行密鑰的多方保存時，并不是只能將樹形分給兩個信息保存者，可以根據(jù)需要，將密鑰分為任意多份。比如：需要將信息交給A、B、C三者保存，我們首先將加密二叉樹的中序遍歷序列交給A保存。我們利用前序遍歷序列任意構(gòu)造一棵二叉樹，我們稱這棵二叉樹為虛擬二叉樹，虛擬二叉樹的樹形與加密二叉樹是不同的，但虛擬二叉樹的前序遍歷序列與加密二叉樹的前序序列是相同的。將虛擬二叉樹的中序序列和后序遍歷序列分別交給B和C，如圖2所示。這樣便可以將密鑰分為三份，需要分解為多份時，采用類似的方法利用虛擬二叉樹的后序序列繼續(xù)構(gòu)造虛擬二叉樹，提供虛擬二叉樹的前序、中序序列繼續(xù)分割。將密鑰分為任意多份時，需要同時利用二叉樹的前、中、后序序列，但只能利用二叉樹的前序、中序序列構(gòu)造虛擬二叉樹，不能利用二叉樹的中序序列構(gòu)造虛擬二叉樹，否則密鑰無法繼續(xù)分割。將信息保管者所保存的信息組合在一起構(gòu)造密鑰的過程，是密鑰分解的逆過程。比如將A、B、C三者的二叉樹遍歷序列組合在一起，構(gòu)造加密二叉樹的樹形時，先將B、C的序列組合構(gòu)造虛擬二叉樹氣．并得到虛擬二叉樹的前序序列，將虛擬二叉樹的前序序列與A所保存的中序序列組合在一起，可以得到加密二叉樹的樹形，即密鑰。

二、基于二叉樹的解密算法

1、解密算法

對密文進(jìn)行解密之前，首先需要將各個信息保存者所保存的二叉樹遍歷序列組合在一起，構(gòu)成二叉樹，然后對密文解密。

基于二叉樹的解密算法是加密算法的逆過程。密文中的每一個字符對應(yīng)二叉樹的一個結(jié)點，在已知樹形的情況下，從根結(jié)點出發(fā)到密文表示的相應(yīng)結(jié)點的路徑上，分支字符組成的字符串作為該密文字符所對應(yīng)的明文段。將所有密文字符所對應(yīng)的明文組合在一起，即是明文信息。加密算法的密鑰就是二叉樹的樹形。

在實際應(yīng)用中，明文的信息量是很大的，二叉樹的結(jié)點數(shù)非常多，先構(gòu)造二叉樹，再進(jìn)行解密的方法需要消耗大量的存儲空間。解密的過程主要是在二叉樹中搜索密文字符的過程，我們可以利用前序序列和中序序列所提供的信息，計算相應(yīng)結(jié)點的左右孩子，在搜索序列的過程中，直接對密文解碼。從二叉樹的根結(jié)點出發(fā)，檢查根結(jié)點或子樹的根結(jié)點：如果該結(jié)點不是需要查找的密文字符，則搜索該結(jié)點的左子樹，如果左子樹中存在密文字符，則字符串增加一位O；以根結(jié)點的左孩子為根結(jié)點繼續(xù)搜索，如果左子樹中不存在，那么密文字符位于右子樹當(dāng)中，字符串增加一位1；以根結(jié)點的右孩子為根結(jié)點繼續(xù)搜索，直到搜索到密文字符，此時就完成了對密文字符的解密工作。

我們用數(shù)組Preorder表示加密二叉樹的先序遍歷序列，數(shù)組Inorder表示加密二叉樹的中序遍歷序列，code表示密文對應(yīng)的二進(jìn)制字符串。具體算法如下：

Node_Code( Preorder[],Inorder[],SearchNode)

{

Preld=1；//指示根結(jié)點在先序序列中的位置。

Inld=1；//指示根結(jié)點在中序序列中的位置。

id =1；

n=l；

flag=0//標(biāo)志位，指示根結(jié)點的左子樹中是否

//存在需要查找的密文字符的標(biāo)志位。

code[ n]；//記錄密文所對應(yīng)的明文信息。

while( Preorder[ Preld]! =SearchNode)

{/SearchNode為需要解密的密文字符；root=Preorder[Preld];While( Inorder[ Inid]!=root}

Gd++；//確定根結(jié)點的左子樹的結(jié)點數(shù)目；

i(inorder[id]! =SearchNode) then flag=1;

//判斷左子樹中是否存在搜索的解密字符。

}

if flag=1

then{//搜索左子樹

Preld++；

root = Preord[ Preld];

code[ n] =0

}

else{//搜索右子樹

Preld = Preld + id;

root = Preord[Preld];

Inid =Inid +id -i

code[n] =1

}

id = 1;

flag =O;

n+ +;

}

}

用二叉樹的先序序列和中序序列解密，在解密過程中，不再需要存儲整個二叉樹，只需要存儲二叉樹的前序序列和中序序列，大大降低了解密程序的空間復(fù)雜度。

2、加密算法的復(fù)雜度分析

我們首先分析解密算法的空間復(fù)雜度。加密二叉樹的結(jié)點非常的多，假設(shè)為Ⅳ個，采用4個字節(jié)來記錄結(jié)點信息，那么存儲二叉樹的先序和中序序列，總共需要個8Ⅳ字節(jié)的存儲空間，這也就是解密算法所需要的存儲空間。采用孩子表示法來存儲一棵二叉樹，一每個結(jié)點有三個域，其中的兩個域，分別記錄指向該結(jié)點左孩子和右孩子的指針，還有一個域用來記錄結(jié)點的信息。在C語言中，一個指針需要占用4個字節(jié)的存儲空間，那么存儲一棵二叉樹需要占用12N個字節(jié)的存儲空間，加上本來就需要存儲的先序和中序序列，那么不采用解密算法，總共需要20N個字節(jié)的空間。解密算法可以節(jié)約60%的存儲空間。因此采用解密算法可以大大降低程序的空間復(fù)雜度。

再來分析解密算法的時間復(fù)雜度。解密的過程也就是從根節(jié)點出發(fā)，逐層向下搜索密文結(jié)點的過程。查找密文結(jié)點的次數(shù)，是由密文結(jié)點的所有祖先結(jié)點的左子樹的結(jié)點數(shù)決定的。在加密二叉樹與完全二叉樹層數(shù)相同的情況下，完全二叉樹的結(jié)點數(shù)多于加密二叉樹，因此可以用完全二叉樹來評估解密算法最壞情況下的時間復(fù)雜度。但是完全二叉樹是不能用來作為加密二叉樹的，它會降低算法的安全性。

假設(shè)完全二叉樹一共有Ⅳ個結(jié)點，M層，由二叉樹的知識可知M =lb(Ⅳ+1)，密文字符位于第K層。密文字符的祖先結(jié)點分別位于1，2，一”，K-1層，第i層祖先結(jié)點的左子樹的層數(shù)為M-i;左子樹也是完全二叉樹，‘結(jié)點數(shù)為2Mi -1;'所以為了查找密文字符需要查找的次數(shù)為2M-K，當(dāng)密文字符出現(xiàn)在二叉樹底層最右邊的結(jié)點時，算法的效率最低，需要查找-1次即N次，這相當(dāng)于搜索了整個二叉樹。因此解密算法最壞情況下的時間復(fù)雜度為O(Ⅳ)，但是正如上文所說的，完全二叉樹不能作為加密二叉樹，因此最壞的情況不會出現(xiàn)，解密時，搜索次數(shù)會大幅減少。

三、加密算法方案評價

基于二叉樹的加密算法可以很好地實現(xiàn)對信息的加密，將二進(jìn)制的明文信息對應(yīng)于加密二叉樹的結(jié)點，加密二叉樹的樹形不確定，無法對密文進(jìn)行解密。為了進(jìn)一步增強密碼的安全性，我們提出對密鑰實現(xiàn)多方保存，只有當(dāng)所有的密鑰的保存者都將自己的密鑰提供出來時，才有可能對密文解密。解密算法利用二叉樹遍歷序列的性質(zhì)，在不構(gòu)造二叉樹的情況下，直接利用二叉樹的中序序列和前序序列對密文實現(xiàn)解密，降低了算法的空間復(fù)雜度。

加密二叉樹的構(gòu)造對密文的安全性有重要的影響，我們提出在完全二叉樹的基礎(chǔ)上隨機修改，構(gòu)造加密二叉樹，但我們并沒有給出具體的標(biāo)準(zhǔn)用來判斷該二叉樹是否可以用于加密操作，這是該算法需要進(jìn)一步改進(jìn)的方面。

admin

收藏 海報分享