第八章-数字签名.ppt

1、,手写签名:Alice对一个文档利用手写签名后, 人们就可以验证她的签名,并且其他人很难模仿她的签名.,数字签名(digital signature),也称电子签名,就是对电子文档利用电子手段进行签名,电子签名必须至少具备手写签名的两个性质,即可验证性与不可伪造性.,！公钥密码体制可提供数字签名: 用私 钥d对文档签名， 用公钥e对签名进行验证。,一个数字签名方案包括3个部分 (1)密钥生成:产生公钥与私钥如公钥密码体制; (2)签名算法:利用私钥对文档签名; (3)验证算法:利用公钥对签名进行验证.,教科书式RSA数字签名 (1)密钥生成如RSA密码体制：n=pq,ed1mod(p-1)(q

2、- 1),(n,e)是Alice的公钥,d是Alice的私钥; (2)签名算法:对文档mZn,Alice计算s=md mod n，s就是Alice对文档m的签名(这里的签名就是RSA的解密程序); (3)验证算法:任何人在收到(m,s)后,可利用Alice的公钥验证签名,只要计算se modn,看结果是否等于m,若相等,则签名是Alice的合法签名; 若不相等,则签名非法.,8.2 数字签名的安全性 安全模型 (1) 攻击目标 完全攻破(total break)：Oscar找到私钥d. UB:Unbreakability 泛伪造(universal forgery)：Oscar可以对任何文档

3、产生合法的签名,即能通过验证算法的签名. UU:Universal Unforgeability 选择性伪造(selective forgery):Oscar能以不可忽略的概率对另外某个人选择的文档产生一个合法的签名. SU: Selective Unforgeability 存在性伪造(existential forgery):Oscar至少能为一 则文档签名. EU:Existential Unforgeability,(2) 攻击类型 唯密钥攻击(key only attack):Oscar只拥有公钥. KOA 已知消息攻击(known message attack):Oscar拥有一些

4、消息与相应的签名. KMA 选择消息攻击(chosen message attack):Oscar可以请求Alice对他选择的任意消息签名. CMA,安全模型关系图 EU SU UU UB KOA KMA CMA,！数字签名设计的最高安全要求是：设计的数字签名方案在选择消息攻击下不可存在性伪造（EU-CMA）.,对教科书式RSA签名的攻击： (1)惟密钥攻击下的存在性伪造； (2)已知消息攻击下的存在性伪造； (3)选择消息攻击下的泛伪造。,8.3 两类改进的RSA签名方案 可通过加盐或使用hash函数克服前面对 教科书式RSA签名方案的攻击. (1)加盐(添加冗余) 如，只对二进制展开型为w

5、|w(其中w是0,1序列)的消息m进行签名.也可以利用其它的添加冗余方式.这种方法也被称是消息恢复签名方法.,带消息恢复的RSA数字签名 (1)密钥生成如RSA密码体制：n=pq， ed1mod(p-1)(q- 1),(n,e)是Alice的公钥,d是Alice的私钥. (2)签名算法: 利用一个公开的冗余函数R. 1对文档DZn,Alice计算R(D)= w|w, 2计算s= (w|w) d mod n，s就是Alice对文档D的 签名. (3)验证算法:任何人在收到s后,可利用Alice的公钥验证签名,计算se modn,看结果是否具有w|w的形式, 若有则签名是Alice的合法签名, 若

6、不具有,则签名非法.,(2)先hash,后签名的方法 这种方法也被称是带附录的方法. 这是密码学界目前流行的方法.,带附录的RSA数字签名 (1)密钥生成如RSA密码体制：n=pq， ed1mod(p-1)(q- 1),(n,e)是Alice的公钥,d是Alice的私钥. (2)签名算法: 利用一个公开的密码学hash函数h,如SHA-1. 1对文档DZn,Alice先计算m=h(D） 2计算s=md mod n，s就是Alice对文档D的签名. (3)验证算法:任何人在收到(D,s)后, 1计算m=h(D） 2可利用Alice的公钥验证签名,计算se modn,看结果是否等于m, 若相等,则

7、签名是Alice的合法签名; 若不相等,则签名非法.,注：(1)前面构造的两种数字签名目前还没有严格证明表明它们在选择消息攻击下不可存在性伪造(EU-CMA); (2)存在RSA数字签名的变形在某些假设下能被证明在选择消息攻击下不可存在性伪造(EU-CMA)。,8.4 利用公钥密码体制构造数字签名的方法 方法如下,8.5 Elgamal数字签名 Elgamal数字签名 (1)密钥生成如ELgamal密码体制：g是Zp的一个本原元, p是一个随机素数,A=ga mod p, a随机,a0,1,p-2, 公开(p,g,A)作为Alice的公钥,a保密作为Alice的私钥. (2)签名算法:利用一个

8、公开的密码学hash函数3.h:0,1* Zp 1Alice随机选取k0,1,p-2,且(k,p-1)=1 2对文档D,Alice计算r=gk mod p，s=k-1(h(D)-ar)mod(p-1) (r,s)就是Alice对文档D的签名. (3)验证算法:任何人在收到(D,(r,s)后,可利用Alice的公钥验证签名.只须验证Arrs=gh(D) mod p, 若等式成立,则签名是Alice的合法签名,若不相等,则签名非法.,注1.Elgamal数字签名每次签名中的k应选择不同, 否则有可能私钥a能被计算出. 2.Elgamal数字签名没有RSA数字签名的效率高, 并且有两倍的消息扩张.

9、3.Elgaml数字签名有很多种变形 4.存在Elgamal数字签名的变形在某些假设下 能被证明在选择消息攻击下是安全的. 5.就像Elgamal密码体制一样,Elgamal数字签 名也可以推广到合适的循环群中.,8.6 DSA DSA (1)密钥生成：q是一个160bit的随机素数,p是一个素数,Zp上的DLP难解,且q|(p-1).Alice找到Zp 的一个阶为q的元个g.计算A=ga mod p, a随机,a0,1,q-1, 公开(p,q,g,A)作为Alice的公钥,a保密作为Alice的私钥. (2)签名算法:利用SHA-1 1Alice随机选取k1,q-1, 2对文档D,Alice

10、计算r=(gk mod p)modq，s=k-1(h(D)+ar)modq 则(r,s)就是Alice对文档D的签名. (3)验证算法:任何人在收到(D,(r,s)后,可利用Alice的公钥验证签名. 1计算u=SHA(D)s-1modq, v=rs-1modq, 2验证(guAv modp)modq=r, 若等式成立,则签名是Alice的合法签名,若不相等,则签名非法.,注 1.DSA是美国国家技术与标准局在1991时选作为数字 签名的标准。 2.DSA类似于Elgamal,但它比Elgamal具有优势 (1)效率更高 (2)签名更短 3.DSA的安全性依赖于Zp的q阶子群上的DLP只有指

11、数算法. 4.DSA的利用大群的小阶子群的思想来源于德国密码 学家Schnorr.,8.7 具有特殊功能的数字签名 1.盲签名(blind signature) 需要盲签名的情形：当Bob想让Alice对一个文档签名，但他又不想让Alice知道这个文档的内容，且Alice在签署文档后不能将这次签名追踪到Bob时需要盲签名. 盲签名的步骤: (1)Bob对要签署的消息进行盲化, (2)Alice对盲化过的消息进行签名, (3)Bob进行脱盲恢复原来消息的签名.,基于RSA数字签名的盲签名 (1)密钥生成如RSA密码体制：n=pq， ed1mod(p-1)(q- 1),(n,e)是Alice的公钥

12、,d是Alice的私钥. (2)盲化算法: 1对文档DZn, Bob计算m=h(D） 2Bob随机选取k,(k,n)=1计算m1=mke mod n，将m1发 给Alice. (3)签名算法: 计算s1=m1d mod n，s1发送给Bob. (4)脱盲算法： Bob计算s=s1/k,则s就是Alice对D的合法签名. (5)验证算法:任何人在收到(D,s)后, 1计算m=h(D） 2可利用Alice的公钥验证签名,计算se modn,看结果是否等于m: 若相等,则签名是Alice的合法签名,若不相等,则签名非法.,注:1.盲签名是由Chaum1983年提出并构造 出来的. 2.Chaum申请

13、了盲签名的专利，实际上他拥有很多签名及其他秘密协议的专利. 3.也有基于Elgamal数字签名的盲数字签名.,.电子选举(electronic voting) 电子选举就是利用计算机网络实施的电子投票.利用盲签 名可以构造出来一个基本的电子选举方案. 一个基本的电子选举方案由三个实体组成: 选举委员会:公布候选人,对选票进行盖章使其合法. 选民:投票的人 计票中心:对所有选票进行统计,公布投票结果.,基本的voting 方案 (1)初始阶段: 选举委员会公布本次选举的候选人名单,有效选民及自己的RSA公钥(n,e).计票中心公布自己的公钥. (2)投票过程: 选民V填好选票v,再利用RSA盲签

14、名方案获得选举委员会对v的签名s.接着将(v,s)通过加密手段发送给计票中心. (3)计票过程: 计票中心解密获得(v,s),并验证选举委员会的签名,若签名合法,就统计进此票,若签名非法,则视其为废票.最后公布选举结果.,3.群签名(group signature) 群签名具有三个性质: (1)群里的任何人都可以群的名义对文档签名； (2)签名的接受者可以验证签名是这个群的合法签名,但不知道它是 群中哪个成员所为, (3)如遇争执,一个可信机构能识别出那个签名者 需要群签名的情形:一个公司拥有自己的局域网,有数个部门.每个 部门拥有自己的打印机,这些打印机都和公司的局域网联网,各个部 门的打印

15、机只允许自己部门的成员使用.这时,就可以使用群签名方 案对打印机进行管理,每个人打印文档时签名,打印机验证这是本部 门的合法签名(合法的群签名),允许打印.部门经理哪天发现这天打 印量超过界限,通过找到签名者能知道是哪个人打多了. 群签名是Chaum和Van Heijst于1991年提出的。,一个群签名方案 1.部门经理(相当于可信机构)选定本部门(群)的公钥方案,比如RSA,然后为每个成员选定若干私钥并告知他,再将群里每个成员的公钥随机排列成一表并公布. 2.每个成员在打印的时候,随机选择一个私钥进行签名,每个私钥只能使用一次,否则验证者可将这些签名联系起来. 3.签名接受者收到一个群签名,

16、使用这个群的公钥列表一个个验证,只要有一个公钥通过验证,则是合法签名,否则非法. 4.发生争执,部门经理能找出具体的签名者.,4.代理签名(proxy signature) 现实中,利用印章签名,可实现代理,就是印章的拥有者可 将印章给别人,当自己有事的时候,这个人就可以对文件 盖章相当于以他的名义对文件签名. 1996 年，Mambo、Usuda 和Okamoto首先提出了代理 数字签名的概念，所谓代理签名就是指：在一个代理签 名方案中，一个代理签名者可以代表原始签名者生成有 效的签名。,代理签名方案应具有的性质： 不可伪造性:除了原始签名者，只有指定的代理签名者能 够代表原签名者产生有效代理签名。 可验证性:从代理签名中，验证者能够相信原始签名者认 同了这份签名消息。 不可否认性:一旦代理签名者代替原始签名者产生了有效 的代理签名，他就不能否认他所签的