现代密码学第七讲：公钥密码学1.ppt

1、1.公钥密码学(一)，第7章现代密码学，回顾上述内容，定义单向函数哈希函数MD5算法SHA-256算法SHA-512和SHA-384算法消息认证码介绍CBC-MAC算法HMAC算法，3。本章主要内容，公钥密码系统的提出和分类：公钥密码系统的基本概念；单向活板门功能的概念设计：公钥加密算法背包密码体制RSA算法和攻击方法ElGmal算法和椭圆曲线密码体制；密钥分发：在加密器指定一个密钥后，他必须尽力将它分发给解密器，同时，他必须小心确保密钥不被泄露。这是对称密码算法的一个内在矛盾。如何解决？对称密码对密钥分发的要求：共享一个密钥：使用密钥分发中心：如何获得第一个密钥，如何获得KDC之间的密钥，公

2、钥密码系统，密钥管理：在一个有多个用户的网络中，任何两个用户都需要有一个共享密钥。当网络中的用户数n较大时，要管理的密钥数为n *(n-1)/2。当委托人A未签名时，提出公钥密码系统，6，公钥加密系统的原理，邮箱的例子，任何人都可以向邮箱发送报告，用户(审计员)可以打开邮箱并读取信件的内容，7，公钥加密模型，公钥加密系统的原理，密钥分发，8， 参数生成过程：1)要求接收消息的端系统生成一对用于加密和解密的密钥，如图中的接收者B，并生成一对密钥PKB，其中PKB是公钥，SKB是密钥。 2)终端系统b公开加密密钥(图中的PKB)，而另一个密钥是保密的(图中的SKB)。公钥加密系统原理。公钥加密系统

3、原理，参数生成的要求：公钥，任何人都可以知道，可以用来加密或验证签名；私钥只能由消息的接收者或签名者知道，用于解密或签名；从私钥和公钥参数计算公钥很容易；很难从公钥和公钥参数推导出私钥。10，加密和解密过程：1)如果a想向b发送消息m，使用b的公钥加密m，m表示为c=EPKBm，其中c是密文，e是加密算法。2)b接收到密文c后，用自己的密钥SKB解密，m表示为DSKBc，d表示解密算法。公钥建立方案(pkes)用于交换秘密信息，并且经常用于对称加密算法的密钥分发，公钥加密(PKE)任何人都可以用公钥加密任何消息。私钥的所有者可以解密消息。任何公钥加密方案都可以用于PKDS密钥分发方案。一些公钥

4、加密方案也是数字签名方案。签名方案用于为消息生成数字签名。私钥的所有者生成一个数字签名。任何人都可以用公钥验证签名。公钥密码系统的分类，12。公钥密码系统的发展历史。1976年，Diffie和Hellman在密码学的新方向上首次公开提出了非对称密码算法的思想，但没有实现加密方案，只给出了一个密钥协商协议；1978年，瑞文斯特、沙米尔和阿德曼提出了广泛使用的RSA算法；1984年，沙米尔提出了基于身份的密码系统，但没有实现加密系统。只给出了一种基于身份的数字签名算法。2001年，波尼、富兰克林和科克独立提出了基于身份的加密算法。2003年，阿尔-里雅米提出了无证书密码系统，公钥密码系统的发展历史

5、，迪菲和赫尔曼，公钥密码系统的发展历史，罗纳德里弗斯特，阿迪萨莫尔和莱恩阿德曼，15，基本概念：公钥密码系统也称为双密钥密码系统/非对称密码系统；该算法的最大特点是使用两个相关的密钥来分隔加密和解密能力，其中一个是公开的，称为公钥，用于加密；另一个密钥对用户来说是私有的，因此是保密的。它被称为解密密钥。使用公钥(和公钥参数)很难推导出私钥。，公钥加密算法的特点，16，公钥加密系统框图，公钥加密算法的特点，17，加密和解密算法需要满足的要求：加密和解密的顺序可以改变，即EPKDSKB(m)=DSKBEPKB(m)非常有用，但它并不要求所有的算法。加密和解密速度比对称算法慢。因此，公钥密码体制目前

6、主要用于密钥管理和数字签名。与对称算法相似，不良搜索在理论上可以破解公钥密码。事实上，密钥足够长(512位)以确保计算安全。安全性取决于足够的难度差异，如NP和P问题(用公钥和公共参数加密明文容易计算；用私钥和公钥参数解密密文容易计算；仅用公钥解密密文是困难的)；公共密钥加密算法18的特征将单向函数定义为两个集合x和y之间的映射，因此y中的每个元素y都具有唯一的原始图像xX，并且很容易通过x计算其图像y，但是通过y计算其原始图像x是不可行的。当给出附加信息时，反演可以在多项式时间内完成。单向陷门函数19是一族可逆函数fk，它满足Y=fk(X)，易于计算(当K和X已知时)。X=f-1k(Y)易于

7、计算(当K和Y已知时)。X=f-1k(Y)单向陷门函数，20，背包问题：设A=(a1，a2，an)是由N个不同正整数组成的背包向量，S是背包体积。找出A的子集A，这样子集中元素ai的和就等于S。A=(43，129，215，473，903，302 S=3231。由于3231=129 473 903 561 1165，从A中找到的满足要求的子集是129，473，903，561，1165。背包密码系统，21。原则上，通过检查A的所有子集，我们总能找到问题的解决方案(如果有的话)。有210=1024个子集(包括空集)。如果a中的元素数n很大，那么子集数2n将非常大，没有比差搜索更好的算法来寻找满足要求

8、的a的子集，因此背包问题是NP问题。只要n足够大，计算就不可行。背包问题可以构造一个单向函数f。如果x(1x2n-1)写成n :的二进制表示，f(x)定义为。在上面的例子中，f(364)=f(0101101100)=129 473 903 561 1165=3231和：f可以类似地获得。F (32)=903，F (46)=3326，F (128)=215，F (261)=2817。F的定义表明，找到f(x)是容易的，但当N较大时，找到X是不可行的。然后求出各组的函数值，并将函数值(背包体积)作为密文分组。例如，背包密码系统24。在上面的例子中，背包向量仍然取A，让明文加密为桑拿和健康。因为A是10，所以明文应该分成10位(即两个明文字母)，分组为SA、UN、A、AN、D、he、AL等。相应的二进制序列是1001100001、10101110、000010000、00001110、00100000、0100000101、00001100、1010000100。函数F被应用于上述二进制序列以获得密文3300。2817，2629，819)，背包密码系统。如果明文消息是英文文本，则每个字母都可以用其在字母表中的序列号来表示，然后序列号可以转换成二进制形式(仅5位)，其中符号表示空格25，并