針對(duì)安全性要求不太高的加密系統(tǒng)，將單邊范式HufFman編碼與等長(zhǎng)編碼相結(jié)合，提出一種基于混合選擇編碼的對(duì)稱密鑰自變動(dòng)加密方案。通過將明文的統(tǒng)計(jì)結(jié)果作為自身加密的密鑰和編碼依據(jù)，使方案易于實(shí)現(xiàn)，且計(jì)算存儲(chǔ)成本低。

一、單邊范式Huffman編碼簡(jiǎn)介

范式Huffman編碼是Huffman編碼的一個(gè)子集。其中心思想是：使用某些強(qiáng)制的約定，僅通過很少的數(shù)據(jù)便能重構(gòu)出哈夫曼編碼樹的結(jié)構(gòu)。單邊范式Huffman編碼是范式Huffman編碼中的一種特例。假設(shè)滿足單邊范式Huffman編碼的信源X由n個(gè)信源符號(hào)組成，按照符號(hào)概率由大到小排列后，寫成{X1，X2，…，xn}，對(duì)應(yīng)的概率集合為{P(x1），P(X2)，…，P(xn))，則其編碼樹結(jié)構(gòu)如圖1所示。

與這棵樹對(duì)應(yīng)的編碼如表1所示。

根據(jù)Huffman樹構(gòu)造規(guī)則，可知信源符號(hào)Xk必定滿足以下條件：

觀察表1和圖1可以得出單邊范式Huffman編碼的一些特性：

(1)符號(hào)的碼字長(zhǎng)度與其排列的位置有關(guān)，即排列后除最后一個(gè)符號(hào)xn外，任一符號(hào)Xk的單邊范式Huffman碼字長(zhǎng)度為后。

(2)碼字長(zhǎng)度為七的單邊范式Huffman編碼的前k-1位碼字為1，第后位碼字為0。

(3)排列后最后一個(gè)符號(hào)石。的碼字長(zhǎng)度為n-1，其單邊范式Huffman編碼由n-1個(gè)1組成。

從這些特性可以看出，使用單邊范式Huffman編碼的編解碼十分簡(jiǎn)單。通過已知的符號(hào)排列序位，編碼器可以直接輸出對(duì)應(yīng)碼字長(zhǎng)度的單邊范式Huffman編碼；而解碼器只需通過對(duì)輸入編碼進(jìn)行碼字長(zhǎng)度判斷，便可以解碼出對(duì)應(yīng)的符號(hào)序位，從而完成解碼。整個(gè)編解碼過程中并不需要進(jìn)行Huffman樹的構(gòu)造，也不需要進(jìn)行編碼的辨識(shí)，只需對(duì)輸入編碼進(jìn)行碼字長(zhǎng)度判斷。

二、簡(jiǎn)易混合選擇編碼方法

單邊范式Huffman編碼是Huffman編碼的一種特例，其適用條件為滿足式(1)。但當(dāng)信源符號(hào)概率按照大小順序排列后不滿足條件式(1)時(shí)，單邊范式Huffman編碼的壓縮性能將變差。由單邊范式Huffman編碼的特性，容易得到其編碼平均碼字長(zhǎng)度L為：

又因?yàn)镻(x1)≥1/n，所以可得其上限值ln：

當(dāng)且僅當(dāng)P(X1)=P(X2)....=P(xn）=1/n時(shí)上式取等號(hào)。

當(dāng)不滿足式(1)時(shí)，單邊范式Huffman編碼并不是最佳的，其與Huffman編碼的平均碼字長(zhǎng)度的差值將變大，壓縮性能也隨之變差。觀察三的上限值，當(dāng)n>2時(shí)，l近似為n/2。對(duì)比使用等長(zhǎng)編碼時(shí)的平均碼字長(zhǎng)度[lbn]，容易看出當(dāng)n>6時(shí)，[lbn]<n/2。等長(zhǎng)編碼的壓縮性能較Huffman編碼來說雖有所降低，但由于使用固定的碼字長(zhǎng)度編碼，因此識(shí)別和編碼較為簡(jiǎn)單，信源符號(hào)的編碼碼字可以與符號(hào)排列后的序位對(duì)應(yīng)。例如，一個(gè)有n個(gè)信源符號(hào)的信源，其符號(hào)按照符號(hào)概率大小排列后，使用等長(zhǎng)編碼，那么第七個(gè)符號(hào)的等長(zhǎng)編碼碼字正好是值k-1的二進(jìn)制表示。

單邊范式Huffman編碼的編解碼構(gòu)造簡(jiǎn)單，但其平均編碼碼字長(zhǎng)度變化范圍會(huì)隨著信源符號(hào)及其概率的變動(dòng)而過大；等長(zhǎng)編碼同樣編解碼構(gòu)造簡(jiǎn)單，其平均編碼碼字長(zhǎng)度在一定程度上是固定的。那么可以對(duì)任意一個(gè)信源輸出序列采取單邊范式Huffman編碼與等長(zhǎng)編碼的混合選擇編碼：對(duì)已知信源符號(hào)根據(jù)其概率進(jìn)行大小排序后，先計(jì)算單邊范式Huffman編碼平均碼字長(zhǎng)度，若此平均碼字長(zhǎng)度大于采取等長(zhǎng)編碼的平均碼字長(zhǎng)度，則使用等長(zhǎng)編碼，否則，使用單邊范式Huffman編碼。這樣信源編碼的平均碼字長(zhǎng)度將取等長(zhǎng)編碼平均碼字長(zhǎng)度與單邊范式Huffman編碼平均碼字長(zhǎng)度中最小的一個(gè)，即信源的平均碼字長(zhǎng)度L≤[1bn]。由于該編碼方法是使用等長(zhǎng)編碼與單邊范式Huffman編碼中的一種，因此對(duì)于任一信源其編解碼結(jié)構(gòu)都將十分簡(jiǎn)單，不需要構(gòu)造 Huffman樹或者進(jìn)行符號(hào)對(duì)應(yīng)的碼字存儲(chǔ)，使得其計(jì)算開銷成本極大地減小，而時(shí)間成本也僅取決于碼字長(zhǎng)度的判斷或二進(jìn)制與十進(jìn)制之間的轉(zhuǎn)換；在壓縮性能方面，較最佳的Huffman編碼來說會(huì)有所降低，但不會(huì)差過在同等概率條件下使用等長(zhǎng)編碼時(shí)的壓縮性能。

三、基于混合選擇編碼的對(duì)稱密鑰自變動(dòng)加密方案

事實(shí)上對(duì)于大型文本的統(tǒng)計(jì)，不同的文本，即便其字符個(gè)數(shù)相同，其統(tǒng)計(jì)結(jié)果也是不一樣的；若對(duì)文本劃分多個(gè)文本塊，那么每個(gè)文本塊的統(tǒng)計(jì)結(jié)果也各不相同。這樣若將文本劃分成多個(gè)塊，而每個(gè)塊采取單邊范式Huffman編碼與等長(zhǎng)編碼的混合選擇編碼方案，則整個(gè)編解碼系統(tǒng)結(jié)構(gòu)將十分簡(jiǎn)單，計(jì)算開銷較小，只是在壓縮性能上有所降低，但最低只會(huì)達(dá)到整個(gè)文本全部采取等長(zhǎng)編碼時(shí)的壓縮性能?？紤]將一個(gè)長(zhǎng)的信源輸出序列進(jìn)行多個(gè)塊的劃分，當(dāng)前塊的統(tǒng)計(jì)結(jié)果將作為下一個(gè)塊的簡(jiǎn)易混合選擇編碼的依據(jù)。這樣后續(xù)的塊將基于前一個(gè)塊的統(tǒng)計(jì)結(jié)果不斷改變編碼方式和信源符號(hào)的排列，從而實(shí)現(xiàn)自變動(dòng)的編解碼，整個(gè)編解碼過程并不依賴于整個(gè)信源符號(hào)的磷切概率；為了使整個(gè)系統(tǒng)計(jì)算開銷均衡，可以采取等長(zhǎng)劃分塊，即劃分塊長(zhǎng)度是一定的。若考慮將第1個(gè)塊的編解碼依據(jù)作為整個(gè)編解碼系統(tǒng)的密鑰，那么整個(gè)系統(tǒng)成為一個(gè)基于簡(jiǎn)易混合選擇編碼方案的對(duì)稱密鑰自變動(dòng)加密系統(tǒng)。

1、加密與解密過程

由于加解密需要知道第1塊段字符的編碼方式、塊的字符串長(zhǎng)度、字符排列順序后，才可以對(duì)整個(gè)密文或者明文進(jìn)行編碼，因此發(fā)送者Alice需要將它們生成為密鑰并對(duì)明文加密后都傳送給接收者Bob。這樣整個(gè)加解密過程如下：

(1)Alice對(duì)外發(fā)布整個(gè)信源符號(hào)的無序排列集合(x1，X2，...，Xk)，選取塊字符串長(zhǎng)度n并對(duì)信源符號(hào)進(jìn)行特定排列，記錄下排列后各個(gè)符號(hào)對(duì)應(yīng)的排列序位（tl，t2，…，tk)以及第1塊段的編碼方式Z，并根據(jù)這些生成密鑰，通過安全信道傳輸給接收者Bob。

(2)Alice根據(jù)靠對(duì)明文m劃取第1個(gè)塊，根據(jù)（t1，t2，…，tk)以及編碼方式Z對(duì)第一個(gè)塊進(jìn)行編碼，并統(tǒng)計(jì)當(dāng)前塊的各個(gè)符號(hào)數(shù)量，第1個(gè)塊編碼結(jié)束后根據(jù)統(tǒng)計(jì)結(jié)果計(jì)算更新(t1，t2，…，tk)與編碼方式i。

(3)Alice繼續(xù)根據(jù)n劃取塊，根據(jù)前一個(gè)塊更新的t1，t2，…，tk與編碼方式f對(duì)當(dāng)前塊編碼，并統(tǒng)計(jì)當(dāng)前塊的各個(gè)符號(hào)數(shù)量，待當(dāng)前塊編碼結(jié)束后根據(jù)統(tǒng)計(jì)結(jié)果計(jì)算更新(tl，t2，…，tk)與編碼方式i。

(4)Alice不斷重復(fù)步驟(3)，完成對(duì)明文m的加密，生成密文c，并將c傳送給接收者Bob。

解密過程正好是加密過程的逆過程，具體如下：

(1)Bob接收到Alice發(fā)送過來的密鑰，生成塊長(zhǎng)度n，第1個(gè)塊信源各符號(hào)排列序位(tl，t2，…，tk)與其編碼方式i。

(2)Bob根據(jù)(t1，t2，…，tk)與編碼方式i，開始對(duì)密文c解碼，并同時(shí)統(tǒng)計(jì)解碼出的各符號(hào)個(gè)數(shù)。

(3)當(dāng)解碼個(gè)數(shù)達(dá)到塊的字符串長(zhǎng)度n時(shí)，Bob根據(jù)當(dāng)前統(tǒng)計(jì)的結(jié)果計(jì)算更新(tl，t2，…，tk)與編碼方式i。

(4)Bob不斷重復(fù)步驟(2)和步驟(3)，完成整個(gè)密文c的解碼，從而獲取Alice所發(fā)送的明文m。

2、系統(tǒng)安全性分析

從整個(gè)加解密過程中可以看出，每個(gè)塊的編碼方式和每個(gè)信源符號(hào)對(duì)應(yīng)的碼字取決于前一個(gè)塊的統(tǒng)計(jì)結(jié)果，而與信源符號(hào)本身的概率集合無關(guān)。Alice發(fā)送的密鑰中包含了第1個(gè)塊編碼所依據(jù)的信源符號(hào)集合的排列序位、編碼方式和塊的字符串長(zhǎng)度靠。可以推斷，攻擊者如果無法準(zhǔn)確獲取到這個(gè)密鑰，那么破解出密文c將是極為困難的。

現(xiàn)在假定攻擊者獲取到了塊的字符串長(zhǎng)度玎和第1個(gè)塊的編碼方式i，但他卻沒有獲得第1個(gè)塊編碼所依據(jù)的信源符號(hào)集合的排列序位。這樣攻擊者可以準(zhǔn)確獲得對(duì)應(yīng)密文c編碼塊數(shù)、信源輸出序列長(zhǎng)度以及各個(gè)塊的數(shù)學(xué)上的統(tǒng)計(jì)結(jié)果。由于攻擊者缺少信源符號(hào)集合排列序位這個(gè)信息，他不得不去猜測(cè)編碼碼字與各個(gè)符號(hào)上的數(shù)學(xué)對(duì)應(yīng)關(guān)系，因此他將獲得k！種信源符號(hào)排序可能。由于每個(gè)塊的編碼取決于上一個(gè)塊的數(shù)學(xué)統(tǒng)計(jì)結(jié)果，而不是信源符號(hào)本身，從第1個(gè)塊所對(duì)應(yīng)的信源符號(hào)的一種排序只會(huì)獲得一種可能解密所得的明文，因此在攻擊者獲知塊的字符串長(zhǎng)度玎和第1個(gè)塊的編碼方式i時(shí)，必定得到k!種明文可能。

進(jìn)一步假設(shè)攻擊者只獲得了第1個(gè)塊的編碼方式i。這時(shí)攻擊者不僅需要確定塊的字符串長(zhǎng)度n，還需要得到k!種信源符號(hào)集合的大小排列序位。對(duì)于處理n，攻擊者可以采取窮舉方法不斷嘗試不同數(shù)值的n。由于攻擊者能全部獲取密文c，因此他能夠輕易統(tǒng)計(jì)出密文c中的比特總數(shù)M。不妨假定，編碼時(shí)Alice都只獲得了最差的壓縮性能，即整個(gè)明文m都采取等長(zhǎng)編碼生成密文c。所以，攻擊者能夠計(jì)算出信源輸出序列總長(zhǎng)度：

其中，k表示信源符號(hào)個(gè)數(shù)；M表示密文e比特總數(shù)；K表示信源符號(hào)使用等長(zhǎng)編碼時(shí)的平均碼字長(zhǎng)度。這樣攻擊者可以根據(jù)N開始進(jìn)行窮舉，以獲得可能的塊長(zhǎng)度。由于整個(gè)輸出序列使用等長(zhǎng)劃分塊，因此劃分的塊的總個(gè)數(shù)l為：

攻擊者根據(jù)式(5)可以近似地認(rèn)為對(duì)于不同的雅，若劃分的塊總個(gè)數(shù)l相同，則對(duì)于這些n值，其破譯結(jié)果是基本一致的。攻擊者考慮到對(duì)于明文m的劃分不會(huì)將塊的字符串長(zhǎng)度n取值過小，因此他需要設(shè)定一個(gè)窮舉n的下限值。而信源符號(hào)個(gè)數(shù)k是已知的，攻擊者可以將k作為窮舉n的下限值。那么不妨假設(shè)攻擊者取后作為窮舉n的下限值，這樣攻擊者將只需要窮舉l取1[n/k]時(shí)所對(duì)應(yīng)的一個(gè)n值。對(duì)于最終這些窮舉的靠，攻擊者認(rèn)為根據(jù)這些H值每次密文c解碼的結(jié)果將會(huì)不同。因?yàn)槊恳粋€(gè)穆值對(duì)應(yīng)著k!種信源符號(hào)集合的大小排列序位可能，所以最終攻擊者得到的解碼明文總數(shù)為[n/k]×k!種。下面將證明若序列總長(zhǎng)度N大于k2時(shí)，攻擊者將不得不猜測(cè)后種可能的序列塊劃分。

引理若N>k2，則存在后個(gè)不同的整數(shù)對(duì)(n,l)滿足：

證明：不妨假設(shè)l=1，2，…，k，先證明l取k個(gè)值中任意一個(gè)都存在一個(gè)靠使之滿足式(6)與式(7)。

設(shè)：

可得：

聯(lián)立式(8)與式(9)有：

由式(10)可得：

聯(lián)立式(11)與式(12)可得：

因此，l取k個(gè)值中任意一個(gè)都存在一個(gè)n，使之滿足式(6)與式(7)。

下面使用反證法證明這k個(gè)l各不相同。假設(shè)存在2個(gè)l值l1與l2，與其對(duì)應(yīng)的n值相同為no，其中，l1>l2。

因?yàn)閚o對(duì)于l1與l2都滿足式(6)與式(7)，所以：

聯(lián)立式(14)與式(15)，可得：

又因?yàn)閘1與l2為l-k的一個(gè)整數(shù)，且l1>l2，所以：

很明顯，式(16)與式(17)互相矛盾，假設(shè)不成立，即l不同取值所對(duì)應(yīng)的H都不會(huì)相同。引理得證。

由引理可知，若序列總長(zhǎng)度N>k2，，那么攻擊者將不得不窮舉出后種可能的序列塊劃分情況，最終攻擊者得到的解碼明文總數(shù)為kxk!。由此有：

即一個(gè)超指數(shù)級(jí)別的數(shù)。因此，若保證信源輸出序列總長(zhǎng)度大于k2，同時(shí)確保信源字符數(shù)后也足夠大，那么攻擊者使用窮舉方式獲得的解碼明文總數(shù)將是一個(gè)超指數(shù)級(jí)別的。顯然這種情形對(duì)于攻擊者來說，破譯密文的難度將會(huì)很大，計(jì)算開銷與時(shí)間開銷也將呈超指數(shù)級(jí)別的。

最后假定攻擊者只獲得了密文c，根據(jù)前面的分析可知此時(shí)攻擊者已經(jīng)很難破譯密文。明文編碼后，其密文比特總數(shù)M取決于各個(gè)塊的編碼方式：

其中，N1表示采取單邊范式Huffman編碼的字符總數(shù)；N2表示采取等長(zhǎng)編碼的字符總數(shù)；K表示采取等長(zhǎng)編碼時(shí)平均碼字長(zhǎng)度；K’表示采取單邊范式Huffman編碼時(shí)總平均碼字長(zhǎng)度。N1和N2滿足：N= Ni +N2。攻擊者對(duì)第1塊段采取不當(dāng)?shù)木幋a方式猜測(cè)，將對(duì)N1和N2值產(chǎn)生偏差，從而使得N值也有所偏差，最終獲得更多的錯(cuò)誤破譯明文。

隨意截取《指環(huán)王》英文文本中的幾段作為加密明文，將其對(duì)應(yīng)的二進(jìn)制文件的4位二進(jìn)制作為信源符號(hào)，即信源符號(hào)共16個(gè)。當(dāng)?shù)?塊的編碼方式為單邊范式Huffman編碼以及第一塊所依據(jù)的信源符號(hào)排列為已知時(shí)，不同塊長(zhǎng)度靠對(duì)應(yīng)的輸出密文總比特?cái)?shù)M如表2所示。

從表2中可以看出，隨著塊長(zhǎng)度n的變化，輸出總比特個(gè)數(shù)M也在變化，但M與信源符號(hào)總個(gè)數(shù)N之間并不具有可循的變化規(guī)律。很顯然，攻擊者此時(shí)若不能截獲塊長(zhǎng)度n的密鑰信息，將不能有效地獲得Ⅳ的信息，來降低破譯密文的難度。

由于每次加密的明文都不相同，因此其統(tǒng)計(jì)的結(jié)果也各不相同，劃分塊字符串長(zhǎng)度穆也不相同。所以，對(duì)于不同的明文，其生產(chǎn)的密鑰是截然不同的，該方案也滿足“一次一密”的加密要求。

3、密鑰的安全性考慮

發(fā)送者Alice需要將塊字符串長(zhǎng)度璣第1個(gè)塊編碼所依據(jù)的信源符號(hào)集合的大小排列序位（t1,t2,...,tk)以及第1塊段的編碼方式i作為密鑰傳送給接收者Bob，倘若直接傳送給Bob，那么需要至少一個(gè)長(zhǎng)度為k+2的數(shù)組保存這些信息。同時(shí)由于（t1,t2,...,tk)與n為純數(shù)值數(shù)據(jù)；而編碼方式i也可以被定義為：當(dāng)i=0時(shí)使用等長(zhǎng)編碼方式，當(dāng)i=1時(shí)使用單邊范式編碼方式，因此Alice傳送給Bob的密鑰數(shù)組為純數(shù)值數(shù)組，攻擊者如果獲得這個(gè)數(shù)值數(shù)組的部分信息，將大大降低破譯密文c的難度，所以，Alice需要對(duì)要傳輸?shù)拿荑€進(jìn)行一定的安全性考慮?？梢钥紤]一種簡(jiǎn)單可行的方法——插值法，對(duì)密鑰的保存也使用了插值法。由于整個(gè)數(shù)組都為數(shù)值數(shù)組，而（（t1,t2,...,tk)與其序列標(biāo)號(hào)有關(guān)tk與k具有對(duì)應(yīng)關(guān)系，因此Alice可以將整個(gè)數(shù)組與其序位構(gòu)成序列，從而獲得k+2個(gè)序列對(duì)：(1，t1)，（2，t2)，…，(k，tk)，(k+l，n)，(k+2，i))，這時(shí)Alice可以使用插值法生成一個(gè)滿足這k+2個(gè)序列對(duì)的插值多項(xiàng)式Pk+．(X)。通過插值法，可以得到多項(xiàng)式Pk+1 (X)完全展開后的形式：

根據(jù)式(20)的形式，Alice實(shí)際需要向Bob傳送這個(gè)多項(xiàng)式的k+2個(gè)系數(shù)，同樣為k+2個(gè)長(zhǎng)度的虢數(shù)值數(shù)組。當(dāng)Bob接收到這k+2個(gè)系數(shù)后，重構(gòu)出Pk+1 (X)，將1～k+2代入Pk+l (X)，從而獲得序列對(duì)(1，t1)，（2，t2)，…，(k，tk)，(k+l，n)，(k+2，i))，最終獲取密鑰。而對(duì)于攻擊者來說，如果他只獲取了Alice所發(fā)送的這些系數(shù)中的幾個(gè)，將無法完整復(fù)原Pk+1(X)，進(jìn)而無法獲得真正的密鑰，所以，他對(duì)密文c的破譯難度不會(huì)得到任何的改善。

另還有多種可行的密鑰傳輸方法，如提出的一種基于橢圓曲線離散對(duì)數(shù)的無證書混合加密方案，利用該加密方案對(duì)密鑰加密，能夠有效保障密鑰傳輸?shù)陌踩浴?/p>

該方案將信源輸出序列進(jìn)行塊劃分，并把第一個(gè)塊的編碼所依據(jù)的信源符號(hào)排列位置、編碼方式和塊長(zhǎng)度作為密鑰，使整個(gè)編碼系統(tǒng)成為一種自變動(dòng)的加密系統(tǒng)；由于將依賴于信源符號(hào)概率的編碼轉(zhuǎn)變?yōu)橐环N排列序位的數(shù)值編碼，因此在整個(gè)編解碼過程中并不需要存儲(chǔ)編碼碼字，大大減少了存儲(chǔ)空間，易于實(shí)現(xiàn)。并證明在完全不知道密鑰的情況下，攻擊基于混合選擇編碼方法的自變動(dòng)加密體制是較為困難的。

admin

收藏 海報(bào)分享