公钥密码概述.pptVIP

公钥密码体制 量子密码研究室 王 滨 2005.4.12 * 上课安排 公钥密码体制的概念、思想和工作方式 Diffie-Hellman密钥交换算法 RSA 算法 EIgamal公钥算法 ECC算法 * 背景 在拥有大量用户的通信网络，若想让两两用户都能进行必威体育官网网址通信，即要求 1 任意一对用户共享一个会话密钥 2 不同的用户对共享的会话密钥不相同 对于分配中心，N个用户则需要分配CN2个会话密钥，大量的数据存储和分配是一件很麻烦的事，在计算机网络环境下显的尤为突出。另外传统密码不易实现数字签名，也进一步限制了其发展。 * 公开密钥算法的提出 公钥密码学是1976年由Diffie和Hellman在其“密码学新方向”一文中提出的，见文献： W.Diffie and M.E.Hellman, New Directrions in Cryptography， IEEE Transaction on Information Theory, V.IT-22.No.6, Nov 1976, PP.644-654 * 公开密钥算法 公开密钥算法是非对称算法，即密钥分为公钥和私钥，因此称双密钥体制 双钥体制的公钥可以公开，因此也称公钥算法 公钥算法的出现，给密码的发展开辟了新的方向。公钥算法虽然已经历了20多年的发展，但仍具有强劲的发展势头，在鉴别系统和密钥交换等安全技术领域起着关键的作用 * 加密与解密由不同的密钥完成 加密： 解密： 知道加密算法，从加密密钥得到解密密钥在计算上是不可行的 两个密钥中任何一个都可以作为加密而另一个用作解密（不是必须的） 公开密钥算法的基本要求 * 基于公开密钥的加密过程 * 用公钥密码实现必威体育官网网址 用户拥有自己的密钥对 KU,KR 公钥 KU公开，私钥KR必威体育官网网址 * 基于公开密钥的鉴别过程 * 用公钥密码实现鉴别 条件：两个密钥中任何一个都可以用作加密而另外一个用作解密 鉴别： 鉴别＋必威体育官网网址 * 公开密钥算法 公钥算法的种类很多，具有代表性的三种密码： 基于整数分解难题（IFP）的算法体制 基于离散对数难题（DLP）算法体制 基于椭圆曲线离散对数难题（ECDLP）的算法体制 * Diffie-Hellman密钥交换算法 * Diffie-Hellman公钥技术 Diffie-Hellman公钥密码技术又称为Diffie-Hellman密码交换协议,它是Whitefield Diffie和Martin Hellman在1976年提出的,是至今仍然流行的一种公 钥技术. 见教材P143 * D-H密钥交换协议背景密钥分配 人工手动分配密钥: 问题 效率低 成本高 每个用户要存储与所有用户通信的密钥 安全性差 机器自动分配密钥: 要求 任何两个用户能独立计算他们之间的秘密密钥 传输量小 存储量小 任何一个 或多个 用户不能计算出其他用户之间的秘密密钥 * 单向陷门函数函数 满足下列条件的函数f： 1 给定x，计算y f x 是容易的 2 给定y, 计算x使y f x 是困难的 3 存在z，已知z 时, 对给定的任何y，若相应的x存在，则计算x使y f x 是容易的 所谓计算x f-1 Y 困难是指计算上相当复杂，已无实际意义 * 单向陷门函数说明 仅满足 1 、 2 两条的称为单向函数；第 3 条称为陷门性，z 称为陷门信息 当用陷门函数f作为加密函数时，可将f公开，这相当于公开加密密钥，此时加密密钥便称为公开密钥，记为Pk f函数的设计者将z必威体育官网网址，用作解密密钥，此时z称为秘密钥匙，记为Sk。由于设计者拥有Sk，他自然可以解出x f-1 y 单向陷门函数的第 2 条性质表明窃听者由截获的密文y f x 推测x是不可行的 * Diffie-Hellman密钥交换算法 Diffie和Hellman在其里程碑意义的文章中，虽然给出了密码的思想，但是没有给出真正意义上的公钥密码实例，也既没能找出一个真正带陷门的单向函数 然而，他们给出单向函数的实例，并且基于此提出Diffie-Hellman密钥交换算法 * Diffie-Hellman密钥交换算法的原理 基于有限域中计算离散对数的困难性问题之上：设F为有限域，g∈F是F的乘法群 F* F\ 0 ，并且对任意正整数x，计算gx是容易的；但是已知g和y求x使y gx，是计算上几乎不可能的 * Diffie-Hellman密钥交换协议描述 Alice和Bob协商好一个大素数p，和大的整数g，1 g p，g最好是FP中的本原元，即FP*＝ p和g无须必威体育官网网址，可为网络上的所有用户共享 * Diffie-Hellman密钥交换协议描述 当Alice和Bob要进行必威体育官网网址通信时，他们可以按如下步骤来做： 1