椭圆曲线密码学知识简介.pptVIP

第七章 椭圆曲线密码学 1 有关的基本概念 (1) 无穷远元素（无穷远点，无穷远直线） 平面上任意两相异直线的位置关系有相交和平行两种 。引入无穷远点，是两种不同关系统一。 ABL1， L2L1，直线AP由AB起绕A点依逆时针方向转 动，P为AP与L1的交点。 L2 L1 P B A P Q Q=BAP /2 AP L2 可设想L1上有一点P，它为L2和L1的交点，称之为无穷无穷 远点远点。 直线L1上的无穷远点只能有一个。 （因为过A点只能有一条平行于L1的直线L2，而两直线 的交点只能有一个。） 结论： 1*. 平面上一组相互平行的直线，有公共的无穷远点。 （为与无穷远点相区别，把原来平面上的点叫做平常点平常点 ） 2* .平面上任何相交的两直线L1,L2有不同的无穷远点。 原因：若否，则L1和L2有公共的无穷远点P，则过两相 异点A和P 有相异两直线，与公理相矛盾。 3*. 全体无穷远点构成一条无穷远直线。 注注：欧式平面添加上无穷远点和无穷远直线，自然构成 射影平面影平面。 (2) 齐次坐标 解析几何中引入坐标系，用代数的方法研究欧氏空 间。这样的坐标法也可推广至摄影平面上，建立平面摄 影 坐标系。 平面上两相异直线L1,L2，其方程分别为： L1: a1x+b1y+c1=0 L2: a2x+b2y+c2=0 A L1 L2 P 其中a1,b1不同时为0；a2,b2也不同时为0。 设 D= a1 b1 Dx= b1 c1 Dy= c1 a1 a2 b2 b2 c2 c2 a2 若D0，则两直线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，则L1L2，此时L1和L2交于一个无穷远点P。 这个点P可用过原点O且平行于L2的一条直线L来指出 他 的方向，而这条直线L的方程就是：a2x+b2y=0. 为把平常点和无穷远点的坐标统一起来，把点的坐标用 （X，Y，Z)表示，X，Y，Z不能同时为0，且对平常点 （x，y)来说，有Z0，x=X/Z，y=Y/Z，于是有： i.e. X / Dx = Y / Dy = Z / D， 有更好的坐标抽象，X,Y,Z),这样对于无穷远点则有Z=0 ， 也成立。 注： a).若实数p0，则(pX,pY,pZ)与（X,Y,Z)表示同一个点 。实质上用（X:Y:Z)表示。3个分量中，只有两个是 独立的，具有这种特征的坐标就叫齐次坐标齐次坐标。 i.e. b).设有欧氏直线L，它在平面直角坐标系Oxy上的方程 为： ax+by+c=0ax+by+c=0 则L上任一平常点(x,y)的齐次坐标为(X,Y,Z)，Z0Z0， 代入得： aXaX+ +bYbY+ +cZcZ=0=0 给L添加的无穷远点的坐标(X,Y,Z)应满足aXaX+ +bYbY=0=0 ，Z=0Z=0;平面上无穷远直线方程自然为：Z=0Z=0 ! (3)任意域上的椭圆曲线 K为域，K上的摄影平面P2(K)是一些等价类的集合 (X:Y:Z)。考虑下面的Weierstrass方程(次数为3的 齐次方程)： Y2Z+a1XYZ+a3YZ2=X3+a2X2z+a4XZ2+a6Z3 (其中系数aiK，或aiK为K的代数闭域） Weierstrass方程被称为光滑的或非奇异的是指对所有适合 以下方程的射影点P=(X:Y:Z) P2(K)来说， F(X,Y,Z)=Y2Z+a1XYZ+a3YZ2-X3-a2X2Z-a4XZ2-a6Z3=0 在P点的三个偏导数 之中至少有一个不 为 0若否称这个方程为奇异的。 椭圆曲线椭圆曲线E 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 (1) 此时，椭圆曲线E就是方程（1)在射影平面P2(K)上 的全部平常点解，外加一个无穷远点组成的集合。 c) 若a1,a2,a2,a4,a6K，此时椭圆曲线E被称为定义在K 上，用E/K表示。如果E能被限定在K上，那么E的K 有理点集合表示为E(K)，它为E中的全体有理坐标 点的集合外加无穷远点. (4)实域R上的椭圆曲线 设K=R，此时的椭圆曲线可表为平面上的通常曲线 上 的点，外加无穷远点。 实域实域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。 P Q P=Q L L L L (PQ) R= TT= (P=Q=R) PQ PQ R R T 上页的实际图像为椭圆曲线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) 注： a) 如果直线L与E相交与三点P,Q,R(不一定相异），那 么 (PQ)R=(从图中可见）。 b) 任给PE, P =P (此时设Q= ，易见L=L) c) 任给P,QE有： P Q =Q P d) 设PE，那么可以找到 - PE使P -P= e) 任给P,Q,RE，有(P Q) R= P (Q R) 综上所述，知E对 运算形成一个Abel群。 f) 上述规则可开拓到任意域上，特别是有限域上。假定 椭圆曲线是定义在有限域Fq上（q=pm)，那么 E(Fq)=(x,y)FqFq | y2+a1xy+a3y=x3+a2x2+a4x+a6 它对“ ”形成一个群，为Abel群。 2 有限域上椭圆曲线的运算 令Fq表示q个元素的有限域，用E(Fq)表示定义在Fq 上 的一个椭圆曲线E。 定理定理1. 1.( (HassHass定理定理) ) E(E(F F q q ) )的点数用的点数用 # # E(E(F F q q ) )表示，则表示，则 | | # # E(E(F F q q )-q-1|2q)-q-1|2q1/2 1/2 (1) Fp（素域，p为素数）上椭圆曲线 令p3，a,bFp，满足4a3+27b20，由参数a和b定 义的Fp上的一个椭圆曲线方程为： y2=x3+ax+b (2) 它的所有解(x,y)，(xFp，yFp)，连同一个称为“无穷 远 点”（记为）的元素组成的集合记为E(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) （3 ） (v)（倍点运算规则） 设(x1,y1) E(Fp),y10，则2(x1,y1)=(x3,y3)，其中 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个点（包括无穷远点 ）。 (2) F2m上的椭圆曲线 F2m上由参数a,bF2m，b0定义的一个非超奇异椭 圆曲线E(F2m)是方程 y2+xy=x3+ax2+b (5) 的解集合(x,y)，其中x,yF2m，连同 。 E(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)且有x1x2则 (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)，其中x10。则 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=F2x / (f(x) = (k0,k1,k2,k3) | (k0,k1,k2,k3)=k0+k1+k22+k33， 为f(x)的零点， kiF2 假定F24上的非超奇异椭圆曲线有下述方程定义： y2+xy=x3+4x2+1，注意f()=0。 方程应表为： (1000)y2 + (1000)xy = (1000)x3 + (1100)x2 +(1000) 3 椭圆曲线密码体制 1985年，N. Koblitz和V. Miller分别独立提出了椭 圆曲线密码体制(ECC)，其依据就是定义在椭圆曲线 点群上的离散对数问题的难解性。 （1）知E(Fq)对点的“”运算形成一个Abel群 设pE(Fq)，若p的周期很大，即使 p p p= (共有 t个p相加） 成立的最小正整数 t，希望 t 很大。 (t = p的周期，表示为(p)=t)。 并且对QE(Fq)，定有某个正整数m使 Q=mp=p p (共有t个p相加) 定义 m=pQ (m为以p为底Q的对数）。 椭圆曲线上的点形成的群E(Fq)，相关它的离散对 数 问题是难处理的。 （2） 建立椭圆曲线密码体制 选取基域Fq，Fq的椭圆曲线具体给定为确定的形式 。 在E(Fq)中选一个周期很大的点，如选了一个点P=(xp,yp) ， 它的周期为一个大的素数n，记 (P)=n(素数)。 注意：在这个密码体制中，具体的曲线及点P和它的n 都 是公开信息。密码体制的形式采用EIGamal体制，是完 全 类比过来。 a)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)