公钥密码系统ppt课件.ppt

Network and Information Security,第4章公钥密码体系,Network and Information Security,主要内容,4.1 公钥密码概述4.2 RSA密码系统4.3 Diffie-Hellman密钥交换4.4 数字签名4.5 数字签名的算法4.6 PGP,问题的提出：,传统的对称加密仅用一个密钥，由发送方和接收方共享如果密钥公开，则通信是不安全的存在的问题：无法保护发送方，如果接收方伪造一个消息并宣称是由发送发发送的密钥的分配：通信双方要进行加密通信，需要通过秘密的安全信道协商加密密钥，如何安全交换密钥？密钥管理问题 若N个人相互保密通信，每人必须拥有（N-1)个密钥，N很大时，需要保存的密钥很多。如何解决？在有多个用户的网络中，任何两个用户之间都需要有共享的密钥。思考：需要的密钥量是多少？,Network and Information Security,挑战！,Network and Information Security,公钥加密算法,Network and Information Security,Network and Information Security,1 公钥的起源公钥密码体系于1976年由美国斯坦福大学的W. Diffie和M. Hellman提出。公钥密码又叫非对称密码，这种密码体系的基本思想:将密钥K一分为二，一个专门加密，一个专门解密，即kekd可以将ke公开，密钥量小，分配比较简单有ke不能计算出kd，所以kd便成为用户的指纹，实现数字签名。,4.1 公钥密码概述,Network and Information Security,2 数学原理-陷门单向函数,公钥密码系统是基于陷门单向函数的概念。陷门单向函数：单向函数是求逆困难的函数，而单向陷门函数，是在不知陷门信息下求逆困难的函数，当知道陷门信息后，求逆是易于实现的。单向陷门函数f(x)，必须满足以下三个条件。 给定x，计算y=f(x)是容易的；给定y, 计算x使y=f(x)是困难的（所谓计算x=f-1(y)困难是指计算上相当复杂已无实际意义）；存在，已知时对给定的任何y，若相应的x存在，则计算x使y=f(x)是容易的。,注： 仅满足(1)、(2)两条的称为单向函数；第(3)条称为陷门性， 称为陷门信息。,Network and Information Security,（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 公开密钥算法的特点,9,4.公钥密码系统可用于以下三个方面： (1) 通信保密：此时将公钥作为加密密钥，私钥作为解密密钥，通信双方不需要交换密钥就可以实现保密通信。这时，通过公钥或密文分析出明文或私钥是不可行的。如图所示，Bob拥有多个人的公钥，当他需要向Alice发送机密消息时，他用Alice公布的公钥对明文消息加密，当Alice接收到后用她的私钥解密。由于私钥只有Alice本人知道，所以能实现通信保密。,10,(2) 数字签名：将私钥作为加密密钥，公钥作为解密密钥，可实现由一个用户对数据加密而使多个用户解读。如图所示，Bob用私钥对明文进行加密并发布，Alice收到密文后用Bob公布的公钥解密。由于Bob的私钥只有Bob本人知道，因此，Alice看到的明文肯定是Bob发出的，从而实现了数字签名。,Network and Information Security,(3) 密钥交换：通信双方交换会话密钥，这种应用也称为混合密码系统，即用常规密码体制加密需要保密传输的消息本身，然后用公钥密码体制加密常规密码体制中使用的会话密钥，将两者结合使用，充分利用对称密码体制在处理速度上的优势和非对称密码体制在密钥分发和管理方面的优势。,Network and Information Security,5 对称密钥与非对称密钥的比较,Network and Information Security,4.2 RSA密码系统4.2.1 RSA算法,1977年由Rivest、Shamir和Adleman在麻省理工学院发明，1978年公布第一个比较完善的同时也是应用最广泛的公钥密码算法。,RSA的基本原理:RSA是基于大整数难分解的公钥密码技术。 大整数的分解问题可以被表述：已知整数n，n是两个素数的积，即n=p.q 。求解p、q的值。 大整数分解是计算上困难的问题，目前还不存在一般性的有效解决算法。,Network and Information Security,RSA的数学基础,除数(因子)：设z为由全体整数而构成的集合，若 b0且 a，b，mz ， 使得a=mb,此时称b整除a.记为ba,还称b为a的除数(因子).素数：对一个自然数P，如果P只能被1和自身除尽时，则称P为素数（或质数），否则为合数。例：100以内的素数共有25个：2，3，5，7，11，13，17，19，23，29，31，37，41，43，47，53，59，61，67，71，73，79，83，89，97,最大公约数与互为素数：设且 a，b，cz ，如果c|a , c|b，称c是a和b的公约数。正整数d称为a和b的最大公约数，如果它满足：（1）d是a和b的公约数；（2）对a和b的任何一个公约数c，有c|d .a和b的最大公约数记为gcd(a,b)=d。如果gcd(a,b)=1，则称a与b是互素的，即a和b互为素数。例：8和15是互素的，即gcd（8，15）1。,Network and Information Security,19,整数同余：设n是一个正整数，a,b Z， 如果 a mod n= b mod n，则称a 和b模n同余， 记作 a b(mod n) ，称整数n为同余模 。模m求余运算称为模运算, 下面是模运算的一些性质。 (1) (a+b) mod m = (a mod m) + (b mod m) mod m (2) (a-b) mod m = (a mod m) - (b mod m) mod m (3) (ab) mod m = (a mod m) (b mod m) mod m (4) (a(b+c) ) mod m = (ab) mod m) + (ac) mod m) mod m (5)a8 mod m=(aaaaaaaa) mod m 化简为：(a2 mod m)2 mod m)2 mod m,11 mod 8=3；15 mod 8=7（11+15）mod 8=26 mod 8=2 （11 mod 8）+（15 mod 8） mod 8 =（3+7）mod 8 =2（11-15）mod 8=-4 mod 8=4 （11 mod 8）-（15 mod 8） mod 8 =（3-7）mod 8 =4（11*15）mod 8=165 mod 8=5 （11 mod 8）*（15 mod 8） mod 8 =（3*7）mod 8 =5,计算117 mod 13,112 =121 4 mod 13114=（112）2 16 mod 13 3 mod 13117=11*112*114 11*4*3 mod 13 132 mod13 2 mod13,加法逆元：对于a Zn ，存在b Zn ，使得ab 0（mod n）,则b是a的加法逆元。记b=-a。例：1115 0（mod 26），则称11模26的加法逆元是15即-11（代表11模26的加法逆元）的结果为15乘法逆元：设a Zn ，如果存在bZn 满足ab 1(mod n)，则称b是a的模n乘法逆元，记为x=a-1(mod n)715 1(mod 26)，则称7模26的乘法逆元是15加法一定存在逆元，乘法不一定存在逆元。,22,欧几里德算法,用途：(1)求两个正整数的最大公约数性质1：对任意非负整数a和正整数b，有 gcd(a,b)=gcd(b,a mod b) (a=b) 可重复使用上式求出最大公约数。重复计算结束的条件是后一个整数等于0，此时前一个数即为二者的最大公约数。例：求gcd(18,12)=gcd(12,18mod12)=gcd(12,6)=gcd(6,12mod6)=gcd(6,0)=6,Network and Information Security,用途： (2)两个正整数互素，可以求一个数关于另一个数的乘法逆元性质2：若gcd(n,a)=1, 则a在模n下有乘法逆元（设an）即存在xn, ax=1 mod n,求解乘法逆元的方法,扩展的欧几里得算法: 求d关于模f的乘法逆元d-1 ，即 dd-1 mod f = 1 (X1,X2,X3) = (1,0,f)； (Y1,Y2,Y3) = (0,1,d) if (Y3=0) then return d-1 = null /无逆元 if (Y3=1) then return d-1 = Y2 /Y2为逆元 Q = X3 div Y3 /整除 ，取商(T1，T2，T3) = (X1 - QY1，X2 - QY2，X3 - QY3) (X1，X2，X3) = (Y1，Y2，Y3) (Y1，Y2，Y3) = (T1，T2，T3) Goto ,例如：k=7, 求解7-1（7关于模26的乘法逆元）,-11即为求得的结果，是11关于模26的加法逆元，即15。,思考：k=550求解550-1（550关于模1769的乘法逆元）,550-1 mod 1769=550,费马（Fermat）定理 描述1：若p是素数，a是正整数且gcd（a,p）=1，则 ap-1 1（mod p） 描述2：对于素数p，若a是任一正整数，则 ap a（mod p）例：p=5,a=3, 则35-1=81 1mod5 35=243 3mod5,Network and Information Security,欧拉函数欧拉函数(m) ：当m1时， (m)表示比m小且与m互素的正整数的个数。 例：m24，比24小且与24互素的正整数有：1、5、7、11、13、17、19、23，共8个。因此(24)8 1）m是素数，则 (m)=m-1 2)m=pq,且p和q是互异的素数，则(m)= (p) (q)=(p-1)(q-1)例： (21)= (3) (7)=（3-1)(7-1)=12,这12个数是1,2,4,5,8,10,11,13,16,17,19,20欧拉定理：对于任何互素的两个整数a和m，有a(m) 1 (mod m) 例：设a=4，m=5 则有(5)=4，44=256，256 1(mod 5),a(m)+1 a (mod m),RSA密码算法,RSA密码体制 (安全性基于大整数因子分解的困难性）明文和密文均是0到n之间的整数，n通常为 1024位二进制数或309位十进制数明文空间P=密文空间C=xZ|0 x n,Z为整数集合。RSA密码的密钥生成具体步骤如下： 选择互异的素数p和q，计算n=pq，(n) = (p - 1)(q - 1)； 选择整数e，使gcd(n),e) = 1，且1 e (n)； 计算d，d e-1 mod (n)，即d为模(n)下e的乘法逆元；公钥Pk = e, n ，私钥Sk = d, n加密：c = me mod n；解密：m = cd mod n。,RSA算法操作过程,RSA算法加密/解密过程,RSA算法的证明,例1： 选p=7，q=17。n=pq=119，(n)=(p-1)(q-1)=96。取e=5，满足1e(n)，且gcd(n),e)=1。确定满足de=1 mod 96且小于96的d， d77。因此公钥为5，119，私钥为77，119。设明文m=19，则由加密过程得密文为 C195 mod 1192476099 mod 11966 解密为 M6677mod 11919,RSA 加密和解密的例子：在以下实例中只选取小数值的素数p,q,以及e,例2假设用户A需要将明文“key”通过RSA加密后传递给用户B。 （1）设计公私密钥(e, n)和(d, n)。令p=3，q=11，得出n=pq=311=33； (n)=(p-1)(q-1)=210=20；取e=3，（3与20互质）则ed1 mod (n)，即3d1 mod 20。用扩展的欧几里德方法求得：d=7。从而可以设计出一对公私密钥，加密密钥（公钥）为：KU =(e,n)=(3,33)，解密密钥（私钥）为：KR =(d,n)=(7,33)。,34,(2)英文数字化。将明文信息数字化。假定明文英文字母编码表为按字母顺序排列数值 则得到分组后的key的明文信息为：11，05，25。,35,（3）明文加密 用户加密密钥(3,33) 将数字化明文分组信息加密成密文。由CMe(mod n)得： 得到相应的密文信息为：11，26，16。,C1(M1)e (mod n)=113 (mod 33)=11C2(M2)e (mod n)=53 (mod 33)=26C3(M3)e (mod n)=253 (mod 33)=16,36,（4）密文解密。用户B收到密文，若将其解密，只需要计算 ，即：用户B得到明文信息为：11，05，25。根据上面的编码表将其转换为英文，我们又得到了恢复后的原文“key”。,26,例3：设通信双方使用RSA加密体制，接收方的公开密钥是（5,35），接收到的密文是10，求明文。,Network and Information Security,解：据题意知： e=5，n=35，C=10 因此有：(n）=(35）=(5）(7）=46=24d=e-1 mod (n）=5-1 mod 24=5所以有： M=Cd mod n=105 mod 35 =5,例4：已知RSA密码体制的公钥为（11，51）（1）若明文M=3，求C（2）若截获得的密文C=9，求M,Network and Information Security,解：据题意知： e=11，n=51 因此有：(n）=(51）=(3）(17=216=32因为加密指数e和私密钥d满足：ed mod (n) =1,所以d=e-1 mod (n) ,私钥d的计算过程如下,Network and Information Security,由以上计算可知私密钥d=3。（1）若明文M=3，则 C = Me mod n=311 mod 51=24；（2）若截获得的密文C=9，则M = Cd mod n=93 mod 51=15,实际运用时，要比这复杂得多。 由于RSA算法的公钥私钥的长度（模长度）要到1024位甚至2048位才能保证安全，因此，p、q、e的选取、公钥私钥的生成，加密解密模指数运算都有一定的计算程序，需要仰仗计算机的高速计算来完成。,RSA算法安全性,在RSA密码应用中，公钥KU是被公开的，即e和n的数值可以被第三方得到。破解RSA密码的问题就是从已知的e和n的数值（n等于pq），设法求出d的数值，这样就可以得到私钥来破解密文。RSA算法的安全性取决于p、q的保密性，以及分解大数的难度，所以在计算出n后要立即彻底删除p、q值。当前运用计算机和素数理论，已能分解出129位长的十进制数。密钥长度应在1024位到2048位之间。,对称密码体制中的一个苦恼,如果有n个用户，需要两两共用1对密钥，一共需要多少对密钥？,4.3 Diffie-Hellman密钥交换,怎样进行密钥协商,一个生活中的例子,在网络上，这样的秘密“传递”能用数学方法实现吗？,3、一个基于离散对数的密钥协商协议Diffie-Hellman密钥协商,1976年，Diffie和Hellman发表了一篇划时代的密码学论文密码学新方向（New Directions in Cryptography），提出公钥密码模型。,有限域上的离散对数问题,离散对数困难性难题：已知整数y、g、p 求整数x，这非常困难。,有多难,512bit离散对数困难度1024bit大整数分解难度,相当,数学知识生成元素数p的生成元（primitive root）的定义：如果a是素数p的生成元，则数a mod p, a2 mod p, ap-1 mod p是不同的并且包含从1到p-1之间的所有整数的某种排列。注：本原根不唯一。可验证19的本原根除了2、3外，还有10、13、14、15。,离散对数若a是素数p的一个生成元，则相对于任意整数b（b mod p0），必然存在唯一的整数i（1ip-1），使得bai mod p，称指数i为以a为底模p的b的离散对数。对于函数ygx mod p，其中，g为素数p的生成元，y与x均为正整数，已知g、x、p，计算y是容易的；而已知y、g、p，计算x是困难的，即求解y的离散对数x。注：离散对数的求解为数学界公认的困难问题。,Network and Information Security,Network and Information Security,巧妙的Diffie-Hellman密钥交换,现在要在公开网络上协商一个公共密钥K,gx mod p,gy mod p,发送方计算,(gy)x mod p,接收方计算,(gx)y mod p,K,gxy mod p,举例,11319 mod (2127-1),11323 mod(2127-1),爱丽丝计算,(11323)19 mod (2127-1),鲍勃计算,(11319)23 mod (2127-1),K,3097088834231538675770610326325810083,中间人攻击,gx mod p,gy mod p,gz mod p,gz mod p,K1=(gz)x mod p,K2=(gz)y mod p,K1=(gx)z mod pK2=(gy)z mod p,问题,如何避免中间人的攻击？,Diffie-Hellman密钥交换算法,Alice和Bob协商好一个大素数p，和大的整数a，1ap，a是p的本原根。p和a无须保密，可为网络上的所有用户共享。当Alice和Bob要进行保密通信时，他们可以按如下步骤来做： Alice选取大的随机数xp，并计算X=ax(mod P)； Bob选取大的随机数yp，并计算Y=ay (mod P)； Alice将X传送给Bob，Bob将Y传送给Alice； Alice计算K=(Y )x(mod P)，Bob计算K (X) y(mod P)显而易见k和k是恒等的，因为k= Yx mod p=(ay)x mod p=(ax)y mod p= Xy mod p= k，即Alice和Bob已获得了相同的秘密值K。,线路上的搭线窃听者只能得到a、p、X和Y的值，除非能计算离散对数，恢复出x和y，否则就无法得到k，因此，k为Alice和Bob独立计算的秘密密钥。,Network and Information Security,图4-3 Diffie-Hellman密钥交换,Diffie-Hellman密钥交换举例,Alice和Bob需进行密钥交换，则： 二者协商后决定采用素数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即为秘密密钥。,Network and Information Security,4.3.2 中间人攻击 Diffie-Hellman密钥交换容易遭受中间人攻击： (1) Alice发送公开值(a、p和X) 给Bob，攻击者Carol截获这些值并把自己产生的公开值发送给Bob。 (2) Bob发送公开值Y给Alice，Carol截获它然后把自己的公开值发送给Alice。 (3) Alice和Carol计算出二人之间的共享密钥k1。 (4) Bob和Carol计算出另外一对共享密钥k2。,Network and Information Security,Alice用密钥k1给Bob发送消息；Carol截获消息后用k1解密就可读取消息；然后将获得的明文消息用k2加密(加密前可能会对消息作某些修改)后发送给Bob。对Bob发送给Alice的消息，Carol同样可以读取和修改。造成中间人攻击的原因是Diffie-Hellman密钥交换不认证对方。利用数字签名可以挫败中间人攻击。,图4-4 中间人攻击,Network and Information Security,4.3.3 认证的Diffie-Hellman密钥交换密钥交换双方通过数字签名和公钥证书相互认证可以挫败中间人攻击。在密钥交换之前，密钥交换的双方Alice和Bob各自拥有公钥/私钥对和公开密钥证书，Alice和Bob签名算法和验证算法分别为SigA、SigB、VerA、VerB。可信中心TA也有一个签名方案，签名算法为SigTA，公开的签名验证算法为VerTA，Alice和Bob各持有一个证书：C(A)=(ID(A), VerA,SigTA(ID(A),VerA)C(B)=(ID(B), VerB,SigTA(ID(B),VerB)其中ID(A)为用户身份信息,证书C(A)由TA事先签发,Network and Information Security,下面是Alice和Bob产生共享秘密密钥的过程：,(1) Alice秘密产生一个随机数x，计算X=ax mod p，然后把X发送给Bob； (2) Bob秘密产生一个随机数y，首先计算Y= ay mod p，然后计算 k=Xy mod p 和yB=SigB(Y, X),最后 Bob把(C(B),Y, yB)发送给Alice；(3) Alice计算k=Yx mod p，并使用VerB 验证yB ，使用VerTA验证C(B)； 计算yA=SigA(Y, X),并将结果 (C(A),yA) 发给用户Bob(4) Bob使用VerA 验证yA,使用VerTA验证C(A)。简要分析抗击中间入侵攻击的过程。若攻击者Carol插在用户Alice和Bob之间，显然Carol可能截获Alice发送的X，并将其替换为X=axmod p,然后Carol截获Bob发送的Y= ay mod p 和SigB(Y, X)。攻击者Carol有可能将Y替换为Y=aymod p,或将SigB(Y, X)替换为SigB(Y, X)，但由于Carol不知道Bob的签名算法SigB，所以他无法计算SigB(Y, X)。同样，Carol也无法知道A 的签名SigA。这样就达到了抗击中间人攻击的目的。,Network and Information Security,图4-5 三方或多方的密钥交换,4.3.4 三方或多方Diffie-Hellman Diffie-Hellman密钥交换协议很容易扩展到三方或多方的密钥交换。下例中，Alice、Bob和Carol一起产生秘密密钥 。,(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) Alice计算Z= Zx mod p并发送Z给Bob； (5) Bob计算X= Xy mod p并发送X给Carol； (6) Carol计算Y= Yz mod p并发送Y给Alice；,Network and Information Security,(7) Alice计算k= Yx mod p；(8) Bob计算k= Zy mod p；(9) Carol计算k= Xz mod p。共享秘密密钥k等于axyz mod p。这个协议很容易扩展到更多方。四方共享密钥要交换计算多少次信息？五方共享密钥要交换计算多少次信息？N个人共享密钥交换计算次数的公式 n2,4.4 数 字 签 名,4.4.1 数字签名概述在网络通信和电子商务中很容易发生如下问题：（1）否认，发送信息的一方不承认自己发送过某一信息。（2）伪造，接收方伪造一份文件，并声称它来自某发送方的。（3）冒充，网络上的某个用户冒充另一个用户接收或发送信息。（4）篡改，信息在网络传输过程中已被篡改，或接收方对收到的信息进行篡改。用数字签名可以有效地解决这些问题。数字签名就是主要用于对数字信息进行的签名，以防止信息被伪造或篡改等。,Network and Information Security,注：数字签名与用户的姓名和手写签名形式毫无关系，它实际使用了信息发送者的私有密钥变换（加密）所需传输的信息。对于不同的文档信息，发送者的数字签名并不相同。,美国电子签名标准对数字签名作了如下解释：“数字签名是利用一套规则和一个参数对数据进行计算所得的结果，用此结果能够确认签名者的身份和数据的完整性”,Network and Information Security,Network and Information Security,4.4 数 字 签 名,在文件上手写签名长期以来被用作作者身份的证明，或表示同意文件的内容。手写签名满足以下五个原则：1.签名是可信的。签名使文件的接收者相信签名者在文件上签的字。2.签名不可伪造。签名证明是签字者而不是其他人在文件上签字。3.签名不可重用。签名是文件的一部分，不法之徒不可能将签名移到不同的文件上。4.签名的文件是不可改变的。在文件签名后，文件不能改变。5.签名是不可抵赖的。签名和文件是物理的东西。签名者事后不能声称他没有签过名。,Network and Information Security,当我们要对计算机文件做同样的事情时问题就变得十分复杂。首先计算机文件易于复制。即使某人的签名难以伪造（例如，手写签名的图形），但是从一个文件到另一个文件复制和粘贴有效的签名都是很容易的,这种签名并没有什么意义；其次文件在签名后也易于修改，并且不会留下任何修改的痕迹。,数字签名的要求：,Network and Information Security,（1）收方能够确认或证实发方的签名，但不能伪造。（2）发方发出签名的消息送收方后，就不能再否认他所签发的消息。（3）收方对已收到的签名消息不能否认，即有收到认证。（4）第三者可以确认收发双方之间的消息传送，但不能伪造这一过程。,Network and Information Security,公钥密码学使得数字签名成为可能。用私钥加密信息，这时就称为对信息进行数字签名。将密文附在原文后，称为数字签名。其他人用相应的公钥去解密密文，将解出的明文与原文相比较，如果相同则验证成功，这称为验证签名。,4.4.2 数字签名的方法,Network and Information Security,基本的数字签名协议是简单的：1.Alice用她的私钥对文件加密，从而对文件签名。2.Alice将签名的文件传给Bob。3.Bob用Alice的公钥解密文件，从而验证签名。这个协议没有通过第三方去验证签名。甚至协议的双方也不需要第三方来解决争端。,Network and Information Security,这个协议也满足我们期待的特征：,1.签名是可信的。当Bob用Alice的公钥验证信息时，他知道是由Alice签名的。2.签名是不可伪造的。只有Alice知道她的私钥。3.签名是不可重用的。签名是文件的函数，并且不可能转换成另外的文件。4.被签名的文件是不可改变的。如果文件有任何改变，文件就不可能用Alice的公钥验证成功。5.签名是不可抵赖的。Bob不用Alice的帮助就能验证Alice的签名。,数字签名需要解决的一些问题：（1）签字后的文件可能被B重复使用。如果签字后的文件是一张支票，B很容易多次用该电子支票兑换现金，为此需要在文件中加上一些该支票的特有的凭证，如时间戳，防止上述情况发生。（2）公钥算法效率很低，不易于长文件的加密。,实际的签名：（1）首先利用hash做压缩，然后签名。（2）为了提供签名后消息的保密性，可以用对方的公钥加密后传送。,Network and Information Security,数字签名协议和单向散列函数一起使用。Alice和Bob并不对整个文件签名，只对文件的散列值签名。1.Alice产生文件的散列值，Alice用她的私钥对散列值加密，凭此表示对文件签名。2.Alice将文件和散列签名送给Bob。3.Bob用Alice发送的文件产生文件的散列值，然后用Alice的公钥对签名的散列值解密。 Bob解密的散列值与自己产生的散列值相同，签名就是有效的。计算速度大大地提高了，并且两个不同的文件有相同的160比特散列值的概率为1/2160。因此，使用单向散列函数的签名和文件签名一样安全。,Network and Information Security,多重签名,采用单向散列函数，是容易的：1.Alice对文件的散列值签名。2.Bob对文件的散列值签名。3.Bob将他的签名交给Alice。4.Alice把文件、她的签名和Bob的签名发给Carol。5.Carol验证Alice和Bob的签名。,多重数字签名的目的是将多个人的数字签名汇总成一个签名数据进行传送，签名收方只需验证一个签名便可确认多个人的签名。,Alice和Bob能同时或顺序的完成步骤（1）和（2），Carol可以只验证其中一人的签名而不用验证另一人的签名。,Network and Information Security,4.4.3 带加密的数字签名,通过把公钥密码和数字签名结合起来，我们能够产生一个协议，可把数字签名的真实性和加密的安全性结合起来。想象你写的一封信：签名提供了原作者的证明，而信封提供了秘密性。,图4-6 带加密的数字签名,设用户Alice发送一个签了名的明文M给用户Bob的数字签名的过程：,Network and Information Security,SA(M),EB(SA(M),DB(EB(SA(M)=SA(M),VA(SA(M)=M,Network and Information Security,4.5 数字签名算法,1.数字签名标准（DSS） 在1991年8月30日，美国国家标准与技术学会（NIST）联邦注册书上发表了一个通知，提出了一个联邦数字签名标准，NIST称之为数字签名标准（DSS）。 1994年12月1日正式采用为美国联邦信息处理标准。 NIST提出：“此标准适用于联邦政府的所有部门，以保护未加保密的信息它适用于E-mail、电子金融信息传输、电子数据交换、软件发布、数据存储及其他需要数据完整性和原始真实性的应用”。,Network and Information Security,4.5.1 数字签名算法DSA,1）DSA的参数说明：(a)全局公钥（p,q,g）p: 为L位长的素数，其中，L为5121024之间且是64倍数的数。q: 是160位长的素数，且为p-1的因子。g: g=h(p-1)/q mod p，其中，h是满足1hp-1且h(p-1)/q mod p大于1的整数。(b)用户秘钥x: x为在0 xq-1内的随机数(c)用户公钥y: y=gx mod p(d)用户每个消息用的秘密随机数k, 0kq,注：前三个参数p、q、g是公开的；x为私钥，y为公钥；x和k用于数字签名，必须保密；对于每一次签名都应该产生一次k。,DSS的签名与验证,签名与验证,签名过程：用户随机选取k，计算：r=(gk mod p) mod qs=k-1(H(M)+xr)mod q(r,s)即为消息M的数字签名,验证过程：接收者收到M,r,s后，首先验证0rq, 0sq，如果通过则计算：w=(s)-1 mod q u1=Mw mod qu2=rw mod qv=(gu1yu2) mod p mod q如果v=r，则确认签名正确,假设取q=101，p=78*101+1=7879，h=3, 所以g=378（mod7879) = 170假设x=75，那么ygx(mod7879)=4567现在, 假设Bob想签名一个消息m=1234，且他选择了随机值k=50，可算得k-1(mod101)=99,签名算出: r=(17050mod7879)mod101 =2518(mod101)=94s=(1234+75*94)99(mod101)=97签名为（94，97）,DSS例子签名,w=97-1（mod101)=25 u1=1234*25(mod101)=45 u2=94*25(mod101)=27 v=17045*456727(mod7879)(mod101) =2518(mod101)=94 v=r，该签名是有效的,DSS例子验证,Network and Information Security,4.5.2 RSA签名方案 前面提到RSA可以用于数字签名。我们可以获得私钥d，公钥e和n，则对消息m签名有r=sig(m)=(H(m)d mod n 其中，H(m)计算消息m的消息摘要，可由散列函数SHA1或MD5得到；r即为对消息的签名。 验证签名时，验证：H(m)=re mod n 若上式成立，则签名有效。整个签名过程如图4-5所示。,Network and Information Security,图4-7 RSA数字签名,Network and Information Security,4.6 案例：加密算法综合应用-PGP,第二章讨论了对称密钥加密算法，第三章讨论了散列函数，本章的前几节讨论公开密钥及数字签名。将这些加密算法综合起来进行应用的典型代表就是PGP（Pretty Good Privacy更好的保护隐私）。,Network and Information Security,4.6.1 PGP简介,创作人：Philip Zimmermann（菲尔.齐默尔曼）PGP 于1991年夏季发布1.0版本，PGP最初的设计主要是用于邮件加密。1992年9月，PGP 2.0在欧洲发布，2.0版本中用国际数据加密算法IDEA。目前PGP是由许多人开发，在国际互联网上广为传播的免费软件。但由于美国对信息加密产品有严格的法律约束，特别是对向美国、加拿大之外国家出售、发布该类软件约束的很严格。,Network and Information Security,PGP是一种在信息安全传输领域首选的加密软件，如今已经发展到了可以加密整个硬盘、分区、文件、文件夹、集成进邮件软件进行邮件加密，甚至可以对ICQ的聊天信息实时加密！,PGP主要功能,Network and Information Security,4.6.2 PGP的加密算法和密钥管理,1 PGP使用的加密算法PGP是一种混合加密算法。它是由一个对称加密算法（IDEA） 、一个非对称加密算法（RSA）、一个单向散列算法（MD5）以及一个随机数产生器组成。因为RSA算法不适合加密大量数据，PGP不用RSA来加密信息内容，而是采用IDEA对称加密算法来对邮件内容加密。由于IDEA的加(解)密速度比RSA快得多，发送者用PGP的一个随机生成的密钥(每个邮件均不相同)及IDEA算法对明文加密，然后再用RSA算法和收信人的公开密钥对该随机密钥加密。收信人是用自己的私钥和RSA算法解密出这个随机密钥，再用随机密钥和IDEA算法解密得到邮件明文。,Network and Information Security,2 PGP的密钥管理机制,公钥密码体系解决了传统加密体系密钥分配困难的缺点。而对于PGP来说公钥本来就是要公开