密鑰非均勻分布的完善保密通信系統

田傳俊

?

密鑰非均勻分布的完善保密通信系統

田傳俊

（深圳大學信息工程學院，廣東 深圳 518060）

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

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

1 引言

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

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

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

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

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

2 正交拉丁方組

下面先介紹正交矩陣和正交拉丁方組的相關知識[15-19]。

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

關于正交拉丁方組的存在性和數量，有如下常見結果。

3 完善密碼系統

關于保密系統的概念，Shannon在文獻[1]中曾給出了兩種略有不同的定義，分別介紹如下。

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

綜合分析可得，第一種定義更適合于通用的基本密碼系統的設計場合；而第二種定義更適合于將“基本密碼系統”大量應用于實際保密通信的場合。

任一單元的解密可表示為

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

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

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

4 基于正交拉丁方組的完善保密通信系統設計

4.1 基本密碼系統的設計

4.2 基本密碼系統的應用設計

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

利用概率論的知識，由已知條件可得

進而

證畢。

4.3 較現有完善保密性結論的優勢

現有文獻大都只是從實際應用角度出發討論了有限保密通信的完善性，甚至可以說直接受到文獻[1]的影響，文獻[7-14]基本上只討論某個基本密碼系統的完善性，具有一定的片面性。與這些現有結果相比，本文所得結果有以下幾個優點。

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

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

5 二元加法完善流密碼系統及其推廣

考慮到現在公認常用的有限完善保密通信系統是基于“模加法運算”或“仿射變換”所設計的隨機“一次一密”保密系統，下面將主要分析最常用的模2加法流密碼完善系統的幾個相關問題。

參照現有文獻和本文結論，對模2加法隨機“一次一密”無限完善保密通信系統介紹如下。

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

6 結束語

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

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

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

[2] 章照止. 現代密碼學基礎[M]. 北京: 北京郵電大學出版社, 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] 胡向東, 魏琴芳. 應用密碼學[M]. 北京: 電子工業出版社, 2006.

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

[5] 溫巧燕, 鈕心忻, 楊義先. 現代密碼學中的布爾函數[M]. 北京: 科學出版社，2000.

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

[6] 丁存生, 肖國鎮. 流密碼學及其應用[M]. 北京: 國防工業出版社, 1994.

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

[7] 魏仕民, 陳愷, 肖國鎮, 等. 關于密碼體制的完善保密性[J]. 通信學報, 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] 亢保元. 關于密碼體制的完善保密性[J]. 中南大學學報, 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] 王云光. 關于密碼體制的完善保密性[J]. 大連理工大學學報, 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] 王勇, 朱芳來. 完善保密的再認識[J]. 計算機工程, 2007, 33(19): 155-157.

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

[12] 雷鳳宇, 崔國華, 徐鵬, 等. 完善保密體制的條件和存在性證明[J]. 計算機科學, 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] 亢保元, 王育明. 完善保密密碼體制的條件與設計[J]. 通信學報, 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] 歐陽錄. 幻方與幻立方的當代理論[M]. 湖南：湖南教育出版社，2004.

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

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

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

[17] 張里千. 關于正交拉丁方的最大數目(I)[J]. 數學進展, 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]. 應用數學學報, 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] 陶照民. 偶階幻方和奇階正交拉丁方的構造方法[J]. 應用數學學報, 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] 田傳俊. 頻率不相關性及其在單鑰密碼系統中的應用[J]. 深圳大學學報，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?），男，湖北荊州人，博士，深圳大學教授，主要研究方向為偽隨機性理論及其在信息安全中的應用。

2018–01–11；

2018–06–30

國家自然科學基金資助項目（No.61070252）

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