二信息保密技术公开密钥密码学PPT课件

1 第二章公开密钥密码学 2 1公开密钥密码系统的原理2 2RSA算法2 3密钥管理2 4Diffie Hellman密钥交换算法 2 2 1公开密钥密码系统的原理 常规密钥密码体制存在的问题 密钥分配问题层次密钥结构未根本解决问题EKs M EKm Ks 签名验证问题Diffie和Hellman在1976年取得了一项惊人的突破 他们研究得到一种解决方法 并且这个方法与过去4000年间的所有密码编码学方法都截然不同 3 2 1 1公开密钥密码系统公开密钥算法要求每个参与方拥有用一对密钥 一个公开 另一个保密 用一个密钥进行加密 而用另一个不同但是有关的密钥进行解密 这些算法有以下重要特性 1 仅仅知道密码算法和加密密钥而要确定解密密钥 在计算上是不可能的 另外 某些算法 比如RSA 还具有下列特性 2 两个相关密钥中任何一个都可以用作加密而让另外一个用作解密 4 公开密钥密码体制的特点 公开密钥算法基于数学函数而不是替代和置换 公开密钥密码体制中的密钥是非对称的 它用到两个不同的密钥 这对于保密通信 密钥分配和鉴别等领域都有着深远的影响 公开密钥密码成功地解决了计算机网络安全的身份鉴别 数字签名等问题 推动了包括电子商务在内的一大批网络应用的不断深入发展 使密钥管理变得容易了 加密和解密较常规密钥密码体制慢 5 需要澄清得几个问题 公开密钥加密方法要比传统的加密方法更加安全 事实上 任何加密方案的安全程度都依赖于密钥的长度和破译密码所包含的工作量 公开密钥密码体制是一种通用技术 它已使传统密码体制成为陈旧 其实正相反 由于当前公开密钥加密在计算上的巨大开销 在可预见的将来常规加密并不会被抛弃 公开密钥的密钥分配实现起来很简单 事实上仍需要某种形式的协议 6 公开密钥加密过程中的重要步骤如下 1 产生密2 公开密钥3 加密用B的公开密钥加密这个报文c EKUB p 4 解密用自己的私有密钥 保密密钥 解密报文p DKRB c 7 公开密钥用于加密 发送方A 接收方B 8 公开密钥用于鉴别 1 如果A想给B发送一个签名报文 他就用自己的私有 保密 密钥加密这个报文 2 B收到这个报文后就用A的公开密钥鉴别该报文 接收方B 发送方A 9 密钥产生 本地产生一对密钥密钥控制 私钥保密 公钥公开密钥更新 产生 公开公钥取代旧公钥区分常规密钥加密和公开密钥加密这两个体制 常规加密中使用的密钥称为秘密密钥 secretkey 公开密钥加密中使用的两个密钥则称为公开密钥 publickey 和私有密钥 privatekey 符号约定 Kab Km Ks KUa KRa加密 EKab P EKUa P EKRa P 签名 解密 DKab C DKRa C DKUa C 鉴别 10 用公开密钥进行加密的方法 Y EKUb X X DKRb Y 11 用公开密钥进行鉴别的方法 A给B发送报文 传输之前用A的私有密钥对它进行加密 签名 B用A的公开密钥将这个报文解密 鉴别 Y EKRa X X DKUa Y 12 该报文是用A的私有密钥加密的 只有A才可能发送了这个报文 整个的加密报文就可以当作一个数字签名 得不到A的私有密钥就不可能对报文进行改动 因此报文的发送者和数据的完整性同时得到了证实 13 用公开密钥进行加密和鉴别的方法 Z EKUb EKRa x X DKUa DKRb Z 14 2 1 2公开密钥密码系统的应用1 加密 解密2 数字签名3 密钥交换交换会话密钥不同算法的应用范围 算法加密 解密数字签名密钥交换RSA是是是Diffie Hellman否否是DSS否是否 15 2 1 3常规加密和公开密钥加密的比较 Return 16 2 2RSA算法 公开密钥密码系统中最常用的是RSA算法 Rivest Shamir Adleman RSA是分组密码体制1 生成密钥 首先任意选取两个大素数p q 使 n pqn称为模则欧拉函数 n 为 n p 1 q 1 然后 任意选取一个与 n 互素的小整数e作为公开的加密指数 由e求出秘密的解密指数d de k n 1 1mod n 17 公钥 n e 私钥 n d 因子p q与私钥一起保存或销毁 2 RSA加密 解密算法RSA加密 将明文数字化并分组 使明文分组m满足 0 m n 对每块进行加密变换 c EKU m memodn解密过程 m DKR c cdmodn在RSA体制下 加密算法和解密算法之间 有下面的关系成立 DKR EKU m me d mmodnEKU DKR m md e mmodn 18 3 证明由费马定理 m p 1 1modp将它们两边取k q 1 次幂 并乘以m得 左边 mk p 1 q 1 1 mk n 1 med右边 m即 med m modp 同样 将p换成q也得相同的结果 即 med m modq 所以对于n pq有med m modpq m modn 19 例子 1 设计密钥 设素数p 3 q 17 计算n n pq 3 17 51 计算 n n p 1 q 1 2 16 32选取e 13 e与 n 32互素 因此公开的加密密钥是 n 51 e 13 然后根据下式求d 先试一下 p 1 和 q 1 的最大公约数k在这个例子中 k 2 所以 解密指数d 2 32 1 13 65 13 5 解密密钥d 5 n 51 20 2 甲方把转换成等效数字的明文 2 发送给乙方 甲方用公开的加密密钥e n将明文加密成密文c c memodn 213mod51 8192mod51 32 乙方用自己秘密保存的解密密钥d n将密文转换成明文 m cdmodn 325mod51 322 322 32mod51 1024 1024 32mod51 4 4 32mod51 512mod51 2 21 1977年RSA的三个发明人在 科学美国人 杂志的数学游戏专栏留下了一个129位的十进制数 426bit 密钥 悬赏 100 估计破译时间为4亿亿年后 1994年Atkins等人动用网上的1600台计算机 耗时8个月 成功地破译了该密码 1999年一个国际密码研究小组在RSA公司举办的RSA密钥竞赛中荣获冠军 该小组用7个月时间 使用世界各地11个地点292台计算机 其中160台SGI和SUN工作站及120台PIIPC机 确定了生成单个512位RSA密钥所用的两个素数 512bit154位10进制数不够安全768bit231位10进制数个人应用1024bit308位10进制数商业应用2048bit616位10进制数重要场合 Return 22 2 3密钥管理 公开密钥加密的用途实际上包括两个不同的方面 2 3 1公开密钥的分配2 3 2用公开密钥分配秘密密钥 Return 23 2 3 1公开密钥的分配 分配公开密钥的技术方案有多种 几乎所有这些方案都可以归为下列几类 公开宣布公开可以得到的目录公开密钥管理机构公开密钥证书 Return 24 公开密钥的公开宣布 宣布方法 1 一一发送 2 广播发送 3 利用公开论坛发布 新闻组 邮件组 优点 方便 问题 伪造公开告示 Return 25 公开可以得到的目录 由一个受信任的系统或组织维持一个公开可以得到的公开密钥动态目录 1 管理机构为每个参与者维护一个目录项 名字 公开密钥 2 管理机构定期发表这个目录或者对目录进行的更新 例如 可以出版一个很像电话号码簿的打印版本 或者可以在一份发行量很大的报纸上列出更新的内容 26 3 每个参与者在目录管理机构登记一个公开密钥 登记必须面对面进行 或者通过某种安全的经过认证的通信方式进行 4 参与者可以随时用新的密钥更换原来的密钥 5 参与者可能以电子方式访问目录 为了这个目的 从管理机构到参与者的通信必须是安全的 经过鉴别的通信 这个方案明显比各个参与者单独进行公开告示更加安全 Return 27 公开密钥管理机构 假定 1 中心管理机构维护一个所有参与者的公开密钥动态目录 2 每个参与者都可靠地知道管理机构的一个公开密钥 而只有管理机构才知道对应的私有密钥 Return A B 28 公开密钥证书 证书方案 每个证书包含一个公开密钥以及其他信息 它由一个证书管理机构制作 并发给具有相匹配的私有密钥的参与者 一个参与者通过传输它的证书将其密钥信息传送给另一个参与者 其他参与者可以验证证书是否是管理机构制作的 证书方案要求 1 证书可阅读2 证书可验证 非伪造品 时效性 3 证书制作和更新在证书管理机构 29 证书方案 每个参与者都向证书管理机构提出申请 提供公开密钥并请求颁发证书 申请必须是面对面的或者是通过某种安全的经过鉴别的方式进行的 对于参与者A来说 管理机构提供如下形式的证书 CA EKRauth T IDA KUa 30 A可以将证书传递给任何其他的参与者 后者以如下方式对证书进行验证 DKUauth CA DKUauth EKRauth T IDA KUa T IDA KUa 接受者使用管理机构的公开密钥KUauth将证书解密 因为这个证书只能以管理机构的公开密钥进行解读 这就验证了证书的确来自证书管理机构 时间戳T用于验证证书的时效性 时间戳防止下列情形的出现 A的私有密钥被敌对方获知 A产生一个新的私有 公开密钥对并向证书管理机构申请一个新的证书 同时敌对方将老的证书重放给B 如果B用被泄露的私有密钥对应的公开密钥加密报文 敌对方就可以解读这些报文 时间戳起的作用就像一个失效日期 如果一个证书过分陈旧 就可以认为它已经过期 Return 31 2 3 2用公开密钥分配秘密密钥 一旦公开密钥已经分配或者已经可以得到 就可以进行安全通信 但很少有用户完全用公开密钥加密进行通信 因为公开密钥加密速度慢 合理的做法是将公开密钥加密当作一个分配常规加密所用的秘密密钥的工具 1 简单的秘密密钥分配 32 如果A希望和B通信 则使用下列步骤 1 A产生一个私有 公开密钥对 KUa KRa 并给B传输一个报文 其中包含KUa和A的一个标识符IDA 2 B产生一个秘密密钥Ks 并将其用A的公开密钥加密后传输给A 3 A计算DKRa EKUa Ks 来恢复这个秘密密钥 因为只有A可以解密这个报文 所以只有A和B才会知道Ks 4 A弃用KUa和KRa B弃用KUa A和B现在就可以使用常规加密和会话密钥进行安全通信 信息交互完成以后 A和B都丢弃Ks 在通信之前不存在密钥 而在通信完成以后也不存在密钥 因而密钥泄露的危险被减小到最低程度 33 问题 此协议容易受到主动攻击 如果攻击方C控制了中间的通信信道 那么C就可以用下列方式破坏通信而不被发觉 34 2 具有保密和鉴别能力的秘密密钥分配下图给出了一种防止被动和主动两种攻击的防护方法 出发点是假定A和B己经通过前边描述的方案之一交换了公开密钥 A B 35 3 一个混合方案另一种使用公开密钥加密分配秘密密钥的方式是IBM主机使用的混合方法 这种方案保留了密钥分配中心 KDC 这个KDC与每个用户共享一个秘密主密钥Km并用这个主密钥加密分配秘密的会话密钥Ks 公开密钥方案被用来分配主密钥 使用这种三层分配方式的理由如下 性能 在许多应用中 会话密钥变化频繁 用公开密钥加密分配会话密钥会使系统的总体性能下降 使用三层结构 公开密钥加密只用来偶尔更新用户和KDC之间的主密钥 向后兼容性 混合方案容易结合到现存的KDC方案中 软件更改量小 增加一个公开密钥层提供了一种安全有效的分配主密钥的方法 Return 36 2 4Diffie Hellman密钥交换算法 Diffie与Hellman在其开创公钥体制的文章中给出了公钥密码的思想 这篇论文中给出的算法常被称为Diffie Hellman密钥交换算法 它是第一个公开发表的公开密钥密码算法 严格地说 它并不能完成信息的加 解密功能 只能用于网络环境中的密钥交换 目前许多商用产品都使用这种密钥交换技术 该算法的目的是使两个用户安全地交换一个密钥 以便于今后的报文加密 本算法仅限于密钥交换的用途 Diffie Hellman算法的有效性依赖于计算离散对数的难度 37 1 算法描述离散对数的概念原根 如果 是素数p的一个原根 那么数值 modp 2modp p 1modp是各不相同的整数 且以某种排列方式组成了从1到p 1的所有整数 p76生成元 离散对数 如果对于一个整数b和素数p的一个原根 可以找到一个唯一的指数i 使得 b imodp其中0 i p 1那么指数i称为b的以 为基数的模p的离散对数 38 Diffie Hellman算法的有效性依赖于计算离散对数的难度 其含义是 当已知大素数p和它的一个原根 后 对给定的b 要计算i 被认为是很困难的 而给定i计算b却相对容易 Diffie Hellman算法假如用户A和用户B希望交换一个密钥 取一个素数q和一个整数 是q的一个原根 用户A选择一个随机数XA q 并计算YA XAmodq 用户B选择一个随机数XB q 并计算YB XBmodq 每一方都将X保密而将Y公开让另一方得到 39 用户A计算密钥的方式 KA YB XAmodqKA XBmodq XAmodq XB XAmodq XBXAmodq XAXBmodq用户B计算密钥的方式 KB YA XBmodqKB XAmodq XBmodq XA XBmodq XAXBmo