RSA公钥密码ppt课件

.1公钥密码概述Diffie-Hellman密钥交换协议背包体制简介RSA密码体制第四章公钥密码技术.2RSA公钥密码算法主要内容：RSA公钥密码算法，RSA公钥密码的实现。重点：RSA算法，脱密的快速实现，素数生成算法。难点：素数生成算法。.3RSA体制由Rivest、Shamir、Adleman于1978年首次发表；最容易理解和实现的公钥算法;经受住了多年深入的攻击;其理论基础是一种特殊的可逆模幂运算，其安全性基于分解大整数的困难性；RSA既可用于加密，又可用于数字签名，已得到广泛采用；RSA已被许多标准化组织(如ISO、ITU、IETF和SWIFT等)接纳；目前许多国家标准仍采用RSA或它的变型.4假设m为要传送的报文。1、任产生两个素数p与q，使得n=pqm2、随机选择数e：e与(p-1)(q-1)互素3、用辗转相除法求d：ed=1mod(p-1)(q-1)4、公开：（e，n），保密：d加密过程：c=memodn解密过程：m=cdmodn一、RSA算法1、RSA算法描述.5定义：任给一个正整数m，如果用m去除任意两个整数a、b所得的余数相同，称a、b对模m同余。记为：，若余数不同，则a、b对模m不同余。记为：。mbamodmbamod定理：，当且仅当m|(a-b)。mbamod定理：欧拉定理，对任意有*nZananmod1)(推论:费尔马定理，若p为素数，则papmod11}1,,2,1,0{nZn}1),(,:{*naZaaZnn其中2、工作原理.6RSA算法论证①E和D的可逆性要证明：D(E(M))=MM＝Cd＝(Me)d＝Medmodn因为ed＝1modφ(n)，这说明ed＝tφ(n)+1,其中t为某整数。所以,Med＝Mtφ(n)+1modn。因此要证明Med＝Mmodn，只需证明Mtφ(n)+1＝Mmodn。.7RSA算法论证在（M，n）＝1的情况下，根据数论(Euler定理)，Mtφ(n)＝1modn，于是有，Mtφ(n)+1＝Mmodn。.8RSA算法论证在（M，n）≠1的情况下，分两种情况：第一种情况：M∈{1,2,3,…,n-1}因为n=pq，p和q为素数，M∈{1,2,3,…,n-1}，且（M，n）≠1。这说明M必含p或q之一为其因子，而且不能同时包含两者，否则将有M≥n，与M∈{1,2,3,…,n-1}矛盾。.9RSA算法论证.10RSA算法论证不妨设M＝ap。又因q为素数，且M不包含q，故有（M，q）＝1，于是有，Mφ(q)＝1modq。进一步有，Mt(p-1)φ(q)＝1modq。因为q是素数，φ(q)＝（q-1），所以t(p-1)φ(q)＝tφ(n)，所以有Mtφ(n)＝1modq。.11于是，Mtφ(n)＝bq+1，其中b为某整数。两边同乘M，Mtφ(n)+1＝bqM+M。因为M＝ap，故Mtφ(n)+1＝bqap+M=abn+M。取模n得，Mφ(n)+1＝Mmodn。RSA算法论证.12第二种情况：M＝0当M＝0时，直接验证，可知命题成立。RSA算法论证.13RSA算法论证②加密和解密运算的可交换性D(E(M))=(Me)d=Med=(Md))e=E(D(M))modn所以，RSA密码可同时确保数据的秘密性和数据的真实性。.14RSA算法论证③加解密算法的有效性RSA密码的加解密运算是模幂运算，有比较有效的算法。.15RSA算法论证④在计算上由公开密钥不能求出解密钥小合数的因子分解是容易的，然而大合数的因子分解却是十分困难的。关于大合数的因子分解的时间复杂度下限目前尚没有一般的结果，迄今为止的各种因子分解算法提示人们这一时间下限将不低于O（EXP（lnNlnlnN）1/2）。根据这一结论，只要合数足够大，进行因子分解是相当困难的。.16RSA算法论证假设截获密文C，从中求出明文M。他知道M≡Cdmodn，因为n是公开的，要从C中求出明文M，必须先求出d，而d是保密的。但他知道，ed≡1modφ(n)，e是公开的，要从中求出d，必须先求出φ(n)，而φ(n)是保密的。但他又知道，φ(n)=(p-1)(q-1)，.17要从中求出φ(n)，必须先求出p和q，而p和q是保密的。但他知道，n=pq，要从n求出p和q，只有对n进行因子分解。而当n足够大时，这是很困难的。RSA算法论证只要能对n进行因子分解，便可攻破RSA密码。由此可以得出，破译RSA密码的困难性≤对n因子分解的困难性。目前尚不能证明两者是否能确切相等，因为不能确知除了对n进行因子分解的方法外，是否还有别的更简捷的破译方法。.183、例子：假设RSA体制中p=3,q=11,取加密密钥e=7.(1)求脱密密钥d;(2)写出相应的加密算法和脱密算法;(3)对明文m=8加密。7dmod20=1因e=7与互素,故可解模方程，即1)(modned20)(n20)1)(1()(qpn解:此时n＝p×q＝33，且得到d＝3。.19故RSA体制明、密文空间:Z/(33)加密密钥：(e,n)=(7,33)脱密密钥：(d,p,q)=(3,3,11)加密算法:c＝m7mod33脱密算法:m＝c3mod33对明文m＝8加密，得:c＝87mod33=2.20二、RSA算法的参数选择为了确保RSA密码的安全，必须认真选择密码参数：①p和q要足够大；一般应用：p和q应512bits重要应用：p和q应1024bits②p和q应为强素数文献指出，只要(p-1)、(p+1)、(q-1)、(q+1)四个数之一只有小的素因子，n就容易分解。③p和q的差要大；.21④（p-1）和（q-1）的最大公因子要小。如果（p-1）和（q-1）的最大公因子太大，则易受迭代加密攻击。⑤e的选择随机且含1多就安全，但加密速度慢。于是，有的学者建议取e＝216+1＝65537⑥d的选择d不能太小，要足够大⑦不要许多用户共用一个模n；易受共模攻击.221989年Lenstra,Manasse利用二次筛法使用数百台工作站分解了106位十进制数；1990年Lenstra,Manasse,Pollar利用数域筛法使用700台工作站花费４个月时间将155位十进制数分解成三个素数之积；1994年Atkins,Graff,Lenstra,Lerland利用多重二次筛法的双重大素数算法动用1600台计算机联网，600名志愿者花费９个月时间分解了129位十进制数；2002年成功分解158位的十进制数。结论：154位十进制数（512bit）的模长已经不安全，应使用308位十进制数（1024bit）模长。.23三、RSA算法中大素数生成RSA的安全性基础是基于大合数分解的困难性，在RSA算法中要求模数N是两个大素数p和q的乘积。用户选择模数N的方法是先找到两个素数，然后生成相应的模数N。素数判定是要解决的首要问题。.241、产生大素数的算法（Rabin素性检测算法）由欧拉定理知，若n为素数：*nZananmod11则n可能为素数，也可能为合数。Rabin由此设计了一个判定n是否为素数的算法。反过来若：，则n必为合数。nanmod11nanmod11若.251、产生大素数的算法——Rabin素性检测算法Rabin素性检测法是一种概率素数测试法。其输入为一奇数，输出为两种状态Yes或No。若输入一奇数N，而输出为No，即表示N必定为合数。若输出为Yes，则表示N为素数的概率为1-ε，其中ε为此素数测试法中可控制的任意小数，但不能为0。（ε是在N是合数的条件下误判为素数的条件概率。）.26Rabin素性检测算法：（1）任取一个大奇数n（2）任取且(a,n)=1（3）如果,则判n是素数；否则判n是合数，重新选取n重复上过程。}2,,3,2{nanpnRabin证明了由上述算法所产生的素数的误判概率:41)(是合数数判定为素nnP由此,我们将算法中的第(2)和(3)步骤重复k次,这样判定n为素数的误判概率小于等于(1/4)k。计算复杂度为：O((log2n)3).27Miller-Rabin算法随机选择一个奇整数n(如利用伪随机数产生器)；随机选择一个整数an；执行诸如Miller-Rabin等概率素数测试。若n未通过测试，则转到第一步；若n通过足够多次的测试，则接受n；否则转向第2步。.28在实际使用中,通过首先检验待检测的随机数是否是小素数(例如所有小于1000的素数)的倍数，待检测通过后再执行Rabin检测。Miller-Rabin素数检测算法，已经作为标准的检测算法列入IEEEP1363的附录和NIST的数字签名标准的附录，作为密码学标准使用。.29RSA的加脱密计算都是在模N运算下进行的，尽管这两个加脱密计算公式形式上比较简单，但由于其加、脱密的两个主要运算，即指数运算与模大整数运算均涉及到很大的数，故RSA的实现还是有较大的难度。①快速乘方算法.30指数运算最简单而直接的计算方法，就是将m连续乘e-1次，如此就可以获得的值了。当m或e很大时，其计算复杂度将是非常高的。em在指数运算中，比较有名的是二元法（也称为平方乘法）.31设e为k位二进制数，w(e)为e的二进制系数中为1的个数，则最多只需要计算w(e)-1次平方和w(e)次数的模乘。从而大大简化了计算。.32以512比特加密指数为例，整数e的二进制表示为:5115112210222eeeee一般的加密过程为:Nmmmmmeeeeemod)))((01510511222.3323120212222()(mod)lllleeeeemmmmmNNmemod3412302122222(())(mod)lllleeeeeemmmmmmN1201222(()))(mod)lleeeemmmmN201222(())(mod)leeemmmmN当要对明文进行加密时，可先进行预处理，计算出m2、m3等，这种方法我们称之为窗口法。.34例：131520(mod2539)计算:B11011202121323)1,0,1,1(),,,(0123eeee2539mod1520133021222(((1520)1520)1520)1520(mod2539)eeee2202((15201520)1520)1520(mod2539).35第一步首先计算215202449(mod2539)第二步计算24491520306(mod2539)第三步计算23062232(mod2539)第四步计算22232306(mod2539)最后一步计算3061520483(mod2539)131520483(mod2539)结论：.36②快速模乘算法反复平方乘算法解决了快速乘方取模的问题，仍未解决快速模乘的问题；Montgomery算法是一种快速模乘的好算法；将以上两种算法结合成为实现RSA密码的有效方法。.37Montgomery算法的思路：•要计算Y=ABmodn,因为n很大，取模运算困难，采取一个小的模R，回避大模数的计算。•利用空间换时间，多用存储空间换取快速。•缺点：不能直接计算出Y=ABmodn，只能计算出中间值ABR-1modn，因此还需要预处理和调整运算。一次性计算Y=ABmodn并不划算。•适合：RSA等密码中多次的模乘计算。.38对称密钥密码学与公钥密码学1、对称密钥密码学的优点（1）能够设计为具有很高的数据吞吐率。硬件实现可以达到每秒加密几百兆字节，而软件实现的吞吐率也达到了每秒兆字节的数量级。（2）对称密码的密钥相对较短。（3）对称密钥密码可以作为要素来构造各种密码机制。比如伪随机数生成器、杂凑函数、快速数字签名方案等（4）对称密钥密码能合成强密码。简单变换容易被分拆，但是研究其弱点后，可用来构造强的乘积密码。.392、对称密钥密码学的缺点（1）在一个双方的通信中，密钥必须在两端都保密。（2）在大型网络中，