[理学]03-公钥密码体系.ppt

第3讲公钥密码体制 王志伟计算机学院信息安全系zhwwang 2020 2 15 南京邮电大学 2 本讲内容 公钥密码体制的设计原理 1 Diffie Hellman密钥交换 2 RSA 椭圆曲线密码体制 3 公钥密码体制的应用 4 2020 2 15 南京邮电大学 3 1公钥密码体制 公钥密码体制的引入公钥密码体制数学基础 在对称密码体制中 消息的发送方和接收方必须在密文传输之前通过安全信道进行密钥传输 而实际的传输信道安全性并不理想 所以密钥在传输过程中被暴露的风险很大 公钥密码的最大优点在于针对密钥管理方法的改进 在公钥密码系统中 加密密钥是公开的 任何人都可以采用这些公开的加密密钥对消息进行加密 同时只有正确的接收方才能够用自己所保管的解密密钥对密文进行解密 这些解密密钥需要妥善保存 提供单向函数的数学难题 NP完全问题 Non deterministicPolynomialCOMPLETE问题 对于一个函数f x 如果对于其定义域上的任意x f x 都容易计算 同时 对于其值域中几乎所有的取值y 计算其逆函数f 1 y 都是不可行的 大整数分解问题离散对数问题椭圆曲线离散对数问题 2020 2 15 南京邮电大学 4 1公钥密码体制 明文 私钥d 公钥e 明文 密文 加密器Ek 解密器Dk 2020 2 15 南京邮电大学 5 1公钥密码体制 公钥密码体制的应用领域 消息的机密性 密钥分配利用通信双方已有的公钥 私钥对计算出一个公有的密钥 用于通信加密 Diffie Hellman 认证 消息的来源和消息的完整性 参见课本P96页图7 1 参见课本P96页图7 2 双重加解密同时实现认证和机密性 具体参见课本P97页图7 3 2020 2 15 南京邮电大学 6 1 1公钥算法 Diffie Hellman密钥分配协议第一个公开发表的公钥密码算法只用于密钥分配并不能完成信息加解密RSA是目前为止最为成功的非对称密码算法第一个比较完善的公钥系统Rivest ShamirandAdleman 2020 2 15 南京邮电大学 7 本讲内容 公钥密码体制的设计原理 1 Diffie Hellman密钥交换 2 RSA 椭圆曲线密码体制 3 公钥密码体制的应用 4 2020 2 15 南京邮电大学 8 2Diffie Hellman Diffie Hellman是一个简单的公钥算法 用于实现密钥交换 这个协议是的通信的双方利用基于离散对数问题的公钥算法建立秘密钥 这个协议是安全的 仅当通信双方的真实性能够得到保证 2020 2 15 南京邮电大学 9 2Diffie Hellman 公开 g和n秘密 Alice的指数a Bob的指数b Alice a Bob b gamodn gbmodn Alice计算 gb a gba gabmodnBob计算 ga b gabmodn他们可以使用K gabmodn做为对称密钥 2020 2 15 南京邮电大学 10 2 1举例 选定n 97 g 5Alice选择自己的私有密钥a 36 则她的公钥是X 536mod97 50Bob选择自己的私有密钥b 58 则他的公钥是Y 558mod97 44用户Alice和Bob互换公钥后 都可以计算出Alice方 k Yamod97 4436mod97 75Bob方 k Xbmod97 5058mod97 75 2020 2 15 南京邮电大学 11 本讲内容 公钥密码体制的设计原理 1 Diffie Hellman密钥交换 2 RSA 椭圆曲线密码体制 3 公钥密码体制的应用 4 2020 2 15 南京邮电大学 12 3RSA密码体制 安全性是建立在 大数分解和素性检测 这个数论难题的基础上 既将两个大素数相乘在计算上容易实现 而将该乘积分解的计算量相当大虽然安全性没有能得到理论证明 但20多年的实践证明其是安全的 2020 2 15 南京邮电大学 13 3 1RSA算法的密钥 选取两个大素数p与q 然后算出n pq n p 1 q 1 再选取一个正整数e 使之满足 e n 1 1 e n 其中 表示求最大公约数 再求出正整数d 使之满足1 d n 且使d e 1mod n 然后用 n e 作为公钥 n d 作为私钥 2020 2 15 南京邮电大学 14 3 2RSA算法的加解密 加密C Memodn解密M Cdmodn 2020 2 15 南京邮电大学 15 3 3举例 选取两个 大 素数p 11 q 3n p q 33 n p 1 q 1 20选择e 3 因为3与20互质再求出正整数d 使之满足1 d n 且使d 3 1mod20所以d 7公钥 n e 33 3 私钥 n d 33 7 2020 2 15 南京邮电大学 16 3 3举例 公钥 n e 33 3 私钥 n d 33 7 假设明文是M 8密文是C Memodn 83 512 17mod33明文是M Cdmodn 177 410 338 673 12 434 505 33 8 8mod33 2020 2 15 南京邮电大学 17 3 4文本加密 令26个字母对应0 25设明文为M publicE p 153 9mod33E u 203 14mod33E b 13 1mod33E l 113 11mod33E i 83 17mod33E c 23 8mod33则c E M 091401111728 joblri 2020 2 15 南京邮电大学 18 3 5文本解密 收到密文后用d 7进行解密D j 097 15mod33 即明文pD o 147 20mod33 即明文uD b 017 1mod33 即明文bD l 117 11mod33 即明文lD r 177 8mod33 即明文iD i 087 2mod33 即明文c 2020 2 15 南京邮电大学 19 RSA算法中的计算问题 求一个整数的整数次幂如果按其含义直接计算 则中间结果运算量非常大如何提高加 解密运算中指数运算的有效性 利用模运算的性质重复对每个部分结果做平方 参见课本P99 100页不作要求 2020 2 15 南京邮电大学 20 RSA讨论 RSA算法是第一个能同时用于加密和数字签名的算法 也易于理解和操作 RSA是被研究得最广泛的公钥算法 从提出到现在已近二十年 经历了各种攻击的考验 逐渐为人们接受 普遍认为是目前最优秀的公钥方案之一 RSA的安全性依赖于大数的因子分解 但并没有从理论上证明破译RSA的难度与大数分解难度等价 即RSA的重大缺陷是无法从理论上把握它的保密性能如何 而且密码学界多数人士倾向于因子分解不是NPC问题 2020 2 15 南京邮电大学 21 RSA算法分析 R L Rivest等人证明 攻破RSA加密算法的计算复杂度等同于分解大数n的计算复杂度 1994年 一个小组利用因特网上1600台计算机 经过8个月的计算 攻破了公钥长度为129位十进制数 约428比特 的RSA 这种攻击意义不大 现在通常认为 采用1024比特密钥长度 约300位十进制数 是比较安全的 2020 2 15 南京邮电大学 22 RSA缺点 A 产生密钥很麻烦 受到素数产生技术的限制 因而难以做到一次一密 B 分组长度太大 为保证安全性 n至少也要600bits以上 使运算代价很高 尤其是速度较慢 较对称密码算法慢几个数量级 随着大数分解技术的发展 这个长度还在增加 不利于数据格式的标准化 目前 SET SecureElectronicTransaction 协议中要求CA采用2048比特长的密钥 其他实体使用1024比特的密钥 椭圆曲线算法 DES和RSA性能比较 同等强度 3 6椭圆曲线算法 2020 2 15 南京邮电大学 24 1985年 N Koblitz和V Miller分别独立提出了椭圆曲线密码体制 ECC 其依据就是定义在椭圆曲线点群上的离散对数问题得难解性 椭圆曲线算法可以用来开发许多椭圆曲线密码方案 包括密钥交换 加密和数字签名 ECC和RSA性能比较 与同等安全性的RSA相比 由于ECC使用的密钥更短 计算速度更快 2020 2 15 南京邮电大学 26 本讲内容 公钥密码体制的设计原理 1 Diffie Hellman密钥交换 2 RSA 椭圆曲线密码体制 3 公钥密码体制的应用 4 2020 2 15 南京邮电大学 27 公钥与以前的密码学不同之处 传统的密码基于混淆和发散 使用替换和置换技术公钥基于数学函数的求解复杂度非对称的两个密钥应用范围更广 消息的保密性 密钥的分配和认证领域 2020 2 15 南京邮电大学 28 公钥vs私钥 公钥体制大大简化了复杂的密钥分配管理问题公钥要比私钥慢得多慢约1000倍公钥用于认证 数字签名 身份识别等 和密钥管理私钥用于信息加密 2020 2 15 南京邮电大学 29 对于公钥的误解一 公钥密码比传统密码更安全 不是 任何加密方法安全性依赖于密钥的长度和破译密文所需要的计算量 2020 2 15 南京邮电大学 30 对于公钥的误解二 公钥是一种通用的方法 传统密码已经过时 不是 公钥的计算量大 目前不能取代传统密码 公钥密码学仅限于用在密钥管理和签名此类应用上 这几乎是被广泛接受的事实 2020 2 15 南京邮电大学 31 对于公钥的误解三 传统密码中与密钥分配中心KDC的握手是一件麻烦的事情公钥的密钥管理非常简单 不 也需要某种形式的协议 该协议一般包含一个中心代理 处理并不比传统密码中的那些工程更简单 2020 2 15 南京邮电大学 32 公钥算法应用 加密 2020 2 15 南京邮电大学 33 用公钥密码实现保密 用户拥有自己的密钥对 KU KR 公钥KU公开 私钥KR保密A Y