一次一密完善保密性的实验验证方案设计
王勇
（计算机与控制学院，桂林电子科技大学，广西 桂林 541004）
E-mail：hellowy@126.com
关键词：一次一密，密码学，完善保密，概率，不可攻破
中图分类号：TP309
1. 引 言
仙农（Shannon，又译香农、申农）提出了完善保密的概念，并且证明了一次一密具有完善保密性[1, 2]。 长期以来，一次一密体制都被认为是不可攻破的，并且依然用在高安全性的加密场合，比如外交和军事中。在文献[3，4]中，从不同角度分析了一次一密并不具有完善保密性，并且指出仙农的证明存在错误。一次一密体制要具备完善保密性需要更多的条件，比如明文长度的限制，概率的限定等。通过多名编码可以使得一次一密逼近完善保密[5]。文献[6] 给出了伪装明文长度的方法。文献[7]对这一问题的根源从信息论和概率论的角度进行了分析。笔者提出的这些问题引起了一定的反响，存在一些反对意见，因此，有必要讨论这其中的验证一次一密完善保密性的实验方案存在的问题，并且笔者提出了新的实验方案，用于验证一次一密的完善保密性，为理论问题提供实验证实的依据。
2. 讨论的背景
在笔者曾经指出仙农证明一次一密完善保密时存在错误[4，7]。用一个简单的例子来说明：某一次一密体制的明文空间为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之间。此时明文的后验概率不等于明文的先验概率，所以，从反例可以看出，一次一密并不具有完善保密性，除非明文先验概率相等。
在上述例子中，考虑我们已知密文为0，则此时密文的概率是不等的，密文为0的概率为1，为1的概率为0。但是根据明文的先验概率分布，密钥是等概率随机分布的，我们可以很容易得出密文为0和为1的概率都为0.5。我们可以看到密文的概率在不同的条件下是冲突的。
在上述例子中，考虑我们的条件是已知密文为0，明文为0的先验概率为0.9，明文为1的先验概率为0.1，根据明文和密钥在此时的一一对应关系，密钥为0的概率为0.9，密钥为1的概率为0.1。而根据密码体制预先的规定，密钥是等概率的，所以，照样出现了概率冲突。
上述的这种冲突说明，在不同的条件下独自得出的概率可能是相互不一致的，需要融合，我们用局限的条件组合得出的概率各个都不能一致，需要整合起来。仙农证明的错误在于，没有考虑到这些条件不一致性和不可共存性，由于它们不能共存，所以如果我们在证明中坚持把原来的条件带入公式，就会出现错误，因为实际上这些概率经过折衷融合以后发生了改变，已经不是原来的值。实际上这种冲突在当考虑密文是一个固定的值的时候，也就是解密的情况的时候就会发生，但是这种冲突由于其隐蔽性，没有被认识到，导致得出了错误的结论。当然，如果对先验概率有另外一种理解，如果先验概率是密文是一个固定的值的情况下的明文概率，一次一密可能是完善保密的，但是，分析表明这似乎不是仙农的看法。
3. 实验方案的探讨
在讨论中，一些学者提出了反对意见，他们给出了一个实验，试图来说明一次一密具有完善保密性：假如根据明文的先验概率生成明文，然后采用随机方法等概率地生成密钥，计算出密文，由此反推不同的密文发生的情况下明文的概率，明文针对密文的条件概率等于先验概率。这种实验具有很强的隐蔽性和迷惑性，根本原因在于此时密文的概率是随机的，等概率的。而针对密文被截获的情况，我们以上面的例子为例，密文应该是确定的，比如要么只可能是0，要么只可能是1，而不是等概率地取0和1。其次，实验是有选择的，而不是任何时候生成的密文都是可以代表被截获的密文，如果我们的密文是1，密文是0的情况应当被淘汰。这种选择意味着明文或者密钥的先验概率有可能不等于明文或者密钥的概率分布。再者，此实验中先验概率就完全地决定了明文的概率，虽然条件概率有密钥参与决定。这是不严谨的，因为我们没有证实先验概率是唯一的决定因素。
一次一密每一位加密都是独立的，是否将上述的实验中的密文是1的所有位的情况进行选取就能代表密文1被截获的情况呢？其实不然，经过选取后，密钥的概率不再是原来的概率分布，与明文相关，而密钥显然不是这样精心选取的，而是随机的。这说明一个条件完全被破坏了，这种破坏是因为人为的选取密文，而不是在实验中保证密文都是1，经过选取后条件被破坏了，比如当密文是1时，如果明文是1的概率为0.1，此时密钥概率P(K=0)=0.1，同样可以得出密钥概率P(K=1)=0.9，但是密文是0时，此时密钥概率分布恰好反过来，P(K=0)=0.9， P(K=1)=0.1。虽然密钥针对不同密文的概率不是相等的，但是它们如果混合起来，恰好是互补的，使得从整体上看密钥分布满足条件，但是根据密文分类选取后，就不是等概率。可见，实验并不能满足密文被截获且确定的情况。
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（12）
Design of Experiment Scheme to Verify Perfect Secrecy of One-time pad
WANG Yong
（School of Computer and Control, Guilin University Of Electronic Technology, Guilin, 541004, Guangxi Province, China）
Abstract
The foregone experiment scheme to verify perfect secrecy of one-time pad was analyzed and it is pointed out that the experiment scheme can not ensure the two conditions that keys are equally likely and ciphertext is certain at the same time. A new imminent experiment scheme is presented. In the new imminent experiment scheme, the plaintext is randomly generated by the prior probability, key is randomly generated equiprobably, the experimental result is effective if n continual ciphertexts are all the same fixed value. Essential explanations to the problem and concrete suggestions to improve the reliability of the experiment are given.
Keywords: one-time-pad, cryptography, perfect secrecy
给出方案好像还是有同样的毛病。
[此贴子已经被作者于2007-11-18 23:17:28编辑过]
[返回] 中文XML论坛 - 专业的XML技术讨论区 →
计算机理论与工程 → 『 安全理论 』 → 一次一密完善保密性的实验验证方案设计
(订阅本版)
2007/11/18 15:04:00
新浪微博
一次一密完善保密性的实验验证方案设计
