一次一密理論的再認(rèn)識(shí)

陸成剛 ,王慶月

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

§1 引言

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

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

§2 一次一密

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

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

§3 滿(mǎn)足完善保密性

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

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

另外一種常見(jiàn)的完善保密性的定義為

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

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

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

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

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

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

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

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

§4 新條件下滿(mǎn)足完善保密性

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

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

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

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

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

類(lèi)似在該定理證明中的方法,可得到

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

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

§5 總結(jié)與展望

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