《密码学第7-8章课件》由会员分享，可在线阅读，更多相关《密码学第7-8章课件（44页珍藏版）》请在金锄头文库上搜索。
1、7 公钥密码算法,7.0 概述 7.1 国际标准RSA算法(基于大数分解) 7.2 ElGamal算法(基于离散对数) 7.3 美国标准DSS/DSA算法 7.4 椭圆曲线密码(ECC)算法 7.5 其它公钥密码算法,7.0 公钥密码算法概述,公钥密码算法(非对称算法)用公开密钥(简称公钥)加密，用私人密钥(简称私钥)解密。当消息用私人密钥加密(签名)而用公开密钥解密(验证)时，称为数字签名。 在公钥密码与数字签名算法领域，DSA(数字签名算法)是NIST专门制定的数字签名标准(DSS)算法，只能用于签名验证，不能用于保密或密钥分配，安全强度较低，速度很慢。RSA算法即可用于保密，又可用于签名
2、验证，安全性比DSA算法高，速度也比DSA算法快多了，是第一个较完善的、最容易理解和实现的公钥算法，被很多国家和组织作为标准，包括国际数字签名标准ISO 9796。不过，RSA算法速度也较慢。我国密码学家陶仁骥等在20世纪80年代就提出了一种基于有限自动机的公钥算法(FAPKC)，性能不错，既可用于签名验证，又可用于保密或密钥交换。虽然有些科研人员指出该算法存在缺陷，但只要其思想可取，就是有价值的。密码算法本来就是随着时间和实践逐步完善的。陶仁骥等已提出了新的改进算法。FAPKC算法可能是我国20世纪所公布的唯一有完全自主知识产权的密码算法。,7.0 公钥密码算法概述（续）,现在，有一种称为E
3、CC(椭圆曲线密码)的公钥算法，性能优越，安全性比RSA算法高多了，速度也比RSA算法快多了，带宽要求低，曲线资源丰富，易于软硬件和智能卡实现，已成为新的公钥密码和数字签名国际标准，并被我国采纳。加拿大和日本向NESSIE提交的几个公钥密码和数字签名算法就是基于ECC的。我国科研人员陈建华教授在ECC领域做出了较大贡献。 非对称算法(公钥密码算法)的基本设计思想是计算复杂性和陷门单向函数。,7.0 公钥密码算法概述 与对称算法结合,在实际应用中，公钥密码算法不会取代对称算法。公钥密码算法一般不用来加密消息，而用作身份认证和加密会话密钥。因为：（算法是公开且好的算法有限，所以需要加密密钥和解密密
4、钥） 1. 对称算法一般比公钥算法快一千倍。 2. 公钥密码系统对选择明文攻击是脆弱的。如果C=E(P)，当P是N个可能明文集中的一个明文，那么密码分析者只需要加密所有N个可能的明文，并能与C比较结果(加密密钥是公开的)。用这种方法，他不可能恢复解密密钥，但他能够确定P。 在大多数实际应用中，公钥密码用作身份认证和加密会话密钥。这些会话密钥用在对称算法中，对通信消息进行保密。有时称这种系统为混合密码系统。 把公钥密码用于密钥分配解决了很重要的密钥管理问题。,7.0 公钥密码算法概述 与Hash函数结合,在实际的实现过程中，采用公钥密码算法对长文件签名效率太低。为了节约时间，数字签名协议经常和单
5、向Hash函数一起使用。并不对整个文件签名，只对文件的Hash值签名。 由于公钥密码算法用于保密和用于签名的原理是一样的，此处只介绍数字签名算法。,7.1 RSA算法(基于大数分解),RSA是第一个既能用于数据加密也能用于数字签名的算法。算法的名字以发明者的名字命名：Ron Rivest, Adi Shamir 和Leonard Adleman。RSA的安全性一直未能得到理论上的证明。它经历了各种攻击，至今未被完全攻破。 RSA算法过程： 首先, 选取三个数, p, q, e, 其中 p, q是两个相异的大质数, e是与(p-1)(q-1)互质的数，计算 n = p*q，e, n便是公钥；接著
6、, 用欧几里德扩展法计算d, 使得de1 mod (p-1)(q-1)，p, q, d便是私钥。假设被签消息为M，则 签名过程为S = M d mod n 验证过程为M = S e mod n,7.1 RSA算法 性能,由于进行的都是大数计算，使得RSA最快的情况也比DES慢上100倍，无论是软件还是硬件实现。速度一直是RSA的缺陷。一般来说只用于少量数据加密和签名。 总之，RSA是被研究最广泛的公钥算法，从提出到现在已经二十年，经历了各种攻击的考验，普遍认为是当时最优秀的公钥方案之一。RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价，即RSA的重大缺
7、陷是无法从理论上把握它的保密性能如何。RSA的缺点主要有：A)产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。B)分组长度太大，为保证安全性，n至少也要600 b以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。目前，SET(安全电子商务)协议中要求CA采用2048 b长的密钥，其他实体使用1024 b的密钥。IEEE已批准RSA成为802.11标准的补充标准。,7.2 ElGamal算法(基于离散对数),ElGamal算法既能用于数据加密也能用于数字签名。 密钥对产生办法为：首先选择一个素数p，
8、两个随机数g和x，g, x p, 计算 y = g x mod p，则其公钥为y, g和p。私钥是x。g和p可由一组用户共享。ElGamal数字签名过程为： 假设被签消息为M，首先选择一个随机数k, k与 p-1互质，计算a = g k mod p。再用扩展 Euclide算法对下面方程求解b： M = x a + kb mod (p-1)。签名就是(a, b)。随机数k须丢弃。 验证时要验证下式：( y a a b ) mod p = g M mod p。同时一定要检验是否满足1a p。否则签名容易伪造。ElGamal签名的安全性依赖于乘法群上的离散对数计算难题。 素数p必须足够大，且p-1
9、至少包含一个大素数因子以抵抗Pohlig & Hellman算法的攻击。M一般都应采用消息的散列值(如SHA算法序列)。ElGamal的安全性主要依赖于p和g，若选取不当则签名容易伪造，应保证g对于p-1的大素数因子不可约。ElGamal的一个不足之处是它的密文成倍扩张。,7.3 美国标准DSS/DSA算法,DSA (数字签名算法)是Schnorr和ElGamal签名算法的变种，是美国NIST专门制定的数字签名标准(DSS)算法，只能用于签名验证，不能用于保密或密钥分配。 DSA算法的安全性依赖于整数有限域上的离散对数问题，安全强度和速度均低于RSA算法。,7.4 椭圆曲线密码(ECC)算法,
10、(基于椭圆曲线上的离散对数) ECC(椭圆曲线密码)算法性能优越，安全性比RSA算法高多了，速度也比RSA算法快多了，带宽要求低，曲线资源丰富，易于软硬件和智能卡实现，已成为新的公钥密码和数字签名国际标准，并被我国采纳。加拿大和日本向NESSIE提交的几个公钥密码和数字签名算法就是基于ECC的。我国科研人员陈建华教授在ECC领域做出了较大贡献。ECC已被IEEE公钥密码标准P1363采用。,7.5 其它公钥密码算法,公钥密码算法还有Rabin算法、Schnorr算法、俄罗斯数字签名标准GOST算法和日本的ESIGN算法等。 Rabin算法的安全性低于RSA算法；Schnorr算法的安全性低于E
11、lGamal算法。 GOST算法安全性很高，但速度比DSA算法慢，公钥参数的生成和存储也比DSA算法复杂。 ESIGN算法的安全性不低于RSA和DSA，但速度快多了。,8 常用认证与密钥交换算法,认证与密钥交换协议比较多，可分为两类：1）对称认证(与密钥交换)，即常用的口令认证，例如EAP-MD5和移动通信系统中的AKG(认证与密钥产生)等。2）非对称认证(与密钥交换)，基于公钥密码算法。著名的非对称认证协议是ITU-T X.509协议；著名的密钥交换协议是IKE(互联网密钥交换)中采用的Diffie-Hellman协议。欧洲的非对称认证新标准是法国人Ecole Normale Suprieu
12、re设计的GPS算法。,8 常用认证与密钥交换算法 8.1 Diffie-Hellman算法,IKE(互联网密钥交换)中采用的Diffie-Hellman密钥交换协议是第一个公钥密码算法，早在1976年就提出了，其安全性源于有限域上计算离散对数比计算指数更为困难。首先，A和B协商一个大素数n和g，g是模n的本原元；这两个整数不必保密；要求(n-1)/2也是素数。则Diffie-Hellman算法过程如下： (1)A选取一个大随机整数x并把X = g x mod n发送给B； (2)B选取一个大随机整数y并把Y = g y mod n发送给A； (3)A计算K = Y x mod n； (4)B
13、计算K* = X y mod n。 K = K* = g y x mod n，密钥交换成功。,8 常用认证与密钥交换算法 8.2 GPS算法,GPS算法是NESSIE收到的唯一的非对称认证方案，被采纳为欧洲标准。这是一个交互式零知识证明协议，其特点为：基于一般任意模数离散对数问题(这等价于整数分解问题和计算素数模的离散对数问题)的可证明安全性，身份密钥短，信息传输量非常小，在线计算量最小化。 GPS算法是Schnorr的改进方案。,8.3 对称密码体制中的密钥管理 (1)对称密码体制中密钥分配的基本方法,两个用户A和B获得共享密钥的方法有以下几种： 密钥由A选取并通过物理手段发送给B。 密钥由
14、第三方KDC选取并通过物理手段发送给A和B。 如果A、B事先已有一密钥，则其中一方选取新密钥后，用已有的密钥加密新密钥并发送给另一方。 如果A和B与第三方KDC分别有一保密信道，则C为A、B选取密钥后，分别在两个保密信道上发送给A、B。,第4种方法比较常用，其中的第三方通常是一个负责为用户分配密钥的密钥分配中心。这时每一用户必须和密钥分配中心有一个共享密钥，称为主密钥。通过主密钥分配给一对用户的密钥称为会话密钥，用于这一对用户之间的保密通信。通信完成后，会话密钥即被销毁。如上所述，如果用户数为n，则会话密钥数为n(n-1)/2。但主密钥数却只需n个，所以主密钥可通过物理手段发送。,8.3 对称
15、密码体制中的密钥管理 (2)密钥的分层管理,网络中如果用户数目非常多而且分布的地域非常广，一个KDC就无法承担为用户分配密钥的重任。问题的解决方法是使用多个KDC的分层结构。例如，在每个小范围（如一个LAN或一个建筑物）内，都建立一个本地KDC。同一范围的用户在进行保密通信时，由本地KDC为他们分配密钥。如果两个不同范围的用户想获得共享密钥，则可通过各自的本地KDC，而两个本地KDC的沟通又需经过一个全局KDC。这样就建立了两层KDC。类似地，根据网络中用户的数目及分布的地域，可建立3层或多层KDC。分层结构可减少主密钥的分布，因为大多数主密钥是在本地KDC和本地用户之间共享。再者，分层结构还
16、可将虚假KDC的危害限制到一个局部区域。,8.3 对称密码体制中的密钥管理 (3)会话密钥的有效期,会话密钥更换得越频繁，系统的安全性就越高。因为敌手即使获得一个会话密钥，也只能获得很少的密文。但另一方面，会话密钥更换得太频繁，又将延迟用户之间的交换，同时还造成网络负担。所以在决定会话密钥的有效期时，应权衡矛盾的两个方面。 对面向连接的协议，在连接未建立前或断开时，会话密钥的有效期可以很长。而每次建立连接时，都应使用新的会话密钥。如果逻辑连接的时间很长，则应定期更换会话密钥。 无连接协议(如面向业务的协议)，无法明确地决定更换密钥的频率。为安全起见，用户每进行一次交换，都用新的会话密钥。然而这又失去了无连接协议主要的优势，即对每个业务都有最少的费用和最短的延迟。比较好的方案是在某一固定周期内或对一定数目的业务使用同一会话密钥。,8.3 对称密码体制中的密钥管理 (4)无中心的密钥协商, A向B发出建立会话密钥的请求和一个一次性随机数N1。 B用与A共享的主密钥MKm对应答的消息加密，并发送给A。应答的消息中有B选取的会话密钥、B的身份、f(
