现代密码学第十章公约密码.ppt

现代密码学 第十章：公钥加密 本章主要内容 10.1.公钥加密简介 10.2.定义 10.2.1选择明文攻击的安全性 10.2.2多重加密 10.3. 混合加密 10.4. RSA加密 10.4.1“教科书式RSA”加密方案及其不安全性 10.4.2对“教科书式RSA”加密方案的攻击 10.4.3填充RSA 10.5. ElGamal加密 10.6选择密文攻击的安全性 10.7 *陷门置换 10.7.1定义 10.7.2来自陷门置换的公钥加密 10.1 公钥加密简介 公钥加密的出现标志着密码学领域的一场革命。在此之前，密码学家们完全依靠共享的秘密密钥来实现秘密通信。 两个人在一间屋子的两端，能通过大声喊叫与对方交流，虽然没有初始密钥，但屋子里没有人知道他们说什么。 在对称密钥加密情况下，两方同意共享一个可同时用于（任何一方）加密和解密的秘密密钥K，公钥加密在这方面是非对称的。具体来说，一方（接收方）产生一对密钥（PK，SK），被分别称为公钥和私钥。发送方用公钥将消息加密，然后发送给对方。接收方就用私鈅将最终收到的密文进行解密。 公钥加密与对称密钥加密的比较 前者假设了所有密钥的完全必威体育官网网址性，然后后者只要求了密钥对（PK，SK）一半的必威体育官网网址性。虽然这看似很小的区别，其实有着很大的不同：在对称密钥加密中，通信的双方必须能够共享密钥，并且不允许第三方获得此密钥；而在公钥环境中，一方可以再不损失安全的情况下通过公共信道将公钥传给第一方。对在一个房间里相互大声喊叫的各方来说，或者更现实点，在一个完全在公共网络（类似电话线或者互联网等）中通信的各方，公钥加密式唯一的选择。 另外一个重要的区别在于：对称密钥加密方案加密和解密时使用的密钥是同一个，而公钥加密方案使用不同的密钥。因为这个原因，公钥加密方案有时候被称作非对称的。这个非对称在公钥情况中意味着发送方和接收方不能像私钥情况下互换身份：一个给定的公钥加密方案只允许单向通信（关键点：单方发起的加密迫使放松者和接受者之间存在区别）。另外，公钥加密方案可使多个发送者与单个接受者秘密通信，与之不同的是，依靠双方共享密钥的对称密钥加密只能让两方进行秘密通信。 对称密码和公钥密码比较（1） 对称密码 运行条件： 1、加密和解密使用同一个密钥和一个算法。 2、发送方和接收方必须共享密钥和算法。 对称密码和公钥密码比较（2） 对称密码 安全条件： 1、密钥必须必威体育官网网址。 2、如果不掌握其他信息，要想解密报文是不可能或者至少是不现实的。 3、知道所用的算法加上密文的样本必须不足以确定密钥。 公钥加密的优缺点 优点 最重要的优势是公钥加密（在某种程度上）解决了密钥分配问题。因为通信双方不需事先共享秘密密钥。公钥加密可以让双方秘密通信，甚至他们之间所有的通信都被监听。 在一个接受者与U个发送者通信的情况下，接受者存储一个单独的私钥SK，比共享、存储以及管理U个不同的密钥要方便的多。事实上，当利用公钥加密时候，潜在发送方的数量和标识不需要再密钥产生时被知道。这就有了极大的灵活性，并且对于一个在线商家来说非常重要。 缺点 比对称密钥加密要慢至少2~3个数量级。 公钥的安全分配 到目前为止，我们隐含地假定敌手是被动的。换言之，敌手仅仅偷听接受者和发送者的通信，但不主动干扰通信。如果敌手能够篡改诚实通信方全部的通信，并且该通信方没有共享密钥，则不能实现私密性。 本章以及下一章对公钥加密的讨论，都简单地假设发送方有一个接受方公钥的合法拷贝。换言之，假设密钥已经安全分配，这个假设不是因为上面提到的主动攻击不值得关注，而是因为存在着其他阻止这些主动攻击的方案，并且很方便的将安全公钥加密的研究与安全密钥分配的研究分离开来。 10.2 定义 定义10.1公钥加密方案是如下一个概率多项式时间算法（Gen，Enc，Dec）的元组。 （1）生成密钥算法Gen用安全参数 作为输入，输出一对密钥（PK，SK）。把 PK称为公钥，把SK称为私钥。为了方便，假设PK和SK的各自长度至少为n，而且可有PK和SK确定。 （2）加密算法Enc把公钥PK和来自某个明文空间的一个消息m作为输入。输出密文c，记为 （3）解密算法Dec把私钥SK和密文c作为书输入，输出一个消息m或一个定义为失败的特殊符号 。不失一般性，假设Dec是确定的，记为m:= 满足 例外的概率是可忽略的，概率的计算来源于由 输出的（PK，SK）和Enc使用的任何随机性。 根据语法的定义，与对称密钥加密的一个重要的区别是： 密钥生成算法Gen现