数字签名机制

在很长一段时间内，由于姓名很容易被伪造，因此，人们无法将姓名签署在电子文件之上。例如：假设通信双方只有Alice和Bob，且他们之间共享一个公共密钥，如此一来，Alice就可以使用该密钥加密整个文件，而Bob也知道此文件是来自Alice，但因为该密钥只有他和Alice知道，因此，Bob并不能知道他所得到的密文是否完整。也许Oscar已经剪切了部分密文，从而导致虽然Bob仍然可以解密密文，但得到的却是错误的信息。另外，在许多情况下，可能需要几个人来验证数字签名，但如前文所述，分发密钥却是一件非常困难的事情。

因此，公开密钥系统的思想被运用到了数字签名之中。签名机制（Signature Schemes）被用于创建一个电子签名，使得其他实体只能验证签名而不能伪造签名。因此，签名机制包括两个以下部分：签名算法（Signing Algorithm）和验证算法（Verification Algorithm）。在签名机制中，当Alice想发送一个消息x给Bob时，她要发送一对（x,sig(x)）给Bob。Bob可以通过检查sig(x)是否正确，从而决定是否接收x。而攻击者Oscar则是想要伪造一个消息（y, z），并希望Bob以为消息y是Alice发来的，从而会接收此消息y。

基于以上描述，可以给出数字签名的正式定义如下：

定义8.1：数字签名是一个五元组（P, A, K, S, V），其满足下列条件：

（1）P是可能的消息的有限集；

（2）A是可能的签名的有限集；

（3）K是密钥空间，即一个可能的密钥的有限集；

（4）对每一个密钥K∈K，存在一个签名算法sigK∈S和一个对应的验证算法verK∈V。函数sigK: |→A和verK: P×A|→{True, False}满足下列等式，对每个消息x∈P和每个签名y∈A，有：

通常，密钥K∈K包括一对密钥，其中一个是公钥（Public Key），另一个是私钥（Secret Key）。签名机制的安全性要求verK是公开已知的，而对于任意的x∈P，在私钥未知的情况下很难伪造sigK。

1.RSA签名机制

RSA签名机制是基于RSA公开密钥系统的，其实现步骤见表8.6。

表8.6　RSA签名机制实现步骤

实际上，RSA签名机制使用RSA的解密函数作为sigK，使用RSA的加密函数作为verK，由于RSA的加密和解密函数是对称的，因此，很容易证明RSA签名机制的正确性。

下面考虑一些可能的针对RSA签名机制的攻击，数字签名的正确性基于如何阻止伪造签名。对RSA签名机制来说，Oscar可以通过如下方式来伪造一个Alice的签名：因为verK是公开的，对某些y值，Oscar可以计算出x=verK(y)=yb (mod n)，并将(x, y)发送给Bob。事实上，验证算法的计算结果是True，Bob就会把此签名当作是Alice的签名。然而，当给定x, b, n时，很难找出一个y使得x=yb (mod n)是有意义的，因此，Oscar很难找出一个y使得x=yb (mod n)是有意义的，故这种类型的攻击就没多大作用。

另一个可能的攻击来自RSA签名机制的一个属性，即sigK(x)·sigK(y)=sigK(xy)。因此，若Oscar获得了(x, sigK(x))和(y, sigK(y))，则可将(xy, sigK(x)·sigK(y))发送给Bob；若xy是有意义的，则Bob就会接受它。

对一个签名机制，Oscar总可以使用下列攻击：Oscar要求Alice签署几个消息(x1,y1), (x2,y2),…, (xt,yt)，其中yi=sigK(xi),i=1,2,…,t，则Oscar发送一个子集给Bob(xj1,yj1), (xj2,yj2),…, (xj3,yj3)。如果验证算法输出总是为True，则Bob就可以接收此消息了。通过选择xj1,xj2,…, xj 3，Oscar可以发送一些错误信息给Bob，而Bob将会认为这些信息是Alice发来的。为了避免这种类型的攻击，可以使用哈希函数或者MAC的办法（见8.5.2节），另一个可行的办法则是对消息xi进行加密。

注意到消息x在签名机制中是不加密的，为了保持消息的秘密性，则必须加密消息。在这种情况下，可在加密前签署消息x来避免可能来自Oscar的攻击。事实上，假设Alice首先加密消息x得到密文y，再签署y，z=sigAlice(y)。最后将(y,z)发送给Bob。若Oscar在中途截获了(y,z)，则可用z′=sigOscar(y)来代替z，然后再将(y, z′)传给Bob。Bob验证消息并认为明文x是源自Oscar的，因此，Alice通常加密(x, sigAlice(x))，并将密文发送给Bob。当Bob接收到密文后，将首先对其进行解密得到(x, sigAlice(x))，然后再验证签名。

2.ElGamal签名机制

ElGamal签名机制是基于ElGamal公开密钥系统的，其运用也很广泛，其实现原理见表8.7。

表8.7　ElGamal签名机制实现步骤

ElGamal签名机制的正确性可证明如下：

这里使用了一个事实，即

因此有

与ElGamal公钥加密相似，随机数k应该保持秘密性。如果Oscar知道了k，则可很容易能找出密钥a：

另外，不能使用相同的k来签署两个不同的信息。如果k被用来签署两个不同的消息x1 和x2，则Oscar可知：

且

因此，Oscar可计算出：

因此有：

这样一来，Oscar通过使用数论的知识即可找出k和密钥a。

Oscar可能使用的另一种攻击与前面讨论过的针对RSA签名机制的攻击类似。Oscar选择两个数u, v，满足gcd(v, p-1)=1。设：

因为βγγδ≡αuδ ，这样就很容易验证(γ,δ)是否是x=uδ的有效签名。而Oscar却很难找出一个有用的x值。

3. 数字签名标准

数字签名标准DSS（Digital Signature Standard）发表于1994年，是由ElGamal签名机制修改而来，其具体实现步骤见表8.8。

表8.8　DSS签名机制实现步骤

DSS对ElGamal签名机制最重要的修改就是使用了的子群Zq，这样签名的程度就缩小到了320位（在ElGamal签名机制中至少1024位）。另外，主要的计算仍然采用了512位模运算，与ElGamal相同。

下面举例说明DSS。

例如：设q=29，p=29×8+1=233，h=3，则：

α=38=6 561≡37 (mod 233)

因此P=，A=Z29×Z29。设a =2，且

β=αa=372≡204 mod 233

其中，p，q，α和β是公开的，而a是私有的。

假设密文x=10，随机数为k=4（1≤k≤28），签名为sigK(10,4)= (γ,δ)，其中：

γ=(374 mod 233) mod 29

≡(2042 mod 233) mod 29

≡142 mod 29

且

δ=(10+2*26)*4−1 mod 29

≡4*4−1 mod 29

=1

则当x=10时，签名为（26, 1）。

为了计算verK(x,γ,δ)= verK(10,26,1)，有：

e1≡10*1−1 mod 29 =10

e2≡26*1−1 mod 29 =26

(3710*20426 mod 233) mod 29≡(74*46 mod 233) mod 29

≡142 mod 29

=26

=γ

因此，验证算法的输出为True。

还有其他几种数字签名机制，基本上从一个公开密钥系统就能够找出一个签名机制来。目前，运用最广泛的签名机制是椭圆曲线数字签名算法（Elliptic Curve Digital Signature Algorithm）。