数字签名(一)
正式开始之前，我们先讨论下，实际生活中，当遇到上一节最后提到的信任问题----让人相信可信的第3方出具的证明----这一问题时，通常是怎么解决的。稍加考虑，我们就会得到简单结论：因为这些证明都附加了令人相信的证据，比如有第3方的亲手签名或盖章。有的朋友可能有过这样的经历，当需要去外面的单位(假设为X单位)参加会议时，通常会由本单位(假设为Z单位)开具一份介绍信，上面大概内容如下：
X单位：现有我单位同志张三，前往贵单位参加某某会议，请招待，某年某月某日。落款为Z单位，并加盖Z单位的公章。
请注意，这里Z单位的公章必不可少，X单位收到介绍信后，就是靠信上的公章来相信，介绍信的持有人就是张三。
这很完美吗？至少是比较完美。因为它基本上解决了前面提到的信任问题，所以直到今天，介绍信仍在社会生活中起到一定的作用。之所以说它是比较完美，是因为仍有一点小小的瑕疵。首先，无论是签名还是盖章，都可以在某种程度上被模仿或伪造。现实生活中，从伪造介绍信、合同到伪造学历、遗嘱，就是明证。其次，缺乏对介绍信持有人(严格地说，是第3方证明中的被证明对象)的身份验证。试想，如果李四通过某种途径得到(比如捡到或偷到)介绍信，就可以用它去参加会议。因为在实际情况中，通常Z单位收到介绍信后，会直接相信李四就是介绍信中的张三，而不会通过其他方法来核实介绍信持有人的身份。
后面我们将看到，这两个缺陷，在公钥密码学中都得到了很好的解决。
现在，回到我们的正式课程。我们面临的问题是：如何让Bob相信，他通过令人不信任的网络得到的一份“证明”，的确是可以信任的。更精确地说，我们要保证做到，无论Bob收到的“证明”，是真的来自Trent，还是别人假冒Trent发出的，Bob都必须能够识别出来。只有同时做到这两点，才能满足我们的要求。
现实生活已经给我们提供了绝佳的工具----签名或盖章。现在的问题是，我们在网络数字世界中怎么去实现它呢，使得真的Trent签名被认可，假的签名被识破。
先换个角度，假设我们已经做到了，会是什么结果。很明显，我们最终将拥有两部分内容，一是被证明的内容(比如，Carol的公钥是Y)，称为消息(记为M)，二是Trent给出的“此消息为真”的证据，称为签名(记为S)。我们注意到，这两部分内容(即消息和签名)是分离的，即理论上可以把它们分开，这一点不像我们日常生活中的签名，一旦签上名后，名字和证明内容就合在一起，不会分开了(因为都在一张纸上)。在数字世界中，为什么消息和签名是分开的？因为它们一旦合在一起(不是无损压缩)，接收方就分辩不出来。举个例子，消息大小为1024字节，签名也是1024字节，总大小是2048字节。如果合在一起，总长度小于2048字节，相当于信息熵减少，接收方无法还原出原来的1024字节消息和1024字节签名。还要注意的是，消息和签名都是以明文的形式保存和传递，否则就轮到Carol面临同样的问题(他要用Bob的公钥加密，需要面对Bob公钥真实性验证的问题)
既然消息和签名可以分开，就得到一个自然推论：签名必须依赖于消息，换句话说，签名是消息的函数，消息一变，签名跟着变。为什么要这样呢？如果签名不依赖于消息，就不是变量，而是常量。Eve可以在不同的消息后面附加这个(万能的)签名常量，去欺骗Bob相信。这是Bob所不能接受的，所以签名是消息的函数，将此函数记为Sig。从而有S=Sig(M)。不失一般性，我们认为签名函数Sig(.)的算法是公开的。
好，现在已知S=Sig(M)，看看还差什么，哦，少了重要的一点，签名S必须只有Trent才能生成，Sig(.)算法是公开的，要想让S由Trent决定，我们只能对Sig(.)略作修改，增加一个参数，变为S=Sig(M,ST)，其中ST必须是一个只有Trent才知道的秘密的值，而且连Bob也不能知道(这样才能通过ST将Trent与其他人区分开)。眼尖的同学马上会说，那Carol怎么知道Trent是否真的用了ST来计算S，或者说，如何判断这个签名S是由Trent生成的。我们还要做什么事呢？
很明显，我们必须要有一个判定准则(或者说是验证算法)，使得给定消息M，能够判断签名S是否为Trent所生成。现在我们仍然假设存在这个验证算法，并用字母V来表示，则可以将验证算法V视作一个返回真假值的函数，它接收消息M和签名S作为入参，并且有以下事实：
如果S=Sig(M,ST)，则V(M，S)=TRUE，表示S是Trent对消息M生成的真正签名
否则，对于任何S≠Sig(M,ST)，V(M，S)=FALSE，表示S不是Trent对消息M生成的真正签名
细心的朋友会发现，验证算法V依赖于Trent的身份，不具备通用性。为了满足这一性质，我们对V稍加改正，再增加一个身份参数P。需要说明的是，P必须是公开的，否则对证明人(这里是Trent)的身份无从区分。经过这一修正，我们得到
如果S=Sig(M,ST)，则V(M，S，PT)=TRUE
否则，对于任何S≠Sig(M,ST)，V(M，S，PT)=FALSE
以上PT是Trent的公开身份信息(或参数)，其中P或S的下标T，是着重表示与T(即Trent)相关的参数
我们将目光集中在等式V(M，Sig(M,ST)，PT)=TRUE上，它从另一个角度告诉我们，给定消息M和Trent的身份信息PT，只有知道Trent的秘密值ST，才能计算出S，使得函数V(M，S，PT)返回真值。
换句话说，如果对于消息M，某人给出签名S，满足V(M，S，PT)为真，则我们可以判断该人就是Trent，或者签名S就是Trent生成的签名。
为什么这样推断？这是因为，满足条件的S--指V(M，S，PT)返回结果真--是由消息M和另一个秘密的只有Trent才知道的参数(ST)计算得到，除Trent外的其他人不知道秘密值ST，所以算不出正确的S，能给出正确值S的人，只有Trent本人。回到前面的例子，Carol通过网络给Bob发送关于消息M(消息内容是：Carol的公钥是Y)的正确签名S，当然同时给出说明--签名S是由Trent生成的。Bob收到后，找到Trent的公开信息PT，计算V(M，S，PT)，发现结果为真。Bob由此判断，S肯定是Trent本人发出来，如果Bob相信Trent本人，他自然会相信M的内容：Carol的公钥是Y。
到这里我们可以看到，S起的作用与平常生活中的签名完全一样，证明了消息M的真实性。唯一的神奇之处在于，它经过了险恶的Internet(任何消息都有可能被窃听、被篡改)，最终仍能够让Bob相信，Carol的公钥确实是Y。
现在剩下两个问题：
一、这样的验证算法V存在吗？
二、Trent的公开信息PT从何而来，它可信吗？
请看数字签名(二)