陸成剛 ,王慶月

(1.浙江工業(yè)大學(xué) 理學(xué)院,浙江杭州 310023;2.寧夏理工學(xué)院計算機學(xué)院,寧夏石嘴山 753000)

§1 引言

1882年銀行家弗蘭克-米勒首次發(fā)現(xiàn)使用了一次性密碼本[1],通信工程師吉爾伯特-佛納于1919年被授權(quán)了也許是密碼史上最重要的一個關(guān)于一次一密的專利[2].克勞德-香農(nóng)在1940年代發(fā)現(xiàn)并證明了一次一密方法的理論意義,他的報告于1949年被公開[3].幾乎同時期蘇聯(lián)數(shù)學(xué)家弗拉基米爾-科特爾尼科夫獨立地證明了一次一密的絕對安全性[4].王勇提出了密鑰分布等概率性與明文概率分布不兼容的問題[5].雷鳳宇證明了完善保密性密碼體制的條件和存在性[6].本文重新審視了密鑰等概率性條件和滿足完善保密性的關(guān)系,在一個特定的完善保密性角度下推導(dǎo)出明文分布的等概率性.進(jìn)一步,傳統(tǒng)一次一密理論的密鑰等概率性條件可以去掉,只保留明文和密鑰的互相獨立性就能證明完善保密性.這個結(jié)果進(jìn)一步推廣了一次一密方法的適用范圍,同時指出密鑰等概率特性下的一次一密法仍可以適用于信源壓縮編碼后的明文加密.

§2介紹一次一密法,§3使用概率論證明了它滿足完善保密性,并且推導(dǎo)出明文的等概率分布特性.§4使用明文和密鑰互相獨立作條件證明了完善保密性.

§2 一次一密

考慮有限加法群G,明文,密鑰和密文分別是以G作為樣本空間的離散隨機變量M,K和C,并且在每一個樣本點上的概率值都大于零.對明文隨機變量M的任一取值m,令任一密鑰k(密鑰隨機變量K的取值)與之運算得到密文c(密文隨機變量C的取值),即m+k=c,其中+為G中的加法運算.而解密運算c?k=m,?為加法運算的逆運算.明文和密文之間的運算k=c?m可以解出密鑰.一個加密算法,其對應(yīng)的解密算法和確定密鑰的算法決定了三個隨機變量M,K和C的三組確定映射

其中f為加密函數(shù),g為解密函數(shù),h可由明文和密文確定密鑰,這三個函數(shù)是確定的,已知的函數(shù).一次一密的主要實現(xiàn)方式為將加密看作一個過程,則明文序列為與隨機變量M同分布的一個隨機過程,每次加密參與的密鑰視作與K同分布的一個隨機過程.在K與M互相獨立,并且K的分布為等概率分布(均勻分布)的條件下可以證明一次一密滿足完善保密性.

§3 滿足完善保密性

見諸于文獻(xiàn)的完善保密性主要是指明文與密文互相獨立,即

它的密碼學(xué)含義可以解釋為知道密文并不能改善對于明文的認(rèn)識,即密文沒有提供對明文的任何信息.使用信息熵的語言,以密文作條件的明文熵等于明文熵,從而知道明文,密文的互信息為零,即

另外一種常見的完善保密性的定義為

它的密碼學(xué)意義也很容易理解,就是密文c是由明文密鑰對(m1,k1)生成而成還是由(m2,k2)加密而成的可能性沒有差異.這個定義等價于聯(lián)合條件概率分布P((M,K)|C=c)為等概率分布.

定理1以加法有限群G為樣本空間的隨機變量M,K和C滿足f,g和h確定函數(shù)組成的式(1),隨機變量M,K互相獨立,隨機變量K概率分布符合均勻分布,則隨機變量M,C滿足式(2).

證設(shè)明文m,密鑰k和密文c滿足

上面倒數(shù)第三個等號利用式(5),倒數(shù)第二個等號利用了隨機變量K的概率分布符合均勻分布的特性,最后的等號說明密文也符合等概率分布,

以上倒數(shù)第二個等號利用了式(5),最后一個等式利用了式(6),這里說明了M,C的互相獨立性,即

定理2以加法有限群G為樣本空間的隨機變量M,K和C滿足f,g和h確定函數(shù)組成的式(1),隨機變量M,K互相獨立,隨機變量K概率分布符合均勻分布,當(dāng)變量M,K和C滿足式(3)定義的完善保密性時,明文一定符合均勻概率分布.

證由于隨機變量M,K互相獨立,隨機變量K概率分布符合均勻分布,由定理1的證明過程得到式(5),(6)成立,考慮

而式(8)左端是等概率分布的(滿足式(3)的完善保密性),于是右端表明明文也是符合等概率分布的.

§4 新條件下滿足完善保密性

為保證完善保密性,在定理1中設(shè)置了一個先決條件,即密鑰的等概率分布特性,實際上這個條件是冗余的,下面通過定理3證明在沒有這一條件時一次一密方法能夠保證完善保密性.

定理3以加法有限群G為樣本空間的隨機變量M,K和C滿足f,g和h確定函數(shù)組成的式(1),隨機變量M,K互相獨立,則隨機變量M,C滿足式(2).

證由于式(1)中f,g,h為確定的,已知算法.易知以下三條件熵為零

另因隨機變量M與K獨立,由H(C)=H(M|K)=H(K|M)得到H(C)=H(M)=H(K).所以H(M|C)=H(M),進(jìn)而滿足式(2).此外

說明明文和密文之間的互信息為零,而這說明明文和密文之間的信道容量為零.

類似在該定理證明中的方法,可得到

這說明在C=c時,聯(lián)合變量(M,K)的不確定性和M是一個量級的,這也是自然的,因為M確定了,K自然也確定了.假如進(jìn)一步要求滿足式(3)的完善保密性,那么由P((M,K)|C=c)的等概率性,導(dǎo)致H((M,K)|C)取到最大值,即H(M)取到最大,而這實際就是要求明文分布的等概率性.而定理3說明變量M,K互相獨立時,就可以滿足隨機變量M,C互相獨立的完善保密性,對明文M的概率分布卻沒有限制.

此外,定理3說明在一次一密執(zhí)行時密鑰的等概率性實際是不必要的,只要密鑰與明文獨立無關(guān)即可.此外,在滿足特定的完善保密性時,密鑰等概率特性帶來了明文分布的等概率特性的限制,但這并非對適用的明文產(chǎn)生了制約.事實上只要明文經(jīng)過熵壓縮信源編碼后的碼流均能呈現(xiàn)0,1比特的概率均衡的隨機性(如果0,1出現(xiàn)的概率不均衡,說明還有進(jìn)一步可壓縮的空間),這恰恰使得“明文”符合在0,1比特上的等概率特性.因此,在使用密鑰等概率特性的一次一密時建議首先對明文進(jìn)行無損熵壓縮編碼.

§5 總結(jié)與展望

本文重新審視了一次一密的密鑰等概率特性與完善保密性的關(guān)系,并通過信息熵工具證明了明文和密鑰獨立無關(guān)條件下的一次一密的安全性.將來可以考慮信息熵工具用于對公私鑰密碼體制的安全性分析的研究.