RSA公钥密码体制简介.ppt

1,公钥密码技术,2,RSA公钥密码算法,主要内容：RSA公钥密码算法，RSA公钥密码的实现。 重点： RSA算法，脱密的快速实现，素数生成算法。 难点：素数生成算法。,3,RSA体制,由Rivest、Shamir、Adleman于1978年首次发表； 最容易理解和实现的公钥算法; 经受住了多年深入的攻击; 其理论基础是一种特殊的可逆模幂运算，其安全性基于分解大整数的困难性； RSA既可用于加密，又可用于数字签名，已得到广泛采用； RSA已被许多标准化组织(如ISO、ITU、IETF和SWIFT等)接纳； 目前许多国家标准仍采用RSA或它的变型,4,假设m为要传送的报文。 1、任产生两个素数p与q，使得n=pqm 2、随机选择数e：e与(p-1)(q-1) 互素 3、用辗转相除法求d：ed=1 mod(p-1)(q-1) 4、公开：（e，n），保密：d 加密过程：c=me mod n 解密过程：m=cd mod n,一、RSA算法,1、RSA算法描述,5,定义：任给一个正整数m，如果用m去除任意两个整数a、b所得的余数相同，称a、b对模m同余。记为： ，若余数不同，则a、b对模m不同余。记为： 。,定理： ，当且仅当m|(a-b)。,定理：欧拉定理，对任意 有,推论:费尔马定理，若p为素数，则,其中,2、工作原理,6,RSA算法论证, E和D的可逆性,要证明：D(E(M)=M,MCd (Me)dMed mod n,因为ed1 mod(n)，这说明edt(n)+1,其中 t为某整数。所以,Med Mt(n)+1 mod n 。,因此要证明Med M mod n ，只需证明 M t(n)+1 M mod n 。,7,RSA算法论证,在（M，n）1的情况下，根据数论(Euler定理)， M t(n) 1 mod n ，,于是有， M t(n)+1 M mod n 。,8,RSA算法论证,在（M，n）1的情况下，分两种情况：,第一种情况：M1,2,3,n-1,因为n=pq，p和q为素数， M1,2,3,n-1，且（M，n）1 。,这说明M必含p或q之一为其因子，而且不能同 时包含两者， 否则将有Mn ， 与 M1,2,3,n-1矛盾。,9,RSA算法论证,10,RSA算法论证,不妨设Map 。 又因q为素数，且M不包含q，故有（M，q）1， 于是有，M (q) 1 mod q 。 进一步有，M t(p-1)(q) 1 mod q。 因为q是素数，(q)（q-1），所以t(p-1)(q) t(n)， 所以有 M t(n) 1 mod q。,11,于是，M t(n) bq+1，其中b为某整数。 两边同乘M， M t(n)+1 bqM+M 。 因为Map，故 M t(n)+1 bqap+M =abn+M 。 取模n得， M (n)+1 M mod n 。,RSA算法论证,12,第二种情况：M0 当M0时，直接验证，可知命题成立。,RSA算法论证,13,RSA算法论证,加密和解密运算的可交换性,D(E(M)=(Me)d =Med =(Md)e =E(D(M) mod n,所以，RSA密码可同时确保数据的秘密性和数据的 真实性。,14,RSA算法论证,加解密算法的有效性,RSA密码的加解密运算是模幂运算，有比较有效 的算法。,15,RSA算法论证,在计算上由公开密钥不能求出解密钥,小合数的因子分解是容易的，然而大合数的因子分 解却是十分困难的。关于大合数的因子分解的时间 复杂度下限目前尚没有一般的结果，迄今为止的各 种因子分解算法提示人们这一时间下限将不低于 O（EXP（lnNlnlnN）1/2）。 根据这一结论，只要合数足够大，进行因子分解是 相当困难的。,16,RSA算法论证,假设截获密文C，从中求出明文M。他知道,MCd mod n ， 因为n是公开的，要从C中求出明文M，必须先求 出d，而d是保密的。但他知道， ed1 mod (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进行因子分解的方法外，是否还有别的更简捷的破译方 法。,18,3、例子： 假设RSA体制中p=3,q=11,取加密密钥e=7. (1) 求脱密密钥d; (2) 写出相应的加密算法和脱密算法; (3) 对明文m=8加密。,7d mod20=1,因e=7与 互素, 故可解模方程 ，即,解: 此时npq33，且,得到d3。,19,故RSA体制明、密文空间: Z/(33) 加密密钥：(e, n) =(7, 33) 脱密密钥：(d, p, q) =(3, 3,11),加密算法: cm7mod33 脱密算法: mc3mod33,对明文m8加密，得: c87mod33=2,20,二、RSA算法的参数选择,为了确保RSA密码的安全，必须认真选择密码参数： p和q要足够大； 一般应用：p和q应512 bits 重要应用：p和q应1024 bits p和q应为强素数 文献指出，只要(p-1)、(p+1)、(q-1)、(q+1)四 个数之一只有小的素因子，n就容易分解。 p和q的差要大；,21,（p-1）和（q-1）的最大公因子要小。 如果（ p-1）和（q-1）的最大公因子太大，则易受迭代加密 攻击。 e的选择 随机且含1多就安全，但加密速度慢。于是，有的学者建议取 e216+165537 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。 素数判定是要解决的首要问题。,24,1、产生大素数的算法（Rabin素性检测算法）,由欧拉定理知，若n为素数：,则n可能为素数，也可能为合数。 Rabin由此设计了一个判定n是否为素数的算法。,反过来若： ，则n必为合数。,若,25,1、产生大素数的算法Rabin素性检测算法,Rabin素性检测法是一种概率素数测试法。 其输入为一奇数，输出为两种状态Yes或No。若输入一奇数N，而输出为No，即表示N必定为合数。若输出为Yes，则表示N为素数的概率为1-，其中为此素数测试法中可控制的任意小数，但不能为0。（ 是在N是合数的条件下误判为素数的条件概率。）,26,Rabin素性检测算法： （1）任取一个大奇数n （2）任取 且(a,n)=1 （3）如果, 则判n是素数； 否则判n是合数，重新选取n重复上过程。,Rabin证明了由上述算法所产生的素数的误判概率:,由此,我们将算法中的第(2)和(3)步骤重复k次, 这样判定n为素数的误判概率小于等于(1/4)k。,计算复杂度为：O(log2n)3),27,Miller-Rabin算法,随机选择一个奇整数n(如利用伪随机数产生器)； 随机选择一个整数an； 执行诸如Miller-Rabin等概率素数测试。若n未通过测试，则转到第一步； 若n通过足够多次的测试，则接受n；否则转向第2步。,28,在实际使用中,通过首先检验待检测的随机数是否是小素数(例如所有小于1000的素数)的倍数，待检测通过后再执行Rabin检测。 Miller-Rabin素数检测算法，已经作为标准的检测算法列入IEEE P1363的附录和NIST的数字签名标准的附录，作为密码学标准使用。,29,RSA的加脱密计算都是在模N运算下进行的，尽管这两个加脱密计算公式形式上比较简单，但由于其加、脱密的两个主要运算，即指数运算与模大整数运算均涉及到很大的数，故RSA的实现还是有较大的难度。,快速乘方算法,30,指数运算 最简单而直接的计算方法，就是将m连续乘e-1次，如此就可以获得的值了。 当m或e很大时，其计算复杂度将是非常高的。,在指数运算中，比较有名的是二元法（也称为平方乘法）,31,设e为k位二进制数，w(e)为e的二进制系数中为1的个 数，则最多只需要计算w(e) -1次平方和w(e)次数的模 乘。从而大大简化了计算。,32,以512比特加密指数为例，整数e的二进制表示为:,一般的加密过程为:,33,当要对明文进行加密时，可先进行预处理，计算出m2、m3等，这种方法我们称之为窗口法。,34,例：,计算:,35,第一步首先计算,第二步计算,第三步计算,第四步计算,最后一步计算,结论：,36,快速模乘算法,反复平方乘算法解决了快速乘方取模的问题， 仍未解决快速模乘的问题； Montgomery算法是一种快速模乘的好算法；,将以上两种算法结合成为实现RSA密码的 有效方法。,37,Montgomery算法的思路： 要计算Y=AB mod n ,因为n很大，取模运算困难，采取一 个小的模R，回避大模数的计算。 利用空间换时间，多用存储空间换取快速。 缺点：不能直接计算出Y=AB mod n ，只能计算出中间 值ABR-1 mod n ，因此还需要预处理和调整运算。一次性 计算Y=AB mod n并不划算。 适合：RSA等密码中多次的模乘计算。,38,对称密钥密码学与公钥密码学,1、对称密钥密码学的优点,（1）能够设计为具有很高的数据吞吐率。硬件实现可以达到每秒加密几百兆字节，而软件实现的吞吐率也达到了每秒兆字节的数量级。,（2）对称密码的密钥相对较短。,（3）对称密钥密码可以作为要素来构造各种密码机制。比如伪随机数生成器、杂凑函数、快速数字签名方案等,（4）对称密钥密码能合成强密码。简单变换容易被分拆，但是研究其弱点后，可用来构造强的乘积密码。,39,2、对称密钥密码学的缺点,（1）在一个双方的通信中，密钥必须在两端都保密。 （2）在大型网络中，要管理许多密钥对。其结果是，有效的密钥管理需要一个无条件可信的TTP。（称一个TTP是无条件可信的，如果它在所有事情上都可信。例如它也许可以访问用户的秘密密钥和私钥，还承担着公钥和标识符的联系） （3）对实体A与B之间的一个双方通信，使用密钥的良好习惯是：经常更换密钥，通常是会话密钥一次一换。 （4）源自对称密钥加密的数字签名机制通常需要关于公开验证函数的大密钥，或者使用TTP。,40,3、公钥密码学的优点,（1）只有私钥必须保密。（但必须保证公钥的真实性） （2）与无条件可信的TTP相反，公钥密码管理需要的只是一个功能上可信的TTP（称一个TTP是功能上可信的，如果它是诚实且公正的，但是不可以访问用户的秘密密钥和私钥）。关于使用方式，和实时的需要使用相反，这个TTP也许只需以离线方式使用。 （3）依赖于使用方式的差别，一个私钥/公钥对可以在一段相当长的时期内保持不变，甚至数年。比如多次会话使用相同密钥。,41,（4）许多公钥方案产生了相对有效的数字签名机制。用于刻画公开验证函数的密钥通常比对称密钥小很多。 （5）在大型网络中，所需密钥的数量要比对称密钥情形下少很多。,42,4、公钥密码学的缺点,（1）在吞吐率方面，大多流行的公钥加密方法要比已知最好的对称密钥加密方案慢几个数量级。 （2）密钥长度（如RSA的1024比特）明显要比对称密钥（如64比特或128比特）加密所需大得多（10倍或更多）。这是因为针对对称密钥系统的最有效的攻击是密钥穷搜（这一般是设计要求），而对公钥系统来说，快捷攻击（如因子分解）比穷搜有效得多。,43,（3）没有公钥方案被证明是安全的（对分组秘密也一样）。至今发现的最有效的公钥加密方案都把安全性建立在一小批数论问题的困难性假定之上。 （4）公钥密码学没有对称密钥加密那样长久的历史，它在20世纪70年代中期才被发现。,44