椭圆曲线密码学基础知识概要(精品).ppt
椭圆曲线密码学基础知识概要参考文献w1ECC加密算法入门介绍加密算法入门介绍作者：ZMWormCCGE-Mail：主页：Http:/ZMWorm.Yeah.Net/椭圆曲线基础知识一、摄影坐标系下的椭圆曲线二、椭圆曲线定义三、椭圆曲线上的加法四、密码学中的椭圆曲线五、椭圆曲线上简单的加密/解密六、密码学中的椭圆曲线参数与安全性一、摄影坐标系下的椭圆曲线w无穷远点：平行线相交于无穷远点Pw摄影坐标系：平面直角坐标系的扩展，能够表示无穷远点。w平面直角坐标系上的点A的坐标（x,y），令x=X/Z，y=Y/Z（Z0）；则点A在摄影坐标系可以表示为（X:Y:Z）。w无穷远点的直线方程是Z=0，无穷远点为（X:Y:0）求无穷远点例子例：求平行线L1：X+2Y+3Z=0与L2：X+2Y+Z=0相交的无穷远点。解：因为L1L2所以有Z=0，X+2Y=0；所以坐标为（-2Y:Y:0），Y0。即（-2:1:0）（-4:2:0）（-2.4:1.2:0）等形如（-2Y:Y:0），Y0的坐标，都表示这个无穷远点。二、椭圆曲线定义w平面直角坐标系下的椭圆曲线方程：y2+a1xy+a3y=x3+a2x2+a4x+a6 w摄影坐标系下的椭圆曲线方程：Y2Z+a1XYZ+a3YZ2=X3+a2X2Z+a4XZ2+a6Z3曲线上的每个点都是非奇异（或光滑）的。无穷远点为O（0:1:0）w椭圆曲线：平常点+无穷远点Ow椭圆曲线一点的切线斜率：f(x)=-Fx(x,y)/Fy(x,y)三、椭圆曲线上的加法w椭圆曲线上的加法运算法则：任意取椭圆曲线上两点P、Q（若P、Q两点重合，则做P点的切线）做直线交于椭圆曲线的另一点R，过R做y轴的平行线交于R。规定P+Q=R。O+P=P。k个相同的点P相加，记作kP。w椭圆曲线上的点和无穷远点构成和加法运算构成一个交换群（除了满足一般的群公理，即运算的结合律、G有单位元、所有G的元素都有逆元之外，还满足交换律公理。）。无穷远点O称为零元。四、密码学中的椭圆曲线（1/2）w椭圆曲线定义在有限域上，连续的椭圆曲线变成离散的点。w有限域Fp，这个域只有有限个元素。Fp中只有p（p为素数）个元素0,1,2p-2,p-1；Fp的加法（a+b）法则是a+bc(modp)；即，(a+c)p的余数和cp的余数相同。Fp的乘法(ab)法则是abc(modp)；Fp的除法(ab)法则是a/bc(modp)；即ab-1c(modp)；（b-1也是一个0到p-1之间的整数，但满足bb-11(modp)；Fp的单位元是1，零元是0。wy2=x3+ax+b（最简单的一类可以用来加密的椭圆曲线）把y2=x3+ax+b这条曲线定义在Fp上：选择两个满足下列条件的小于p(p为素数)的非负整数a、b4a3+27b20(modp)则满足下列方程的所有点(x,y)，再加上无穷远点O，构成一条椭圆曲线。y2=x3+ax+b(modp)其中x,y属于0到p-1间的整数，并将这条椭圆曲线记为Ep(a,b)。w椭圆曲线上点的阶：如果椭圆曲线上一点P，存在最小的正整数n，使得数乘nP=O，则将n称为P的阶阶，若n不存在，我们说P是无限阶的。事实上，在有限域上定义的椭圆曲线上所有的点的阶n都是存在的四、密码学中的椭圆曲线（2/2）wy2=x3+x+1(mod23)的图像1无穷远点O是零元，有O+O=O，O+P=P2P(x,y)的负元是(x,-y)，有P+(-P)=O3P(x1,y1),Q(x2,y2)的和R(x3,y3)有如下关系：x3k2-x1-x2(modp)y3k(x1-x3)-y1(modp)其中若P=Q则k=(3x2+a)/2y1若PQ，则k=(y2-y1)/(x2-x1)五、椭圆曲线上简单的加密/解密（1/2）w困难问题K=kG其中K,G为Ep(a,b)上的点，k为小于n（n是点G的阶）的整数给定k和G，根据加法法则，计算K很容易；但给定K和G，求k就相对困难。五、椭圆曲线上简单的加密/解密（2/2）w一个利用椭圆曲线进行加密通信的过程：1、用户A选定一条椭圆曲线Ep(a,b)，并取椭圆曲线上一点，作为基点G。2、用户A选择一个私有密钥k，并生成公开密钥K=kG。3、用户A将Ep(a,b)和点K，G传给用户B。4、用户B接到信息后，将待传输的明文编码到Ep(a,b)上一点M（编码方法很多），并产生一个随机整数r（rn）。5、用户B计算点C1=M+rK；C2=rG。6、用户B将C1、C2传给用户A。7、用户A接到信息后，计算C1-kC2，结果就是点M。因为C1-kC2=M+rK-k(rG)=M+rK-r(kG)=M再对点M进行解码就可以得到明文。w在这个加密通信中，如果有一个偷窥者H，他只能看到Ep(a,b)、K、G、C1、C2而通过K、G求k或通过C2、G求r都是相对困难的。因此，H无法得到A、B间传送的明文信息。六、密码学中椭圆曲线参数与安全性w密码学中，描述一条Fp上的椭圆曲线，常用到六个参量：T=(p,a,b,G,n,h)。（p、a、b用来确定一条椭圆曲线，G为基点，n为点G的阶，h是椭圆曲线上所有点的个数m与n相除的整数部分）这几个参量取值的选择，直接影响了加密的安全性。参量值一般要求满足以下几个条件：1、p当然越大越安全，但越大，计算速度会变慢，200位左右可以满足一般安全要求；2、pnh；3、pt1(modn)，1t20；4、4a3+27b20(modp)；5、n为素数；6、h4。
