第4章公钥密码系统.ppt

第第4 4章章 公钥密码体系公钥密码体系 第第4章章 公钥密码体系公钥密码体系 4.1 4.1 公钥密码概述公钥密码概述4.2 RSA4.2 RSA密码系统密码系统4.3 Diffie-Hellman4.3 Diffie-Hellman密钥交换密钥交换4.4 4.4 数字签名数字签名4.54.5 数字签名的算法数字签名的算法4.6 加密算法综合分析与选择加密算法综合分析与选择4.7 PGP4.7 PGP第第4 4章章 公钥密码体系公钥密码体系 导读导读 解密密钥与加密密钥不同？解密密钥与加密密钥不同？ 非对称密码系统的解密密钥与加密密钥是不同的。非对称密码系统的解密密钥与加密密钥是不同的。 一个称为一个称为公开密钥（简称公开密钥（简称公钥公钥），另一个称为，另一个称为秘秘密密钥密密钥（或（或私人密钥，简称私人密钥，简称私钥私钥）。）。 这种密码体系也称为公钥密码体系。这种密码体系也称为公钥密码体系。 公钥密码除可用于加密外，还可用于公钥密码除可用于加密外，还可用于数字签名数字签名。 中华人民共和国电子签名法中华人民共和国电子签名法已于已于20052005年年4 4月月1 1日实行。日实行。第第4 4章章 公钥密码体系公钥密码体系 回顾回顾网络安全网络安全的五个目标的五个目标秘密秘密密钥密码体系密钥密码体系对称密钥密码体系对称密钥密码体系数据加密标准数据加密标准DES 、AES、IDEA加密和解密用加密和解密用同一个同一个密钥密钥如何共享同一个密钥？如何共享同一个密钥？电子邮件电子邮件电话电话邮局邮寄邮局邮寄 以上三种方式安全以上三种方式安全?第第4 4章章 公钥密码体系公钥密码体系 1 公钥的起源公钥的起源 公钥密码体系于公钥密码体系于1976年由年由W. Diffie和和M. Hellman提出。提出。 公钥密码又叫公钥密码又叫非对称密码，非对称密码，这种密码体系采用了这种密码体系采用了一对一对不同的不同的密钥密钥加密密钥和解密密钥加密密钥和解密密钥； 这一对密钥，一个可以这一对密钥，一个可以公开公开(公钥公钥)，另一个为用，另一个为用户户专用专用(私钥私钥)。4.1 公钥密码概述 第第4 4章章 公钥密码体系公钥密码体系 2 数学原理数学原理-陷门单向函数陷门单向函数 公钥密码系统是公钥密码系统是基于陷门单向函数基于陷门单向函数的概念。的概念。 单向函数是易于计算但单向函数是易于计算但求逆求逆困难的函数困难的函数。 而陷门单向函数是在而陷门单向函数是在不知道不知道陷门陷门信息情况信息情况下求逆困难，而在下求逆困难，而在知道知道陷门信息时易于求陷门信息时易于求逆的函数。逆的函数。第第4 4章章 公钥密码体系公钥密码体系 （1）发送者用加密密钥PK（public key）对明文X加密后，接收者用解密密钥SK （secure key）解密，即可恢复出明文，或写为：DSK(EPK(X) X 此外，加密和解密的运算可以对调，即 EPK(DSK(X) X。 （2）加密密钥是公开的，但不能用它来解密，即DPK(EPK(X) X （3）在计算机上可以容易地产生成对的PK和SK。 （4）从已知的PK实际上不可能推导出SK，即从PK到SK是“计算上不可行的”。 （5）加密和解密算法都是公开的。3 公钥密码算法的特点公钥密码算法的特点第第4 4章章 公钥密码体系公钥密码体系 4 公钥密码体系的优缺点公钥密码体系的优缺点公钥密码体系的优点：公钥密码体系的优点：能适应网络的能适应网络的开放性要求，密开放性要求，密钥管理相对简单，钥管理相对简单，并且可方便地并且可方便地实现数字签名和身份实现数字签名和身份认证等功能认证等功能，是目前电子商务等技术的核心基础。，是目前电子商务等技术的核心基础。其缺点：其缺点：算法复杂，加密数据的算法复杂，加密数据的速度和效率较低速度和效率较低。因此在实际应用中，通常将因此在实际应用中，通常将对称对称加密算法和加密算法和非对称非对称加加密算法密算法结合结合使用。使用。通过这种方法可以通过这种方法可以有效地有效地提高加密的效率提高加密的效率并能简化对并能简化对密钥的密钥的管理。管理。第第4 4章章 公钥密码体系公钥密码体系 4 公钥密码体系的优缺点公钥密码体系的优缺点公钥密码体系的优点：公钥密码体系的优点：能适应网络的能适应网络的开放性要求，密开放性要求，密钥管理相对简单，钥管理相对简单，并且可方便地并且可方便地实现数字签名和身份实现数字签名和身份认证等功能认证等功能，是目前电子商务等技术的核心基础。，是目前电子商务等技术的核心基础。其缺点：其缺点：算法复杂，加密数据的速度和效率较低。算法复杂，加密数据的速度和效率较低。因此在实际应用中，通常将因此在实际应用中，通常将对称对称加密算法和加密算法和非对称非对称加加密算法密算法结合结合使用。使用。通过这种方法可以通过这种方法可以有效地有效地提高加密的效率提高加密的效率并能简化对并能简化对密钥的密钥的管理。管理。第第4 4章章 公钥密码体系公钥密码体系 第一个完善的公开密钥算法第一个完善的公开密钥算法RSA （取名字的首字母）（取名字的首字母）。 RSA密码系统的安全性基于大数分解的困难性。密码系统的安全性基于大数分解的困难性。 求一对大素数的乘积很容易，但要对这个乘积进行求一对大素数的乘积很容易，但要对这个乘积进行因因式分解式分解则非常困难（求逆）。则非常困难（求逆）。 因此，可以把一对大素数的因此，可以把一对大素数的乘积公开作为公钥乘积公开作为公钥，而把，而把素数作为私钥素数作为私钥，从而由一个公开密钥和密文中恢复出，从而由一个公开密钥和密文中恢复出明文的难度等价于明文的难度等价于分解两个大素数之积分解两个大素数之积。4.2 RSA密码系统4.2.1 RSA算法第第4 4章章 公钥密码体系公钥密码体系 公钥密码系统一般都涉及数论的知识，如素数、公钥密码系统一般都涉及数论的知识，如素数、欧拉函数、中国剩余定理等等。欧拉函数、中国剩余定理等等。“三人同行七十（）稀， 五树梅花二一（）枝， 七子团圆正半月（），除百零五（）便得知第第4 4章章 公钥密码体系公钥密码体系 若用整数若用整数X表示明文，用整数表示明文，用整数Y表示密表示密文文(X和和Y均小于均小于n)，则加密和解密运算为：，则加密和解密运算为：加密：加密：Y Xe mod n 解密：解密：X Yd mod n (encryption discryption ) 1 加密算法第第4 4章章 公钥密码体系公钥密码体系 现在讨论现在讨论RSA公开密钥密码体制中每个参数是如何选公开密钥密码体制中每个参数是如何选择和计算的。择和计算的。 计算计算n。用户秘密地选择两个大素数。用户秘密地选择两个大素数p和和q，计算出，计算出n pq。n称为称为RSA算法的模数。算法的模数。 计算计算(n)。 计算计算 n的欧拉函数的欧拉函数(n) (p 1)(q 1) 选择选择e。从。从1, (n) 1中选择一个中选择一个与与(n)互素的数互素的数e作为公开的加密指数。作为公开的加密指数。2 密钥的产生第第4 4章章 公钥密码体系公钥密码体系 计算计算d作为解密指数。作为解密指数。用户计算出满足下式的用户计算出满足下式的ded 1 mod(n) 即：即：(ed 1) mod(n)=0 由此推出由此推出 ed =t (n)+1 (t 是大于等于是大于等于1的正整数）的正整数） 得出所需要的公开密钥和秘密密钥：得出所需要的公开密钥和秘密密钥：公开密钥公开密钥(即加密密钥即加密密钥)PK e, n秘密密钥秘密密钥(即解密密钥即解密密钥)SK d, n 其中，其中，p、q、(n)和和d就是就是秘密的陷门秘密的陷门(四项并不是相四项并不是相互独立的互独立的)，这些信息不可以泄露。，这些信息不可以泄露。Congruence 同余第第4 4章章 公钥密码体系公钥密码体系 RSA加密消息m时(这里假设m是以十进制表示的)，首先将消息分成大小合适的数据分组，然后对分组分别进行加密。 每个分组的大小应该比n小？ 设ci为明文分组mi加密后的密文，则加密公式为 ci=mie (mod n) 解密时，对每一个密文分组进行如下运算：mi=cid (mod n)（可用中国剩余定理推导）第第4 4章章 公钥密码体系公钥密码体系 举例举例:说明说明RSA的加的加/解密过程。解密过程。 选选p=5，q=11，则，则n=pq=55，(n)=(p1)(q1)=40 选择选择e , 与与(n)互素互素 e=7 d要满足要满足 ed 1 mod(n) d=23 ed=7*23=161 第第4 4章章 公钥密码体系公钥密码体系 算法分析算法分析 如果如果明文明文mi同同n不是互为素数（不是互为素数（ m 取取p或或q ），就有可能出现消息暴露情况。就有可能出现消息暴露情况。 一个明文同一个明文同n有公约数的概率不大于有公约数的概率不大于1/p+1/q，因此，对于大的因此，对于大的p和和q来说，这种概率是非常小来说，这种概率是非常小的。的。第第4 4章章 公钥密码体系公钥密码体系 由加由加/解密公式可以得到加密表如表所示解密公式可以得到加密表如表所示表10.1 加 密 表明文明文密文密文明文明文密文密文明文明文密文密文明文明文密文密文111492852424821816362939433234217831264651449181732434753641192434344827728212136314914822312373851694242938475213122326163919533713727341465454第第4 4章章 公钥密码体系公钥密码体系 4.2.2 对对RSA算法的挑战算法的挑战 在在1977年年Rivest、Shamir及及Adleman提出公开钥密提出公开钥密码系统时，他们认为每秒钟百万次运算的计算机码系统时，他们认为每秒钟百万次运算的计算机可以在可以在4小时之内因子分解一个小时之内因子分解一个50位的数，但是分位的数，但是分解一个解一个100位的数要花几乎一个世纪位的数要花几乎一个世纪，而，而200位的位的数大约要花数大约要花40亿年。亿年。 甚至考虑到计算速度可以再提高百万倍甚至考虑到计算速度可以再提高百万倍（当时尚（当时尚未出现），基于未出现），基于200位数的密码看来是十分安全的。位数的密码看来是十分安全的。第第4 4章章 公钥密码体系公钥密码体系 Mirtin Gardner在在1977年年“Scientific American”的专栏文章的专栏文章中介绍了中介绍了RSA。 为了显示这一技术的威力，为了显示这一技术的威力，RSA公司的研究人员用一个公司的研究人员用一个129位位的十进制数的十进制数N和一个和一个4位数位数e 对一个关于秃鹰的消息（对一个关于秃鹰的消息（The magic words are squeamish ossifrage）作了编码。）作了编码。 Gardner刊登了那个刊登了那个密文，同时给出了密文，同时给出了N和和e。RSA公司还悬公司还悬赏赏100美元，奖给第一个破译这密码的人。美元，奖给第一个破译这密码的人。 然而数学史上往往有意外的事发生。这个叫阵的然而数学史上往往有意外的事发生。这个叫阵的RSA-129仅仅仅在十七年之后就败下阵来。一批松散组成的因子分解迷，仅在十七年之后就败下阵来。一批松散组成的因子分解迷，大约有六百多人，分布在二十几个国家。大约有六百多人，分布在二十几个国家。 他们经过八个月的努力最后于他们经过八个月的努力最后于1994年年4月为月为RSA-129找到了找到了64位数和位数和65位数位数两个素数因子。两个素数因子。第第4 4章章 公钥密码体系公钥密码体系 1977年认为年认为512 bit的的n就很安全就很安全.512 bit对应十进制多少位对应十进制多少位?现在认为现在认为1024 bit才安全才安全!问题问题: 一个明文很大一个明文很大, 如何用非对称密钥加密如何用非对称密钥加密?分组分组!第第4 4章章 公钥密码体系公钥密码体系 公钥密码系统用于三个方面公钥密码系统用于三个方面 (1) 通信保密通信保密：此时将：此时将公钥作为加密密钥，私钥作为解公钥作为加密密钥，私钥作为解密密钥密密钥，通信双方不需要交换密钥就可以实现保密通信，通信双方不需要交换密钥就可以实现保密通信。 Alice的公钥Joy明文输入加密算法，如RSA传输密文解密算法明文输出Alice的私钥Bob的公钥环TedAliceMike图10.1 通信保密 第第4 4章章 公钥密码体系公钥密码体系 (2) 数字签名数字签名：将：将私钥私钥作为加密密钥（数字签名），作为加密密钥（数字签名），公钥公钥作为解作为解密密钥（验证签名），可实现由一个用户对数据加密而使多个密密钥（验证签名），可实现由一个用户对数据加密而使多个用户解读。用户解读。Bob的公钥Joy明文输入加密算法，如RSA传输密文解密算法明文输出Bob的私钥Alice的公钥环TedBobMike图10.2 数字签名 第第4 4章章 公钥密码体系公钥密码体系 (3) 密钥交换密钥交换：通信双方交换会话密钥，以加密：通信双方交换会话密钥，以加密通信双方通信双方后续连接后续连接所传输的信息。所传输的信息。 实际应用中，考虑实际应用中，考虑效率和安全性效率和安全性两个因素，通常两个因素，通常用非对称密钥密码传递用非对称密钥密码传递密钥密钥，用对称密钥密码系，用对称密钥密码系统实现统实现保密通信保密通信。Diffie -Hellman密钥交换协议密钥交换协议 -只能用来交换密钥只能用来交换密钥 公钥密码算法一般比对称算法慢公钥密码算法一般比对称算法慢1000倍倍 第第4 4章章 公钥密码体系公钥密码体系 对称密钥与非对称密钥的比较对称密钥与非对称密钥的比较密钥密钥个数个数密钥是否密钥是否保密保密算法算法速度速度应用方面应用方面对称对称密钥密钥1保密保密置换、替换、置换、替换、移位、压缩、移位、压缩、扩展、异或扩展、异或快快保密通信保密通信非对非对称密称密钥钥2一个公开一个公开一个保密一个保密陷门单向函数陷门单向函数慢慢保密通信保密通信数字签名数字签名密钥交换密钥交换第第4 4章章 公钥密码体系公钥密码体系 RSA进行密钥分配的缺陷进行密钥分配的缺陷 通信的通信的某一方某一方决定密钥，决定密钥，密钥密钥不是不是保密通信双方保密通信双方共同协商的结果。共同协商的结果。第第4 4章章 公钥密码体系公钥密码体系 4.3 Diffie-Hellman密钥交换密钥交换 4.3.1 Diffie-Hellman算法算法 Diffie-Hellman算法是算法是第一个第一个公开密钥算法，公开密钥算法，发明于发明于1976年。年。 Diffie-Hellman算法能够用于算法能够用于密钥分配密钥分配，但不，但不能用于加密或解密信息能用于加密或解密信息, 当然也不适用数字签当然也不适用数字签名。名。第第4 4章章 公钥密码体系公钥密码体系 l Diffie-Hellman算法的安全性在于在算法的安全性在于在有限域上计算离散有限域上计算离散对数非常困难对数非常困难。 l 定义定义素数素数p的本原根的本原根(Primitive Root)为一种能生成为一种能生成1p1所有数的一个数，即如果所有数的一个数，即如果a为为p的本原根，则的本原根，则a mod p，a2 mod p，ap1 mod pl 两两互不相同，构成两两互不相同，构成1p1的的全体数的一个排列全体数的一个排列(例如例如p=11，a=2)。对于。对于任意数任意数b(bp)及素数及素数p的的本原根本原根a，可以，可以找到一个找到一个惟一惟一的指数的指数i，满足：，满足：b = ai mod p, 0ip1 称指数称指数i为以为以a为底模为底模p的的b的离散对数的离散对数。第第4 4章章 公钥密码体系公钥密码体系 如果如果Alice和和Bob想在不安全的信道上交换密钥，他们可以采用如下步想在不安全的信道上交换密钥，他们可以采用如下步骤：骤： (1) Alice和和Bob协商一个大素数协商一个大素数p及及p的本原根的本原根a，a和和p可以公开；可以公开； (2) Alice秘密产生一个随机数秘密产生一个随机数x，计算，计算X=ax mod p，然后把，然后把X发发送给送给Bob； (3) Bob秘密产生一个随机数秘密产生一个随机数y，计算，计算Y= ay mod p，然后把，然后把Y发发送给送给Alice； (4) Alice计算计算k=Yx mod p； (5) Bob计算计算k=Xy mod p。 k和和k是恒等的，因为是恒等的，因为k= Yx mod p=(ay)x mod p=(ax)y mod p= Xy mod p= k 线路上的搭线窃听者只能得到线路上的搭线窃听者只能得到a、p、X和和Y的值，的值，除非能计算离散对除非能计算离散对数，恢复出数，恢复出x和和y，否则就无法得到，否则就无法得到k，因此，因此，k为为Alice和和Bob独立计算独立计算的秘密密钥。的秘密密钥。第第4 4章章 公钥密码体系公钥密码体系 图4-3 Diffie-Hellman密钥交换第第4 4章章 公钥密码体系公钥密码体系 下面用一个例子来说明上述过程。下面用一个例子来说明上述过程。Alice和和Bob需进需进行密钥交换，如图行密钥交换，如图4-3所示，则：所示，则： 二者协商后决定采用素数二者协商后决定采用素数p=353及其本原根及其本原根a=3。 Alice选择随机数选择随机数x=97，计算，计算X=397 mod 35340，并，并发送给发送给Bob。 Bob选择随机数选择随机数y=233，计算，计算Y=3233 mod 353248，并发送给并发送给Alice。 Alice计算计算k=Yx mod p24897 mod 353=160。 Bob计算计算k=Xy mod p40233 mod 353=160。k和和k即为秘密密钥。即为秘密密钥。第第4 4章章 公钥密码体系公钥密码体系 4.3.2 中间人攻击Diffie-Hellman密钥交换容易遭受中间人攻击： (1) Alice发送公开值(a、p和X) 给Bob，攻击者Carol截获这些值并把自己产生的公开值X发送给Bob。(2) Bob发送公开值Y给Alice，Carol截获它然后把自己的公开值Y发送给Alice。(3) Alice和Carol计算出二人之间的共享密钥k1。(4) Bob和Carol计算出另外一对共享密钥k2。第第4 4章章 公钥密码体系公钥密码体系 AliceAlice用密钥用密钥k1k1给给BobBob发送消息；发送消息；CarolCarol截获消息后用截获消息后用k1k1解密解密就可读取消息；然后将获得的明文消息用就可读取消息；然后将获得的明文消息用k2k2加密加密( (加密前可能加密前可能会对消息作某些修改会对消息作某些修改) )后发送给后发送给BobBob。对对BobBob发送给发送给AliceAlice的消息，的消息，CarolCarol同样可以读取和修改。同样可以读取和修改。造成中间人攻击的原因是造成中间人攻击的原因是Diffie-HellmanDiffie-Hellman密钥交换密钥交换不认证对不认证对方方。利用数字签名可以挫败中间人攻击。利用数字签名可以挫败中间人攻击。图4-4 中间人攻击 第第4 4章章 公钥密码体系公钥密码体系 4.3.3 认证的Diffie-Hellman密钥交换 密钥交换双方通过密钥交换双方通过数字签名和公钥证书数字签名和公钥证书相互认证可以挫败相互认证可以挫败中间人攻击。中间人攻击。 在密钥交换之前，密钥交换的双方在密钥交换之前，密钥交换的双方AliceAlice和和BobBob各自拥有公各自拥有公钥钥/ /私钥对和私钥对和公开密钥证书公开密钥证书，AliceAlice和和BobBob签名算法和签名算法和验证算验证算法法分别为分别为SigSigA A、SigSigB B、VerVerA A、VerVerB B。 可信中心可信中心TATA也有一个签名方案，签名算法为也有一个签名方案，签名算法为SigSigTATA，公开的，公开的签名验证算法为签名验证算法为VerVerTATA，AliceAlice和和BobBob各持有一个证书：各持有一个证书：C(A)=(ID(A), VerC(A)=(ID(A), VerA A,Sig,SigTATA(ID(A),Ver(ID(A),VerA A)C(B)=(ID(B), VerC(B)=(ID(B), VerB B,Sig,SigTATA(ID(B),Ver(ID(B),VerB B)其中其中ID(A)ID(A)为用户身份信息为用户身份信息, ,证书证书C(A)C(A)由由TATA事先签发事先签发 第第4 4章章 公钥密码体系公钥密码体系 下面是下面是AliceAlice和和BobBob产生共享秘密密钥的过程：产生共享秘密密钥的过程：(1) Alice(1) Alice秘密产生一个随机数秘密产生一个随机数x x，计算计算X=aX=ax x mod p mod p，然后把，然后把X X发送给发送给BobBob； (2) Bob(2) Bob秘密产生一个随机数秘密产生一个随机数y y，首先，首先计算计算Y= aY= ay y mod p mod p，然后计算，然后计算 k=Xk=Xy y mod pmod p 和和y yB B=Sig=SigB B(Y, X(Y, X),),最后最后 BobBob把把(C(B),Y, y(C(B),Y, yB B) )发送给发送给AliceAlice；(3) (3) AliceAlice计算计算k=Yk=Yx x mod p mod p，并使用，并使用VerVerB B 验证验证y yB B ，使用，使用VerVerTATA验证验证C(B)C(B)； 计算计算y yA A=Sig=SigA A(Y, X),(Y, X),并将结果并将结果 (C(A),y(C(A),yA A) ) 发给用户发给用户BobBob(4) (4) BobBob使用使用VerVerA A 验证验证y yA A, ,使用使用VerVerTATA验证验证C(A)C(A)。简要分析抗击中间入侵攻击的过程。简要分析抗击中间入侵攻击的过程。若攻击者若攻击者CarolCarol插在用户插在用户AliceAlice和和BobBob之间，显然之间，显然CarolCarol可能截获可能截获AliceAlice发送的发送的X X，并将其替换为并将其替换为X X =a=ax xmod p,mod p,然后然后CarolCarol截获截获BobBob发送的发送的Y= aY= ay y mod p mod p 和和SigSigB B(Y, (Y, X X ) )。攻击者攻击者CarolCarol有可能将有可能将Y Y替换为替换为Y Y =a=ay ymod p,mod p,或将或将SigSigB B(Y, X(Y, X ) )替换为替换为SigSigB B(Y(Y , , X)X)，但由于，但由于CarolCarol不知道不知道BobBob的签名算法的签名算法SigSigB B，所以他无法计算所以他无法计算SigSigB B(Y(Y , X), X)。同样，同样，CarolCarol也无法知道也无法知道A A 的签名的签名SigSigA A。这样就达到了抗击中间人攻击的目的。这样就达到了抗击中间人攻击的目的。第第4 4章章 公钥密码体系公钥密码体系 图4-5 三方或多方的密钥交换 4.3.4 三方或多方Diffie-Hellman Alice、Bob和Carol三方共享密钥?Diffie-Hellman密钥交换协议很容易扩展到三方或多方的密钥交换。第第4 4章章 公钥密码体系公钥密码体系 (1) Alice选取一个大随机整数选取一个大随机整数x，计算，计算X=ax mod p，然后，然后把把X发送给发送给Bob； (2) Bob选取一个大随机整数选取一个大随机整数y，计算，计算Y= ay mod p，然后，然后把把Y发送给发送给Carol； (3) Carol选取一个大随机整数选取一个大随机整数z，计算，计算Z= az mod p，然，然后把后把Z发送给发送给Alice；第第4 4章章 公钥密码体系公钥密码体系 (4) Alice计算计算Z= Zx mod p并发送并发送Z给给Bob； (5) Bob计算计算X= Xy mod p并发送并发送X给给Carol； (6) Carol计算计算Y= Yz mod p并发送并发送Y给给Alice；第第4 4章章 公钥密码体系公钥密码体系 (7) Alice计算计算k= Yx mod p；(8) Bob计算计算k= Zy mod p；(9) Carol计算计算k= Xz mod p。共享秘密密钥共享秘密密钥k等于等于axyz mod p。这个协议很容易扩。这个协议很容易扩展到更多方。展到更多方。第第4 4章章 公钥密码体系公钥密码体系 四方共享密钥四方共享密钥要交换要交换/ /计算多少次信息？计算多少次信息？五方共享密钥五方共享密钥要交换要交换/ /计算多少次信息？计算多少次信息？N N个人共享密钥个人共享密钥交换交换/ /计算次数的公式计算次数的公式 n n2 2第第4 4章章 公钥密码体系公钥密码体系 4.4 数数 字字 签签 名名4.4.1 4.4.1 数字签名概述数字签名概述 在文件上手写签名长期以来被用作作者在文件上手写签名长期以来被用作作者身份的证明身份的证明，或表示，或表示同意文件的内容。同意文件的内容。1.1.签名是可信的签名是可信的。签名使文件的。签名使文件的接收者接收者相信相信签名者签名者在文件上签的在文件上签的字。字。2.2.签名不可伪造签名不可伪造。签名证明是签字者而不是其他人在文件上签字。签名证明是签字者而不是其他人在文件上签字。3.3.签名不可重用签名不可重用。签名是文件的一部分，不法之徒不可能将签名。签名是文件的一部分，不法之徒不可能将签名移到不同的文件上。移到不同的文件上。4.4.签名的文件是不可改变的签名的文件是不可改变的。在文件签名后，文件不能改变。在文件签名后，文件不能改变。5.5.签名是不可抵赖的签名是不可抵赖的。签名和文件是物理的东西。签名者事后不。签名和文件是物理的东西。签名者事后不能声称他没有签过名。能声称他没有签过名。第第4 4章章 公钥密码体系公钥密码体系 在在现实生活现实生活中，中，签名能够被伪造签名能够被伪造，签名能够从，签名能够从文章中盗用文章中盗用移到移到另一篇文章中，另一篇文章中，文件在签名后文件在签名后能够被改变能够被改变。 计算机文件易于复制。即使某人的签名难以伪计算机文件易于复制。即使某人的签名难以伪造（例如，造（例如，手写签名的图形手写签名的图形），但是从一个文），但是从一个文件到另一个文件复制和粘贴有效的签名都是很件到另一个文件复制和粘贴有效的签名都是很容易的容易的,这种签名并没有什么意义；这种签名并没有什么意义；其次文件在其次文件在签名后也易于修改，并且不会留下任何修改的签名后也易于修改，并且不会留下任何修改的痕迹痕迹。第第4 4章章 公钥密码体系公钥密码体系 公钥密码学使得数字签名成为可能。 用私钥加密信息，这时就称为对信息进行数字签名。 将密文附在原文后，称为数字签名。 其他人用相应的公钥去解密密文，将解出的明文与原文相比较，如果相同则验证成功，这称为验证签名。第第4 4章章 公钥密码体系公钥密码体系 4.4.2 基本的数字签名方案基本的数字签名方案 基本的数字签名协议是简单的： 1.Alice用她的私钥对文件加密，从而对文件签名。 2.Alice将签名的文件传给Bob。 3.Bob用Alice的公钥解密文件，从而验证签名。 这个协议没有通过第三方去验证签名。第第4 4章章 公钥密码体系公钥密码体系 如果能确认如果能确认Alice的公钥的公钥，这个协议也满足我们期待的特征：这个协议也满足我们期待的特征：1.1.签名是签名是可信可信的。当的。当BobBob用用AliceAlice的公钥验证信息时，他的公钥验证信息时，他知道是由知道是由AliceAlice签名的。签名的。2.2.签名是签名是不可伪造不可伪造的。只有的。只有AliceAlice知道她的私钥。知道她的私钥。3.3.签名是签名是不可重用不可重用的。签名是文件的函数，并且不可能的。签名是文件的函数，并且不可能转换成另外的文件。转换成另外的文件。4.4.被签名的文件是被签名的文件是不可改变不可改变的。如果文件有任何改变，的。如果文件有任何改变，文件就不可能用文件就不可能用AliceAlice的公钥验证成功。的公钥验证成功。5.5.签名是签名是不可抵赖不可抵赖的。的。BobBob不用不用AliceAlice的帮助就能验证的帮助就能验证AliceAlice的签名。的签名。第第4 4章章 公钥密码体系公钥密码体系 协议协议存在四个问题存在四个问题1、公钥密码算法对长文件签名效率太低；、公钥密码算法对长文件签名效率太低；2、签名文件没有保密功能（如果签名文件只想让、签名文件没有保密功能（如果签名文件只想让Bob解开）；解开）； 3、没有实现多重签名、没有实现多重签名-多个人签名；多个人签名；4、没有进行身份认证，即、没有进行身份认证，即Alice声称的公钥与他的身份声称的公钥与他的身份是否相同。是否相同。 为了解决第为了解决第4个问题，可采用数字证书对身份进个问题，可采用数字证书对身份进行认证（详见第行认证（详见第7章）。下面分别解决章）。下面分别解决1-3中存在的中存在的问题。问题。通过CA来解决这个问题第第4 4章章 公钥密码体系公钥密码体系 4.4.3 高效数字签名方案高效数字签名方案 数字签名协议和单向散列函数数字签名协议和单向散列函数一起使用。一起使用。AliceAlice和和BobBob并不并不对整个文件签名，只对文件的散列值签名。对整个文件签名，只对文件的散列值签名。1.Alice1.Alice产生文件的散列值，产生文件的散列值，AliceAlice用她的私钥对散列值加密，用她的私钥对散列值加密，凭此表示对文件签名。凭此表示对文件签名。 ? ?2.Alice2.Alice将文件和散列签名送给将文件和散列签名送给BobBob。3.Bob3.Bob用用AliceAlice发送的文件产生文件的散列值，然后用发送的文件产生文件的散列值，然后用AliceAlice的的公钥对签名的散列值解密。公钥对签名的散列值解密。 BobBob解密的散列值与自己产生的散列值相同，签名就是有效解密的散列值与自己产生的散列值相同，签名就是有效的的。速度大大地提高了。速度大大地提高了。第第4 4章章 公钥密码体系公钥密码体系 对单向散列函数签名和文件签名一样安全？对单向散列函数签名和文件签名一样安全？ 若用若用SHASHA计算散列值，由于两个不同的文件有计算散列值，由于两个不同的文件有相同的相同的160160比特散列值的概率为比特散列值的概率为1/21/2160160。 因此因此对散列值的签名可以认为就是对原文件签名对散列值的签名可以认为就是对原文件签名。 这样，可认为使用这样，可认为使用单向散列函数的签名和文件签单向散列函数的签名和文件签名一样安全。名一样安全。第第4 4章章 公钥密码体系公钥密码体系 4.4.4 保密签名方案保密签名方案 通过把通过把公钥密码和数字签名公钥密码和数字签名结合起来，我们能够产生一个结合起来，我们能够产生一个协议，可把数字签名的协议，可把数字签名的真实性和加密的安全性真实性和加密的安全性结合起来。结合起来。 想象你写的一封信：想象你写的一封信：签名提供了原作者的证明，而信封提签名提供了原作者的证明，而信封提供了秘密性。供了秘密性。消息M用Alice的私钥签名用Bob的公钥加密EB(SA(M)消息M用Bob的私钥解密用Alice的公钥验证EB(SA(M)图4-6 带加密的数字签名 第第4 4章章 公钥密码体系公钥密码体系 1.Ailce1.Ailce用她的私钥对信息签名：用她的私钥对信息签名：S SA A(M)(M)2.Alice2.Alice用用BobBob的公钥对签名的信息加密，然后送给的公钥对签名的信息加密，然后送给BobBob：E EB B(S(SA A(M)(M)3.Bob3.Bob用他的私钥解密：用他的私钥解密：D DB B(E(EB B(S(SA A(M)=S(M)=SA A(M)(M)4.Bob4.Bob用用AliceAlice的公钥验证并且恢复出信息：的公钥验证并且恢复出信息：V VA A(S(SA A(M)=M(M)=M第第3和第和第4步能否交换步能否交换?第第4 4章章 公钥密码体系公钥密码体系 4.4.5 多重签名方案多重签名方案 Alice和和Bob怎么对同一数字文件签名呢？怎么对同一数字文件签名呢？ 分两种情况，分两种情况，一种是直接在文件上签名，另一种是结合单向一种是直接在文件上签名，另一种是结合单向散列函数签名散列函数签名。 若若Alice首先签名，然后首先签名，然后Bob对对Alice的签名再进行签名的签名再进行签名。 对吗？对吗？ 在不验证在不验证Bob签名的情况下就验证签名的情况下就验证Alice的签名是不可能的的签名是不可能的。 并且在验证签名不成功的情况下不能并且在验证签名不成功的情况下不能倒追倒追责任责任，将不能准确，将不能准确判断哪个人的签名出现了问题，这点就不符合签名满足不可判断哪个人的签名出现了问题，这点就不符合签名满足不可否认性的要求。否认性的要求。第第4 4章章 公钥密码体系公钥密码体系 1直接在文件上签名。直接在文件上签名。 签名方案应该是签名方案应该是Alice和和Bob分别对文件的副本分别对文件的副本签名，结果签名的信息量是原文的两倍。签名，结果签名的信息量是原文的两倍。 若有若有n个人在同一份文件上个人在同一份文件上分别分别签名，签名，签名的签名的信息量是原文的信息量是原文的n倍倍,效率很低。效率很低。第第4 4章章 公钥密码体系公钥密码体系 4.4.5 多重签名方案多重签名方案2结合单向散列函数签名。结合单向散列函数签名。1.Alice对文件的散列值签名。2.Bob对文件的散列值签名。3.Bob将他的签名交给Alice。4.Alice把文件、她的签名和Bob的签名发给Carol。5.Carol验证Alice和Bob的签名。第第4 4章章 公钥密码体系公钥密码体系 4.5 数字签名算法4.5.1 4.5.1 数字签名算法数字签名算法DSADSA 19911991年年8 8月，美国月，美国NISTNIST公布了用于数字签名标准公布了用于数字签名标准DSSDSS的的数字签名算法数字签名算法DSADSA，19941994年年1212月月1 1日正式采用为美国联日正式采用为美国联邦信息处理标准。邦信息处理标准。 DSADSA中用到了以下参数：中用到了以下参数：(1) p(1) p为为L L位长的素数，其中，位长的素数，其中，L L为为51251210241024之间且是之间且是6464倍数的数。倍数的数。(2) q(2) q是是160160位长的素数，且为位长的素数，且为p-1p-1的因子。的因子。(3) g=h(3) g=h(p-1)/q(p-1)/q mod p mod p，其中，其中，h h是满足是满足1 1h hp-1p-1且且h h(p-1)/q(p-1)/q mod pmod p大于大于1 1的整数。的整数。(4) x(4) x是随机产生的大于是随机产生的大于0 0而小于而小于q q的整数。的整数。(5) y=g(5) y=gx x mod p mod p。(6) k(6) k是随机产生的大于是随机产生的大于0 0而小于而小于q q的整数的整数。第第4 4章章 公钥密码体系公钥密码体系 前三个参数前三个参数p p、q q、g g是公开的；是公开的；x x为私钥，为私钥，y y为公钥；为公钥；x x和