一次一密完善保密性的信息理论证明的错误分析
王勇
（计算机与控制学院，桂林电子科技大学，广西 桂林 541004）
E-mail：hellowy@126.com
摘 要：分析了关于一次一密完善保密性的信息理论证明，指出了信息理论并不适合证明一次一密是完善保密的，且一次一密并不具有完善保密性。问题关键在于不同条件下的值被混淆，且密文是一个固定的值这一条件被忽视了。同时指出类似的错误可能在应用信息理论证明其他的定理的时候发生。
关键词：一次一密，密码学，完善保密，概率，不可攻破
中图分类号：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 一次一密的完善保密性
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)，因而要严格区分这两种情况，而不能混淆。
为了进一步认识这种概率的冲突和信息融合的必要性，我们可以做如下分析：
在上述一次一密的例子中，考虑我们已知密文为0，则此时密文的概率是不等的，密文为0的概率为1，为1的概率为0。但是根据明文的先验概率分布，密钥是等概率随机分布的，我们可以很容易得出密文为0和为1的概率都为0.5。我们可以看到密文的概率在不同的条件下是冲突的。
同样考虑我们的条件是已知密文为0，明文为0的先验概率为0.9，明文为1的先验概率为0.1，根据明文和密钥在此时的一一对应关系，密钥为0的概率为0.9，密钥为1的概率为0.1。而根据密码体制预先的规定，密钥是等概率的，所以，照样出现了概率冲突。
上述的这种冲突说明，在不同的条件下独自得出的概率可能是相互不一致的，需要融合，我们用片面的条件组合得出的各个概率都不能一致，需要整合起来。仙农证明的错误在于，没有考虑到这些条件不一致性和不可共存性，由于它们不能共存，所以如果我们在证明中坚持把原来的条件带入公式，就会出现错误，因为实际上这些概率经过折衷融合以后发生了改变，已经不是原来的值。好比本来不齐脚的桌子放在水平地面上总是要翘起一个脚，如果一定要它们都着地，必然会带来一定的扭曲和改变，已经不是原来的状态了。
以上的证明中的各种值，比如熵，条件熵和联合概率分布应当是在相同的条件下，比如要么是加密的情况，密文是随机的，要么是密文是固定的情况下。以上证明应当是分析的加密的情况，只有在这一条件下，各种值才能轻易得出，如果是考虑密文是固定值的情况，将会非常的复杂。但是要得出完善保密，我们的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
Yong WANG, Security of One-time System and New Secure System [J], Netinfo Security, 2004, (7):41-43
[4]. 王勇，朱芳来，完善保密的再认识，计算机工程，2007，33（19） Yong WANG, Fanglai ZHU, Reconsideration of Perfect Secrecy, Computer Engineering, 2007, 33（19）
[5]. 王勇，完善保密及其实现[J]，计算机安全，2005（05）Yong WANG, Perfect Secrecy and Its Implement [J],Network & Computer Security,2005(05)
[6]. 王勇，朱芳来，一次一密体制的安全性分析与改进，四川大学学报（工程科学版），2007，39（5）增刊:222-225 Yong WANG, Fanglai ZHU, Security Analysis of One-time System and Its Betterment, Journal of Sichuan University (Engineering Science Edition), 2007, supp. 39(5):222-225
[7]. 王勇，周胜源，论概率攻击，信息安全与通信保密，2007，（8）：39－40 Yong WANG, Shengyuan Zhou, On Probability Attack, Information Security and Communications Privacy, 2007,(8)：39－40
[8]. Yong WANG, Confirmation of Shannon's Mistake about Perfect Secrecy of One-time-pad, http://arxiv.org/abs/0709.4420
[9]. Yong WANG, Mistake Analyses on Proof about Perfect Secrecy of One-time-pad, http://arxiv.org/abs/0709.3334
[10]. Massey, J.L., An introduction to contemporary cryptology, Proceedings of the IEEE, 1988,76 (5):533 - 549
[11]. Raymond W. Yeung, A First Course in Information Theory, Springer, 2002: 116
Mistake Analysis on the Information-Theoretic Proof about Perfect Sec
[返回] 计算机科学论坛 →
计算机理论与工程 → 『 安全理论 』 → 一次一密完善保密性的信息理论证明的错误分析
(订阅本版)
2007/11/6 16:20:00
新浪微博
一次一密完善保密性的信息理论证明的错误分析
