第6章 公钥密码体制(RSA算法).ppt

《第6章 公钥密码体制(RSA算法).ppt》由会员分享，可在线阅读，更多相关《第6章 公钥密码体制(RSA算法).ppt（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、赵海燕赵海燕赵海燕赵海燕第第6 6章公钥密码体制章公钥密码体制(RSA(RSA算法算法)661 1概述概述问题的提出：问题的提出：密钥管理困难密钥管理困难传统密钥管理两两分别用一对密钥时，则传统密钥管理两两分别用一对密钥时，则n n 个用户个用户需要需要C(n,2)=n(n-1)/2 C(n,2)=n(n-1)/2 个密钥，当用户量增大个密钥，当用户量增大时时密钥空间急剧增大密钥空间急剧增大。如。如:n=100 n=100 时时C(100,2)=4,995C(100,2)=4,995n=5000 n=5000 时时C(5000,2)=12,497,500C(5000,2)=12,497,500

2、陌生人间的保密通信问题陌生人间的保密通信问题 数字签名的问题数字签名的问题传统加密算法无法实现抗抵赖的需求传统加密算法无法实现抗抵赖的需求公钥密码体制公钥密码体制公钥密码又称为双钥密码、非对称密码公钥密码又称为双钥密码、非对称密码公钥密码体制提出的标志性文献：公钥密码体制提出的标志性文献：19761976年，年，DiffieDiffie和和HellmanHellman，密码学的新方向密码学的新方向W.Diffie and M.E.Hellman,New Directions in Cryptography,W.Diffie and M.E.Hellman,New Directions in C

3、ryptography,IEEE Transaction on Information Theory,V.IT-22.No.6,IEEE Transaction on Information Theory,V.IT-22.No.6,Nov 1976,PP.644-654Nov 1976,PP.644-654公钥密码算法公钥密码算法基于数学函数基于数学函数而不是代替和换位操而不是代替和换位操作。作。支持数字签名支持数字签名：用两个密钥中的任何一个加密的：用两个密钥中的任何一个加密的内容，都可以用对应的另一个密钥解密。内容，都可以用对应的另一个密钥解密。对公钥密码体制的要求对公钥密码体制的要求（1

4、 1）参参与与方方B B容容易易通通过过计计算算产产生生一一对对密密钥钥（公公开开密密钥钥K KUbUb和和私有密钥私有密钥K KRbRb）。）。（2 2）在在知知道道公公开开密密钥钥和和待待加加密密报报文文MM的的情情况况下下，对对于于发发送送方方A A，很容易通过，很容易通过公开密钥公开密钥计算产生对应的密文：计算产生对应的密文：C CE EKUbKUb（MM）（3 3）接接收收方方B B使使用用私私有有密密钥钥容容易易通通过过计计算算解解密密所所得得的的密密文文以便恢复原来的报文：以便恢复原来的报文：MMD DKRbKRb（C C）D DKRbKRb（E EKUbKUb（MM）（4 4）

5、敌敌对对方方即即使使知知道道公公开开密密钥钥K KUbUb，要要确确定定私私有有密密钥钥K KRbRb在计算上是不可行的。在计算上是不可行的。（5 5）敌敌对对方方即即使使知知道道公公开开密密钥钥K KUbUb和和密密文文C C，要要想想恢恢复复原来的报文原来的报文MM在计算上也是不可行的。在计算上也是不可行的。（6 6）加加密密和和解解密密函函数数可可以以以以两两个个次次序序中中的的任任何何一一个个来来使用（适用于部分公钥密码体制）使用（适用于部分公钥密码体制）:MMD DKRbKRb(E(EKUbKUb(M)(M)（机密性）（机密性）M=EM=EKUbKUb(D(DKRbKRb(M)(M)

6、（数字签名）（数字签名）对公钥密码体制的要求对公钥密码体制的要求陷门陷门设计公钥密码算法的关键设计公钥密码算法的关键单向单向陷门函数陷门函数满足下列条件的函数满足下列条件的函数f f叫做单向陷门函数：叫做单向陷门函数：(1)给定给定x，计算，计算y=f(x)是容易的是容易的(2)给定给定y,计算计算x使使y=f(x)是不可行的是不可行的(3)存在存在，已知，已知 时时,对给定的任何对给定的任何y，若相应的，若相应的x存在，则计算存在，则计算x使使y=f(x)是容易的是容易的设计公钥密码算法的关键设计公钥密码算法的关键单向单向陷门函数陷门函数单向函数单向函数陷门性陷门性陷门信息陷门信息 （1 1

7、）当用陷门函数）当用陷门函数f f作为加密函数时，可将作为加密函数时，可将f f公开，公开，这相当于公开加密密钥。此时加密密钥便称为公开密这相当于公开加密密钥。此时加密密钥便称为公开密钥，记为钥，记为PkPk。（2 2）f f函数的设计者将函数的设计者将保密，用作解密密钥，此时保密，用作解密密钥，此时称为秘密密钥，记为称为秘密密钥，记为SkSk。（3 3）由于加密函数是公开的，任何人都可以将信息）由于加密函数是公开的，任何人都可以将信息x x加密成加密成y=f(x)y=f(x)，然后送给函数的设计者（当然可以通，然后送给函数的设计者（当然可以通过不安全信道传送）；由于设计者拥有过不安全信道传送

8、）；由于设计者拥有SkSk，他自然可，他自然可以解出以解出x=fx=f-1-1(y)(y)。（4 4）窃听者由于没有）窃听者由于没有SkSk，则他由截获的密文，则他由截获的密文y=f(x)y=f(x)推测推测x x是不可行的。是不可行的。设计公钥密码算法的关键设计公钥密码算法的关键单向单向陷门函数陷门函数公开密钥密码系统的分析方法公开密钥密码系统的分析方法蛮力攻击蛮力攻击(对密钥对密钥)防范措施：采用长密钥防范措施：采用长密钥公开密钥算法本身可能被攻破公开密钥算法本身可能被攻破 找到从公钥计算私钥的方法找到从公钥计算私钥的方法可能报文攻击可能报文攻击(对报文本身的强行攻击对报文本身的强行攻击)

9、搜索报文本身的所有可能，跟密文匹配搜索报文本身的所有可能，跟密文匹配同等加密强度下同等加密强度下DES和和RSA密钥密钥长度的比较长度的比较公钥密码系统的应用公钥密码系统的应用加密加密/解密解密数字签名（第数字签名（第9 9章）章）密钥密钥交换（第交换（第7 7章）章）并不是所有的公开密钥密码体制都支持加密解密、并不是所有的公开密钥密码体制都支持加密解密、数字签名和密钥交换。数字签名和密钥交换。如如RSARSA、ECCECC三种都支持；三种都支持；DSADSA只用于数字签名；只用于数字签名；DHDH只用于密钥交换。只用于密钥交换。混合密码系统混合密码系统加密加密用对称密码加密明文，用对称密码加

10、密明文，发挥速度优势发挥速度优势用非对称密码加密密钥，用非对称密码加密密钥，发挥密钥分发管理优势发挥密钥分发管理优势混合密码系统混合密码系统解密解密用非对称密码用非对称密码解密密钥解密密钥用对称密码用对称密码解密密文解密密文662 2RSARSA 由由RivestRivest，ShamirShamir和和AdlemanAdleman在在19781978年提出，是目年提出，是目前唯一被广泛接受并实现的通用公开密钥密码算法。前唯一被广泛接受并实现的通用公开密钥密码算法。其数学基础是其数学基础是EulerEuler定理，并建立在大整数因子分定理，并建立在大整数因子分解困难问题之上。解困难问题之上。陷

11、门陷门RSARSA密码体制描述密码体制描述明文空间明文空间P P密文空间密文空间C=ZC=Zn n密钥的生成密钥的生成选择互异素数选择互异素数p p、q q，计算，计算n=pqn=pq，(n)=(p-(n)=(p-1)(q-1)1)(q-1)选择满足条件选择满足条件gcd(gcd(n),e)=1(n),e)=1，0e0e (n)(n)的整数的整数e e计算计算d d，使使d=ed=e-1-1mod mod (n)(n)公钥公钥Pk=ePk=e，nn私钥私钥Sk=dSk=d，p p，qqRSARSA密码体制描述密码体制描述加密加密 (用用e e，n)n)明文：明文：MnMn（若明文比（若明文比n

12、 n长，则对明文进行分组，长，则对明文进行分组，确保每一个分组满足确保每一个分组满足Mn Mn）密文：密文：C=MC=Me e (mod n)(mod n)解密解密 (用用d d，n)n)密文：密文：C C 明文：明文：M=CM=Cd d (mod n)(mod n)BobBob为接收（实现）者：为接收（实现）者：BobBob选择选择p=7p=7和和q q1717则则n=119,n=119,(n)=616(n)=61696962 25 533选择一个正整数选择一个正整数e(0e e(0e (n)(n)能用作加密指数能用作加密指数 ，当且，当且仅当仅当e e不能被不能被2 2，3 3所整除，即满

13、足所整除，即满足(e(e，(n)(n)1 1假设假设BobBob选择选择e=5e=5，那么用辗转相除法将求得：，那么用辗转相除法将求得：d=e d=e-1-1 77(mod 96)77(mod 96)BobBob的私钥的私钥d=77d=77，7 7，1717，保密；公钥为，保密；公钥为55，119 119 ，公开公开 RSARSA的例子的例子RSARSA的例子的例子现假设现假设AliceAlice想发送明文想发送明文1919给给BobBob：lAlice计算：计算：195mod11966，在开放信道上发送密文，在开放信道上发送密文66给给Bob；lBob收到密文计算：收到密文计算：6677mo

14、d11919，从而恢复明文。，从而恢复明文。例：例：p=47,q=61,(n)=(47-1)(61-1)=2760时，时，选择选择e=167是否是否满足秘密密满足秘密密钥的钥的条件条件？QX1X2X3Y1Y2Y31027600116716011671168811168811779111779233982339172817117281719314231931427412231用用辗转相除法辗转相除法计算：计算：gcd(2760,167)=1即可证明即可证明e满足条件满足条件。RSARSA密码体制的证明密码体制的证明欧拉定理：欧拉定理：若整数若整数a与整数与整数n互素，则互素，则a(n)1(mod

15、 n)RSARSA密码体制的证明密码体制的证明(1)(1)当当n n非常大时，攻击者要将其分解为两个不同素数非常大时，攻击者要将其分解为两个不同素数p p、q q的乘积是非常困难的，这就是著名的大整数因子分解的乘积是非常困难的，这就是著名的大整数因子分解困难的问题。这就保证了攻击者不能得到困难的问题。这就保证了攻击者不能得到 (n)=(p(n)=(p1)(q1)(q1)1)从而不能从公钥从而不能从公钥e e推导出私钥推导出私钥d=e d=e-1-1 mod mod (n)(n)来。来。RSARSA密码体制的分析密码体制的分析RSARSA密码体制的分析密码体制的分析(2)(2)加密函数加密函数C

16、=MC=Me e (mod n)(mod n)是一个单向函数，由是一个单向函数，由MM、e e、n n计算密文计算密文C C容易；但在不知道陷门信息容易；但在不知道陷门信息d d、p p、q(q(私私钥钥)的情况下，已知的情况下，已知C C、e e、n n恢复明文恢复明文MM是非常困难的。是非常困难的。(3)(3)接收方由于拥有私钥接收方由于拥有私钥d d、p p、q(q(即陷门即陷门)，则可以通过，则可以通过M=CM=Cd d (mod n)(mod n)直接恢复出明文。直接恢复出明文。RSARSA的实例的实例例：设例：设p=43p=43，q=59q=59，取，取e=13e=13，用，用RS

17、ARSA算法加密和解算法加密和解密恢复明文密恢复明文“public”public”。解：解：1 1）计算：）计算：n=p n=p q=4359 q=435925392539；(n)=(p-1)(n)=(p-1)(q-1q-1)=4259=2436=4259=2436；d=ed=e-1-1modmod(n)=13(n)=13-1 1mod 2436=937mod 2436=937 2 2）将明文代替为数字，代替方案为：）将明文代替为数字，代替方案为：a-00a-00，b-01b-01，z-25(z-25(两位十进制数表示两位十进制数表示)。考虑到考虑到n=2539n=2539，这样，就可将明文，

18、这样，就可将明文“public”public”两两个字符一组转化为：个字符一组转化为：15201520，01110111和和08020802，保证，保证MnMn条件的满足。条件的满足。3 3）加密：）加密：C=MC=Me e mod n=1520mod n=152013 13 mod 2539mod 253900950095 其余两组可类似得出：其余两组可类似得出：16841684和和14101410。4 4）解密：）解密：M=CM=Cd d mod n=0095mod n=0095937 937 mod2539=1520mod2539=1520 其余两组可类似得出：其余两组可类似得出：011

19、10111和和08020802RSARSA的实例的实例 要求：若使要求：若使RSARSA安全，安全，p p与与q q必为足够大的素数，使必为足够大的素数，使分析者没有办法在有效时间内将分析者没有办法在有效时间内将n n分解出来。分解出来。建议：选择建议：选择p p和和q q大约是大约是100100位的十进制素数，位的十进制素数，模模 n n的长度要求至少是的长度要求至少是200200位十进制数位十进制数（512512比特）比特），e e 或者或者d d 也各为也各为100100位左右。位左右。RSARSA算法归纳算法归纳l1999年，一个国际密码研究小组通过一台年，一个国际密码研究小组通过一台

20、Cray900-16超级计算机和超级计算机和300台个人计算机，花费台个人计算机，花费7个多月成功地个多月成功地分解了分解了155位的十进制数（位的十进制数（512比特）。比特）。RSARSA算法归纳算法归纳为了抵抗现有的整数分解算法，对为了抵抗现有的整数分解算法，对RSARSA模模n n的素因子的素因子p p和和q q还有如下要求：还有如下要求：(1)|p-q|(1)|p-q|很大，但通常很大，但通常 p p和和q q的长度应相差不大；的长度应相差不大；(2)p-1(2)p-1 和和q-1q-1分别含有大素因子分别含有大素因子p p1 1和和q q1 1 (3)gcd(p (3)gcd(p1

21、 1-1,q-1,q1 1-1)-1)应该很小。应该很小。为了提高加密速度，通常取为了提高加密速度，通常取e e为特定的小整数，如通为特定的小整数，如通常使用常使用e=2e=24 4+1=17+1=17或或 e e2 216161 16553765537，这是因为它，这是因为它们的二进制中只有们的二进制中只有2 2个个1 1。为了提高加密速度，有时候甚。为了提高加密速度，有时候甚至允许取至允许取e e3 3，这时加密速度一般比解密速度快，这时加密速度一般比解密速度快1010倍以倍以上。上。RSARSA的实现的实现问题：问题：(1)(1)如何快速计算如何快速计算a amm mod n mod n（快速取模指数算（快速取模指数算法）？法）？(2)(2)如何判断两个数互素（求出如何判断两个数互素（求出gcdgcd）？）？(3)(3)如何判定一个给定的整数是素数？如何判定一个给定的整数是素数？(4)(4)如何找到足够大的素数如何找到足够大的素数p p和和q?q?(5)(5)如何求得如何求得d=ed=e-1-1(mod(mod (n)(n)（扩展欧几里得（扩展欧几里得算法）？算法）？