仙农关于一次一密完善保密性的错误确定与分析

wangyong77

仙农关于一次一密完善保密性的错误确定与分析

王勇

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

WANG Yong

（School of Computer and Control, GuiLin University Of Electronic Technology，Guilin, 541004, Guangxi Province, China）

摘要：本文分析了仙农在论证一次一密体制完善保密过程中的一些可能性，并且确认了仙农的错误。从信息论和概率论的角度分析了错误的根源，指出概率往往具有随机不确定性，概率论往往忽视概率的这种随机不确定性。信息论没有考虑信息的可靠性和多重随机不确定性，这使得信息论在现实中的应用存在局限性。
关键词： 一次一密体制；密码学；完善保密；信息论
Confirmation and Analyses of Shannon’s Mistake about Perfect Secrecy of One-time System
Abstract: Through analyzing some possibilities in Shannon’s proof that one-time system is perfectly secure, this paper confirms Shannon’s mistake. And the root of the mistake is pointed out from the angles of information theory and probability theory because the probability theory alwayes ignores the random uncertainty of probability itself and the information theory has its limitation in application due to ignoring the unreliability and multiple random uncertainty of information.
Keywords:
one-time system, cryptography, perfect secrecy, information theory
中图分类号：TP309 文献标识码：A
仙农（Shannon，又译香农、申农）提出了完善保密的概念并且证明一次一密密码体制（简称一次一密体制）具有完善保密性[1，2]。完善保密的密码体制被认为是不可攻破的[1]。长久以来，一次一密密码体制被认为是不可攻破的，除了它泄漏和限制明文的长度外，其安全性没有受到其他质疑，并且它至今依然应用在高度保密的信息传输中。最近的文献[3，4]指出了一次一密体制并非完善保密的，文献[5]论证了一次一密体制完善保密需要具备的条件，并且利用多名编码来让密码体制逼进完善保密。文献[6]分析了一次一密体制完善保密时需要增加的条件，并且提出了一些伪装明文长度的方法。文献[7]则从概率的角度提出了一种密码分析方法，这种分析方法可以用于对一次一密体制实施一种不是很奏效的攻击。文献[4]还考虑了一种非常特殊的可能性，这种情况下满足特殊的情况，一次一密才可能具有完善保密性。而本文对一次一密体制的完善保密性的证明进行了深入的分析，并且确定这种可能性并非仙农的想法，从而，即使在考虑明文长度必须一致的限制的情况下，一次一密体制也并不如仙农认为的那样具有完善保密性。
1.一次一密体制完善保密性错误的确定我们姑且不考虑一次一密体制所有的明文和密文必须都是等长度的限制问题，实际上，仙农的证明中也隐含了这一条件，但是仙农并没有把这一条件在结论中明确指出。在这里的讨论中，我们假设所有的明文都是等长度的，密文和密钥的长度也是等于该长度。
为了说明问题，举一个很简单的例子：明文空间为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。而根据密码体制预先的规定，密钥是等概率的，所以，照样出现了概率冲突。
上述的这种冲突说明，在不同的条件下独自得出的概率可能是相互不一致的，需要融合，我们用局限的条件组合得出的概率各个都不能一致，需要整合起来。仙农证明的错误在于，没有考虑到这些条件不一致性和不可共存性，由于它们不能共存，所以如果我们在证明中坚持把原来的条件带入公式，就会出现错误，因为实际上这些概率经过折衷融合以后发生了改变，已经不是原来的值。
在上述的例子中，有几个条件，比如明文被发送的概率，这个概率是根据通信语境等非密码体制的信息作为条件来决定的。密码体制的信息，比如采用一次一密体制，密钥等概率的信息。密文是一个确定的值。密文的值是某一个值C。此外，这些条件组合也会得出不同的概率。
以求明文的概率而言，有以下几种不同的条件可以得出明文的概率：
（1）
以明文的通信语境等信息为条件，在本例子中，明文是0的概率为0.9，明文是1的概率为0.1。
（2）
以密码体制的信息，加上密文是未知，但是却是确定的值为条件（密文可能不知道，但是密文不是随机变量，是确定的值），可以很容易得出明文是等概率的。
（3）
以密码体制的信息，加上密文是某一个已知的值为条件（针对已经获得密文的情况），同样可以很容易得出明文是等概率的。
（4）
以明文的通信语境等信息，加上密码体制信息为条件，但是此时密文的值不是确定的，明文是0的先验概率为0.9，明文是1的先验概率为0.1。
（5）
以明文的通信语境等信息，加上密码体制信息，以及密文的值为未知，但是是确定的值为条件，明文是0的概率介于0.5－0.9之间，明文是1的概率介于0.1－0.5之间。
（6）
以明文的通信语境等信息，加上密码体制信息，以及密文的值为某一个已知的值为条件，明文是0的概率介于0.5－0.9之间，明文是1的概率介于0.1－0.5之间。
后验概率是条件概率，是根据某种条件得出的，实际上先验概率也是依据某种条件和依据得出的。由于这里条件繁多，有多个先后关系，用先验概率和后验概率不能称谓所有的概率，所以我们用已知条件来称谓对应的概率更加确切。仙农在定义明文先验概率的时候，并没有很好地确定其条件是什么，而实际上先验概率可能是（1）、（4）、（5）之一。已知密文后的后验概率可能是（3）、（6）之一。 文献[8]则考虑到（5）的情形，假如仙农的先验概率考虑的是（5）的情形，后验概率考虑的是（6）的情形，则先验概率可能等于后验概率。

wangyong77

假如是上面的先验概率等于后验概率的情形，则仙农应当有信息融合的概念，并且能够区分以上各种不同的条件，在定义中加以明确。但是，仙农一直没有提起过信息融合的问题，而且这个信息融合的算法在当时还没有，要计算它都没有可行的算法，因此，仙农考虑此种情形的可能性不大。仙农一向以概率不改变来定义完善保密，即使我们考虑上面提到的那种情形，虽然先验概率等于后验概率，但是，先验概率比较最初的由通信语境等信息决定的概率依然是改变了的，一次一密体制改变了明文最初的概率，一旦一个密码体制的信息改变了明文的概率，在仙农看来也会认为是不安全的。文献[7]提出了一种算法进行这种情形下的信息融合。

同样，仙农的后验概率也是具有歧义的，严格的说应当是（6）的情形。但是，由于定义不清楚，依然有其他的可能，比如，它可能是知道密文以后，根据密码体制的信息得出的概率，即上述的（3）的情形。这样的情形很容易被认为是后验概率，因为根据条件（3）已经能够得出明文的概率，而且它与先验概率存在不一致，一旦此时忽视先验概率的存在，则不必解释概率为什么会改变，也无需考虑概率折衷融合的问题，从仙农的证明来看，他也没有谈到上述的概率不一致和信息融合问题。可见，仙农很可能是把后验概率看成是条件（3）下的概率，即明文是等概率分布的。

仙农在文献[1]中举出了一个例子，该例子下的加密运算为s=i+j(Mod n)，其中i为明文，j为密钥，s为密文，仙农得出PE(M)=1/n的结论（注：缺乏具体证明过程，可能是仙农认为很简单），从这个结论可以看出与条件（3）的情形下得出的概率是一致的，因此可以认为仙农的确是在考虑后验概率的时候，忽视了先验概率的存在，根据明文和密钥一一对应的关系得出它们的概率是相等的。从仙农直接给出结论来看，显然这个PE(M)的计算过程都不值得推导和论证，假如仙农此时考虑先验概率的不等性，PE(M)的计算过程将是非常复杂的，甚至当时还没有合理的算法来计算折衷的概率。

为了进一步确实仙农的错误，我们可以根据仙农的PE(M)=1/n以及完善保密的条件P (M)= PE(M)，得出P (M)=1/n，也就是说明文是等概率的。显然明文不会天然等概率的，除非巧合。可见，这种结果会导致对已知条件的改变，因而论证中存在错误。这也是对笔者论证在明文等概率时，所有明文等长度，所有等长度编码都是明文时，一次一密体制是完善保密的一种印证。

2.关于证明错误的分析
以上我们分析并且确定仙农的想法并不是出于单纯的理由，而是希望借助它来分析其他理论的局限性，比如信息论的局限性，以及相关的概率论基础的一些局限。

在我们分析中，有一个很重要的问题就是概率的折衷融合的问题，在上面并没有详细讨论，直接认为要采取折衷算法，在这里做一定的分析。首先，怎样来理解这里的不同概率以及概率的折衷融合问题。这里为什么会有不同的概率，是因为有不同的条件，比如我们可以根据语境等信息得出明文的概率，也可以根据密文和密码体制的信息得出明文的概率，也可以组合这些条件得出概率。可见，概率应该是相对于条件而言的，当对事物的了解不充分的时候，比如昨天某同学是否迟到，虽然是确定的事情，但是由于信息的不完备，我们只能得出随机不确定的结果[8]。这样的情况下，我们对概率应该有不同的表述，这里推测出来的概率应该说成是根据已知的所有信息推测出某同学迟到的概率，而不是某同学昨天迟到的概率。同样，这里的明文概率分布，一开始只知道一个大致的概率分布，仅仅是根据通信的语境等信息得出的，显然它并不能够很可靠地反映明文的概率分布，但是由于条件的限制，我们不了解更多的信息，所以只有权宜地采用该概率分布。当信息越来越多的时候，我们对事物的了解就进一步完备可靠。这也是为什么事件的概率分布可能从最初的不确定到发生以后的确定改变的原因。我们根据密码体制和密文的信息同样也可能得出概率分布，这一个概率分布一般不会和原来的概率分布一致，除非巧合。由于两组条件同时存在的情况下的概率是未知的，这时候求最终的概率，显然应该是对不同概率的一个折衷。当然，这里的最终概率是相对于这两组条件而言的，即严格地说应该是这两组条件同时存在的情况下明文的概率。如果有更多的条件，则需要更多的折衷。这里的问题相对于概率论中的条件概率而言，差别在于条件概率有先后关系，但是这里的概率是单个条件下的，并不知道这些条件相互的条件概率，因此，计算它们的联合概率就不能利用概率论中现成的公式，而是需要进行折衷融合。在文献[4]中，给出了一种先采用几何加权平均，然后进行归一化处理的概率融合算法，可以满足结合律，在特殊情况下的概率进行验证是符合事实的。

为了更加明确地说明问题，我们考虑在某些条件共同发生的情况下，确定某一事件m的概率，这些条件可能与m的概率有关，也可能无关，我们可以选择所有的有关的条件，我们假设其概率可以由n个有关的条件c1，c2，…，cn来决定，概率可以表示为

P(m)＝f（c1，c2，…，cn）

当然实际的情况更加复杂，而且可能呈现多种表现形式，比如，有些条件并不能确定概率的值，而是得出其概率呈现某一概率分布，比如，仅仅知道实验得出的概率，我们以此为条件，则可能得出理论上的概率是一个以实验得出的概率分布为中心的一个随机的分布，特别是在实验是不可靠的时候。为了方便，我们暂且用上面的这个很简单的函数式来表达，从而说明概率论中的某些问题。

当我们对某些条件不了解的时候，此时概率P(m)本身由于未知数的存在，而并不固定，我们知道的条件越多，得出的概率就越是可靠。本例子中，也是如此，由于条件的不全面，得出的概率并不等于全面条件下的概率，因此，这些不完备的条件下的概率冲突是可以理解的，即它们不能完全代表完备条件下的概率。同样说明用它们代替完备条件下的概率是不可靠的，当然条件越是完备，概率值（或者概率的概率分布）将会是越可靠。为了要让概率更加可靠，所以，我们要将片面条件下的概率进行融合。

这里反映出信息论没有考虑的一些问题，比如，信息论没有考虑信息的可靠性，所以不存在信息融合的问题[9]。在信息论中，我们只需要将信息可靠地传输，而不考虑信息本身的可靠性，这对于单个无相关的信息而言，可以不考虑，但是当我们考虑信息的意义的时候，这些意义可能是不一致的，甚至冲突的，需要进行信息融合，而信息融合的目的，还是要增强信息的可靠度。信息论由于没有考虑信息的可靠性，所以不存在信息融合的问题。正是如此，在应用中，信息论也存在很大的局限性，它在信息融合、人工智能等领域经常是无能为力的[10]。本文一次一密体制就是一个很好的例子，信息论不能解决一次一密体制中的信息融合问题，仙农由于忽略了先验概率的存在而无需面临信息融合问题，进而得出了错误的结论。

wangyong77

仙农将信息定义为消除不确定性的东西，但是，信息未必是消除不确定性的东西。在本例子中，依据通信语境等信息得到的明文的不确定性，比综合考虑各种条件的明文不确定性要低，密码体制和密文的信息不但没有消除不确定性，而且还增加了不确定性。这似乎与仙农的条件熵不增加矛盾，仔细看仙农的条件熵的公式，就会发现仙农的条件熵公式是将各种条件进行拆分后，计算条件熵，然后进行加权平均得出总的条件熵，该后验熵可以被证明不大于原来的先验熵。这一加权平均做法并不合理，而且也不能保证发生某种事件后，其他事件的熵一定不增加，因为它是一个加权平均值，不能代表个体不增加。在文献[11，12]中有更多的分析。

在本例子中，虽然明文的先验熵小于后验熵，但是人们依然会选择后验熵，是因为后者考虑的条件更加完备，进而信息更加可靠。固然，消除不确定性是一种需要，但是根本的还是在于增加信息的可靠性。如果要在可靠性高，但是不确定性低的信息和可靠性低，但是不确定性高的信息之间选择的话，人们会选择可靠性高，但是不确定性低的信息。这从一定程度上说明，对信息的需要重要的是要得到可靠的信息，我们可以模仿仙农的定义，将信息看成增加可靠性的东西。通过信息不仅加强信息本身的可靠性，还会增加其他信息的可靠性。人们在运用信息的时候，总是试图去得到尽量可靠的信息，并且运用已有的信息来增加其他信息的可靠性。即使在消除不确定性时，也是以增强可靠性为目的的，消除不确定性是一个副产品而已。当然，这里的可靠性的赋值往往是人为的，如果与实际偏离，可能会把谎言当作真理，进而得出错误的判断，降低可靠性。

仙农对信息可靠性的忽视，可以从仙农对信息的表达上看出来。绝对可靠的信息的表达方式是确定的，所以它在用概率表达时候，概率值可以是固定值。非绝对可靠的信息，它的表达本身就是有多个可能值，所以，它的概率分布本身也不确定。比如，A告诉B：“他估计C迟到的概率为百分之五十。”由于他仅仅是估计，所以C迟到的概率大致上在百分之五十左右，但是也不是固定是百分之五十，根据A说话的可靠程度，C迟到的概率可能是以百分之五十为中心的一个概率分布。即概率本身也可能是随机不确定的，仙农高明地用随机不确定性来表示信息，而不是用确定的方式来表示信息，但是，没有注意到天外有天，表示信息的概率本身也可能具有随机不确定性。仙农虽然没有强调他表示信息的概率是固定值，但是从他在对概率的应用上可以看出他的概率值是固定的，否则，信息论中的许多论证是无意义的。这里我们也可以看出，信息的可靠性可以用信息的多重随机不确定性来表征。当然，这种表示并不满足所有现实中的信息而有待于推广，比如，模糊信息就不能用这种方式表达。



3.结束语
本文对仙农证明中错误进行了确认，并且分析了产生问题的根源，比如信息论并没有考虑信息的可靠性和完备性。目前一些其他的教材和讲义中针对一次一密体制的完善保密性有比仙农更加详细的证明，同样存在类似的问题。虽然一次一密体制并不具有完善保密性，但是依然具有很好的密码特性。对信息论的局限的分析有助于信息论的发展和推广，因为信息的可靠性和完备性是非常重要的，信息的价值之所以存在，就是因为信息具有一定的可靠性，否则，它一文不值。

参考文献
[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].      王勇. 论概率的相对性[OL]. 中国科技论文在线(http://www.paper.edu.cn). 2007年08月27日

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

[10].   王勇，论信息的相对性[C]，武汉：首届全国社会信息科学研讨会论文集，2007年06月

[11].   王勇. 香农信息论的局限性分析[OL]. 中国科技论文在线(http://www.paper.edu.cn). 2007年07月18日

[12].   王勇. 条件熵的质疑[OL]. 中国科技论文在线(http://www.paper.edu.cn). 2007年8月6日





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