椭圆密码学教程书籍，椭圆曲线密码学的数学理论

OKX欧易app

欧易交易所app是全球排名第一的虚拟货币交易所，注册领取6万元盲盒礼包!

APP下载 官网注册

binance币安交易所app

币安交易所app是全球排名第一的虚拟货币交易所，注册领取盲盒礼包!

APP下载 官网注册

一、椭圆曲线密码学的一些具体的内容

⑴无穷远元素（无穷远点，无穷远直线）

平面上任意两相异直线的位置关系有相交和平行两种。引入无穷远点，是两种不同关系统一。

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

Q=∠BAP→p/2 AP→ L2

可设想L1上有一点P∞，它为L2和L1的交点，称之为无穷远点。

直线L1上的无穷远点只能有一个。

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

结论：

1*.平面上一组相互平行的直线，有公共的无穷远点。

（为与无穷远点相区别，把原来平面上的点叫做平常点）

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

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

3*.全体无穷远点构成一条无穷远直线。

注：欧式平面添加上无穷远点和无穷远直线，自然构成射影平面。

⑵齐次坐标

解析几何中引入坐标系，用代数的方法研究欧氏空

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

坐标系。

牋 L1,L2

L1: a1x+b1y+c1=0

L2: a2x+b2y+c2=0

其中a1,b1不同时为0；a2,b2也不同时为0。

设

D= a1 b1 Dx= b1 c1 Dy= c1 a1

a2 b2 b2 c2 c2 a2

若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的方程就是：a2x+b2y=0.

为把平常点和无穷远点的坐标统一起来，把点的坐标用

（X，Y，Z）表示，X，Y，Z不能同时为0，且对平常点

（x，y）来说，有Z≠0，x=X/Z，y=Y/Z，于是有：

i.e.

X/ Dx= Y/ Dy= Z/ D，

有更好的坐标抽象，X,Y,Z），这样对于无穷远点则有Z=0，

也成立。

注：

a).若实数p≠0，则（pX,pY,pZ）与（X,Y,Z）表示同一个点。实质上用（X:Y:Z）表示。3个分量中，只有两个是独立的，</pre>

<pre>；具有这种特征的坐标就叫齐次坐标。

b).设有欧氏直线L，它在平面直角坐标系Oxy上的方程为：

ax+by+c=0

则L上任一平常点（x,y）的齐次坐标为（X,Y,Z），Z≠0，代入得：

aX+bY+cZ=0

给L添加的无穷远点的坐标（X,Y,Z）应满足aX+bY=0，Z=0；平面上无穷远直线方程自然为：Z=0!!

⑶任意域上的椭圆曲线

K为域，K上的摄影平面P2(K）是一些等价类的集合{(X:Y:Z)}。考虑下面的Weierstrass方程（次数为3的齐次方程）：

Y2Z+a1XYZ+a3YZ2=X3+a2X2z+a4XZ2+a6Z3

（其中系数ai∈K，或ai∈K为K的代数闭域）

Weierstrass方程被称为光滑的或非奇异的是指对所有适合

以下方程的射影点P=(X:Y:Z)∈ P2(K）来说，

F(X,Y,Z)=Y2Z+a1XYZ+a3YZ2-X3-a2X2Z-a4XZ2-a6Z3=0

在P点的三个偏导数之中至少有一个不为

0若否称这个方程为奇异的。

椭圆曲线E的定义：

椭圆曲线E是一个光滑的Weierstrass方程在P2(K）中的

全部解集合。

Y2Z+a1XYZ+a3YZ2=X3+a2X2Z+a4XZ2+a6Z3

注：

a)在椭圆曲线E上恰有一个点，称之为无穷远点。即（0:1:0）用θ表示。

b)可用非齐次坐标的形式来表示椭圆曲线的Weierstrass方程：

设 x=X/Z，y=Y/Z，于是原方程转化为：

y2+a1xy+a3y=x3+a2x2+a4x+a6⑴

此时，椭圆曲线E就是方程⑴在射影平面P2(K）上的全部平常点解，外加一个无穷远点θ组成的集合。

c)若a1,a2,a2,a4,a6∈K，此时椭圆曲线E被称为定义在K上，用E/K表示。如果E能被限定在K上，那么E的K--</pre>

<pre>；有理点集合表示为E(K），它为E中的全体有理坐标点的集合外加无穷远点θ.

⑷实域R上的椭圆曲线

设K=R，此时的椭圆曲线可表为平面上的通常曲线上

的点，外加无穷远点θ。

实域R上椭圆曲线的点的加法运算法则：

设L∈ P2(R）为一条直线。因为E的方程是三次的，所以L可与E在P2(R）恰有三个交点，记为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。

上页的实际图像为椭圆曲线y2=x3- x的一般化。来自对具体曲线的抽象。对运算更具体一些：

设 P=(x1,y1），Q=(x2,y2），P⊙Q=(x3,y3），

由P Q的定义，设y=αx+β为通过P,Q两点直线L的方程，可算出：

α=(y2-y1）/(x2-x1），β=y1-αx1

易见，直线L上的一个点（x，αx+β）是在椭圆曲线E上，

当且仅当（αx+β）2= x3- x。

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′）

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| y2+a1xy+a3y=x3+a2x2+a4x+a6}∪{θ}

它对?斝纬梢桓鋈海?狝bel群。令Fq表示q个元素的有限域，用E(Fq）表示定义在Fq上

的一个椭圆曲线E。

定理1.(Hass定理） E(Fq）的点数用#E(Fq）表示，则

|#E(Fq)-q-1|≤2q1/2

⑴ Fp（素域，p为素数）上椭圆曲线

牋 p&gt;3 a,b Fp 4a3+27b2 0 a b

义的Fp上的一个椭圆曲线方程为：

y2=x3+ax+b⑵

它的所有解（x,y），（x Fp，y Fp），连同一个称为撑耷钤?

点敚?俏?龋┑脑?刈槌傻募?霞俏狤（Fp），由Hass定理

知：p+1-2p1/2≤#E(Fp)≤ p+1+2p1/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）中非互逆元，则

（x1,y1）⊙(x2,y2）=(x3,y3），其中

x3=α2-2x1，y3=α（x1-x3）-y1

且α=(y2-y1）/(x2-x1）⑶

（v）（倍点运算规则）

设（x1,y1）∈E(Fp),y1≠0，则2(x1,y1）=(x3,y3），其中

x3=α2-2x1,y3=α（x1-x3）-y1

这里α=（3x12+a)/（2y1）⑷

注：若#E(Fp)=p+1，曲线E(Fp）称为超奇异的，否则称为

非超奇异的。

例子：F23上的一个椭圆曲线

令y2=x3+x+1是F23上的一个方程（a=b=1），则该椭圆曲

线方程在F23上的解为（y2=x3+x+1的点）：

（0,1），（0,22），（1,7），（1,16），（3,10），（3,13），（4,0），（5,4），（5,19），（6,4），</pre>

<pre>；（6,19），（7,11），（7,12），（9,7），（9,16），（11,3），（11,20），（12,4），（12,19），（13,7），</pre>

<pre>；（13,16），（17,3），（17,20），（18,3），（18,20），（19,5），（19,18）；θ。

群E(F23）有28个点（包括无穷远点θ）。

2） F2m上的椭圆曲线

F2m上由参数a,b∈F2m，b≠0定义的一个非超奇异椭

圆曲线E(F2m）是方程

y2+xy=x3+ax2+b⑸

的解集合（x,y），其中x,y∈F2m，连同θ。

E(F2m）的加法规则如下：

（i)θ+θ=θ

（ii)任给（x,y)∈E(F2m），则（x,y）⊙θ=(x,y)

（iii)任给（x,y)∈E(F2m），则（x,y)+(x,x+y)=θ，

即点（x,y）的逆为（x,x+y).

（iv)两个相异且不互逆的点的加法规则：

令（x1,y1），（x2,y2）∈E(F2m）且有x1≠x2则

（x1,y1）(x2,y2）=(x3,y3），其中

x3=α2+α+x1+x2+a；

y3=α（x1+x3）+x3+y1.

其中α=(y2+y1）/(x2+x1）

（v)倍点规则

令（x1,y1）∈E(F2m），其中x1≠0。则

2(x1,y1）=(x3,y3），其中

x3=α 2+α+a,y3=x12+（α+1）x3，这里α=(x1+y1/x1）

易见，群E(F2m）为Abel群。

例：F24上的一个椭圆曲线

f(x)=x4+x+1为F2上的一个不可约多项式，易见

F24=F2[x]/(f(x))={(k0,k1,k2,k3）|(k0,k1,k2,k3）=k0+k1α+k2α2+k3α3，</pre>

<pre>；α为f(x)的零点，ki∈F2}

假定F24上的非超奇异椭圆曲线有下述方程定义：

y2+xy=x3+α4x2+1，注意f（α）=0。

方程应表为：

（1000)y2+（1000)xy=（1000)x3+（1100）x2+（1000) 1985年，N. Koblitz和V. Miller分别独立提出了椭圆曲线密码体制（ECC），</pre>

<pre>；其依据就是定义在椭圆曲线点群上的离散对数问题的难解性。

⑴知E(Fq）对点的?斣怂阈纬梢桓鯝bel群

设p∈E(Fq），若p的周期很大，即使

p⊙p⊙……⊙p=θ（共有 t个p相加）

成立的最小正整数 t，希望 t很大。

（t= p的周期，表示为∏（p)=t）。

并且对Q∈E(Fq），定有某个正整数m使

Q=m&middot;p=p⊙……⊙p（共有t个p相加）

定义

m=㏒pQ(m为以p为底Q的对数）。

椭圆曲线上的点形成的群E(Fq），相关它的离散对数

问题是难处理的。选取基域Fq，Fq的椭圆曲线具体给定为确定的形式。

在E(Fq）中选一个周期很大的点，如选了一个点P=(xp,yp），

它的周期为一个大的素数n，记∏(P)=n（素数）。

注意：在这个密码体制中，具体的曲线及点P和它的n都

是公开信息。密码体制的形式采用EIGamal体制，是完全

类比过来。

a）密钥的生成

Bob（使用者）执行了下列计算：

i)在区间[1,n-1]中随机选取一个整数d。

ii)计算点Q:=dP(d个P相）

iii) Bob公开自己的公开密钥--(E(Fq),p,n,Q)

iv) Bob的私钥为整数d！

Alice要发送消息m给Bob，Alice执行：

i)查找Bob的公钥（E(Fq),p,n,Q),

ii)将m表示成一个域元素m∈Fq,

iii)在区间[1，n-1]内选取一个随机数k,

iv)依据Bob的公钥计算点(x1,y1）：=kP(k个P相）

v)计算点（x2,y2）：=kQ，如果x2=0，则回到第iii）步

Ⅵ）计算C:=m&middot;x2

Ⅶ）传送加密数据（x1,y1,C）给Bob

b) Bob的解密过程

Bob收到Alice的密文（x1,y1,C）后，执行

i)使用私钥d，计算点（x2，y2）：=d(x1,y1），再计算Fq中x2-1=

通过计算m:=C&middot;x2-1，恢复出明文数据

二、椭圆曲线密码学的数学理论

ECC的主要优势是在某些情况下它比其他的方法使用更小的密钥——比如RSA——提供相当的或更高等级的安全。ECC的另一个优势是可以定义群之间的双线性映射，基于Weil对或是Tate对；双线性映射已经在密码学中发现了大量的应用，例如基于身份的加密。不过一个缺点是加密和解密操作的实现比其他机制花费的时间长。

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

对椭圆曲线来说最流行的有限域是以素数为模的整数域（参见模运算）GF(p)，或是特征为2的伽罗华域GF（2m）。後者在专门的硬件实现上计算更为有效，而前者通常在通用处理器上更为有效。专利的问题也是相关的。一些其他素数的伽罗华域的大小和能力也已经提出了，但被密码专家认为有一点问题。

给定一条椭圆曲线E以及一个域GF(q)，我们考虑具有(x,y)形式有理数点E(q)的阿贝尔群，其中x和y都在GF(q)中并且定义在这条曲线上的群运算+在文章椭圆曲线中描述。我们然後定义第二个运算*| Z×E(q)->E(q)：如果P是E(q)上的某个点，那么我们定义2*P=P+P,3*P=2*P+P=P+P+P等等。注意给定整数 j和k，j*(k*P)=(j*k)*P=k*(j*P)。椭圆曲线离散对数问题（ECDLP）就是给定点P和Q，确定整数k使k*P=Q。

一般认为在一个有限域乘法群上的离散对数问题（DLP）和椭圆曲线上的离散对数问题（ECDLP）并不等价；ECDLP比DLP要困难的多。

在密码的使用上，曲线E(q)；和其中一个特定的基点G一起被选择和公布。一个私钥k被作为随机整数来选择；值P=k*G被作为公钥来公布（注意假设的ECDLP困难性意味着k很难从P中确定）。如果Alice和Bob有私钥kA和kB，公钥是PA和PB，那么Alice能计算kA*PB=(kA*kB)*G；Bob能计算同样的值kB*PA=(kB*kA)*G。

这允许一个“秘密”值的建立，这样Alice和Bob能很容易地计算出，但任何的第三方却很难得到。另外，Bob在处理期间不会获得任何关于kA的新知识，因此Alice的私钥仍然是私有的。

基于这个秘密值，用来对Alice和Bob之间的报文进行加密的实际方法是适应以前的，最初是在其他组中描述使用的离散对数密码系统。这些系统包括：

Diffie-Hellman— ECDH

MQV— ECMQV

ElGamal discrete log cryptosystem— ECElGamal

DSA— ECDSA

对于ECC系统来说，完成运行系统所必须的群操作比同样大小的因数分解系统或模整数离散对数系统要慢。不过，ECC系统的拥护者相信ECDLP问题比DLP或因数分解问题要难的多，并且因此使用ECC能用小的多的密钥长度来提供同等的安全，在这方面来说它确实比例如RSA之类的更快。到目前为止已经公布的结果趋于支持这个结论，不过一些专家表示怀疑。

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

国家标准与技术局和ANSI X9已经设定了最小密钥长度的要求，RSA和DSA是1024位，ECC是160位，相应的对称分组密码的密钥长度是80位。NIST已经公布了一列推荐的椭圆曲线用来保护5个不同的对称密钥大小（80,112,128,192,256）。一般而言，二进制域上的ECC需要的非对称密钥的大小是相应的对称密钥大小的两倍。

Certicom是ECC的主要商业支持者，拥有超过130项专利，并且已经以2千5百万美元的交易获得了国家安全机构（NSA）的技术许可。他们也已经发起了许多对ECC算法的挑战。已经被解决的最复杂的是109位的密钥，是在2003年初由一个研究团队破解的。破解密钥的这个团队使用了基于生日攻击的大块并行攻击，用超过10,000台奔腾级的PC机连续运行了540天以上。对于ECC推荐的最小密钥长度163位来说，当前估计需要的计算资源是109位问题的108倍。

在2005年2月16日，NSA宣布决定采用椭圆曲线密码的战略作为美国政府标准的一部分，用来保护敏感但不保密的信息。NSA推荐了一组被称为Suit B的算法，包括用来密钥交换的Menezes-Qu-Vanstone椭圆曲线和Diffie-Hellman椭圆曲线，用来数字签名的椭圆曲线数字签名算法。这一组中也包括AES和SHA。

三、密码学基础2:椭圆曲线密码学原理分析

首先要说明的一点是，椭圆曲线不是椭圆。椭圆方程是下面这样的：

而通常我们讨论的椭圆曲线的曲线方程是一个二元三次方程，它有多种形式，在椭圆曲线密码体系中，最常用的是如下的Weierstrass通用式(curve25519等其他类型的椭圆曲线本文不讨论)：

之所以取名叫椭圆曲线，是因为该曲线方程跟求椭圆弧长的积分公式相似。从曲线方程和图像易知，椭圆曲线关于X轴对称。判定式不等于零是为了椭圆曲线不存在奇异点，即处处光滑可导，这样才能进行椭圆曲线上的加法运算。下面是一些适合用于加密的椭圆曲线，其中。

椭圆曲线加密算法涉及数学中的群论、有限域等内容，这节简要介绍下相关数学理论。亦可以跳过直接看第3节，遇到相关名词再查阅即可。

在讨论群之前，先说说集合。集合简单来说就是把一堆东西放在一起，如自然数集合。当然光有一堆东西还不够，东西之间相互作用才能更好的描述大千世界。于是，自然数集合通过加减运算衍生出整数集合、整数集合经过乘除又可以衍生出有理数，而后通过无理数的加入又衍生出实数集合、负数开方引入了复数集合。群则是集合和一个二元运算。

而如果再满足交换律，则该群就被称为是一个阿贝尔群。

根据群的定义，整数的加法运算就是一个群，而且还是一个阿贝尔群。而自然数的加法运算就不是一个群。整数加法运算构成群，因为它满足群的定义：整数加法的封闭性、结合律、交换律都成立。整数加法运算中单位元是 0。所有整数 n都有加法逆元-n。

在密码学中一般都需要一个有限的群，定义如下:

为了使一个结构同时支持四种基本算术(即加减乘除)，我们需要一个包含加法和乘法群的集合，这就是域。当一个集合为域的时候，我们就能在其中进行基本算术运算了。

所以域中元素只要形成加法群和乘法群并满足分配律就行，因为群中元素都有逆元，减法/除法可以转换为加/乘元素的逆元实现。实数集合是一个域，加法群中单位元是 0，每个实数都有加法逆元，乘法群中单位元是，每个非零实数都有乘法逆元。而整数集合就不是域，因为大部分元素没有乘法逆元，不能构成一个乘法群。

在密码学中，通常只对有限元素的域感兴趣，这种域称为有限域(Finite Field)。有限域中我们经常用到的是素数域，所谓素数域，就是阶为素数的有限域。比如当 p为素数时，整数环就是一个素数域，可以记作。在素数域中进行算术运算，需要遵守整数环的规则，即加法是模 p加法，而乘法是模 p乘法。

例如对于有：

椭圆曲线上的点经过一种特定的加法运算可以让椭圆曲线在实数域构成一个群。

无穷远点：定义一个无穷远点，即经过椭圆上任意一点的与X轴垂直的直线都经过该点。可能有人疑惑垂直于X轴的直线是平行线，为啥可以定义为都经过点？因为在非欧几何中，可认为平行线在无穷远处会交于一点。

椭圆曲线点加法：椭圆曲线上经过和两个点的直线与椭圆曲线的交点记作，根据定义有以及。继而定义椭圆曲线点加法：，即加法结果是经过点且与 X轴垂直的直线与椭圆曲线的另外一个交点，简单来说，就是交点关于 X轴的对称点。

椭圆曲线群：定义为椭圆曲线在实数域上的点集以及点加法

由此可知，椭圆曲线上的点在椭圆曲线加法运算上构成了一个阿贝尔群。增加了单位元后，椭圆曲线方程改为：

由定义可知，，所以，最终加法只需要计算交点的逆元即可。几种特殊情况说明：

上一节定义了椭圆曲线几何上意义的点加法，需要转换为代数加法以方便计算。要注意的是，这并不是两个点的坐标简单相加。

假设直线 PQ的斜率，然后将直线方程代入曲线可以得到：,转换成标准式，根据韦达定理，即而可求得，想了解具体推导过程的可参见 [cubic-equations]。

斜率计算需要区分两种情况，当 P=Q时求椭圆曲线在 P点的切线斜率(求导)即可：

可以简单验证，比如椭圆曲线是，通过参考资料1的 [可视化工具]可得。容易验证，与代数加法公式计算结果一致。

对于特殊情况中有一个是切点的情况，如，计算方式不变，易得。而对于特殊情况，采用切线斜率亦可验证公式正确。

在实际加密算法中，我们通常需要多次通过椭圆曲线加法来实现一次加密，如下图所示：

图中打点的过程就是：

而在实际加密算法中，我们常常是使用一个点自己叠加，即初始直线变成椭圆曲线的切线即可，像下面这样：

我们定义对一个点 P进行 n次加法得到 nP，称之为标量乘法。如前面例子中。

不过，当 n很大时，执行 n次加法需要时间，效率有问题。因为椭圆曲线点加法在实数域构成阿贝尔群，满足交换律和结合律，于是可以通过 [Double-and-add]算法进行优化。比如，其二进制表示为，通过优化只要7次倍乘和4次加法计算即可，时间复杂度降到。这是一个很好的单向函数，正向计算容易，而反向和蛮力计算复杂。

令，则 Q作为公钥，n为私钥。如果要破解该密钥，问题就是"Q= nP，如果已知 P和 Q，如何求解 n"?这个问题是比较困难的。不过由于在实数域上曲线连续，可能会更容易找到一些规律进行破解。而且实数域上数值大小没有限制、浮点数等问题而导致计算效率问题，在实际应用中常将椭圆曲线限制到一个有限域内，将曲线变成离散的点，这样即方便了计算也加大了破解难度。

前面提到为了安全性和便于实现，需要将椭圆曲线限制到一个有限域内，通常用的是素数域(即对于点为素数)。于是破解就会变成一个离散对数问题，这比连续曲线上的对数问题会难很多。素数域下椭圆曲线定义如下：

下面是曲线和的图像。可以发现，椭圆曲线变成了离散的点，且关于对称。

定义上椭圆曲线点加法如下，公式跟实数域上相比只是多了模操作。

斜率 m计算同样分两种情况：

椭圆曲线在素数域上的点加法依然构成阿贝尔群。单位元依旧是无穷远点，元素的逆元变成。而交换律、结合律、封闭性则可以通过素域上的模加法、模乘法来证明。实数域的椭圆曲线点加法定义是有明确几何意义的，从几何上好证明。而椭圆曲线在就没有明显的几何意义了，观察可发现三点满足，群律的证明过于繁琐，略去(其实是没有找到一个简易的证明)。

以前面曲线为例，，则有，且和都在椭圆曲线上。从图形上看，在直线上。

在有限域下，椭圆曲线加法群的元素是有限的，元素数目就是群的阶。

如椭圆曲线，其在素数域中元素有，阶为24(23个素数域中的点+ 1个无穷远点)，如果 p很大的话，则通过蛮力计算阶是很难的，好在使用 [Schoof算法]可以在多项式时间内计算出群的阶。计算椭圆曲线在有限域上点的数目可以参见 [Counting points on elliptic curves]。

Schoof算法运用了 Hasses定理。Hasses定理给出了椭圆曲线在的阶的范围，可以看出，当 p很大时，阶跟 p的值是比较接近的。

跟实数域一样，在素数域里面也是选取一个点 P，然后计算倍乘 nP作为公钥。还是以为例，，我们采用素数域下新的计算公式计算。

可以发现，即 P的标量乘法得到的点集是原椭圆曲线群的一个子集，则它是原椭圆曲线群的一个子群，而且是循环子群。子群中元素个数称为子群的阶(示例子群的阶为8)，点 P称为该子群的基点或者生成元。循环子群是椭圆曲线密码体系的基础，我们期望子群中元素越多越好，如何找到一个合适的子群尤为重要。

首先要解决一个问题，就是已知下的椭圆曲线上的点 P，如何求得 P的倍乘运算后生成的子群的阶?根据拉格朗日的群论定理，子群的阶是父群的阶的约数。求解曲线上点 P生成的子群的阶可以用下面方法：

以示例曲线为例，父群的阶是，则以曲线上的点生成的子群的阶只能是。对于点，故其生成的子群的阶就是 8，而点生成的子群的阶则正好等于父群的阶24。

在加密算法中，我们期望找到一个阶高的子群。不过，通常不是先去找个基点，然后计算子群的阶，因为这样过于不确定，算法上不好实现。相反地，先选择一个大的子群阶，然后再找生成该子群的一个基点就容易多了。

前面提到，子群的阶 n是父群的阶 N的约数，即有，h是一个整数，我们称之为子群的余因子(cofactor)。因为，所以有:

通常会选择一个素数作为子群的阶，即 n是素数。可以发现，点生成了阶为 n的子群(除外，因为这个子群的阶为1)，不等于的点就是我们寻找的基点。具体步骤如下：

需要注意，上面算法里的 n必须是素数，否则计算的基点 G生成的子群的阶可能是 n的约数而不是 n，不符合要求。以曲线为例，，我们选择，则，随机选取一个点，计算，恰好满足要求。

如前所述，椭圆曲线加密算法工作在素数域下的椭圆曲线循环子群中，需要的域参数(Domain Parameter)包括：

如比特币用来做数字签名中采用的椭圆曲线 [secp256k1]的域参数如下：

OKX欧易app

欧易交易所app是全球排名第一的虚拟货币交易所，注册领取6万元盲盒礼包!

APP下载 官网注册

binance币安交易所
已有2000万用户加入币安交易所

立即下载