北京交通大学密码学第90章公钥密码1.ppt

《北京交通大学密码学第90章公钥密码1.ppt》由会员分享，可在线阅读，更多相关《北京交通大学密码学第90章公钥密码1.ppt（62页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第9-10章 公钥密码,本章内容,公钥密码体制的基本原理 数论基础 RSA算法 Diffie-Hellman密钥交换算法 ElGamal密码体制 椭圆曲线密码体制ECC,公钥密码体制的基本原理,公钥密码体制的提出和起源 公钥密码的特点 公钥密码的应用 公钥密码的要求 公钥密码的理论基础,公钥密码体制的基本原理,公钥密码以前：所有的密码算法都是基于代换和置换这两个基本工具。 而公钥密码体制为密码学的发展提供了新的理论和技术基础 基本工具是数学函数 公钥密码算法是以非对称的形式使用两个密钥，两个密钥的使用对保密性、密钥分配、认证等都有着深刻的意义。 可以说公钥密码体制的出现在密码学史上是一个最大的

2、而且是惟一真正的革命。,问题的提出,公钥密码体制的概念是在解决单钥密码体制中最难解决的两个问题时提出的，这两个问题是密钥分配和数字签字。 密钥分配问题 通信双方要进行加密通信，需要通过秘密的安全信道协商加密密钥，而这种安全信道可能很难实现； 密钥管理问题 ：两两分别用一对密钥时，则n个用户需要C(n,2)=n(n-1)/2个密钥，当用户量增大时，密钥空间急剧增大。如: n=100 时， C(100,2)=4,995 n=5000时， C(5000,2)=12,497,500 没有签名功能：当主体A收到主体B的电子文挡（电子数据）时，无法向第三方证明此电子文档确实来源于B，无法实现抗抵赖的需求。

3、,起源,公钥密码又称为双钥密码和非对称密码，是1976年由Stanford大学的Diffie和Hellman在其“密码学新方向” 一文中提出的，见划时代的文献： W.Diffie and M.E.Hellman, New Directrions in Cryptography, IEEE Transaction on Information Theory, V.IT-22.No.6, Nov 1976, PP.644-654 RSA公钥算法是由Rivest,Shamir和Adleman在1978年提出来的, 见：Communitions of the ACM. Vol.21.No.2. Feb

4、. 1978, PP.120-126.,公钥密码的重要特性,加密与解密由不同的密钥完成 加密: XY: Y = EKU(X) 解密: YX: X = DKR(Y) = DKR(EKU(X) 知道加密算法,从加密密钥得到解密密钥在计算上是不可行的 两个密钥中任何一个都可以用作加密而另一个用作解密 (不是必须的) X = DKR(EKU(X) = EKU(DKR(X),基于公开密码的加密过程,用户拥有自己的密钥对(KU,KR)，公钥KU公开,私钥KR保密 Bob Alice: Y=EKUa(X) Alice: DKRb(Y)= DKRa(EKUa(X)=X,基于公开密码的鉴别过程,条件: 两个密钥

5、中任何一个都可以用作加密而另一个用作解密 鉴别: AilceALL: Y=EKRa(X) ALL: EKUa(Y)=DKUa(EKRa(X)=X,基于公开密码的鉴别过程,在实际应用中，特别是用户数目很多时，以上认证方法需要很大的存储空间，因为每个文件都必须以明文形式存储以方便实际使用，同时还必须存储每个文件被加密后的密文形式即数字签字，以便在有争议时用来认证文件的来源和内容。 改进的方法是减小文件的数字签字的大小，即先将文件经过一个函数压缩成长度较小的比特串，得到的比特串称为认证码。 认证码具有这样一个性质：如果保持认证码的值不变而修改文件这在计算上是不可行的。 用发送者的秘密钥对认证码加密，

6、加密后的结果为原文件的数字签字。,基于公开密码的鉴别+保密过程,鉴别+保密: A B: Z= EKUb(EKRa(X) B: DKUa(DKRb(Z)=X,公钥密码的应用范围,加密/解密（保密性） 数字签名(身份鉴别) 密钥交换（会话密钥）,基本思想和要求,涉及到各方：发送方、接收方、攻击者 涉及到数据：公钥、私钥、明文、密文 公钥算法的条件： 产生一对密钥是计算可行的 已知公钥和明文，产生密文是计算可行的 接收方利用私钥来解密密文是计算可行的 对于攻击者，利用公钥来推断私钥是计算不可行的 已知公钥和密文，恢复明文是计算不可行的 (可选)加密和解密的顺序可交换 其中最后一条虽然非常有用，但不是

7、对所有的算法都作要求。,公钥密码的理论基础,难解问题：没有有效算法，求解所需时间非常长。 易解问题：存在有效算法，求解所需时间短 一般来说计算一个难解的问题所需要的时间通常是所输入数据长度的一个指数函数，因此计算时间是随着数据长度的增加急剧增加的。,陷门单向函数,公钥密码是建立在陷门单向函数上的。 单向函数（one way function）： (1)给定x，计算y=fk(x)是容易的； (2)给定y, 计算x使y=fk-1(x)是不可行的。 陷门单向函数（trapdoor one way function）: (1)给定x，计算y=fk(x)是容易的； (2)给定y, 计算x使y=fk-1(

8、x)是不可行的。 (3)存在k，已知k 时,对给定的任何y，若相应的x存在，则计算x使y=fk-1(x)是容易的。 研究公钥密码算法就是要找出合适的陷门单向函数。,公钥密码体制的安全性,像对称密码体制一样，密钥穷搜索攻击理论上是有效的； 但是使用的密钥太大 (512bits) 安全性依赖于难解问题； 一般难解问题是已知的，但是需要设计的足够难； 需要使用很大的数； 因此比对称密码算法要慢；,数论基础,1、素数 2、模运算 3、Euclid算法 4、费马定理和欧拉定理 5、素性测试 6、中国剩余定理 7、离散对数 见：第8章 数论入门.ppt,经典例子,RSA算法 Diffe-Hellman密钥

9、交换算法 ElGamal密码体制 椭圆曲线密码体制ECC,RSA公开密钥算法,RSA算法描述 RSA的实现问题 RSA的安全性,RSA公开密钥算法,1977年由Ron Rivest、Adi Shamir和Len Adleman发明，1978年公布 是一种分组加密算法 明文和密文在0n-1之间,n是一个正整数 用数论构造 迄今为止理论上最为成熟完善的公钥密码体制 应用最广泛的公钥密码算法 只在美国申请专利，且已于2000年9月到期,RSA公开密钥算法算法描述,算法的论证,RSA算法的论证,加密和解密运算的可交换性 D(E(M)=(Me)d=(Md)e=E(D(M) mod n 所以,RSA密码可

10、同时确保数据的秘密性和真实性 加解密算法的有效性 RSA密码的加解密运算是模幂运算，有比较有效的算法,RSA算法的论证,在计算上由公开密钥不能求出解密钥 小合数的因子分解是容易的，然而大合数的因子分解确是十分困难的。关于大合数的因子分解的时间复杂度下限目前尚没有一般的结果，迄今为止的各种因子分解算法提示人们这一时间下限将不低于O(EXP(lnNlnlnN)1/2)。根据这一结论，只要合数足够大，进行因子分解是相当困难的。,RSA算法的论证,假设截获密文C, 从中求出明文M。他知道 MCd mod n， 因为n是公开的，要从C中求出明文M，必须先求出d，而d是保密的。但知道， ed1 mod (

11、n)， E是公开的，要从中求出d，必须先求出(n)，而(n)是保密的。,RSA算法的论证,在计算上由公开密钥不能求出解密密钥 但知道，(n)=(p-1)(q-1) 要从中求出(n)，必须先求出p和q，而p和q是保密的。 知道 n=pq，要从n求出p和q，只有对n进行因子分解。 而当n足够大时，这是很困难的。 只要能对n进行因子分解，便可攻破RSA密码。由此可以 得出，破译RSA密码的困难性=对n因子分解的困难性。 目前尚不能证明两者是否能确切相等，因为不能确知除了 对n进行因子分解的方法外，是否还有别的更简捷的破译 方法。 目前只有Rabin密码具有： 破译Rabin密码的困难性=对n因子分解

12、的困难性,RSA算法的论证,RSA的安全性是基于加密函数ek(x)=xe(mod n)是一个单向函数，所以对的人来说求逆计算不可行。 而Bob能解密的陷门是分解n=pq，知 (n)=(p-1)(q-1)。从而用扩展的Euclid算法解出解密私钥d。 密码分析者攻击RSA体制的关键点在于如何分解n。若分解成功使n=pq，则可以算出(n)（p-1)(q-1)，然后由公开的e，解出秘密的d。 猜想：攻破RSA与分解n是多项式等价的。然而，这个猜想至今没有给出可信的证明！,两个问题和两个假设,RSA的安全性是基于RSA假设，而不是基于分解大整数的困难性假定,RSA算法举例,RSA密码体制的实现,实现的

13、步骤如下：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) (5) Bob在目录中公开n和e作为她的公开钥。 选好这些参数后，将明文划分成块，使得每个明文报文P长度m满足0mn。 加密P时，计算CPe(mod n)，解密C时计算PCd(mod n)。由于模运算的对称性，可以证明，在确定的范围内，加密和解密函数是互逆的。 为实现加密，需要公开(e, n)，为实现解密需要(d, n)。,RSA的加、解密

14、过程示例,RSA的实现参数选择,为了确保RSA密码的安全，必须认真选择密码参数： p和q要足够大： 一般应用：p和q应512b 重要应用：p和q应1024b p和q应为强素数 文献指出，只要(p-1)、(p+1)、(q-1)、(q+1)四个数之一 只有小的素因子，n就容易分解。 (p-1)和(q-1)的最大公因子要小 如果(p-1)和(q-1)的最大公因子太大，则易受迭代加密 攻击。,RSA的实现参数选择, e的选择 随机且含1多就安全，但加密速度慢。于是，有的学者 建议取e=216+1=65537 d的选择 d不能太小，要足够大 不要许多用户公用一个模n：易受共模攻击,另外两个常用的e的选择

15、是3和17.但是如果e=3。这时加密速度一般比解密速度快10倍以上。但是易受低指数攻击。 注意：密钥产生要求（e, (n)）=1，因此如果用户选择了e=65537，接着生成了素数p，q， 很有可能不能满足（e, (n)）=1，因此用户应该去掉那些模65537和1不同余的p和q。,RSA实现中的问题,（1）如何计算ab mod n 需要计算模 300 digits (or 1024+ bits) 的乘法 （2）如何判定一个给定的整数是素数？ （3）如何找到足够大的素数p和q ?,其中d是中间结果，d的终值即为所求结果。c在这里的作用是表示指数的部分结果，其终值即为指数m，c对计算结果无任何贡献，

16、算法中完全可将之去掉。,快速加解密,加密很快，指数小 解密比较慢，指数较大 利用中国剩余定理CRT，分别计算mod p和mod q，再组合成所需的 结果。可以加快运算速度，比直接计算M=Cd mod n 相比，速度大约快4倍。 CRT 对RSA解密算法生成两个解密方程（利用M=Cd mod n） 即: Vp = M mod p = (C mod p)d mod (p-1) Vq = M mod q = (C mod q)d mod (q-1) 解方程 M = Vp mod p M = Vq mod q 具有唯一解（利用CRT ）： 定义： Xp = q（q1 mod p ） Xq = p（p1

17、 mod q） M =（ Vp Xp + Vq Xq ）mod n 只有知道p和q的私钥的拥有者才能使用这种技术；,如何判定一个给定的整数是素数？,Miller and Rabin, WITNESS算法 WITNESS(a,n) 判定n 是否为素数，a是某些小于n的整数； 首先将n-1表示为二进制形式bkbk-1b0，并给d赋初值1，则算法Witness(a,n)的核心部分如下： for i=k down to 0 do xd; d(dd) mod n; if d=1 and(x1)and(xn-1)then return False; if bi=1 then d(da) mod n if

18、d1 then return False; return True.,返回值： FALSE: n一定不是素数 TRUE: n可能是素数 应用：随机选择a n,计算s次，如果每次都返回TRUE，则这时n是素数的概率为(1 - 1/2s)。,如何找到足够大的素数p和q ?,1. 随机选一个奇数n (如: 可使用伪随机数发生器) 2. 随机选择一个整数a n 3. 执行概率素数判定测试(如:用WITNESS(a,n),如果n 未测试通过,则拒绝数值n, 转向步骤1 4. 如果n已通过足够的测试, 则接受n, 否则转向步骤2; 说明： 随机选取大约用ln(N)/2的次数，如ln(2200)/2=70

19、好在生成密钥对时才用到，慢一点还可忍受。 确定素数p和q以后，只需选取e, 满gcd(e,(n)=1, 计算d = e-1 mod (n) （扩展的Euclid算法）； 两个随机数互素的概率约为0.6；,对RSA的攻击方法,1、强力攻击（穷举法）：尝试所有可能的私有密钥 2、数学分析攻击：各种数学方法，等价与两个素数乘积的 因子分解 3、对RSA实现的攻击,数学分析攻击,用数学方法攻击RSA的途径有一下三种: 分解 n=p.q, 这样可以计算 (n) ，从而可以确定 d； 直接确定 (n)而不先确定p和q， 也可以计算d； 直接确定d，而不先确定 (n)； 目前认为后两种方法与第一种方法是等价

20、的，因此对RSA密码分析的讨论大都集中于：将n分解为两个素数因子： 尽管因子分解具有大素数因子的数n仍然是一个难题，但是已不像以前那么难。 2005.5，已经可以用格筛法分解200 位十进制数（663bit) 对于大整数的威胁除了人类的计算能力外，还来自分解算法的进一步改进。 二次筛法(QS ) 一般数域筛法(GHFS ) 格域筛法( LS) 估计在未来一段比较长的时期，密钥长度介于1024比特至2048比特之间的RSA是安全的。 在使用RSA算法时对其密钥的选取要特别注意其大小,要确保 p, q 相似的长度，并且满足其他的限制；,Progress in Factoring,Progress

21、in Factoring,对RSA的攻击,对RSA的具体实现存在一些攻击方法，但不是针对基本算法的，而是针对协议的。 选择密文攻击： 共模攻击 对RSA的小加密指数攻击 对RSA的小解密指数攻击 计时攻击：取决于解密算法的运算时间,对RSA的选择密文攻击,例1：E监听A的通信，收集 由A的公开密钥加密的密文 c, E想知道消息的明文m,使 m=cd mod n 他首先选择随机数r,使rn。 然后用A的公开密钥e计算 x=re mod n y=xc mod n t=r-1 mod n 如果x=re mod n，则 r=xd mod n,对RSA的选择密文攻击,例2：E让A对m3签名。他产生两个消

22、息m1和m2 满足m3=m1m2(mod n) 如果E能让A分别对m1和m2签名，则可以计算m3 m3d=(m1d mod n)(m2d mod n),为防止这种攻击，可以在加密之前对明文进行随机填充或者使用一种最优非对称加密填充 (OAEP)的程序对明文进行修改。,Optimal Asymmetric Encryption Padding (OAEP),对RSA的共模攻击,一种可能的RSA实现方法是 给每个人相同的n，但指数 d和e不同. 问题:如果相同的消息曾用两个 不同的指数加密，而这两个指数 是互素的， 则明文可以不用任何 一个解密密钥来恢复 令m为明文消息，两个加密密钥 为e1,e2

23、,两个密文消息为c1,c2,注意:不要让一群用户共享一个模 n,对RSA的小加密指数攻击,如果使用一个较小的e值，则进行RSA签名和加密会很快，但也不安全。 如果用相同e值的不同公开密钥加密e(e+1)/2个线性相关的消息，则系统是可破的。如果有少于这些的消息或消息不相关，则无问题。 比如：消息为mj，使用同样的指数e，模数分别为q1,q2,qs(两两互素)，则密文为mje mod q1, mje mod q2， , mje mod qs,根据中国剩余定理，m mod q1 q2 qs. 可以计算出来，对于较小的e，可以解出mj. 解决办法：加密前将消息与随机值混合，并保证m与n有相同的长度,对RSA的小解密指数攻击,使用较小的d会产生穷尽解密攻击的可能 当d为n的1/4长度时，而e小于n时，可以恢复d， 当e,d是随机选择时，这种情况很少发生，当e 很小时不会发生。 注意：应选择一个大的d值,计时攻击,是Paul Kocher 在1996年证明，攻击者可以通过记录解密消息所用的时间来确定私钥。 由前边的模幂算法可知，RSA算法中的模幂运算是通过一位一位来实现的，每次迭代之星一次模乘运算，且弱该位为1，则还需要再执行一次模乘运算。 解决方法： 不变的幂运算时间 随机延时 隐蔽：在执行幂运算之前先将密文乘上一个随机数。,