A
Diffie-Hellman 公开值。
4．Alice 钥 K。 5． Bob
通过计算 K ( y B )
aA
mod p
生成密
通过计算 K ( y A )
aB
mod p 生成密钥
K。
6．Alice 和 Bob 生成的密钥 K 是恒等 的，因为：
K ( yB )
(
(
aB
aA
mod p (
第四讲 公钥密码体制
北京科技大学数理学院 卫宏儒 Weihr168@
主要内容
一、公钥密码系统原理 二、RSA算法
三、Diffie-Hellman密钥交换 和EIGamal算法
四、椭圆曲线密码 五、公钥密码系统的密钥管理
背
景
对称密钥密码体制的一个缺点是它需要在 Alice 和 Bob 之间首先在传输密文之前使用一个安 全的通道交换密钥。实际上，这可能是很难达到的。 例如：假定 Alice 和 Bob 居住相距遥远，他们决定 用 Email 通信，在这种情况下，Alice 和 Bob 可能 无法获得一个相当安全的通道。
RSA 密码体制是基于群 Z 中大整数因子分解的困难 性。RSA 体制可以描述如下：
n
1．生成两个大素数 p 和 q 。 2．计算这两个素数的乘积 n pq 。 3．计算小于 n 并且与 n 互素的整数的个数，即欧拉 函数 ( n ) ( p 1)( q 1) 。 4． 选取一个随机数 b 满足 1 b ( n ) ， 并且 b 和 (n ) 互 素，即 gcd( b , ( n )) 1 。这一必要条件保证了 n 具有乘法 逆元。 5．计算 a b mod ( n ) 。 6．保密 a ， p 和 q ，而公开 n 和 b ，任何想给你 传送加密信息的人都可以得到 n 和 b 。
log 2 10
倍， 所以一个 1024 比特的整数
2
的十进制位数是 1024 / log
n
10 308
。然而从长期安全性来
的长度至少应为 2048 比特（或者是 616
位的十进制数） 。
三、Diffie-Hellman密钥交换 和EIGamal算法
公钥密码学的思想是由 Diffie 和 Hellman 在 1976 年的公开文献中引入的。RSA 密码体制是由 Rivest, Shamir 和 Adleman 发现的。对于公钥密码 学的一个一般的综述，我们推荐 Diffie 的文章[W.
p
p*
p*
p*
例子：考虑域 Z 13* {1, 2,3, 4,5,6,7 ,8,9,10 ,11,12 } 。这个域的生 成元是 2，因为其中的每个元素都可以由 2 的某一 a 次方幂生成，其中 0 a 11 ；即
2
2
0
mod 13 = 1, mod 13 = 3, mod 13 = 5, mod 13 = 7, mod 13 = 9, mod 13 = 11,
1． Alice 和 Bob 确定一个适当的素数 p 和整数

，使得

是 p 的本原根；

aA
和 p 可以公开。 ， y 计算
A
2． Alice 秘密选取一个整数 并把
yA

aA
mod p
发送给 Bob。
aB
3． 秘密选取一个整数 Bob 并把
yB
， 计算 y
B
B

aB
mod p
发 送 给 Alice 。 y 和 y 就 是 所 说 的
aABiblioteka aBmod p )
aBa A
aA
mod p
)
)
mod p
mod p (
mod p
aB
aA
aB
aA
mod p )
mod p
(yA)
aB
mod p
安全性 Diffie-Hellman 密钥交换的安全性是基 于这样的假设：从
aA
yA
或者
yB
以及 计算
或
aB
在计算上是不可行的；因为这等价于
Diffie-Hellman第一个提出了公钥密码算法。 这个算法本身基于计算离散对数的难度，其目 的是实现两个用户之间安全地交换密钥以便于 后续的数据加密。直到现在， Diffie-Hellman 密钥交换算法仍然在许多商用产品中使用。 如果Alice和Bob希望使用Diffie-Hellman密钥 交换协议在一个不安全的信道上交换密钥，他 们可以这样做：
A A B B B
B
B
（二）EIGamal算法 （基于离散对数的又一种可用于加密 和认证的公钥密码算法）
背景知识 ElGamal 密码系统是 ElGamal 设计的， 1984 于 年发表。 这一体制基于有限域上离散对数问题的困 难性。域实际上是一个群，并具有附加性质：域中 每一个非零元素都有乘法逆元。 p 是素数，Z 设 就是有限域的一个例子。这个域由元素集合 {0 ,1, 2 , , p 1} ，模 p 的加法运算和模 p 的乘法运 算组成。另一个有限域的例子是 Z ，其中的所有 元素都与 p 互素。 Z 还具有另外一个特性：它 是一个循环域。换言之，任意元素 Z 都可以 由一个生成元 g 的 a 次幂生成， 其中 0 a p 2 。
的一个特别概览，参看 Boneh[D. Boneh. Twenty years of
attacks on the RSA cryptosystem. Notices of the American Mathematical Society, 46(1999), 203—213.]。
（一）Diffie-Hellman密钥交换
二、RSA算法
1、Whitefield Diffie和Martin Hellman [DH76] 于1976年提出了公钥密码系统的思想，然而他们 并没有给出一个实用的公钥密码系统。DiffieHellman的文章发表两年后，MIT的Ronald Rivist、Adi Shamir和Len Adlemar[RSA78]开发 出了第一个公钥密码体制---RSA密码体制。 2、RSA是一种分组密码算法，基于大整数n分解为 两个素数之积的难解性，其输入明文和输出密文 都是0到（n-1）之间的整数。
一、公钥密码系统原理
1、公钥密码应用模型 (1)、公钥加密私钥解密； （2）、私钥加密公钥解密； （3）、上述两种方法相结合即为数字签名 2、公钥密码算法的要求（六条）
1 、 k
2 、 C
p
, k c的 生 成 ；
E k pb M
kc b

kc b k pb
3 、 M D C D E M 4 、 通 过 公 钥 推 导 私 钥 在 计 算 上 是 不 可 能 的 。 5 、 通 过 公 钥 和 密 文 获 得 明 文 在 计 算 上 是 不 可 能 的 。
d
共享密钥的通信。Bob 将是唯一能够利用解密规则 （称为私钥）对密文进行解密的人。
公 钥 密 码 体 制 的 思 想 是 在 1976 年 由 Diffie和Hellman提出的。然后在1977年由 Rivest, Shamir和Adleman发明了著名的RSA 密码体制，将在本讲中研究。此后，几个公 钥密码体制被提出，其安全性依赖于不同的 计算问题。其中，最著名的是RSA密码体制 （及其变种），其安全性基于分解大整数的 困难性；ElGamal密码体制（及其变种，例 如：椭圆曲线密码体制），其安全性基于离 散对数问题。我们在本讲中讨论RSA密码体 制和它的变种、ElGamal密码体制。
6 、 M
D kc
E
kp
M
Dk p
E M
kc
公钥密码系统原理（续）
3、上述要求的实现，实质上是要构造一个单向函数。 4、公钥密码系统受到的攻击和防范： 强行攻击 增加密钥长度，控制算法复杂性； 通过公钥推导对应的私钥； 对于公钥加密的短消息，存在的另一种攻击是可能字攻击。
在Diffie和Hellman之前，公钥密码学的思 想已经由James Ellis在1970年1月的一篇题为 “非隐秘加密的可能性”的文章中（短语“非 秘密加密 ” 即是 公 钥密 码 学 ） 提 出。 James Ellis是电子通讯安全小组（CESG）的成员， 这个小组是英国政府通讯司令部（GCHQ）的一 个特别部门。这篇文章没有在公共文献中发表， 而是在1997年12月由GCHQ正式解密的五篇文章 中的一篇。在这五篇文章中，还有一篇由 Clifford Cocks在1973年发表的题为“关于非 秘密加密的注记” 的文章，其中描述的公钥 密码体制跟RSA密码体制基本一致。
Diffie, The first ten years of public—key cryptography. In Contemporary Cryptology, The Science of Information Intefrity, pages 135—175. IEEE Press, 1992.]关于 RSA
A B A A A A
认证Diffie-Hellman密钥交换（续）
Bob 可以用 Alice 的公开验证算法来确定 sig ( y ) 是否真是 Alice 对 y 的签名。同样，Bob 对 y 签名并把 y 和 sig ( y ) 同时送给 Alice，她 能够利用 Bob 的公开验证算法来判断 sig ( y ) 是否 Bob 对 y 的签名。 这样双方都能够确定他们从对 方那里所收到的消息有没有被窜改过。因此， Alice（或 Bob）就不会受到欺骗：收到了 Eve 的 消息用来生成密钥，却误以为这些消息来自 Bob （或 Alice） 。
在公钥密码体制中的一个想法就是：可以找到一个 密码体制使得由给定的 果这样的话，加密规则