信息安全专题讲座07课件

Q=∠BAP→/2AP→L2可设想L1上有一点P∞，它为L2和L1的交点，称之为无穷远点。直线L1上的无穷远点只能有一个。（因为过A点只能有一条平行于L1的直线L2，而两直线的交点只能有一个。）结论：1*.平面上一组相互平行的直线，有公共的无穷远点。（为与无穷远点相区别，把原来平面上的点叫做平常点）2*.平面上任何相交的两直线L1,L2有不同的无穷远点。原因：若否，则L1和L2有公共的无穷远点P∞，则过两相异点A和P∞有相异两直线，与公理相矛盾。Q=∠BAP→/2AP→13*.全体无穷远点构成一条无穷远直线。注：欧式平面添加上无穷远点和无穷远直线，自然构成射影平面。(2)齐次坐标解析几何中引入坐标系，用代数的方法研究欧氏空间。这样的坐标法也可推广至摄影平面上，建立平面摄影坐标系。

平面上两相异直线L1,L2，其方程分别为：

L1:a1x+b1y+c1=0 L2:a2x+b2y+c2=0AL1L2P∞3*.全体无穷远点构成一条无穷远直线。AL1L2P∞2其中a1,b1不同时为0；a2,b2也不同时为0。设

D=a1b1Dx=b1c1Dy=c1a1a2b2b2c2c2a2若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.其中a1,b1不同时为0；a2,b2也不同时为0。3为把平常点和无穷远点的坐标统一起来，把点的坐标用（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个分量中，只有两个是独立的，具有这种特征的坐标就叫齐次坐标。i.e.为把平常点和无穷远点的坐标统一起来，把点的坐标用i.e.4b).设有欧氏直线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

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

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

(其中系数ai∈K，或ai∈K为K的代数闭域）b).设有欧氏直线L，它在平面直角坐标系Oxy上的方程为：5Weierstrass方程被称为光滑的或非奇异的是指对所有适合以下方程的射影点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)用θ表示。Weierstrass方程被称为光滑的或非奇异的是指对所有适6b)可用非齐次坐标的形式来表示椭圆曲线的Weierstrass方程:设x=X/Z，y=Y/Z，于是原方程转化为：

y2+a1xy+a3y=x3+a2x2+a4x+a6(1)此时，椭圆曲线E就是方程（1)在射影平面P2(K)上的全部平常点解，外加一个无穷远点θ组成的集合。c)若a1,a2,a2,a4,a6∈K，此时椭圆曲线E被称为定义在K上，用E/K表示。如果E能被限定在K上，那么E的K——有理点集合表示为E(K)，它为E中的全体有理坐标点的集合外加无穷远点θ.(4)实域R上的椭圆曲线设K=R，此时的椭圆曲线可表为平面上的通常曲线上的点，外加无穷远点θ。b)可用非齐次坐标的形式来表示椭圆曲线的Weier7实域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的另一个交点定义为PQ。信息安全专题讲座07课件8PQP=QLLL′L′(PQ)

R=θθθTT=θ(P=Q=R)PQPQRRTPQP=QLLL′L′(PQ)R=θθθTT=θP9上页的实际图像为椭圆曲线y2=x3-x的一般化。来自对具体曲线的抽象。对运算更具体一些：设P=(x1,y1)，Q=(x2,y2)，PQ=(x3,y3),由PQ的定义，设y=αx+β为通过P,Q两点直线L的方程，可算出：

α=(y2-y1)/(x2-x1),β=y1-αx1

易见，直线L上的一个点（x,αx+β)是在椭圆曲线E上，当且仅当(αx+β)2=x3–x。

PQ=(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时：

PQ=（x3，y3）算得：x3=((3x12-1)/2y1)2-2x1;y3=-y1+((3x12-1)/2y1)(x1-x3)

上页的实际图像为椭圆曲线y2=x3-x的一般化。10注：a)如果直线L与E相交与三点P,Q,R(不一定相异），那么(PQ)R=θ(从图中可见）。b)任给P∈E,Pθ=P(此时设Q=θ，易见L=L′)c)任给P,Q∈E有：PQ=QPd)设P∈E，那么可以找到-P∈E使P-P=θe)任给P,Q,R∈E，有(PQ)R=P(QR)综上所述，知E对运算形成一个Abel群。f)上述规则可开拓到任意域上，特别是有限域上。假定椭圆曲线是定义在有限域Fq上（q=pm)，那么

E(Fq)={(x,y)∈Fq×Fq|y2+a1xy+a3y=x3+a2x2+a4x+a6}∪{θ}它对“”形成一个群，为Abel群。注：112有限域上椭圆曲线的运算令Fq表示q个元素的有限域，用E(Fq)表示定义在Fq上的一个椭圆曲线E。定理1.(Hass定理)

E(Fq)的点数用#E(Fq)表示，则

|#E(Fq)-q-1|≤2q1/2(1)Fp（素域，p为素数）上椭圆曲线

令p>3，a,b∈Fp，满足4a3+27b2≠0，由参数a和b定义的Fp上的一个椭圆曲线方程为：y2=x3+ax+b(2)它的所有解(x,y)，(xFp，yFp)，连同一个称为“无穷远点”（记为θ）的元素组成的集合记为E(Fp)，由Hass定理2有限域上椭圆曲线的运算令Fq表示q12知：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)（3）(v)（倍点运算规则）设(x1,y1)∈E(Fp),y1≠0，则2(x1,y1)=(x3,y3)，其中知：p+1-2p1/2≤#E(Fp)≤p+1+2p1/213

x3=α2-2x1,y3=α(x1-x3)-y1这里α=(3x12+a)/(2y1)(4)注：若#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)，(6,19)，(7,11)，(7,12)，(9,7)，(9,16)，(11,3)，(11,20)，(12,4)，(12,19)，(13,7)，(13,16)，(17,3)，(17,20)，(18,3)，(18,20)，(19,5)，(19,18)；θ。群E(F23)有28个点（包括无穷远点θ）。x3=α2-2x1,y3=α(x1-14(2)F2m上的椭圆曲线

F2m上由参数a,b∈F2m，b≠0定义的一个非超奇异椭圆曲线E(F2m)是方程y2+xy=x3+ax2+b(5)的解集合(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则(2)F2m上的椭圆曲线F2m上由参数a,b∈15(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上的一个不可约多项式，易见

(x1,y1)(x2,y2)=(x3,y316F24=F2[x]/(f(x))={(k0,k1,k2,k3)|(k0,k1,k2,k3)=k0+k1α+k2α2+k3α3，α为f(x)的零点，ki∈F2}假定F24上的非超奇异椭圆曲线有下述方程定义：y2+xy=x3+α4x2+1，注意f(α)=0。方程应表为：(1000)y2+(1000)xy=(1000)x3+(1100)x2+(1000)F24=F2[x]/(f(x))=173椭圆曲线密码体制1985年，N.Koblitz和V.Miller分别独立提出了椭圆曲线密码体制(ECC)，其依据就是定义在椭圆曲线点群上的离散对数问题的难解性。（1）知E(Fq)对点的“”运算形成一个Abel群设p∈E(Fq)，若p的周期很大，即使

pp……p=θ(共有t个p相加）成立的最小正整数t，希望t很大。(t=p的周期，表示为∏(p)=t)。并且对Q∈E(Fq)，定有某个正整数m使

Q=m·p=p……p(共有t个p相加)3椭圆曲线密码体制1985年，18定义

m=㏒pQ(m为以p为底Q的对数）。椭圆曲线上的点形成的群E(Fq)，相关它的离散对数问题是难处理的。（2）建立椭圆曲线密码体制

选取基域Fq，Fq的椭圆曲线具体给定为确定的形式。在E(Fq)中选一个周期很大的点，如选了一个点P=(xp,yp)，它的周期为一个大的素数n，记∏(P)=n(素数)。注意：在这个密码体制中，具体的曲线及点P和它的n都是公开信息。密码体制的形式采用EIGamal体制，是完全类比过来。定义19a)密钥的生成

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)步.a)密钥的生成

Bob(使用者）执行了下列计算：20精品课件！精品课件！21精品课件！精品课件！22ⅵ)计算C:=m·x2

ⅶ)传送加密数据(x1,y1,C)给Bobb)Bob的解密过程Bob收到Alice的密文(x1,y1,C)后，执行i)使用私钥d，计算点(x2，y2):=d(x1,y1)，再计算Fq中x2-1=?Ii)通过计算m:=C·x2-1，恢复出明文数据m。ⅵ)计算C:=m·x223Q=∠BAP→/2AP→L2可设想L1上有一点P∞，它为L2和L1的交点，称之为无穷远点。直线L1上的无穷远点只能有一个。（因为过A点只能有一条平行于L1的直线L2，而两直线的交点只能有一个。）结论：1*.平面上一组相互平行的直线，有公共的无穷远点。（为与无穷远点相区别，把原来平面上的点叫做平常点）2*.平面上任何相交的两直线L1,L2有不同的无穷远点。原因：若否，则L1和L2有公共的无穷远点P∞，则过两相异点A和P∞有相异两直线，与公理相矛盾。Q=∠BAP→/2AP→243*.全体无穷远点构成一条无穷远直线。注：欧式平面添加上无穷远点和无穷远直线，自然构成射影平面。(2)齐次坐标解析几何中引入坐标系，用代数的方法研究欧氏空间。这样的坐标法也可推广至摄影平面上，建立平面摄影坐标系。

平面上两相异直线L1,L2，其方程分别为：

L1:a1x+b1y+c1=0 L2:a2x+b2y+c2=0AL1L2P∞3*.全体无穷远点构成一条无穷远直线。AL1L2P∞25其中a1,b1不同时为0；a2,b2也不同时为0。设

D=a1b1Dx=b1c1Dy=c1a1a2b2b2c2c2a2若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.其中a1,b1不同时为0；a2,b2也不同时为0。26为把平常点和无穷远点的坐标统一起来，把点的坐标用（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个分量中，只有两个是独立的，具有这种特征的坐标就叫齐次坐标。i.e.为把平常点和无穷远点的坐标统一起来，把点的坐标用i.e.27b).设有欧氏直线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

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

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

(其中系数ai∈K，或ai∈K为K的代数闭域）b).设有欧氏直线L，它在平面直角坐标系Oxy上的方程为：28Weierstrass方程被称为光滑的或非奇异的是指对所有适合以下方程的射影点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)用θ表示。Weierstrass方程被称为光滑的或非奇异的是指对所有适29b)可用非齐次坐标的形式来表示椭圆曲线的Weierstrass方程:设x=X/Z，y=Y/Z，于是原方程转化为：

y2+a1xy+a3y=x3+a2x2+a4x+a6(1)此时，椭圆曲线E就是方程（1)在射影平面P2(K)上的全部平常点解，外加一个无穷远点θ组成的集合。c)若a1,a2,a2,a4,a6∈K，此时椭圆曲线E被称为定义在K上，用E/K表示。如果E能被限定在K上，那么E的K——有理点集合表示为E(K)，它为E中的全体有理坐标点的集合外加无穷远点θ.(4)实域R上的椭圆曲线设K=R，此时的椭圆曲线可表为平面上的通常曲线上的点，外加无穷远点θ。b)可用非齐次坐标的形式来表示椭圆曲线的Weier30实域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的另一个交点定义为PQ。信息安全专题讲座07课件31PQP=QLLL′L′(PQ)

R=θθθTT=θ(P=Q=R)PQPQRRTPQP=QLLL′L′(PQ)R=θθθTT=θP32上页的实际图像为椭圆曲线y2=x3-x的一般化。来自对具体曲线的抽象。对运算更具体一些：设P=(x1,y1)，Q=(x2,y2)，PQ=(x3,y3),由PQ的定义，设y=αx+β为通过P,Q两点直线L的方程，可算出：

α=(y2-y1)/(x2-x1),β=y1-αx1

易见，直线L上的一个点（x,αx+β)是在椭圆曲线E上，当且仅当(αx+β)2=x3–x。

PQ=(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时：

PQ=（x3，y3）算得：x3=((3x12-1)/2y1)2-2x1;y3=-y1+((3x12-1)/2y1)(x1-x3)

上页的实际图像为椭圆曲线y2=x3-x的一般化。33注：a)如果直线L与E相交与三点P,Q,R(不一定相异），那么(PQ)R=θ(从图中可见）。b)任给P∈E,Pθ=P(此时设Q=θ，易见L=L′)c)任给P,Q∈E有：PQ=QPd)设P∈E，那么可以找到-P∈E使P-P=θe)任给P,Q,R∈E，有(PQ)R=P(QR)综上所述，知E对运算形成一个Abel群。f)上述规则可开拓到任意域上，特别是有限域上。假定椭圆曲线是定义在有限域Fq上（q=pm)，那么

E(Fq)={(x,y)∈Fq×Fq|y2+a1xy+a3y=x3+a2x2+a4x+a6}∪{θ}它对“”形成一个群，为Abel群。注：342有限域上椭圆曲线的运算令Fq表示q个元素的有限域，用E(Fq)表示定义在Fq上的一个椭圆曲线E。定理1.(Hass定理)

E(Fq)的点数用#E(Fq)表示，则

|#E(Fq)-q-1|≤2q1/2(1)Fp（素域，p为素数）上椭圆曲线

令p>3，a,b∈Fp，满足4a3+27b2≠0，由参数a和b定义的Fp上的一个椭圆曲线方程为：y2=x3+ax+b(2)它的所有解(x,y)，(xFp，yFp)，连同一个称为“无穷远点”（记为θ）的元素组成的集合记为E(Fp)，由Hass定理2有限域上椭圆曲线的运算令Fq表示q35知：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)（3）(v)（倍点运算规则）设(x1,y1)∈E(Fp),y1≠0，则2(x1,y1)=(x3,y3)，其中知：p+1-2p1/2≤#E(Fp)≤p+1+2p1/236

x3=α2-2x1,y3=α(x1-x3)-y1这里α=(3x12+a)/(2y1)(4)注：若#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)，(6,19)，(7,11)，(7,12)，(9,7)，(9,16)，(11,3)，(11,20)，(12,4)，(12,19)，(13,7)，(13,16)，(17,3)，(17,20)，(18,3)，(18,20)，(19,5)，(19,18)；θ。群E(F23)有28个点（包括无穷远点θ）。x3=α2-2x1,y3=α(x1-37(2)F2m上的椭圆曲线

F2m上由参数a,b∈F2m，b≠0定义的一个非超奇异椭圆曲线E(F2m)是方程y2+xy=x3+ax2+b(5)的解集合(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则(2)F2m上的椭圆曲线F2m上由参数a,b∈38(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上的一个不可约多项式，