现代密码学07---数字签名

现代密码学林喜军中国海洋大学信息安全实验室数字签名第7章本章内容7.1数字签名概述7.2RSA签名方案7.3ElGamal签名方案7.4公钥基础设施(PKI)37.1数字签名概述45对称密码技术（MAC算法）的局限性只能实现数据完整性不能实现非否认耍赖，不承认曾经参与过某次通信什么是否认•因为双方都持有相同的密钥（信息是对称的）•接收方可以产生相同的消息，所以发送方可以诬赖消息是接收方伪造的Q:为什么对称密码技术不能实现非否认？数字签名是基于公钥思想的数据完整性技术6手写签名：Alice对一份文件签名后①别人可以验证她的签名②其他人很难模仿她的签名①可验证性②不可伪造性7数字签名：利用电子手段对电子文档进行签名，数字签名至少要满足手写签名的两个基本性质①别人可以验证数字签名②其他人很难模仿数字签名①可验证性②不可伪造性89•由于数字签名技术对政府、企事业、一般团体和个人的重要影响，世界各国都加强了对它的研究。·1994年，美国正式颁发美国数字签名标准DSS·1995年，我国制定自己的签名标准(GB15851-1995)·1999年，美国参议院已通过了立法，规定电子数字签名与手写签名的文件、邮件在美国具有同等的法律效力·2004年，我国颁发《中华人民共和国电子签名法》10发送者利用自己的私钥SK产生消息的认证码(类似于MAC)数字签名的基本思想：只有发送者掌握SK，所以该认证码只有发送者才能产生任何人都可以用相应的公钥PK验证认证码的合法性只要通过验证，就可以确信发送者产生了该消息认证码相当于发送者在消息上做的“签名”，故而称作数字签名•数字签名方案包括三个组成部分：·密钥生成Setup：产生公钥/私钥·签名算法Sign：利用私钥对消息产生数字签名·验证算法Ver：利用公钥对数字签名进行验证SignSK(M)=s签名VerPK(M,s)=true/false验证Setup(1k)=PK/SKSetupVerPK(M,SignSK(M))=true/false1112M||SignSKM’s’VerPK数字签名原理图不安全信道•Sign是签名算法•Ver是验证算法true,false类似MAC算法s=SignSK(M)M,s13抗伪造非否认数字签名主要安全特性签名者事后无法否认自己的签名消息认证相当于在电子文件上签自己的名字任何人都不能伪造他人的签名接收者可以确信消息发送者的身份防篡改任何人无法篡改已签名的消息14抗伪造是数字签名的核心安全性要求15在不知道私钥SK的情况下，产生签名s，使得VerPK(M,s)=true则称s是对M伪造的签名(PK是SK对应的公钥)也即找到一对能通过验证算法校验的(M,s)什么叫伪造签名给定消息M，在不知道私钥SK的情况下，产生签名s，使得VerPK(M,s)=true是计算上不可行的什么叫抗伪造数字签名安全模型①完全攻破：攻击者能找到私钥SK（UB:Unbreakability，不可完全攻破）②泛伪造：攻击者可以对任何消息产生合法的签名（UU:UniversalUnforgeability，泛不可伪造）③选择性伪造：对别人选择的消息，攻击者能以不可忽略的概率产生一个合法的签名（SU:SelectiveUnforgeability，选择性不可伪造）④存在性伪造：攻击者能至少为一条消息产生合法的签名（EU:ExistentialUnforgeability，不可存在性伪造）攻击者最容易实现的伪造16数字签名攻击分类依据攻击者获得信息的多少，对数字签名的攻击分类：①唯密钥攻击:攻击者只知道公钥(KOA:Keyonlyattack)②已知消息攻击:攻击者拥有一系列用私钥签过的消息和相应的签名(KMA:Knownmessageattack)③选择消息攻击:攻击者任意选择一系列消息，并可获得相应的签名(CMA:Chosenmessageattack)恢复私钥(但很难实现)，或伪造签名攻击者的目标攻击者的灵活性最大17数字签名安全模型关系图攻击者最容易实现的伪造而且灵活性最大18数字签名方案的最高安全性要求：选择消息攻击下不可存在性伪造（EU-CMA）197.2RSA签名方案2021•RSA算法不仅可用于加密，还可用于数字签名•注意–绝大多数算法只能用于加密或签名二者之一2122①系统建立：·随机选择大素数p、q，计算n＝pq·随机选取eφ(n)，且gcd(e,φ(n))=1·计算d，使ed≡1(modφ(n))·(e，n)为公钥·d为私钥(与RSA加密方案的系统建立过程完全一样)②签名：s＝mdmodn,m∈Z*n③校验：m?＝semodnRSA签名方案描述2223•安全性原理–只有签名者知道私钥d，所以他是产生签名s的唯一人–公钥e是公开的，任何人都可以验证签名s的合法性•但上述基本的RSA签名方案有安全漏洞——存在性伪造RSA签名方案安全性2324RSA签名方案存在性伪造•给定消息m,计算签名s=Sigsk(m)•给定m和s,验证合法性Verpk(m,s)?=true先看一下数字签名的原理•先选择s，再构造相应的消息m,使得Verpk(m,s)=true•这样不知道私钥sk，也可以产生满足验证算法的消息和签名，这种伪造称为存在性伪造存在性伪造的原理：将产生签名的思路反过来2425RSA签名方案RSA签名方案的存在性伪造•攻击者随机选择s•用签名者公钥(e,n)计算M←semodn•将(M,s)作为消息/签名输出伪造的过程•很明显，(M,s)满足验证算法M＝semodn的要求•因此，(M,s)是一对合法的伪造Q:(M,s)能否通过验证算法的校验呢？2526•可以利用两个消息的签名，产生新消息的签名–如果攻击者知道消息m1和m2的签名，设分别是s1=m1dmodn，s2=m2dmodn则可以伪造消息m=m1m2的签名s=s1s2–因为RSA签名方案存在以下性质：(m1m2)d≡m1dm2d(modn)所以，se≡(s1s2)e≡(m1dm2d)e≡((m1m2)d)e≡m1m2≡m(modn)RSA签名方案其他漏洞举例2627•重要作用①抵抗存在性伪造②加快计算速度•方法•“对消息m签名”改为“对H(m)签名”•原理①抵抗存在性伪造：利用Hash函数的单向、抗碰撞等性质②加快计算速度：H(m)比m短得多HASH函数在数字签名中的重要作用2728•改进后的方案–签名：s=H(m)dmodn–验证：H(m)?=semodn•可抵抗“存在性伪造”–攻击者随机选择s,用签名者公钥计算h=semodn–但计算一个m，使得H(m)=h在计算上不可行•可抵抗“利用两个消息的签名，产生新消息的签名”–因为(H(m1)H(m2))d≠H(m1m2)d(modn)利用Hash函数改进RSA签名方案2829利用Hash函数改进RSA签名方案•注意–目前没有严格证明表明其在选择消息攻击下不可存在性伪造(EU-CMA)–一些RSA签名方案的变形在某些假设下能被证明在选择消息攻击下不可存在性伪造(EU-CMA)7.3ElGamal签名方案303031•1985年提出•其变型已被NIST采纳为数字签名算法(DSA)ElGamal签名方案TaherElgamal3132①系统建立·随机选择大素数p,及生成元g∈Z*p·随机选取0＜x≤p2，计算y=gxmodp·公钥是(p,g,y)·私钥是x(与ElGamal加密方案的系统建立过程完全一样)ElGamal签名方案描述3233②签名对消息m，随机选择0＜r≤p2，然后计算：u=grmodps=r-1(m-xu)mod(p-1)m的签名为(u,s)③验证对于消息/签名(m,(u,s))，如果：yuus≡gm(modp)则(u,s)是m的有效签名ElGamal签名方案描述3334•正确性：yuus=gxugrs=gxu+rs=gmmodpxu+rs=xu+r(r-1(m-xu))=xu+m-xu=my=gx、u=grElGamal签名方案描述3435•对ElGamal签名的存在性伪造•攻击者随机选择0＜r,v≤p2，且gcd(v,p-1)=1•计算u=gryvmodps=-uv-1mod(p-1)m=-ruv-1mod(p-1)则(u,s)是对伪造的消息m的有效签名•伪造的正确性·yuus=yu(gryv)s=gxu(grgxv)s=gxu+rs+xvs=gmmodpxu+rs+xvs=xu+rs+xv(-uv-1)=xu+rs-ux=rs=r(-uv-1)=-ruv-1=mElGamal签名方案存在性伪造3536•签名u=grmodp,s=r-1(H(m,u)–xu)mod(p-1)其中Hash函数H:{0,1}*Zp则m的签名为(u,s)•验证对于消息/签名(m,(u,s))，如果：yuus=gH(m,u)modp则(u,s)是m的有效签名。ElGamal签名方案利用HASH函数改进3637ElGamal签名方案•注意①每次签名时，必须选择不同的r，否则私钥x可能会泄露②效率不如RSA签名高，而且数据长度有扩张③有很多种变形④有的ElGamal签名方案的变形能在某些假设下被证明在选择消息攻击下是安全的38ElGamal签名方案DSA•DSA(数字签名算法)是NIST在1991年选定的数字签名标准•DSA类似于ElGamal，但具有明显的优势①效率更高②签名更短39具有特殊功能的数字签名方案——盲签名(BlindSignature)Bob想让Alice对一个消息进行签名，但又不想让Alice知道文档的内容，且当Bob揭示签名和消息后，Alice无法知道这就是当初她签过的消息。如何实现？•由Chaum于1983年提出，并申请了专利•应用：电子投票40具有特殊功能的数字签名方案扩展阅读GroupSignatureOnline/OfflineSignatureUndeniableSignatureOne-timeSignatureFail-stopSignatureProxySignature407.4公钥基础设施(PKI)414142•公钥的分发仍是个严重的问题–当你要与Alice通信时，首先你必须获得她的公钥–但是，你从网络上接收到的公钥只是一个杂乱无章的比特串，你能确定它就是Alice的公钥吗？•解决方案–以公钥和用户身份作为消息，产生数字签名(目的是抗伪造)，将两者捆绑在一起•现在的问题是，该签名由谁产生？–其他用户？——缺乏公信力–应该由可信第三方承担，称之认证机构(CA)4243证明持有者的真实性证明公钥所有者的真实性CA证书数字世界签发公安局身份证现实世界签发“公钥证书”与“身份证”的类比4344Name:TomSerialnumber:484865Issuedby:GA-CAIssuedate:19970102Expirationdate:20030102Publickey:84A3796301C…用户身份和用户公钥的结合体；由CA审核用户身份后签发公钥证书的逻辑形式4445•为配合公钥证书的签发，需要十分复杂的管理机构，CA只是其中一个组成部分而已•由此，引出PKI的概念公钥基础设施(PKI)4546公钥基础设施(PKI)概述•如何建立相互间的信任关系•如何确保信息的真实性、完整性、机密性和非否认通过网络进行交流和商业活动，面临的最大问题是PKI是解决这一系列问题的技术基础它是电子商务、电子政务的关键和基础技术•为了提供可信任的高效密钥和证书管理，以支持众多依赖于公钥的安全技术目的4647公钥基础设施(PKI)概述一个使用公钥概念和密码技术实施和提供安全服务的具有普适性的安全基础设施的总称PKI的定义•生成、管理、存储、颁发和撤销公钥证书所需要的软硬件、人员、策略和规程的总和•提供密钥管理和数字签名服务的平台PKI不是特指某一个密码设备和管理设施，它是4748•通用应用–电子邮件的加密与签名–SSL/TLS–IPSec–VPN•特殊应用–金融HSM设备证书–ATM证书公钥基础设施(PKI)应用4849密钥产生证书签发密钥使用证书检验密钥过期密钥更新公钥基