第四讲公钥密码体制补充内容(第6章)

第四讲 公钥密码体制 （补充内容）

北京科技大学应用学院 卫宏儒 [email protected]

主要内容

一、公钥密码系统原理 二、RSA算法 三、Diffie-Hellman密钥交换 和EIGamal算法

四、椭圆曲线密码 五、公钥密码系统的密钥管理

背

景

对称密钥密码体制的一个缺点是它需要在 Alice 和 Bob 之间首先在传输密文之前使用一个安 全的通道交换密钥。实际上，这可能是很难达到的。 例如：假定 Alice 和 Bob 居住相距遥远，他们决定 用 Email 通信，在这种情况下，Alice 和 Bob 可能 无法获得一个相当安全的通道。

在公钥密码体制中的一个想法就是：可以找到一个 密码体制使得由给定的 果这样的话，加密规则

eK eK

来求

dK

是计算不可行的。 如

是一个公钥，可以在一个目

录中发布（这也就是公钥体制名称的由来） 。公钥体制 的优点就是 Alice(或者其他任何人)可以利用公钥加密 规则

eK

发出一条加密的消息给 Bob，而不需要预先的

dK

共享密钥的通信。Bob 将是唯一能够利用解密规则 （称为私钥）对密文进行解密的人。

公 钥 密 码 体 制 的 思 想 是 在 1976 年 由 Diffie和Hellman提出的。然后在1977年由 Rivest, Shamir和Adleman发明了著名的RSA 密码体制，将在本讲中研究。此后，几个公 钥密码体制被提出，其安全性依赖于不同的 计算问题。其中，最著名的是RSA密码体制 （及其变种），其安全性基于分解大整数的 困难性；ElGamal密码体制（及其变种，例 如：椭圆曲线密码体制），其安全性基于离 散对数问题。我们在本讲中讨论RSA密码体 制和它的变种、ElGamal密码体制。

在Diffie和Hellman之前，公钥密码学的思 想已经由James Ellis在1970年1月的一篇题为 “非隐秘加密的可能性”的文章中（短语“非秘 密加密”即是公钥密码学）提出。James Ellis 是电子通讯安全小组（CESG）的成员，这个小 组是英国政府通讯司令部（GCHQ）的一个特别 部门。这篇文章没有在公共文献中发表，而是 在1997年12月由GCHQ正式解密的五篇文章中的 一篇。在这五篇文章中，还有一篇由Clifford Cocks在1973年发表的题为“关于非秘密加密的 注记” 的文章，其中描述的公钥密码体制跟 RSA密码体制基本一致。

一、公钥密码系统原理

1、公钥密码应用模型 (1)、公钥加密私钥解密； （2）、私钥加密公钥解密； （3）、上述两种方法相结合即为数字签名 2、公钥密码算法的要求（六条）

( 2 )、 C = E ( M )

k pb

kc b

(1)、k , k 的生成；

p c

( 3 )、 M = D ( C ) = D ( E ( M ) ) ( 4 )、通过公钥推导私钥在计算上是不可能的。 ( 5)、通过公钥和密文获得明文在计算上是不可能的。

kc b k pb

( 6 )、 M

= D kc E k p ( M

(

)) =

D k p ( E kc ( M

))

公钥密码系统原理（续）

3、上述要求的实现，实质上是要构造一个单向函数。 4、公钥密码系统受到的攻击和防范： 强行攻击 增加密钥长度，控制算法复杂 性； 通过公钥推导对应的私钥； 对于公钥加密的短消息，存在的另一种攻击是可能字攻 击。

二、RSA算法

1、Whitefield Diffie和Martin Hellman [DH76] 于1976年提出了公钥密码系统的思想，然而他们 并没有给出一个实用的公钥密码系统。DiffieHellman的文章发表两年后，MIT的Ronald Rivist、Adi Shamir和Len Adlemar[RSA78]开发 出了第一个公钥密码体制---RSA密码体制。 2、RSA是一种分组密码算法，基于大整数n分解为 两个素数之积的难解性，其输入明文和输出密文 都是0到（n-1）之间的整数。

RSA 密码体制是基于群 Z 中大整数因子分解的困难 性。RSA 体制可以描述如下：

n

1．生成两个大素数 p 和 q 。 2．计算这两个素数的乘积 n = pq 。 3．计算小于 n 并且与 n 互素的整数的个数，即欧拉 函数 ϕ ( n ) = ( p − 1 )( q − 1 ) 。 4． 选取一个随机数 b 满足 1

3、RSA 的加密和解密过程 明文是以分组的方式来加密的。每一个 分组的比特数应该小于 n 的二进制表示；也 就是说，每一分组的长度应该小于 特。对于一组明文 x ，利用公钥 计算：

c = x b mod n

log 2 n 个比

(b , n )

通过

得到相应的分组密文 c 。而

x = c a mod n

由分组密文 c 通过计算 复出明文 x 。

便可以恢

4、RSA 的安全因素 选取的素数 定了它们的乘积 的情况下分解 如果知道了 算，既然 所以

a a n

p

和

q

要足够大，使得给

p

n

， 在事先不知道

或

q

是计算上不可行的。破译

n

RSA 密码体制基本上等价于分解

p和 q

；因为，

，则

ϕ (n)

ϕ (n )

可以很容易计 的乘法逆元，

是

b

关于模

也可以马上算出来。

1999 年，一个由 292 台计算机组成的网络利 用数域筛法 （是指一种大因子分解技巧） 花了 5.2 ， 个月的时间分解了一个 155 位的十进制数（512 比特） ；基于短期安全性考虑， 要求 十进制位数的 看，

n

的长度至少

应为 1024 比特。整数的二进制表示的比特数是其

log 2 10

倍， 所以一个 1024 比特的整数

2

的十进制位数是 1024 / log 10 ≈ 308 。然而从长期安全性来

n

的长度至少应为 2048 比特（或者是 616

位的十进制数） 。

三、Diffie-Hellman密钥交换 和EIGamal算法

公钥密码学的思想是由 Diffie 和 Hellman 在 1976 年的公开文献中引入的。RSA 密码

体制是由 Rivest, Shamir 和 Adleman 发现的。对于公钥密码 学的一个一般的综述，我们推荐 Diffie 的文章[W.

Diffie, The first ten years of public—key cryptography. In Contemporary Cryptology, The Science of Information Intefrity, pages 135—175. IEEE Press, 1992.]关于 RSA

的一个特别概览，参看 Boneh[D. Boneh. Twenty years of

attacks on the RSA cryptosystem. Notices of the American Mathematical Society, 46(1999), 203—213.]。

（一）Diffie-Hellman密钥交换

Diffie-Hellman第一个提出了公钥密码算法。 这个算法本身基于计算离散对数的难度，其目 的是实现两个用户之间安全地交换密钥以便于 后续的数据加密。直到现在， Diffie-Hellman 密钥交换算法仍然在许多商用产品中使用。 如果Alice和Bob希望使用Diffie-Hellman密钥 交换协议在一个不安全的信道上交换密钥，他 们可以这样做：

1． Alice 和 Bob 确定一个适当的素数 p 和整数

α ，使得 α 是 p 的本原根； α 和 p 可以公开。

2． Alice 秘密选取一个整数 并把

y

A

aA

， y 计算

A

= α a A mod p

发送给 Bob。

aB

3． 秘密选取一个整数 Bob 并把

yB

， 计算 y

B

B

= α a B mod p

发 送 给 Alice 。 y 和 y 就 是 所 说 的

A

Diffie-Hellman 公开值。

4．Alice 钥 K。 5． Bob

K = ( y B ) a A mod p 生成密 通过计算

K = ( y A ) aB mod p 生成密钥 通过计算

K。

6．Alice 和 Bob 生成的密钥 K 是恒等 的，因为：

K = ( y B ) aA mod p = (α a mod p ) a mod p

B A

= (α

= (α

aB

aA

) a A mod p = α

)

aB

aBaA

mod p

aB

mod p = (α

aA

mod p )

mod p

= ( y A ) a B mod p

安全性 Diffie-Hellman 密钥交换的安全性是基 于这样的假设：从

aA 或 a B

yA

或者

yB

以及 α 计算

在计算上是不可行的；因为这等价于

求解离散对数问题。

中间人攻击 Diffie-Hellman 密钥交换容易遭受中间人攻击， 在这一攻击中，入侵者（我们称她为 Eve）拦截消息 并篡改它，然后再把篡改后的消息发送给 Bob 和 Alice，如图下图所示。Alice 认为她是用 Bob 的 y B 生成密钥，但实际上她使用了 Eve 的值 y B ' 。同样， Bob 认为他是用 Alice 的 y A 生成密钥，但实际上她 使用了 Eve 的值 y A ' 。因此，Alice 和 Bob 所生成的 密钥就被 Eve 共享，但双方却不知道这一点。利用认 证 Diffie-Hellman 密钥交换可以挫败中间人攻击。

认证 Diffie-Hellman 密钥交换 Diffie-Hellman 密钥交换的适当变形可以挫败中间 人攻击， 这就是利用数字签名来签署和认证 Alice 和 Bob 所 交 换 的 整 数 y A 和 yB 。 这 个 方 案 类 似 于 Diffie-Hellman 交换，所不同的是：Alice 用一个数字 签 名 算 法 签 署 y A 产 生 签 名 sig ( y A ) ， 然 后 把 y A 和 sig( y A ) 传送给 Bob。

认证Diffie-Hellman密钥交换（续）

Bob 可以用 Alice 的公开验证算法来确定 sig ( y

A ) 是否真是 Alice 对 y A 的签名。同样，Bob 对 y B 签名并把 y B 和 sig ( y B ) 同时送给 Alice，她 能够利用 Bob 的公开验证算法来判断 sig ( y B ) 是否 Bob 对 y B 的签名。 这样双方都能够确定他们从对 方那里所收到的消息有没有被窜改过。因此， Alice（或 Bob）就不会受到欺骗：收到了 Eve 的 消息用来生成密钥，却误以为这些消息来自 Bob （或 Alice） 。

（二）EIGamal算法 （基于离散对数的又一种可用于加密 和认证的公钥密码算法）

背景知识 ElGamal 密码系统是 ElGamal 设计的， 1984 于 年发表。 这一体制基于有限域上离散对数问题的困 难性。域实际上是一个群，并具有附加性质：域中 每一个非零元素都有乘法逆元。 p 是素数，Z p 设 就是有限域的一个例子。这个域由元素集合 {0,1,2, , p − 1} ，模 p 的加法运算和模 p 的乘法运 算组成。另一个有限域的例子是 Z p * ，其中的所有 元素都与 p 互素。 Z p * 还具有另外一个特性：它 是一个循环域。换言之，任意元素 β ∈ Z 都可以 由一个生成元 g 的 a 次幂生成， 其中 0 ≤ a ≤ p − 2 。

p*

例子：考虑域 Z13* = {1,2,3,4,5,6,7,8,9,10,11,12} 。这个域的生 成元是 2，因为其中的每个元素都可以由 2 的某一 a 次方幂生成，其中 0 ≤ a ≤ 11 ；即

2 0 mod 13 = 1,

24 mod 13 = 3,

2 1 mod 13 = 2,

2 2 mod 13 = 4 2 5 mod 13 = 6,

2 9 mod 13 = 5,

211 mod 13 = 7,

2 8 mod 13 = 9,

2 3 mod 13 = 8

210 mod 13 = 10,

2 7 mod 13 = 11,

2 6 mod 13 = 12

一个域的生成元称为模 p 的本原元。

算法依据

离散对数问题可应用于任一个有限域；但 我们的讨论仅局限于它在域 Z p 上的应用。考

a 虑方程 β = g mod p ， 其中

β ∈ Z

p*

；如果仔

细选择 p ，那么对于给定的 β 、 g 和 p ， 计算 a 的值是非常困难的。但是给定了 g 、 a 和 p ， β 就可以非常有效的计算出来。也 就是说，对适当的 p 来说，模 p 的指数运算 是一个单向函数。

加密解密过程

ElGamal 系统： 首先选取一个合适的素数 于小于

p

，使得对

p 的整数的离散对数问题是困难的。

β

然后选择适当的

β = g a mod p

、

g

和 a 满足

。公开

β

、 g 和 p ，保密 a 。

加密过程 Alice 秘密选取一个随机 为了加密明文 x ， 整数 k ，满足 k ≤ p −1；设 ek 是加密变换，记

ek ( x , k ) = ( y1 , y 2 )

其中 y = g mod p ， y = xβ mod p 。注意到 密文依赖于 Alice 所选取的 k 值，明文 x 可 以加密成很多种不同的密文；因而 ElGamal 密码 体制是非确定性的。

k

k

1

2

解密过程 如果

dk

是解密变换，记

d k ( y1, y 2 ) = y 2 ( y1 ) −1 mod p

a

来“掩 y 2 和 g k 的乘积传送给 Bob——私钥持 盖” ；把 有者。然后 Bob 就可以用他的私钥 a 从 g k 中 计算出 β k 。最后，通

过 y 2 除以“掩盖” β k 就能够确定出明文 x 。

β

k

简单地说，明文 x 通过乘以

例6-4-1

练习：设 p = 11 ，取 g = 2 ，α = 8 ， （1）计 算β

≡ g mod p ，指出公钥和私钥； （2）对

α

明文组 m = 5 ，选随机数 k = 9 ，计算密文 并解密。

β ≡ g mod p = 28 mod11 = 3 ， 解： （1）

α

公钥为 Kc = (3, 2,11) ，私钥为 K p = (8,11)

（2）若明文组 m = 5 ，选随机数 k = 9 ， gcd ( k, p −1) = gcd ( 9,10) = 1，则：

y1 = g mod p = 2 mod11 = 6，

k 9

y2 = M β mod p = 5× 3 mod11 = 9，

k 9

所以密文（6，9） 。

解密：

M ≡ y2 × ( y1 ) mod11 ≡ (9 × 6 mod11) ≡ (9 × (6 mod11) mod11)

8 −1

α −1

−8

∵ (6 mod11) = 2

∴ M ≡ (9 × 2 mod11) = (9 × 3 mod11) = 5

8

−1

安全性分析

到目前为止，求解离散对数问题最有效 的算法是数域筛法。这个算法的一个变形可 以用于大数分解。域 Z 上的离散对数问题 一般认为比群 Z n 上的大数分解问题更困难 一些。然而，正如 RSA 体制中对于群 Z n 的模 n 的要求一样，基于合理的安全性考虑，对 于 ElGamal 体制中的域 Z ， 素数 p 的长度 至少应为 1024 比特； 而对于长期的安全性要 求，p 的长度至少应为 2048 比特。

p*

p*

四、椭圆曲线密码

公钥密码学的思想是基于这样的问 题：从一个方向可以有效地计算，但是其 逆问题却非常困难；就如离散对数问题和 大数因子分解问题一样。多年来，研究人 员一直在寻找这样的问题，它们具有足够 的难度从而有作为密码系统基础的价值。

五、公钥密码系统的密钥管理

公钥分配 利用公钥密码方案分配对称密钥

1、公钥分配

分配公钥的策略 公开发布：公钥密码系统的本质特性；缺点是存在假冒 发布消息的安全隐患。 共享的公钥目录：由一个可信赖的实体建立和维护各用 户都可以访问的动态公钥目录。该方案包含六个组成要 素。 （1）目录项；（2）用户注册；（3）可更改公钥值 （4）目录表更新；（5）安全认证。 通过公钥管理机构获得对方公钥 公钥管理机构维护公钥目录。 公钥证书管理---对上一方法 的改进，直接验证对方的 某种证书（公钥证书）。

公钥分配（续）

直接验证的证书由可信赖的证书认证管理中 心（CA）签发。两个用户发生交互时只需要交换 证书并验证其有效性即可。基本要求为： （1）标识和公钥；（2）有效性；（3）签发 和更新。 CA签发证书的4个过程（申请,认证,发证,签名）。 以CA为基本组成元素，建立称为公钥基础设施 （PKI）的公钥证书管理体系。

公钥基础设施（PKI） 的结构和信任模型

PKI结构和模型（续）

根CA给B、C和D颁发CA证书；它们依 次颁发其他的CA证书，一些接受者颁发 CA证书而其他的颁发

终端用户证书。为 了验证任何一个证书的有效性（根CA除 外），证书处理实体不仅需要确定讨论 中的证书是否有效，而且系统或者实体 也需要检查直到根CA路径上的每一个证 书，保证每一个证书都是有效的。

PKI结构和模型（续）

对于根CA的私钥，应当给予非常严格 的安全要求，因为一旦根CA的密钥泄漏， 位于层次路径上一直到根CA的所有CA以及 终端用户的证书连同根CA证书都需要吊 销。根CA私钥的长度至少为2048比特。总 之，CA在层次结构中的层次越高，对与讨 论中的CA的私钥相关联的安全要求越高， 因为如果某CA的密钥泄漏，则该CA颁发的 所有证书，连同所有位于直到该CA的路径 上的CA颁发的证书都需要吊销。

PKI结构和模型（续）

在该图所示的例子中，C 和 D 可以是独立的组织，例如，具有双向 信任关系的厂商和客户， 或者他们是某一给定组织里的不同的组。 对于 L 和 M 也有同样的情况。

PKI结构和模型（续）

在使用交叉认证之前必须要慎重，因为 交叉认证可能会导致安全隐患。 例如，如果C和D之间有一个交叉认证 协议，D向C颁发一个CA证书，如果C向其 他的商业伙伴颁发证书，除非D有非常严格 的访问策略，则C的这些商业伙伴可以建立 起到D的网络的VPN链路，尽管D并不希望 让他们这样作。

2、利用公钥密码方案分配对称密钥

公钥加密算法效率远低于对称密码算 法，所以应用中往往是： 数据加密----对称密码方法 对称密钥分发----公钥密码方法 实现方案