第十一讲 椭圆曲线

第十一讲椭圆曲线第1页，共47页，2023年，2月20日，星期三1984年，HendrikLenstra提出了依靠椭圆曲线性质分解整数的精妙算法。这一发现激发了学者进一步研究椭圆曲线在密码和计算数论的其它应用。第2页，共47页，2023年，2月20日，星期三

椭圆曲线密码在1985年分别由NealKoblitz和VictorMiller提出。椭圆曲线密码方案为公钥机制，提供如同RSA一样的功能。但是，它的安全性依赖不同的困难问题，也就是椭圆曲线离散对数问题(ECDLP)。第3页，共47页，2023年，2月20日，星期三

我们知道解决分解整数问题需要亚指数时间复杂度的算法，而目前已知计算ECDLP的最好方法都需要全指数时间复杂度。这意味着在椭圆曲线系统中我们只需要使用相对于RSA短得多的密钥就可以达到与其相同的安全强度。例如，一般认为160比特的椭圆曲线密钥提供的安全强度与1024比特RSA密钥相当。使用短的密钥的好处在于加解密速度快、节省能源、节省带宽、存储空间。第4页，共47页，2023年，2月20日，星期三本讲提要Weierstrass方程实域上的椭圆曲线有限域上的椭圆曲线椭圆曲线密码椭圆曲线在分解中的应用第5页，共47页，2023年，2月20日，星期三1Weierstrass方程第6页，共47页，2023年，2月20日，星期三第7页，共47页，2023年，2月20日，星期三2实域上的椭圆曲线

2.1简化Weierstrass方程第8页，共47页，2023年，2月20日，星期三2.2实域上的椭圆曲线第9页，共47页，2023年，2月20日，星期三2.3加法法则第10页，共47页，2023年，2月20日，星期三弦和切线法则2.3加法法则(续)第11页，共47页，2023年，2月20日，星期三弦和切线法则(续)2.3加法法则(续)第12页，共47页，2023年，2月20日，星期三2.3加法法则(续)第13页，共47页，2023年，2月20日，星期三2.3加法法则(续)第14页，共47页，2023年，2月20日，星期三代数公式2.3加法法则(续)第15页，共47页，2023年，2月20日，星期三2.3加法法则(续)第16页，共47页，2023年，2月20日，星期三3有限域上的椭圆曲线3.1模素数p的椭圆曲线，p≠2，3情形3.1.1加法法则第17页，共47页，2023年，2月20日，星期三3.1.2

例子第18页，共47页，2023年，2月20日，星期三3.1.2

例子(续)第19页，共47页，2023年，2月20日，星期三3.2有限域GF(2n)上的椭圆曲线第20页，共47页，2023年，2月20日，星期三3.2.1简化Weierstrass方程第21页，共47页，2023年，2月20日，星期三3.2.2加法法则第22页，共47页，2023年，2月20日，星期三3.2.2加法法则(续)第23页，共47页，2023年，2月20日，星期三3.2.2加法法则(续)第24页，共47页，2023年，2月20日，星期三3.2.2加法法则(续)第25页，共47页，2023年，2月20日，星期三3.2.3例子第26页，共47页，2023年，2月20日，星期三3.3点的数量第27页，共47页，2023年，2月20日，星期三3.3点的数量(续)第28页，共47页，2023年，2月20日，星期三3.4椭圆曲线上的离散对数第29页，共47页，2023年，2月20日，星期三3.4椭圆曲线上的离散对数(续)第30页，共47页，2023年，2月20日，星期三4椭圆曲线密码4.1明文表示第31页，共47页，2023年，2月20日，星期三4.1明文表示(续)第32页，共47页，2023年，2月20日，星期三4.2椭圆曲线ElGamal密码系统第33页，共47页，2023年，2月20日，星期三4.2椭圆曲线ElGamal密码系统(续)第34页，共47页，2023年，2月20日，星期三4.2椭圆曲线ElGamal密码系统(续)第35页，共47页，2023年，2月20日，星期三4.2椭圆曲线ElGamal密码系统(续)第36页，共47页，2023年，2月20日，星期三4.3椭圆曲线数字签名算法(ECDSA)第37页，共47页，2023年，2月20日，星期三4.3椭圆曲线数字签名算法(ECDSA)(续)第38页，共47页，2023年，2月20日，星期三5椭圆曲线在分解中的应用

5.1椭圆曲线分解算法第39页，共47页，2023年，2月20日，星期三5.1椭圆曲线分解算法(续)第40页，共47页，2023年，2月20日，星期三5.1椭圆曲线分解算法(续)第41页，共47页，2023年，2月20日，星期三5.1椭圆曲线分解算法(续)第42页，共47页，2023年，2月20日，星期三5.1椭圆曲线分解算法(续)第43页，共47页，2023年，2月20日，星期三5.1椭圆曲线分解算法(续)第44页，共47页，2023年，2月20