Ch04+公钥密码体制

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,网络与信息安全,Ch04 公钥密码体制,1,本章学习目的,掌握,公钥密码体制的基本概念、原理,掌握,基本的数学理论,理解RSA算法,了解其它的密码体制，如ElGamal算法、椭圆曲线密码算法,理解,密钥交换原理,理解数字签名技术、标准,2,传统密码系统有两个特点：,加密和解密时所使用的密钥是,相同的或者类似的,，从加密钥可以很容易地推导出解密钥，反之亦然，因此我们常称传统密码系统为单钥密码系统或对称钥密码系统。,在一个密码系统中，我们不能假定加密算法和解密算法是保密的，因此密钥必须保密。然而发送信息的通道往往是不可靠的，所以在传统密码系统中，必须用不同于发送信息的另一个信道来发送密钥。,3,密码学的新方向,1976,年，美国学者Diffie和Hellman为解决密钥的分发与管理问题发表了著名论文密码学的新方向New Direction in Cryptography，提出一种密钥交换协议，允许在,不安全的媒体,上通过通讯双方交换信息，安全地传送秘密密钥，并提出了建立“,公开密钥密码体制,”(Public Key)的新概念。,这篇文章中提出的公钥密码的思想：若每一个用户A有一个加密密钥ka，不同于解秘密钥ka，加密密钥ka公开，ka保密，当然要求ka的公开不至于影响ka的安全。若B要向A保密送去明文m，可查A的公开密钥ka，若用ka加密得密文c，A收到c后，用只有A自己才掌握的解密密钥ka对x进行解密得到m。,当时他们还没有实现这种体制的具体算法。,4,1976年，W. Diffie和N.E.Hellman发表的著名论文“密码学的新方向”，奠定了公钥密码的基础。公钥密码系统提出了一系列新颖的概念和思想，开创了密码学的新时代，其特点是：,加密钥和解密钥本质是不同的，知道其中一个，不存在一个有效地推导出另一个密钥的算法，所以公钥密码系统常又被称为双钥密码系统或非对称密码系统；,不需要分发密钥的额外信道，我们可以公开加密钥，这样无损于整个系统的保密性，需要保密的仅仅是解密钥。,公钥密码系统还带来认证性的好处。,5,41、 公钥密码的理论基础,公开钥,明文,密文,私钥,明文,秘密钥,秘密钥,明文,密文,明文,密钥建立,6,单向函数,单向函数,：计算,F(m, K)c,容易，但由,c,计算,m,不容易。,在密码学中最常用的单向函数有两类，,一是公开密钥密码中使用的单向,陷门,函数、,二是消息摘要中使用的单向散列函数。,7,大数分解问题RSA公钥密码,有限域上的离散对数问题ElGamal公钥密码,椭圆曲线上离散对数问题,陷门单向函数,：如果已知,K,，由,c,计算,m,是不容易的，但如果知道陷门秘密,d,(,K,)，由,c,就能容易的得到,m,。,所以,单向函数不能用作加密，可以用陷门单向函数来解释公钥密码系统,。,计算难易计算复杂性理论为基础,8,公钥密码与对称钥密码的比较：,公钥密码：不需共享密钥；理论基础坚实；产生数字签名;,速度慢、密钥长.,对称钥密码：速度快，密钥短，,可作为基本单元构建,各种密码工具如伪随机数产生器、,Hash,函数；,需要实现共享密钥、密钥管理困难；,没有可证明安全性；,公钥密码有效的数字签名和密钥管理；少量数据的加密，,公钥常用于加密对称密钥。这样的系统称为,混合密码系统,。,对称钥密码有效的大量数据加密和一些数据完整性应用。,9,公钥密码体制(加密)概念,一 基本概念、原理,每个用户都有一对预先选定的密钥：一个是,公钥,，以,k1,表示，另一个是,私钥,，以,k2,表示，公钥,k1,是公开的，任何人都可以得到，私钥是其拥有者自己保存。,10,公钥密码（加密）+认证,一 基本概念、原理,公钥密码体制既可用于实现公共通信网的保密通信，也可实现信息保密性和对消息的认证。,11,数论知识简介,互素：若最大公因子gcd(a,b)=1，则整数a和b互素。,定义：若a,x mod n =1,，则称a与x对于模n互为逆元。,用欧几里得Euclid算法求乘法逆元,若a和n互素，则a在模n下有逆元。,二 数学基础,12,欧拉函数,欧拉Euler函数：,(n)=,与n互素的、小于n的正整数的个数，n1。例：,(3)= (4) =2,，,(5)=4,，,(7),=6,13,数论知识简介,模运算性质：同余,模运算满足自反性、对称性、传递性；,a=a mod n；,若a=b mod n，则b=a mod n；,若a=b mod n，b=c mod n，则a=c mod n,若a mod n=b mod n，则(a-b)mod n=0；,(a mod n) +(b mod n)mod n=(a + b) mod n；,- - ；,* * ；,例：15,2,mod 12 =(3*3) mod 12=9,二 数学基础,14,若n是素数，则,(n)=n-1,若n=p*q，p、q是素数，则,(n)=(p-1)*(q-1),例：,(21)= (3*7)=2*6=12,二 数学基础,数论知识简介,定理,：若 p 是素数，e是一个正整数，则,15,费马Fermat定理,若,m,是素数，且,a,不是,m,的倍数，则,a,m-1,mod m=1,。,或者：若,m,是素数，则,a,m,mod m=a,例：,4,6,mod 7=4096 mod 7=1,4,7,mod 7=16384 mod 7=4,其中,是同余运算符,16,欧拉Euler定理：a,(n),mod n =1,推论：若a与n互素，则a与a,(n)-1,互为逆元。,例：a=4，n=7，,(7)=6,，,a,(7)-1,=4,5,=1024,所以，4和1024在模7下互为逆元。,验证：4x1024 mod7 =1,二 数学基础,数论知识简介,例：,即2和6对于模11互为逆元,17,例如：,m=3, n=10;,(10)=4,m,(n),=3,4,=81 ;,81,mod 10 = 1,即,81 1 mod 10,3,4+1,= 243 3 mod 10,欧拉定理,若整数,m,和,n,互素，则,等价形式,18,例：,19,高次幂剩余的运算,欧几里德算法,欧几里德算法可以迅速地找出给定的两个整数a和b的最大公因数 gcd（a，b），并可判断a与b是否互素，因此该算法可用来寻找加密密钥和解密密钥,。,二 数学基础,20,高次幂剩余的运算,二 数学基础,例：gcd(98,44)=?,98=44*2+,10,44=10*4+,4,10=4*2+,2,4=,2,*2+0,余数为0，则有最大公约数，且为2；,21,欧几里得算法（辗转相除法）,求最大公因子,22,欧几里得算法求逆元,用扩展欧几里得算法计算,若a和n互素，则a在模n下有逆元，记做a,-1,。,定义：若a,x mod n =1,，则称a与x对于模n互为逆元。,用欧几里得Euclid算法求乘法逆元，即存在两个整数x，y（可为负数）使得x,a,+y,n,=1。,23,例：用扩展欧几里得算法计算37,-1,mod98,解：,37和98互素，即gcd（37，98）=1,98=2*37+24,37=1*24+13,24=1*13+11,13=1*11+2,11=5*2,+1,接着辗转代换,1,=11-5*2,=11-5*(13-1*11),=6*11-5*13,=6*(24-1*13)-5*13,=6*24-11*13,=6*24-11*(37-1*24),=17*24-11*37,=17*(98-2*37)-11*37,=17*98,-45,*37,一般取最小非负整数，故,=17*98-(98-53)*37=53*37-81*37,即,37,模,98,的逆元为,53,。,24,1 RSA算法概述,三 RSA算法,掌握,传统密码体制的缺陷：,密钥管理的麻烦：n个用户保存n*(n-1)/2个密钥。,不能提供法律证据 :不仅要保密还要解决证实问题。,1976年，美国学者Diffie和Hellman发表了著名论文密码学的新方向，提出了建立“公开密钥密码体制”：若用户A有加密密钥ka（公开），不同于解秘密钥ka（保密），要求ka的公开不影响ka的安全。,若B要向A保密送去明文m,可查A的公开密钥ka，用ka加密得到密文c，A收到c后，用只有A自己才掌握的解密密钥ka对x进行解密得到m。,RSA(Rivest-Shamir-Adelman),25,2 RSA算法概述,1978,年，美国麻省理工学院,(MIT),的研究小组成员：李维斯特,(Rivest),、沙米尔,(Shamir),、艾德曼,(Adleman),提出了一种基于公钥密码体制的优秀加密算法,RSA,算法。,RSA,算法是一种分组密码体制算法，它的保密强度是建立在具有大素数因子的合数，其因子分解是困难的。,RSA,得到了世界上的最广泛的应用，,ISO,在,1992,年颁布的国际标准,X.509,中,将,RSA,算法正式纳入国际标准。,1999,年美国参议院已通过了立法，规定电子数字签名与手写签名的文件、邮件在美国具有同等的法律效力。,三 RSA算法,26,3 RSA算法概述,每个合数都可以唯一地分解出素数因子,6 = 2 3,999999 = 3337111337,27641 = 131121,从2 开始试验每一个小于等于27641 的素数。,素数：只能被1和它本身整除的自然数；否则为合数。,整数n的十进制位数 因子分解的运算次数 所需计算时间（每微秒一次）,501.4x10,10,3.9,小时,759.0x10,12,104,天,1002.3x10,15,74,年,2001.2x10,23,3.8x10,9,年,3001.5x10,29,4.0x10,15,年,5001.3x10,39,4.2x10,25,年,三 RSA算法,27,4 素数的产生,目前，适用于RSA算法的最实用的办法是概率测试法。该法的思想是随机产生一个大奇数，然后测试其是否满足条件，如满足，则该大奇数可能是素数，否则是合数。,素数定理说明素数有无穷多个，同时也说明通过随机产生一个大奇数来判断其素性是具有实用性的。,三 RSA算法,28,5 RSA算法的实现,RSA,加密算法的过程,取两个随机大素数,p,和,q,（,保密）,计算公开的模数,n=p*q(,公开,),计算秘密的欧拉函数,(n) =,（,p-1,)*,(q-1),（,保密），丢弃,p,和,q,，不要让任何人知道。,随机选取整数,e,满足,gcd(e,(n)=1(,公开,e,加密密钥,),计算,d,满足,de,1(mod,(n)(,保密,d,解密密钥,),加密：,将明文,x,（,按模为,r,自乘,e,次幂以完成加密操作，从而产生密文,y,（,X,、,Y,值在,0,到,n-1,范围内）。,Y=,x,e,mod n,解密：,将密文,y,按模为,n,自乘,d,次幂。,X=Y,d,mod n,三 RSA算法,29,6 RSA算法的实现,例设p=43,q=59,r=p,q=43*59=2537, ,(r)=(p-1)(q-1) =42*58 =2436, 取,e=13,求e的逆元d,解方程 d,e = 1 mod 2436,2436 =13* 187+ 5, 13= 2* 5+ 3,5= 3+ 2, 3= 2+ 1,所以1= 3- 2 ，2= 5- 3， 3 =13- 2* 5,5 =2436- 13* 187,所以，1= 3- 2= 3-（ 5- 3）= 2* 3- 5,=2*（ 13- 2* 5）- 5= 2 *13- 5* 5,=2* 13- 5*（ 2436 -13 *187）,=937* 13- 5* 2346,即937* 13,1 mod 2436,取e= 13 时d= 937,三 RSA算法,30,例：,(1) p11, q=23,(2) n=pq=1123=253,(3) 取e=3，gcd(3,220)=1，e为公钥；,(4),由扩展欧几里的算法求出3 mod 220的逆为 d=147。,(5) 明文空间为,对于明文m=165，则密文,(6) 解密过程,31,关于素数的分布,1 - 100 25,101 - 200 21,201 - 300 16,301 - 400 16,401 - 500 17,501 - 600 14,601 - 700 16,701 - 800 14,801 - 900 15,901 - 1000 14,素数定理：当X变得很大时，从2到X区间的素数数目,(X),与X/ln(X)的比值趋近于1，即,(X),X/ln(X),= 1,lim,x,X,(X) X/ln(X),(X),X/ln(X),1000 168 145 1.159,10,000 1,229 1,086 1.132,100,000 9,592 8,686 1.104,1,000,000 78,498 72,382 1.084,10,000,000 664,579 620,421 1.071,100,000,000 5,761,455 5,428,681 1.061,1,000,000,000 50,847,478 48,254,942 1.054,三 RSA算法,7 素数的分布,32,依赖于大数分解，但是否等同于大数分解一直未能证明。不管怎样，分解,n,是最显然的攻击方法。,1994,年,4,月,26,日，美国各大媒体报道：由,RSA,发明人在,17,年前出的,129,位数字已被因子分解。,目前，已能分解,140,位十进制的大素数。因此，模数,n,必须选大一些。,RSA,最快的情况也比,DES,慢上,100,倍，无论是软件还是硬件实现。速度一直是,RSA,的缺陷。一般只用于少量数据加密。,三 RSA算法,8 RSA的安全性,33,不能证明,RSA,密码破译等同于大数因子分解,速度问题 提高,p,q,将使开销指数级增长,至少有,9,个明文,，,加密后不变，即,m,e,mod n=m,普通用户难于选择,p,、,q,。对,p,、,q,的基本要求：,p,、,q,不相同，即不要太接近，又不能差别太大,p-1,、,q-1,都有大素数因子，增加猜测,(r),难度,Gcd,(,p-1,q-1),应当小,三 RSA算法,8 RSA的安全性,34,P,、,q,选择不当，则变换周期性、封闭性而泄密,例：,p=17,，,q=11,，,e=7,，则,n=187,。设,m=123,，,则,C1=123,7,mod 187=183,C2=183,7,mod 187=72,C3=72,7,mod 187=30,C4=30,7,mod 187=123,明文,m,经过,4,次加密，恢复成明文。,总之，,RSA,对用户要求太苛刻，密钥不能常更换。,三 RSA算法,8 RSA的安全性,35,其它公钥密码体制,背包体制 1978年提出 5年后被 Shamir破解,ElGamal 体制 1985年 基于有限域上计算离散对数难解性，已用于DSS(数字签名标准）,例：3,x,mod 17=5，解得：x=6,3,x,mod 13=7， 无解,椭圆曲线体制(ECC) 1985年 基于离散对数,优点：安全性高；密钥短；灵活性好。,同等安全下的密钥长度：,RSA:512 1024 2048 21000,ECC:106 160 211 600,四 其它密码体制,36,4.3 Diffie Hellman密钥交换算法,第一个发表的公开密钥算法，1976,用于通信双方安全地协商一个会话密钥,只能用于密钥交换,基于离散对数计算的困难性,主要是模幂运算 a,p,mod n,37,离散对数,对数是指数的反函数： b= a,i,= i= log,a,b ;,模运算如何？ b,a,i,mod p = i = log,a,b mod p ？,素根（Primitive Root）,a是素数p 的一个素根，如果,a mod p, a,2,mod p , , a,p-1,mod p 是1到p-1的排列,38,离散对数(续),对于任何整数b 和素数p 的一个素根a, 可以找到一个唯一的指数i，使得：,b = a,i,mod p , 其中0,i(p-1),i 称为 b 的以a 为底模p的离散对数或指数，记为 ind,a,p,(b),对比：对数运算： i = log,a,（b） mod p,ind,a,p,(1)=0, 因为 a,0,mod p =1 mod p =1;,ind,a,p,(a)=1 因为 a,1,mod p =a mod p =a;,39,离散对数(续),y = g,x,mod p,已知 g, x , p 计算y 是容易的，,已知g, y, p , 计算x 是非常困难的,40,Diffie-Hellman 密钥交换过程,全局公开的参数：,q 是一个素数，,a q , a是q 的一个素根,A 选择一个私有的X,A,X,A, q,计算公开的Y,A,Y,A,= a,X,A,mod q,B 选择一个私有的X,B, X,B, q,计算公开的Y,B, Y,B,= a,X,B,mod q,Y,A,Y,B,A计算会话密钥,K=(Y,B,),X,A,mod q,B计算会话密钥,K=(Y,A,),X,B,mod q,E,K,(m),41,证明K=K,五 密钥交换,K=(Y,B,),XA,mod p,=(a,XB,mod p),XA,mod p,=(a,XB,),XA,mod p /取模规则,=a,XAXB,mod p,=(a,XA,),XB,mod p,=(a,XA,mod p),XB,mod p,=(Y,A,),XB,mod p,=K,42,Diffie-Hellman 密钥交换过程,例：,全局公开参数： q=97, a = 5 ( 5是97 的素根）,A选择私钥 X,A,=36 , B 选择私钥 X,B,=58,A 计算公钥 B 计算公钥,Y,A,= 5,36,mod 97 = 50 Y,B,= 5,58,mod 97=44,A 与 B 交换公开密钥,A 计算会话密钥,K = Y,B,X,A,mod q = 44,36,mod 97= 75,B 计算会话密钥,K = Y,A,X,B,mod q = 44,36,mod 97= 75,43,Diffie-Hellman 密钥交换算法,Diffie 和Hellman 并没有给出公钥密码实例，也既没能找出一个真正带,陷门,的单向函数。然而，他们给出单向函数的实例，并且基于此提出D-H密钥交换算法。,这个算法是基于有限域中计算离散对数的困难性问题之上的：对任意正整数x，计算g,x,是容易的；但是已知g和y求x使y= g,x,，是计算上几乎不可能的。这称为有限域上的离散对数问题。,公钥密码学中使用最广泛的有限域为素域,F,P,。D-H密钥交换算法拥有美国和加拿大的专利。,五,密钥交换原理,44,D-H密钥交换协议：A和B协商一个大素数p和大整数a，1ap，a是F,P,中的一个原根，即a,x,mod p可生成1p-1中的各整数，例：2是11的本原元。p和a公开。,当A和B按如下步骤进行保密通信：,(1)A取大的随机数X,A,，并计算Y,A,= a,XA,mod P,(2)B取大的随机数Y,B,，并计算Y,B,=,a,XB,mod P,(3)Y,A,、Y,B,是公开的，B可以获得Y,A,，同样A可以获得Y,B,(4)A计算,K=(Y,B,),XA,mod,P；B计算K,(Y,A,),XB,mod P,可以验证，K=K,A和B已获得了相同的秘密值K。双方以K作为加解密钥以传统对称密钥算法进行保密通信。,Diffie-Hellman 密钥交换算法,五,密钥交换原理,45,优缺点,五 密钥交换,优点,需要时生成密钥，防止长期存放密钥,只需要全局参数，无其它事先约定,缺点,无身份认证的任何信息,易遭受阻塞性攻击,无法防止重放攻击,易受到中间人攻击,46,非对称密码算法原理,对称密钥密码系统的缺陷,密钥必须经过安全的信道分配,无法用于数字签名,密钥管理复杂 O(n,2,),非对称密钥密码，也称公开密钥密码，由,Diffie, Hellman 1976年提出,使用两个密钥，对于密钥分配、数字签名、认证等有深远影响,基于数学函数而不是代替和换位，密码学历史上唯一的一次真正的革命,47,公钥密码系统的加密原理,每个通信实体有一对密钥（公钥，私钥）。公钥公开，用于加密和验证签名，私钥保密，用作解密和签名,A向B 发送消息，用B的公钥加密,B收到密文后，用自己的私钥解密,PlainText,加密,算法,解密,算法,A,B,cipher,PlainText,B的私钥,C的公钥,B的公钥,任何人向B发送信息都可以使用同一个密钥(B的公钥)加密,没有其他人可以得到B 的私钥，所以只有B可以解密,48,公钥密码系统的签名原理,A向B 发送消息，用A的私钥加密（签名）,B收到密文后，用A的公钥解密（验证）,PlainText,加密,算法,解密,算法,cipher,PlainText,A,B,A的私钥,A的公钥,49,公钥密码算法的表示,对称密钥密码,密钥：会话密钥（Ks）,加密函数：C= E,Ks,P,对密文C，解密函数：D,Ks,C，,公开密钥,(KUa，,KRa,),加密/签名：C= E,KUb,P，E,KRa,P,解密/验证：P= D,KRb,C，D,KUa,C,50,数字签名和加密同时使用,X,加密,（签名）,加密,解密,解密,（验证）,X,Y,Z,Y,Z= E,KUb,Y = E,KUb, E,KRa,(X) ,X= D,KUa,Y = D,KUa, D,KRb,(Z) ,A,B,产生密钥对,产生密钥对,KRa,KUa,KRb,KUb,51,对公开密钥密码算法的要求,1.参与方B容易产生密钥对（KUb, KRb）,2.已知KUb，A的加密操作是容易的：,C=E,KUb,(P),3.已知KRb，B解密操作是容易的:,P=D,KRb,(C) =D,KRb,( E,KUb,(P) ),4. 已知KUb，求,KRb,是计算上不可行的；,5. 已知KUb和C, 欲恢复P是计算上不可行的。,52,公钥密码系统的应用,三种用途：,加密/解密：,数字签名：发送方用自己的,私钥,签署报文，接收方用对方的公钥验证对方的签名。,密钥交换：双方协商会话密钥,算法,加密/解密,数字签名,密钥交换,RSA,Y,Y,Y,Diffie-Hellman,N,N,Y,DSA,N,Y,N,53,RSA用于密钥交换举例,假定现在要加密一些数据使用对称密钥12345。,利用RSA公钥，RSA算法加密这个密钥12345。并把它放在要加密的数据的前面（可能后面跟着一个分割符或文件长度，以区分数据和密钥）。,使用对称加密算法加密正文，使用的密钥就是12345。,当对方收到时，解密程序找到加密过的密钥，并利用RSA私钥解密出来。,确定出数据的开始位置，利用密钥12345来解密数据。这样就使得一个可靠的经过高效加密的,数据安全,地传输和解密。,54,RSA用于密钥交换原理,使用公钥来加密一个,对称加密算法,的密钥，然后再利用一个快速的对称加密算法来加密大量数据。,这个,对称算法,的密钥是随机产生的，是保密的，因此，得到这个密钥的唯一方法就是使用私钥来解密。,55,对公钥密码算法的误解,公开密钥算法比对称密钥密码算法更安全？,任何一种算法都依赖于密钥长度、破译密码的工作量，从抗分析角度，没有一方更优越,公开密钥算法使对称密钥成为过时了的技术？,公开密钥很慢，只能用在密钥管理和数字签名，对称密钥密码算法将长期存在,使用公开密钥加密，密钥分配变得非常简单？,事实上的密钥分配既不简单，也不有效,56,数字签名技术,数字签名概念,在计算机网络应用过程中，有时不要求电子文档的保密性，但必须要求电子文档来源的真实性。,数字签名(digital signature)是指利用数学方法及密码算法对电子文档进行防伪造或防篡改处理的技术。就象日常工作中在纸介质的文件上进行签名或按手印一样，它证明了纸介质上的内容是签名人认可过的，可以防伪造或篡改。,随着计算机网络的迅速发展，特别是电子商务、电子政务、电子邮件的兴起，网络上各种电子文档交换的数量越来越多，电子文档的真实性显得非常重要。数字签名技术能有效地解决这一问题。,57,1 概念,鉴别文件或书信真伪的传统做法亲笔签名或盖章。签名起到认证，核准，生效的作用。电子商务、政务要求对电子文档进行辨认和验证，因而产生数字签名。,数字签名的作用：,保证信息完整性；,提供信息发送者的身份认证。,与传统签名的区别：,需要将签名与消息绑定在一起。,通常任何人都可验证。,要考虑防止签名的复制、重用。,六 数字签名,58,手写签名与数字签名的主要差别,签署文件方面,手写签名与被签的文件在物理上不可分割,数字签名,能与所签文件“绑定”,验证方面,手写签名通过与一个真实的手写签名相比较,数字签名通过公开的验证算法来验证,“拷贝”方面,手写签名不易拷贝,数字签名容易拷贝,59,1 概念,六 数字签名,数字签名(Digital Signature),信息发送者使用公开密钥算法技术，产生别人无法伪造的一段数字串。,发送者用自己的,私有密钥,加密数据传给接收者，接收者用发送者的公钥解开数据后，就可确定消息来自于谁，同时也是对发送者发送的信息的真实性的一个证明。发送者对所发信息不能抵赖。,60,数字签名必须保证,：,可验证：签字是可以被确认的,防抵赖：发送者事后不承认发送报文并签名；,防假冒：攻击者冒充发送者向收方发送文件；,防篡改：收方对收到的文件进行篡改；,防伪造：收方伪造对报文的签名。,签名对安全、防伪、速度要求比加密更高。,61,数字签名的特性,签名是可信的,：任何人都可以方便地验证签名的有效性。,签名是不可伪造的,：除了合法的签名者之外，任何其他人伪造其签名是困难的。这种困难性指实现时计算上是不可行的。,签名是不可复制的,：对一个消息的签名不能通过复制变为另一个消息的签名。如果一个消息的签名是从别处复制的，则任何人都可以发现消息与签名之间的不一致性，从而可以拒绝签名的消息。通过增加时间戳实现。,62,数字签名的过程：,假设A要发送一个电子文件给B。,1系统初始化：选择签名所需的算法、参数,2. 产生签名：A用其私钥加密文件并发送给B ；,3签名验证：B用A的公钥解开A送来的文件,签名体制的构成：签名算法；验证算法,2 签名过程,六 数字签名,63,消息加密产生数字签名的基本方式,64,数字签名技术,问题:,速度慢,公钥算法效率很低,不易用于长文件的加密,信息量大,第三方仲裁时必须暴露明文信息,漏洞:,E,KRa,(x,y),E,KRa,(x),E,KRa,(y) mod n,解决办法：一般采用Hash函数+公钥算法进行数字签名,所谓Hash函数，也称为杂凑函数，即对于任意长度的信息m,经过哈希函数运算后，压缩成固定长度的数,先做摘要: HM = hash(M)，再对HM签名SA=EKRa(HM),hash函数的无碰撞性保证了签名的有效性,65,数字签名技术,消息,Hash函数,消息摘要,发方A,相等？,收方B,加密算法,私钥A,签名,消息,加密的,消息摘要,签名,消息,Hash函数,消息摘要,解密算法,公钥A,签名有效,y,签名无效,n,66,数字签名技术,第一步：,将消息按哈希算法计算得到一个固定位数的消息摘要值。,在数学上保证：只要改动消息的任何一位，重新计算出的消息摘要就会与原先值不符。这样就保证了消息的不可更改,。,67,数字签名技术,第二步：,对消息摘要值用发送者的私有密钥加密，所产生的密文即称数字签名。然后该数字签名同原消息一起发送给接收者。,第三步：,接收方收到消息和数字签名后，用同样的哈希算法对消息计算摘要值，然后与用发送者的公开密钥对数字签名进行解密，将解密后的结果与计算的摘要值相比较。如相等则说明报文确实来自发送者。,68,数字签名的应用例子,现在Alice向Bob传送数字信息，为了保证信息传送的保密性、真实性、完整性和不可否认性，需要对要传送的信息进行数字加密和数字签名，其传送过程如下：,69,Alice准备好要传送的数字信息（明文）。,Alice对数字信息进行哈希（hash）运算，得到一个,信息摘要,。,Alice用自己的,私钥,（SK）对信息摘要进行加密得到Alice的数字签名，并将其附在数字信息上。,Alice随机产生一个加密密钥（DES密钥），并用此密钥对要发送的信息进行加密，形成密文。,数字签名的应用例子,70,Alice用Bob的公钥（PK）对刚才随机产生的加密密钥进行加密，将加密后的DES密钥连同密文一起传送给Bob。,Bob收到Alice传送过来的密文和加过密的DES密钥，先用自己的私钥（SK）对加密的DES密钥进行解密，得到DES密钥。,Bob然后用DES密钥对收到的密文进行解密，得到明文的数字信息，然后将DES密钥抛弃（即DES密钥作废）。,数字签名的应用例子,71,Bob用Alice的公钥（PK）对Alice的数字签名进行解密，得到信息摘要。,Bob用相同的hash算法对收到的明文再进行一次hash运算，得到一个新的信息摘要。,Bob将收到的信息摘要和新产生的信息摘要进行比较，如果一致，说明收到的信息没有被修改过。,数字签名的应用例子,72,数字签名技术,直接数字签名,direct digital signature,Alice,Bob,Pub-A,Pub-B,Pri-A,Pri-B,消息,密文,解密算法,加密算法,密文,消息,Pri-A,Pub-A,73,数字签名标准DSS,Digital Signature Algorithm(DSA),是,Schnorr,和,ElGamal,签名算法的变种，,公布于1994年5月19日的联邦记录上，并于1994年12月1日,被美国,NIST采纳为DSS(Digital SignatureStandard),数字签名标准。,DSS,是由美国国家标准化研究院和国家安全局共同开发的。由于它是由美国政府颁布实施的，主要用于与美国政府做生意的公司，其他公司则较少使用，它只是一个签名系统，而且美国政府不提倡使用任何削弱政府窃听能力的加密软件，认为这才符合美国的国家利益,。,74,DSS算法说明-算法参数,全局公开密钥分量,p 素数, 其中2,L-1,p2,L,512,L1024,且L为64的倍数:即比特长度在512到1024之间,长度增量为64比特,q是(p-1)的素因子, 其中2,159,q2,160,g=h,(p-1)/q,mod p, 其中h是一整数,1h(p-1),用户私有密钥,x 随机或伪随机整数, 其中0xq,用户公开密钥,y=g,x,mod p,用户每个报文的密数,k随机或伪随机整数, 其中0kq,75,DSS算法的签名与验证过程,签名,r=(g,k,mod p)mod q,s=k,-1,(H(M)+xr) mod q,签名=(r,s),验证,w=(s,),-1,mod q,u,1,=H(M,)w mod q, u,2,=( r,) w mod q,v=(g,u1,y,u2,)mod p mod q,TEST: v=r,符号:,M 要签名的消息,H(M)使用SHA-1生成的M的散列码,M,r ,s 接收到的M,r,s版本,76,DSS签名和验证,77,DSS算法的签名与验证实例,用,DSS,签名,假设,取,q=101，p=78*9+1=7879，3,为,F7879,的一个,本原元，,所以能,取,=3,78,mod7879)=170,为模,p,的,q,次,单位,根,假设,a=75 ，,那么,=,a,(mod7879)=4567。,现在,假设,Bob,想,签名一个消息,x=,1234,，,且他选择,了,随,机,值,k=50,可,算得,k,-1,(mod101)=99,签名,算,出,:,r=(170,50,(mod7879)(mod101) =2518(mod101)=94,s=(1234+75*94)99(mod101)=97,签名为（,1234,94,97）,DSS,验证过程,w,-1,=97,-1,( mod101)=25 ,u,1,=1234*25(mod101)=45, u,2,=94*25(mod101)=27,(170,45,*4567,27,(mod7879)(mod101)=2518(mod101)=94,因,此,该,签名是有,效,的,78,注意：,签名与加密,签名提供真实性(authentication),先签名,后加密,加密提供保密性(confidentiality),先加密,后签名:,“签名+加密”提供“真实性+保密性”,79,1,签字后的文件可能被,B,重复使用。如果签字后的文件是一张支票，,B,很容易多次用该电子支票兑换现金，为此,A,需要在文件中加上一些该支票的特有的凭证，如,timestamp,等，以防止上述情况发生。,2,公钥算法效率很低，不易用于长文件的加密。一般采用,Hash,函数，将原文件单向映射为,H=,Hash(P,),，,H,只有几百,bit,，并且由,P,可以很快生成,H,，但由,H,几乎不可能生成,P,。,3,数字签名需要解决的问题,六 数字签名,80,将公钥算法作用在H上生成“签名”S，记为E,k1,（H）=S，k1为A的私钥，A将（P，S）传给B，B收到(P,S)后，要验证S是A的签字。,若D,k2,（S）=Hash（P），则S就是A的签字。,六 数字签名,3,数字签名需要解决的问题,81,）发方用单向散列函数对信息生成摘要。,）用自己的私钥签名信息摘要。,）把信息本身和已签名的信息摘要一起发送出去。,）收方通过使用同一个单向散列函数对接收的信息生成新摘要，再用的公钥对数字签名解密，并与新生成的信息摘要比较，以确认发方的身份和信息是否被修改过。,六 数字签名,3,数字签名需要解决的问题,82,六 数字签名,4 群签名(,群数字签名),定义：允许群中各成员以群的名义匿名地签发消息。即一个群体中的任意一个成员可以以,匿名,的方式代表整个群体对消息进行签名。,83,4 群签名(,群数字签名),特点:,只有群的成员能代表这个群签名；,签名接收者能验证它是这个群的合法签名，但不知具体是哪个成员；,在发生争端时，借助群成员或可信机构能识别出那个签名者。,用途：投标，在公共资源的管理，重要军事情报的签发，重要领导人的选举，电子商务重要新闻的发布，金融合同的签署等事务中,84,5 盲签名(,盲数字签名),所谓,盲签名,，就是将要隐藏的文件放进信封里，而除去盲因子就是打开信封。当文件在信封时，任何人都不能读它。对文件的签名就是通过在信封里放一张复写纸，当签名者在信封上签名时，他的签名便透过复写纸签到了文件上。,85,盲数字签名,消息,M,的拥有者,A,，,想让,B,对,M,签名，但又不希望,B,知道,M,的内容，而只是让,B,以证人身份证实在某一时刻存在文件,M,。,签名步骤：,A,将,M,乘以一个随机数,(,盲因子,),得,M,并发送给,B;,B,在,M,上签名得,SIG(M),，,并发送给,A,；,A,通过去除盲因子，由,SIG(M),得到,SIG(M),。,六 数字签名,5 盲签名,86,5 盲签名,盲签名在某种程度上保护了参与者的利益，但不幸的是盲签名的匿名性可能被犯罪份子所滥用。为了阻止这种滥用，人们又引入了,公平盲签名,的概念。公平盲签名比盲签名增加了一个特性，即建立一个,可信中心,，通过可信中心的授权，签名者可追踪签名。,87,6 双重签名,双重签名：实现三方通信时的身份认证和信息完整性、防抵赖的保护。,例如：,网上购物：客户和商家之间要完成在线付款，在客户(甲) 、商家(乙)和银行(丙)之间将面临以下问题：甲向乙发送订单和甲的付款信息；乙收到订单后，要同丙交互，以实现资金转帐。但甲不愿让乙看到自己的帐户信息，也不愿让丙看到订购信息。此时甲使用双重签名技术对两种信息作数字签名，完成只能让商家看到的,订购信息,，和只能让银行看到的,支付信息,。,88,双重签名实现过程,客户用Hash函数对订购信息和支付信息进行散列处理，分别得到,订购信息的消息摘要,和,支付信息的消息摘要。,将两个消息摘要连接起来再用Hash函数进行散列处理，得到,支付订购消息摘要。,客户用他的私钥加密支付订购消息摘要，最后得到的就是经过,双重签名,的信息。,89,教训,声称你的算法是“不可攻破的”,多次使用一次性密码本,没有使用最好的可用算法,没有正确的实现算法,在产品里放置了后门,90,教训1,声称你的算法是“不可攻破”的,1930年，德国官员声称他们的密码机Enigma是不可攻破的，,第二次世界大战时，Luftwaffe最高指挥部给战场指挥官发布了一条消息，保证Enigma是不可攻破的。,但是我们怎么知道这样一条消息被送出，因为在他发出不久以后英国的密码破译者就截获被解密了它。,1977年， RSA的作者加密了一条消息，为任何解密者提供100美元。,需要40,quadrillion,(百万之四次方)年,17年后破译了他。,91,教训2,多次使用一次性密码本,1930s和1940s，苏联使用一次性密码本加密消息，1942年苏联密码中心偶然打印了一份密码本的复本，,1943年美国的密码分析家发现了这一问题，从而能够破解1942到1948年间发送的消息,1998年，微软发布了PPTP协议，使用RC4连接客户与服务器端，,但两个方向使用同样的密钥,92,教训3,没有使用最好的可能算法,现在有很多加密算法，有些是免费的，有些不是。,微软设计操作系统NT时，提出了一个保护口令的方式，涉及对口令做消息摘要，“LANMAN”，破译者可以几秒内攻破。,93,教训4,没有正确实现算法,Sun 公司发布JDK1.1时，使用了DSA，其中涉及到随机数k。JDK1.1.2修正了他，但计算一次签名需要45秒。,94,教训5,在产品了放置了后门,Clipper 芯片,瑞士公司Crypto AG卖的加密产品。,95,本章小结,理解公钥密码体制的基本原理,知道公钥密码系统的主要用途,掌握RSA算法流程与应用,了解其他公钥密码体制,掌握数字签名的基本概念和工作方式,96,作业,P802、 3、4（3、4题可列出相关计算公式尽量求解）、8,补充题：根据RSA算法原理，选择两个素数,p,为3，,q,为11，试计算公钥(,n,，,e,)和私钥(,n,，,d,)。若明文,M,为8，试计算出密文数据C是什么？并根据解密算法由密文数据还原为明文数据。,97,作业,阅读2011-2012中国互联网安全研究报告，结合自己实际了解的网络安全现状、日常碰到过的网络安全威胁及使用的网络安全措施，撰写2000字左右的我认识的网络安全报告，暂定第10周上交。,98,Any Question?,99,