椭圆曲线密码学基础知识概要

《椭圆曲线密码学基础知识概要》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、椭圆曲线密码学基础知识概要参考文献[1]ECC加密算法入门介绍作者 ：ZMWorm[CCG]E-Mail：zmworm@sohu.com主页 ：Http://ZMWorm.Yeah.Net/椭圆曲线基础知识一、摄影坐标系下的椭圆曲线二、椭圆曲线定义三、椭圆曲线上的加法四、密码学中的椭圆曲线五、椭圆曲线上简单的加密/解密六、密码学中的椭圆曲线参数与安全性一、摄影坐标系下的椭圆曲线无穷远点：平行线相交于无穷远点P∞摄影坐标系：平面直角坐标系的扩展，能够表示无穷远点。平面直角坐标系上的点A的坐标（x,y），令x=X/Z，y=Y/Z（Z≠0）；则点A在摄影

2、坐标系可以表示为（X:Y:Z）。无穷远点的直线方程是Z=0，无穷远点为（X:Y:0）求无穷远点例子例：求平行线L1：X+2Y+3Z=0与L2：X+2Y+Z=0相交的无穷远点。解：因为L1∥L2所以有Z=0，X+2Y=0；所以坐标为（-2Y:Y:0），Y≠0。即（-2:1:0）（-4:2:0）（-2.4:1.2:0）等形如（-2Y:Y:0），Y≠0的坐标，都表示这个无穷远点。二、椭圆曲线定义平面直角坐标系下的椭圆曲线方程：y2+a1xy+a3y=x3+a2x2+a4x+a6摄影坐标系下的椭圆曲线方程：Y2Z+a1XYZ+a3YZ2=X3+a2X2Z+

3、a4XZ2+a6Z3曲线上的每个点都是非奇异（或光滑）的。无穷远点为O∞（0:1:0）椭圆曲线：平常点+无穷远点O椭圆曲线一点的切线斜率：f'(x)=-Fx(x,y)/Fy(x,y)三、椭圆曲线上的加法椭圆曲线上的加法运算法则：任意取椭圆曲线上两点P、Q（若P、Q两点重合，则做P点的切线）做直线交于椭圆曲线的另一点R’，过R’做y轴的平行线交于R。规定P+Q=R。O∞+P=P。k个相同的点P相加，记作kP。椭圆曲线上的点和无穷远点构成和加法运算构成一个交换群（除了满足一般的群公理，即运算的结合律、G有单位元、所有G的元素都有逆元之外，还满足交换律公理

4、。）。无穷远点O∞称为零元。四、密码学中的椭圆曲线（1/2）椭圆曲线定义在有限域上，连续的椭圆曲线变成离散的点。有限域Fp，这个域只有有限个元素。Fp中只有p（p为素数）个元素0,1,2……p-2,p-1；Fp的加法（a+b）法则是a+b≡c(modp)；即，(a+c)÷p的余数和c÷p的余数相同。Fp的乘法(a×b)法则是a×b≡c(modp)；Fp的除法(a÷b)法则是a/b≡c(modp)；即a×b-1≡c (modp)；（b-1也是一个0到p-1之间的整数，但满足b×b-1≡1(modp)；Fp的单位元是1，零元是0。y2=x3+ax+b（最

5、简单的一类可以用来加密的椭圆曲线）把y2=x3+ax+b这条曲线定义在Fp上： 选择两个满足下列条件的小于p(p为素数)的非负整数a、b   4a3+27b2≠0(modp)则满足下列方程的所有点(x,y)，再加上无穷远点O∞，构成一条椭圆曲线。y2=x3+ax+b (modp)其中x,y属于0到p-1间的整数，并将这条椭圆曲线记为Ep(a,b)。椭圆曲线上点的阶：如果椭圆曲线上一点P，存在最小的正整数n，使得数乘nP=O∞，则将n称为P的阶，若n不存在，我们说P是无限阶的。  事实上，在有限域上定义的椭圆曲线上所有的点的阶n都是存在的四、密码

6、学中的椭圆曲线（2/2）y2=x3+x+1 (mod23)的图像1无穷远点O∞是零元，有O∞+O∞=O∞，O∞+P=P  2P(x,y)的负元是(x,-y)，有P+(-P)=O∞  3P(x1,y1),Q(x2,y2)的和R(x3,y3)有如下关系：x3≡k2-x1-x2(modp)   y3≡k(x1-x3)-y1(modp)其中若P=Q则k=(3x2+a)/2y1若P≠Q，则k=(y2-y1)/(x2-x1)五、椭圆曲线上简单的加密/解密（1/2）困难问题K=kG [其中K,G为Ep(a,b)上的点，k为小于n（n是点G的阶）的整数]给定k

7、和G，根据加法法则，计算K很容易；但给定K和G，求k就相对困难。五、椭圆曲线上简单的加密/解密（2/2）一个利用椭圆曲线进行加密通信的过程：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（r

8、点M。因为C1-kC2=M+rK-k(rG)=M+rK-r(kG)=M再对点M进行解码就可以得到明文。在这个