rsa公钥密码体制简介

《rsa公钥密码体制简介》由会员分享，可在线阅读，更多相关《rsa公钥密码体制简介（46页珍藏版）》请在金锄头文库上搜索。

1、1 公钥密码技术 2 RSARSA公钥密码算法公钥密码算法 n主要内容：RSA公钥密码算法，RSA公钥密 码的实现。 n重点： RSA算法，脱密的快速实现，素数 生成算法。 n难点：素数生成算法。 3 RSA体制 由Rivest、Shamir、Adleman于1978年首次 发表； 最容易理解和实现的公钥算法; 经受住了多年深入的攻击; 其理论基础是一种特殊的可逆模幂运算，其 安全性基于分解大整数的困难性； RSA既可用于加密，又可用于数字签名，已 得到广泛采用； RSA已被许多标准化组织(如ISO、ITU、IETF 和SWIFT等)接纳； 目前许多国家标准仍采用RSA或它的变型 4 假设m为

2、要传送的报文。 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 一、一、RSARSA算法算法 1、RSA算法描述 5 定义：任给一个正整数m，如果用m去除任意两个整 数a、b所得的余数相同，称a、b对模m同余。记为： ，若余数不同，则a、b对模m不同余。记为： 。 定理： ，当且仅当m|(a-b)。 定理：欧拉定理，对任意 有 推论:费尔马定理，若p为素数，则 其中 2、工作原理 6 RSA算法论

3、证 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

4、。 这说明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得，

5、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算法论证 在计算上由公开密钥不能求出解密钥 小合数的因子分解是容易的，然而大合数的因子分 解却是十分困难的。关于大合数的因子分解的时间 复杂度下限目前尚没有一般的结果，迄今为止的

6、各 种因子分解算法提示人们这一时间下限将不低于 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足够大时 ， 这是

7、很困难的。 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)

8、脱密密钥：(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的选择

9、随机且含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年成

10、功分解158位的十进制数。 结论：154位十进制数（512bit）的模长已经不 安全，应使用308位十进制数（1024bit）模长。 23 三、三、RSARSA算法中大素数生成算法中大素数生成 l RSA的安全性基础是基于大合数分解的困 难性，在RSA算法中要求模数N是两个大素数 p和q的乘积。 l 用户选择模数N的方法是先找到两个素数， 然后生成相应的模数N。 l 素数判定是要解决的首要问题。 24 1、产生大素数的算法（Rabin素性检测算法） 由欧拉定理知，若n为素数： 则n可能为素数，也可能为合数。 Rabin由此设计了 一个判定n是否为素数的算法。 反过来若： ，则n必为合数。 若

11、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次,

12、 这样判定n为素数的误判概率小于等于(1/4)k。 计算复杂度为：O(log2n)3) 27 Miller-Rabin算法 l 随机选择一个奇整数n(如利用伪随机数产生器 )； l 随机选择一个整数an； l 执行诸如Miller-Rabin等概率素数测试。若n 未通过测试，则转到第一步； l 若n通过足够多次的测试，则接受n；否则转 向第2步。 28 在实际使用中,通过首先检验待检测的随机数是否 是小素数(例如所有小于1000的素数)的倍数，待检测 通过后再执行Rabin检测。 Miller-Rabin素数检测算法，已经作为标准的检测 算法列入IEEE P1363的附录和NIST的数字签名标

13、准的 附录，作为密码学标准使用。 29 RSA的加脱密计算都是在模N运算下 进行的，尽管这两个加脱密计算公式形式 上比较简单，但由于其加、脱密的两个主 要运算，即指数运算与模大整数运算均涉 及到很大的数，故RSA的实现还是有较大 的难度。 快速乘方算法 30 指数运算 最简单而直接的计算方 法，就是将m连续乘e-1次，如此就可 以获得的值了。 当m或e很大时，其计算复杂度将是 非常高的。 在指数运算中，比较有名的是二元法 （也称为平方乘法） 31 设e为k位二进制数，w(e)为e的二进制系数中为1的个 数，则最多只需要计算w(e) -1次平方和w(e)次数的模 乘。从而大大简化了计算。 32

14、以512比特加密指数为例，整数e的二进制表示为: 一般的加密过程为: 33 当要对明文进行加密时，可先进行预处理， 计算出m2、m3等，这种方法我们称之为窗口法。 34 例： 计算: 35 第一步首先计算 第二步计算 第三步计算 第四步计算 最后一步计算 结论： 36 快速模乘算法 反复平方乘算法解决了快速乘方取模的问题 ， 仍未解决快速模乘的问题； Montgomery算法是一种快速模乘的好算法； 将以上两种算法结合成为实现RSA密码的 有效方法。 37 Montgomery算法的思路： 要计算Y=AB mod n ,因为n很大，取模运算困难，采取一 个小的模R，回避大模数的计算。 利用空间

15、换时间，多用存储空间换取快速。 缺点：不能直接计算出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、公钥密码学的