关于一次一密完善保密证明的错误探讨

wangyong77

关于一次一密完善保密证明的错误探讨
Discussion on Mistake Concerning Perfect Secrecy of One-time-pad

王勇

（计算机与控制学院，桂林电子科技大学，广西　桂林　541004）

WANG Yong

School of Computer and Control, GuiLin University Of Electronic Technology, Guilin City, Guangxi Province , China, 541004
hellowy@126.com
摘要：本文分析了关于一次一密完善保密性的证明，指出了其错误。错误在于当利用概率论计算概率的时候，等式两边的概率的条件不一致，一些条件被忽略了。通过一个实例分析，显示了一次一密并不具有完善保密性。
关键词：一次一密，密码学，完善保密，概率，不可攻破
Abstract: This paper discusses the proofs that one-time system is perfectly secure, and points out that they are wrong. The mistakes lie in that the conditions of the probabilities are not the same in the equation and some conditions are ignored when using probability theory to compute the probabilities. An example is analyzed to show that one-time-pad is not perfectly secure.
Keywords:
one-time-pad, cryptography, perfect secrecy, probability, unbreakable
中图分类号：TP309 文献标识码：A

1.
引言仙农（香农，Shannon）提出了完善保密的概念，并且证明了一次一密具有完善保密性[1, 2]。 长期以来，一次一密体制都被认为是不可攻破的，并且依然用在高安全性的加密场合，比如外交和军事中。在文献[3，4]中，从不同角度分析了一次一密并不具有完善保密性，并且指出仙农的证明存在错误。一次一密体制要具备完善保密性需要更多的条件，比如明文长度的限制，概率的限定等。通过多名编码可以使得一次一密逼近完善保密[5]。文献[6] 给出了伪装明文长度的方法。文献[7]提出了一种基于概率计算的密码分析方法，并且用于对一次一密进行分析，虽然这种方法只能给出概率的结果，但是具有一定的理论意义。以上的分析都是直接针对仙农的证明而言的。但是仙农对于一次一密完善保密性的证明非常简单，并不详细。后人依照他的证明给出了更加详细的证明。为了进一步核实和印证一次一密并不具备完善保密性，我们来分析这些后来证明的错误。
2.
一次一密完善保密的代表性证明有许多关于一次一密具有完善保密性的证明。其中一部分直接认为明文都是等概率的，所以一次一密具有完善保密性。但是这是明显错误的，因为完善保密要求明文的先验概率等于后验概率，无论那些说法认为是明文的先验概率还是后验概率是等概率的，最终都能得出明文的先验概率是等概率的，这显然不符合事实，因为除非巧合，明文先验概率不会是等概率的。另外一类证明大同小异，代表性的证明如下：
定理：一次一密具有完善保密性。
证明：假设明文M和密文C的长度都是n比特。
那么有P(M = x｜C = y) =
P(M = xΛC = y) = P(M = x ΛK = (x⊕y))
= P(M = x)·P (K = (x⊕y)) (K独立于M)
= P(M = x) ·2-n (K是n比特长的字串中等概率选择的P (K = (x⊕y) =2-n)
又由于, P(C = y) =∑xP(M = xΛC = y)
=∑x P(M = x) ·2-n(∑x P(M = x)=1)
= 2-n。
从而密文是等概率的。
所以
P(M = x｜C = y) = = P(M = x)
一次一密具有完善保密性。

wangyong77

3.        证明的错误分析
仙农错误地利用了贝叶斯公式，同样上面的证明同样利用了贝叶斯公式。从证明中的 K独立于M 的说明和P(M = x)·P (K = (x⊕y)) = P(M = x) ·2-n, 我们可以发现在计算联合概率分布P(M = xΛC = y)时，密文是一个固定的值没有被考虑。我们可以用反证法来证明。假如对固定的密文y, P (K = (x⊕y))=2-n（注意，这是利用反证法，我们假设证明中利用的P (K = (x⊕y))=2-n是正确的，并不是笔者结论）, 由于对于固定的密文，明文和密钥具有一一对应的关系，我们可以得出 P(M = x｜C = y)= 2-n，最终根据完善保密的条件可以得出明文的先验概率P(M = x)= 2-n。但是这是明显错误的，因为明文先验概率一般不会相等。所以 P(M = x)·P (K = (x⊕y)) 代表的是当y不固定时候 x 和y 的联合概率分布。但是仙农所认为的后验概率是在密文被截获以后的概率，此时密文是一个固定的值。考虑下面等式：

P(M = x｜C = y) =
在仙农认为的P(M = x｜C = y)中，显然密文是一个固定的值。而根据证明过程中利用的条件，P(M = x｜C = y)和P(C = y)考虑的均是已知明文的先验概率，密钥等概率分布，而密文是随机不确定的情况，而不可能是一个确定的值。可见等式两边的前提都不一致，等式左边考虑的是截获密文解密时候的概率分布，而等式右边考虑的是已知明文先验概率，利用密钥加密的情况，在不同的情形下概率是不等的，所以等式并不成立。

当然，如果把P(M = x｜C = y)也考虑成是已知明文先验概率，密钥等概率分布，而密文并不是固定值的情况下的概率，等式是成立的，但是由于并不是代表密钥被截获的情况，所以并不是仙农认为的后验概率，所以不能证明一次一密具有完善保密性。

在一次一密中，有复杂和隐蔽的条件影响着明文、密钥和密文的概率。所以，有必要认识所有的条件，并且谨慎地运用概率论。在本文讨论的证明中，密文是一个固定的值（即使未知），而不上随机变量，本身是一个很重要的条件，它对明文、密钥的概率都会有影响，但是由于其隐蔽性，并没有被认识到。

4.        实例分析
以上从条件不一致的角度来分析了一次一密的证明是错误的。为了深入理解和认识错误，我们通过举例来证明一次一密并不具有完善保密性，并且从新的角度来分析错误，以便清楚了解明文概率的转变。

为了说明问题，举一个很简单的例子：明文空间为M＝{0,1}，密文空间为C＝{0,1}，密钥空间为K＝{ 0,1}，密钥等概率随机分布，采用一次一密体制进行加密。根据当时的通信语境，已知明文是0的先验概率为0.9，明文是1的先验概率为0.1。后来在这个基础上另外知道密文是0。我们仅仅考虑已知密文情况下明文的概率分布，由于密文是0，根据密钥等概率随机分布以及明文和密钥一一对应的特点，可以得出明文是0的概率为0.5，明文是1的概率为0.5，与明文的先验概率并不一致。在这样的情况下，需要将不同条件下的概率进行折衷融合，融合后，明文是0的概率介于0.5－0.9之间，明文是1的概率介于0.1－0.5之间。此时，后验概率并不等于先验概率，所以一次一密并不具有完善保密性。

wangyong77

在上述例子中，考虑我们已知密文为0，则此时密文的概率是不等的，密文为0的概率为1，为1的概率为0。但是根据明文的先验概率分布，密钥是等概率随机分布的，我们可以很容易得出密文为0和为1的概率都为0.5。我们可以看到密文的概率在不同的条件下是冲突的。

在上述例子中，考虑我们的条件是已知密文为0，明文为0的先验概率为0.9，明文为1的先验概率为0.1，根据明文和密钥在此时的一一对应关系，密钥为0的概率为0.9，密钥为1的概率为0.1。而根据密码体制预先的规定，密钥是等概率的，所以，照样出现了概率冲突。

上述的这种冲突说明，在不同的条件下独自得出的概率可能是相互不一致的，需要融合，我们用片面的条件组合得出的概率各个都不能一致，需要整合起来。仙农证明的错误在于，没有考虑到这些条件不一致性和不可共存性，由于它们不能共存，所以如果我们在证明中坚持把原来的条件带入公式，就会出现错误，因为实际上这些概率经过折衷融合以后发生了改变，已经不是原来的值。好比本来不齐脚的桌子放在水平地面上总是要翘起一个脚，如果一定要它们都着地，必然会带来一定的扭曲和改变，已经不是原来的状态了。

5.        结束语
本文进一步说明了关于一次一密具有完善保密性的证明是错误的。以上分析说明一次一密并不是完善保密的，尽管如此，它依然具有很好的密码特性和安全性。我们可以采取一些措施来增强其安全性。这一证明的错误还与概率论和信息论的局限性有关系。它们都将概率一直当作一种固定的值，而不是随机变量[8, 9]。

Reference
[1].   Bruce Schneier, Applied Cryptography Second Edition: protocols, algorithms, and source code in C[M], John Wiley &Sons, Inc, 1996.

[2].   C. E. Shannon, Communication Theory of Secrecy Systems[J], Bell System Technical journal, v.28, n. 4, 1949, 656-715.

[3].   王勇，一次一密的安全性与新保密体制[J]，信息网络安全，总第43期，2004年7月，41-43

[4].   王勇，朱芳来，完善保密的再认识，计算机工程，2007，33（19）

[5].   王勇，完善保密及其实现[J]，计算机安全，2005（05）

[6].   王勇，朱芳来，一次一密体制的安全性分析与改进，四川大学学报（工程科学版），2007，39（5）增刊:222-225

[7].   王勇，周胜源，论概率攻击，信息安全与通信保密，2007，（8）：39－40

[8].   王勇，论信息定义之舍本逐末[C]，首届全国社会信息科学研讨会论文集，2007年06月

[9].   王勇. 论概率的相对性[OL]. www.paper.edu.cn, 2007年8月27日.

广西自然科学基金项目(桂科自0640171)；现代通信国家重点实验室基金项目资助（基金号：9140C1101050706）

作者简介：王勇（1977 - ），男，讲师. 研究方向：信息安全，密码学、量子信息技术

作者简介：

王勇，男，1977年3月生，湖北天门人，桂林电子科技大学讲师，硕士，毕业于西南交通大学，研究方向：信息安全，密码学、量子信息技术。电话13978357217     E-mail:  hellowy@126.com   wang197733yong@sohu.com

WANG Yong（1977－），male，master，Hubei province tianmen city , research fields：cryptography，information security，quantum information technology。  GuiLin University Of Electronic Technology ，Guangxi, Guilin, 541004  E-mail:  hellowy@126.com   wang197733yong@sohu.com

Mobile 13978357217

通讯地址：广西省桂林市七星区金鸡路桂林电子科技大学计算机与控制学院 王勇 邮编541004