第四章公钥密码介绍.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 椭圆曲线的方程是以下形式的三次方程： y2+axy+by=x3+cx2+dx+e (4.1) 其中a，b，c，d，e是满足某些简单条件的实数。定义中包括一个称为无穷远点的元素，记为O。图1 是椭圆曲线的两个例子。 4.6.1 椭圆曲线 图1 椭圆曲线的两个例子 点加法运算： 如果其上的3个点位于同一直线上，那么它们的和为O。 椭圆曲线上的加法律： ① O为加法单位元，即对椭圆曲线上任一点P，有P+O=P。 ② 设P1=(x,y)是椭圆曲线上的一点，它的加法逆元定义为P2=-P1=(x, -y)。 这是因为P1、P2的连线延长到无穷远时，得到椭圆曲线上的另一点O，即椭圆曲线上的3点P1、P2，O共线，所以P1+P2+O=O，P1+P2=O，即P2=-P1。 由O+O=O，还可得O=-O ③ 设Q和R是x坐标不同的两点，Q+R的定义： 画一条通过Q、R的直线与椭圆曲线交于P1。由Q+R+P1=O 得Q+R=-P1。 ④ 点Q的倍数： 在Q点做椭圆曲线的一条切线，设切线与椭圆曲线交于点S，定义2Q=Q+Q=-S。类似地可定义3Q=Q+Q+Q+，…，等。 以上定义的加法具有加法运算的一般性质，如交换律、结合律等。 密码中普遍采用的是有限域上的椭圆曲线，是指曲线方程定义式中，所有系数都是某一有限域GF(p)中的元素（p为一大素数）。其中最为常用的是由方程 y2≡x3+ax+b(mod p) (a,b∈GF(p),4a3+27b2≠0(modp)) (4.2) 定义的曲线。 4.6.2 有限域上的椭圆曲线 例 p=23，a=b=1，4a3+27b2(mod 23)≡8≠0 ，方程(4.2)为y2≡x3+x+1，其图形是连续曲线。 (b) y 2 = x 3 + x +1 R Q P 1 -P 1 2 3 -2 1 -1 0 -4 -2 2 4 (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) 点集E23(1,1) 一般来说，Ep(a,b)由以下方式产生： ① 对每一x(0≤xp且x为整数），计算x3+ax+b(mod p)。 ② 决定①中求得的值在模p下是否有平方根，如果没有，则曲线上没有与这一x相对应的点；如果有，则求出两个平方根（y=0 时只有一个平方根）。 Ep(a,b)上的加法定义如下： 设P, Q∈Ep(a,b)，则 ① P+O=P。 ② 如果P=(x,y)，那么(x, y)+(x, -y)=O，即 (x, -y)是P的加法逆元，表示为-P。 由Ep(a,b)的产生方式知，-P也是Ep(a,b)中的点，如上例，P=(13,7)∈E23(1,1)，-P=(13, -7)， 而 -7mod 23≡16，所以-P=(13, 16)，也在E23(1,1)中。 ③ 设P=(x1,y1)，Q=(x2,y2)，P≠-Q，则P+Q=(x3,y3)由以下规则确定： x3≡λ2-x1-x2(mod p) y3≡λ(x1-x3)-y1(mod p) 其中 例 以E23(1,1)为例，设P=(3,10)，Q=(9,7)，则 所以P+Q=(17,20)，仍为E23(1,1)中的点。 x3≡λ2-x1-x2(mod p),y3≡λ(x1-x3)-y1(mod p) 若求2P则 所以2P=(7,12)。 x3≡λ2-x1-x2(mod p),y3≡λ(x1-x3)-y1(mod p) 倍点运算仍定义为重复加法，如4P=P+P+P+P。 可以看出，加法在E23(1,1)中是封闭的，且能验证还满足交换律。对一般的Ep(a,b)，可证其上的加法运算是封闭的、满足交换律，同样还能证明其上的加法逆元运算也是封闭的，所以Ep(a,b)是一个Abel群。 4.6.3 明文消息嵌入到椭圆曲线上 设明文消息为m, k是一个足够大的整数，使得将明文消息镶嵌到椭圆曲线上时，错误概率是