椭圆曲的线密码算法.ppt

在这个加密通信中，如果有一个偷窥者H ，他只能看到Ep(a,b)、K、G、C1、C2 而通过K、G 求k 或通过C2、G求r 都是相对困难的。因此，H无法得到A、B间传送的明文信息。 * 作者签名用到了：椭圆曲线Ep(a,b)，基点G，私有密钥k，及随机数r。 软件验证用到了：椭圆曲线Ep(a,b)，基点G，公开密钥K。 Cracker要想制作注册机，只能通过软件中的Ep(a,b)，点G，公开密钥K ，并利用K=kG这个关系获得k后，才可以。而求k是很困难的。 * 椭圆曲线密码算法(ECC) Content 椭圆曲线是由Neil Koblitz和Victor Miller两位学者分别于1985年首先独立提出。 椭圆曲线具有的性质： 有限域上椭圆曲线在点加运算下构成有限交换群，且其阶与基域规模相近； 类似于有限域乘法群中的乘幂运算，椭圆曲线多倍点运算构成一个单向函数 RSA与ElGamal系统中需要使用长度为1024位的模数，才能达到足够的安全等级。而ECC只需使用长度为160位的模数即可，且传送密文或签章所需频宽较少，并已正式列入IEEE 1363标准 使ECC成为构造公开密钥密码体制一个有力的工具。 椭圆曲线并非椭圆，之所以称为椭圆曲线是因为它的曲线方程与计算椭圆周长的方程类似。 椭圆曲线的方程： 其中a, b, c, d, e是满足某些简单条件的实数。 一条椭圆曲线E(x,y)是由全体解(x,y)再加上一个无穷远点构成的集合。(椭圆曲线上的是有限的) 椭圆曲线有一个特殊的点，记为O，它并不在椭圆曲线E上，此点称为无穷远点。 在实数域中，椭圆曲线可定义成 若方程式没有重复的因式或 ，E（a,b）是一条非奇异椭圆曲线。 否则，E（a,b）是一条奇异椭圆曲线（某些数的逆元素(inverse)将不存在）。 满足方程的任意一点是否都存在切线 加法运算 两异点相加：假设P和Q是椭圆曲线上两个相异的点，而且P不等于-Q 。若P +Q=R ，则点R是经过P、Q两点的直线与椭圆曲线相交之唯一交点的负点。 双倍的点：令P +P=2P ，则点2P是经过P的切线与椭圆曲线相交之唯一交点的负点。 椭圆曲线运算规则 椭圆曲线在模p下的运算规则 加法规则： 对所有的点 P?E(Fp)，则P+O=O+P ，P+(-P)=O 令 及 且 ，则 如果 ，则对所有的点 而言， 乘法规则： 如果 ，则对所有的点 而言， kP=P+P+…+ P (k个P相加) 如果 ，则对所有的点 而 言， 如果椭圆曲线上一点P，存在最小的正整数n，使得数乘nP =O，则将n称为P的阶，若n不存在，我们说P是无限阶的. 事实上，在有限域上定义的椭圆曲线上所有的点的阶n都是存在的. 例1：有限域F23之下，点 是椭圆曲线 的生成数。求nP P = (0, 1) 2P = (13, 13) 3P = (5, 5) 4P = (3, 15) 5P = (6, 17) 6P = (19, 2) 7P = (17, 9) 8P = (18, 0) 9P = (17, 14) 10P = (19, 21) 11P = (6, 6) 12P = (3, 8) 13P = (5, 18) 14P = (13, 10) 15P = (0, 22) 注： 其实还要加上一个无穷远点，故E上的点共有16个，点P的秩n = 16。 在坐标上画出，并观察图像特点 例2：在有限域F23之下，取椭圆曲线 上的两点 及 若 则 R = ? 例3：条件同例2，若 ，则R ? 椭圆曲线在 下的运算规则 加法规则： 对所有的点 则 ， 令 及 ， 且 ，则x3,y3分别为 如果 ，则对所有的点 而言