椭圆曲线密码算法.ppt

椭圆曲线密码算法(ECC) 椭圆曲线是由Neil Koblitz(Koblitz, 1985)和Victor Miller(Miller, 1985)两位学者分别于1985年首先提出 大多数的椭圆曲线密码系统是在模p或F2n下运算。此密码系统仍是存有RSA或ElGamal常见的弱点(e.g. 同模数攻击、低指数攻击)。 RSA与ElGamal系统中需要使用长度为 1024位的模数，才能达到足够的安全等 级 而ECC只需使用长度为160位的模数即可， 且传送密文或签章所需频宽较少，并已正式列入IEEE 1363标准 椭圆曲线密码系统基于椭圆曲线离散对数问题(Elliptic Curve Discrete Logarithm Problem, ECDLP)。 即在有限域K之下，给定椭圆曲线E上的两相异点P及Q，其中当点P的秩(order)若够大时(大于160位)，要找出一整数l使得Q=lP是很难的计算难题。 在实数域中，椭圆曲线可定义成所有满足方程式 的点(x,y)所构成的集合。若方程式没有重复的因式或 ，则 能成为群(group)。 例如，椭圆曲线 的图形如图1-1所示。若 ，则此曲线将会形成退化(某些数的逆元素(inverse)将不存在)。 椭圆曲线 的图形如图1-1所示。 椭圆曲线密码系统在模p(或Fp)下定义为椭圆曲线 其中 模F2n下定义为椭圆曲线 其中 ，此曲线称为nonsuper-singular。 椭圆曲线有一个特殊的点，记为O，它并不在椭圆曲线E上，此点称为无穷远点(the point at infinity) 两个相异的点相加：假设P和Q是椭圆曲线上两个相异的点，而且P不等于-Q 。若P +Q=R ，则点R是经过P、Q两点的直线与椭圆曲线相交之唯一交点的负点。如图1-2所示。 双倍的点：令P +P=2P ，则点2P是经过P的切线与椭圆曲线相交之唯一交点的负点。如图1-3所示。 椭圆曲线运算规则 椭圆曲线在模p下的运算规则 加法规则： 对所有的点 P?E(Fp)，则P+O=O+P ， P+(-P)=O (ii) 令 及 且 ，则 ，其中 (iii) 如果 ，则对所有的点 而言， 乘法规则： 如果 ，则对所有的点 而言，kP=P+P+…+ P (k个P相加) 如果 ，则对所有的点 而 言， 例子1：有限域F23之下，点 是椭圆曲线 的生成数。 请计算2P和3P的值 注： 其实还要加上一个无穷远点，故E上的点共有16个，点P的秩n = 16。 例2：在有限域F23之下，取椭圆曲线 上的两点 及 若 则 R = ? 例3：条件同例2，若 ， 则R = ? 解： 椭圆曲线在 下的运算规则 加法规则： 对所有的点 则 ， 令 及 ，且 。则 ，其x3,y3分别为： (iii) 如果 ，则对所有的点 而言， 例子4：在有限域 之下，取椭圆曲线 y2+xy=x3+g8x2+g2 上的两点P=(g3,g9) 及Q=(g,g5) ，其中 g=(0010) 为 的生成数，且不可约多项式为 f(x)=x4+x+1 。若 P+Q=R=(x3,y3) 则R = ? 注：g的乘幂如下 例5 条件同例4，若 则R = ? 解： 椭圆曲线密钥生成 令E是FP上的椭圆曲线，P是E(FP)上的点，设P的阶是素数n，则集合 P={∞,P,2P,3P,…,(n-1)P}