一次一密完善保密性的信息理论证明的错误分析1
王勇
桂林电子科技大学计算机与控制学院，广西桂林（541004）圣诞快来了
E-mail：
写植物的日记
摘要：分析了关于一次一密完善保密性的信息理论证明，指出了信息理论并不适合证明一次一密是完善保密的，且一次一密并不具有完善保密性。问题关键在于不同条件下的值被混淆，且密文是一个固定的值这一条件被忽视了。同时指出类似的错误可能在应用信息理论证明其他的定理的时候发生。
关键词：一次一密，密码学，完善保密，概率，不可攻破
中图分类号：TP309
1.引言
留学需要具备哪些条件
仙农（Shannon，又译香农、申农）提出了完善保密的概念，并且证明了一次一密具有完善保密性[1, 2]。长期以来，一次一密体制都被认为是不可攻破的，并且依然用在高安全性的加密场合，比如外交和
军事中。在文献[3，4]中，从不同角度分析了一次一密并不具有完善保密性，并且指出仙农的证明存在错误。一次一密体制要具备完善保密性需要更多的条件，比如明文长度的限制，概率的限定等。通过多名编码可以使得一次一密逼近完善保密[5]。文献[6]给出了伪装明文长度的方法。文献[7]提出了一种基于概率计算的密码分析方法，并且用于对一次一密进行分析，虽然这种方法只能给出概率的结果，但是具有一定的理论意义。文献[4]中考虑了一种特殊的情况，在这样的认识下，明文长度都是一致的情况下，一次一密可以认为是完善保密的，文章分析这种认识可能性不大，但是文献[8]进一步确定不是仙农的观点。由于仙农的证明太简单，更加严谨的证明是后人给出的，文献[9] 分析这种更加严谨的证明，同时指出了它的错误所在。本文针对从信息理论角度证明一次一密是完善保密的证明进行分析，并且指出其中的错误。
2.一次一密的完善保密性的信息理论证明
挂灯笼一次一密的完善保密性的证明绝大多数都是基于概率论的，包括仙农最初提出的证明，也有学者从信息理论的角度提供了证明，这类证明在一些教材和讲义中，有些不是很清晰[10，11]。下面就是代表性的证明：
定理：一次一密具有完善保密性。
证明：假设明文、密钥和密文分别是M，K和C。它们的长度都是n比特。证明过程如图1示。
由于明文、密文和密钥中的两个都可以决定第三者，所以有H(K|MC) = 0，H(M|CK) = 0 和H(C|MK) = 0. N是密钥长度, 所以有H(K) = N。M和K是独立的，所以有I(M; K) = 0.
I(K; C|M) = H(K)－I(M; K)－H(K|CM) = N, 又由于H(Y) ≤log2 |Y| = N，所以有I(M; C) = 0。
I(M; C) = 0代表密文对明文不提供任何信息，所以一次一密具有完善保密性。
证明完毕。
1本课题得到广西自然科学基金项目(桂科自0640171)；现代通信国家重点实验室基金项目（基金号：9140C1101050706）的资助。
图1 一次一密的完善保密性
3.证明的错误分析
证明是基于信息论，所以我们从信息论的角度来分析问题。我们可以从仙农的条件熵的公式和证明过程中看出，条件熵是在某种固定的联合概率分布情况下得出的，所以在以上的证明中，所有的熵和条件熵都应当是在该固定的联合概率分布下的值，也可以说是在同一个条件下的值。但是，实际上以上的证明正是将不同条件下的概率混淆了。我们已经指出过，在一次一密中，有隐蔽的条件影响明文、密钥和密文的概率分布。但是在本证明中，没有意识到密文是一个固定（即使是未知的）的值，而不是随机变量这一隐蔽条件对概率的影响。可能有人认为密文的值是一个固定的值没有必要独立地拿出来作为一个条件，我们可以进行以下的分析：在一次一密中，当我们考虑加密的情形时，密文是一个随机变量，在这种认可密文是随机变量的情况下，密文的值可以是无数的。此时，密文有什么可能的值都不能确定，更不能确定相应的概率分布，但是，假如我们将密文的值设定为固定的值，可能值就是有限的，也很容易计算。当我们考虑密文被截获的情形时，密文是一个固定的值，所以很适合增加一个明文是固定的值的条件。我们通过举例来说明密文是一个固定的值这一条件对明文和密钥概率分布的影响，从而影响相应的熵。下面是一个一次一密的简单例子：一次一密的明文、密钥和密文空间都是{0,1}，密钥等概率分布。事先得到明文的先验概率为P(M=0) = 0.9，P(M=1) = 0.1，所以在加密的情形下，明文的概率为P(M=0) = 0.9，P(M=1) = 0.1，而密文是等概率的随机变量。当我们仅仅考
虑密文是一个固定的值（即使不知道是0还是1）并且密钥等概率，此时由于可以解密，密钥和明文具有一一对应的关系，这种对应使得对应的密钥和明文的概率是相等的，由于密钥都是等概率的，所以明文也是等概率的。这种条件下P(M=0) = 0.5，P(M=1) = 0.5，这一概率显然和先验的概率分布不一致。可见，在同时考虑密文是确定的值，明文的先验概率以及密钥是等概率的情况下，我们需要将上面的两组概率进行折衷，最终的结果是明文等于0的概率介于0.9-0.5之间，明文等于1的概率介于0.1-0.5之间。由于无论对于密文是0还是1，都有最终的概率是明文等于0的概率介于0.9-0.5之间，明文等于1的概率介于0.1-0.5之间，综合考虑明文在密文是确定的情况下的最终的概率也是在两组概率之间，很明显此时明文的概率和先验概率相比较就发生了改变，同样，针对密文被截获的情况，明文的概率和先验概率相比较也发生了改变，因而一次一密不是完善保密的。以上分析可以看出明文、密钥和密文的各种概率分布及联合概率分布在加密的情况和考虑密文是一个固定值（解密的情况）的情况下是不完全一样的，所以，在图1中，某些值在两种情况下是不一样的，比如H(M)，因而要严格区分这两种情况，而不能混淆。
以上的证明中的各种值，比如熵，条件熵和联合概率分布应当是在相同的条件下，比如
要么是加密的情况，密文是随机的，要么是密文是固定的情况下。以上证明应当是分析的加
密的情况，只有在这一条件下，各种值才能轻易得出，如果是考虑密文是固定值的情况，将
会非常的复杂。但是要得出完善保密，我们的M当然是最初的加密的情况，密文是随机的，而C显然是在密文被截获，即密文是固定值的情况。而以上证明中I(M; C) = 0的M和C应
该是在相同的条件下的，所以以上的证明并不能够保证一次一密具有完善保密性。原因在于
密文是一个固定的值这一条件有时候被无意识地用了，有时候被忽略了，从而导致了混淆和
错误。
可能有人会认为M的先验概率可以是在密文是固定值情况下的概率，从而以上证明是
在该条件下得出的。实际上根据相关的一些证明和背景可以看出并不是仙农的观点，这一点
我们在文献[8]中进行了详细分析。在文献[9]中提供的证明也显示这并不是密码学家和密码
学界的看法。
4.结束语
由于在一次一密中，有复杂和隐蔽的条件影响着明文、密钥和密文的概率，加之，概率
论和信息论本身也具有一定局限性，导致了一些错误的产生，这并不能怪一些专家，这种情
况下错误本身难免。本文分析了关于一次一密是完善保密的信息理论证明中的错误，尽管一
次一密并不是完善保密的，但是它依然具有很好的密码性质，完善保密是一种过于苛刻的条件，所以不具备完善保密并不说明很大的问题。本证明中出现的问题可能也会出现在信息论
的其他应用中，特别是涉及到密码学的应用中。
参考文献
[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].Yong WANG, Confirmation of Shannon's Mistake about Perfect Secrecy of One-time-pad,
小猪奴尼arxiv/abs/0709.4420姓氏的英文>描写螳螂的作文
[9].Yong WANG, Mistake Analys on Proof about Perfect Secrecy of One-time-pad,
arxiv/abs/0709.3334
[10].Masy, J.L., An introduction to contemporary cryptology, Proceedings of the IEEE, 1988,76 (5):533 - 549
[11].Raymond W. Yeung, A First Cour in Information Theory, Springer, 2002: 116
Mistake Analysis on the Information-Theoretic Proof about白茶的好处和功效
Perfect Secrecy of OTP
Wang Yong
School of Computer and Control，Guilin University Of Electronic Technology，Guilin，Guangxi
（541004）
Abstract
This paper analyzes the information-theoretic proofs about perfect crecy of OPT and points out that information theory is not proper to prove that OPT is perfectly cure and OPT is not perfectly cure. The sticking point lies in the values under different conditions are confud and the condition that ciphertext is fixed is not considered. It is also pointed out that the similar mistake may take place when information theory is ud to prove other theorems.
Keywords：one-time-pad，cryptography，perfect crecy，probability，unbreakable
作者简介：王勇，男，1977年3月生，湖北天门人，桂林电子科技大学讲师，硕士，毕业于西南交通大学，研究方向为信息安全，密码学、量子信息技术
