《RSA公钥密码》课件.docx

《RSA公钥密码》PPT课件.ppt[模版仅供参考，切勿通篇使用]1 公钥密码概述Diffie Hellman密钥交换协议背包体制简介RSA密码体制 第四章公钥密码技术 2 RSA公钥密码算法 主要内容 RSA公钥密码算法 RSA公钥密码的实现 重点 RSA算法 脱密的快速实现 素数生成算法 难点 素数生成算法 3 RSA体制 由Rivest Shamir Adleman于1978年首次发表 最容易理解和实现的公钥算法 经受住了多年深入的攻击 其理论基础是一种特殊的可逆模幂运算 其安全性基于分解大整数的困难性 RSA既可用于加密 又可用于数字签名 已得到广泛采用 RSA已被许多标准化组织 如ISO ITU IETF和SWIFT等 接纳 目前许多国家标准仍采用RSA或它的变型 4 假设m为要传送的报文 1 任产生两个素数p与q 使得n pq m2 随机选择数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不同余 记为 定理 当且仅当m a b 定理 欧拉定理 对任意有 推论 费尔马定理 若p为素数 则 其中 2 工作原理 6 RSA算法论证 E和D的可逆性 要证明 D E M M M Cd Me d Medmodn 因为ed 1mod n 这说明ed t n 1 其中t为某整数 所以 Med Mt n 1modn 因此要证明Med Mmodn 只需证明Mt n 1 Mmodn 7 RSA算法论证 在 M n 1的情况下 根据数论 Euler定理 Mt n 1modn 于是有 Mt n 1 Mmodn 8 RSA算法论证 在 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 矛盾 9 RSA算法论证 10 RSA算法论证 不妨设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算法论证 13 RSA算法论证 加密和解密运算的可交换性 D E M Me d Med Md e E D M modn 所以 RSA密码可同时确保数据的秘密性和数据的真实性 14 RSA算法论证 加解密算法的有效性 RSA密码的加解密运算是模幂运算 有比较有效的算法 15 RSA算法论证 在计算上由公开密钥不能求出解密钥 小合数的因子分解是容易的 然而大合数的因子分解却是十分困难的 关于大合数的因子分解的时间复杂度下限目前尚没有一般的结果 迄今为止的各种因子分解算法提示人们这一时间下限将不低于O EXP lnNlnlnN 1 2 根据这一结论 只要合数足够大 进行因子分解是相当困难的 16 RSA算法论证 假设截获密文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进行因子分解的方法外 是否还有别的更简捷的破译方法 18 3 例子 假设RSA体制中p 3 q 11 取加密密钥e 7 1 求脱密密钥d 2 写出相应的加密算法和脱密算法 3 对明文m 8加密 7dmod20 1 因e 7与互素 故可解模方程 即 解 此时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 素数判定是要解决的首要问题 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 如利用伪随机数产生器 随机选择一个整数a n 执行诸如Miller Rabin等概率素数测试 若n未通过测试 则转到第一步 若n通过足够多次的测试 则接受n 否则转向第2步 28 在实际使用中 通过首先检验待检测的随机数是否是小素数 例如所有小于1000的素数 的倍数 待检测通过后再执行Rabin检测 Miller Rabin素数检测算法 已经作为标准的检测算法列入IEEEP1363的附录和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 ABmodn 因为n很大 取模运算困难 采取一个小的模R 回避大模数的计算 利用空间换时间 多用存储空间换取快速 缺点 不能直接计算出Y ABmodn 只能计算出中间值ABR 1modn 因此还需要预处理和调整运算 一次性计算Y ABmodn并不划算 适合 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年代中期才被发现。