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

《第6章 公钥密码体制(RSA算法)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、密码学基础赵海燕zhaohaiyan@ccniit.com第6章　公钥密码体制(RSA算法)§6－1概　述问题的提出：密钥管理困难传统密钥管理两两分别用一对密钥时，则n个用户需要C(n,2)=n(n-1)/2个密钥，当用户量增大时密钥空间急剧增大。如:n=100时C(100,2)=4,995n=5000时C(5000,2)=12,497,500陌生人间的保密通信问题数字签名的问题传统加密算法无法实现抗抵赖的需求公钥密码体制公钥密码又称为双钥密码、非对称密码公钥密码体制提出的标志性文献：1976年，Diffie和Hellman，《密码学的新方向》W.DiffieandM.E.Hellman

2、,NewDirectionsinCryptography,IEEETransactiononInformationTheory,V.IT-22.No.6,Nov1976,PP.644-654公钥密码算法基于数学函数而不是代替和换位操作。支持数字签名：用两个密钥中的任何一个加密的内容，都可以用对应的另一个密钥解密。对公钥密码体制的要求（1）参与方B容易通过计算产生一对密钥（公开密钥KUb和私有密钥KRb）。（2）在知道公开密钥和待加密报文M的情况下，对于发送方A，很容易通过公开密钥计算产生对应的密文：C＝EKUb（M）（3）接收方B使用私有密钥容易通过计算解密所得的密文以便恢复原来的报文：

3、M＝DKRb（C）＝DKRb（EKUb（M））（4）敌对方即使知道公开密钥KUb，要确定私有密钥KRb在计算上是不可行的。（5）敌对方即使知道公开密钥KUb和密文C，要想恢复原来的报文M在计算上也是不可行的。（6）加密和解密函数可以以两个次序中的任何一个来使用（适用于部分公钥密码体制）:M＝DKRb(EKUb(M))（机密性）M=EKUb(DKRb(M))（数字签名）对公钥密码体制的要求陷门设计公钥密码算法的关键——单向陷门函数满足下列条件的函数f叫做单向陷门函数：(1)给定x，计算y=f(x)是容易的(2)给定y,计算x使y=f(x)是不可行的(3)存在δ，已知δ时,对给定的任何y，若

4、相应的x存在，则计算x使y=f(x)是容易的设计公钥密码算法的关键——单向陷门函数单向函数陷门性陷门信息（1）当用陷门函数f作为加密函数时，可将f公开，这相当于公开加密密钥。此时加密密钥便称为公开密钥，记为Pk。（2）f函数的设计者将δ保密，用作解密密钥，此时δ称为秘密密钥，记为Sk。（3）由于加密函数是公开的，任何人都可以将信息x加密成y=f(x)，然后送给函数的设计者（当然可以通过不安全信道传送）；由于设计者拥有Sk，他自然可以解出x=f-1(y)。（4）窃听者由于没有Sk，则他由截获的密文y=f(x)推测x是不可行的。设计公钥密码算法的关键——单向陷门函数公开密钥密码系统的分析方法

5、蛮力攻击(对密钥)防范措施：采用长密钥公开密钥算法本身可能被攻破找到从公钥计算私钥的方法可能报文攻击(对报文本身的强行攻击)搜索报文本身的所有可能，跟密文匹配同等加密强度下DES和RSA密钥长度的比较公钥密码系统的应用加密/解密数字签名（第9章）密钥交换（第7章）并不是所有的公开密钥密码体制都支持加密解密、数字签名和密钥交换。如RSA、ECC三种都支持；DSA只用于数字签名；DH只用于密钥交换。混合密码系统——加密用对称密码加密明文，发挥速度优势用非对称密码加密密钥，发挥密钥分发管理优势混合密码系统——解密用非对称密码解密密钥用对称密码解密密文§6－2RSA由Rivest，Shamir和

6、Adleman在1978年提出，是目前唯一被广泛接受并实现的通用公开密钥密码算法。其数学基础是Euler定理，并建立在大整数因子分解困难问题之上。陷门RSA密码体制描述明文空间P＝密文空间C=Zn密钥的生成选择互异素数p、q，计算n=p×q，(n)=(p-1)(q-1)选择满足条件gcd((n),e)=1，0

7、dn)Bob为接收（实现）者：Bob选择p=7和q＝17则n=119,(n)=6×16＝96＝25×3选择一个正整数e(0