第五章 数字签名

5.1数字签名 政治、军事、外交、商业以及日常事物经常出现需要签名的场合。签名的作用是核准后认可并且生效。随着信息时代的到来，人们希望能通过网络信息传输对文件、契约、合同、信件、帐单等进行数字签名(Digital Signature)，从而代替面对面的手写签名。实际上数字签名是一种证明签名者身份和所签署内容真实性的一段信息。

手写签名与数字签名的区别： 1）手写签名是所签的文件的物理组成部分。数字签名必须与所签文件捆绑在一起 2 验证手写签名通过与标准签名比较或检查笔迹来实现，伪造签名比较容易。数字签名通过公开的验证(Verification)算法。好的数字签名(Signing)算法应该使得伪造(Forgery)签名十分困难 3）手写签名不易复制。数字签名是一个二进制信息，复制十分容易，所以必须防止数字签名重复使用

数字签名算法必须满足的条件 一般，数字签名算法必须满足： l         签名者事后不能否认自己的签名 l        任何他人不能伪造签名 l         当双方为签名真伪发生争执时，可以由第 三方解决争端

签名算法的分类 l         按目的可以把数字签名分成普通数字签名和特殊目的的数字签名（如不可否认签名、盲签、群签等）。前者由签名算法(Digital Signature Generation Algorithm)和验证算法(Digital Signature Verification Algorithm)组成。而后者还需要有附加的部件。 l         按验证方法可分成：在验证时需要输入被签信息和在验证中自动恢复被签信息两类 l         按是否使用随机数可分成：确定的和随机的两种签名算法

数字签名的应用 1）在把被签的数据格式化(Formatting Data)成可签的消息之后，签名者使用签名算法生成数字签名。接收者接到数字签名使用验证算法验证签名的真实性。最后从消息恢复成为数据(Recovering Data). 2）在信息安全中，数字签名有许多应用如认证、数据完整性和不可否认性。主要的应用之一是大型网络中的“公钥证书”。所谓证书是由一个可信第三方(Trusted Third Party, 简称TTP)把用户身份标识与用户公钥绑在一起的一种手段。其他用户不需要TTP帮助，自己就可以认证一个公钥。

5.2 RSA数字签名 密钥生成 p, q是两个不同的大素数，n=pq， 任取b满足gcd(b,φ(n))=1。 求b模的φ(n)逆a，即ab=1mod(φ(n)) n,b是签名者的RSA公钥, p,q,a 是签名者的RSA 私钥,

数字签名 验证签名算法 数字签名算法: Sigk(x)=xamod n 验证签名算法: Verk(x,y)=true x=yk mod n

用私钥解密x’和z，求出A的签名 信息发送者除了签名表示对此信息负责外还要求保密传送 该信息，可以将消息x和签名用对方公钥加密后传送。过程 如下图所示   发送者 接收者 公钥 nA bA, 公钥 nB bB, 私钥pA qA aA， 私钥pB qB aB 计算 z=(x aAmod nA ) bB mod nB 用私钥解密x’和z，求出A的签名 和x并验证

注意： 1）  由于RSA签名能自动恢复被加密的消息。上面不必计算和传送。 2）  这里的顺序是十分重要的。如果先加密再签名，则可能受到伪装攻击。假设发送者发送z=(x bB mod nB) aA mod nA 。敌手C截获z，利用A的公钥和自己的私钥在不知道明文的情况下计算自己对密文的签 名 发给接收者B。B将会认为消息是C发送过来的。

RSA签名算法的弱点 l         任何人都可以伪造某签名者对于随机信息x的签名y, 。其方法是先选y，用某签名者的公钥n,b计算x=yb mod n, y就是某签名者对信息x的签名 l         若敌手掌握某签名者对信息x1,x2的签名分别是y1,y2，则可以伪造x1x2的签名y1y2 l         对长的信息签名要分成若干长为[log2 n]的组分别进行签名，运算量极大。（可通过使用哈希函数解决）

5.2.2 RSA的重新分组问题 前面讲过，通常会把RSA签名经加密后传给对方。 对方使用自己的私钥和发送方的公钥可以直接恢 复信息。这里需要认真对待模数大小的问题。令 A的公钥nA,bA，B的公钥nB,bB且 nA>nB 。A加密 一个信息传送给B，有可能B不能恢复出原来的消 息。 例如：

A计算 (> 55465219), 发送给B B计算 出现不能恢复明文的概率为

解决这个问题的方法有两个。第一个方法是为每个实体生成两组公私钥对，分别用于加密和签名。公钥中的两个模数，加密模数有t+1位，签名模数为t位。显然这个方法要付出空间代价。第二个方法是规定模数的形式， , 使出现上述问题的概率减小.具体做法是: 选一个 位的随机素数p; 选另一个素数满足 ,使得 ,例如 k=3,n是12位二进制数 取 是6位二进制数

取q=59. 假设 具有上述形式， 是A对x的签名，y< 。这时并不能保证B正确解密，只是把不能正确解密的概率降到足够小。这里有两种可能 : 1）y 的最左一位为0，则y的形式必为 显然y小于具有这种形式的其它模数。 2）y 的最左一位为1，因y<nA，所以1后面的位全为0。这样的有可能大于对方的模数。但这样的y在整体中只占2-k。当k比较大时（如 k=100），这个概率可以忽略不计。

5.3改进的Rabin签名算法 公钥生成 1）选随机素数 p=3mod 8，q=7mod 8，令n=pq， 称n是Williams数。 2）n是公钥，私钥 d= (n-p-q-5)/8 签名算法 1）计算 2）计算Jacobi数J = 3）当J = 1时，对的签名是 mod n 当J = -1时，对的签名是 mod n 验证算法1）得到签名者的公钥 n 2）计算

3) 4) 验证 是否以0110结尾。如果不是，则拒绝。否则 s是对明文m的Rabin签名。 注： 1）这里有 。从 知 当 时

且 ，故 当 是， 有 故 。

2）使用改进的Rabin签名算法，我们从来不会对 Jacobi数为-1的信息v签名。否则 ， 。而v2是模n的二次剩余， 。又 ，所以 不成立。由此可推断 或 q，即导致分解 n。

例如： 要签名的信息 m=12， 对信息 m的 Rabin 签名 。 下面验证签名。计算 ，因 ， 它的二进 制形式为：11000110，明文为 S是对明文m的 Rabin签名。