椭圆曲线密码算法.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下的运算规则 加法规则：对所有的点 PE(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,2P,3P,(n-1)P 是由P生成的椭圆曲线循环子群。素数p，椭圆曲线方程E，点P和阶n构成公开参数组。,私钥在区间1,n-1内随机选择的正整数d，相应的公钥是Q=dP。由公开参数组和公钥Q求私钥d的问题是椭圆曲线离散对数问题(ECDLP),密钥对生成,输入：椭圆曲线参数组(p,E,P,n)输出：公钥Q和私钥d选择d1，n计算Q=dP返回(Q,d),基本椭圆曲线加密,输入：椭圆曲线参数组(p,E,P,n)，公钥Q，明文m输出：密文(C1,C2)将明文m表示为E(FP)上的点M选择k1，n计算C1=kP计算C2=M+kQ返回(C1,C2),基本椭圆曲线解密,输入：椭圆曲线参数组(p,E,P,n)，私钥d，密文(C1,C2)输出：明文m计算M=?，并从点M取出明文m返回(m),