信息安全导论（以问题为导向） 课件 04 公开密钥密码

1公开密钥密码

PublicKeyCryptography教学视频、国家级一流在线课程链接：/course/FUDAN-12063578112内容提要对称密钥密码的密钥交换问题公钥密码模型提出设计公钥密码的基本要求数字签名RSA算法公钥密码的特征总结Diffie-Hellman密钥交换算法3内容提要1、对称密钥密码的密钥交换问题4回顾：对称密钥密码对称的,单密钥,秘密密钥,传统密码:发送方加密和接收方解密使用同一个的密钥该密钥需要事先由发送方和接收方实现共享，是发送方和接收方共同的秘密如果密钥泄露，则不安全（无法提供保密性服务）对称：通信双方是对等的5回顾：对称密钥密码模型双方共享的秘密：KeyAliceBob发送方接收方安全的信道

加密容易实现，但密钥交换是个问题6内容提要2、公钥密码模型提出7BobAlice每个人有两个密钥公钥，Publickey——公开私钥，Privatekey——保密公开密钥(非对称)密码模型8BobAliceBob’sPublickeyAlice’sPublickeyBob’sPrivatekeyAlice’sPrivatekey非对称密码模型公开9BobAliceBob’sPublickeyAlice’sPublickeyBob’sPrivatekeyAlice’sPrivatekey非对称密码模型公开保密保密10用非对称密码实现“保密通信”BobAlice提供“保密通信”安全服务攻击者11两种密码体制据使用的密钥数量对称的,单密钥,秘密密钥,传统密码技术:发送方和接收方使用同一个的密钥非对称的,双密钥,公钥密码技术:发送方和接收方使用不同的密钥加密密钥和解密密钥分割开来,且无法由一个推出另一个,使得不仅可以公开密码算法,而且加密密钥也可公开（公告牌、号码簿）12公开密钥密码人类文明史3000年以来，密码技术一个新的篇章两个密钥–apublic&aprivatekey非对称：通信双方的地位不平等往往应用数论的一些函数精心构造补充而非取代对称密钥密码技术缺点：公钥密码的主要弱点是加密和解密速度慢13历史1976年，Diffie和Hellman在论文“密码学新方向（NewDirectioninCryptography）”中首次提出了公开密钥密码体制的思想；Diffie和Hellman提出了第一个基于公开密钥思想的密码算法，称为DH算法，此算法可以用于实现密钥交换。1977年，Rivest、Shamir和Adleman三个人实现了公开密钥密码体制，现在称为RSA算法，它是第一个既能用于密钥交换、也能用于数据加密和数字签名的算法。14内容提要3、设计公钥密码的基本要求一个公开密钥系统由六要素组成：明文公开密钥（记作：PU或KU）私有密钥（记作：KR或PR）加密算法密文解密算法公开密钥加密系统参与方B容易通过计算产生出一对密钥（公开密钥KUb

，私有密钥KRb

）发送方A很容易计算产生密文接收方B通过计算解密密文敌对方即使知道公开密钥KUb

，要确定私有密钥KRb

在计算上是不可行的敌对方即使知道公开密钥KUb

和密文C，要确定明文M在计算上是不可行的密钥对互相之间可以交换使用公开密钥算法的基本要求公钥密码构建在计算复杂性理论基础之上17往往让敌方求解目前仍未找到多项式时间算法的NP完全问题18内容提要4、数字签名19密钥对互相之间可以交换使用：20数字签名BobAlice提供“数字签名”安全服务21公钥密码能提供的安全服务保密通信本课程最初提出的安全需求，先前讲解的密码方案主要用于解决这个问题密钥交换数字签名能够检验加密数据的来源（认证）能够抗抵赖22公钥密码原理总结公开密钥密码技术涉及两个密钥:公钥：

公开，任何人可以知道,用于加密明文，验证签名私钥,仅有接收者/拥有者自己知道，用于解密，签名非对称的含义：密钥的不对称：加／解密的密钥不同用于加密的不能解密，用于解密的不能加密23本讲内容5、RSA算法5.1密钥生成1977年由MIT的Rivest,Shamir和Adleman

三人提出是一个分组加密方法目前被最广泛地采用理论基础是数论中的下述论断:要求得两个大素数的乘积是容易的,但要分解一个合数为两个大素数的乘积,则在计算上几乎是不可能的。RSA算法25RSA密钥生成每个用户执行：（1）生成两个大素数p和q。（2）计算这两个素数的乘积n=p×q。（3）计算小于n并且与n互质的整数的个数，即欧拉函数φ(n)=(p-1)(q-1)。（4）选择一个随机数e满足1<e<φ(n)，并且e和φ(n)互质，即gcd(e,φ(n))=1。（5）解方程e·d

≡1modφ(n)，求出d26RSA密钥（6）保密d，p和q（销毁），公开n和e。公钥公开:PU={e,n}私钥保密:PR={d,n}密钥生成的计算量如何得到足够大的随机素数如何求解方程e·d

≡1modφ(n)27如何得到足够大的随机素数实际应用所采用的方法是：首先，产生一个足够大的随机数，然后，通过采用一个概率多项式时间算法来检测该随机数是否为素数（即是否具有素性）。常用的两个素性测试算法：Solovay-Strassen素性测试；Miller-Rabin素性测试。索洛维-斯特拉森求解方程e·d

≡1modφ(n)扩展的欧几里德算法（辗转相除法）29当e＝1001，ø(n)＝3837时

方程为x*1001=1(mod3837)

求解过程：

3837=3*1001+834

1001=1*834+167

834=4*167+166

167=166+1

所以

1=167-166

=167-(834-4*167)

=5*167-834

=5*(1001-834)-834

=5*1001-6*834

=5*1001-6*(3837-3*1001)

=23*1001-6*383730本讲内容5、RSA算法5.2加解密算法31RSA使用公钥公开:PU={e,n}私钥保密:PR={d,n}加密一个报文M，发送方:获取接收方的公钥

PU={e,n}

计算:C=Memodn,where0≤M<n解密

密文C，接收方:用自己的私钥

PR={d,n}

计算:M=Cdmodn

32RSA例子–密钥挑选质数:p=17&q=11计算

n=?33RSA例子–密钥挑选质数:p=17&q=11计算

n=pq=17x11=187计算ø(n)=(p–1)(q-1)=16x10=160选择e:

gcd(e,160)=1;不妨选e=7求解d:

ed=1mod160

且d

<160

d=23，显然

23x7=161=10x160+1PublickeyPU={7,187}PrivatekeyPR={23,187}34RSA例子–加密/解密RSA加密/解密:M=88(注意:

88<187)加密:C=887mod187=11

解密:M=1123mod187=88

模指数运算简化35在RSA密码体制中，加密和解密运算都是模指数运算，即C=Memodn可以通过e-1次模乘来实现计算，然而，如果e非常大，其效率会很低下平方-乘算法可以把计算所需的模乘的次数降低1123mod187=[(111mod187)*(112mod187)*(114mod187)*(118mod187)*(118mod187)]mod187111mod187=11112mod187=121114mod187=14641mod187=55118mod187=214358881mod187=331123mod187=(11*121*55*33*33)mod187=79720245mod187=88求模指数实例37RSA注意RSA加密时，明文以分组的方式加密：每一个分组的比特数应该小于log2n比特，即：M<n选取的素数p和q要足够大，从而乘积n足够大，在事先不知道p和q的情况下分解n是计算上不可行的。38本讲内容5、RSA算法5.3

RSA安全性讨论39RSA算法的安全性在理论上,RSA的安全性取决于模n分解的困难性。若n被分解成功,则RSA被攻破。目前最快的分解因子算法其时间复杂性为并没有证明分解大整数就是NP问题,并不能排除存在尚未发现的多项式时间算法。也没有证明对RSA的攻击的难度与分解n等价因此对RSA的攻击的困难程度不比大数分解难目前，RSA的一些变种算法已被证明等价于大数分解。不管怎样，分解n是最显然的攻击方法。现在人们已能分解多个十进制位的大素数，因此，模数n必须选大一些。40RSA因数分解挑战分解挑战奖金于2007终止ChallengeNumber Prize($US) StatusRSA-576(174Digits) $10,000 Factored(Dec2003)RSA-640(193Digits) $20,000 Factored(Nov2005)RSA-704(212Digits) $30,000 Factored(July2012)RSA-768(232Digits) $50,000 Factored(Dec2009)RSA-896(270Digits) $75,000 NotFactoredRSA-1024(309Digits) $100,000 NotFactoredRSA-1536(463Digits) $150,000 NotFactoredRSA-2048(617Digits) $200,000 NotFactoredRSA-704 DecimalDigits:212

7403756347956171282804679609742957314259318888923128908493623263897276503402826627689199641962511784399589433050212758537011896809828673317327310893090055250511687706329907239638078671008609696253793465056379635941RSA-232(768bits)hasnotbeenfactoredsofar.100988139787192354690956489430946858281823382195557395514112051620583102133852854537436610975715436366491338008491706516992170152473329438927028023438096090980497644054071120196541074755382494867277137407501157718230539834060616207942RSA算法的速度由于都是大数计算，RSA最快的情况也比DES慢许多倍，无论是软件还是硬件实现。速度一直是RSA的缺陷。一般来说只用于少量数据加密。RSA是被研究得最广泛的公钥算法，提出到现在已近二十年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一43本讲内容6、公钥密码的特征总结公开密钥算法设计需要有以下基本要求：加密与解密由不同的密钥完成；知道加密算法，从加密密钥得到解密密钥在计算上是不可行的；两个密钥中任何一个都可以作为加密而另一个用作解密。公钥密码的特征公钥密码算法基础单向函数

对于一个函数，如果对于其定义域上的任意x，都容易计算，同时，对于其值域中几乎所有的取值

y

，计算其逆函数都是不可行的，则函数被称为单向函数。

可以提供单向函数的三大数学难题大整数分解问题（简称IFP）；离散对数问题（简称DLP）；椭圆曲线离散对数问题（简称ECDLP）。

对于一个单向函数，如果其逆函数在已知某些辅助信息的情况下容易求解得出，则称该单向函数为单向陷门函数。构造公钥密码系统的关键是如何在求解某个单向函数的逆函数的NP完全问题中设置合理的“陷门”。单向陷门函数