基于椭圆曲线密码的 Diffie-Hellman 密钥交换
陈永玲
河海大学计算机及信息工程学院 江苏南京 (210098)
摘要：本文介绍了在实数域和有限域中椭圆曲线的基本定义，然后以椭圆曲线的基本定义为基础，详细论
述了基于椭圆曲线密码的 Diffie-Hellman 密钥交换的基本原理及利用椭圆曲线实现密钥交换的方法，分
析了 Diffie-Hellman 密钥交换技术的优缺点，并给出了值得改进的地方。 Diffie-hellman 密钥交换技
术被许多商业产品广泛采用，它的主要目的是使两个用户能安全地交换密钥，以便在后续的通信中用该密
钥对消息加密。
关键字：椭圆曲线，椭圆曲线密码， Diffie-Hellman 算法，密钥交换
中图分类号：
1. 引言
椭圆曲线已研究很多年，1985年，Neal Koblitz 和 分别提出将它用于公开密
钥密码体制[1][2]。他们没有发明有限域上使用椭圆曲线的新的密码算法，但他们用椭圆曲线
实现了已经存在的公开密钥密码算法，如 Diffie-Hellman 算法[3]，由于该算法本身限于密钥
交换的用途，被许多商用产品用作密钥交换技术，因此该算法通常称为 Diffie – Hellman 密
钥交换。这种密钥交换技术的目的在于使得两个用户安全的交换一个秘密密钥以便用于以后
的报文加密。
2. 椭圆曲线密码
Abel 群
Abel 群 G 由元素的集合及其上的二元运算 * 组成，有时记为 {G，*}。将 G 中的
元素序偶 (a，b)与 G 中的元素 (a * b) 对应，使得下述公理成立：
a) 封闭性 若 a 和 b 属于 G，则 a * b 也属于 G。
b) 结合性 对 G 中任意的 a，b 和 c，a * (b * c) = (a * b) * c
c) 单位元 G 中存在元素 e，使得对 G 中所有的 a * e = e * a = a
d) 逆元 对 G 中任何 a，存在 G 中元素 a * a’ = a’ * a = e
e) 交换性 对 G 中任何 a 和 b，有 a * b = b * a
实数域上的椭圆曲线
椭圆曲线密码[4]使用椭圆曲线上称为加法的运算，乘法定义为重复相加。椭圆椭圆曲线
是一个具有两个变元的方程。对于密码学而言，变元和系数均限制于有限域上，在讨论之前，
首先来讨论变元和系数均是实数的椭圆曲线。
1
一般所用到的椭圆曲线的方程为：
2 3y x ax b= + + ……………(1)。
椭圆曲线的定义中还包含一个成为无穷远点或零点的元素，记为：O。
满足等式(1)的所有点(x，y)和元素O所组成的点集为 E(a，b)。a，b的值不同，则相应
的集合 E(a，b)也不同。
例 1：椭圆曲线 2 3y x x= - 和椭圆曲线 2 3 1y x x= + + 可以分别用 E(-1，0)E(1,1)表示。
椭圆曲线上加法的几何描述
如果椭圆曲线
2 3y x ax b= + + 满足条件：
3 24 27 0a b+ ¹ ，则可基于集合 E(a，b)
定义一个 Abel群 (封闭性，结合性，单位元，逆元，交换性)。在 E(a，b)上定义加法运算，
用“+”表示。几何描述定义加法的运算规则：若椭圆曲线上的三个点同在一条直线上，则
它们的和为 O。
1) O是加法的单位元。这样有 O = -O；对椭圆曲线上的任何一点 P，有 P+O=P。
下面假定 P≠Q且 Q≠O。
2) 点 P的负元是具有相同 x坐标和相反 y坐标的点(即若 P(x，y)，则-P=(x，-y))。
这两个点可用一条垂直的线连接起来，并且 P+(-P)=P-P=O。
3) 要计算 x坐标不相同的两点 P和 Q之和，则在 P和 Q间作一条直线并找出第三个交
点 R，显然存在有唯一的交点 R(除非这条直线在 P和 Q处与该椭圆曲线相切，此时我们分别
取 R=P 或 R=Q)。所以三个点上的加法为：P+Q=-R，即定义 P+Q 为交点 R 的镜像（相对于 x
轴）。
4) 具有相同 x坐标的两个点 P和-P，用一条垂直的线连接这两点，也可以看做是在无
穷远点处与曲线相交，因此有 P+(-P)=O。
5) 计算点 Q的 2倍，画一条切线并找出另一交点 S，则 Q+Q=2Q=-S。
加法的代数描述
对不是互为负元的两个不同的点 ( , )p pP x y= 和 ( , )q qQ x y= ，连接它们的曲线 L的斜
率 ( ) /( , )q p q py y x xD = - 。L恰与椭圆曲线相交于另一点，即 P与 Q之和的负元。
利用某些代数运算，我们可以如下表示和：
R = P + Q：
2
( )
r p q
r p p r
x x x
y y x x
ì = D - -ï
í
= - + D -ïî
此加法满足普通加法的性质，如交换律和结合律。因此定义正整数 k乘以椭圆曲线上的
点 P为 k个 P之和。因此有 2P = P + P，3P = P + P + P等。
2
如果 P = Q，就变为自身相加，即 2P = P + P = R。所以，当 0py ¹ 时，表达式为：
2
2
2
3
( ) 2
2
3
( )( )
2
p
r p
p
p
r p r p
p
x a
x x
y
x a
y x x y
y
ì +
= -ï
ï
í
+ï = - -ï
î
pZ 上的椭圆曲线
对于 pZ 上的椭圆曲线
[5]
，使用变元和系数均在 0到 p-1的整数集上取值的三次方程，
所执行的计算均是模 p运算。与实数时的情形一样，限制方程具有等式(1)所示的形式，但
是系数和变元均限制在 pZ 中：
2 3mod ( ) mody p x ax b p= + + ………………………..(2)
( , )pE a b 上的加法运算构造与定义在实数上的椭圆曲线中描述的代数方法是一致的。
若
3( ) modx ax b p+ + 无重复因子，即 3 2(4a +27b )mod p 0mod p¹ 则基于集合E ( , )p a b
可以定义一个有限 Abel群。
若 ( , )p pP x y= ， ( , )q qQ x y= ，且 P Q¹ - ，则 R=P+Q= ( , )r rx y 。由下列规则确定：
2( ) mod
( ( ) ) mod
r p q
r p r p
x x x p
y x x y p
l
l
ì = - -ï
í
= - -ïî
其中：
2
( ) mod ............................................... P Q
3
( ) mod ............................................... P Q
2
q p
q p
p
p
y y
p
x x
x a
p
y
l
-ì
¹ï -ï= í
+ï =ï
î
若
若
例 2 详细说明 pZ 椭圆曲线上的加法运算：
考虑椭圆曲线 2 3y x ax b= + + ，a=b=1，p取 23。构成了 23E (1,1)。
下表所示椭圆曲线 23E (1,1)上的点：
表 1 椭圆曲线 23E (1,1)上的点
(0，1) (6，4) (12，19)
(0，22) (6，19) (13，7)
3
(1，7) (7，11) (13，16)
(1，16) (7，12) (17，3)
(3，10) (9，7) (17，20)
(3，13) (9，16) (18，3)
(4，0) (11，3) (18，20)
(5，4) (11，20) (19，5)
(5，19) (12，4) (19，18)
在 23E (1,1)上取 P = (3，10)，Q = (9，7)，
那么：P + Q = ？
首先计算l，
7 10 3 1( ) mod 23 ( ) mod 23 ( ) mod 23 11
9 3 6 2
l
- - -
= = = =
-
然后计算： 2(11 3 9) mod 23 109 mod 23 17rx = - - = =
(11*(3 17) 10) mod 23 164mod 23 20ry = - - = - =
所以：P + Q = (17，20)。
计算 2P = ？
首先计算l：
23(3 ) 1 5 1( ) mod 23 ( ) mod 23 ( ) mod 23 6
2 *10 20 4
l
+
= = = = 。(需要求 4在 23Z 中
的乘法逆元)。
然后计算： 2(6 3 3) mod 23 30 mod 23 7rx = - - = =
(6(3 7) 10) mod 23 34 mod 23 12ry = - - = - =
所以：2P = (7，12)。
3 Diffie–Hellman 密钥交换
Diffie 和 Hellman 在一篇具有独创意义的论文中首次提出了公钥算法，给出了公钥密
码学的定义，该算法通常称为 Diffie – Hellman 密钥交换。该算法的目的是使两个用户能安
全地交换密钥，以便在后续的通信中用该密钥对消息加密，该算法本身只限于进行密钥交换。
Diffie – Hellman 密钥交换过程如下（见图 1）：
4
图 1 Diffie – Hellman 密钥交换算法
在这个方法中，素数 q 及其本原根 a 是两个公开的整数。假定用户 A 和 B 希望交
换密钥，那么用户 A 选择一个随机整数 AX q< ，并计算 modA
X
AY a q= 。类似的，用
户 Ｂ 也独立地选择一个随机整数 BX q< ，并计算 modB
X
BY a q= 。A 和 B 保持其
X 是私有的，但对另一方而言，Y 是公开可访问的。用户 A 计算 ( ) modAXBK Y q= 并
将其作为密钥，用户 B 计算 ( ) modBXAK Y q= 并将其作为密钥。这两种计算所得的结
果是相同的：
全局公开量
q 素数
a a < q 且 a 是 q 的本原根
用户 A 的密钥产生
选择秘密的 AX AX q<
计算公开的 AY modA
X
AY a q=
用户 B 的密钥产生
选择秘密的 BX BX q<
计算公开的 BY modB
X
BY a q=
用户 A 计算机产生密钥
( ) modAXBK Y q=
用户 B 计算机产生密钥
( ) modBXAK Y q=
5
( ) mod
( mod ) mod
( ) mod
mod
( ) mod
( mod ) mod
( ) mod
A
B A
B A
B A
A B
A B
B
X
B
X X
X X
X X
X X
X X
X
A
K Y q
a q q
a q
a q
a q
a q q
Y q
=
=
=
=
=
=
=
至此 A 和 B 完成了密钥的交换。此外，由于 AX 和 BX 是私有的，所以攻击者只
能通过 q，a， AY 和 BY 来进行攻击。这样，他就必须求离散对数才能确定密钥。例如，
要对用户 B 的密钥进行攻击，攻击者就必须计算：
, ( )B a q BX ind Y=
然后他就可以像用户 B 那样计算出密钥 K。
Diffie – Hellman 密钥交换的安全性建立在下述事实之上：求关于素数的模幂运算相对
容易，而计算离散对数却非常困难；对于大素数，求离散对数被认为是不可行的。
下面再简单举一个使用 Diffie – Hellman 算法的例子。假设有一组用户（例如一个局域
网上的所有用户），每个人都产生一个长期的私有密钥 AX ，并计算一个公开密钥 AY 。这
些公开密钥数值，连同全局公开数值 q 和 a 都存储在某个中央目录中。在任何时刻，用户
B 都可以访问用户 A 的公开数值，计算一个秘密密钥，并使用这个密钥发送一个加密报文
给 A。如果中央目录是可信任的，那么这种形式的通信就提供了保密性和一定程度的鉴别
功能。因为只有 A 和 B 可以确定这个密钥，其它用户都无法解读报文（保密性）。接收方
A 知道只有用户 B 才能使用此密钥生成这个报文（鉴别）。
4 用椭圆曲线密码实现密钥交换
利用椭圆曲线可按如下方式实现迷药交换。首先，挑选一个大整数 q 以及椭圆曲线参
数 a 和 b，这里 q 为素数 p 或是形为 2m 的整数。由此可以定义出点的椭圆群
( , )qE a b ；其次，在 ( , )qE a b 中挑选基点 1 1( , )G x y= ，G 的阶为一个非常大的数 n。椭
圆曲线上点 G 的阶 n 是使得 nG = O 成立的最小正整数。 ( , )qE a b 和 G 是该密码体制
中通信各方均已知的参数。
用户 A 和用户 B 之间完成密钥交换的过程如下（见图 2）：
6
图 2 ECC密钥交换
1) A 选择一个小于 n 的正整数 An 作为其私钥，然后产生其公钥 A AP n G= ´ ；该公
钥是 ( , )qE a b 中的一点。
2) B 可类似得选择私钥 Bn 并计算公钥 BP 。
3) 产生秘密密钥 A BK n P= ´ ，B 产生秘密密钥 B AK n P= ´ 。
5 结论
本文给出了用椭圆曲线实现 Diffie-Hellman 密钥交换，Diffie-Hellman 密钥交换有
优点，也有其缺点，Diffie – Hellman 算法非常有吸引力的优点：
1) 仅当需要时才生成密钥，减小了将密钥存储很长一段时间而致使遭受攻击的机会。
2) 除对全局参数的约定外，密钥交换不需要事先存在的基础结构。
全局公开量
( , )qE a b 参数为 a, b 和 q 的椭圆曲线，其中 q 是素数或形为2
m 的整数
G 阶为 n 的椭圆曲线上的点，其中 n 是最大的整数
用户 A 的密钥产生
选择私有的 An An n<
计算公开的 AP A AP n G= ´
用户 B 的密钥产生
选择私有的 Bn Bn n<
计算公开的 BP B BP n G= ´
用户 A 产生秘密钥
A BK n P= ´
用户 B 产生秘密密钥
B AK n P= ´
7
然而除了上述的有点，该算法同样存在很多不足之处：
1) 没有提供双方身份的任何信息。
2) 它是计算密集性的，因此容易遭受阻塞性攻击，即对手请求大量的密钥。受攻击者
花费了相对多的计算资源来求解无用的幂系数而不是在做真正的工作。
3) 没办法防止重演攻击。
4) 容易遭受中间人的攻击。第三方 C 在和 A 通信时扮演 B；和 B 通信时扮演 A。
A 和 B 都与 C 协商了一个密钥，然后 C 就可以监听和传递通信量。中间人攻击按如下
进行：
a) B 在给 A 的报文中发送他的公开密钥。
b) C 截获并解析该报文。C 将 B 的公开密钥保存下来并给 A 发送报文，该报文具
有 B 的用户 ID 但使用 C 的公开密钥 CY ，仍按照好像是来自 B 的样子被发送出去。A
收到 C 的保温后，将 CY 和 B 的用户 ID 存储在一块。类似的，C 使用 CY 向 B 发送
好像来自 A 的报文。
c) B 基于私有密钥 BX 和 CY 计算秘密密钥 1K 。A 基于私有密钥 AX 和 CY 计
算秘密密钥 2K 。C 使用私有密钥 CX 和 BY 计算 1K ，并使用 CX 和 AY 计算 2K 。
5) 从现在开始，C 就可以转发 A 发送 B 的报文或转发 Ｂ 发给 A 的报文，在途中根
据需要修改它们的密文。使得 A 和 B 都不知道他们在和 C 共享通信。
为了克服 Diffie – Hellman 算法的缺点，可以选用 Oakley 算法，它保留了 Diffie –
Hellman 算法的优点，同时也克服了其缺点，这在以后的研究工作中将继续研究。
8
参考文献
[1] , “Elliptic Curve Cryptosystems” Mathematics of Computation, , ,1987, -209.
[2] . Miller, “Use of Elliptic Curves in Cryptography,” Advances, Springer-Verlag, 1986 -426.
[3] (美)Bruce Schneier 著；吴世忠，祝世雄 等译. 应用密码学：协议，算法与 C源程序. 北京：机械工业
出版社，
[4] (美) Stallings，W. 著；刘玉珍等译. 密码编码学与网络安全：原理与实践：第三版. 北京：电子工业出
版社，
[5] 李继国，余纯武，张福泰，马春光著. 信息安全数学基础. 武汉：武汉大学出版社，
Based on Elliptic Curves Cryptosystern Diffie-Hellman key
exchange
CHEN Yongling
Department of Computer and Information Engineer Hohai University, Nanjing Jiangsu 210098
Abstract
This paper introduces the real number domain and limited domain of the definition of Elliptic
Curves, it introduces the basic principles of Diffie-Hellman key exchange in detail which bases on the
definition of Elliptic Curve Cryptosystem, and the methods of implementation which makes use of
Elliptic Curve. It analysis the advantages and disadvatages of the Diffie-Hellman key exchange
technology , and gives a worthwhile improvement in the same time. Diffie-Hellman key exchange
technology has been widely used in many commercial products. Its main purpose is to enable two users
to safely exchange keys in order to follow-up communication with the message encryption key pair.
Key words: Elliptic Curve, Elliptic Curve Cryptosystem, Diffie-Hellman algorithm, key exchange
9
