程序员面试必考题（十九）--信息安全中的数字签名与鉴别技术

数字签名

在人们日常生活中，各种文件、合同、书信等文档是依靠人的手写签名或者印章来证明其真实性的，而在计算机网络中传送的文件数据要证明其真实性，就需要用到数字签名技术。一个用于计算机网络中表示文件真实性的数字签名技术，必须要实现以下三个功能：

接收方可以验证发送方所宣传的身份。
发送方在发出数据后不能进行否认。
接收方不可能自己编造信息。

实现数字签名的方法分为对称密钥签名和公钥签名两种。对称密钥签名的基本思想是：

网络中建立一个可以信任的权威机构S，每一个用户选择一个保密的密钥作为和S进行加密通信的对称密钥。当用户A要向用户B发送一条签名的明文时，它利用与S共享的密钥KA将该明文与用户B的标识进行加密，然后与A的标识一起发送给S。

S收到该信息后，利用KA进行解密，得到原始明文和B的标识，然后S利用自己特有的密钥KS对原始明文和A的标示进行加密（意味着S对原始明文和A的标识进行签名），将得到的密文与原始明文和A的标识一起用KB加密后发送给B。

当B收到来自S的密文后，利用KB解密得到A的标识、原始明文和S签名后的信息，就可以知道A给自己发送的明文。由于S是可以信任的权威机构，则其通过KA确认明文的发送者是A不是其他用户。而且，如果A后来拒绝承认自己曾经发送过该明文给B，则S可以解密发送给B的签名，还原出原始明文和A的标识，证明Ａ曾经发送过该明文给S。

采用公钥技术进行数字签名比采用对称密钥更加容易实现。在公钥加密体制下，假设选取的加密算法E和解密算法D满足：E（D（P））=P，P为明文。当用户A向用户B发送明文时，利用A的私钥进行D运算，将得到的密文发送给B。B收到密文后，利用A的公钥对密文进行E运算，可以得到原始明文。

因为A的私钥只有A自己知道，所有其他用户不可能利用A的私钥对明文进行D运算，这样就可以让B确信报文是由A发送的。而如果其他用户对A发送的报文进行篡改，但无法得到A的私钥对明文进行D运算，而B对篡改过的报文进行E运算后，将会得到不可读的明文，就可以知道收到的报文被篡改过。

如果A要否认曾经发送过报文给B，B可以把经过E运算得出的明文和收到的密文一起出示给权威可信的第三方，第三方利用公开的Ａ的公钥对密文进行E运算，与Ｂ提交的明文进行比对，就可以证明Ａ是否发送过该明文给Ｂ。这样的过程只能对报文进行签名，而不能进行加密。

2.鉴别技术

鉴别是指在通信过程中，参加通信的实体要验证通信的对方是自己所要通信的对象，而不是其他冒充者。鉴别技术也是保证网络安全的一项重要手段，在计算机网络中，最常用的鉴别技术是报文鉴别。

报文鉴别是指接收者在收到数据报文后，能够确认该报文是发送者所发，而没有经过他人的篡改。进行数字签名是进行报文鉴别的主要手段，但对于很长的报文进行数字签名会大大加重计算机的负担，因此，当进行不需要加密报文的传送时，接收方应该能够用简单的方法进行报文的鉴别。

典型的报文鉴别方法是报文摘要MD（MessageDigest）。报文摘要的基本思想是：发送方A将要发送的较长的报文经过某种报文摘要运算后变成很短的报文摘要，然后用自己的私钥对报文摘要进行D运算，即进行数字签名。

经过数字签名的报文摘要称为报文鉴别码MAC（MessageAuthentication Code）。A将报文鉴别码MAC插入到原始报文之后一起发送给接收方B。B收到原始报文和报文鉴别码MAC之后，首先将原始报文与报文鉴别码MAC分离，然后利用A的公钥对报文鉴别码进行E运算，还原出报文摘要；再对原始报文进行报文摘要运算，将得到结果与由MAC还原出的报文摘要进行比对，如果两者一致，则说明收到的报文是A发送的，否则，则说明报文受到了其他用户的篡改。

报文摘要的优点在于：对于长度很短的报文摘要进行数字签名要比对整个报文进行数字签名要简单的多；同时，将原始报文和报文鉴别码合在一起是不可伪造的。

报文摘要算法的原理是利用单向哈希函数（One-way Hash）将任意长度的输入报文经过计算得出固定位数的输出。所谓单向是指该算法是不可逆的，即从输出计算得到输入是不可实现的，而且要找到任意两个输入报文，使得它们具有相同的报文摘要也是不可能的。

最常用的报文摘要算法是由RFC1321所提出的MD5算法。MD5算法可以对任意长的报文进行运算，得出固定长度为128位的报文摘要，其运算过程可以概括为：

（1）对任意长度的报文按模264计算其余数，得到的结果追加在报文后面。

（2）在报文和余数之间进行填充，使得填充后的总长度为512的倍数。

（3）将总的报文分割成若干个512位的数据块，每个数据块再分割成4个128位的子数据块依次送到不同的哈希函数进行4轮运算。每一轮又都按32位的小数据块进行复杂运算，一直到最后计算出128位的报文摘要。

MD5算法的设计者麻省理工学院的Rivest指出，要根据MD5计算出的报文摘要还原出原始报文，其计算量的级数为2128，在实际情况中是不可能实现的。虽然有不少研究者在不断尝试证明MD5算法是有漏洞，是可以被攻破的，但到目前为止仍然没有人能找到破解MD5算法的方法。除了MD5算法之外，美国国家标准局提出了安全散列算法SHA，其原理与MD5相似，不同的是采用160位的报文摘要。