网络信息安全第九章.ppt

2020 2 13 现代密码学理论与实践 09 1 32 网络信息安全Chapter9Public keyCryptographyandRSA 2020 2 13 现代密码学理论与实践 09 2 32 本章要点 非对称密码是一种密码体制 其加密算法和解密算法使用不同的密钥 一个是公钥 一个是私钥 非对称密码也称为公钥密码 非对称密码用两个密钥中的一个以及加密算法将明文转换为密文 用另一个密钥以及解密算法从密文恢复出明文 非对称密码可以用来保密 认证或者两者兼而有之 应用最广泛的公钥密码体制是RSA 破解RSA的困难 是基于分解大合数的素因子的困难 2020 2 13 现代密码学理论与实践 09 3 32 9 1公开密钥密码体制的基本原理 对称密码体制的问题加密能力与解密能力是捆绑在一起的密钥更换 传递和交换需要可靠信道 密钥分发困难如有N用户 则需要C N N 1 2个密钥 n 1000时 C 1000 2 500000 密钥管理困难无法满足不相识的人之间通信的保密要求不能实现数字签名非对称密码体制的基本特点加密能力与解密能力是分开的密钥分发简单需要保存的密钥量大大减少 N个用户只需要N个密钥可满足不相识的人之间保密通信可以实现数字签名 2020 2 13 现代密码学理论与实践 09 4 32 公开密钥密码体制 公钥算法依赖于一个加密密钥和一个与之相关的不同的解密密钥 算法有如下特点 仅根据密码算法和加密密钥来确定解密密钥在计算上是不可行的两个密钥的任何一个都可用来加密 另一个用来解密公钥密码体制的组成明文 算法的输入 可读信息或数据加密算法 对明文进行各种转换公钥和私钥 算法的输入 分别用于加密和解密密文 算法的输出 依赖于明文和密钥解密算法 根据密文和密钥 还原明文 2020 2 13 现代密码学理论与实践 09 5 32 公钥算法的主要步骤 每个用户产生密钥 用来加密和解密消息每个用户将其中一个密钥 公钥 存于公开的寄存器或其他可访问的文件中 另一密钥私有 每个用户可以拥有若干其他用户的公钥若Bob要发消息给Alice 则要用Alice的公钥对消息加密Alice收到消息后 用其私钥对消息解密 由于只有Alice知道其自身的私钥 所以其他的接收者均不能解密消息需要认证时示证方用自己的私钥加密消息 签名 验证方用示证方的公钥解密消息 验证 如果结果证实公钥与示证方的私钥相吻合 则可以确认示证方确为合法的用户 认证 加密和认证可以结合起来 同时实现保密性和认证 2020 2 13 现代密码学理论与实践 09 6 32 公开密钥加密过程 2020 2 13 现代密码学理论与实践 09 7 32 公开密钥认证过程 2020 2 13 现代密码学理论与实践 09 8 32 常规和公开密钥加密的重要特征 2020 2 13 现代密码学理论与实践 09 9 32 公开密钥密码系统 保密性 C KUb M M KRb C 2020 2 13 现代密码学理论与实践 09 10 32 公开密钥密码系统 认证 S KRa M M KUa S 2020 2 13 现代密码学理论与实践 09 11 32 公开密钥密码系统 保密和认证 C KRa KUb M M KRb KUa C 2020 2 13 现代密码学理论与实践 09 12 32 公钥密码体制的应用 加密 解密 发送方用接收方的公钥对消息加密数字签名 发送方用其私钥对消息签名 可以对整体消息签名或对消息的摘要签名密钥交换 通信双方交换会话密钥 2020 2 13 现代密码学理论与实践 09 13 32 产生一对密钥 公钥ke和私钥kd 在计算上是容易的不难计算C E ke m 和m D kd C 知道ke 计算kd不可行不知道kd 即使知道ke E D及C 计算m也不可行对明文m E ke m 有定义 且D kd E ke m m对密文c D kd C 有定义 且E ke D kd C C加密变换和解密变换可以互换顺序 即D E m E D m 1976年 WhitfieldDiffie和MartinHellman提出这样的设想 每个用户A有一加密密钥ka 不同于解密密钥ka 可将加密密钥ka公开 ka 保密 要求ka的公开不影响ka 的安全 若B要向A秘密发送明文m 可查A的公开密钥ka 加密得密文C Eka m A收到C后用只有A才拥有的解密密钥ka 对C进行解密得m Dka C 实用方案的发展依赖于单向陷井函数 对公开密钥密码编码系统的要求 2020 2 13 现代密码学理论与实践 09 14 32 WhitfieldDiffieandMartinHellman WHITFIELDDIFFIE MARTINHELLMAN Diffie W Hellman M 1976 Newdirectionsincryptography IEEETransactionsonInformationTheory22 6 644 654 15 2020 2 13 现代密码学理论与实践 09 16 32 公钥密码的分析 公钥密码易受穷举攻击 解决方法是使用长密钥 同时为了便于实现加密和解密 又希望密钥足够短 目前仅限于密钥管理和签名 找出一种从给定的公钥计算出私钥是第二种攻击方法 尚未在数学上证明对一特定公钥算法这种攻击是不可行的 因此包括RSA在内的任何算法都是值得怀疑的 穷举消息攻击是第三种攻击形式 攻击者用公钥对所有可能的消息加密 并与传送的密文匹配 从而解密任何消息 抵抗的方法是在要发送的消息后附加随机数 2020 2 13 现代密码学理论与实践 09 17 32 9 2RSA算法 概述1977年 Rivest Shamir Adleman提出的非对称密码体制 是基于大合数的质因子分解问题的困难性 1994年4月一个小组通过Internet合作 8个月时间成功分解129位的数 大约428比特 1999年分解155位合数 最新的记录是2005年5月分解200位十进制数 RSA专利于2000年9月20日到期 2020 2 13 现代密码学理论与实践 09 18 32 9 2RSA算法 概述RSA体制是一种分组密码体制 其明文和密文均是0至某n 1之间的整数 通常n的大小为1024位二进制或309位十进制数 也就是说n小于21024 2020 2 13 现代密码学理论与实践 09 19 32 R S ARonRivest AdiShamir LenAdleman LefttoRight RonRivest AdiShamir LenAdleman 20 21 2020 2 13 现代密码学理论与实践 09 22 32 算法流程随机选择两个秘密大素数p和q 计算公开模数n p q 计算秘密的欧拉指数函数 n p 1 q 1 选择一个与 n 互素的数 作为e或d 用Euclid算法计算模 n 的乘法逆元素 即根据edmod n 1 求d或e 加密 C Memodn解密 M Cdmodn Memodn dmodn M这里 n 为欧拉函数 即集合 1 2 n 1 中与n互素的数的个数 RSA密码体制基本原理 2020 2 13 现代密码学理论与实践 09 23 32 2020 2 13 现代密码学理论与实践 09 24 32 2020 2 13 现代密码学理论与实践 09 25 32 一个例子 p 17 q 11 e 7 M 88求公钥KU和私钥KR分别为多少 加密计算后所得到的C为多少 并验证解密运算后 是否能恢复出明文M 2020 2 13 现代密码学理论与实践 09 26 32 一个例子 p 17 q 11 n pq 17x11 187 n p 1 q 1 16x10 160选择e 7 gcd 7 160 1 23x7 161 所以d 23公钥KU 7 187 私钥KR 23 187 M 88加密计算C 887mod187887mod187 884mod187 x882mod187 x881mod187 mod187881mod187 88882mod187 7744mod187 77884mod187 59969536mod187 132887mod187 88x77x132 mod187 894432mod187 11解密计算M 1123mod187 88 2020 2 13 现代密码学理论与实践 09 27 32 RSA密码体制基本原理 RSA算法满足公开密钥加密的要求 必须符合下列条件 有可能找到e d n的值 使得对所有M n有Medmodn M对于所有M n的值 要计算Me和Cd是相对容易的在给定e和n时 计算d是不可行的几个关系 n pq p q p 1 q 1 p qareprimeedmod n 1 ed k n 1 即ed 1mod n d e 1mod n 2020 2 13 现代密码学理论与实践 09 28 32 定理 给定edmod n 1 m 0 n 1 gcd m n 1 则 memodn dmodn medmodn m证明 edmod n 1 ed k n 1 对某些整数k medmodn mk n 1modn m mk n modn modn mk n modn m n modn kmodn 1kmodn 1 medmodn m 1 modn m RSA密码体制基本原理 2020 2 13 现代密码学理论与实践 09 29 32 RSA密码体制基本原理 RSA方案概述primep q 私有 选择n pq 公开 计算出e gcd n e 1 1 e n 公开 选择d e 1mod n 私有 计算出RSA实现方面的考虑加密与解密模运算特性之一 amodn x bmodn modn axb modn指数运算的效率问题 2020 2 13 现代密码学理论与实践 09 30 32 计算abmodn的算法和快速取模指数算法 2020 2 13 现代密码学理论与实践 09 31 32 确定两个素数p和q 选择e或d并计算另外一个检验素数随机选择一个奇数 如使用伪随机数产生器随机选一个整数a n完成随机素数性检验 如果n没有通过检验 则另选n如果n通过了足够多次的检验 则接受n 否则另选例 p 5 q 7 n 35 n 24选d 11 则e inv 11 24 11 M 2C memodn 211mod35 18M Cdmodn 1811mod35 2 密钥的产生和检验素数 2020 2 13 现代密码学理论与实践 09 32 32 RSA的安全性 例 p 53 q 61 n pq 3233 n 52x60 3120令d 791 则e 71令m RENAISSANCE即m 170413000818180013020426170471mod3233 3106 C 310601000931269119842927RSA的安全性有三种可能的对RSA的攻击方法强行攻击 尝试所有可能的密钥数学攻击 对两个素数乘积的因子分解 FAC问题 计时攻击 依赖于解密算法的运行时间RSA的安全性问题依赖于大合数的素因子分解 即factorizationproblem FAC FAC的计算复杂性为T exp ln n ln ln n 1 2 同DLP问题 2020 2 13 现代密码学理论与实践 09 33 32 p和q应满足下列约束条件 P和q的长度应仅相差几位 p和q都应约在1075到10100之间 p 1 和 q 1 都应有一个大的素因子GCD p 1 q 1 应该较小另外 已经证明 若e n且d n1 4 则d很容易确定 2020 2 13 现代密码学理论与实践 09 34 32 针对RSA的计时攻击 计时攻击类似通过观察他人转动保险柜拨号盘的时间长短来猜测密码可能的解决办法不变的幂运行时间 可能会降低性能在求幂运算中加入随机延时隐蔽 在执行幂运算之前先将密文乘上一个随机数RSA数据安全算法 用私钥实现操作M Cdmodn的过程如下产生0 n 1之间的秘密随机数r计算C C re modn e是公开的指数计算M C dmodn计算M M r 1modn 其中r 1是r模n的乘法逆元 根据redmodn r 可以证明结论是正确的 2020 2 13 现代密码学理论与实践 09 35 32 几种不同复杂性的算法的代价