頻率不相關(guān)性及其在單鑰密碼系統(tǒng)中的應(yīng)用

田傳俊

深圳大學(xué)信息工程學(xué)院，深圳 518060

?

【電子與信息科學(xué) / Electronic and Information Engineering】

頻率不相關(guān)性及其在單鑰密碼系統(tǒng)中的應(yīng)用

田傳俊

深圳大學(xué)信息工程學(xué)院，深圳 518060

探討頻率測(cè)度論在保密通信中的應(yīng)用，研究單鑰密碼系統(tǒng)中加密變換非線性性質(zhì)的相關(guān)問題．針對(duì)目前常見分組密碼算法在非線性性質(zhì)方面缺乏理論規(guī)范描述和嚴(yán)格證明的現(xiàn)狀，探討一般單鑰密碼系統(tǒng)中非線性加密變換嚴(yán)格的數(shù)學(xué)描述和實(shí)現(xiàn)方法．利用頻率測(cè)度論中的不相關(guān)概念，引入不相關(guān)單鑰密碼系統(tǒng)這一新概念，指出這類不相關(guān)基本單鑰密碼系統(tǒng)的存在性，并在理論上嚴(yán)格證明了強(qiáng)大數(shù)定律，即在利用不相關(guān)基本單鑰密碼系統(tǒng)進(jìn)行所有可能的保密通信過程中，當(dāng)明文單元序列服從離散無(wú)記憶均勻分布且密鑰周期性更換時(shí)，明文序列與密文序列將必然不相關(guān)．

數(shù)據(jù)安全；保密通信系統(tǒng)；不相關(guān)單鑰密碼系統(tǒng)；強(qiáng)大數(shù)定律；頻率測(cè)度論；不相關(guān)性

隨著數(shù)字通信技術(shù)的發(fā)展，計(jì)算機(jī)數(shù)字通信的安全性日益成為當(dāng)今的重大科研課題．密碼學(xué)是一門重要的基礎(chǔ)理論，加密技術(shù)則是保證信息安全傳輸和存儲(chǔ)的重要技術(shù)之一．在最近幾十年中，加密算法已引起許多學(xué)者的關(guān)注，并取得令人矚目的成就[1-5]．根據(jù)現(xiàn)代密碼學(xué)理論，加密算法可分為單鑰密碼算法和雙鑰密碼算法，其中，單鑰密碼算法又可分為分組密碼算法和序列密碼算法．在現(xiàn)有常見的分組密碼算法中，普遍認(rèn)為加密變換的非線性性質(zhì)是通過局部的S盒變換來(lái)實(shí)現(xiàn)的，但迄今為止未見這方面嚴(yán)格的理論證明．

Shannon[1]于1949年創(chuàng)立了基于信息論的保密通信理論，并在密碼學(xué)理論的發(fā)展過程中做出了杰出貢獻(xiàn)．他用概率統(tǒng)計(jì)的觀點(diǎn)對(duì)消息源、密鑰源、接收和截獲消息進(jìn)行了數(shù)學(xué)描述和分析，用不確定性和唯一距離度量了密碼系統(tǒng)的安全性，闡明了密碼系統(tǒng)、完善保密性、純密碼、理論安全性和實(shí)際安全性等概念，從而宣告了密碼學(xué)信息理論時(shí)代的到來(lái)[2]．

研究分析文獻(xiàn)[1-9]發(fā)現(xiàn)，基于Shannon理論的現(xiàn)代保密通信理論還存在一些問題．例如，現(xiàn)有保密通信系統(tǒng)的理論安全性概念不明確，相應(yīng)理論研究所用基礎(chǔ)理論知識(shí)的綜合應(yīng)用程度不夠，導(dǎo)致現(xiàn)有常見密碼算法的設(shè)計(jì)過于注重實(shí)際安全性而忽略了理論安全性的基礎(chǔ)指導(dǎo)作用；對(duì)Shannon提出的完善保密性概念的解釋混亂或片面，妨礙了相關(guān)問題的深入研究；常見分組密碼算法中加密變換的非線性的概念不規(guī)范，且利用S盒局部變換的實(shí)現(xiàn)方式也缺乏嚴(yán)格理論證明[6-9]．這些問題可能是現(xiàn)有的保密通信系統(tǒng)中相關(guān)研究難以深入的主要原因之一．

文獻(xiàn)[2-5]指出，目前學(xué)者普遍認(rèn)為保密通信系統(tǒng)既包含完全隨機(jī)性，又含有偽隨機(jī)性．因此，綜合利用隨機(jī)性和偽隨機(jī)性的知識(shí)來(lái)研究保密系統(tǒng)中的相關(guān)問題才更全面或恰當(dāng)．由文獻(xiàn)[1]可知，Shannon建立的保密通信理論在理論安全性的描述或研究中對(duì)信息論知識(shí)的應(yīng)用較多，但對(duì)偽隨機(jī)性理論知識(shí)在其中的綜合應(yīng)用的論述仍不夠深入，因而有必要進(jìn)一步探討偽隨機(jī)性理論在保密通信系統(tǒng)設(shè)計(jì)中的應(yīng)用問題．若綜合利用隨機(jī)性和偽隨機(jī)性理論來(lái)研究保密通信系統(tǒng)的設(shè)計(jì)問題，則有可能獲得一些新成果，甚至建立起研究保密通信系統(tǒng)的新方法或密碼算法的設(shè)計(jì)原則．

筆者在文獻(xiàn)[10]嘗試建立了一門相對(duì)獨(dú)立的基礎(chǔ)理論——頻率測(cè)度論，它是研究序列偽隨機(jī)性的一門較系統(tǒng)的基礎(chǔ)理論，其主要內(nèi)容與概率論的內(nèi)容相互對(duì)應(yīng)．可啟發(fā)人們?nèi)ヌ接戭l率測(cè)度論在概率論的一些應(yīng)用問題(含現(xiàn)代密碼學(xué))中的相關(guān)研究．由于頻率測(cè)度論剛建立不久，還未見有文獻(xiàn)討論它在保密通信中的應(yīng)用問題．本研究以加密算法非線性性質(zhì)研究作為頻率測(cè)度論用于保密通信理論的切入點(diǎn)，給出相關(guān)的數(shù)學(xué)概念和證明方法，嘗試綜合利用概率論和頻率測(cè)度論進(jìn)行保密通信系統(tǒng)理論研究，為今后加密算法設(shè)計(jì)打下基礎(chǔ)．

1 頻率測(cè)度論的基本知識(shí)

本節(jié)介紹頻率測(cè)度論中的一些基本知識(shí)[10]．

由文獻(xiàn)[10]可知，對(duì)于任意離散數(shù)列(X，Y)， 若E(X)和E(Y)存在，則當(dāng)且僅當(dāng)E(XY)存在時(shí)， cov(X，Y)存在，且cov(X，Y)=E(XY)-E(X)E(Y)；當(dāng)且僅當(dāng)E(XY)=E(X)E(Y)時(shí)，X與Y不相關(guān)．

2 問題描述

將任一有限集合上一一對(duì)應(yīng)的映射稱為置換，本研究著重分析有限整數(shù)集合Zn={0，1，…，n-1}上的置換f：Zn?Zn． 由于不少常見的密碼算法都利用了置換作為“置亂”變換，因此，研究置換特性對(duì)密碼系統(tǒng)的設(shè)計(jì)具有特殊意義．文獻(xiàn)[2]指出，設(shè)計(jì)分組密碼的關(guān)鍵在于找到一種算法，使其能在密鑰的控制下，從一個(gè)足夠大且“好”的置換子集中，便捷地選出置換．然而，如何系統(tǒng)地評(píng)估置換的“好”或“壞”仍未有公認(rèn)的有效方法．本研究將會(huì)初步探討該問題．

Shannon[1]曾將密碼(或保密)系統(tǒng)(或算法)定義為從明文空間到密文空間上的一組可逆變換．因此，可將密碼系統(tǒng)表示為(M，C，T)． 其中，M為明文空間；C為密文空間；T是從M到C上的一組可逆變換，被稱為(理論)密鑰變換空間．在保密通信的理論研究中，密碼系統(tǒng)(M，C，T)具有重要的基礎(chǔ)作用，被稱為理論模型．不過，為便于實(shí)際應(yīng)用，密鑰變換空間T通常需要利用整數(shù)子集K和加密函數(shù)E來(lái)實(shí)現(xiàn)．相應(yīng)地，所有逆變換T-1要利用K和解密函數(shù)D來(lái)實(shí)現(xiàn)．因此，現(xiàn)代密碼學(xué)中常用5元組(M，K，C，E，D)表示密碼系統(tǒng)．其中，K為(實(shí)際)密鑰空間；E和D分別是加密和解密變換或函數(shù)．為了區(qū)別，將(M，K，C，E，D)稱為實(shí)際模型或綜合模型．一般來(lái)講，同一個(gè)理論模型可利用多種不同形式的實(shí)際模型來(lái)實(shí)現(xiàn)，因而理論模型是基礎(chǔ)．

當(dāng)前，在實(shí)際計(jì)算機(jī)保密通信的過程中，需選擇一個(gè)基礎(chǔ)的密碼系統(tǒng)(M，K，C，E，D)或(M，C，T)進(jìn)行大量的保密通信．其中，明文和密文空間通常是由所有nbit序列組成的集合(M=C=Z2n)， 這里，n∈N ；M和C中的每個(gè)元素通常是加解密函數(shù)E和D一次處理的基本單元．此時(shí)，將(M，K，C，E，D)或(M，C，T)稱為基本密碼系統(tǒng)，M、C、T或K中的元素分別稱為(基本)單元．根據(jù)現(xiàn)代密碼學(xué)理論和實(shí)際保密通信應(yīng)用的現(xiàn)狀，可將保密通信系統(tǒng)的設(shè)計(jì)分為2個(gè)階段：一是基本密碼系統(tǒng)的設(shè)計(jì)；二是基本密碼系統(tǒng)應(yīng)用過程的設(shè)計(jì)．在實(shí)際應(yīng)用過程中，保密通信中所有可能的明文是由所有可能的基本明文單元組成的一個(gè)隨機(jī)序列M1，M2，…， 相應(yīng)的密鑰單元序列為K1，K2，…， 密文單元序列為C1，C2，…． 其中，Ci=E(Mi，Ki)，i=1，2，…．

設(shè)基本明文與密文空間為M=C=Z2n={0，1，…，2n-1}， 密鑰空間為K或T． 當(dāng)密鑰確定后，加密變換Ti：Z2n?Z2n就是一個(gè)置換，被稱為(基本)系統(tǒng)置換或算法置換．其中，Ti∈T是利用ki∈K和加密函數(shù)E所確定的一個(gè)可逆變換，且Ti和ki通常都是相互唯一確定的．這樣，基本單鑰密碼系統(tǒng)的設(shè)計(jì)通常都等價(jià)于一組系統(tǒng)置換的設(shè)計(jì)．如此一來(lái)，一組系統(tǒng)置換的效果就會(huì)影響到保密通信的安全性與高效性等．如何評(píng)價(jià)置換的置亂效果是保密通信系統(tǒng)的基礎(chǔ)問題．

保密通信系統(tǒng)的安全性是保密通信的核心．當(dāng)前，密碼系統(tǒng)的安全性分析或評(píng)估方法主要有兩類：一是由Shannon提出的基于信息論的方法[1]；二是基于現(xiàn)代計(jì)算復(fù)雜性理論的方法[2]．一般來(lái)講，信息論只能用于描述密碼系統(tǒng)內(nèi)部的各種隨機(jī)性及其關(guān)系，而計(jì)算復(fù)雜性理論只是用于分析密碼系統(tǒng)內(nèi)部的各種具體變換的計(jì)算量。由于一個(gè)或多個(gè)確定性置換并不包含隨機(jī)性，且理論上研究這些置換時(shí)并未考慮到它們的具體實(shí)現(xiàn)方法，因而就不必去分析具體變換的計(jì)算量大小. 因此，上述兩種評(píng)價(jià)方法都無(wú)法準(zhǔn)確地評(píng)價(jià)一個(gè)或多個(gè)確定性置換的置亂效果，因而需考慮利用不同的分析方法去評(píng)價(jià)置換的置亂效果的好壞．由于確定性置換的置亂效果好壞是一種類隨機(jī)性質(zhì)，這為利用頻率測(cè)度論的知識(shí)來(lái)描述置換的置亂效果提供了可能．

為便于表述，將保密通信中具體的明文、密鑰和密文單元分別用m、k(或Ti)和c表示，并將任意隨機(jī)選取的明文與密鑰及其相應(yīng)的密文單元用M、K(或T)和C表示，則c=E(k，m)或m=D(k，c)， 且C=E(M，K)，或C=T(M)，又或M=D(C，K)． 其中，C=E(M，K)表示當(dāng)隨機(jī)變量K和M任意取定一個(gè)值時(shí)加密函數(shù)的取值為C．

若將單鑰密碼算法或系統(tǒng)的基本明文和密文單元所決定的最大十進(jìn)制數(shù)設(shè)為n-1， 則給定一個(gè)或所有密鑰，可將基本密碼算法等效地看成Zn上的一個(gè)或所有的系統(tǒng)置換．不妨將所有明文單元排列成自然順序(0，1，…，n-1)， 并稱之為標(biāo)準(zhǔn)數(shù)列，當(dāng)密鑰ki或Ti確定后，將所有對(duì)應(yīng)的密文單元設(shè)為(c0，c1，…，cn-1)， 則每一個(gè)密鑰ki或Ti就決定了所有明文單元(0，1，…，n-1)到相應(yīng)的密文單元(c0，c1，…，cn-1)之間的一個(gè)系統(tǒng)置換．其中，i，ci∈Zn和ci=Ek(i)=E(i，k)， 且(c0，c1，…，cn-1)兩兩互不相同．直觀上看，若明文與相應(yīng)密文單元序列之間是毫不相關(guān)或類隨機(jī)，又或混亂的，則可認(rèn)為該系統(tǒng)置換的置亂效果較好．因此，當(dāng)不同密鑰決定的系統(tǒng)置換互不相同，甚至不同系統(tǒng)置換之間“毫不相關(guān)”時(shí)，只要密鑰數(shù)量足夠多，就可認(rèn)為該基本單鑰密碼系統(tǒng)在大量的實(shí)際保密通信中的應(yīng)用效果良好．

顯然，全體明文單元(0，1，…，n-1)與相應(yīng)的全體密文單元(c0，c1，…，cn-1)之間的關(guān)系是確定的，且它們之間是否“混亂”與保密通信系統(tǒng)的安全性密切相關(guān)．若利用頻率測(cè)度論的知識(shí)來(lái)描述它們之間“毫不相關(guān)”等類似隨機(jī)的性質(zhì)，則可利用“頻率獨(dú)立”、“頻率不相關(guān)”或“頻率聯(lián)合分布”等概念和知識(shí)進(jìn)行描述．本研究?jī)H探討利用頻率不相關(guān)的概念來(lái)描述單鑰密碼系統(tǒng)中的系統(tǒng)置換或密鑰變換效果好壞的問題．

3 不相關(guān)置換

直觀上看，用不同的置換將所有明文單元(0，1，…，n-1) “打亂”為密文單元(c0，c1，…，cn-1)的置亂效果是不一樣的，甚至不同置換之間的相關(guān)程度也不一樣．由于密鑰空間所決定的每個(gè)系統(tǒng)置換是確定的，而密鑰和明文的選取是隨機(jī)的，因此，為全面研究加密變換或系統(tǒng)置換的效果，需綜合利用概率論和頻率測(cè)度論等知識(shí)．

由于頻率測(cè)度論與概率論的主要內(nèi)容相互對(duì)應(yīng)，因此，參照概率論研究隨機(jī)性的一些方法可提出研究偽隨機(jī)性的相應(yīng)方法．概率論中不相關(guān)性和獨(dú)立性等是研究隨機(jī)性問題的常用概念，本研究?jī)H考慮頻率不相關(guān)性在保密通信系統(tǒng)研究中的應(yīng)用，其他知識(shí)應(yīng)用尚待下一步考慮．

為便于利用頻率測(cè)度論的知識(shí)分析有限個(gè)元素所組成的序列間的性質(zhì)，有必要給出有限序列的相關(guān)概念，這有利于設(shè)計(jì)基本密碼系統(tǒng)．

定義7 對(duì)于任意2個(gè)有限數(shù)列L和H， 將L和H進(jìn)行周期性的無(wú)限擴(kuò)展后所得到的數(shù)列X=(L，L，…)和Y=(H，H，…)，分別稱為L(zhǎng)和H的周期擴(kuò)展數(shù)列．若數(shù)列X和Y是頻率不相關(guān)的，則稱相應(yīng)的有限數(shù)列L和H也是(頻率)不相關(guān)的，由此可類似定義頻率獨(dú)立等概念．

特別地，若任一密鑰變換T前后的明文序列M=(0，1，…，n-1)與密文序列C=(c0，c1，…，cn-1)是不相關(guān)的，則將該密鑰變換T稱為不相關(guān)置換．由頻率測(cè)度論(或概率論)可知，不相關(guān)置換說(shuō)明變換前后的兩個(gè)序列不是線性關(guān)系，因此，為保證整個(gè)理論密鑰空間具有良好性質(zhì)，可要求基本密碼系統(tǒng)中每個(gè)系統(tǒng)置換不相關(guān)，甚至還可要求任意兩個(gè)系統(tǒng)置換之間也不相關(guān)．

下面用一類具體置換的例子說(shuō)明不相關(guān)置換的存在性與數(shù)量問題．

眾所周知，幻方可用于構(gòu)造加密算法中的各種置換，其概念為：對(duì)于自然數(shù)n>2， 若將數(shù)集0，1，…，n2-1(或1，2，…，n2)排列成一個(gè)n階方陣，使得每行、每列和兩條對(duì)角線上的所有元素之和都相等，則稱該方陣為n階幻方，記為Hn， 并將Hn每行的和n(n2-1)/2稱為幻和，并將所有不同的n階幻方的數(shù)目記為?(n)[11-13]．

當(dāng)n>2時(shí)，任意n階幻方都是存在的[11-13]．由文獻(xiàn)[13]可知， ?(3)=8和?(4)=7 040． 在說(shuō)明不相關(guān)置換的存在性與應(yīng)用之前，先將幻方概念稍作推廣．

定義8 對(duì)任一自然數(shù)n>2， 稱n階方陣Gn=(gij)n×n是一個(gè)(n階)廣義幻方，如果以下條件成立：

1) (g11，g12，…，g1n，g21，g22，…，g2n，…，gn1，gn2，…，gnn)是(0，1，…，n2-1)或(1，2，…，n2)的一個(gè)置換；

本研究將利用廣義幻方所構(gòu)造的置換定義為廣義幻方置換．其中，用廣義幻方設(shè)計(jì)M=Zn2上的一個(gè)置換作為加密變換T是指T(m)=gij， 這里，m=(i-1)n+(j-1) ∈Zn2．

引理1 設(shè)n>2， 且n∈N ，Hn是一個(gè)n階幻方，則將Hn的行或列進(jìn)行有限次的互換所得到的矩陣Gn就是一個(gè)廣義幻方．

由引理1可知，n階廣義幻方不僅存在，且所有n階廣義幻方的數(shù)量比所有n階幻方的數(shù)量更多．將所有不同的n階廣義幻方的數(shù)目稱為廣義幻方數(shù)，記為ρ(n)， 則有ρ(n)≥?(n)， 且有ρ(3)>?(3)=8和ρ(4)>?(4)=7 040．

下面證明廣義幻方置換具有不相關(guān)性，從而說(shuō)明不相關(guān)置換是存在的，且數(shù)量比廣義幻方數(shù)更多．

定理1 設(shè)整數(shù)n>2，Gn=(gij)n×n是一個(gè)廣義幻方，則由Gn按逐行(或列)讀取所得到的數(shù)列LGn=(g11,g12,…,g1n,g21,g22,…,gn1,gn2…,gnn)與標(biāo)準(zhǔn)數(shù)列W=(0，1，…，n2-1)是不相關(guān)的．

(1)

因式(1)的分子為

0g11+…+(n-1)g1n+ng21+…+(2n-1)g2n+…+(n2-n)gn1+…+(n2-1)gnn=

0(g11+g12+…+g1n)+n(g21+g22+…+g2n)+…+(n2-n)(gn1+gn2+…+gnn)+

(g12+g22+…+gn2)+2(g13+g23+…+gn3)+…+(n-1)(g1n+g2n+…+gnn)=

(2)

因此，covf(X，Y)=Ef(XY)-Ef(X)Ef(Y)=0， 即X和Y不相關(guān)．

證畢．

由定理1可知，若將任一n階廣義幻方作為基本密碼系統(tǒng)中M=C=Zn2上的一個(gè)系統(tǒng)置換，則該置換具有不相關(guān)性，因而可以說(shuō)它是非線性變換，此時(shí)可以認(rèn)為幻方作為加密變換的置亂效果不差．

4 不相關(guān)單鑰密碼算法概念與性質(zhì)

當(dāng)前，非線性系統(tǒng)研究已成為眾多學(xué)者研究的熱點(diǎn)，因而有理由要求所設(shè)計(jì)的保密通信系統(tǒng)的系統(tǒng)置換都是非線性變換．下面將著重討論一般單鑰密碼系統(tǒng)具有不相關(guān)性的相關(guān)問題，利用其理論模型先給出如定義9的“非線性”基本單鑰密碼系統(tǒng)的概念．

定義9 設(shè)基本密碼系統(tǒng)(M，C，T)的明文和密文空間為M=C=Zn． 若該基本密鑰空間的任一系統(tǒng)置換T滿足：基本明文單元序列與利用T對(duì)它們依次作加密變換后得到的相應(yīng)密文序列是不相關(guān)的，則將該基本單鑰密碼系統(tǒng)或算法稱為(弱)不相關(guān)的，或一般性地稱為非線性的．

同時(shí)，對(duì)于一個(gè)不相關(guān)基本單鑰密碼系統(tǒng)，如果該系統(tǒng)中的任意2個(gè)不同的系統(tǒng)置換之間也不相關(guān)，則將該基本單鑰密碼系統(tǒng)或算法稱為強(qiáng)不相關(guān)單鑰密碼系統(tǒng)，其中，兩個(gè)系統(tǒng)置換f1：Zn?Zn和f2：Zn?Zn的不相關(guān)是指由它們所決定的兩個(gè)序列L1和L2不相關(guān).這里，L1=(f1(0)，f1(1)， …，f1(n-1))；L2=(f2(0)，f2(1)， …，f2(n-1))．

顯然，可將不相關(guān)基本單鑰密碼系統(tǒng)的概念推廣到任意有限重單鑰密碼系統(tǒng)(Mr，Cr，Tr)、 甚至所有可能的無(wú)限保密通信或無(wú)窮維單鑰密碼系統(tǒng)之中．其中，所有可能的保密通信具有不相關(guān)性是指任意的無(wú)限明文與相應(yīng)密文之間必然是不相關(guān)的，且Mr=M×M×…×M等. 這對(duì)研究實(shí)際和所有可能的保密通信是有用的．因此，可以說(shuō)定義9給出了非線性單鑰密碼系統(tǒng)的一種嚴(yán)格數(shù)學(xué)概念．

由定義9和以上討論，顯然定理2成立．

定理2 如果基本單鑰密碼系統(tǒng)(M，C，T)的基本明文和密文空間為M=C=Zn2，其中，n是一個(gè)不小于3的整數(shù)，且其基本密鑰變換空間T是從ρ(n)個(gè)不同的廣義幻方中選取的一組廣義幻方所確定的置換(如可選│T│=n2或n2的某個(gè)正整數(shù)倍)，則該基本單鑰密碼系統(tǒng)就具有不相關(guān)性．

備注1 定理2給出了非線性單鑰密碼系統(tǒng)的一種實(shí)現(xiàn)方式，這點(diǎn)與現(xiàn)有分組密碼算法中關(guān)于加密變換的非線性性質(zhì)的實(shí)現(xiàn)方式略有不同．例如，普遍認(rèn)為包含數(shù)據(jù)加密標(biāo)準(zhǔn)(dataencryptionstandard，DES)算法在內(nèi)的常用分組密碼算法中加密變換的非線性性質(zhì)主要是通過S盒來(lái)實(shí)現(xiàn)的[6-8]．但S盒只是一種局部的非線性變換，而不相關(guān)的系統(tǒng)置換是一種全局的非線性變換，由此可見，如定義9和定理2所定義的單鑰密碼系統(tǒng)的非線性性質(zhì)及其相應(yīng)的實(shí)現(xiàn)方式更合理．

備注2 定理2所選取的基本密鑰變換空間是否能夠利用K=Zn2和某個(gè)簡(jiǎn)單易計(jì)算的加密函數(shù)E來(lái)實(shí)現(xiàn)呢？同時(shí)，如何從ρ(n)個(gè)不同的廣義幻方中選取出性能優(yōu)良的一組廣義幻方置換作為理論密鑰空間？這些是今后值得研究的問題.

由現(xiàn)有文獻(xiàn)可知，將任一基本密碼系統(tǒng)用于實(shí)際保密通信時(shí)，系統(tǒng)的安全性將在很大程度上受到明文和密鑰統(tǒng)計(jì)特性等實(shí)際因素的影響．下面將給出明文單元序列和密鑰單元序列滿足某種條件時(shí)，利用不相關(guān)基本單鑰密碼系統(tǒng)進(jìn)行所有可能的保密通信也會(huì)具有不相關(guān)性，因而從非線性角度來(lái)看該保密通信具有較為理想的安全性，因?yàn)殡y以利用密文的線性變換對(duì)明文做出有把握的統(tǒng)計(jì)推斷．

【證】 由已知條件可知，存在正整數(shù)q， 使得ki+q=ki， 對(duì)任意i=1，2，…，記k1，k2，…=(k1k2…kq)． 由于M1，M2，…是一列相互獨(dú)立、同均勻分布的隨機(jī)變量序列，因此，由Borel強(qiáng)大數(shù)定律，得

j=0，1，…，n-1

(3)

(4)

其中，Q=(n-1)/2．

(5)

其中，j=0，1，…，n-1；i=1，2，…，q．

(6)

顯然，對(duì)任意充分大的整數(shù)r>0和u=rq，都有

(7)

其中，rij表示在明文序列M1，M2，…，Mrq中相應(yīng)利用密鑰kj加密所用的明文i出現(xiàn)的次數(shù)，對(duì)一切i∈Zn和j=1，2，…，q．

由式(5)可得， 對(duì)任意i∈Zn和j=1， 2， …，q， 都有

(8)

因此，由式(4)～式(8)和頻率互協(xié)方差的定義與性質(zhì)，可得

(9)

于是，定理3的結(jié)論成立．

證畢.

類似定理3的證明，還可得到定理4．

(10)

(11)

證畢.

結(jié) 語(yǔ)

本研究探討了頻率測(cè)度論在保密通信中的應(yīng)用問題，利用頻率不相關(guān)性提出了不相關(guān)單鑰密碼系統(tǒng)的新概念，并利用不同于現(xiàn)有S盒的方式實(shí)現(xiàn)了加密變換的非線性．特別是在現(xiàn)有密碼系統(tǒng)非線性性研究中普遍缺乏科學(xué)描述和嚴(yán)格理論證明的情況下，本文給出了一般單鑰密碼系統(tǒng)具有非線性性質(zhì)的規(guī)范數(shù)學(xué)概念，并從理論上嚴(yán)格證明了將不相關(guān)基本單鑰密碼系統(tǒng)用于所有可能的保密通信中時(shí)，在一定條件下，保密通信系統(tǒng)幾乎必然也具有不相關(guān)性．該結(jié)論說(shuō)明了利用密文序列的任何線性運(yùn)算難以對(duì)明文序列作出有把握的估計(jì)或推斷，因而僅從利用密文單元對(duì)明文單元進(jìn)行線性估計(jì)的角度來(lái)看，該保密通信系統(tǒng)具有較為理想的安全性．同時(shí)，該結(jié)論也說(shuō)明了將不相關(guān)基本單鑰密碼系統(tǒng)用于實(shí)際保密通信時(shí)，存在某種應(yīng)用場(chǎng)合或條件，使得整個(gè)保密通信系統(tǒng)具有不相關(guān)性．

另外，在對(duì)理論安全的保密通信系統(tǒng)進(jìn)行實(shí)際模擬時(shí)，由于實(shí)際應(yīng)用中的密鑰單元序列通常只能是周期性的，尤其是常見分組密碼算法和序列密碼算法的密鑰序列的現(xiàn)有實(shí)際使用方式都是周期性的，因此，本研究所得結(jié)果在模擬常見理論安全的保密通信系統(tǒng)中將會(huì)起一定的基礎(chǔ)作用．頻率測(cè)度論的其他知識(shí)在保密通信理論安全性及其密碼算法設(shè)計(jì)中的應(yīng)用將是今后的重要研究課題．

/ References：

[1] Shannon C E．Communication theory of secrecy system[J]．Bell System Technical Journal，1949，28(4)：656-715．

[2] Zhang Zhaozhi．Basis of modern cryptography[M]．Beijing：Beijing University of Posts and Telecommunications Publishing House，2004．(in Chinese) 章照止．現(xiàn)代密碼學(xué)基礎(chǔ)[M]．北京：北京郵電大學(xué)出版社，2004．

[3] Ren Wei．Modern cryptography[M]．Beijing：Beijing University of Posts and Telecommunications Publishing House，2011．(in Chinese) 任 偉．現(xiàn)代密碼學(xué)[M]．北京：北京郵電大學(xué)出版社，2011．

[4] Konheim A G．Computer security and cryptography[M]．Tang Ming，Wang Houzhen，Han Haiqing，et al，trans．Beijing：Publishing House of Electronics Industry，2010．(in Chinese) Konheim A G．計(jì)算機(jī)安全與密碼學(xué)[M]．唐 明，王后珍，韓海清，等，譯．北京：電子工業(yè)出版社，2010．

[5] Li Shundong，Wang Daoshun．Modern cryptography：theory，method and research front[M]．Beijing：Science Press，2009．(in Chinese) 李順東，王道順．現(xiàn)代密碼學(xué)：理論、方法與研究前沿[M]．北京：科學(xué)出版社，2009．

[6] Liu Jia．Security analysis of S-boxes in symmetric ciphers[J]．Journal of Nanjing University of Information Science and Technology: Natural Science Edition，2013，5(4)：352-357．(in Chinese) 劉 佳．對(duì)稱密碼算法S盒安全性分析[J]．南京信息工程大學(xué)學(xué)報(bào)：自然科學(xué)版，2013，5(4)：352-357．

[7] Ding Wenxia，Wang Hao．Design of S-boxes based on discrete chaos system[J]. Journal of National University of Defense Technology，2013，35(1)：83-88．(in Chinese) 丁文霞，王 浩．一種基于離散混沌系統(tǒng)的S-Box候選算法設(shè)計(jì)[J]．國(guó)防科技大學(xué)學(xué)報(bào)，2013，35(1)：83-88．

[8] Wang Y，Yang L，Li M，et al．A method for designing S-box based on chaotic neural network[C]// The 6th International Conference on Natural Computation．Yantai(China)：IEEE Press，2010：1033-1037．

[9] Wang Danhui, Wang An．The efficiency of power analysis attack based on S-boxes of block ciphers[J]．Journal of Shandong University Engineering Science, 2014，44(2)：6-11． 王丹輝，王 安．針對(duì)分組密碼S盒的能量分析攻擊效率研究[J]．山東大學(xué)學(xué)報(bào)工學(xué)版，2014，44(2)：6-11．

[10] Tian Chuanjun．Frequency measure theory[M]．Beijing：Science Press，2010．(in Chinese) 田傳?。l率測(cè)度論[M]．北京：科學(xué)出版社，2010．

[11] Deni H E Du． One over one million persons will only be able to play mathematical games[M]．Kao Yonggui，Nie Yongge，trans．Beijing：Publishing House of Electronics Industry，2010．(in Chinese) 亨利·E 杜德尼．1/1 000 000的人才會(huì)做的數(shù)學(xué)游戲[M]．考永貴，聶永革，譯．北京：電子工業(yè)出版社，2010．

[12] Wu Heling．Magic square and prime number[M]．Beijing：Science Press，2008．(in Chinese) 吳鶴齡．幻方與素?cái)?shù)[M]．北京：科學(xué)出版社，2008．

[13] Li Guanlin，Gu Daquan．Research on magic square method for programmer[J]．Microcomputer Applications, 2010，26(1): 17-18．(in Chinese) 李冠林，顧大權(quán)．幻方的實(shí)現(xiàn)方法研究[J]．微型電腦應(yīng)用，2010，26(1)：17-18．

【中文責(zé)編：英 子；英文責(zé)編：雨 辰】

Frequency irrelevance and its applications in one-key cryptosystems

Tian Chuanjun?

College of Information Engineering, Shenzhen University, Shenzhen 518060, P.R.China

This paper explores applications of frequency measure theory in secrecy communication systems and studies the nonlinearity of encryption transformation in one-key cryptosystems. Aiming at the lack of normative description and strict demonstration in the theory for the nonlinearity of familiar block cipher systems, we introduce a strict mathematical definition and its implementation on nonlinear encryption transformation in general one-key cryptosystems. Based on the notion of irrelevance in the frequency measure theory, we propose a new definition called “irrelevant one-key cryptosystem” and testify to the existence of irrelevant basic one-key cryptosystems. In addition, we prove the following strong law of large numbers theoretically: sequences of message units and their corresponding cryptograph units are certainly irrelevant in probability 1 for any periodic sequence of secret keys on condition that the sequence of message units has a discrete memoryless uniform distribution during the secrecy communication process when an irrelevant basic one-key cryptosystem is used to transmit all possible messages secretly.

data security; secrecy communication system; irrelevant one-key cryptosystem; strong law of large numbers; frequency measure theory; irrelevance

：Tian Chuanjun．Frequency irrelevance and its applications in one-key cryptosystems[J]. Journal of Shenzhen University Science and Engineering, 2015, 32(1): 32-39.(in Chinese)

TN 918

A

10.3724/SP.J.1249.2015.01032

國(guó)家自然科學(xué)基金資助項(xiàng)目(61070252)

田傳俊(1964—)，男(漢族)，湖北省荊州市人，深圳大學(xué)教授．E-mail：tiancj@szu.edu.cn

Received：2014-01-15；Revised：2014-11-24；Accepted：2014-12-05

Foundation：National Natural Science Foundation of China(61070252)

? Corresponding author：Professor Tian Chuanjun．E-mail：tiancj@szu.edu.cn

引 文：田傳俊．頻率不相關(guān)性及其在單鑰密碼系統(tǒng)中的應(yīng)用[J]. 深圳大學(xué)學(xué)報(bào)理工版，2015，32(1)：32-39.