(中文版)第三章_公钥加密和消息认证

第三章
公钥加密和消息认证 (Ⅳ)
主讲：綦朝晖
石家庄铁道学院计算机与信息工程分院
1
内容回顾
1 ,公钥算法的三种典型的应用 ；
2
,掌握RSA公钥算法（一定要会计算）；
2
内容回顾
在广义上可以把公钥加密系统分为三类：


1, 加密/解密
2, 数字签名
3, 密钥交换
3
内容回顾
密钥生成算法：

公钥证书由公钥加上公钥所有者的用户ID以及可信 的第三方签名的整个数据块组成。通常， 第三方 就是用户团体所信任的认证中心(CA)，如政府机构 或金融结构。
49
密钥管理
图3.12 描述了这个过程。知识点
1， Diffie-Hellman 密钥交换算法 ； 2， 什么是数字签名的概念； 3， 什么是public-key certificates（公钥证书）；
图3.11 Diffie-Hellman 密钥交换
29
Diffie-Hellman 密钥交换
假设用户A希望与用户B建立连接，并且在此连接上使用
密钥加密消息。 用户A可以生成一次性密钥XA，计算YA，然后把YA发送 给用户B。作为回应，用户B生成私钥XB，计算YB，然后 将其发送给用户A。 这时两个用户都可以计算密钥了。
任何时候用户B都可以访问A的公开值，计算密钥，再
使用它给用户A发送加密消息。
然而，该技术并不能防止重放攻击。
32
Diffie-Hellman 密钥交换
33
概要
Diffie-Hellman 密钥交换
其他公钥加密算法 数字签名 密钥管理
34
其他密钥加密算法
在本节中我们将介绍两种已被商业接受的其他的公钥
27
Diffie-Hellman 密钥交换
下图 (教材，图3.11) 给出了使用Diffie-Hellman 计算
的一种简单协议。
28
用户A
生成 随机数XA < q ; 计算 YA = aXA mod q
用户 B
YA
YB 计算 K = (YB)XA mod q
生成 随机数XB < q ; 计算 YB = aXB mod q 计算 K = (YA)XB mod q
25
Diffie-Hellman 密钥交换
Diffie-Hellman 密钥交换的安全性在于：虽然计算模
幂运算相对容易，
但是计算离散对数却非常困难。对于大对数，计算离
散对数被认为是不可行的。
26
Diffie-Hellman 密钥交换
例如，选择素数q = 71 ，并且选择71的本原根a = 7。
Diffie-Hellman之所以有效，是因为它基于离散对数
的计算困难。
首先，我们学习一些关于Diffie-Hellman算法的基本
概念。
13
Diffie-Hellman 密钥交换
素数q的本原根:

我们定义素数q的本原根为它的幂能够生成1~q1之间的所有整数的数。 即如果a是素数q的一个本原根，则下列各个数： a mod q, a2 mod q , …, aq-1 mod q 各不相同，但它们组成了1~q-1之间整数的某种 排列组合。
验证：

验证（M，r，s）＝ 真 当且仅当 v = r；
38
DSA
大家注意：DSS 和 DSA 有什么区别？
39
椭圆曲线加密术
采用公钥实现加密和数字签名的绝大多数产品
和标准都使用RSA算法。
最近几年来，安全RSA使用的比特长度在不断
增加，加大了RSA应用处理的负担。
40
密钥管理
47
密钥管理
只是介绍 “公钥证书”； 从字面理解，公钥加密的意思就是公钥是公开的。 所
以，如果有某种广泛接受的公钥算法，如RSA，任何 参与者都可以给其他参与者发送他的或她的公钥，或 向群体广播自己的公钥。
然而，任何人都可以伪造这种公共通告。
48
密钥管理
解决这种问题的方法就是公钥证书。 公钥证书：
算法： 数字签名标准（DSS，Digital Signature Standard）和椭圆曲线加密术（elliptic-curve cryptography）。
35
数字签名标准
美国国家标准与技术研究所(NIST)已经发布
了联邦信息处理标准FIPS PUB 186，也就是 数字签名标准(DSS)。
52
课后作业
91页 题目：
3.16 a
;
3.16 b
53
30
Diffie-Hellman 密钥交换
还有使用Diffie-Hellman算法的另一个例子。假设一
组用户(如局域网上的所有用户)各自生成持续使用很长 时间的私钥值XA，然后计算公开值YA。
这些公开值连同全局公开值q和a都存储在某个中央目
录里。
31
Diffie-Hellman 密钥交换

2, 用户A选择一个大的随机数xA < q并保持它的
私密性。同样地，用户B选择xB <并保持它的私 密性。这就是他们的“私钥”。
20
Diffie-Hellman 密钥交换

3, 用户A计算她的公钥yA = axA (mod q) 并通过
不安全的通信将它发送给用户B 。用户B计算他 的公钥yB = gxB (mod q) 并将它发送给用户A 。 其中 0 < yA < p， 0 < yB < p。 如我们所知，这样通过通过不安全的通信发送 公钥是安全的。
所以，人们对ECC的信赖水品好没有RSA高。
42
概要
Diffie-Hellman 密钥交换 其他公钥加密算法 数字签名
密钥管理
43
数字签名
如图3.7b 教材，图3.7)所示，公钥加密还可以按另一
种方式使用。
44
数字签名
假设Bob想给Alice发送消息。虽然这条消息的保密性
在以上的背景下，我们可以定义Diffie-Hellman密钥
交换, 在下图中给出了它的概述(教材图3.10)
16
17
18
Diffie-Hellman 密钥交换
Diffie和Hellman的思想是计算一个素数的幂模运算相
对容易，但是反过来计算离散对数却非常困难。
如果有人问你2的多少次幂模11的结果为7， 你很快就
14

Diffie-Hellman 密钥交换
离散对数i：
对于任意小于q的整数b和q的本原根a，我们
能够找到一个唯一的指数i，使得
b = ai mod q 其中 0 ≤ i ≤ (q-1)
称指数i为b的基为a模为q的离散对数。我们把这
个值记为inda,q (b) 。
15
Diffie-Hellman 密钥交换
23
Diffie-Hellman 密钥交换
这样，双方都交换了密钥。此外，因为XA和
XB为私有，所以攻击者只能利用如下元素进行 攻击：q， a， YA和YB。
24
Diffie-Hellman 密钥交换
例如，为确定用户B的私钥，攻击者必须计算
XB = inda,q (YB) 此后，攻击者就可以使用与用户B相同的方式计算密钥 K了。
21
Diffie-Hellman 密钥交换

4, 通信双方都保持X值的私密性并向对方公开 Y值。 用户A通过下式计算密钥： K= (YB)XA mod q 同时用户B计算 K= (YA)XB mod q
22
Diffie-Hellman 密钥交换
这两个计算产生相同的结果：
K = ( YB )XA mod q = ( aXB mod q )XA mod q = ( aXB )XA mod q = aXB XA mod q = ( aXA )XB mod q = ( aXA mod q )XB mod q = ( YA )XB mod q
A和B分别选择私钥XA = 5 和 XB = 12。各自计算自己 的公钥： YA = 75 mod 71 = 51 YB = 712 mod 71 = 4 他们交换公钥后，分别计算公共密钥： K = ( YB )XA mod 71 = 45 mod 71 = 30 K = ( YA )XB mod 71 = 5112 mod 71 = 30 明显地，一个攻击者不能容易地计算出密钥30。

1,生成两个随机的大的素数p和q， 它们的大小 近似相等，从而使它们的乘积n（n = pq）能满 足要求的比特长度，例如1024比特； 2,计算n = pq and φ(n) = (p-1)(q-1);

4
内容回顾

3,选择一个整数e，其中1 < e < φ(n)，使得 gcd (e, φ(n) ) = 1；
性论文中，该算法定义了公钥加密术，通常称该算法 为Diffie-Hellman密钥交换。
许多商业产品都采用了这种密钥交换技术。
11
Diffie-Hellman 密钥交换
算法的目的是使得两个用户能够安全地交换密钥，供
以后加密消息时使用。
该算法本身局限于密钥交换。
12
Diffie-Hellman 密钥交换
加密：
发送者A进行如下操作：


1,获取接收者B的公钥(n, e)； 2,将明文消息表示为一个正整数M； 3,计算密文C = Me mod n； 4,把密文C发送给B。
7
内容回顾
解密：
接收者B进行如下操作：


1,使用自己的私钥(n, d)来计算 M = Cd mod n； 2,从M中提取出原始的明文；