第十一讲 椭圆曲线_图文.ppt

第十一讲椭圆曲线 1984 年, Hendrik Lenstra 提出了依靠椭圆曲线性质分解整数的精妙算法。这一发现激发了学者进一步研究椭圆曲线在密码和计算数论的其它应用。椭圆曲线密码在 1985 年分别由 Neal Koblitz 和 Victor Miller 提出。椭圆曲线密码方案为公钥机制,提供如同 RSA 一样的功能。但是, 它的安全性依赖不同的困难问题,也就是椭圆曲线离散对数问题(ECDLP) 。我们知道解决分解整数问题需要亚指数时间复杂度的算法,而目前已知计算 ECDLP 的最好方法都需要全指数时间复杂度。这意味着在椭圆曲线系统中我们只需要使用相对于 RSA 短得多的密钥就可以达到与其相同的安全强度。例如,一般认为 160 比特的椭圆曲线密钥提供的安全强度与 1024 比特 RSA 密钥相当。使用短的密钥的好处在于加解密速度快、节省能源、节省带宽、存储空间。本讲提要? Weierstrass 方程?实域上的椭圆曲线?有限域上的椭圆曲线?椭圆曲线密码?椭圆曲线在分解中的应用 1 Weierstrass 方程是无穷远点。其中, : 有理点的集合是上的的扩域,则是若。下: 的判别式,具体定义如是, 且, , , , 其中, 由下述方程定义: 上的椭圆曲线域???????????????????????????????}{0} ), {(=)( 44 24 927 8 0 : 6422 331 2 24 232431626 2186 236 31442 212 642 36 348 22 64321 64 22 331 2axaxaxy xy+a +a yLL yxLE LEKL aaaaaaaaaadaad aaadaad ddddddd EKaaaaa x+a +a x +a y=x xy+a +a yE E K 定义1 有理点。上的的所有扩域,并认为无穷远点是点的属于和且坐标有理点是满足曲线方程的曲线远点。是曲线唯一的一个无穷点以上不同的切线。有点都没有两个或两个”的,即曲线的所确保椭圆曲线是“光滑条件的基础域。为的元素。均为域, , , , 为系数上的椭圆曲线,这是因是域我们称方程。中的方程称为 LLK yx Lyx LE E K Kaaa aa KE),( (5) (4) 0 (3) (2) s Weierstras (1) 643 21 ???定义1 评述. 2 实域上的椭圆曲线 简化 Weierstrass 方程)27 4(16 : 24 12 4216 336 12 3),( : 23 32 321 3112 21 64 22 331 2ba +ax+b =x yE aaaaxayaaxyx x+a +a x +a y=x xy+a +a yE???????????????????这里, 实域上的椭圆曲线 73 : (b) :)a( 322 321????xyExxyE; 加法法则