椭圆曲线密码概述：椭圆曲线密码学（ECC, Elliptic curve cryptography ）是基于椭圆曲线数学的一种公钥密码的方法。

1985年，Neal Koblitz 和Victor Miller 分别独立提出了椭圆曲线密码体制(ECC)，其依据就是定义在椭圆曲线点群上的离散对数问题的难解性。

引言：ECC 被广泛认为是在给定密钥长度的情况下，最强大的非对称算法，因此在对带宽要求十分紧的连接中会十分有用。

ECC 的主要优势是在某些情况下它比其他的方法使用更小的密钥——比如RSA ——提供相当的或更高等级的安全。

ECC 的另一个优势是可以定义群之间的双线性映射，基于Weil 对或是Tate 对；双线性映射已经在密码学中发现了大量的应用，例如基于身份的加密。

不过一个缺点是加密和解密操作的实现比其他机制花费的时间长。

国家标准与技术局和ANSI X9已经设定了最小密钥长度的要求，RSA 和DSA 是1024位，ECC 是160位，相应的对称分组密码的密钥长度是80位。

NIST 已经公布了一列推荐的椭圆曲线用来保护5个不同的对称密钥大小(80, 112, 128, 192, 256)。

一般而言，二进制域上的ECC 需要的非对称密钥的大小是相应的对称密钥大小的两倍。

椭圆曲线密码学的许多形式有稍微的不同，所有的都依赖于被广泛承认的解决椭圆曲线离散对数问题的困难性上，对应有限域上椭圆曲线的群。

引理及有关概念：（1） 无穷远元素（无穷远点，无穷远直线）平面上任意两相异直线的位置关系有相交和平行两种。

引入无穷远点，是两种不同关系统一。

AB ⊥L1， L2∥L1，直线AP 由AB 起绕A 点依逆时针方向转动，P 为AP 与L1的交点，如图1。

Q=∠BAP →π /2则AP → L2，可设想L1上有一点P ∞，它为L2和L1的交点，称之为无穷远点。

直线L1上的无穷远点只能有一个（因为过A 点只能有一条平行于L1的直线L2，而两直线的交点只能有一个）。

图1结论：1.平面上一组相互平行的直线，有公共的无穷远点（为与无穷远点相区别，把原来平面上的点叫做平常点）。

2. 平面上任何相交的两直线L1,L2有不同的无穷远点。

原因：若否，则L1和L2有公共的无穷远点P ∞，则过两相异点A 和P ∞有相异两直线，与公理相矛盾。

3. 全体无穷远点构成一条无穷远直线备注：欧式平面添加上无穷远点和无穷远直线，自然构成射影平面，如图2。

图2（2）齐次坐标，解析几何中引入坐标系，用代数的方法研究欧氏空间。

这样的坐标法也可推广至摄影平面上，建立平面摄影坐标系。

平面上两相异直线L1,L2，其方程分别为：L1: 0111=++c y b x a L2: 0222=++c y b x a其中11,b a 不同时为0；22,b a 也不同时为0。

设：D=2211b a b a Dx=2211c b c b Dy=2211a c a c若D ≠0，则两直线L1,L2相交于一平常点P(x,y)，其坐标为x=Dx/D ，y=Dy/D. 这组解可表为：x/Dx=y/Dy=1/D 。

(约定：分母Dx ，Dy 有为0时，对应的分子也要为0）上述表示可抽象为（Dx ，Dy ，D)。

若 D=0，则L1∥L2，此时L1和L2交于一个无穷远点P ∞。

这个点P ∞可用过原点O 且平行于L2的一条直线L 来指出他的方向，而这条直线L 的方程就是：022=+y b x a .为把平常点和无穷远点的坐标统一起来，把点的坐标用（X ，Y ，Z)表示，X ，Y ，Z 不能同时为0，且对平常点（x ，y)来说，有Z ≠0，x=X/Z ，y=Y/Z ，于是有：X / Dx = Y / Dy = Z / D ，有更好的坐标抽象（X,Y,Z),这样对于无穷远点则有Z=0也成立。

备注：1. 若实数p ≠0，则(pX,pY,pZ)与（X,Y,Z)表示同一个点。

实质上用（X:Y:Z)表示。

3个分量中，只有两个是独立的，具有这种特征的坐标就叫齐次坐标。

DD Z YD Z X y x 1==2. 设有欧氏直线L ，它在平面直角坐标系Oxy 上的方程为：0=++c by ax .则L上任一平常点(x,y)的齐次坐标为(X,Y,Z)，Z ≠0，代入得：0=++cz by ax .给L 添加的无穷远点的坐标(X,Y,Z)应满足0=+by ax ，0=z ;平面上无穷远直线方程自然为:0=z . (3)任意域上的椭圆曲线K 为域，K 上的摄影平面)(2K P 是一些等价类的集合{(X:Y:Z)}。

考虑下面的Weierstrass 方程(次数为3的齐次方程)：36242232312z a xz a z x a x yz a xyz a z y +++=++(其中系数ai ∈K ，或ai ∈K 为K 的代数闭域）Weierstrass 方程被称为光滑的或非奇异的是指对所有适合以下方程的射影点P=(X:Y:Z) ∈)(2K P 来说：=),,(z y x F 036242232312=----++z a xz a z x a x yz a xyz a z y在P 点的三个偏导数之中至少有一个不为 0若否称这个方程为奇异的。

椭圆曲线E 的定义：椭圆曲线E 是一个光滑的Weierstrass 方程在)(2K P 中的全部解集合。

36242232312z a xz a z x a x yz a xyz a z y +++=++备注：1. 在椭圆曲线E 上恰有一个点，称之为无穷远点，即(0:1:0)用θ表示。

2.椭圆曲线的研究来源于椭圆积分：⎰)(x E dx这里)(x E 是x 的三次多项式或四次多项式.这样的积分不能用初等函数来表达,为此引进所谓椭圆函数.所谓椭圆曲线指的是由韦尔斯特拉斯(Weierstrass)方程，可用非齐次坐标的形式来表示，设x=X/Z ，y=Y/Z ，于是原方程可转化为：64223312a x a x a x y a xy a y +++=++ (1) 此时，椭圆曲线E 就是方程（1)在射影平面)(2K P 上的全部平常点解，外加一个无穷远点θ组成的集合。

3.若K a a a a a ∈64321,,,,,此时椭圆曲线E 被称为定义在K 上，用E/K 表示。

如果E 能被限定在K 上，那么E 的K ——有理点集合表示为E(K)，它为E 中的全体有理坐标点的集合外加无穷远点θ.(4)实域R 上的椭圆曲线：设K=R ，此时的椭圆曲线可表为平面上的通常曲线上 的点，外加无穷远点θ。

实域R 上椭圆曲线的点的加法运算法则：设L ∈)(2R P 为一条直线。

因为E 的方程是三次的，所以L 可与E 在)(2R P 恰有三个交点，记为P,Q,R （注意：如果L 与E 相切，那么P,Q,R 可以不是相异的）。

按下述方式定义E 上运算⊕;设P,Q ∈ E ，L 为联接P,Q 的直线（若P=Q ，则L 取过P 点的切线）；设R 为L 与E 的另一个交点；再取连接R 与无穷远点的直线L ′。

则L ′与E 的另一个交点定义为P ⊕ Q 。

以上的实际图像为椭圆曲线x x y -=32的一般化。

来自对具体曲线的抽象。

对运算更具体一些：设 P=(x1,y1)，Q=(x2,y2)，P ⊕Q=(x3,y3),由P ⊕Q 的定义，设βα+=x y 为通过P,Q 两点直线L 的方程，可算出：111212),/()(x y x x y y αβα-=--=易见，直线L 上的一个点（x, αx+β)是在椭圆曲线E 上，当且仅当x x x -=+32)(βα，P ⊕Q=(x1,y1) ⊕(x2,y2)=(x3,y3) =(x3,-(αx3+β)) 其中，x3= α2-x1-x2=((y2-y1) / (x2-x1) )2-x1-x2；y3=-y1+((y2-y1)/(x2-x1))(x1-x3) ;当P=Q 时： P ⊕Q=（x3，y3）算得 :x3=((3x12-1)/2y1)2-2x1; y3= -y1+((3x12-1)/2y1)(x1-x3) ;备注：a) 如果直线L 与E 相交与三点P,Q,R(不一定相异），那么 (P ⊕Q)⊕R=θ(从图中可见）；b) 任给P ∈E,P ⊕θ=P(此时设Q= θ，易见L=L ′)；T ⊕(P=Q=R)c) 任给P,Q ∈E 有：P ⊕Q=Q ⊕P ；d) 设P ∈E ，那么可以找到-P ∈E 使P ⊕-P=θ；e) 任给P,Q,R ∈E ，有(P ⊕ Q) ⊕ R= P ⊕(Q ⊕ R)； 综上所述，知E 对⊕ 运算形成一个Abel 群。

f) 上述规则可开拓到任意域上，特别是有限域上。

假定椭圆曲线是定义在有限域Fq 上（q=pm)，那么 E(Fq)={(x,y)∈Fq ×Fq | 64223312a x a x a x y a xy a y +++=++} ∪{θ},它对“⊕ ”形成一个群，为Abel 群。

有限域上椭圆曲线的⊕运算令Fq 表示q 个元素的有限域，用E(Fq)表示定义在Fq 上的一个椭圆曲线E 。

定理1.(Hass 定理) E(Fq)的点数用#E(Fq)表示，则| #E(Fq)-q-1|≤2q^(1/2) (1) Fp （素域，p 为素数）上椭圆曲线,令p>3，a,b ∈Fp ，满足027423≠+b a ，由参数a 和b 定义的Fp 上的一个椭圆曲线方程为：b ax x y ++=32 (2) 它的所有解(x,y)，(x ∈Fp ，y ∈Fp)，连同一个称为“无穷远点”（记为θ）的元素组成的集合记为E(Fp)，由Hass 定理知：p+1-2p^(1/2)≤#E(Fp) ≤ p+1+2p^(1/2)集合E(Fp)对应下面的加法规则，且对加法⊕形成一个Abel 群： (i) θ⊕θ=θ（单位元素）;(ii)(x,y)⊕θ=(x,y),任给(x,y)∈E(Fp);(iii)(x,y)⊕(x,-y)=θ,任给(x,y)∈E(Fp),即点(x,y)的逆元为(x,-y); (iv) 令(x1,y1),(x2,y2)为E(Fp)中非互逆元，且满足21x x ≠的两点，则(x1,y1) ⊕(x2,y2)=(x3,y3),其中⎩⎨⎧--=--=1)31(32132y x x y x x x λλ，1212x x y y --=λ （3） (v)（倍点运算规则）设(x1,y1) ∈E(Fp),y1≠0，则2(x1,y1)=(x3,y3)，其中⎩⎨⎧--=-=1312)(3123y x x y x x λλ，12132y a x +=λ （4） 备注：若#E(Fp)=p+1，曲线E(Fp)称为超奇异的，否则称为非超奇异的。