第5章消息认证与数字签名






本章导读

消息认证是用来防止主动攻击的重要技术，用以保证消息的完整性。常见的消息认证密码技术包括消息认证码（MAC）和安全散列函数。另外，消息加密也可以提供一种形式的认证。

MAC是需要使用密钥的算法，其输入是可变长度的消息和密钥，其输出是一个定长的认证码。只有拥有密钥的消息，发送方和接收方才可以生成消息认证码和验证消息的完整性。

散列函数和MAC算法类似，也是一个单向函数，但是无需密钥，其输入是可变长度的消息，其输出是固定长度的散列值，也叫消息摘要。

数字签名是基于公钥密码技术的认证技术。它和手写签名类似，使得消息的发送方可以使用自己的私钥为初始消息生成一个有签名作用的签名码，接收方接收到初始消息和相应的签名码，可以使用消息发送方的公钥对该消息的签名码进行验证。数字签名可以保证消息的来源和消息本身的完整性。

使用数字签名，通常需要和散列函数配合使用。

5.1认证

加密通常用于保密，对某个信息的加密操作使得其内容对于未授权的人而言是保密的、安全的。但是，在某些情况下，完整性比保密性更重要。例如，在某个医院的医疗系统中检索到的病人的医疗记录，或者银行系统中检索到的某个人的信用记录，检索到的这些信息和所存储的正本是否一致是非常重要的。在传统的或者没有考虑完整性的系统中，文件的组成部分或者消息的组成部分，即每字节、位或者每个字符都是彼此独立的，由于缺乏彼此的绑定，使得攻击者对于信息的修改无法被发现。在目前的电子商务系统中的各种应用中，这类问题造成的后果更加严重。能否为文件或者网络中通信的消息打上一个标签，当文件或消息出现了任何改变，即便只修改了一位信息时，我们都可以从标签和信息的关系上知道有内容被修改了。这种想法和中世纪在信封上使用蜡封类似。在密码技术中，提供这样的蜡封技术或标签技术的就是为信息提供一种认证，这样的蜡封或者标签在密码技术中称为认证码，如后文中讨论的哈希值、校验和等都是某种形式的认证码。

同样，在网络通信环境中，保密的目的是防止攻击者破译系统中的机密信息，但在大多数网络应用中，仅提供保密性是远远不够的。网络安全的威胁来自两个方面： 一是被动攻击，攻击者只是通过侦听和截取等手段被动地获取数据，并不对数据进行修改； 二是主动攻击，攻击者通过伪造、重放、篡改、改变顺序等手段改变数据。认证则是防止主动攻击的重要技术，它对于开放环境中的各种信息系统的安全性有重要作用，可以防止如下一些攻击。

信息安全原理与技术（第4版）

第5章消息认证与数字签名


 伪装： 攻击者生成一个消息并声称这条消息是来自某个合法实体，或者攻击者冒充消息接收方向消息发送方发送的关于收到或未收到消息的欺诈应答。

 内容修改： 对消息内容的修改，包括插入、删除、转换和修改。

 顺序修改： 对通信双方消息顺序的修改，包括插入、删除和重新排序。

 计时修改： 对消息的延迟和重放。在面向连接的应用中，攻击者可能延迟或重放以前某合法会话中的消息序列，也可能会延迟或重放消息序列中的某一条消息。
认证的目的主要有两个： 第一，验证消息的发送方是合法的，不是冒充的，这称为实体认证，包括对信源、信宿等的认证和识别； 第二，验证信息本身的完整性，这称为消息认证，验证数据在传送或存储过程中没有被篡改、重放或延迟等。

保密和认证是信息系统安全的两个重要方面，但它们又是不同的。认证不能自然地提供保密性，而保密性也不能自然地提供认证功能。但从某个层面上而言，我们也可以说保密性提供了某种认证功能，因为攻击者如果无法获得用于加密的密钥，而消息接收方收到了密文，并使用密钥进行解密，同时可以确认解密后得到的信息是正确的（如根据解密后的信息的含义），在这种情况下，整个密文就提供了认证功能。但如果发送方发送的信息是无意义的字符，消息接收方即便正确解密了，也无法通过字符的含义来判定所收到的消息是否是正确的。

因此，如果考虑加密函数的某种认证功能，我们考虑的可用于提供认证功能的认证码的函数则可以分为以下3类。

 加密函数： 使用消息发送方和消息接收方共享的密钥对整个消息进行加密，则整个消息的密文将作为认证符。

 消息认证码（Message Authentication Code）： 它是消息和密钥的函数，用于产生定长度值，该值将作为消息的认证符。

 散列函数： 它是将任意长的消息映射为定长的hash值的函数，以该hash值作为认证符。
一个基本的认证系统模型如图5.1所示。



图5.1基本的认证系统模型


5.2消息认证码

消息认证码（MAC）是一种使用密钥的认证技术，它利用密钥来生成一个固定长度的短数据块，并将该数据块附加在消息之后。在这种方法中假定通信双方A和B共享密钥K。若A向B发送消息M时，则A使用消息M和密钥K，计算MAC＝C（K，M），其中： 

 M＝输入消息，可变长 

 C＝MAC函数 

 K＝共享的密钥 

 MAC＝消息认证码
消息认证码MAC为消息M的认证符，MAC也称为密码校验和。


如图5.2所示，发送方将消息M和MAC一起发送给接收方。接收方收到消息后，假设该消息为M′，使用相同的密钥K进行计算得出新的MAC′=C（K，M′），比较MAC′和所收到的MAC。假设双方共享的密钥没有被泄露，则比较计算得出的MAC′和收到的MAC的结果，如果两者是相同的话，则可以认为： 


（1） 接收方可以相信消息未被修改。因为若攻击者篡改了消息，他必须同时相应地修改MAC值。而我们已假定攻击者不知道密钥，所以他不知道应如何改变MAC才能使其与修改后的消息相一致。

（2） 接收方可以相信消息来自真正的发送方。因为其他各方均不知道密钥，他们不能产生具有正确MAC的消息。

（3） 如果消息中含有消息序列号，那么接收方可以相信消息的顺序是正确的，因为攻击者无法成功地修改序列号。



图5.2消息认证码的使用



从使用密钥上看，MAC函数与加密函数类似，需要生成MAC方和验证MAC方共享一个密钥。但它们又存在本质的区别，区别之一为MAC算法不要求可逆性，而加密算法必须是可逆的。一般而言，MAC函数是多对一函数，其定义域由任意长的消息组成，而值域由所有可能的MAC和密钥组成。若使用n位长的MAC，则有2n个可能的MAC，而有m条可能的消息，其中m2n，而且若密钥长为k，则有2k种可能的密钥。

例如，假定使用100位的消息和10位的MAC，那么总共有2100不同的消息，但仅有210种不同的MAC。所以平均而言，同一MAC可以由2100/210条不同的消息产生。若使用的密钥长为5位，则从消息集合到MAC值的集合有25＝32种不同的映射。可见密钥的位数太短，很容易通过穷举进行攻击，但只要位数足够长，则可以保证其安全性。

图5.2给出的消息认证码的使用只是对传送消息提供单纯的认证性。它还可以和加密函数一起提供消息认证和保密性。如图5.3所示，发送方在加密消息M之前，先计算M的认证码，然后使用加密密钥将消息及其认证码一起加密； 接收方收到消息后，先解密得到消息及其认证码，再验证解密得到的消息和验证码是否匹配，如果匹配则表示消息在传输中没有被改动。



图5.3结合加密函数的消息认证码的使用方法


5.2.1MAC的安全要求

MAC中使用了密钥，这点和对称密钥加密一样，如果密钥泄露了或者被攻击了，则无法保证MAC的安全性。在基于算法的加密函数中，攻击者可以尝试所有可能的密钥以进行穷举攻击，一般对k位的密钥，穷举攻击需要2k-1步。对于仅依赖于密文的攻击，若给定密文C，攻击者要对所有可能的Ki计算Pi=DKi（C），直到产生的某Pi具有适当的明文结构为止（前提是这样的明文结构是可以判断的）。

MAC函数是多对一函数，这就意味消息的取值空间比MAC的取值空间大，则一定存在着不同的消息会对应于相同的MAC。假设MAC所使用的密钥位数为k，计算所得的MAC位数为n。若k>n，即假定密钥位数比MAC长，则对满足MAC1＝CK1（M1）的M1和MAC1，密码分析者要对所有可能的密钥值Ki计算MACi=CKi（M1），那么至少有一个密钥会使得MACi=MAC1。因为k个密钥总共会产生2k个MAC，但只有2n（2n<2k）个不同的MAC值，所以不同密钥都会产生正确的MAC，而攻击者却不知其中哪一个是正确的密钥。平均来说，有2k/2n=2k-n个密钥会产生正确的MAC，因此攻击者必须重复下述攻击。

（1） 第1轮。

 给定M1，MAC1＝CK（M1）。

 对所有2k个密钥判断MACi＝CKi（M1）。

 匹配数≈2k-n。
（2） 第2轮。

 给定M2，MAC2＝CK（M2）。

 对循环1中找到的2k-n个密钥判断MACi＝CKi（M2）。

 匹配数≈2k-2n。
攻击者可以按此方法不断对密钥进行测试，直到将匹配数缩小到足够小的范围。平均来讲，若k=a×n，则需a次循环。例如，如果使用80位的密钥和长为32位的MAC，那么第1次循环会得到约248个可能的密钥，第2次循环会得到约216个可能的密钥，第3次循环则得到唯一一个密钥，这个密钥就是发送方所使用的密钥。这样看来，若密钥的长度小于或等于MAC的长度，则很可能在第1次循环中就得到一个密钥。

由此可见，如果密钥足够长，用穷举方法来确定MAC的密钥就不是一件容易的事。

当然，以上的穷举攻击是建立在算法安全强度可信的前提下。针对不同的MAC算法，攻击者可能不需要使用穷举攻击即可找到密钥。攻击者针对下面的MAC算法，则不需要使用穷举攻击即可获得密钥信息。

设消息M＝（X1‖X2‖…‖Xm），即由64位分组Xi连接而成。定义：


Δ（M）＝X1X2… Xm
Ck（M）=EK［Δ（M）］


其中是异或（XOR）运算，加密算法是电码本方式实现的DES算法，则密钥长为56位，MAC长为64位。若攻击者获取{M‖Ck（M）}，并使用穷举攻击，则确定K须执行至少256次加密，但是攻击者可以用任何期望的Y1~Ym-1替代X1~Xm-1，用Ym替代Xm来进行攻击，其中Ym的计算方法如下。


Ym＝Y1Y2…Ym-1Δ（M）


攻击者可以将Y1~Ym-1与原来的MAC连接成一个新的消息M′，接收方收到（M′，Ck（M））时，由于Δ（M′）=Y1Y2… Ym=Δ（M），因此Ck（M）=EK［Δ（M′）］，接收方会认为该消息是真实的。利用这种办法，攻击者可以插入任意长为64×（m-1）位的消息。

因此，一个安全的MAC函数应具有下列性质。

 若攻击者知道M和Ck（M），则构造满足Ck（M′）=Ck（M）的消息M′在计算上是不可行的。

 Ck（M）应是均匀分布的，即对任何随机选择的消息M和M′，Ck（M）=Ck（M′）的概率是2-n，其中n是MAC的位数。

 设M′是M 的某个已知的变换，即M′=f（M），则Ck（M）=Ck（M′）的概率为2-n。

5.2.2基于DES的消息认证码

数据认证算法（FIPS PUB 113）是使用最广泛的MAC算法之一，它也是一个ANSI标准（X9.17）。该算法建立在DES算法之上，利用了密文链接模式（CBC）对消息进行加密处理。该算法在实际中的应用很广泛，特别是在银行系统中。

如图5.4所示，数据认证算法取初始值为0，这个初始值没有实际意义，只是用于第1次计算，需要认证的消息被划分成64位的分组D1，D2，…，DN，若最后分组不足64位，则在其后填0直至成为64位的分组。利用DES加密算法E和密钥K，计算认证码的过程如图5.4所示。





O1=EK（D1）
O2=EK（［D2O1］）
O3=EK（［D3O2］）
︙
ON=EK（［DNON-1］）


不输出最后一个分组的加密结果，取其最左边的n位作为认证码。



图5.4数据认证算法


5.3Hash函数

Hash函数（也称散列函数或杂凑函数）是将任意长的输入消息作为输入生成一个固定长的输出串的函数，即h=H（M）。这个输出串h称为该消息的散列值（或消息摘要、杂凑值）。散列函数通常和一个安全的Hash函数H应该至少满足以下几个条件。

（1） H可以应用于任意长度的数据块，产生固定长度的散列值。

（2） 对每一个给定的输入m，计算H（m）是很容易的。

（3） 给定Hash函数的描述，对于给定的散列值h，找到满足H（m）=h的m在计算上是不可行的。

（4） 给定Hash函数的描述，对于给定的消息m1，找到满足m2≠m1且H（m2）=H（m1）的m2在计算上是不可行的。

（5） 找到任何满足H（m1）=H（m2）且m1≠m2的消息对（m1，m2）在计算上是不可行的。

条件（1）和条件（2）指的是Hash函数的“单向”（OneWay）特性，条件（3）和条件（4）是对使用散列值的数字签名方法所做的安全保障。否则攻击者可以由已知的明文及相关数字签名任意伪造对其他明文的数字签名。条件（5）的主要作用是防止后文将要提到的“生日攻击”。通常我们称满足条件（1）~条件（4）的散列函数为“弱散列函数”，若能同时满足条件（5），则称其为“强散列函数”。

Hash函数主要用于完整性校验和提高数字签名的有效性，目前已有很多方案。这些算法都是伪随机函数。早在1978年，Rabin就利用DES算法，使用密文分组链接（CBC）方式，提出一种简单快速的散列函数，方法如下所示。 

将明文M分成固定长度的64位的分组： m1，m2，…，mk。使用DES的CBC操作模式，对每个明文分组进行加密，令h0=初始值，hi=Emi［hi-1］，最后散列值为hk，这个方法和第5.2.2节中的基于DES的MAC算法类似，但不同的是该算法中的加密没有使用任何密钥。但需要指出的是，使用Rabin散列函数的数字签名是不安全的，已经发现可以在有限的计算范围内，不通过获得签名私钥的方法即可实现伪造签名。

好的散列函数的输出以不可辨别的方式依赖于输入。任何输入串中单个位的变化，将会导致输出位串中大约一半的位发生变化。其处理思想是先要将明文分成固定长度的明文分组，再对每个分组做相同的处理，比较有名的有MD5、Ripend160、SHA、Whirlpool等算法。所有的散列函数都具有图5.5中的处理结构，这种结构称为迭代Hash函数，它是由Merkle提出的。其中的f算法即是散列函数中对分组进行迭代处理的压缩函数。散列函数重复使用压缩函数f，它的输入是前一步得出的n位输出（称为链接值）和一个b位消息分组，输出为一个n位分组。链接值的初始值由算法在开始时指定，其终值即为散列值。这样，一般结构的Hash函数可归纳如下： 


CV0=IV=n位初始值
CVi=f（CVi-1，Yi-1）1≤ i≤ L
H（M）=CVL


其中Hash函数的输入为消息M，经填充后的消息分成L个分组，分别是Y0，Y1，…，YL-1。



图5.5Hash函数的一般结构


Hash函数和MAC函数不同，不需要使用密钥，因此也觉得了Hash函数无法像图5.1中所示的那样单独提供对消息的认证，通常它和数字签名结合使用来提供认证性。在网络安全通信中，Hash函数和对称密码、非对称密码结合使用以提供不同的安全服务。图5.6给出了几种基本应用。



图5.6Hash的基本应用



图5.6（a）给出了Hash函数和数字签名的典型使用方法。对消息M的数字签名通常不是直接对消息进行计算，而是先使用Hash函数得到消息的散列值，再使用发送方的签名私钥PRa对代表消息的散列值进行签名，这样既可以提供消息的认证性，又可以保证效率。图5.6（b）所给出的消息认证方式和MAC有点类似，因为Hash函数不使用密钥，如果直接对消息进行散列值计算，并和消息进行连接传送，则攻击者很容易篡改消息并相应地重新计算散列值。因此，对于计算出来的散列值，使用密钥加密的方法则可以避免发生上述问题，攻击者即便篡改了消息，也因为没有相应的加密密钥伪造消息散列值的密文。图5.6（c）中提供的安全服务是保密性和认证性。除此之外，根据应用需求提供，Hash函数还可以和其他密码函数结合使用提供不同的应用模式。


5.3.1散列函数的安全要求

将第5.3节中给出的安全Hash函数需要满足的后面3个条件重新描述如下（即是Hash函数的安全要求）。

（1） 单向性： 对任何给定的散列码h，找到满足H（x）＝h的x在计算上是不可行的。

（2） 抗弱碰撞性： 对任何给定的消息x，找到满足y≠x且H（x）=H（y）的y在计算上是不可行的。

（3） 抗强碰撞性： 找到任何满足H（x）=H（y）的偶对（x，y）在计算上是不可行的。

在图5.5所示的一般结构的Hash函数中，其输入消息被划分成L个固定长度的分组，每一分组长为b位，最后一个分组不足b位时需填充为b位，最后一个分组包含输入的总长度。由于输入中包含长度，所以攻击者必须找出具有相同散列值且长度相等的两条消息，或者找出两条长度不等但加入消息长度信息后散列值相同的消息，从而增加了攻击的难度。Merkle和Damgard发现，如果压缩函数具有抗碰撞能力，那么迭代Hash函数也具有抗碰撞能力，因此Hash函数常使用上述迭代结构，这种结构可用于对任意长度的消息产生安全Hash函数。

1. 生日攻击（Birthday Attack）

如果攻击者希望伪造消息M的签名来欺骗接收方，则他需要找到满足H（M′）=H（M）的M′来替代M。对于生成64位散列值的散列函数，平均需要尝试263次以找到M′。但是建立在生日悖论上的生日攻击法，则会更有效。

对于上述问题换种说法： 假设一个函数有n个函数值，且已知一个函数值H（x）。任选k个任意数作为函数的输入值，则k必须为多大才能保证至少找到一个输入值y且H（x）=H（y）的概率大于0.5？

对于任意的y，能够满足H（x）=H（y）的概率是1/n，反之，满足H（x）≠H（y）的概率为1-1/n。对于所选的k个任意的输入值y都没有一个满足H（x）=H（y）的概率则是（1-1/n）k。这样，至少有一个y满足H（x）=H（y）的概率是1-（1-1/n）k。

二项式定理可描述如下： 


（1-a）k=1-ka+k（k-1）2!a2-k（k-1）（k-2）3!a3+…


当a趋近0时，（1-a）k趋近1-ka，因此至少有一个y满足H（x）=H（y）的概率约为1-（1-1/n）k≈1-（1-k/n）=k/n。当k> n/2时，这个概率将超过0.5。

若散列值为m位，则可能有2m个散列值，使上述概率为0.5的k为k=2m-1。即对于生成64位散列值的散列函数而言，攻击者至少需要尝试263对明文，才能有大约0.5的成功概率。这个结果似乎表明选择64位的散列函数是安全的，但事实并非如此。Yuval提出的“生日悖论”对于之前提到的Rabin散列函数的数字签名攻击，只需要232次的运算。

在讨论Yuval的方法之前，先来解释一下“生日悖论”的数学背景。我们可以这样描述这类问题： k为多大时，在k个人中至少找到两个人的生日相同的概率大于0.5？不考虑2月29日，并且假定每个生日出现的概率相同。

首先k个人的生日排列的总数目是365k。这样，k个人有不同生日的排列数为：


N=365×364×…×(365-k+1)=365!(365-k)!



因此，k个人有不同生日的概率为不重复的排列数除以总数目，得到：


Q（365，k）=365!（365-k）!（365）k


则，k个人中，至少找到两个人同日出生的概率是：


P（365，k）=1-Q(365，k)=1-365!（365-k）!(365)k


当k=100时，P（365，100）=0.9999997，这意味着只有一个重复的概率接近于百分百。如果只考虑同日出生的概率超过0.5时，则根据P（365，23）=0.5037，k只需要为23。

Yuval的生日攻击法描述如下。

（1） 合法的签名方对于其认为合法的消息愿意使用自己的私钥对该消息生成的m位的散列值进行数字签名。

（2） 攻击者为了伪造一份有（1）中的签名者签名的消息，首先产生一份签名方将会同意签名的消息，再产生出该消息的2m/2种不同的变化，且每一种变化表达相同的意义（如在文字中加入空格、换行字符）。然后，攻击者再伪造一条具有不同意义的新的消息，并产生该伪造消息的2m/2种变化。

（3） 攻击者在上述两个消息集合中找出可以产生相同散列值的一对消息。根据“生日悖论”理论，能找到这样一对消息的概率是非常大的。如果找不到这样的消息，攻击者将再产生一条有效的消息和伪造的消息，并增加每组中的明文数目，直至成功为止。

（4） 攻击者用第一组中找到的明文提供给签名方要求签名，这样，这个签名就可以被用来伪造第二组中找到的明文的数字签名。这样，即使攻击者不知道签名私钥也能伪造签名。

生日攻击表明Hash值的长度必须达到一定的值，如果过短，则容易受到穷举攻击，如一个40位的Hash值，只需要穷举一百万次。一般建议Hash值需要160位，SHA1的最初选择是128位，后来改为160位，这就是为了防止利用生日攻击原理穷举Hash值。


2. 中间相遇攻击法（Meet in the Middle Attack）

中间相遇攻击是生日攻击的一种变形，它不比较散列值，而是比较处理链中的中间变量。这种攻击主要适用于攻击具有分组链接结构的Hash函数。其基本原理为： 将消息分成两部分，对伪造消息的第一部分从初始值开始逐步向中间阶段产生r1个变量； 对伪造消息的第二部分从Hash结果开始逐步退回中间阶段产生r2个变量。在中间阶段有一个匹配的概率与生日攻击成功的概率一样。

这种攻击方法让攻击者可以仅根据已知的明文及其数字签名，来任意伪造其他明文的数字签名。

（1） 根据已知数字签名的明文，先产生散列函数值h。

（2） 再根据意图伪造签名的明文，将其分成每个64位长的明文分组Q1，Q2，…，QN-2。Hash函数的压缩算法为hi=EQi［hi-1］，1≤i≤N-2。

（3） 任意产生232个不同的X，对每个X计算EX［hN-2］。同样地，任意产生232个不同的Y，对每个Y计算DY［G］，D是相对应E的解密函数。

（4） 根据“生日悖论”，有很大的概率可以找到很多X及Y满足EX［hN-2］=DY［G］。

（5） 如果找到了这样的X和Y，攻击者重新构造一个明文： Q1，Q2，…，QN-2，X，Y。这个新的明文的散列值也为h，因此攻击者可以使用已知的数字签名为这个构造的明文伪造新的明文的签名。


5.3.2SM3

SM3是国家商用密码管理局于2010年12月17日发布的商用散列算法。本标准适用于商用密码应用中的数字签名和验证、消息认证码的生成与验证以及随机数的生成，可满足多种密码应用的安全需求。同时，本标准还可为安全产品生产商提供产品和技术的标准定位以及标准化的参考，提高安全产品的可信性与互操作性。SM3是将长度为L(L< 264) 比特的消息m，压缩输出为256比特的摘要值,如图5.7所示。



图5.7SM2主要处理过程



SM3算法描述如下。

1) 填充与分组

SM3对输入消息先填充，再分组，分组的长度为512比特，消息填充后的比特长度为512的倍数。填充方法如下： 假设消息m的长度为L比特。首先将比特“1”添加到消息的末尾，再添加k个“0”，k是满足L+1+k≡448 mod 512的最小的非负整数。然后再添加一个64位比特串，该比特串是长度L的二进制表示。填充后的消息m′的比特长度为512的倍数。

例如： 对消息01100001 01100010 01100011，其长度L=24，经填充得到比特串： 


01100001 01100010 01100011 1 00…00423比特 00…01100064比特 1的二进制表示 



2) 初始化


SM3采用8个寄存器ABCDEFGH存储散列运算中间结果和最终结果，首先对寄存器值进行初始化为IV=7380166f 4914b2b9 172442d7 da8a0600 a96f30bc 163138aa e38dee4d b0fb0e4e。这些字节采用高端(bigendian)格式存储，高端格式存储规定： 左边为高有效位，右边为低有效位。数的高阶字节放在存储器的低地址，数的低阶字节放在存储器的高地址。

3) 压缩过程

（1） 迭代过程。


以512位的分组为单位进行迭代压缩计算，将填充后的消息m′按512比特进行分组，


m′=Y0Y1…Yn-1

其中n=(L+k+65)/512。

对m′按下列方式迭代： 

FOR i=0 TO n-L
Vi+1=CF(VI,Yi)
ENDFOR

其中CF是压缩函数，V0为256比特初始值IV，Yi为填充后的消息分组，迭代压缩的结果为Vn。

（2） 消息扩展。

将消息分组Yi按以下方法扩展生成132个字W0，W1,…,W67，W′0,W′1,…,W′63，用于压缩函数CF： 

a) 将消息分组Yi划分为16个字，即W0，W1,…,W15。

b) FOR j=16 TO 67

 Wj←P1(Wj-16⊕j-9⊕(Wj-3<<<15))⊕(Wj-13<<<7)⊕Wj-6

ENDFOR

c) FOR j=0 TO 63

W′j=Wj⊕Wj+4

ENDFOR

其中，⊕表示32比特异或运算，<<<k表示循环左移k比特运算，P1为置换函数，计算方式见下面部分。

（3） 压缩函数。

令A、B、C、D、E、F、G、H为字寄存器,SS1、SS2、TT1、TT2为中间变量,压缩函数Vi+1=CF(Vi;Yi),0≤i ≤n-1。计算过程描述如下： 

ABCDEFGH←Vi

FOR j=0 TO 63

SS1←((A<<<12)+E+(Tj<<<j))<<<7

SS2←SS1⊕(A<<<12)

TT1←FFj(A,B,C)+D+SS1+W′j

TT2←GGj(E,F,G)+H+SS1+Wj

D←C

C←B<<<9

B←A

A←TT1

H←G

G←F<<<19

F←E

E←P0(TT2)

ENDFOR

Vi+1←ABCDEFGH⊕Vi

最后输出即为摘要值。

其中，Tj为常量，其值为： 


Tj=79cc45190≤j≤15
7a879d8a16≤j≤63



FFj和GGj是布尔函数，计算如下： 

FFj(X,Y,Z)=X⊕Y⊕Z0≤j≤15
(X∧Y)∨(X∧Z)∨(Y∧Z)16≤j≤63
GGj(X,Y,Z)=X⊕Y⊕Z0≤j≤15
(X∧Y)∨(�瘙
綈X∧Z)16≤j≤63



其中的一些符号含义表示为： 

∧： 32比特与运算

∨： 32比特或运算

�瘙
綈： 32比特非运算

+： mod232算术加运算

P0为压缩函数部分的置换函数，P1消息扩展部分的置换函数，按照下面方式进行运算。


P0(X)=X⊕(X<<<9)⊕(X<<<17)

P1(X)=X⊕(X<<<15)⊕(X<<<23)



式中，X为字。


5.3.3MD5

MD5（MessageDigest Algorithm 5）是由Ronald L.Rivest（RSA算法中的R）在20世纪90年代初开发出来的，经MD2、MD3和MD4发展而来。它比MD4复杂，但设计思想类似，同样生成一个128位的信息散列值。其中，MD2是为8位计算机做过设计优化的，而MD4和MD5却是面向32位的计算机。

Osrschot和Wiener曾为了攻击MD5，使用穷举攻击搜寻碰撞的函数，并耗费一千万美元设计了一台碰撞搜寻计算机，它能在24天内找到一个碰撞。但即便如此，从1991年起的十多年里，并没有出现替代MD5的算法或MD6，并且，由于使用MD5算法无须支付任何专利费，所以在实际中的应用非常广泛。直到2004年8月，在美国召开的国际密码学会议（Crypto2004）上，王小云教授给出破解MD5、HAVAL128、MD4和RIPEMD算法的报告。她给出了一个非常高效的寻找碰撞的方法，可以在数小时内找到MD5的碰撞。

MD5算法的描述：

MD5的输入可以是任意长度的消息，其输出是128位的消息散列值。由于MD5的设计是针对32位处理器的，因此MD5内的所有基本运算都是针对32位运算单元的。其算法的主要过程如下。

（1） 填充消息： 任意长度的消息首先需要进行填充处理，使得填充后的消息总长度与448模512同余（即填充后的消息长度≡448 mod 512）。填充的方法是在消息后面添加一位1，后续都是0。

（2） 添加原始消息长度： 在填充后的消息后面再添加一个64位的二进制整数表示在填充前原始消息的长度。这时经过处理后的消息长度正好是512位的倍数。

（3） 初始值（IV）的初始化： MD5中有4个32位缓冲区，用（A，B，C，D）表示，用来存储散列计算的中间结果和最终结果，缓冲区中的值被称为链接变量（Chaining Variable）。首先将其分别初始化为A=0x01234567，B=0x89abcdef，C=0xfedcba98，D=0x76543210。这些值以高端格式存储，即字节的最高有效位存于低地址字节位置。

（4） 以512位的分组为单位对消息进行循环散列计算，如图5.8所示，经过处理的消息，以512位为单位，分成N个分组，为Y0，Y1，…，YN-1。MD5对每个分组进行散列处理。每一轮的处理会对（A，B，C，D）进行更新。

（5） 输出散列值： 所有的N个分组消息都处理完后，最后一轮得到的4个缓冲区的值即为整个消息的散列值。



图5.8MD5主要处理过程



在第（4）步中的循环散列计算共有4轮（见图5.9），每轮循环都很相似，进行16次操作。在第1轮的第1个步骤开始处理时，将A、B和C、D的值保存在另外的单元，假设为AA、BB、CC和DD中。然后每次操作对A、B、C和D中的其中3个做1次非线性函数运算，然后将所得结果加上第4个变量、消息的一个子分组和一个常数，再将所得结果向右环移一个不定的数。最后得到的结果再加上之前保存在AA、BB、CC或DD中的值，这里的“+”指的是mod 232的模加运算。得到的新的4个32字作为A、B、C和D的新的值。然后继续使用下一分组进行运算，最后输出的A、B、C和D的级联即是整个消息的128位散列值。



图5.9MD5算法一次循环的处理过程



每次操作中用到的4个非线性函数为：


F（X，Y，Z）=（X&Y）|（（~X）&Z）
G（X，Y，Z）=（X&Z）|（Y&（~Z））
H（X，Y，Z）=X^Y^Z
I（X，Y，Z）=Y^（X|（~Z））


其中，&是与，|是或，~是非，^是异或。

将每次处理的512位的消息分组再分成32位一组，共16组，表示为Mk，k=0，…，15，则在每次的4轮运算中的计算方法是：


FF（A，B，C，D，Mj，s，ti）表示A=B+（（A+（F（B，C，D）+Mj+ti）<<<s）
GG（A，B，C，D，Mj，s，ti）表示A=B+（（A+（G（B，C，D）+Mj+ti）<<<s）
HH（A，B，C，D，Mj，s，ti）表示A=B+（（A+（H（B，C，D）+Mj+ti）<<<s）
II（A，B，C，D，Mj，s，ti）表示A=B+（（A+（I（B，C，D）+Mj+ti）<<<s）


其中“<<<s”表示循环左移s位。则4轮（每轮16步，共64步）的操作如下所示。

1） 第1轮

FF（A，B，C，D，M0，7，0xd76aa478）

FF（D，A，B，C，M1，12，0xe8c7b756）

FF（C，D，A，B，M2，17，0x242070db）

FF（B，C，D，A，M3，22，0xc1bdceee）

FF（A，B，C，D，M4，7，0xf57c0faf）

FF（D，A，B，C，M5，12，0x4787c62a）

FF（C，D，A，B，M6，17，0xa8304613）

FF（B，C，D，A，M7，22，0xfd469501）

FF（A，B，C，D，M8，7，0x698098d8）

FF（D，A，B，C，M9，12，0x8b44f7af）

FF（C，D，A，B，M10，17，0xffff5bb1）

FF（B，C，D，A，M11，22，0x895cd7be）

FF（A，B，C，D，M12，7，0x6b901122）

FF（D，A，B，C，M13，12，0xfd987193）

FF（C，D，A，B，M14，17，0xa679438e）

FF（B，C，D，A，M15，22，0x49b40821）

2） 第2轮

GG（A，B，C，D，M1，5，0xf61e2562）

GG（D，A，B，C，M6，9，0xc040b340）

GG（C，D，A，B，M11，14，0x265e5a51）

GG（B，C，D，A，M0，20，0xe9b6c7aa）

GG（A，B，C，D，M5，5，0xd62f105d）

GG（D，A，B，C，M10，9，0x02441453）

GG（C，D，A，B，M15，14，0xd8a1e681）

GG（B，C，D，A，M4，20，0xe7d3fbc8）

GG（A，B，C，D，M9，5，0x21e1cde6）

GG（D，A，B，C，M14，9，0xc33707d6）

GG（C，D，A，B，M3，14，0xf4d50d87）

GG（B，C，D，A，M8，20，0x455a14ed）

GG（A，B，C，D，M13，5，0xa9e3e905）

GG（D，A，B，C，M2，9，0xfcefa3f8）

GG（C，D，A，B，M7，14，0x676f02d9）

GG（B，C，D，A，M12，20，0x8d2a4c8a）

3） 第3轮

HH（A，B，C，D，M5，4，0xfffa3942）

HH（D，A，B，C，M8，11，0x8771f681）

HH（C，D，A，B，M11，16，0x6d9d6122）

HH（B，C，D，A，M14，23，0xfde5380c）

HH（A，B，C，D，M1，4，0xa4beea44）

HH（D，A，B，C，M4，11，0x4bdecfa9）

HH（C，D，A，B，M7，16，0xf6bb4b60）

HH（B，C，D，A，M10，23，0xbebfbc70）

HH（A，B，C，D，M13，4，0x289b7ec6）

HH（D，A，B，C，M0，11，0xeaa127fa）

HH（C，D，A，B，M3，16，0xd4ef3085）

HH（B，C，D，A，M6，23，0x04881d05）

HH（A，B，C，D，M9，4，0xd9d4d039）

HH（D，A，B，C，M12，11，0xe6db99e5）

HH（C，D，A，B，M15，16，0x1fa27cf8）

HH（B，C，D，A，M2，23，0xc4ac5665）

4） 第4轮

II（A，B，C，D，M0，6，0xf4292244）

II（D，A，B，C，M7，10，0x432aff97）

II（C，D，A，B，M14，15，0xab9423a7）

II（B，C，D，A，M5，21，0xfc93a039）

II（A，B，C，D，M12，6，0x655b59c3）

II（D，A，B，C，M3，10，0x8f0ccc92）

II（C，D，A，B，M10，15，0xffeff47d）

II（B，C，D，A，M1，21，0x85845dd1）

II（A，B，C，D，M8，6，0x6fa87e4f）

II（D，A，B，C，M15，10，0xfe2ce6e0）

II（C，D，A，B，M6，15，0xa3014314）

II（B，C，D，A，M13，21，0x4e0811a1）

II（A，B，C，D，M4，6，0xf7537e82）

II（D，A，B，C，M11，10，0xbd3af235）

II（C，D，A，B，M2，15，0x2ad7d2bb）

II（B，C，D，A，M9，21，0xeb86d391）

常数ti可以如下选择： 在第i步中，ti是232×abs（sin（i））的整数部分，i的单位是弧度。


5.3.4SHA512

美国国家标准局（NIST）为了配合数字签名标准（DSA），在1993年对外公布了安全散列函数（SHA），并公布为联邦信息处理标准（FIPS 180），其设计的方法是依据已有的MD4算法，所以其基本框架与MD4类似。1995年NIST发布了SHA的修订版（FIPS 1801），通常称之为SHA1，SHA1产生160位的散列值。2002年，NIST再次发布了修订版（FIPS 1802），其中给出了3种新的SHA版本，散列值长度依次为256、384和512位，分别称作SHA256、SHA384和SHA512（见表5.1）。这些新的版本和SHA1具有相同的基础结构，使用了相同的模算术和二元逻辑运算。2005年，NIST宣布逐步废除SHA1，转而使用SHA的其他更高位长的版本。2005年，王小云带领的研究小组研究出了一种攻击，用269次操作可以找到两个独立的消息使它们有相同的SHA1值，而以前认为要找到一个SHA1碰撞需要280次的操作，所需操作大为减少。这意味着，对于SHA的使用需要选择更高位数的版本。




表5.1SHA参数比较



参数SHA1SHA256SHA384SHA512


散列值长度160256384512
消息长度<264<264<2128<2128
分组长度51251210241024
字长度32326464
步骤数80648080
安全性80128192256

注： 

（1） 所有的长度以比特为单位。

（2） 安全性是指对输出长度为n位Hash函数的生日攻击产生碰撞的工作量大约为2n/2。


1. SHA512 算法

该算法的输入是最大长度小于2128位的消息，输出是512位的散列值，输入消息以1024位的分组为单位进行处理。输出摘要的总体过程遵循图5.10所示的一般结构。和MD5类似，其过程包含下列步骤。



图5.10SHA512主要处理过程



（1） 对消息进行填充。对原始消息进行填充使其长度与896模1024同余（即填充后的消息长度≡896 mod 1024）。即使原始消息已经满足上述长度要求，仍然需要进行填充，因此填充位数为1~1024。填充部分由一个1和后续的0组成。

（2） 添加消息长度信息。在填充后的消息后添加一个128位的块，用来说明填充前消息的长度，表示为一个无符号整数（最高有效字节在前）。至此，产生了一个长度为1024位整数倍的扩展消息。如图5.10所示，扩展的消息被表示为一串长度为1024位的消息分组Y1，Y2，…，YN，因此扩展消息的长度为N×1024位。

（3） 初始化Hash缓冲区。Hash函数计算的中间结果和最终结果保存在512位的缓冲区中，分别用64位的寄存器（A，B，C，D，E，F，G，H）表示，并将这些寄存器初始化为下列64位的整数（十六进制值）。

A＝0x6A09E667F3BCC908E=0x510E527FADE682D1

B＝0xBB67AE8584CAA73B F=0x9B05688C2B3E6C1F

C＝0x3C6EF372FE94F82BG=0x1F83D9ABFB41BD6B

D＝0xA54FF53A5F1D36F1H=0x5BE0CD19137E2179

这些值以高端格式存储，即字的最高有效字节存于低地址字节位置（最左边）。这些字的获取方式如下： 前8个素数取平方根，取分数部分的前64位。


（4） 以1024位分组（16个字）为单位处理消息。处理算法的核心是需要进行80轮运算的模块，即图5.9中的F。图5.11给出了F的逻辑原理： 每一轮都把512位缓冲区的值ABCDEFGH作为输入，并更新缓冲区的值。第1轮时，缓冲区的值是中间的Hash值Hi-1。每一轮使用一个64位的值Wt（0≤t≤79）该值由当前被处理的1024位消息分组Yi导出，导出算法是后面将要讨论的消息调度算法。每一轮还将使用常数Kt（0≤t≤79）。这些常数的获得方法： 前80个素数取3次根，取小数部分的前64位。这些常数提供了64位随机串集合，可以消除输入数据里的任何规则性。第80轮的输出和第1轮的输入Hi-1相加产生Hi。缓冲区里的8个字和Hi-1里的相应字独立进行模264的加法运算。



图5.11SHA512每一步的核心处理


（5） 输出。所有的N个1024位分组都处理完以后，最后输出的即是512位的消息散列值。

从总体上看，SHA512的运算如下所示。


H0=IV
Hi=SUM64（Hi-1， ABCDEFGHi）
MD=HN


其中，IV为上述算法第（3）步里定义的ABCDEFGH缓冲区的初始值； ABCDEFGHi为第i个消息分组处理的最后一轮的输出； N为消息（包括填充和长度域）里的分组数； SUM64为对输入对里的每个字进行独立的模264加； MD为最后的消息散列值。

2. 消息调度处理

每一轮的Wt（0≤t≤79）的值由当前被处理的1024位消息分组Yi导出。其导出算法如图5.12所示，前16个Wt（0≤t≤15）直接取自当前消息分组的16个字。余下的值按如下方式导出： 


Wt=σ5121（Wt-2）+Wt-7+σ5120（Wt-15）+Wt-16


其中，σ5120（x）=ROTR1（x）+ROTR8（x）+SHR7（x）。


σ5121（x）=ROTR19（x）+ROTR61（x）+SHR6（x）。



ROTRn（x）=对64位的变量x循环右移n位。

SHRn（x）=对64位变量x向左移动n位，右边填充0。

因此，在前16步处理过程中，Wt的值等于消息分组里的相应字。对于余下的64步，Wt的值由其前面的4个值的异或形成的值构成，要对4个值中的两个进行移位和循环移位操作。



图5.12SHA512每步操作中的消息调度处理


3. SHA512的轮函数

SHA512中最核心的处理就是对单个512分组处理的80轮的每一轮的处理，其运算方法如下所示。


T1=h+Ch（e，f，g）+∑5121e+Wt+Kt
T2=∑5120a+Maj（a，b，c）
a=T1+T2
b=a
c=b
d=c
e=d+T1
f=e
g=f
h=g


其中： 

 t为步骤数，0≤t≤79。

 Ch（e，f，g）=（e AND f）（NOT e AND g）条件函数，如果e，则f，否则g。

 Maj（a，b，c）=（a AND b）（a AND c）（b AND c），函数为真，仅当变量的多数（2或3）为真。

 ∑5120 a＝ROTR28（a）ROTR34（a）ROTR39（a）。

 ∑5121 e=ROTR14（e）ROTR18（e）ROTR41（e）。

 Wt为64位，从当前的512位消息分组导出。

 Kt为64位常数。

 “＋”为模264加。

5.3.5HMAC

Hash函数是不使用密钥的，不能像MAC一样使用。正如第5.2节所讨论的，MAC是主要基于对称密码算法设计的，如第5.2.2节中讨论的MAC算法。但目前，研究者提出了一些将Hash函数用于构建MAC算法的方案。HMAC是其中之一，并已经成为FIPS标准发布（FIPS 198），后被使用于IPSec和SSL协议中。

1. HMAC的设计目标

HMAC的设计目标如下。

 可以直接使用现有的Hash函数。

 不针对某个Hash函数，可以根据需要更换Hash函数模块。

 可保持Hash函数的原有性能，不能过分降低其性能。

 对密钥的使用和处理应较简单。

 如果已知嵌入的Hash函数的强度，则可以知道认证机制抵抗密码分析的强度。


图5.13HMAC的结构

因此，HMAC中使用的Hash函数并不局限于某一种Hash函数，所以使用不同的Hash函数，HMAC将有不同的实现，如HMACSHA、HMACMD5等。

2. HMAC算法

 	图5.13给出了HMAC的总体结构，其中的符号定义如下所示。


 H： 嵌入的Hash函数（如MD5、SHA1、RIPEMD160）。

 IV： 作为Hash函数输入的初始值。

 M： HMAC的消息输入（包括使用的Hash函数中定义的填充位）。

 Yi： M的第i个分组，0≤i≤L-1。

 L： M中的分组数。


 b： 每一分组所含的位数。

 n： 使用的Hash函数所产生的散列值的位长。

 K： 密钥，建议密钥长度大于n。若密钥长度大于b，则将密钥作为Hash函数的输入以产生一个n位的密钥。

 K+： 为使K为b位长而在K左边填充0后所得的结果。

 ipad： 00110110（十六进制数36）重复b/8次的结果。

 opad： 01011100（十六进制数5C）重复b/8次的结果。

HMAC可描述为：

HMACK=H［（K+opad）‖H［（K+ipad）‖M］］

算法的处理流程如下所示。

（1） 在密钥K后面填充0，得到b位的K+（例如，若K是160位，b=512，则在K中加入44个0字节0×00）。

（2） K+与ipad执行异或运算（位异或）产生b位的分组Si。

（3） 将M附于Si后。

（4） 将H作用于第（3）步所得的结果。

（5） K+与opad执行异或运算（位异或）产生b位的分组S0。

（6） 将第（4）步中的散列值附于S0后。

（7） 将H作用于第（6）步所得出的结果，输出最终结果。

在上述操作中，K与ipad异或后，其信息位有一半发生了变化； 同样，K与opad异或后，其信息位的另一半也发生了变化，这样，通过将Si与S0传给Hash算法中的压缩函数，可以从K伪随机地产生出两个密钥。


如图5.14所示，为了有效地实现HMAC，HMAC中多执行的3次Hash运算（对Si、So和H（Si‖M））可以采用预计算的方式先求出下面的值。



图5.14HMAC的实现方案





f（IV，（K+ipad））
f（IV，（K+opad））


其中f（cv，block）是Hash函数中的压缩函数，其输入是n位的链接值和b位的消息分组，输出是n位的链接变量。上述这些值只在初始化或密钥改变时才需要计算。实际上，这些预先计算的值取代了Hash函数中的初始值IV。这样的处理方式使得HMAC只需要多执行一次压缩函数，但这种处理方式只有在对较长消息处理的时候可以显示出效果，对于较短的消息处理，则没有太大意义。


5.4数 字 签 名
5.4.1数字签名的基本概念

前面章节讨论的消息认证方法主要是保护通信双方之间的消息不被第三方篡改，但却无法防止通信双方互相欺骗。例如在下面的情形中，通信双方会产生某些纠纷。

（1） 在通信中，通信方A和B是通过共享的秘密钥对传输的消息计算MAC以提供认证。这样B可以伪造一个消息，并使用共享的密钥对其生成MAC，然后声称这个消息来自A。

（2） A否认曾经发送过某条消息给B，但事后他可以辩称B收到的这条消息是B伪造的，即否认自己的行为。

（3） B收到A发送的某条消息后，出于某种原因，他否认收到过这条消息。

在上述情形中，由于通信方存在互不信任的情况，单纯地使用签名讨论的消息认证方法无法解决这些问题。数字签名是解决这些问题的最好选择，数字签名主要的功能是保证信息传输的完整性、发送方的身份认证、防止交易中发生否认现象。简单地说，数字签名技术可以解决如下问题。

 否认： 发送方否认发送过或签名过某条消息。

 伪造： 用户A伪造一份消息，并声称该消息来自B。

 冒充： 用户A冒充其他用户接收或发送报文。

 篡改： 消息接收方对收到的消息进行篡改。
数字签名也是一种认证机制，它是公钥密码学发展过程中的一个重要组成部分，是公钥密码算法的典型应用。数字签名的应用过程是，数据源发送方使用自己的私钥对数据校验和（或）其他与数据内容有关的信息进行处理，完成对数据的合法“签名”，数据接收方则利用发送方的公钥来验证收到的消息上的“数字签名”，以确认签名的合法性。

数字签名需要满足以下条件。

 签名的结果必须是与被签名的消息相关的二进制位串。

 签名必须使用发送方某些独有的信息（发送方的私钥），以防伪造和否认。

 产生数字签名比较容易。

 识别和验证签名比较容易。

 给定数字签名和被签名的消息，伪造数字签名在计算上是不可行的。

 保存数字签名的副本，并由第三方进行仲裁是可行的。
数字签名的典型使用方法如下（见图5.6（a））。

（1） 发送方计算消息的哈希值。

（2） 发送方使用自己的私钥对消息散列值进行计算，得到一个较短的数字签名串。

（3） 这个数字签名将和消息一起发送给接收方。

（4） 接收方首先从接收到的消息中用同样的散列函数计算出一个消息摘要，然后使用这个消息摘要、发送方的公钥以及收到的数字签名，进行数字签名合法性的验证。

数字签名技术是在网络虚拟环境中确认身份、提供消息完整性和保证消息来源的重要技术，可以提供和现实中的“亲笔签字”类似的效果，在技术和法律上都有保证。数字签名通常和Hash函数结合使用，用来向用户提供安全高效的数字签名的方法，被广泛应用在各种认证协议中和网络应用中，如电子商务中安全、方便的电子支付、数据传输的完整性、身份验证机制以及交易的不可否认性的实现。

5.4.2数字签名方案

本节给出一些常见的数字签名方案及数字签名的应用。

1. Schnorr数字签名

1989年，Schnorr提出一签名算法，其算法安全性基于求解离散对数难题。

算法描述如下所示。

（1） 系统参数的选择。

p和q： 满足q|p-1，q≥2160，q≥2512。

g： g∈Zp，满足gq=1 mod p，g≠ 1。

H： 为散列函数。

x： 为用户的私钥，1<x<q。

y： 为用户的公钥，y=gx mod p。

（2） 签名。

设要签名的消息为M，0<M<p。签名者随机选择一整数k，1<k<q，并计算： 


e=H（r，M）
s=k-xe mod q


（e，s）即为M的签名。签名者将M 连同（r，s）一起存放，或发送给验证者。

（3） 验证。

验证者获得M和（e，s），需要验证（e，s）是否是M的签名。

计算： 


r′=gsre mod p


检查H（r′，M）=e是否成立，若成立，则（e，s）为M的合法签名。

2. 数字签名标准（DSS）

1991年，美国国家标准局（NIST）发布了数字签名标准（FIPS PUB186），简称DSS（Digital Signature Standard）。DSS采用了SHA散列算法，给出了一种新的数字签名方法，即数字签名算法（DSA）。DSS被提出后，1996年又被稍做修改，2000年发布了该标准的扩充版，即FIP 1862。DSA的安全性是建立在求解离散对数难题之上的，算法基于ElGamal和Schnorr签名算法，其后面发布的最新版本还包括基于RSA和椭圆曲线密码的数字签名算法。这里给出的算法是最初的DSA算法。

DSA只提供数字签名功能的算法，虽然它是一种公钥密码机制，但是不能像RSA和ECC算法那样还可以用于加密或密钥分配。

DSS方法使用Hash函数产生消息的散列值，和随机生成的k作为签名函数的输入，签名函数依赖于发送方的私钥（PRA）和一组参数，这些参数为一组通信伙伴所共有，我们可以认为这组参数构成全局公钥PUG。签名由两部分组成，标记为r和s。

接收方对收到的消息计算散列值，和收到的签名（r，s）一起作为验证函数的输入，验证函数依赖于全局公钥和发送方公钥，若验证函数的输出等于签名中的r，则签名合法。

DSA算法的具体描述如下所示（见图5.15）。



图5.15DSS签名算法


（1） DSA的系统参数的选择如下所示。

p： 512的素数，其中2L-1<p<2L，512≤L≤1024，且L是64的倍数，即L的位长为512~1024位并且其增量为64位。

q： 160位的素数且q|p-1。

g： 满足g=h（p-1）/q mod p。

H： 为散列函数。

x： 为用户的私钥，0<x<q。

y： 为用户的公钥，y=gx mod p。

p、q、g为系统发布的公共参数，与公钥y公开； 私钥x保密。

（2） 签名。

设要签名的消息为M，0<M<p。签名者随机选择一整数k，0<k<q，并计算： 


r=（gk mod p） mod q
s=［k-1（H（M）+xr）］ mod q


（r，s）即为M的签名。签名者将M 连同（r，s）一起存放，或发送给验证者。

（3） 验证。

验证者获得M和（r，s），需要验证（r，s）是否是M的签名。

首先检查r和s是否属于［0，q］，若不属于，则（r，s）不是签名值。

否则，计算： 


w=s-1 mod q
u1=（H（M）w） mod q
u2=rw mod q
v=（（gu1yu2） mod p） mod q


如果v=r，则所获得的（r，s）是M的合法签名。

在DSA中，签名者和验证者都需要进行一次模q的求逆运算，这个运算是比较耗时的。Yen和Laih提出了两种改进的方法，可以免去签名者或验证者的求逆运算，其方法如下所示。

（1） DSA改进方法1。

签名： r=（gk mod p） mod q

s=（rk-H（M））x-1 mod q

验证： t=r-1 mod q

v=（gh（M）t yst mod p） mod q

判断v是否和r相等。

（2） DSA改进方法2。

签名： r=（gk mod p） mod q

s=（k（H（M）+xr）-1） mod q


验证： t=sH（M） mod q

v=（gtysr mod p） mod q


判断v是否和r相等。

在上述方法中，有些计算可以预先完成。在改进方法1中，签名时会用到的x-1，如果x不是经常更换，则x-1可以预先计算并保存以便多次使用，这样就可以省掉一次求逆运算。在改进方法2中，验证者无须计算逆元。即便对于初始DSA，也可以采用预计算的方法提高效率： 签名时所计算的gk mod p并不依赖于消息，因此可以预先计算出。用户还可以根据需要预先计算出多个可用于签名的r，以及相应的r-1，这样可以大大提高效率。

以上给出的签名方案是直接数字签名，或称为普通数字签名，包括RSA、Schnorr、DSA、ECC、FiatShamir、GuillouQuisquarter、OngSchnorrShamir等数字签名算法。这类数字签名只涉及通信双方，即签名方使用自己的私钥对整个消息或者对于消息的散列值进行签名，验证者使用签名者的公钥进行验证。即便发生纠纷，仲裁法也是根据密钥及签名值进行仲裁。该方案的有效性完全依赖于签名方的私钥。如果签名者的私钥丢失或者被攻击者获取，则有可能被他人伪造签名，这时产生纠纷后，仲裁者无法给出实时的判断。因此，在实际应用中，除了普通数字签名外，还有些特殊的签名方案，更多的可以说是一种安全协议，如仲裁数字签名、盲签名、代理签名、多重签名、不可否认签名、公平盲签名、门限签名、具有消息恢复功能的签名等，它们与具体应用环境密切相关。

3. 仲裁数字签名

仲裁签名中除了通信双方外，还有一个仲裁方。发送方A发送给B的每条签名的消息都先发送给仲裁者T，T对消息及其签名进行检查以验证消息源及其内容，检查无误后给消息加上日期再发送给B，同时指明该消息已通过仲裁者的检验。因此，仲裁数字签名实际上涉及多余一步的处理，仲裁者的加入使得对于消息的验证具有实时性。

下面是使用对称密码的仲裁签名的例子。

（1）  A→T： M‖EKAT［IDA‖H（M）］。

（2）  T→B： EKTB［IDA‖M‖EKAT［IDA‖H（M）］‖T］。

在这个例子中，签名采用的是对消息的加密处理，即整个密文就是消息的签名： 发送方A和仲裁者T共享密钥KAT，A和B共享密钥KAB。A产生消息M并计算出其散列值H（M），然后将消息M及其签名发送给T，其签名由A的标识IDA和消息散列值组成，并且用KAT加密。A对签名解密后，通过检查散列值来验证该消息的有效性，然后T用KTB对IDA、来自A的原始消息M、来自A的签名和时间戳加密后传给B。B对T发来的消息解密即可恢复消息M和签名。B检查时间戳以确定该消息是实时的、而不是重放的消息。B可以存储M及其签名，如果和A发生争执，则B可将下列消息发给T以证明曾收到过来自A的消息： EKTB［IDA‖M‖EKAT［IDA‖H（M）］‖T］。


下面是使用公钥密码体制的签名，并且仲裁者不能阅读消息，只能仲裁发送方的行为。

（1） A→T： IDA‖EPRA［IDA‖EPUB（EPRA［M］）］。

（2） T→B： EPRT［IDA‖EPUB［EPRA［M］］‖T］。

发送方A首先使用自己的私钥对消息进行签名，然后再使用接收方B的公钥对消息及签名进行加密，A再次使用自己的私钥对连同标识和密文的内容进行签名。仲裁者收到消息后，使用A的公钥验证外层签名的合法性，但是无法获得原始消息M的内容。如果签名合法，仲裁方对密文消息加上时间戳，并使用自己的私钥进行签名，并发送给B。B收到后可以验证仲裁方的签名以及消息的实时性，并使用自己的私钥对密文进行解密，再使用A的公钥验证解密后的消息中的签名，以判断消息的合法性。B可以保存第（2）步中的消息，如果和A产生纠纷，则可以作为证据提供给仲裁方。

和前面一个方案相比，采用公钥密码的方案可以更有效地保护发送方和接收方的利益，因为在前面的方案中，仲裁者可以看到消息的内容，可能和接收方勾结欺骗发送方，也可能和发送方勾结欺骗接收方，而这个方案中，仲裁者看不到消息的内容，并且也无法进行联合欺骗。

4. 盲签名

盲签名是Chaum在1982年首次提出的，Chaum利用盲签名技术提出了第一个电子现金方案。盲签名因为具有盲性这一特点，可以有效地保护所签名的消息的具体内容，所以在电子商务等领域有着广泛的应用。

盲签名允许消息发送方先将消息盲化，而后让签名者对盲化的消息进行签名，最后消息拥有者对签名除去盲因子，得到签名者关于原消息的签名。消息发送方可以使用盲签名让签名者对给定的消息进行签名，但不泄露关于消息和消息签名的任何信息。它除了满足一般的数字签名条件外，还必须拥有如下所示的两条性质。

（1） 签名者不知道其所签名的消息的具体内容。

（2） 签名消息不可追踪，即当签名消息被公布后，签名者无法知道这是他哪次签署的。

关于盲签名，我们曾经给出了一个非常直观的说明： 所谓盲签名，就是先将隐蔽的文件放进信封里，而除去盲因子的过程就是打开这个信封，当文件在一个信封中时，任何人都不能阅读它。文件签名就是通过在信封里放一张复写纸，签名者在信封上签名时，他的签名便透过复写纸签到文件上。

A期望获得对消息m的签名，B对消息m的盲签名实现的描述如下所示。

（1） 盲化： A对于消息进行处理，使用盲因子合成新的消息M并发给B。

（2） 签名： B对消息M签名后，将签名（M，sign（M）） 返回给A。

（3） 去盲： A去掉盲因子，从对M的签名中得到B对m的签名。

一般来说，一个好的盲签名应该具有以下的性质。

（1） 不可伪造性。除了签名者本人外，任何人都不能以他的名义生成有效的盲签名。

（2） 不可否认性。签名者一旦签署了某个消息，他无法否认自己对消息的签名。

（3） 盲性。签名者虽然对某个消息进行了签名，但他不可能得到消息的具体内容。

（4） 不可跟踪性。一旦消息的签名被公开后，签名者不能确定自己何时签署的这条消息。也就是说，即使签名者存储了盲消息M和相应的签名sign（M），等到m和其签名sign（m）公布后，他也无法找出（m，sign（m））和（M，sign（M））之间的联系。

不满足上述第（4）条的盲签名方案成为弱盲签名方案，否则称为强盲签名方案。这4条性质既是我们设计盲签名所应遵循的安全标准，又是我们判断盲签名性能优劣的根据。

自Chaum提出首个基于大整数分解难题上的盲签名方案后，研究者陆续提出了基于离散对数的盲签名方案、基于二项剩余的盲签名方案、基于ElGamal且具有匿名性的盲签名方案、群盲签名方案、基于比特承诺的盲签名等。

利用盲签名技术可以保护用户的隐私权，因此，盲签名技术在诸多电子支付、电子现金方案中被广泛使用。盲数字签名技术在充分保护用户隐私的同时，也为不法分子提供了可乘之机，他们利用电子现金的完全匿名性特点进行欺骗等违法犯罪活动。1995年M.Stadler、J.M.Piveteau和J.Camenischt提出了公平盲签名的概念，可用于条件匿名支付系统，在一定程度上消除了电子现金极端匿名性带来的负面影响。

5. 代理签名

代理签名的目的是当某签名人因某种原因不能行使签名权力时，将签名权委派给其他人替自己行使签名权。由原始签名者（部分）授权代理签名者，使代理签名者产生代替原始签名的签名就是代理数字签名。这个概念是由Mambo、Usada和Okamoto于1996年首先提出的，并且给出了一个代理签名方案（下面简称为MUO方案）。

MUO代理数字签名方案描述如下所示。

系统参数： p是一个大素数，q为p-1的大素因子，g∈Z*p，且gq≡1 mod p。原始签名者A、代理签名者B的私钥为PRA、PRB∈{1，2，…，q-1 }； 公钥分别为PUA=gPUA mod p、PUA=gPUB mod p。代理签名步骤如下所示。

（1） 产生代理密钥： A随机选择一个数k∈Z*p，计算r=gk mod p，然后计算代理签名密钥s=（PRA+kr）mod q。

（2） 代理密钥的传递： A将（s，r）以安全的方式发送给B。

（3） 代理密钥的验证： B检查等式gs=PUArr mod p是否成立，如果成立则接受，否则拒绝。

（4） 代理签名者对消息签名： 对于消息m，B将s作为新的私钥（替代PRA）使用签名算法产生对m的签名sp=sig（s，m），然后将（sp，r）作为他代表A对于消息m的数字签名（即代理签名）。

（5） 对代理签名的验证： 接收方收到消息m和代理签名（sp，r），验证ver（PUA，（sp，r），m）=true，是否成立，如果成立则认为代理签名成立，否则拒绝。

也就是说，在上述签名方案中，A并没有泄露自己的私钥，但是通过计算为B生成了一对代理公私钥对，设为（PRB，PUB），其中PRB=s，PRB=gs mod q。在B代理签名中，将利用这对密钥对对消息进行签名。

现在已经出现了一些基于离散对数和素因子分解问题的代理签名方案。在这些代理签名方案中，假设A委托B进行代理签名，则签名必须满足以下3个最基本的条件。

（1） 签名接收方能够像验证A的签名那样验证B的签名。

（2） A的签名和B的签名应当完全不同，并且容易区分。

（3） A和B对签名事实不可否认。


5.5关 键 术 语

消息认证码（Message Authentication Code，MAC）

散列函数（也称杂凑函数）（Hash Function）	

散列消息认证码（Hashed Message Authentication Code，HMAC）

安全散列函数（Secure Hash Function，SHF）

数字签名标准（Digital Signature Standard，DSS）

数字签名（Digital Signature）	

盲签名（Blind Signature）

习题5

5.1为什么需要消息认证？

5.2SHA中使用的基本算术和逻辑函数是什么？

5.3一个安全的散列函数需要满足的特性有哪些？

5.4什么是生日攻击？

5.5散列函数和消息认证码有什么区别？各自可以提供什么功能？

5.6数字签名和散列函数的应用有什么不同？

5.7数字签名需要满足哪些条件？

5.8说出几种数字签名技术，并分析其优缺点。