第十一讲-椭圆曲线课件

1984年，HendrikLenstra提出了依靠椭圆曲线性质分解整数的精妙算法。这一发现激发了学者进一步研究椭圆曲线在密码和计算数论的其它应用。1984年，HendrikLenstra提出了依靠椭1椭圆曲线密码在1985年分别由NealKoblitz和VictorMiller提出。椭圆曲线密码方案为公钥机制，提供如同RSA一样的功能。但是，它的安全性依赖不同的困难问题，也就是椭圆曲线离散对数问题(ECDLP)。椭圆曲线密码在1985年分别由NealKoblitz2我们知道解决分解整数问题需要亚指数时间复杂度的算法，而目前已知计算ECDLP的最好方法都需要全指数时间复杂度。这意味着在椭圆曲线系统中我们只需要使用相对于RSA短得多的密钥就可以达到与其相同的安全强度。例如，一般认为160比特的椭圆曲线密钥提供的安全强度与1024比特RSA密钥相当。使用短的密钥的好处在于加解密速度快、节省能源、节省带宽、存储空间。我们知道解决分解整数问题需要亚指数时间复杂度的算法，而3本讲提要Weierstrass方程实域上的椭圆曲线有限域上的椭圆曲线椭圆曲线密码椭圆曲线在分解中的应用本讲提要Weierstrass方程41Weierstrass方程1Weierstrass方程5第十一讲-椭圆曲线课件62实域上的椭圆曲线

2.1简化Weierstrass方程2实域上的椭圆曲线

2.1简化Weierstrass方程72.2实域上的椭圆曲线2.2实域上的椭圆曲线82.3加法法则2.3加法法则9弦和切线法则2.3加法法则(续)弦和切线法则2.3加法法则(续)10弦和切线法则(续)2.3加法法则(续)弦和切线法则(续)2.3加法法则(续)112.3加法法则(续)2.3加法法则(续)122.3加法法则(续)2.3加法法则(续)13代数公式2.3加法法则(续)代数公式2.3加法法则(续)142.3加法法则(续)2.3加法法则(续)153有限域上的椭圆曲线3.1模素数p的椭圆曲线，p≠2，3情形3.1.1加法法则3有限域上的椭圆曲线3.1模素数p的椭圆曲线，p≠2，3163.1.2

例子3.1.2例子173.1.2

例子(续)3.1.2例子(续)183.2有限域GF(2n)上的椭圆曲线3.2有限域GF(2n)上的椭圆曲线193.2.1简化Weierstrass方程3.2.1简化Weierstrass方程203.2.2加法法则3.2.2加法法则213.2.2加法法则(续)3.2.2加法法则(续)223.2.2加法法则(续)3.2.2加法法则(续)233.2.2加法法则(续)3.2.2加法法则(续)243.2.3例子3.2.3例子253.3点的数量3.3点的数量263.3点的数量(续)3.3点的数量(续)273.4椭圆曲线上的离散对数3.4椭圆曲线上的离散对数283.4椭圆曲线上的离散对数(续)3.4椭圆曲线上的离散对数(续)294椭圆曲线密码4.1明文表示4椭圆曲线密码4.1明文表示304.1明文表示(续)4.1明文表示(续)314.2椭圆曲线ElGamal密码系统4.2椭圆曲线ElGamal密码系统324.2椭圆曲线ElGamal密码系统(续)4.2椭圆曲线ElGamal密码系统(续)334.2椭圆曲线ElGamal密码系统(续)4.2椭圆曲线ElGamal密码系统(续)344.2椭圆曲线ElGamal密码系统(续)4.2椭圆曲线ElGamal密码系统(续)354.3椭圆曲线数字签名算法(ECDSA)4.3椭圆曲线数字签名算法(ECDSA)364.3椭圆曲线数字签名算法(ECDSA)(续)4.3椭圆曲线数字签名算法(ECDSA)(续)375椭圆曲线在分解中的应用

5.1椭圆曲线分解算法5椭圆曲线在分解中的应用

5.1椭圆曲线分解算法385.1椭圆曲线分解算法(续)5.1椭圆曲线分解算法(续)395.1椭圆曲线分解算法(续)5.1椭圆曲线分解算法(续)405.1椭圆曲线分解算法(续)5.1椭圆曲线分解算法(续)415.1椭圆曲线分解算法(续)5.1椭圆曲线分解算法(续)425.1椭圆曲线分解算法(续)5.1椭圆曲线分解算法(续)435.2退化曲线5.2退化曲线445.2退化曲线(续)5.2退化曲线(续)455.2退化曲线(续)5.2退化曲线(续)461984年，HendrikLenstra提出了依靠椭圆曲线性质分解整数的精妙算法。这一发现激发了学者进一步研究椭圆曲线在密码和计算数论的其它应用。1984年，HendrikLenstra提出了依靠椭47椭圆曲线密码在1985年分别由NealKoblitz和VictorMiller提出。椭圆曲线密码方案为公钥机制，提供如同RSA一样的功能。但是，它的安全性依赖不同的困难问题，也就是椭圆曲线离散对数问题(ECDLP)。椭圆曲线密码在1985年分别由NealKoblitz48我们知道解决分解整数问题需要亚指数时间复杂度的算法，而目前已知计算ECDLP的最好方法都需要全指数时间复杂度。这意味着在椭圆曲线系统中我们只需要使用相对于RSA短得多的密钥就可以达到与其相同的安全强度。例如，一般认为160比特的椭圆曲线密钥提供的安全强度与1024比特RSA密钥相当。使用短的密钥的好处在于加解密速度快、节省能源、节省带宽、存储空间。我们知道解决分解整数问题需要亚指数时间复杂度的算法，而49本讲提要Weierstrass方程实域上的椭圆曲线有限域上的椭圆曲线椭圆曲线密码椭圆曲线在分解中的应用本讲提要Weierstrass方程501Weierstrass方程1Weierstrass方程51第十一讲-椭圆曲线课件522实域上的椭圆曲线

2.1简化Weierstrass方程2实域上的椭圆曲线

2.1简化Weierstrass方程532.2实域上的椭圆曲线2.2实域上的椭圆曲线542.3加法法则2.3加法法则55弦和切线法则2.3加法法则(续)弦和切线法则2.3加法法则(续)56弦和切线法则(续)2.3加法法则(续)弦和切线法则(续)2.3加法法则(续)572.3加法法则(续)2.3加法法则(续)582.3加法法则(续)2.3加法法则(续)59代数公式2.3加法法则(续)代数公式2.3加法法则(续)602.3加法法则(续)2.3加法法则(续)613有限域上的椭圆曲线3.1模素数p的椭圆曲线，p≠2，3情形3.1.1加法法则3有限域上的椭圆曲线3.1模素数p的椭圆曲线，p≠2，3623.1.2

例子3.1.2例子633.1.2

例子(续)3.1.2例子(续)643.2有限域GF(2n)上的椭圆曲线3.2有限域GF(2n)上的椭圆曲线653.2.1简化Weierstrass方程3.2.1简化Weierstrass方程663.2.2加法法则3.2.2加法法则673.2.2加法法则(续)3.2.2加法法则(续)683.2.2加法法则(续)3.2.2加法法则(续)693.2.2加法法则(续)3.2.2加法法则(续)703.2.3例子3.2.3例子713.3点的数量3.3点的数量723.3点的数量(续)3.3点的数量(续)733.4椭圆曲线上的离散对数3.4椭圆曲线上的离散对数743.4椭圆曲线上的离散对数(续)3.4椭圆曲线上的离散对数(续)754椭圆曲线密码4.1明文表示4椭圆曲线密码4.1明文表示764.1明文表示(续)4.1明文表示(续)774.2椭圆曲线ElGamal密码系统4.2椭圆曲线ElGamal密码系统784.2椭圆曲线ElGamal密码系统(续)4.2椭圆曲线ElGamal密码系统(续)794.2椭圆曲线ElGamal密码系统(续)4.2椭圆曲线ElGamal密码系统(续)804.2椭圆曲线ElGamal密码系统(续)4.2椭圆曲线ElGamal密码系统(续)814.3椭圆曲线数字签名算法(ECDSA)4.3椭圆曲线数字签名算法(ECDSA)824.3椭圆曲线数字签名算法(ECDSA)(续)4.3椭圆曲线数字签名算法(ECDSA)(续)835椭圆曲线在分解中的应用

5.1椭圆曲线分解算法5椭圆曲线在分解中的应用

5.1椭圆曲线分解算法845.1椭圆曲线分解算法(续)5.1椭圆曲线分解算法(续)855.1椭圆曲线分解算法(续)5.