1976年 Diffie和 Hellman提出公钥密码思想以来，国际上
提出了许多种公钥密码体制的实现方案。一些已经被攻破，
一些被证明是不可行的。目前，只有 3类公钥密码体制被认
为是安全有效的，按照其所依据的数学难题划分为：基于大
整数分解问题（I FP） ，如R SA体 制和R abin体制；基于有限
域离散对数问题 (DLP) ，如 Diffie-Hellman 体制和 ElGamal体
制；基于椭圆曲线离散对数问题（ ECDLP），如椭圆密码
体制。椭圆曲线应用到密码学上最早是由 Neal Koblitz和
Victor Miller 在 1985年分别独立提出的。它是目前已知的公
钥体制中，对每一比特所提供加密强度最高的一种体制。它
具有安全性高、密钥量小、灵活性好的特点，受到了国际上
的广泛关注。而 SET(Secure Electronic Transaction)协议的制
定者已把它作为下一代S ET协议中缺省的公钥密码算法。深
入研究基于椭圆曲线离散对数问题的公钥密码具有很大的现
实意义。
1 椭圆曲线
1.1 椭圆曲线的定义
若 定义给定域G 上 的三元齐次 Weierstrass方程：
Y
2
Z+a
1
XYZ+a
3
YZ
2
=X
3
+a
2
X
2
Z+a
4
XZ
2
+a
6
Z
3
(a
i
∈G )满足
条件
Z
F
Y
F
X
F
?
?
?
?
?
?
,,
F (X,Y,Z)()≠(0,0,0)
时，W eierstrass 方程在射影平面P
2
(G)中所有解组成的集合
E： {(X, Y, Z)∈ P
2
(G)|F(X, Y, Z)=0且 X , Y, Z 不会为0 }∪
{O}称 为域G 上 的椭圆曲线E.
P
2
(G) 由仿射平面A
2
(G)添加一条虚直线（其上的点为虚
点）而成。
Z
Y
y
Z
X
x = ,=
令 代入
E： y
2
+a
1
xy+a
3
y=x
3
+a
2
x
2
+a
4
x+a
6
称为仿射平面A
2
(G) 上的椭圆曲线方程，其中的虚点为（0 ，
1 ，0 ）。
在实际的密码学应用中，主要研究和应用的椭圆曲线
方程有以下两种：
(1) 有限域上的椭圆曲线 F
q
( 表示q 个 元素的有限域)
y
2
=x
3
+ax+b 其中a ,b ∈F
q
, 满足4a
3
+27b
2
≠0
(2) 有限域上的椭圆曲线 F
2
m
y
2
+xy =x
3
+ax
2
+b 其 中a ,b∈ F
2
m
，b≠0
1.2 椭圆曲线离散对数问题
若给定一条有限域 Fp 上的椭圆曲线E (Fp) ，G 为 E上的一
点，则 E 上关于G 的 ECDLP 为：给定一点Q , 求解整数 r,使得
rG=Q(rG为 倍乘，即 r个 G相 加) 。对该系统的攻击依赖于在
Fp上 求解方程：G r≡ Q mod P 或r=log
G
Q mod P。 DLP求解是
非常困难的， ECDLP 比有限域上的 DLP更 难求解。在 Fp上
选择一条椭圆曲线E 及 一个具有较高阶的基点G∈E (Fp)，计
算该点的倍乘r G， 相对来说较容易，但已知G 和 rG 要求 r则
是很困难。基于椭圆曲线密码的安全性最终归结为解
ECDLP 问题。当数据量足够大以致此 ECDLP问题无法解决
时，认为该密码体制是安全的。
2 建立椭
圆曲线公钥密码体制
2.1 椭圆曲线域的参数
在基于椭圆曲线的加解密和数字签名的实现方案中，首
先要给出椭圆曲线域的参数来确定一条椭圆曲线。在 IEEE
P1363 标准中，定义其参数为一个七元组： T=(q,FR,a,b,G，
n,h), 其中q 代表有限域G F(q) ，q 为 素数或2
m
; FR为域表示法，
如 f(x)为 F
2
m
域元素的不可约多项式的表示法；曲线的方程，
当 q为 素数时，方程为y
2
=x
3
+ax+b， 当q 为 2
m
时，方程为y
2
+xy
=x
3
+ax
2
+b. a,b 是方程中的系数；G 为基点；n 为大素数并且等
于点 G的 阶， h 是小整数称为余因子且 h=#E(Fq)/n. 主要的安
基金项目：云南省信息网络开发技术专项计划资助项目：“基于安
全操作系统平台的 PKI 网络信息软件系统”（ 20011710）；云南省
自然科学基金资助项目：“基于网络信息安全的椭圆曲线密码算法
研究”（ 2002F0010M）
作者简介：张 雁（ 1973—），女，硕士生，研究方向：信息安
全；林 英，硕士生；郝 林，硕导
收稿日期：2002-12-05 E -mail ： zy10@https://www.doczj.com/doc/363742144.html,
椭圆曲线公钥密码体制的研究热点综述
张 雁，林 英，郝 林
(云南大学信息学院计算机科学系 ， 昆明 650091)
摘 要 ：椭圆曲线密码体制是公钥密码中的研究热点。该文介绍了椭圆曲线密码体制的基本概念及相关知识，讨论了目前基于椭圆离散对数
问题的椭圆曲线密码的研究动态，并指出今后的研究方向和重点。
关键词：椭圆曲线密码体制；椭圆曲线离散对数问题；椭圆曲线；阶；倍乘
Summarize of Elliptic Curve Cryptosystem Research
ZHANG Yan, LIN Ying, HAO Lin
（ Department of Computer Science, College of Information, Yunnan University, Kunming 650091）
【Abstract】Elliptic curve cryposystem is research hotspot in the public_key cryptography. This paper introduces the basic concept of ECC and some
correlative contents, and discusses the trends of research in the ECC based on elliptic curve discrete logarithm problem(ECDLP) and points out the
heading of the research .
【Key words】Elliptic curve cryptosystem(ECC) ; ECDLP; Elliptic curve; Order; Scalar multiplication
第 30卷 第 3期
Vol.30 № 3
计 算 机 工 程
Computer Engineering
2004年 2月
February 2004
·安全技术· 中图分类号：
文章编号： 1000— 3428(2004)03 — 0127— 03 文献标识码：A TP309
—1 27—全性参数是n ， 因此E CC密 钥的长度就定义为 n的长度。
2.2 椭圆曲线密码的密钥
选取了基域 Fq 和椭圆曲线后，得到了在有限域 Fq上的
曲线E 确定的具体的形式，即上述的椭圆曲线域参数的一个
七元组。每个用户选取一个整数d(1≤d
Q =dG(G 为基点) 作其公钥，这样形成一个椭圆曲线公钥
密码系统。在这个密码体制中，具体的曲线，基域F q，基
点 G 及其阶 n，以及每个用户的公钥都是该系统的公开参
数，每个用户的私钥是保密的。
2.3 基于椭圆曲线密码体制的加解密
假设用户 A 欲将明文 m 加密后发送给 B ，A 执行以下操
作：
(1) 查 找B 的公钥(E(F
q
),G,n,Q
B
)；
(2) 将 m 表示成一个域元素，即m∈F
q
；
(3) 在 区间 [1 ， n-1]内 选取一个随机数 k；
(4) 计算点kG=(x
1
,y
1
)；
(5) 依 据B 的公钥计算点kQ
B
=(x
2
,y
2
), 若x
2
=0，则返回到第 (3)步；
(6) 计 算 C=m× x
2
;
(7) 传 送加密数据（x
1
,y
1
,C ）给B.
B收 到A 的 密文（x
1
,y
1
,C）后，执行以下操作。
(1) 使 用私钥d
B
，计算点d
B
(x
1
,y
1
)=(x
2
,y
2
) ，再计算F
q
中的(x
2
)
-1
；
(2) 计算m=C(x
2
)
-1
，得到明文m.
3 椭圆曲线密码的研究动态
3.1 椭圆曲线密码的安全性
ECC的安全性是建立在离散对数问题计算难度基础之
上，如果离散对数可以计算，从一个用户的公钥就可得到他
的私钥， ECC 就不安全了。对于一般的 ECDLP，目前有两
种较好的求解法
[5]
： Pohlig-Hellman 方法和 Pollard-ρ方法。
但对于两类特殊的椭圆曲线，已经有了其他有效的求解方
法。一类特殊的椭圆曲线——超奇异椭圆曲线
[6]
（设 Fq的特
征为 p ，当 E/Fq 的 q 阶F robenius 变换的迹 t 是 p 的倍数时， E称
为超奇异的），采用概率亚指数算法—— MOV算 法和 FR算
法可以解决 ECDLP. 另 一类特殊椭圆曲线是异常(anomalous)
椭圆曲线
[6]
（设q=p
m
，p≠2 ,3 为素数，E /Fq 由方程y
2
=x
3
+ax+b
定义， P ∈ E(Fq) 的阶为 p. 当 p=q 时，异常曲线上的 p阶
Frobenius变 换的迹t =1） ， SSSA 算法可以解决ECDLP.
3.2 椭圆曲线的选取
要保证椭圆曲线密码的安全性，就是要使所选取的曲线
能抵抗上述的关于 ECDLP解决的方法和算法，所以选取一
条安全的椭圆曲线，是一个深刻的数学难题，在此，仅提供
几点椭圆曲线选取的安全准则
[3]
：
(1) 为了抗击P
ollard-ρ攻击，所选取E C 的阶# E(GF(q))的分解式
中应该包含一个大的素数因子，目前应不小于 160bit；
(2) 为了抗击 对和 对的攻击，对于 ≤W
eil Tate 1 k≤3 0 ， n不能除
q
k
-1（不宜选取超奇异椭圆曲线）；
(3) 为了抗击 的攻击所选曲线的阶不
Semaev-Smart-Satoh-Araki
能完全等于该曲线所定义于的有限域的阶，即 #E(Fq) ≠ q（不宜选
取异常椭圆曲线）；
(4) 对于二进制域
GF(
2
m
) 的度 m 不宜为合数。 Gaudry,Hess和
Smart 提出，若m 有小约数 l（ l =4 ），存在比 Pollard's rho算法更快求
解 ECDLP的方法。
下
面介绍3 种选择适宜的椭圆曲线的方法：
(1) 仅 限于有限域为F
2
m
上构造椭圆曲线。其原理是将定义在特
征值比较小的有限域的椭圆曲线提升到该域的扩域上去，并且 m能
被小整数k ≥1 整除。这种方法简单，但是得到的曲线较少。
(2) CM(Complex Multicaplication)法，根据给定的阶来选取符合
此阶的椭圆曲线。它的实现速度相对较快，但这种方法产生的椭圆
曲线具有附带的结构特征。从安全性角度来说，这是一个潜在的威
胁。
(3) 随机选取曲线。随机选取曲线的参数 a,b ∈ Fq( 如果 q是素
数，则满足4a
3
+27b
2
≠ 0;如 果q=2
m
，则 b ≠ 0) ，然后计算 u=#E(Fq)和
大素数因子 n，直到所选曲线满足安全需求。这种方法比较理想，
选取的曲线安全级别高，它完全依赖于椭圆曲线阶的计算。
3.3 椭圆曲线阶的计算
从上述椭圆曲线的安全性来看，如果曲线的阶充分的
大，平方根攻击如 Shanks's baby-step gaint-step 或Pollard's ρ
方法就不太有效，要能抗击 Pohlig-hellman攻击，一个好的
策略是确保曲线的阶# E(Fq)中包含有大素数因子（该大素数
n
作为所选取基点P 的 阶）, 使 得 Pohlig-hellman算 法的O()
计算量不能实现。由此看来，计算 #E(Fq)是研究定义在有限
域上的椭圆曲线的一个核心问题。
对于# E(Fq)的计算是一个纯粹的数学问题。目前有两种
方法可以采用：
(1) 随机选取一条定义于有限域F q的椭圆曲线，直接计算该曲
线的阶，使其满足 #E(Fq) 中包含有大素数因子。在这方面，R.
School做 了开创性的工作，提出了著名的 School 算法，后经 Atkin和
Elkies 的改进，提出了 SEA(School Elkies Atkin)算 法 。 后 来 ，
Morain,Lercier 等人又对它作了一些优化，如今 SEA算法已成为计算
椭圆曲线阶的有效算法。另外， Satoh 也提出了比较有效的 Satoh算
法及目前对于二进制域效率较高的 Satoh-FGH算法。
(2) 仅 限于有限域为F
2
m
且它要求所定义的F
2
m
有限域中的 m能分
解为m =de ，其中d 为一个小整数，通过计算小域F
2
d
上的#E(F
2
d
)， 从
而计算出#E(F
2
d
e).这种方法简单易实现，但是适用范围较小，不能
计算出任意 m或 固定 m的 #E(F
2
m
).
3.4 椭圆曲线的快速算法
在椭圆曲线密码体制应用中的大量运算是倍乘（数
乘），就是一串点的加法运算，即计算k*P=P+P+…+ P 共有k
个 P相 加。椭圆曲线密码快速实现的关键就是快速实现 kP的
运算（包括算法优化和程序优化、软件实现和硬件实现）。
其中 kP的运算主要基于两方面的运算：基域上域元素和曲
线上点的运算。这些运算与我们所选取的有限域、采用的坐
标系、基域中的元素表示方法、选取怎样的椭圆
曲线和计算
kP的方法有关。因为同一基域中的元素表示方法不一样
（如F
2
m
中有多项式和通项表示法）；不同的坐标系（如仿
射坐标和射影坐标）下，都会影响 kP的计算量。对于一些
特殊的曲线，如K oblitz curves，已经有了较好的算法，但是
对一般随机的椭圆曲线，如何快速计算 kP仍是一个需要研
究的问题。
4 结束语
椭圆曲线密码是一种能适应未来通信技术和信息安全技术发
展的新型密码体制，它在运算速度和存储空间方面占有很大
的优势，目前它已成为公钥密码体制中的研究热点。从上述
的分析可看出，椭圆曲线密码的主要研究方向有3 个方面：
(1) 如 何快速选取安全性高的椭圆曲线。( 2) 如何有效计算椭
圆曲线的阶。因为选取安全椭圆曲线的核心步骤是对椭圆曲
线阶的计算，对计算椭圆曲线阶的有效算法的研究也是实现
安全椭圆曲线密码体制的一个极其重要的环节。( 3) 在椭圆
曲线密码体制中，椭圆曲线群上点的倍乘占了整个运算的很
大比例，它的效率关系到整个体制的执行效率。对椭圆曲线
中的k P倍乘计算仍需研究一种高效快速的方法。
—1 28—
（上接第7 0页）
于地址寄存器，比如I 0~I8，
就是一个寄存器文件。这样
设计有利于旁路电路的设
计，而且可以使控制信号不
是很多。
由于 MD16有并行乘法
器，这使得至少需要一个附
加寄存器类来存放乘法结
果。当指令格式采用编码指
令形式后，对于一些源和目
的寄存器的选择将有所限
制，而这也使得要附加另外
一类寄存器。
2.7 控制流
很多 DSP都支持标准的
控制流指令，比如条件跳转
等。而且分支不利情况是很
少的。 DSP算法的共同特征
在于大部分处理时间花在执行包含在相对小循环内的少量指
令。因此， MD16处理器具有零开销循环控制的专门硬件。
零开销循环是指处理器不用花时间测试循环计数器的值就能
执行一组指令的循环，硬件完成循环跳转和循环计数器的衰
减。这就允许了执行重复的算法而不花费分离的周期在循环
控制上。很多运算或者移动指令都是条件执行的。在很多具
体的例子中，这就避免了条件载入 PC值的开销。所以对于
MD16 部分指令也是采用条件执行的控制。而且在M D16中
一些算术操作可以是由一些寄存器中的某一位的值来控制
的。
3 结果和总结
根据上面所述的方法而设计的D SP核 结果如图 3所示。
整个M D16 硬件核都是由V erilog HDL进 行R TL级描述，
用 Synopsys 公司 DC把该核综合成门级网表，这里我们采用
0.35μ m CMOS标准单元库，实现了本设计，综合出来关键
路径延时为 8.81ns， 不包括片上存储器约有3
万门大小。
本文对于嵌入式D SP核的设计从编译技术的角度提出了
设计方法，并根据确定结构可重定目标能力的参数来考虑设
计了一个 16 位定点D SP 核。由此方法设计的D SP处理器的结
构有着与编译器产生的代码紧密结合的特点。从另一个角度
讲也可以说是编译器产生的代码具有高质量、高效率的特
点。
参考文献
1 Goossens G, Van Praet J, Lanneer D, et al. Embedded Software in
Realtime Signal Processing Systems: Design Technologies. Proceedings
of the IEEE, 1997,85(3):436-454
2 Lanneer D, Van Praet J, Kifli A, et al. CHESS: Retargetable Code
Generation for Embedded DSP Processors. In Code Generation for
Embedded Processors, Kluwer Academic Publishers, 1995: 85-102
3 Liem C, Paulin P. Compilation Techniques and Tools for Embedded
Processor Architecture. In Hardware/Software Co-design: Principles
and Practice, Kluwer Academic Publishers, 1997: 149-191
4 Bang K H, Jeong N H. Design and Vlsi Implementation of a Digital
Audio-specific DSP Core for MP3/AAC. Consumer Electronics,
ICCE. 2002 Digest of Technical, 2002
5 Hennessy J L, Patterson D A. Computer Architecture: A
Quantitative Approach. Morgan Kaufmann, 2002-05
参考文献
1 IEEE,P1363: Standard Specifications for Public Key Cryptography.
Draft (Version 13), https://www.doczj.com/doc/363742144.html,/groups/1363/P1363/draft.
html, 1999-11-12
2 Certiom. ECC Challenge. https://www.doczj.com/doc/363742144.html, /research
3 Lopez J, Dahab R. An Overview of Elliptic Curve Cryptography.
Technical Report, Institute of Computing, State University of Camp-
inas, Brazil, 2000-05-22
4 Kolitz N, Menezes A, Vanstone S. The State of Elliptic Curve
Cryptography. Designs,Codes,and Cryptography, 2000,19: 173-193
5 李学俊 , 敬忠良等 . 基于椭圆曲线离散对数问题的公钥密码 . 计算
机工程与应用, 2002,38(6):20-22
6 斐定一 , 祝 跃飞. 算法数论 . 北 京：科学出版社，2002
—1 29—