基于4階正交拉丁方組實(shí)際基本密碼系統(tǒng)設(shè)計(jì)

田傳俊

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

當(dāng)前，密碼學(xué)已成為數(shù)字信息安全領(lǐng)域的一門重要基礎(chǔ)理論，其中，SHANNON創(chuàng)立的保密通信理論是現(xiàn)代密碼學(xué)中最重要的基礎(chǔ)理論之一[1-5]．2018年，筆者對SHANNON保密通信理論的部分內(nèi)容進(jìn)行了重新解釋[6-7]，利用無限完善保密系統(tǒng)概念建立了比現(xiàn)有完善保密系統(tǒng)更一般的數(shù)學(xué)模型，豐富了實(shí)用流密碼系統(tǒng)的設(shè)計(jì)方法．文獻(xiàn)[6]將密碼算法設(shè)計(jì)分為基本密碼系統(tǒng)和應(yīng)用系統(tǒng)兩個相對獨(dú)立的設(shè)計(jì)步驟．為使整個應(yīng)用密碼(或保密通信)系統(tǒng)具有完善保密性，可利用正交拉丁方組設(shè)計(jì)相關(guān)基本密碼系統(tǒng)中的理論密鑰空間，但這會使相關(guān)的實(shí)際密鑰空間及其加解密變換的設(shè)計(jì)更加復(fù)雜．因此，研究基于拉丁方組的密鑰空間的設(shè)計(jì)方法十分必要．考慮到文獻(xiàn)[6]并未對實(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ù)來設(shè)計(jì)基本密碼系統(tǒng)就是全新的方法，可作為序列密碼算法的重要組成部分．若將加密看成置亂編碼，則1 bit加密是標(biāo)量置亂編碼，而多bit加密是矢量置亂編碼，矢量編碼比標(biāo)量編碼要復(fù)雜得多．當(dāng)前對2 bit明密文空間上相關(guān)的多比特密鑰空間設(shè)計(jì)的研究還未充分展開．因此，本研究擬討論一類長度為2 bit或4元(明密文空間)非線性基本實(shí)際密碼模型的設(shè)計(jì)問題，該方法易于推廣到更多bit基本密碼系統(tǒng)中．

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

1 記號和概念

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

用小寫字母表示基本明文和密文與實(shí)際密鑰空間的元素或單元，如m∈M， 則對明文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ì)為由某個長度的(所有)不同bit(向量或序列)組成的同一個集合，因而其設(shè)計(jì)會很簡單．設(shè)計(jì)基本密碼系統(tǒng)就是設(shè)計(jì)理論或?qū)嶋H密鑰空間和加解密函數(shù)．為便于應(yīng)用，K通常會被設(shè)計(jì)為一個較短消息組成的集合，而E和D會被設(shè)計(jì)為一組易于計(jì)算機(jī)實(shí)現(xiàn)的規(guī)則或運(yùn)算，且最好做到E和D相同．K最好能設(shè)計(jì)為由某個長度的所有不同比特向量組成的集合，正如數(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ì)出與理論模型對應(yīng)的實(shí)際模型，先解釋一下理論模型中每個理論密鑰可逆變換的表示方法和正交拉丁方組的基本知識．

(1)

需要強(qiáng)調(diào)的是，每個Z22或Zn={0,1,…,n-1}上可逆變換的函數(shù)計(jì)算式都不是唯一的，但其表格式和矩陣式都是唯一的(在不管排序的情況下)，其中，n=2,3,…． 同一個可逆變換的函數(shù)計(jì)算式形式不同，其計(jì)算量也不同．因此，在實(shí)際應(yīng)用中計(jì)算量最少或容易實(shí)現(xiàn)的計(jì)算式更會受到關(guān)注．表格式和矩陣式的唯一性有利于描述和研究變換或函數(shù)的一些本質(zhì)特性，在理論研究中具有重要作用．盡管表面上函數(shù)計(jì)算式的多樣性和靈活性會給理論研究帶來不少困惑和麻煩，但因具有適于計(jì)算機(jī)應(yīng)用等特點(diǎn)常被用于實(shí)際應(yīng)用中．同時，函數(shù)計(jì)算式的實(shí)用性也易導(dǎo)致在實(shí)用的密碼算法設(shè)計(jì)中只注重設(shè)計(jì)算法的實(shí)際模型，難見用“先理論模型、后實(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)成的矩陣對(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個矩陣都是兩兩正交的4階拉丁方，且2階拉丁方僅兩個，但它們并不正交．為便于敘述，本研究將由一個拉丁方組成的矩陣集合稱為正交拉丁方組．

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

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

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

將式(1)中的3個拉丁方所決定的所有可逆變換按照從上到下、從左到右的順序依次記為{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ì)算式表示上述可逆變換．對任意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

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

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

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

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

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

(4)

2)基本解密變換D1： 對任一密文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： 對任一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： 對任一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： 對任一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)可見，只要調(diào)整好各自的應(yīng)用密鑰流序列的統(tǒng)計(jì)特性，利用有重復(fù)和無重復(fù)拉丁方組所設(shè)計(jì)的基本密碼系統(tǒng)構(gòu)造出的兩種保密通信系統(tǒng)就會是等價的．

2)解密函數(shù)D3： 對任一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次常見的逐個bit異或運(yùn)算所設(shè)計(jì)的2 bit基本密碼系統(tǒng)是線性的，因而可認(rèn)為利用這3種非線性新基本密碼系統(tǒng)來設(shè)計(jì)流密碼算法將完全不同于現(xiàn)有常見的流密碼算法，且(加解密或被攻擊或破解的)計(jì)算量會更大．

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

結(jié) 語

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

1)在現(xiàn)有流密碼算法中，通常采用標(biāo)量置亂編碼方式的模2加法線性基本密碼系統(tǒng)，它等價于利用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)造上．通過對拉丁方組所決定的理論密鑰變換進(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ì)方法對單鑰密碼算法設(shè)計(jì)都具有啟發(fā)意義．

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