密鑰非均勻分布的完善保密通信系統(tǒng)

田傳俊

?

密鑰非均勻分布的完善保密通信系統(tǒng)

田傳俊

（深圳大學(xué)信息工程學(xué)院，廣東 深圳 518060）

提出了理論上更加嚴(yán)格的無限完善保密性和隨機(jī)“一次一密”保密通信系統(tǒng)的概念，并將保密通信設(shè)計(jì)過程劃分為基本密碼系統(tǒng)設(shè)計(jì)及其應(yīng)用設(shè)計(jì)兩個(gè)階段。首先研究了利用正交拉丁方組設(shè)計(jì)基本密碼系統(tǒng)的問題，并舉例說明了其非線性加密變換的設(shè)計(jì)方法；然后討論了利用一類非均勻分布的隨機(jī)方法設(shè)計(jì)應(yīng)用過程中密鑰序列的問題，并在理論上嚴(yán)格證明了基于所設(shè)計(jì)的基本密碼系統(tǒng)的隨機(jī)“一次一密”無限保密通信系統(tǒng)具有完善保密性。這一成果推廣了當(dāng)前常見的基于“模加法密碼系統(tǒng)”的隨機(jī)“一次一密”完善保密通信系統(tǒng)，因而可將其作為序列密碼算法設(shè)計(jì)的一種更廣泛的理想模擬原型。由于所能設(shè)計(jì)的基本密碼系統(tǒng)的數(shù)量遠(yuǎn)超過現(xiàn)有常用方法所能設(shè)計(jì)的基本密碼系統(tǒng)的數(shù)量，因此，所得結(jié)果對(duì)當(dāng)前序列密碼算法的主流設(shè)計(jì)方法是一種有效的補(bǔ)充與完善。

單鑰密碼系統(tǒng)；完善保密性；非線性基本密碼系統(tǒng)；一次一密系統(tǒng)；正交拉丁方組

1 引言

隨著計(jì)算機(jī)科學(xué)與技術(shù)的發(fā)展，信息安全已成為當(dāng)今科學(xué)研究的重大課題之一。密碼學(xué)是信息安全領(lǐng)域中一門重要的基礎(chǔ)理論課程。在密碼學(xué)理論的發(fā)展過程中，Shannon[1]曾做出杰出貢獻(xiàn)，他于1949年創(chuàng)立了基于信息論的保密通信理論，以概率統(tǒng)計(jì)的觀點(diǎn)對(duì)消息源、密鑰源、接收和截獲消息進(jìn)行了數(shù)學(xué)描述和分析，闡明了密碼系統(tǒng)、完善保密性、理論安全性和實(shí)際安全性等一系列重要概念，從此宣告了科學(xué)的密碼學(xué)信息理論時(shí)代的到來[2]。現(xiàn)代密碼學(xué)理論將密碼系統(tǒng)或算法分為單鑰密碼系統(tǒng)和雙鑰密碼系統(tǒng)，其中，單鑰密碼系統(tǒng)又可分為序列（或流）密碼系統(tǒng)和分組密碼系統(tǒng)。

人們普遍認(rèn)為，Shannon保密通信理論誕生后在1949—1976年間基本上停滯不前。1976年，Diffie等[3]發(fā)表的論文《密碼編碼學(xué)新方向》引起了密碼學(xué)理論及其應(yīng)用上的又一次革命，影響并引領(lǐng)了之后的密碼學(xué)研究的發(fā)展方向，極大地促進(jìn)了計(jì)算復(fù)雜性理論和保密通信理論及其應(yīng)用的發(fā)展。可以說這次革命極大地促進(jìn)了Shannon理論中與實(shí)際安全性相關(guān)的保密通信理論的發(fā)展，但對(duì)理論安全性相關(guān)的保密通信理論的影響有限，因而保密通信理論中與理論安全性相關(guān)的理論及其應(yīng)用研究還有待進(jìn)一步的發(fā)展和完善。

參照微積分理論及其成功應(yīng)用的經(jīng)驗(yàn)，可以說理論研究的一個(gè)主要特點(diǎn)是需要研究無限精度的理想情形，而實(shí)際應(yīng)用研究的主要特點(diǎn)是研究以理想情形為目標(biāo)的有限精度的現(xiàn)實(shí)情形。受此啟發(fā)，首先需要明確如何描述保密通信系統(tǒng)的理想情形與實(shí)際應(yīng)用情形。Shannon在文獻(xiàn)[1]中指出保密系統(tǒng)中被加密的對(duì)象是從一個(gè)有限符號(hào)集中取出的一串離散信號(hào)，并構(gòu)成一個(gè)隨機(jī)序列或隨機(jī)過程。這樣，在考慮所有可能的一列被加密的離散符號(hào)信號(hào)時(shí)，自然會(huì)想到將大量被加密的明文信號(hào)當(dāng)作一個(gè)理想的無限隨機(jī)序列（即含無限多個(gè)離散符號(hào)），因而理論上需要研究“無限”保密通信的理想情形。毫無疑問，研究“無限”保密通信情形會(huì)比有限保密通信情形更加廣泛、全面與深刻。另一方面，在實(shí)際應(yīng)用中，所設(shè)計(jì)的保密系統(tǒng)只能是有限長(zhǎng)度的，且需要將該有限長(zhǎng)度的保密系統(tǒng)用于任意長(zhǎng)度的保密通信之中。因此，為了便于實(shí)際應(yīng)用，只能先設(shè)計(jì)出某個(gè)固定長(zhǎng)度的保密系統(tǒng)（可稱為基本保密系統(tǒng)或基本密碼系統(tǒng)），然后再反復(fù)利用該基本密碼系統(tǒng)多次地加密這個(gè)固定長(zhǎng)度的明文信號(hào)即可實(shí)現(xiàn)任何長(zhǎng)度的保密通信。下文中所說的無限保密通信是指利用一個(gè)基本密碼系統(tǒng)中無限多個(gè)明文進(jìn)行的保密通信。

為了便于理論研究和實(shí)際應(yīng)用，基于上述分析和現(xiàn)有文獻(xiàn)，可以將整個(gè)保密通信系統(tǒng)的設(shè)計(jì)過程劃分為兩個(gè)階段：1) 基本密碼系統(tǒng)設(shè)計(jì)；2) 將基本密碼系統(tǒng)應(yīng)用于所有可能的保密通信的設(shè)計(jì)，即應(yīng)用系統(tǒng)設(shè)計(jì)。基于這一觀點(diǎn)，下面先利用正交拉丁方組來設(shè)計(jì)一類基本密碼系統(tǒng)，之后再討論所設(shè)計(jì)的基本密碼系統(tǒng)的一種理想應(yīng)用設(shè)計(jì)。

需要說明的是，文獻(xiàn)[1]及其后續(xù)文獻(xiàn)[2-14]有關(guān)完善保密通信系統(tǒng)的研究基本可歸屬于有限保密通信系統(tǒng)的研究范疇。這可能是由于現(xiàn)有關(guān)于完善保密通信的研究文獻(xiàn)都只關(guān)注實(shí)際上所有可能的保密通信問題，但卻很少關(guān)注理論上所有可能的保密通信問題而造成的。在理論上，通常會(huì)認(rèn)為無限情形是有限情形的理想化推廣，其研究方法更加嚴(yán)格與深刻，因而本文研究的無限保密通信系統(tǒng)是新穎和有意義的。

2 正交拉丁方組

下面先介紹正交矩陣和正交拉丁方組的相關(guān)知識(shí)[15-19]。

為了敘述方便，將由一個(gè)拉丁方組成的集合也稱為正交拉丁方組。

關(guān)于正交拉丁方組的存在性和數(shù)量，有如下常見結(jié)果。

3 完善密碼系統(tǒng)

關(guān)于保密系統(tǒng)的概念，Shannon在文獻(xiàn)[1]中曾給出了兩種略有不同的定義，分別介紹如下。

第二種定義：在文獻(xiàn)[1]的第一部分Shannon又將保密系統(tǒng)定義為從明文集到密文集的一組可逆變換，且該可逆變換集或密鑰集具有一定的概率分布。顯然，第二種定義是在第一種定義基礎(chǔ)上增加了密鑰變換集要服從某個(gè)隨機(jī)分布這一新要素。可進(jìn)行如下直觀分析：為了防止實(shí)際保密通信受到攻擊，密鑰隨機(jī)性應(yīng)該是由將大量保密密鑰分配給不同用戶而產(chǎn)生的，而用戶群進(jìn)行保密通信的方式或頻繁程度會(huì)決定密鑰集所具有的隨機(jī)分布類型。

綜合分析可得，第一種定義更適合于通用的基本密碼系統(tǒng)的設(shè)計(jì)場(chǎng)合；而第二種定義更適合于將“基本密碼系統(tǒng)”大量應(yīng)用于實(shí)際保密通信的場(chǎng)合。

任一單元的解密可表示為

保密通信的核心問題是其安全性，為了描述保密通信的安全性，Shannon曾提出了完善保密性概念[1-3]，它可描述所截獲的密文對(duì)攻擊某段明文無任何幫助。現(xiàn)有文獻(xiàn)都只是研究了有限保密通信系統(tǒng)的完善保密性問題。因此，參照文獻(xiàn)[1-14]，可按照如下方式給出這種“有限”完善保密性概念。

根據(jù)文獻(xiàn)[1,2,4-6]，“有限”完善保密系統(tǒng)是存在的，公認(rèn)的完善保密系統(tǒng)是隨機(jī)“一次一密”（有限）保密系統(tǒng)。因此，有限完善保密通信來源于將一個(gè)基本密碼系統(tǒng)應(yīng)用于某個(gè)有限長(zhǎng)度的所有可能保密通信。但是，本文所討論的理想保密通信是所用可能的無限保密通信，因而任何一段有限明文和密文都會(huì)被認(rèn)為是從無限長(zhǎng)的明文和密文單元序列中所截取的。這樣，需要將定義3所描述的“有限完善保密性”推廣為“無限完善保密性”。因此，可以將無限完善保密性和隨機(jī)“一次一密”保密系統(tǒng)做出如下嚴(yán)格的數(shù)學(xué)表述。

顯然，定義4是將定義3中的某個(gè)有限長(zhǎng)度加強(qiáng)為任意長(zhǎng)度的明文序列與密文序列之間的相互獨(dú)立，或者形象地說，定義4是將定義3所描述的“有限完善性”理想化為“無限完善性”了，因而定義4的完善性更加嚴(yán)格。因此，下面將要證明的無限完善保密通信系統(tǒng)比現(xiàn)有有限完善保密系統(tǒng)更加嚴(yán)格，能保證該無限完善保密通信系統(tǒng)也具有有限完善保密性。

4 基于正交拉丁方組的完善保密通信系統(tǒng)設(shè)計(jì)

4.1 基本密碼系統(tǒng)的設(shè)計(jì)

4.2 基本密碼系統(tǒng)的應(yīng)用設(shè)計(jì)

將某個(gè)基本密碼系統(tǒng)用于大量實(shí)際保密通信的過程中，所遇到的明文千差萬別，因此難以完全控制明文的統(tǒng)計(jì)特性。在整個(gè)保密通信系統(tǒng)的應(yīng)用系統(tǒng)設(shè)計(jì)中，本文主要考慮密鑰單元序列的設(shè)計(jì)問題。由于完善保密性能保證密文單元序列不包含明文單元序列的任何信息，利用密文序列來攻擊明文幾乎沒有作用，因此，常將其當(dāng)成一種理想安全的保密通信系統(tǒng)。這樣，在只考慮系統(tǒng)安全性且暫時(shí)不考慮密鑰分配難度的情況下，為了保證所有可能的保密通信具有完善性，可將選取的密鑰序列設(shè)計(jì)為某種不受明文影響的理想隨機(jī)序列，得到定理1。

利用概率論的知識(shí)，由已知條件可得

進(jìn)而

證畢。

4.3 較現(xiàn)有完善保密性結(jié)論的優(yōu)勢(shì)

現(xiàn)有文獻(xiàn)大都只是從實(shí)際應(yīng)用角度出發(fā)討論了有限保密通信的完善性，甚至可以說直接受到文獻(xiàn)[1]的影響，文獻(xiàn)[7-14]基本上只討論某個(gè)基本密碼系統(tǒng)的完善性，具有一定的片面性。與這些現(xiàn)有結(jié)果相比，本文所得結(jié)果有以下幾個(gè)優(yōu)點(diǎn)。

1) 本文研究了無限保密通信系統(tǒng)的完善性，給出了更嚴(yán)格的無限保密系統(tǒng)完善性的新概念，并獲得了一類無限保密通信系統(tǒng)具有無限完善性的充分條件，該條件也可保證任一有限保密通信系統(tǒng)具有有限完善性。由此說明了本文所研究的無限保密通信系統(tǒng)的完善性是有意義和創(chuàng)新性的。

3) 本文所獲結(jié)果在不要求明文具體統(tǒng)計(jì)特性的情況下，得到了密文序列是獨(dú)立均勻分布的一種充分條件，這在更多考慮密碼系統(tǒng)的安全性時(shí)需要進(jìn)一步引入對(duì)明文均勻化處理提供了可能性。

5 二元加法完善流密碼系統(tǒng)及其推廣

考慮到現(xiàn)在公認(rèn)常用的有限完善保密通信系統(tǒng)是基于“模加法運(yùn)算”或“仿射變換”所設(shè)計(jì)的隨機(jī)“一次一密”保密系統(tǒng)，下面將主要分析最常用的模2加法流密碼完善系統(tǒng)的幾個(gè)相關(guān)問題。

參照現(xiàn)有文獻(xiàn)和本文結(jié)論，對(duì)模2加法隨機(jī)“一次一密”無限完善保密通信系統(tǒng)介紹如下。

顯然，定理2是定理1的特殊情形。考慮到隨機(jī)密鑰單元序列在實(shí)際應(yīng)用中會(huì)引起密鑰管理上的極大困難，只能將定理2作為各種實(shí)用二元序列密碼算法的理想模擬原型，具體方法通常是利用性能優(yōu)良的偽隨機(jī)密鑰序列來替代離散無記憶均勻分布隨機(jī)序列。

6 結(jié)束語

本文將現(xiàn)有有限保密通信的完善保密性和“一次一密”保密系統(tǒng)推廣為無限保密通信情形，研究了將正交拉丁方組應(yīng)用于基本密碼系統(tǒng)和無限完善保密通信系統(tǒng)之中的設(shè)計(jì)問題，并嚴(yán)格證明了所設(shè)計(jì)的隨機(jī)“一次一密”無限保密通信系統(tǒng)具有完善保密性的一種充分條件，也可保證任一有限保密通信的完善保密性。這一理論結(jié)果為序列密碼系統(tǒng)的設(shè)計(jì)提供了豐富且不同于現(xiàn)有常用的理想模擬原型，這對(duì)序列密碼算法的相關(guān)理論研究具有較為明顯的指導(dǎo)意義。

Shannon曾指出，有限完善保密系統(tǒng)在實(shí)際應(yīng)用中占有一席之地，它可能在安全性要求高和明文數(shù)量較少的場(chǎng)合中具有重要應(yīng)用[1]。由此推測(cè)，本文所研究的無限完善保密系統(tǒng)在相關(guān)的場(chǎng)合中也具有一定的實(shí)際應(yīng)用意義。從保密通信的安全性和實(shí)用性角度來看，本文所提出的多比特基本密碼系統(tǒng)設(shè)計(jì)方法可以為序列密碼算法提供一種全新且可行的設(shè)計(jì)方法，進(jìn)而有可能進(jìn)一步豐富序列密碼設(shè)計(jì)理論。

[1] SHANNON C E. Communication theory of secrecy system[J]. Bell System Technical Journal, 1949, 28（4）：656-715.

[2] 章照止. 現(xiàn)代密碼學(xué)基礎(chǔ)[M]. 北京: 北京郵電大學(xué)出版社, 2004.

ZHANG Z Z. The foundation of modern cryptography[M]. Beijing: Beijing University of Posts and Telecommunications, 2004.

[3] DIFFIE W, HELLMAN M. New directions in cryptography[J]. IEEE Trans. On Info Theory, 1976, IT-22(6)：644-654.

[4] 胡向東, 魏琴芳. 應(yīng)用密碼學(xué)[M]. 北京: 電子工業(yè)出版社, 2006.

HU X D, WEI Q F. Applied cryptography[M]. Beijing: Electronic Industry Press, 2006.

[5] 溫巧燕, 鈕心忻, 楊義先. 現(xiàn)代密碼學(xué)中的布爾函數(shù)[M]. 北京: 科學(xué)出版社，2000.

WEN Q Y, NIU X X, YANG Y X. Boolean functions in modern cryptography[M]. Beijing: Science Press, 2000.

[6] 丁存生, 肖國(guó)鎮(zhèn). 流密碼學(xué)及其應(yīng)用[M]. 北京: 國(guó)防工業(yè)出版社, 1994.

DING C S, XIAO G Z. Stream cryptography and its application[M]. Beijing: National Defense Industry Press, 1994.

[7] 魏仕民, 陳愷, 肖國(guó)鎮(zhèn), 等. 關(guān)于密碼體制的完善保密性[J]. 通信學(xué)報(bào), 2001, 22(7): 44-47.

WEI S M, CHEN K, XIAO G Z, et al. On perfect secrecy of cryptosystem[J]. Journal on Communications, 2001, 22(7): 44-47.

[8] 亢保元. 關(guān)于密碼體制的完善保密性[J]. 中南大學(xué)學(xué)報(bào), 2004, 35(3): 453-456.

KANG B Y. On perfect secrecy of cryptosystem[J]. Journal of Central South University, 2004, 35(3): 453-456.

[9] 王云光. 關(guān)于密碼體制的完善保密性[J]. 大連理工大學(xué)學(xué)報(bào), 2003, 43(S1): 69-71.

WANG Y G. Study of perfect secrecy of cryptosystem[J]. Journal of Dalian University of Technology, 2003, 43(S1): 69-71.

[10] STINSON D R. Cryptography theory and practice[M]. New York: CRC Press, 2005.

[11] 王勇, 朱芳來. 完善保密的再認(rèn)識(shí)[J]. 計(jì)算機(jī)工程, 2007, 33(19): 155-157.

WANG Y, ZHU F L. Reconsideration of perfect secrecy[J]. Computer Engineering, 2007, 33(19): 155-157.

[12] 雷鳳宇, 崔國(guó)華, 徐鵬, 等. 完善保密體制的條件和存在性證明[J]. 計(jì)算機(jī)科學(xué), 2010, 37(5): 99-102.

LEI F Y, CUI G H, XU P, et al. On the condition and the proof of the existence of perfect secrecy cryptosystem[J]. Computer Science, 2010, 37(5): 99-102.

[13] 亢保元, 王育明. 完善保密密碼體制的條件與設(shè)計(jì)[J]. 通信學(xué)報(bào), 2004, 22(7): 44-47.

KANG B Y, WANG Y M. On the condition and design of perfect secrecy cryptosystem[J]. Journal on Communications, 2004, 25(2): 44-47.

[14] JUHA P. Symmetric blind decryption with perfect secrecy[J]. Journal of Computer Networks and Communications, 2017.

[15] 歐陽(yáng)錄. 幻方與幻立方的當(dāng)代理論[M]. 湖南：湖南教育出版社，2004.

OUYANG L. The contemporary theory of magic cube and phantom cube[M]. Hunan: Hunan Education Press, 2004.

[16] 吳正聲, 孫志人. 組合數(shù)學(xué)初步[M]. 南京: 南京師范大學(xué)出版社, 2001.

WU Z S, SUN Z R. Preliminary combinatorial mathematics[M]. Nanjing: Nanjing Normal University Press, 2001.

[17] 張里千. 關(guān)于正交拉丁方的最大數(shù)目(I)[J]. 數(shù)學(xué)進(jìn)展, 1963, 6(2): 201-204.

ZHANG L Q. On the maximum number of orthogonal Latin squares (I)[J]. Advances in Mathematics, 1963, 6(2): 201-204.

[18] 李超. 用線性取余變換造正交拉丁方和幻方[J]. 應(yīng)用數(shù)學(xué)學(xué)報(bào), 1996, 19(2): 231-238.

LI C. Constructing orthogonal Latin squares and magic square by using linear congruent transformation[J]. Acta Mathematicae Applicatae Sinica, 1996, 19(2): 231-238.

[19] 陶照民. 偶階幻方和奇階正交拉丁方的構(gòu)造方法[J]. 應(yīng)用數(shù)學(xué)學(xué)報(bào), 1983, 6(3): 276-281.

TAO Z M. The general methods for constructing even order magic squares and odd order orthogonal Latin squares[J]. Acta Mathematicae Applicatae Sinica, 1983, 6(3): 276-281.

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

TIAN C J. Frequency irrelevance and its applications in one-key crypto systems[J]. Journal of Shenzhen University Science and Engineering. 2015, 32(1): 32-39.

Perfect secrecy cryptosystem with nonuniform distribution of keys

TIAN Chuanjun

College of Information Engineering, Shenzhen University, Shenzhen 518060, China

More strictly mathematical concepts of infinite perfect secrecy and random “one-time pad” cryptosystem in theory were presented, and the whole secure communication system was divided into two stages: design of a basic cryptosystem and one of its applications. How to design a basic cryptosystem by using a group of orthogonal Latin squares was first studied and an example to illustrate how to design nonlinear encryption transformations for a basic cryptosystem was given. Then, how to design the sequence of keys by using random method with nonuniform distribution was discussed,and it was strictly proven in theory that the infinite random “one-time pad” cryptosystem based on the designed basic cryptosystem was of perfect secrecy. Since the obtained result generalizes the existing one for random “one-time pad” cryptosystem to be perfect by using a basic cryptosystem with modulo addition, it may be used as a wider ideal simulated prototype to design stream cipher algorithms.Since the number of basic cryptosystems that can be designed is much more than one of the common basic cryptosystems with modulo addition, the obtained result is effective supplement and perfection to mainstream design method for the current stream cryptosystems.

single key cryptosystem, perfect secrecy, nonlinear basic cryptosystem, one-time pad cryptosystem, orthogonal Latin square

TN918

A

10.11959/j.issn.1000-436x.2018234

田傳俊（1964?），男，湖北荊州人，博士，深圳大學(xué)教授，主要研究方向?yàn)閭坞S機(jī)性理論及其在信息安全中的應(yīng)用。

2018–01–11；

2018–06–30

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

The National Natural Science Foundation of China (No.61070252)