计算机系统与网络安全技术（第2版）-课件 1-5-12 公钥密码学基础（ECC算法4）

第一章信息安全概述有限域上的椭圆曲线计算机系统与网络安全技术有限域上椭圆曲线：y2

x3+ax+bmodpp是奇素数,且4a3+27b2

0modp（构成Abel群的条件，证明过程略）y2+xy

x3+ax2+bmod2m(Galois域的椭圆曲线）有限域上的椭圆曲线含义有限域上的椭圆曲线信息安全概述（3）加法公式:P=(xp,yp),Q=(xQ,yQ)若xP=xQ且yP=-yQ则P+Q=O否则P+Q=(xR,yR)xR=

2-xP-xQyR=

(xP-xR)-yP其中

=(yQ-yP)/(xQ-xP),如果P

Q=(3xP2+a)/（2yP），如果P=Q（1）P+O=P（2）P=(x,y)P＋(x,-y)=O其中（x,-y)是P的负元－P(4)重复相加：nP=P+…+P按照上述定义构成了一个椭圆曲线上的Abel群椭圆曲线的运算规则有限域上的椭圆曲线信息安全概述示例：有限域上椭圆曲线

y2

x3+ax+bmodp条件：a=1,b=1,x=9,y=7,p=23y2

=x3+ax+b=(93+9+1)mod23=3椭圆曲线的运算规则有限域上的椭圆曲线信息安全概述示例：有限域上椭圆曲线

y2

x3+ax+bmodp条件：a=1,b=1,x=9,y=7,p=23问题：求满足上述方程的所有整数对（x，y）以及无穷远点O组成的集合Ep（a，b）＝E23（1，1）？椭圆曲线的运算规则有限域上的椭圆曲线信息安全概述椭圆曲线的运算规则E23（1，1）(0,1)(6,4)(12,19)(0,22)(6,19)(13,7)(1,7)(7,11)(13,16)(1,16)(7,12)(17,3)(3,10)(9,7)(17,20)(3,13)(9,16)(18,3)(4,0)(11,3)(18,20)(5,4)(11,20)(19,5)(5,19)(12,4)(19,18)有限域上的椭圆曲线信息安全概述椭圆曲线的运算规则E23（1，1）(0,1)(6,4)(12,19)(0,22)(6,19)(13,7)(1,7)(7,11)(13,16)(1,16)(7,12)(17,3)(3,10)(9,7)(17,20)(3,13)(9,16)(18,3)(4,0)(11,3)(18,20)(5,4)(11,20)(19,5)(5,19)(12,4)(19,18)1）P＝（0，1），P+O＝（0，1）2）P＝（13，7）

-P=（13，-7）=(13,16)3）P＝（3，10），Q＝（9，7）

P+Q=(17,20)4）P＝（3，10）

2P=(7,12)有限域上的椭圆曲线信息安全概述椭圆曲线的运算规则P＋Q计算过程：x3=

2-x1-x2y3=

(x1-x3)-y1其中

=(y2-y1)/(x2-x1),如果PQ=(3x12+a)/2y1,如果P=Q有限域上的椭圆曲线信息安全概述有限域上椭圆曲线y2+xy

x3+ax2+bmod2m(Galois域的椭圆曲线）（3）加法公式:P=(xP,yP),Q=(xQ,yQ),且P≠-Q,P≠Q则P+Q=(xR,yR)xR=

2+

+xP+xQ+ayR=

(xP+xR)+xR+yP其中

=(yQ+yP)/(xQ+xP)（1）P+O=P（2）P=(x,y)P＋(x,-y)=O其中（x,-y)是P的负元－P(4)若P=(xP,yP),则R＝2P=(xr,yr)其中：xR=

2+

+ayR