田傳俊

深圳大學(xué)電子與信息工程學(xué)院，廣東深圳518060

當(dāng)前，密碼學(xué)已成為數(shù)字信息安全領(lǐng)域的一門重要基礎(chǔ)理論，其中，SHANNON創(chuàng)立的保密通信理論是現(xiàn)代密碼學(xué)中最重要的基礎(chǔ)理論之一[1-5]．2018年，筆者對(duì)SHANNON保密通信理論的部分內(nèi)容進(jìn)行了重新解釋[6-7]，利用無(wú)限完善保密系統(tǒng)概念建立了比現(xiàn)有完善保密系統(tǒng)更一般的數(shù)學(xué)模型，豐富了實(shí)用流密碼系統(tǒng)的設(shè)計(jì)方法．文獻(xiàn)[6]將密碼算法設(shè)計(jì)分為基本密碼系統(tǒng)和應(yīng)用系統(tǒng)兩個(gè)相對(duì)獨(dú)立的設(shè)計(jì)步驟．為使整個(gè)應(yīng)用密碼(或保密通信)系統(tǒng)具有完善保密性，可利用正交拉丁方組設(shè)計(jì)相關(guān)基本密碼系統(tǒng)中的理論密鑰空間，但這會(huì)使相關(guān)的實(shí)際密鑰空間及其加解密變換的設(shè)計(jì)更加復(fù)雜．因此，研究基于拉丁方組的密鑰空間的設(shè)計(jì)方法十分必要．考慮到文獻(xiàn)[6]并未對(duì)實(shí)際基本密鑰空間與加解密變換設(shè)計(jì)進(jìn)行深入細(xì)致的研究，本研究提出基本實(shí)際密碼模型的具體設(shè)計(jì)方法，以便為設(shè)計(jì)應(yīng)用保密通信系統(tǒng)打下部分基礎(chǔ)．

常用的基本密碼系統(tǒng)都是利用1 bit明密文空間上的線性函數(shù)設(shè)計(jì)的[6-9]．因此，利用2 bit或多bit明密文空間上的非線性函數(shù)來(lái)設(shè)計(jì)基本密碼系統(tǒng)就是全新的方法，可作為序列密碼算法的重要組成部分．若將加密看成置亂編碼，則1 bit加密是標(biāo)量置亂編碼，而多bit加密是矢量置亂編碼，矢量編碼比標(biāo)量編碼要復(fù)雜得多．當(dāng)前對(duì)2 bit明密文空間上相關(guān)的多比特密鑰空間設(shè)計(jì)的研究還未充分展開(kāi)．因此，本研究擬討論一類長(zhǎng)度為2 bit或4元(明密文空間)非線性基本實(shí)際密碼模型的設(shè)計(jì)問(wèn)題，該方法易于推廣到更多bit基本密碼系統(tǒng)中．

由文獻(xiàn)[6]可知，在1 bit(明密文)空間中，現(xiàn)有流密碼系統(tǒng)常用的基本密碼系統(tǒng)，是利用一個(gè)2階拉丁方來(lái)設(shè)計(jì)其中關(guān)鍵的理論密鑰空間的，而在2 bit明密文空間中，利用4階拉丁方組可設(shè)計(jì)出更多的新基本密碼系統(tǒng)．考慮到利用4階及其以上階拉丁方組比利用2階拉丁方來(lái)設(shè)計(jì)基本密碼系統(tǒng)或其理論密鑰空間要復(fù)雜得多，本研究重點(diǎn)研究基于4階正交拉丁方組的基本實(shí)際模型設(shè)計(jì)的問(wèn)題．

1 記號(hào)和概念

參照文獻(xiàn)[6-7]，將基本密碼系統(tǒng)的理論模型表示為(M,C,T)或(M,C,T,T-1)，并將與之對(duì)應(yīng)的實(shí)際模型表示為(M,C,K,E,D)．其中，M和C為(基本)明文和密文空間；T為基本理論加密密鑰空間；K為實(shí)際密鑰空間；E為(基本)加密變換；D為解密變換．在實(shí)際應(yīng)用中，對(duì)于某個(gè)基本密碼系統(tǒng)，設(shè)計(jì)的基本理論(密碼)模型(M,C,T)和相應(yīng)的基本實(shí)際(密碼)模型(M,C,K,E,D)應(yīng)滿足如下關(guān)系：T可利用(K,E)來(lái)實(shí)現(xiàn)或表示，但T可利用多種不同形式的K和E來(lái)實(shí)現(xiàn)，逆變換T-1類似．

用小寫(xiě)字母表示基本明文和密文與實(shí)際密鑰空間的元素或單元，如m∈M， 則對(duì)明文m加密可表示為c=T(m)=E(k,m)=Ek(m)∈C， 解密也類似表示．

參照文獻(xiàn)[2-6]和計(jì)算機(jī)實(shí)際應(yīng)用現(xiàn)狀，通常將M和C設(shè)計(jì)為由某個(gè)長(zhǎng)度的(所有)不同bit(向量或序列)組成的同一個(gè)集合，因而其設(shè)計(jì)會(huì)很簡(jiǎn)單．設(shè)計(jì)基本密碼系統(tǒng)就是設(shè)計(jì)理論或?qū)嶋H密鑰空間和加解密函數(shù)．為便于應(yīng)用，K通常會(huì)被設(shè)計(jì)為一個(gè)較短消息組成的集合，而E和D會(huì)被設(shè)計(jì)為一組易于計(jì)算機(jī)實(shí)現(xiàn)的規(guī)則或運(yùn)算，且最好做到E和D相同．K最好能設(shè)計(jì)為由某個(gè)長(zhǎng)度的所有不同比特向量組成的集合，正如數(shù)據(jù)加密標(biāo)準(zhǔn)(data encryption standard, DES)算法中的實(shí)際密鑰空間是由(幾乎)所有不同的56 bit向量組成的集合一樣．

設(shè)計(jì)基本密碼系統(tǒng)的實(shí)際模型(M,C,K,E,D)要基于理論模型(M,C,T)，并利用正交拉丁方組設(shè)計(jì)該理論模型[6]．為設(shè)計(jì)出與理論模型對(duì)應(yīng)的實(shí)際模型，先解釋一下理論模型中每個(gè)理論密鑰可逆變換的表示方法和正交拉丁方組的基本知識(shí)．

(1)

需要強(qiáng)調(diào)的是，每個(gè)Z22或Zn={0,1,…,n-1}上可逆變換的函數(shù)計(jì)算式都不是唯一的，但其表格式和矩陣式都是唯一的(在不管排序的情況下)，其中，n=2,3,…． 同一個(gè)可逆變換的函數(shù)計(jì)算式形式不同，其計(jì)算量也不同．因此，在實(shí)際應(yīng)用中計(jì)算量最少或容易實(shí)現(xiàn)的計(jì)算式更會(huì)受到關(guān)注．表格式和矩陣式的唯一性有利于描述和研究變換或函數(shù)的一些本質(zhì)特性，在理論研究中具有重要作用．盡管表面上函數(shù)計(jì)算式的多樣性和靈活性會(huì)給理論研究帶來(lái)不少困惑和麻煩，但因具有適于計(jì)算機(jī)應(yīng)用等特點(diǎn)常被用于實(shí)際應(yīng)用中．同時(shí)，函數(shù)計(jì)算式的實(shí)用性也易導(dǎo)致在實(shí)用的密碼算法設(shè)計(jì)中只注重設(shè)計(jì)算法的實(shí)際模型，難見(jiàn)用“先理論模型、后實(shí)際模型”(或“理論與實(shí)際模型”并重)方法設(shè)計(jì)常用密碼算法．因此，本研究基于文獻(xiàn)[6]利用“理論與實(shí)際模型”并重的方法設(shè)計(jì)幾種新的基本密碼系統(tǒng)．

設(shè)A=(aij)n×n和B=(bij)n×n都是由數(shù)集Zn={0,1,…,n-1}中的數(shù)字構(gòu)成的n階矩陣，將A和B構(gòu)成的矩陣對(duì)(A,B)記為

(2)

下面給出拉丁方及其正交組的相關(guān)概念．

定義1設(shè)n∈{2,3,4,5,…}， 若Zn上所有不同的數(shù)字在n階方陣L的每行和每列中都出現(xiàn)，則稱L為n階拉丁方．

由定義1和定義2，可驗(yàn)證式(1)中的3個(gè)矩陣都是兩兩正交的4階拉丁方，且2階拉丁方僅兩個(gè)，但它們并不正交．為便于敘述，本研究將由一個(gè)拉丁方組成的矩陣集合稱為正交拉丁方組．

利用正交拉丁方組設(shè)計(jì)基本密碼系統(tǒng)能在理論上保證整個(gè)保密通信系統(tǒng)在一定條件下具有完善保密性[6]．不過(guò)，每個(gè)正交拉丁方組都只能用于直接設(shè)計(jì)密碼系統(tǒng)的理論密鑰變換空間，相應(yīng)的實(shí)際密鑰空間及其加解密變換的設(shè)計(jì)方法卻是復(fù)雜多樣的．下面將對(duì)這一問(wèn)題展開(kāi)研究．

2 基本實(shí)際密碼模型的設(shè)計(jì)方法

以式(1)中的正交拉丁方組所決定的理論密鑰空間為例，設(shè)計(jì)相應(yīng)的實(shí)際密鑰空間．本研究設(shè)計(jì)方法可推廣到其他類型的正交拉丁方組．

將式(1)中的3個(gè)拉丁方所決定的所有可逆變換按照從上到下、從左到右的順序依次記為{T1,T2,T3,T4}，{T5,T6,T7,T8}和{T9,T10,T11,T12}． 甚至將明文省略，則T1,T2, …,T12可用向量表示為T1=(0,3,1,2)，T2=(1,2,0,3)，…，T12=(2,3,1,0)．

利用函數(shù)計(jì)算式表示上述可逆變換．對(duì)任意m1，m2∈Z2和m=m1m2∈Z22， 可逆變換T1為

(3)

采用類似方法，可得其他可逆變換的代數(shù)式為

c=T2(m)=(m2×m-m1+1)mod 4

c=T3(m)= (m2×m-m1+3)mod 4

c=T5(m)= (m2m1+3)mod 4

c=T6(m)= (m+m1+m2+2)mod 4

c=T7(m)= (m+m1+m2)mod 4

c=T8(m)= (m2m1+1)mod 4

c=T10(m)=[(2×m2-1) ×m1+m2]mod 4

c=T12(m)=(m2×m-m1+2)mod 4

需要注意的是，對(duì)任意x,y∈Z2，xy和x×y意義并不相同．可見(jiàn)，式(1)中的每個(gè)拉丁方都可利用“非統(tǒng)一形式”的非線性代數(shù)計(jì)算式表示．

按照上述方式，Z22中的每個(gè)可逆變換都能利用代數(shù)式表示，在此不再贅述．不過(guò)，3 bit或4 bit等所確定的集合Z8或Z16等的所有可逆變換或拉丁方數(shù)量會(huì)非常多，難以全部列舉，導(dǎo)致相關(guān)代數(shù)式也難以全部列出．Z22中每個(gè)可逆變換或拉丁方實(shí)際中都能明確寫(xiě)出其代數(shù)式的特點(diǎn)會(huì)在理論密鑰變換空間設(shè)計(jì)時(shí)發(fā)揮特殊作用．

然后，考慮基本實(shí)際密鑰空間K和加解密函數(shù)E與D的設(shè)計(jì)．與1 bit基本密碼系統(tǒng)的密鑰空間具有唯一性不同，2 bit基本密碼系統(tǒng)的密鑰空間呈多樣性，且密鑰數(shù)量隨正交拉丁方組數(shù)量的變化而變化．若與應(yīng)用密鑰流序列空間特性結(jié)合，還能提出新的研究方向．下面將詳述把K設(shè)計(jì)為長(zhǎng)度為2、3和4 bit時(shí)的設(shè)計(jì)方法．

2.1 基本實(shí)際密碼系統(tǒng)實(shí)際密鑰空間K1由2 bit組成

T11(m)+(k1∧k2)×T12(m)]mod 4

(4)

2)基本解密變換D1： 對(duì)任一密文c=c1c2∈Z22和密鑰k=k1k2∈Z22， 其中，c1,c2，k1,k2∈Z2， 將D1設(shè)計(jì)為

(5)

2.2 基本實(shí)際密碼系統(tǒng)實(shí)際密鑰空間K2由3 bit組成

1) 加密變換E2： 對(duì)任一2 bit明文m=m1m2∈Z22和任意3 bit密鑰k=k1k2k3∈Z2， 其中，m1,m2,k1,k2,k3∈Z2， 將E2設(shè)計(jì)為

(k1∧k2∧k3)×T8(m)]mod 4

(6)

2)解密變換D2： 對(duì)任一2 bit密文c=c1c2∈Z22和任意3 bit密鑰k=k1k2k3∈Z23， 其中，c1,c2,k1,k2,k3∈Z2， 將D2設(shè)計(jì)為

(k1∧k2∧k3)×T3(c)+

(7)

2.3 實(shí)際基本密碼系統(tǒng)實(shí)際密鑰空間K3由4 bit組成

1)加密函數(shù)E3： 對(duì)任一2 bit明文m=m1m2∈Z22和任意4 bit密鑰k=k1k2k3k4∈Z24， 其中，m1,m2,k1,k2,k3,k4∈Z2， 可利用如下統(tǒng)一代數(shù)式將加密變換c=E3(k,m)設(shè)計(jì)為

(8)

由式(8)可見(jiàn)，只要調(diào)整好各自的應(yīng)用密鑰流序列的統(tǒng)計(jì)特性，利用有重復(fù)和無(wú)重復(fù)拉丁方組所設(shè)計(jì)的基本密碼系統(tǒng)構(gòu)造出的兩種保密通信系統(tǒng)就會(huì)是等價(jià)的．

2)解密函數(shù)D3： 對(duì)任一2 bit密文c=c1c2∈Z22和任意4 bit密鑰k=k1k2k3k4∈Z24， 其中，c1,c2,k1,k2,k3,k4∈Z2， 可將解密變換m=D3(k,c)設(shè)計(jì)為

(9)

上述3種2 bit(明密文空間)基本密碼系統(tǒng)都是非線性的[6]，而重復(fù)利用2次常見(jiàn)的逐個(gè)bit異或運(yùn)算所設(shè)計(jì)的2 bit基本密碼系統(tǒng)是線性的，因而可認(rèn)為利用這3種非線性新基本密碼系統(tǒng)來(lái)設(shè)計(jì)流密碼算法將完全不同于現(xiàn)有常見(jiàn)的流密碼算法，且(加解密或被攻擊或破解的)計(jì)算量會(huì)更大．

為說(shuō)明上述基本密碼系統(tǒng)能用于設(shè)計(jì)完整的流密碼算法，結(jié)合JK觸發(fā)器所產(chǎn)生的密鑰流序列設(shè)計(jì)了一個(gè)簡(jiǎn)單流密碼算法，對(duì)1個(gè)短英文文本文件進(jìn)行加密，得到的加密文件為亂碼．算法代碼、原文件及加密文件請(qǐng)掃描論文末頁(yè)右下角二維碼查看圖S1、S2和S3．

結(jié) 語(yǔ)

本研究基于文獻(xiàn)[6]，利用1個(gè)4階正交拉丁方組設(shè)計(jì)3種不同的4元或2 bit(明密文空間)非線性基本密碼系統(tǒng)．本研究具有以下特點(diǎn)：

1)在現(xiàn)有流密碼算法中，通常采用標(biāo)量置亂編碼方式的模2加法線性基本密碼系統(tǒng)，它等價(jià)于利用2階正交拉丁方設(shè)計(jì)基本密碼系統(tǒng)，該方法的單一性決定了現(xiàn)有基本密碼系統(tǒng)的研究缺乏技巧性和豐富性．本研究利用矢量置亂編碼方式的4階正交拉丁方組設(shè)計(jì)基本密碼系統(tǒng)，高階正交拉丁方組及其代數(shù)式構(gòu)造靈活多樣，豐富了基本密碼系統(tǒng)的設(shè)計(jì)方法．

2)所提出4階正交拉丁方組的非統(tǒng)一代數(shù)計(jì)算式構(gòu)造方法，有利于推廣到更高階拉丁方組的構(gòu)造上．通過(guò)對(duì)拉丁方組所決定的理論密鑰變換進(jìn)行統(tǒng)一的代數(shù)式設(shè)計(jì)，建立3種基本密碼系統(tǒng)的實(shí)際模型，可用于新的序列密碼算法設(shè)計(jì)．這種綜合考慮基本密碼系統(tǒng)理論模型和實(shí)際模型的設(shè)計(jì)方法，可為現(xiàn)有序列密碼算法設(shè)計(jì)提供參考．利用理論密鑰變換更利于分析密鑰變換的性能，而利用實(shí)際密鑰及其加密變換更利于在計(jì)算機(jī)實(shí)現(xiàn)．因此，理論與實(shí)際密碼模型并重的設(shè)計(jì)方法對(duì)單鑰密碼算法設(shè)計(jì)都具有啟發(fā)意義．

綜上，4階拉丁方組的構(gòu)造方法對(duì)高階拉丁方組的構(gòu)造具有一定的指導(dǎo)作用，有利于進(jìn)一步研究設(shè)計(jì)基本密碼系統(tǒng)及其流密碼系統(tǒng)．