1、 （1）密钥管理量的困难）密钥管理量的困难 传统密钥管理：两两分别用一对密钥时，则传统密钥管理：两两分别用一对密钥时，则n个用户需要个用户需要C(n,2)=n(n-1)/2个密钥，当用户量增大时，密钥空间急剧增大个密钥，当用户量增大时，密钥空间急剧增大。如。如: n=100 时，时， C(100,2)=4,995 n=5000时，时， C(5000,2)=12,497,500 （2）数字签名的问题）数字签名的问题 传统加密算法无法实现抗抵赖的需求。传统加密算法无法实现抗抵赖的需求。（3）密钥必须经过安全的信道分配）密钥必须经过安全的信道分配问题的提出问题的提出9.1.1 公钥密码机制公钥密码机
2、制 公开密钥算法是公开密钥算法是非对称算法非对称算法，即密钥分为公钥和私钥，因，即密钥分为公钥和私钥，因此称此称双密钥体制双密钥体制 双钥体制的公钥可以公开，因此也称双钥体制的公钥可以公开，因此也称公钥算法公钥算法基于数学函数而不是代替和换位，基于数学函数而不是代替和换位，密码学历史上唯一的一密码学历史上唯一的一次真正的革命次真正的革命公钥密码学是公钥密码学是1976年由年由Diffie和和Hellman在其在其“密码学新方密码学新方向向”一文中提出的公钥算法的出现，给密码的发展开辟了一文中提出的公钥算法的出现，给密码的发展开辟了新的方向。公钥算法虽然已经历了新的方向。公钥算法虽然已经历了20
3、20多年的发展，但仍具多年的发展，但仍具有强劲的发展势头，在有强劲的发展势头，在鉴别系统和密钥交换鉴别系统和密钥交换等安全技术领等安全技术领域起着关键的作用域起着关键的作用9.1 公钥密码学公钥密码学从最初一直到现代，几乎所有密码系统都建立在基从最初一直到现代，几乎所有密码系统都建立在基本的本的替代和置换替代和置换工具的基础上。工具的基础上。在用了数千年的本质上可以手算完成的算法之后，在用了数千年的本质上可以手算完成的算法之后，常规的密码学随着常规的密码学随着转轮加密转轮加密/解密机解密机的发展才出现的发展才出现了一个重大进步。了一个重大进步。机电式变码旋转软件使得极其复杂的密码系统被研机电式
4、变码旋转软件使得极其复杂的密码系统被研制出来。有了计算机后，更加复杂的系统被设计出制出来。有了计算机后，更加复杂的系统被设计出来。来。但是不管是转轮机还是后来的但是不管是转轮机还是后来的DES（数据加密标（数据加密标准），虽然代表了重要的进展，却仍然依赖于替代准），虽然代表了重要的进展，却仍然依赖于替代和置换这样的基本工具。和置换这样的基本工具。密码学历史上唯一的一次真正的革命密码学历史上唯一的一次真正的革命9.1.2 公钥密码的应用公钥密码的应用加密加密/解密解密数字签名数字签名密码交换密码交换公钥密码系统的加密原理公钥密码系统的加密原理 每个通信实体有一对密钥（公钥，私钥）。公钥公开，用每
5、个通信实体有一对密钥（公钥，私钥）。公钥公开，用于加密和验证签名，私钥保密，用作解密和签名于加密和验证签名，私钥保密，用作解密和签名PlainText加密算法解密算法ABcipherPlainTextB的私钥C的公钥B的公钥任何人向B发送信息都可以使用同一个密钥(B的公钥)加密没有其他人可以得到B 的私钥，所以只有B可以解密公钥密码体制的加密功能公钥密码体制的加密功能 A向向B发消息发消息X， B的公钥为的公钥为KUb,私钥为私钥为KRb 加密加密 Y = EKUb(X) 解密解密 X = DKRb(Y) 公钥密码体制的加密公钥密码体制的加密公钥密码系统的签名公钥密码系统的签名/认证原理认证原
6、理 A向向B 发送消息，用发送消息，用A的私钥加密（签名）的私钥加密（签名） B收到密文后，用收到密文后，用A的公钥解密（验证）的公钥解密（验证）PlainText加密算法解密算法cipherPlainTextABA的私钥A的公钥公钥密码体制的认证公钥密码体制的认证 A向向B发送消息发送消息X A的公钥为的公钥为KUa，私钥为，私钥为KRa “加密加密”： Y = EKRa(X) （数字签名）（数字签名） “解密解密”： X = DKUa(Y) 注意：不能保证消息的保密性注意：不能保证消息的保密性公钥密码体制的认证公钥密码体制的认证具有保密与认证的公钥体制具有保密与认证的公钥体制 鉴别保密鉴别
7、保密 :():( )baabKUKRKUKRAB ZEEXB EEZX对称密码对称密码 公钥密码公钥密码一般要求：1、加密解密用相同的密钥、加密解密用相同的密钥2、收发双方必须共享密钥、收发双方必须共享密钥安全性要求：1、密钥必须保密、密钥必须保密2、没有密钥，解密不可行、没有密钥，解密不可行3、知道算法和若干密文不足以确定、知道算法和若干密文不足以确定密钥密钥一般要求：1、加密解密算法相同，但使用不同、加密解密算法相同，但使用不同的密钥的密钥2、发送方拥有加密或解密密钥，而、发送方拥有加密或解密密钥，而接收方拥有另一个密钥接收方拥有另一个密钥安全性要求：1、两个密钥之一必须保密、两个密钥之一
8、必须保密2、无解密密钥，解密不可行、无解密密钥，解密不可行3、知道算法和其中一个密钥以及若、知道算法和其中一个密钥以及若干密文不能确定另一个密钥干密文不能确定另一个密钥对公钥密码算法的误解对公钥密码算法的误解 公开密钥算法比对称密钥密码算法更安全？公开密钥算法比对称密钥密码算法更安全？ 任何一种算法都依赖于密钥长度、破译密码的工任何一种算法都依赖于密钥长度、破译密码的工作量，从抗分析角度，没有一方更优越作量，从抗分析角度，没有一方更优越 公开密钥算法使对称密钥成为过时了的技术？公开密钥算法使对称密钥成为过时了的技术？ 公开密钥很慢，只能用在密钥管理和数字签名，公开密钥很慢，只能用在密钥管理和数
9、字签名，对称密钥密码算法将长期存在对称密钥密码算法将长期存在 使用公开密钥加密，密钥分配变得非常简单？使用公开密钥加密，密钥分配变得非常简单？ 事实上的密钥分配既不简单，也不有效事实上的密钥分配既不简单，也不有效 公钥密钥的应用范围公钥密钥的应用范围加密加密/解密：解密：数字签名数字签名(身份鉴别身份鉴别)密钥交换密钥交换公钥密钥遭受穷举攻击，密码越长越好；但为了加解密，公钥密钥遭受穷举攻击，密码越长越好；但为了加解密，密钥又要足够短；因此公钥密码仅限于密钥管理和签名中密钥又要足够短；因此公钥密码仅限于密钥管理和签名中算法算法加加/解密解密 数字签名数字签名密钥交换密钥交换RSA是是是是是是D
10、iffie-Hellman否否否否是是DSS否否是是否否9.1.3 公钥密码的要求公钥密码的要求 涉及到各方：发送方、接收方、攻击者涉及到各方：发送方、接收方、攻击者 涉及到数据：公钥、私钥、明文、密文涉及到数据：公钥、私钥、明文、密文 公钥算法的条件：公钥算法的条件： 产生一对密钥是产生一对密钥是计算可行的计算可行的 已知公钥和明文，产生密文是已知公钥和明文，产生密文是计算可行的计算可行的 接收方利用私钥来解密密文是计算可行的接收方利用私钥来解密密文是计算可行的 对于攻击者，利用公钥来推断私钥是对于攻击者，利用公钥来推断私钥是计算不可行的计算不可行的 已知公钥和密文，恢复明文是已知公钥和密文
11、，恢复明文是计算不可行的计算不可行的 (可选可选)加密和解密的顺序可交换加密和解密的顺序可交换 满足下列条件的函数满足下列条件的函数f f： (1) 给定给定x，计算，计算y=f(x)是容易的是容易的 (2) 给定给定y, 计算计算x使使y=f(x)是困难的是困难的 (3) 存在存在z，已知，已知z 时时, 对给定的任何对给定的任何y，若相应的，若相应的x存存 在，则计算在，则计算x使使y=f(x)是容易的是容易的所谓计算所谓计算x= x= f-1(Y)(Y)困难是指计算上相当复杂，已无困难是指计算上相当复杂，已无实际意义实际意义满足上述条件找到单向陷门函数函数满足上述条件找到单向陷门函数函数
12、寻找合适的单向陷门函数是公钥密码体制应用的关键单向陷门函数说明单向陷门函数说明仅满足仅满足(1)、(2)两条的称为单向函数；第两条的称为单向函数；第(3)条称为陷门性，条称为陷门性，z 称为陷门信息称为陷门信息当用陷门函数当用陷门函数f作为加密函数时，可将作为加密函数时，可将f公开，这相当于公开公开，这相当于公开加密密钥，此时加密密钥便称为公开钥，记为加密密钥，此时加密密钥便称为公开钥，记为Pkf函数的设计者将函数的设计者将z保密，用作解密密钥，此时保密，用作解密密钥，此时z称为秘密钥匙，称为秘密钥匙，记为记为Sk。由于设计者拥有。由于设计者拥有Sk，他自然可以解出，他自然可以解出x=f-1(
13、y)单向陷门函数的第单向陷门函数的第(2)条性质表明窃听者由截获的密文条性质表明窃听者由截获的密文y=f(x)推测推测x是不可行的是不可行的人物介绍人物介绍1976年，年，美国斯坦福大学教授赫尔曼美国斯坦福大学教授赫尔曼(E.Hellman)和他的研究和他的研究助理助理迪菲迪菲(W.Diffie)，以及博士生，以及博士生默克勒默克勒(R.C.Merkle)（简称（简称为为DHM）首先创立并发表了所谓的）首先创立并发表了所谓的“公钥密码体制公钥密码体制”（public key cryptography），即加密、解密用两个不同的钥，），即加密、解密用两个不同的钥，加密用公钥（加密用公钥（publ
14、ic key），即可以公开，不必保密，任何人），即可以公开，不必保密，任何人都可以用；解密用私钥（都可以用；解密用私钥（private key），此钥必须严加管理，），此钥必须严加管理，不能泄漏。更为称绝的是，他们还发明了所谓的数字签名不能泄漏。更为称绝的是，他们还发明了所谓的数字签名（digital signatures）技术，即用私钥签名，再用公钥验证。）技术，即用私钥签名，再用公钥验证。当然，当然，DHM只是提出了一种关于公钥密码体制与数字签名的只是提出了一种关于公钥密码体制与数字签名的思想，而没有真正实现。不过，他们确实是实现了一种体现思想，而没有真正实现。不过，他们确实是实现了一种体
15、现公钥密码体制思想、基于离散对数问题的、在不安全的通道公钥密码体制思想、基于离散对数问题的、在不安全的通道上进行上进行密钥形成与交换的新技术。密钥形成与交换的新技术。公开密钥算法公开密钥算法公钥算法的种类很多，具有代表性的三种密码：公钥算法的种类很多，具有代表性的三种密码： 基于整数分解难题（基于整数分解难题（IFPIFP）的算法体制）的算法体制 基于离散对数难题（基于离散对数难题（DLPDLP）算法体制）算法体制基于椭圆曲线离散对数难题（基于椭圆曲线离散对数难题（ECDLPECDLP）的算法体制）的算法体制 经典例子经典例子 RSA算法算法 Diffie-Hellman密钥交换算法密钥交换算
16、法 椭圆曲线密码算法椭圆曲线密码算法ECC9.2 RSA算法算法 由由MIT的的 Rivest, Shamir & Adleman 在在 1977 提出提出 最著名的且被广泛应用的公钥加密体制最著名的且被广泛应用的公钥加密体制 明文、密文是明文、密文是0到到n-1之间的整数，通常之间的整数，通常n的大的大小为小为1024位或位或309位十进制数位十进制数2022-1-2024RSA1977由由MIT的的Rivest, Shamir 和和 Adleman发明发明已知的且被广泛使用的公钥密码方案已知的且被广泛使用的公钥密码方案有限域中的乘方运算有限域中的乘方运算乘方运算需要乘方运算需要 O(log
17、 n)3) 操作操作 (容易的容易的) 使用一些大的整数使用一些大的整数 (例如例如. 1024 bits)安全性基于大数的素因子分解的困难性安全性基于大数的素因子分解的困难性素因子分解需要素因子分解需要 O(e log n log log n) 操作操作 (困难的困难的) 2022-1-20252022-1-20西安电子科技大学计算机学院26 费马小定理费马小定理：若：若 p 是素数，是素数，a 是正整数且不能被是正整数且不能被 p 整除，则：整除，则： ap-1 = 1(mod p)。或者另一种形式：。或者另一种形式：ap=a(mod p)，这种形式不要求，这种形式不要求 a 与与 p 互
18、素。互素。 欧拉定理欧拉定理：对任意互素的：对任意互素的 a 和和 n，有，有 a(n) = 1(mod n)。其中，。其中，(n)是欧拉函数，即小于是欧拉函数，即小于 n 且与且与 n 互素互素的正整数的个数。的正整数的个数。 大整数分解问题大整数分解问题：将两个整数乘起来是简单的，但：将两个整数乘起来是简单的，但是将一个整数分解为几个整数的乘积是困难的，尤是将一个整数分解为几个整数的乘积是困难的，尤其是当这个数比较大的时候。迄今为止没有有效的其是当这个数比较大的时候。迄今为止没有有效的算法来解决这个问题，甚至我们连这个问题的计算算法来解决这个问题，甚至我们连这个问题的计算复杂度量级是多少都
19、不知道。复杂度量级是多少都不知道。Euler 函数函数 所有模所有模m和和r同余的整数组成剩余类同余的整数组成剩余类r 剩余类剩余类r中的每一个数和中的每一个数和m互素的充要条件是互素的充要条件是r和和m互素互素 和和m互素的同余类数目用互素的同余类数目用(m)表示，称表示，称m的的Euler函数函数 当当m是素数时，小于是素数时，小于m的所有整数均与的所有整数均与m互素，因此互素，因此(m)=m-1对对n=pq, p和和q 是素数，是素数，(n)=(p)(q)=(p-1)(q-1)若（若（a, n）=1, 则则 a (n)= 1 mod n若若a, n不互素不互素, 则则 a (n)+1=
20、a mod nRSA算法的实现算法的实现 实现的步骤如下：实现的步骤如下：Bob为实现者为实现者 (1) Bob寻找出两个大素数寻找出两个大素数p和和q (2) Bob计算出计算出n=pq 和和(n)=(p-1)(q-1) (3) Bob选择一个随机数选择一个随机数e (0e (n)，满足，满足(e,(n)=1 (4) Bob使用辗转相除法计算使用辗转相除法计算d=e-1(mod(n)，即，即ed 1(mod(p-1)(q-1) (5) Bob在目录中（在目录中（e,n)作为公钥作为公钥. （6）(d,n)或者或者d作为私钥作为私钥.密码分析者攻击密码分析者攻击RSA体制的关键点在于如何分解体
21、制的关键点在于如何分解n。若分。若分解成功使解成功使n=pq，则可以算出，则可以算出(n)（p-1)(q-1)，然后由公，然后由公开的开的e，解出秘密的，解出秘密的dRSA算法编制算法编制 参数参数T=NT=N；私钥私钥SK=DSK=D；公钥公钥PK=EPK=E； 设：明文设：明文M M，密文，密文C C，那么：，那么： 用公钥作业：用公钥作业：M ME E mod N = C mod N = C 用私钥作业：用私钥作业：C CD D mod N = M mod N = MRSA Example1.Select primes: p=17 & q=112.Compute n = pq =1711
22、=1873.Compute (n)=(p1)(q-1)=1610=1604.Select e : gcd(e,160)=1; choose e=75.Determine d: de=1 mod 160 and d 160 Value is d=23 since 237=161= 1160+16.Publish public key KU=7,1877.Keep secret private key KR=23,187RSA Example cont sample RSA encryption/decryption is: given message M = 88 (nb. 88187) enc
23、ryption:C = 887 mod 187 = 11 decryption:M = 1123 mod 187 = 88 加密算法：加密算法：假设 M 是明文（Mn），那么密文就是 C = Memod n。解密算法：解密算法：假设 C 是密文，那么明文就是 M = Cd mod n。证明：（1）由于 Cd = Me*d = Mk*(n)+1 (mod n)= Mk*(n)+1 。如果 M 和 n 是互素的，显然直接由欧拉定理我们就能得到：Cd = Mk*(n)*M1 = M (mod n) = M。ed 1(mod(p-1)(q-1)2）如果 M 和 n 不互素，由于 n 是两个素数 p 和
24、 q 的乘积且 Mn，e*d = 1(mod (n) = 1(mod (p-1)(q-1) ，可以得到：Me*d = Mk*(p-1)*(q-1)+1 = Mk*(n)+k-(k-1) = Mk*(n)+1)-(k-1)(mod p)= Mk*(n)+1)-(k-1) = Mk-(k-1) = M(mod p)若（若（a, n）=1, 则则 a (n)= 1 mod n若若a, n不互素不互素, 则则 a (n)+1= a mod n2）证明方法二如果 M 和 n 不互素，由于 n 是两个素数 p 和 q 的乘积且 Mn，e*d = 1(mod (n) = 1(mod (p-1)(q-1) ，
25、可以得到：e*d = 1(mod (p-1) 且 e*d = 1(mod (q-1)。则 e*d 可以写成： e*d = k*(p-1)+1, e*d = h*(q-1)+1由费马小定理：Me*d = Mk*(p-1)+1 = M(mod p) 和 Me*d = Mh*(q-1)+1 = M(mod q)。所以我们有：Cd = Me*d = M (mod p*q) = M (mod n) = M2022-1-20西安电子科技大学计算机学院369.2.2幂幂 运运 算算可以用平方和乘法运算可以用平方和乘法运算N 次方，只需要次方，只需要 O(log2 n) 次乘法运算次乘法运算如如. 75 =
26、74.71 = 3.7 = 10 mod 11如如. 3129 = 3128.31 = 5.3 = 4 mod 11 反复平方乘反复平方乘例如：例如：5*20=95，367，431，640，625=25 mod35；原理：如原理：如20=10100（0，1，10，101，1010，10100）=（0，1，2，5，10，20）1=0*2+1；2=1*2；5=2*2+1；10=5*2；20=10*2；10 2121 2252 212105 222010 225(5 )55mod355(5)525mod355(5 )5255 3125 10mod355(5 )10100 30mod355(5 )30
27、900 25mod35 2022-1-2039加密的效率加密的效率加密要计算加密要计算 e 次方幂次方幂若若 e 较小较小, 计算将很快计算将很快通常选择通常选择 e = 65537 (216-1) EDI国际标准国际标准或选择或选择 e = 3 或或 e = 17但若但若 e太小太小 (如如 e = 3)将易受到攻击将易受到攻击用中国剩余定理用中国剩余定理必须确保必须确保(e, (n) = 1为了提高加密速度，通常取为了提高加密速度，通常取e为特定的小整数为特定的小整数2022-1-2040解密的效率解密的效率解密计算解密计算d次方幂次方幂看起来很大，否则不安全看起来很大，否则不安全用中国剩
28、余定理分别计算用中国剩余定理分别计算mod p和和mod q，则，则可以得到所希望的答案可以得到所希望的答案比直接快约比直接快约4倍倍只有知道只有知道p和和q及私钥的接收者可以直接采用及私钥的接收者可以直接采用这个技术进行计算这个技术进行计算参数参数e和和d选择选择 但是但是e也不能太小，以也不能太小，以e=3为例说明：为例说明： 假设假设A实体给三个实体发送同样的消息实体给三个实体发送同样的消息m,三个实体三个实体的模数分别为的模数分别为n1,n2,n3,那么那么A将发送将发送ci=m3modni,i=1,2,3. 由于这些模数完全有可能两两互素，攻击者在观察由于这些模数完全有可能两两互素，
29、攻击者在观察到到c1,c2,c3后，可使用下列同余式：后，可使用下列同余式：x=c1modn1；x=c2modn2；x=c3modn3。 x n1n2n3,由于由于m3 n1n2n3,可以通过中国剩可以通过中国剩余定理求得余定理求得x=m m3 3,再计算再计算x的三次方根，的三次方根，攻击者就能恢复明文攻击者就能恢复明文m。 因此公钥因此公钥e不能太小不能太小。 同理，对于参数同理，对于参数d的选择。如果减少的选择。如果减少d的长的长度，可以提升加密与解密的效率，但是，如果度，可以提升加密与解密的效率，但是，如果d的长度太小，的长度太小，RSA系统安全性性会受到破坏。系统安全性性会受到破坏。
30、例如，一种典型的情况是，若例如，一种典型的情况是，若gcd(p-1,q-1)很小很小时，则存在有效的算法可由公开信息（时，则存在有效的算法可由公开信息（n,e）计）计算出算出d。其次可利用。其次可利用C=memodn，直接猜出，直接猜出d，其过程为：求出其过程为：求出cdmodn=m，若成立，则，若成立，则d为为正确，否则继续猜测正确，否则继续猜测d，由于，由于d长度很小，则猜长度很小，则猜测测d的空间变小，猜对的概率相对较大。的空间变小，猜对的概率相对较大。 因此，因此，d的长度不能太小的长度不能太小。RSA 的安全性的安全性 穷举攻击穷举攻击:尝试所有可能的密钥。因此，尝试所有可能的密钥。
31、因此，e 和和d 的位数越大的位数越大，算法就越安全。然而，在密钥产生和加密解密中使用的计，算法就越安全。然而，在密钥产生和加密解密中使用的计算都非常复杂，所以密钥越大，系统运行越慢。算都非常复杂，所以密钥越大，系统运行越慢。 数学攻击数学攻击：试图分解两个素数的乘积试图分解两个素数的乘积 计时攻击计时攻击：依赖于解密算法的运行时间，利用依赖于解密算法的运行时间，利用CPU处理某处理某些特殊的模乘比较慢的规律来确定每一位指数些特殊的模乘比较慢的规律来确定每一位指数 选择密文攻击选择密文攻击：利用利用RSA算法的性质算法的性质 RSA的安全性是基于大整数素因子分解的困难性，的安全性是基于大整数素
32、因子分解的困难性，RSA 的安全性的安全性：分解因子问题分解因子问题数学方法攻击数学方法攻击RSA三种途径三种途径（1）分解成功使）分解成功使n=pq，则可以算出，则可以算出(n)（p-1)(q-1)，然后由，然后由公开的公开的e，解出秘密的，解出秘密的d（一般采用第一种一般采用第一种）（2）直接确定）直接确定(n)而不先确定而不先确定p和和q，这样就可以确定，这样就可以确定（3）直接确定）直接确定d，而不先确定，而不先确定1(mod ( )den()n2022-1-2045分解因子问题分解因子问题对于因子分解问题对于因子分解问题很多年来进展很慢很多年来进展很慢用用“Lattice Sieve
33、” (LS),算法，算法，最好的是分解了最好的是分解了200位十进制数位十进制数(663 bit) 最大的改进就是对改进算法的改良最大的改进就是对改进算法的改良 QS to GHFS to LS当前假设当前假设1024-2048bit RSA 是安全的是安全的确保确保 p, q 有相似的大小并满足其它约束有相似的大小并满足其它约束 每个合数都可以唯一地分解出素数因子每个合数都可以唯一地分解出素数因子6 = 2 3999999 = 333711133727641 = 131121从从2 开始试验每一个小于等于开始试验每一个小于等于27641 的素数。的素数。素数：只能被素数：只能被1和它本身整除
34、的自然数；否则为合数。和它本身整除的自然数；否则为合数。整数整数n的十进制位数的十进制位数 因子分解的运算次数因子分解的运算次数 所需计算时间（每微秒一次）所需计算时间（每微秒一次）501.4x10103.9小时小时759.0 x1012104天天1002.3x101574年年2001.2x10233.8x109年年3001.5x10294.0 x1015年年5001.3x10394.2x1025年年建议选择建议选择p和和q大约是大约是100位的十进制素数位的十进制素数模模n的长度要求至少是的长度要求至少是512比特，比特，EDI攻击标准使用的攻击标准使用的RSA算法中规定算法中规定n的长度为
35、的长度为512至至1024比特位之间，但必须是比特位之间，但必须是128的倍数的倍数国际数字签名标准国际数字签名标准ISO/IEC 9796中规定中规定n的长度位的长度位512比比特位特位 为了抵抗现有的整数分解算法，对为了抵抗现有的整数分解算法，对RSA模模n的素因子的素因子p和和q还有如下要求：还有如下要求： (1) |p-q|很大，通常很大，通常 p和和q的长度相同；的长度相同； (2) p-1 和和q-1分别含有大素因子分别含有大素因子p1和和q1 (3) P1-1和和q1-1分别含有大素因子分别含有大素因子p2和和q2 (4) p+1和和q+1分别含有大素因子分别含有大素因子p3和和
36、q32022-1-2049计计 时时 攻攻 击击20世纪世纪90年代由年代由Paul Kocher提出提出探测操作中的时间变化探测操作中的时间变化eg. multiplying by small vs large number or IFs varying which instructions executed基于所耗时间的大小，对操作数的大小进行猜测基于所耗时间的大小，对操作数的大小进行猜测RSA exploits time taken in exponentiationCountermeasures(解决办法解决办法)use constant exponentiation time（不变的
37、（不变的 幂运算时间）幂运算时间）add random delays（随机时延）（随机时延）blind values used in calculations（隐蔽）（隐蔽）2022-1-2050选择密文攻击选择密文攻击RSA 对于选择密文来说是易受攻击的对于选择密文来说是易受攻击的攻击者选择密文并得到相应明文攻击者选择密文并得到相应明文选择密文可给密码分析者探测选择密文可给密码分析者探测RSA的特性提供信息的特性提供信息optimal asymmetric encryption padding (OAEP).RSA的速度的速度由于进行的都是大数计算，使得RSA最快的情况也比DES慢上100倍
38、，无论是软件还是硬件实现。速度一直是RSA的缺陷。一般来说只用于少量数据加密。RSA的缺点的缺点A)产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。B)分组长度太大。C)为保证安全性，n 至少也要 600 bits以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。D)目前，SET(Secure Electronic Transaction)协议中要求CA采用2048比特长的密钥，其他实体使用1024比特的密钥。RSA算法应用算法应用 RSA为公用网络上信息的加密和鉴别提供了一种基本的方法。 它通常
39、是先生成一对RSA 密钥，其中之一是保密密钥，由用户保存；另一个为公开密钥，可对外公开，甚至可在网络服务器中注册，人们用公钥加密文件发送给个人，个人就可以用私钥解密接受。为提高保密强度，RSA密钥至少为500位长，一般推荐使用1024位。 RSA系统是公钥系统的最具有典型意义的方法，大多数使用公钥密码进行加密和数字签名的产品和标准使用的都是RSA算法 单钥密码加密速度快,人们用它来加密较长的文件,然后用RSA来给文件密钥加密,极好的解决了单钥密码的密钥分发问题。 人物说明 Euler Leonhard (1707-1783) 欧拉，莱奥哈尔德：欧拉，莱奥哈尔德：(1707-1783) 瑞士数学
40、家，尤其他对瑞士数学家，尤其他对微积分的开创性贡献，以及他的复数、对数、三角函数和微积分的开创性贡献，以及他的复数、对数、三角函数和月球运动等理论而闻名于世月球运动等理论而闻名于世物理学家物理学家. Fer.mat Pierre de (1601-1665) 费马，皮尔费马，皮尔德：德：(1601-1665) 法国数学家，他有系统地阐法国数学家，他有系统地阐述了现代数理论和概率论述了现代数理论和概率论. Euclid欧几里得欧几里得(约公元前约公元前3世纪的古希腊数学家世纪的古希腊数学家) 他把逻辑学中他把逻辑学中的演绎原理应用到几何学中，籍以由定义明确的公理导出的演绎原理应用到几何学中，籍以
41、由定义明确的公理导出语句语句.DES密钥长度密钥长度(bit)RSA密钥长度密钥长度(bit)56 38464 512 1121792 1282304DES和和RSA性能比较性能比较(同等强度）同等强度） 公开密钥密码总结公开密钥密码总结l公钥算法加密解密速度慢公钥算法加密解密速度慢l误区误区:公开密钥密码算法更安全公开密钥密码算法更安全 公开密钥密码使对称密钥密码过时了公开密钥密码使对称密钥密码过时了 公钥的分发是简单和一目了然的公钥的分发是简单和一目了然的。公开密码的应用公开密码的应用 秘密性秘密性 因为公钥密码不需要共享密钥。因为公钥密码不需要共享密钥。 任何和都可以使用对方公钥，所以不
42、能确定任何和都可以使用对方公钥，所以不能确定alice的真正身的真正身份。无法实现抗抵赖的需求份。无法实现抗抵赖的需求2.数字签名和不可否认数字签名和不可否认 用私钥对数据加密，不可否认。用私钥对数据加密，不可否认。3.秘密性和不可否认秘密性和不可否认 通信双方是通信双方是Alice Bob。 MaliceBob 先签名再加密先签名再加密 MBobAlice先加密再签名先加密再签名 CA:使用使用Alice私钥解密私钥解密 MA:使用使用Alice的公钥加密消息的公钥加密消息 思考：思考：“宝藏在宝藏在*”先签名再加密先签名再加密&先加密再先加密再签名的区别？签名的区别？ 用用RSA给别人发送
43、一则信息，首先要用私钥加给别人发送一则信息，首先要用私钥加密签名，然后再用对方的公钥加密信息和签名密签名，然后再用对方的公钥加密信息和签名，把消息发送给对方。，把消息发送给对方。 如果先加密后签名，那如果先加密后签名，那么签名在传播途中被人为地篡改，我们可以做么签名在传播途中被人为地篡改，我们可以做个形象的比喻，本来鲍勃要发送给对方一则信个形象的比喻，本来鲍勃要发送给对方一则信息给艾丽丝，可是途中却被伊芙拦截，把签名息给艾丽丝，可是途中却被伊芙拦截，把签名稍加修改就成了自己发出去的一则信息了，那稍加修改就成了自己发出去的一则信息了，那么鲍勃就不知道这是谁发出的信息了。么鲍勃就不知道这是谁发出的信息了。
