密钥非均匀分布的完善保密通信系统

田传俊



密钥非均匀分布的完善保密通信系统

田传俊

（深圳大学信息工程学院，广东 深圳 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)