现代密码学第7讲：公钥密码学1

《现代密码学》第七讲

公钥密码(一)

上讲内容回顾

单向函数 Hash函数的定义 MD5算法 SHA-256算法 SHA-512和SHA-384算法 消息鉴别码简介 CBC-MAC算法 HMAC算法

本章主要内容

公钥密码体制的提出及分类 公钥密码体制的基本概念 单向陷门函数的概念 设计公钥加密算法--背包密码体制 RSA算法及攻击方法 ElGmal算法及椭圆曲线密码体制

公钥密码体制的提出

密钥分配：加密者指定一个密钥后，必须得 想方设法把密钥分发出去给解密者，同时还 得小心翼翼确保密钥不被泄露。这是对称密 码算法固有的一个矛盾，如何解决呢？

对称密码进行密钥分配的要求：

已经共享一个密钥： 利用密钥分配中心：

第一个密钥如何获得

和KDC之间的密钥如何获得

公钥密码体制的提出

密钥管理：在有多个用户的网络中，任何两 个用户之间都需要有共享的秘密钥，当网络 中的用户n很大时，需要管理的密钥数目是n (n-1)/2 无签名功能 当主体A收到主体B的电子文挡 (电子数据)时，无法向第三方证明此电子 文档确实来源于B。

公钥加密体制的原理邮箱的例子 任何人可以向邮箱投举报信 用户(审计人员)才能打开邮箱，读信的内容

公钥加密体制的原理公钥加密模型

密钥分配

公钥加密体制的原理参数生成过程：1) 要求接收消息的端系统，产生一对用来加密和 解密的密钥，如图中的接收者B,产生一对密钥PKB, SKB,其中PKB是公开钥，SKB是秘密钥. 2)端系统B将加密密钥(图中的PKB)予以公开， 另一密钥被保密 (图中的SKB).

公钥加密体制的原理参数生成需满足的要求：

公开密钥(public-key), 可以被任何人知道, 用 于加密或验证签名； 私钥(private-key), 只能被消息的接收者或签名 者知道,用于解密或签名； 由私钥及公开参数容易计算出公开密钥； 由公钥及公开参数推导私钥是困难的；

公钥密码体制的原理加解密过程：1) A要想向B发送消息m,则使用B的公开钥加密m, 表示为c=EPKB[m], 其中c是密文，E是加密算法.

2) B收到密文c后，用自己的秘密钥SKB解密，表示 为m=DSKB[c],其中D是解密算法.

公钥密码体制的分类

Public Key Establishment Schemes (PKES) 用于交换秘密信息 常用于对称加密算法的密钥

Public Key Encryption (PKE) 用于加密任何消息 任何人可以用公钥加密消息 私钥的拥有者可以解密消息 任何公钥加密方案能够用于密钥分配方案PKDS 许多公钥加密方案也是数字签名方案

Signature Schemes (SS) 用于生成对某消息的数字签名 私钥的拥有

者生成数字签名 任何人可以用公钥验证签名11

公钥密码体制的发展历史

1976年 Diffie和Hellman 在《密码学的新方向》中首次公开提

出了非对称密码算法的思想，但是没有实现加密方案，只给出一个密钥协商协议；

1978年 Rivest,Shamir和Adleman提出应用广泛的RSA算法； 1984年 Shamir提出基于身份的密码体制，没有实现加密体制， 只给出一个基于身份的数字签名算法

2001年 Boneh,Franklin和Cocks分别独立提出基于身份的加密算法

2003年 Al-Riyami提出的无证书的密码体制12

公钥密码体制的发展历史

Diffie和Hellman

公钥密码体制的发展历史Ronald Rivest, Adi Shamir, and Len Adleman

公钥加密算法的特点基本概念：公钥密码体制也称为双钥密码体制/非对称 密码体制； 算法的最大特点是采用两个相关密钥将加 密和解密能力分开，其中一个密钥是公开的， 称为公开密钥，简称公开钥，用于加密；另 一个密钥是为用户专用，因而是保密的，称 为秘密密钥，简称秘密钥，用于解密. 利用公开密钥(及公开参数)推导私有密钥 困难。 15

公钥加密算法的特点分析者

发送者 M 信源

M

加密

C 无噪信道

解密 K’ 安全信道

M

接收者

无噪信道

K

密钥源

公钥加密体制框图16

公钥加密算法的特点加解密算法需满足要求：加、解密次序可换，即 EPKB[DSKB(m)]=DSKB[EPKB(m)] 这一条虽然非常有用，但不是对所有的算法都作要求.

加解密速度比对称算法慢，因此公钥密码体制目前主要用于密钥 管理和数字签字. 类似于对称算法,穷搜索在理论上是能够破解公钥密码. 实际上, 密钥足够长 (>512bits)保证计算安全. 安全性依赖于足够大的困难性差别，如NP和P问题(利用公钥及公 开参数加密明文容易计算；利用私钥及公开参数解密密文容易计 算；只利用公钥解密密文困难);

单向陷门函数定义 单向函数是两个集合X、Y之间的一个映 射，使得Y中每一元素y都有惟一的一个原像 x∈X,且由x易于计算它的像y,由y计算它 的原像x是不可行的. 一个函数是单向陷门函数，是指该函数是易 于计算的，但求它的逆是不可行的，除非再 已知某些附加信息。当附加信息给定后，求 逆可在多项式时间完成.

单向陷门函数单向陷门函数是一族可逆函数fk,满足 ① Y=fk(X)易于计算(当k和X已知时). ② X=f-1k(Y)易于计算(当k和Y已知时). ③ X=f-1k(Y)计算上是不可行的(当Y已知但k 未知时). 研究公钥密码算法就是要找出合适的陷门单 向函数

背包密码体制背包问题：设A=(a1,a2,…,an)是由n个不同的 正整数构成的背包向量，s是背包容积.求A的 子集A’,使子集中

的元素ai的和恰好等于s.例. A=(43, 129, 215, 473, 903, 302, 561, 1165, 697, 1523),s=3231. 由于 3231=129+473+903+561+1165. 所以从A中找出的满足要求的子集合是{129、 473、903、561、1165}.

背包密码体制原则上讲，通过检查A的所有子集，总可找 出问题的解(如果有解的话).上例中，A的子集共有210=1024个(包括空集).

如果A中元素个数n很大，子集个数2n将非常 大, 且寻找满足要求的A的子集没有比穷搜索 更好的算法，因此背包问题是NP问题. 只要n 足够大，那么，计算不可行.21