计算机系统与网络安全技术（第2版）-课件 1-5-7 公钥密码学基础（RSA算法存在的安全威胁）

第一章信息安全概述-RSA算法存在的安全威胁计算机系统与网络安全技术RSA的安全性是基于加密函数ek(x)=xe(modn)是一个单向函数，所以对攻击的人来说求逆计算不可行。而Bob能解密的陷门是分解n=pq，知

(n)=(p-1)(q-1)，从而用欧几里德算法解出解密私钥d。RSA算法的安全性RSA算法存在的安全威胁信息安全概述

每个合数都可以唯一地分解出素数因子

6=2·3 999999=3·3·3·7·11·13·37 27641=131·121

从2开始试验每一个小于等于√27641的素数。素数：只能被1和它本身整除的自然数；否则为合数。整数n的十进制位数因子分解的运算次数所需计算时间（每微秒一次）

50 1.4x1010 3.9小时 75 9.0x1012 104天 100 2.3x1015 74年

200 1.2x1023 3.8x109年 300 1.5x1029 4.0x1015年

500 1.3x1039 4.2x1025年因子分解的难度和时间RSA算法存在的安全威胁信息安全概述对RSA的具体实现存在一些攻击方法，但不是针对基本算法的，而是针对协议的。对RSA的选择密文攻击对RSA的公共模攻击对RSA的小加密指数攻击对RSA的小解密指数攻击时间性攻击：取决于解密算法的运算时间针对RSA的攻击RSA算法存在的安全威胁信息安全概述例1：E监听A的通信，收集由A的公开密钥加密的密文c，E想知道消息的明文m,使

m=cdmodn他首先选择随机数r,使r<n.然后用A的公开密钥e计算：

x=remodny=xcmodnt=r-1modn如果x=remodn，则

r=xdmodn现在E让A对y签名，即解密y,A向E发送u=ydmodn而E计算

tumodn=r-1yd

modn=r-1xdcdmodn=cdmodn=m针对RSA的选择密文攻击RSA算法存在的安全威胁信息安全概述例2：E让A对m3签名。他产生两个消息m1和m2，满足

m3=m1m2(modn)如果E能让A分别对m1和m2签名，则可以计算m3：

m3d=(m1dmodn)(m2dmodn)启示：不要用RSA对陌生人的随机文件签名，签名前先使用一个散列函数针对RSA的选择密文攻击RSA算法存在的安全威胁信息安全概述一种可能的RSA实现方法是给每个人相同的n,但指数d和e不同。问题：如果相同的消息曾用两个不同的指数加密，而这两个指数是互素的，则明文可以不需要任何解密密钥来恢复。令m为明文消息，两个加密密钥为e1，e2,两个密文消息为c1,c2c1=me1modnc2=me2modn由于e1和e2互素，所以可以用扩展的Euclid算法找到r,s使re1+se2=1,同样，可以用扩展的Euclid算法计算c1-1,而(c1-1)-r*c2s=mmodn启示：不要让一群用户共享一个模n针对RSA的公共模攻击RSA算法存在的安全威胁信息安全概述

对RSA的小加密指数攻击如果使用一个较小的e值，则进行RSA签名和加密会很快，但也不安全。如果用相同e值的不同公钥，可以得到e(e+1)/2个线性相关的消息，则系统是可破的；如果有少于这些的消息或消息不相关，则无问题。比如：消息为mj,使用同样的指数e,模数分别为q1,q2,…qs（两两互素）,则密文为mjemodq1，mjemodq2，…mjemodqs，根据中国剩余定理，m'=mjemodq1q2…qs.可以计算出来，对于较小的e，可以解出mj。解决办法：加密前将消息与随机值混合，并保证m与n有相同的长度。RSA算法存在的安全威胁信息安全概述使用较小的d会产生穷尽解密攻击的可能当d为n的1/4长度时，而e小于n时，可