返回信息流椭圆曲线密码(ECC)算法简介(一)
目 录
1、密码学的历史 2
1.1、密码学的发展阶段 2
1.2、公钥密码学 3
1.3、两种密码系统的结合 5
2、椭圆曲线 5
2.1、椭圆曲线 5
2.2、有限域上的椭圆曲线 7
2.3、DIFFIE-HELLMAN密钥交换协议 9
2.4、ELGAMAL密码体制 10
2.5、关键技术指标 11
2.6、安全性分析 11
2.6.1、ECC安全性的理论基础 11
2.6.2、ECC安全性的实现 12
3、椭圆曲线国际标准 15
4、椭圆曲线技术实现 16
4.1、运算层 16
4.2、密码层 16
4.3、接口层 18
4.4、应用层 18
4.5、ECC的实现效率 18
4.5.1、ECC密码机制 18
4.5.2、安全前瞻性 18
4.5.3、应用环境 19
4.5.4、算法优化 19
5、应用前景 19
1、密码学的历史
1.1、密码学的发展阶段
密码学是一门古老而又年轻的科学，它用于保护军事和外交通信可追溯到几千年前。在当今的信息时代，大量的敏感信息通过公共通信设施或计算机网络来进行交换，而这些信息的秘密性和真实性是人们迫切需要的。因此，现代密码学对于军事、政治和外交、商业的价值越来越重要。明文信息可以用两种办法之一来隐藏：一是信息隐蔽，即隐藏信息的存在，二是利用密码学方法通过对文本信息的不同转换而实现信息的对外不可读。
密码学的发展历史大致可划分为三个阶段：
第一个阶段为从古代到1949年。这一时期可看作是科学密码学的前夜时期，这段时期的密码技术可以说是一种艺术，而不是一种科学，密码学专家常常是凭借直觉和信念来进行密码设计和分析，而不是推理证明。例如，最早应用替代的凯撒密码。
第二个阶段为从1949年到1975年。1949年Shannon发表的“保密系统的信息理论”一文为对称密码系统建立了理论基础，从此密码学成为一门科学，人们将此阶段使用的加密方法称为传统加密方法，其安全性依赖于密钥的秘密性，而不是算法的秘密性，也就是说，使得基于密文和加解密算法的知识去解密一段信息在实现上不可能。
1977年美国国家标准局正式公布实施了美国的数据加密标准（DES），公开它的加密算法，并批准用于非机密单位和商业上的保密通信。密码学的神秘面纱从此被揭开。
第三个阶段1976年至今。1976年Diffie和Hellman的“密码学的新方向”一文导致了密码学上的一场革命。他们首次证明了在发送端和接收端无密钥传输的保密信息是可能的，从而开创了公钥密码学的新纪元。
在密码学的发展过程中，数学和计算机科学作出了卓越的贡献。数学中许多分支如数论、概率统计、近世代数、信息论、椭圆曲线理论、算法复杂性理论、自动机理论、编码理论等都可以在其中找到各自的位置。它的踪影遍及数学许多分支，而且还推动了并行算法的研究，从而成为近若干年来非常引人入胜的领域。
随着计算机网络不断渗透到各个领域，密码学的应用也随之扩大。数字签名、身份鉴别等都是由密码学派生出来的新技术和应用。
1.2、公钥密码学
公钥密码学是整个密码学发展历史中最伟大的一次革命，也可以说是唯一的一次革命。从密码学产生至今，几乎所有的密码系统都是基于替换和置换这些初等方法，几千年来，算法的实现主要是通过手工计算来完成的。随着转轮加密/解密机器的出现，传统密码学有了很大进展，利用电子机械转轮可以开发出极其复杂的加密系统，利用计算机甚至可以设计出更加复杂的系统，最著名的例子是Lucifer在IBM实现数据加密标准（DES）时所设计的系统。转轮机器和DES是密码学发展的重要标志，但是它们都是基于替换和置换这些初等方法之上。
公钥密码学与其前传统的密码学完全不同, 它的出现使密码学的研究发生了巨大的变化。与传统加密系统不同的是，使用这种方法的加密系统，不仅公开加密算法本身，也公开了加密用的密钥。首先，公钥算法是基于数学函数而不是基于替换和置换，更重要的是，与只使用一个密钥的对称传统密码不同，公钥密码学是非对称的，它使用两个独立的密钥。我们将会看到，使用两个密钥在消息的秘密性、密钥分配和认证领域有着重要意义。
目前的公钥密码系统主要依赖下面三种数学难题：
（I） 大整数因子分解问题
（II） 离散对数问题
（III） 椭圆曲线上的离散对数问题
第一类公钥系统是由Rivet，Shamir，Adelman提出的，简称为RSA系统，它的安全性是基于大整数因子分解的困难性，而大整数因子分解问题是数学上的著名难题，因而可以确保RSA算法的安全性。RSA系统是公钥系统的最具有典型意义的方法，自提出以来就一直是人们研究的焦点。对于密码破译者来说，在这种系统中，已知密文而想得出明文就必须进行大整数的因子分解。
从上述介绍中不难看出，RSA方法的优点主要在于原理简单，易于使用。但是，随着分解大整数方法的进步及完善、计算机速度的提高以及计算机网络的发展（可以使用成千上万台机器同时进行大整数分解），作为RSA加解密安全保障的大整数要求越来越大。为了保证RSA使用的安全性，其密钥的位数一直在增加，比如，目前一般认为RSA需要1024位以上的字长，显然，密钥长度的增加导至了其加解密的速度大为降低，硬件实现也变得越来越难以任受，这对使用RSA的应用带来了很重的负担，对进行大量安全交易的电子商务更是如此，从而使得其应用范围越来越受到制约。
第二类公钥系统的安全性依赖于离散对数的计算困难性（简称DLP问题）。设G为一个有限ABEL加法群，假定g为G的某个元，a为任意的整数，如果已知g及ag，如何求出整数a来的问题在数学上称为离散对数问题。一般说来，当群G选择得当，且整数a充分大时，求解此类问题是非常困难的。离散对数问题又可细分为两类，一类为某个有限域上的离散对数问题。一类为椭圆曲线上的离散对数问题。两者比较，后一类问题求解更为困难些。基于这一判断，人们通过对群G作出不同的选择时，构造了各种不同的公钥系统，比如，Massey-Omura公钥系统，ElGamal公钥系统等等。
第三类公钥系统是建立在椭圆曲线离散对数问题上的密码系统，称为椭圆曲线密码系统。众所周知，定义在某一代数数域上椭圆曲线上的有理点在适当的定义了零元素和运算规则(常记作加法)后，构成一个有限秩的Able 群。设GF(p)为一有限域，则GF(p)上的一条椭圆曲线E上的有理点构成一个有限群Ep，这个有限群的阶可经由某些特别方法计算出来，设已知属于Ep的点g和ag，从g和ag求出a来是非常困难的，此种问题称为椭圆曲线离散对数问题，它较通常的离散对数问题更为困难。椭圆曲线加密算法(Elliptic Curve Cryptography 简称ECC)是由Neal Koblit和Victor Miller于1985年首先提出，从那时起ECC的安全性和实现效率就被众多的数学家和密码学家所广泛研究。所得的结果表明，较之RSA算法，ECC具有密钥长度短，加解密速度快，对计算环境要求低，在需要通讯时，对带宽要求低等特点。近年来，ECC被广泛应用于商用密码领域，这可由ECC被许多著名的国际标准组织所采纳所佐证，如ANSI（American National Standards Institute）、IEEE、ISO、NIST（National Institute of Standards and Technology）。ECC最新的发展状况可参见2000年10月份在德国ESSEN举行的ECC国际会议上所发表的各种文献上。
1.3、两种密码系统的结合
在实际应用中，对称密码系统与公钥密码系统经常有两种结合方式：电子信封和交换会话密钥。
电子信封，指使用对称密码系统对明文加密，然后用公钥系统对对称密码的密钥加密，最后将明文加密结果和密钥加密结果，一起传给接收者；接收者接到数据后，先通过公钥系统解密出对称密码的密钥，再用对称密码系统解出明文。
交换会话密钥，指在实际通讯之前，通讯双方先使用公钥系统，共享一个随机的对称密码的密钥。然后，再用这个密钥，通过对称密码系统进行实质的数据交换。
这两种结合方式，都能够有效的发挥两种密码系统的优势，达到两全其美的效果。
2、椭圆曲线
2.1、椭圆曲线
简单的说，椭圆曲线并不是椭圆，之所以称为椭圆曲线是因为它们是用三次方程来表示的，并且该方程与计算椭圆周长的方程相似。一般而言，椭圆曲线的三次方程形为
y2 + axy + by = x3 + cx2 + dx + e
其中a,b,c,d和e是满足某些条件的实数，因为方程中的指数最高是3，所以我们称之为三次方程，或者说方程的次数为3。图1给出了椭圆曲线的两个例子，由图1中可知，上述方程有时对应的是一条怪异的曲线。
我们在椭圆曲线上定义加法运算。简单地说，可如下定义加法运算：若椭圆曲线上的三个点同在一条直线上，则它们的和为O（称为无穷远点或零点的元素）。从这个定义出发我们可以定义椭圆曲线加法的运算规则：
1．O是加法的单位元。这样有O ＝ －O；对椭圆曲线上的任何一点P，有P＋O＝P。
2．一条垂直的线与椭圆曲线相交于两点，这两点具有相同的x坐标，设为P1(x,y)和P2(x,-y)。这条直线与曲线也在无穷远点相交，因此P1＋P2＝O且P1＝－P2，因此一个点的负元是具有相同x坐标和相反的y坐标的点。图1说明了这一情形。
3．要计算x坐标不相同的两点Q和R之和，则在Q和R间作一条直线并找出第三个交点P1，显然存在有唯一的交点P1（除非这条直线在Q或R处与该椭圆曲线相切，此时我们取P1＝Q或P1＝R），因此Q＋R＋P1＝O，从而Q＋R＝－P1。图1说明了这种情形。
4．要计算Q的两倍，则作一条切线并找出另一交点S，那么Q＋Q＝2Q＝－S。
上述加法满足普通加法的性质，如交换律和结合律。我们定义正整数k乘以椭圆曲线上的点P为k个P之和，因此有2P＝P＋P，3P＝P＋P＋P，等等。
2.2、有限域上的椭圆曲线
在ECC中，我们关心的是某种特殊形式的椭圆曲线，即定义在有限域上的椭圆曲线。模p椭圆群对密码学具有重要意义（这里p是素数），选择两个小于p的非负整数a和b，它们满足
4a3 + 27b2 (mod p) 1 0
我们用Ep(a,b)表示模p椭圆群，其元素是满足下列条件的小于p的非负整数对(x,y)以及无穷远点O：
y2 o x3 + ax + b (mod p) (1)
例如，取p＝23，椭圆曲线y2＝x3+x+1，此时a=b=1。由于4′ 13 + 27 ′ 12 (mod 23) = 8 1 0，可见a和b满足模23椭圆群所要求的条件。
方程(1)即是图1b中给出的方程，该图显示了满足方程的所有的实数点所组成的连续曲线。对于椭圆群，我们只关心从（0，0）到（p，p）的满足上述方程的非负整数。表1列出了E23(1,1)上的部分点（除O外）。一般而言，可按如下方法生成该表：
1．对满足0 ￡ x < p的任何x，计算x3+ax+b (mod p)。
2．对步骤1中计算出的每个值，确定它是否有模p的平方根。若没有，则在Ep(a,b)上没有值为x的点，否则有两个平方根y（除非y为0），因此(x,y)是Ep(a,b)上的点。
表1 椭圆曲线E23(1,1)上的非负整数点
(0，1) (6，4) (12，19)
(0，22) (6，19) (13，7)
(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)
(6，19) (12，4) (19，18)
若将Ep(a,b)上的加法规则与图1所示的几何方法对应起来，则可如下描述加法运算：
1．P＋O＝P
2．若P ＝ (x,y),则P + (x,-y) = O。点(x,-y)是P的负元，记为－P。由图1可知，(x,-y)也是椭圆曲线上的点，并且也在Ep(a,b)中。例如，对E23(1,1)上的点P ＝ (13，7)，有－P ＝(13，-7)，而-7 mod 23=16，因此，－P = (13,16),该点也在E23(1,1)中。
3．若P ＝ (x1,y1)，Q ＝ (x2,y2)，且P 1 -Q则P + Q = (x3,y3)，其中(x3,y3)由下列规则确定：
x3＝l2－x1－x2 （mod p）
y3＝l(x1－x3) －y1 （mod p）
其中
可以分析如下两个例子：令P = (3,10)，Q = (9,7),那么
所以P＋Q＝(17，20)。下面计算2P。
可见2P＝(7，12)。
另外，乘法定义为重复相加，例如4P＝P＋P＋P＋P。
椭圆曲线的吸引人之处在于提供了由“元素”和“组合规则”来组成群的构造方式。用这些群来构造密码算法具有完全相似的特性，且没有减少密码分析的分析量。因为采用椭圆曲线就没有“平滑”的概念，也就是说，在一随机元素能以大的概率被一个简单算法表示的情况下，不存在小元素的集合。
2.3、Diffie-Hellman密钥交换协议
我们将ECC中的加法运算与RSA中的模乘运算相对应，将ECC中的乘法运算与RSA中的模幂运算对应，可以建立基于椭圆曲线的密码体制。其中，关键需要类似因子分解两个素数之积或求离散对数这样的“难题”。
考虑方程Q=kP，其中Q, P? Ep(a,b)且k < p。可以证明k和P计算Q比较容易，而由Q和P计算k则比较困难。
利用椭圆曲线实现密钥交换的原理是：首先，挑选一个素数p?2160以及方程为(1)的椭圆曲线的参数a和b，由此定义出椭圆群Ep(a,b)；其次，在Ep(a,b)中挑选生成元点G=(x1,y1)，G应使得满足nG ＝ O的最小的n是一个非常大的素数。Ep(a,b)和G是该密码体制的公开参数，可为通信各方所知。
比如，用户A和用户B之间密钥交换过程如下：
1．A选择一个小于n的整数nA作为其私钥，然后产生其公钥PA＝nA′G；该公钥是Ep(a,b)中的一个点。
2．B可类似地选择私钥nB并计算公钥PB。
3．A产生秘密钥K = nA′PB，B产生秘密钥K = nB′PA。
其中K的两种计算结果是相同的，因为
nA ′ PB = nA ′ (nB ′ G) = nB ′ (nA ′ G) = nB ′ PA
要破译这种体制，攻击者必须由G和KG计算K，是这是非常难的。
例如，取p = 211，Ep(0,-4)，G = (2,2)，这里Ep(0,-4)即是曲线y2=x3-4，则计算可得241G = O。A的私钥nA = 121，所以A的公钥PA = 121(2,2) = (115,48)。B的私钥nB = 203，所以B的公钥为203(2,2) = (130,203)，它们共享的秘密钥为121(130,203) = 203(115,48) = (161,169)。
请注意，这里秘密钥是一对数字。若将它用作传统密码中的会话密钥，则必须是一个数字，我们可以简单地取为x坐标或x坐标的某简单函数。
2.4、ElGamal密码体制
椭圆曲线加/解密的实现方法有多种，下面介绍其中最简单的一种方法。首先，我们必须将要发送的消息明文m按照某种方法与一个形为（x,y）的点Pm对应，并对点Pm进行其后的加密和解密。
和密钥交换系统中一样，加/解密系统也需要点G和椭圆群Ep(a,b)这些参数。假设用户A和用户B进行通信，首先用户A生成一个私钥nA，并产生公钥PA ＝nA ′ G，同样的，用户B生成一个私钥nB，并产生公钥PB ＝nB ′ G。
若A要将消息Pm加密后发送给B，则A随机选择一个正整数k，并产生密文Cm：
Cm = {kG, Pm + kPB}
注意，此处A使用了B的公钥PB。B要对密文解密，则需用第二个点减去第一个点与B的私钥之积：
Pm + kPB - nB (kG) = Pm + k (nBG) - nB (kG) = Pm
A通过将kPB与Pm相加来伪装消息Pm，因为只有A知道k，所以即使PB是公钥，除A外任何人均不能除去伪装kPB；但是，A也在伪装后的消息中包含了有关“线索”，使得已知私钥nB时可以除去伪装。攻击者要想恢复消息明文，则他必须从G和kG求出k，但这是很困难的。
下面举例说明椭圆曲线加密，取p = 751；Ep(-1,188)，即其椭圆曲线方程为y2 = x3 – x + 188，G ＝(0，376)。假定A要将对应于椭圆曲线上点Pm = (562-201)的消息发送给B，且A挑选的随机数k = 386，B的公钥为PB = (201,5)，那么有386(0,376) = (676,558)和(562,201) + 386(201,5) = (385,328).。于是A发送的密文是{(676,558)，(385,328)}。
2.5、关键技术指标
椭圆曲线密码（ECC）算法的理论基础是椭圆曲线离散对数问题（ECDLP）。该密码的实现基于大整数基本运算。
基于ElGamal系统，我们研制出的一种（ECC）加密系统，其主要性能指标及特点如下：
（1）关于素数p的选择，国外的p 一般选择为p=2，既在GF(2n)域上（n一般来说不超过 ）。我们的p取为任意的素数，字长可取为 多比特。
（2） 关于椭圆曲线的选择：椭圆曲线应选择为“好的” 椭圆曲线，即要求所选择的曲线满足安全的要求，通过精心的大量计算，我们选出一类满足此条件的曲线。
（3）我们研制的ECC系统，p为字长为 多比特的素数，首先，将明文欲传送的明文经某种方法嵌入到有限群Ep中去，然后，加密后传送。试验后得出的结论是，加解密的速度比RSA-1024快5-8 倍。
椭圆曲线密码(ECC)算法简介(二)
2.6、安全性分析
2.6.1、ECC安全性的理论基础
ECC的安全性，广义的讲，依赖于著名的数学难题：离散对数问题。
离散对数问题是：设G为有限Able群，设g和g1为G中已知元，求解是否有整数X存在，使得gx= g1。
这个问题的难度强烈依赖于G的选择。如果取G为Fq（q=pn），则称之为有限城上的离散对数问题（DLP）。
如果取G为Fq椭圆曲线上所构成的加法群，则相应的问题则称之为椭圆曲线离散对数问题（ECDLP）。
众所周知，解DLP有亚指数级算法，如通常的指标算法。而对于ECDLP而言，虽然经过许多优秀的数学家的努力，至今一直没有找到亚指数级算法，（比如，最近出现的被人们寄予厚望的Xedni方法被证明为指数级算法。）
正是由于目前所知求解ECDLP的最好方法是指数级的，这使得我们选用ECC作加解密及数字签名时，所要求的密钥长度要短得多。这可由下页的表格看出。
密钥大小 MIPS-年 密钥大小 MIPS-年
150 3.8′1010 512 3′104
205 7.1′1018 768 2′108
234 1.6′1028 1024 3′1011
1280 1′1014
1536 3′1016
2048 3′1020
(a) 用Pollard rho方法求椭圆曲线对数 (b)使用一般数域筛进行整数因子分解
2.6.2、ECC安全性的实现
虽然目前对于ECDLP只有指数级算法，但是并非所有的椭圆曲线都能达到这一点。在具体将ECC用于实际中去，我们至少面临着如下的选择：
1． 基本域的选择。通常我们只有两种考虑，即F2n和Fp（p>3），由于最近出现了攻击F2n上的ECDLP的方法，导致对F2n中n的要求越来越严，比如，在2000年，Gaudry Hess 和Smart等人通过改进的Weil 下降方法，使得对于F2n上的ECDLP，当n不是素数时，计算变得有效，基于这个理由，我们选择Fp作为基本域。
2． 如果选取Fp作基域，如何选取p。一般说来，为了算法实现的效率，p可选取成Mersenne素数或拟Mersenne素数。所谓拟Mersenne素数，即 P=at+b,其中a ,b都是小整数。我们可以取其中一种，也可以选择随机素数p。
3． 曲线的选择。这是ECC的关键所在。“好的”椭圆曲线才具有高度安全性。大量的研究表明，特殊的椭圆曲线是有安全隐患的，因此，为了抗击各种攻击方法，我们的曲线选择至少要满足：
1）Ep不是超椭圆曲线（ap≠0），这里的ap为Frobenius 映射的迹
2）Ep不是反常椭圆曲线（ap≠1）
3）Ep的阶（记为|Ep|）包含有大的素因子（如要求大于2160）
4）|Ep|不能整除pk－1，这里的1≤k≤20
上述的对曲线的限制主要是由目前已知的攻击方法所决定的。这些攻击方法有：
u Pollig-Hellman方法，
u Pollard的rho方法，
u Weil对和Tate 对方法，
u Semeav-Satoh-Araki-Smart方法，
u Mov方法，
u 以及最近出现的Gardry, Hess和Smart等人的方法；
这里，Pollig-Hellman方法和Pollard-rho方法对于一般有限Able群上的离散对数问题都是有效的，但计算复杂度为指数级的；即O(√p )，其中，p为|Ep|最大素因子。
其它方法都只对特殊的椭圆曲线有效。比如，MOV方法只对超椭园曲线有效。
在避免采用上述特殊的曲线后，为防范Pollig-Hellman方法和Pollard-rho方法的攻击，我们首先应有能力计算Ep的阶|Ep|，最好将|Ep|选为素数。
4． 阶的计算。对于|Ep|的计算有许多种方法。如，设ap为Frobenius映射的迹，对于任意的Q∈Ep，由于|Ep| = p+1-ap，可知（p+1）Q = apQ，从上式出发，我们可以用BSGS方法计算出ap来，由于|ap|≤2p1/2；可知计算复杂度为O(p1/4+ε)，当P〉280时，这一方法失效。
1985年Schoof找到了计算|Ep|的多项式算法，Schoof方法的出发点为如下的公式：
φ2 - apφ+p=0 这时φ为Frobenius映射。
通过约化，利用除多项式的性质，Schoof实现了他的算法，但是这一方法在实际计算中效率极低。其算法的复杂度为O(log8p)从1988年至今，Atkin，Elkis等人改进了Schoof算法，他们通过分析Ep上的同种映射，利用模多项式的性质，得出的方法称之为SEA方法，SEA方法的概率复杂度为O(log6p)，因此，较之Schoof方法更为有效，Morain等人利用这一方法，加之其他的改进措施，曾计算出p = 10500的Ep的阶来。
我们通过改进SEA方法，结合BSGS方法，对于计算|Ep|作了许多工作，比如，当p为160位时，我们在Pentium III 450微机上联网计算出|Ep|来，所费时间为10多分钟，当然如果使用更多的技巧，还可以大大提高效率。
基于算阶方面的工作，我们选择的椭园曲线具有如下的特点：
（1） 全随机的素数P和椭园曲线。
（2） |Ep|为素数。
3、椭圆曲线国际标准
椭圆曲线密码系统已经形成了若干国际标准。它们涉及加密、签名、密钥管理等方面。包括：
? IEEE P1363 加密、签名、密钥协商机制
? ANSI X9 椭圆曲线数字签名算法椭圆曲线密钥协商和传输协议
? ISO/IEC 椭圆曲线ElGamal体制签名
? IETF 椭圆曲线DH密钥交换协议
? ATM Forum 异步传输安全机制
? FIPS 186-2 美国政府用于保证其电子商务活动中的机密性和完整性
4、椭圆曲线技术实现
ECC的技术实现可以分成四个层次：运算层、密码层、接口层和应用层。运算层最基础、最核心；应用层最接近用户。
4.1、运算层
运算层的主要功能是，提供密码算法所需要的所有数论运算支持，包括：大整数加、减、乘、除、模，gcd、逆、模幂等。
运算层的实现效率将对整个密码系统的效率起决定性作用。因而运算层的编程工作是算法实现最核心、最基础，也是最艰巨的部分。
4.2、密码层
密码层的主要功能是，在运算层的支持上，选择适当的密码体制，科学地、准确地、安全地实现密码算法。
在相同的运算层的基础上，我们可以构建起多种密码体制。对于密码体制和具体结构的选择和实现，是密码层的核心内容。最终，密码系统的安全性，将决定于密码层的实现能力。
在密码层中，为了支持公钥密码系统，通常必须提供五种操作：生成密钥对、加密、解密、签名、验证签名。
· 生成密钥对
1．挑选生成元点G=(x1，y1)，G应使得满足nG ＝ O的最小的n是一个非常大的素数；
2．选择一个小于n的整数nA作为其私钥，然后产生其公钥PA＝nA′G；
·加密和解密
将要发送的消息明文m按照某种方法与一个形为（x，y）的点Pm对应，并对点Pm进行其后的加密和解密。
象密钥交换系统中一样，加/解密系统也需要点G和椭圆群Ep(a，b)这些参数。每个用户A选择一个私钥nA，并产生公钥PA ＝nA ′ G。
若A要将消息Pm加密后发送给B，则A随机选择一个正整数k，并产生密文Cm = {kG， Pm + kPB}
注意，此处A使用了B的公钥PB。B要对密文解密，则需用第二个点减去第一个点与B的私钥之积：
Pm + kPB - nB (kG) = Pm + k (nBG) - nB (kG) = Pm
A通过将kPB与Pm相加来伪装消息Pm，因为只有A知道k，所以即使PB是公钥，除A外任何人均不能除去伪装kPB；但是，A也在伪装后的消息中包含了有关“线索”，使得已知私钥nB时可以除去伪装。攻击者要想恢复消息明文，则他必须从G和kG求出k，但这是很困难的。
·签名和验证签名
信息发送者对信息生成数字摘要，再使用其私钥对数字摘要进行加密，由于只有信息发送者拥有其私钥，保证了其签名的不可否认性，达到了防伪的目的。其流程如图2所示。
图2 签名与验证签名
4.3、接口层
接口层的主要功能是，对各种软硬件平台提供公钥密码功能支持。
其工作重点在于：对各种硬件环境的兼容、对各种操作系统的兼容、对各种高级语言的兼容、对多种应用需求兼容。
其难点主要在于：保持良好的一致性、可移植性、可重用性，以有限的资源换取应用层尽可能多的自由空间。
4.4、应用层
应用层是最终用户所能接触得到的唯一层面。它为用户提供应用功能和操作界面。
应用功能包括：交易、网络、文件、数据库、加解密、签名及验证等等。
操作界面包括：图形、声音、指纹、键盘鼠标等等。
4.5、ECC的实现效率
ECC的实现效率一般表现为ECC公钥密码功能的效率。实现效率是被多种因素制约和影响的。以下，我们列举了我们在实现ECC的过程中遇到的涉及ECC实现效率的方面。
4.5.1、ECC密码机制
众所周知，任何密码理论都必须在某种密码机制上实现，才能完成密码功能（如：加密、签名等）。同一种密码理论也可以运用于不同的密码机制上，而且它们的实现效率也不尽相同。我们在自行发明的、拥有自主知识产权的密码机制上实现ECC，并且我们容易证明其安全性不低于其它常用密码体制，且效率更高。
4.5.2、安全前瞻性
由于公钥系统的安全性建立在数学的困难性上。所以在选择ECC参数时，我们认为不能一味地追求速度快，而是应该在理论上、在实现上都要为安全性留出一定的余量，以保证在密码分析技术进步后，不至受到重大威胁。F2n和Fp的比较就集中的体现了这一点。同时，对p的选择也体现了这一点。
当然，这种安全性上的保障是要通过降低一定的效率换取的。
4.5.3、应用环境
应用环境是ECC软硬件实现的约束条件。硬件环境要求空间小、指令简单、高稳定性、低成本；软件环境要求兼容性好、可移植性好、易于维护升级。
因此，从高端到低端，从高级语言到汇编、从系统到门电路设计，每个应用环境对ECC实现所提供的支持和约束都不相同。所以，ECC实现效率也依应用环境而异。
4.5.4、算法优化
算法优化始终都是提高效率的根本所在。我们对ECC实现算法的优化主要从这几个方面入手：
1） 对数学公式的变形和组合优化；
2） 在软件实现中，根据编译系统的特点、CPU指令集的特点优化；
3） 在硬件实现中，根据硬件资源的具体特点优化。
5、应用前景
ECC密码体制是建立在椭圆曲线密码理论基础上的先进公钥密码体制。该系统所具有的安全性已经被全世界所承认。在椭圆曲线密码理论的基础上，我们经过长期的理论研究和科学实践，已经成功地将该理论转换为实际可用的密码算法，并将运用于安全产品之中。ECC技术拥有广泛的应用前景，如：可应用于安全数据库、智能卡应用、VPN、安全电子商务等。将ECC技术应用于安全产品不仅能够充分发挥我们已经取得的优势，创造更多的效益，而且可以使我国的公钥密码应用技术进入一个更广阔的新天地。
这是一条镜像帖。来源：北邮人论坛 / soft-design / #230同步于 1 周前
该镜像源已超过 30 天没有更新，可能在源站已被删除。
SoftDesign机器人发帖
椭圆曲线密码(ECC)算法简介
Lonhero
1 周前镜像同步2 回复
订阅后，新回复会通过你的通知中心匿名送达。