第十六讲 椭圆曲线.

Presentation on theme: "第十六讲 椭圆曲线."— Presentation transcript:

1 第十六讲 椭圆曲线

2 1984年，Hendrik Lenstra提出了依靠椭圆曲线性质分解整数的精妙算法。这一发现激发了学者进一步研究椭圆曲线在密码和计算数论的其它应用。

3 椭圆曲线密码在1985年分别由Neal Koblitz 和Victor Miller提出。椭圆曲线密码方案为公钥机制，提供如同RSA一样的功能。但是，它的安全性依赖不同的困难问题，也就是椭圆曲线离散对数问题(ECDLP)。

4 我们知道解决分解整数问题需要亚指数时间复杂度的算法，而目前已知计算ECDLP的最好方法都需要全指数时间复杂度。这意味着在椭圆曲线系统中我们只需要使用相对于RSA 短得多的密钥就可以达到与其相同的安全强度。例如，一般认为160比特的椭圆曲线密钥提供的安全强度与1024比特RSA密钥相当。使用短的密钥的好处在于加解密速度快、节省能源、节省带宽、存储空间。

5 本讲提要 Weierstrass方程 实域上的椭圆曲线 有限域上的椭圆曲线 椭圆曲线密码 椭圆曲线在分解中的应用

6 1 Weierstrass方程

7

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

9 2.2 实域上的椭圆曲线

10 2.3 加法法则

11 2.3 加法法则(续) 弦和切线法则

12 2.3 加法法则(续) 弦和切线法则(续)

13 2.3 加法法则(续)

14 2.3 加法法则(续)

15 2.3 加法法则(续) 代数公式

16 2.3 加法法则(续)

17 3 有限域上的椭圆曲线 3.1 模素数p的椭圆曲线，p≠2，3情形 3.1.1 加法法则

18 3.1.2 例子

19 3.1.2 例子(续)

20 3.2 有限域GF(2n)上的椭圆曲线

21 3.2.1简化Weierstrass方程

22 3.2.2 加法法则

23 3.2.2 加法法则(续)

24 3.2.2 加法法则(续)

25 3.2.2 加法法则(续)

26 3.2.3 例子

27 3.3 点的数量

28 3.3 点的数量(续)

29 3.4 椭圆曲线上的离散对数

30 3.4 椭圆曲线上的离散对数(续)

31 4 椭圆曲线密码 4.1 明文表示

32 4.1 明文表示(续)

33 4.2 椭圆曲线ElGamal密码系统

34 4.2 椭圆曲线ElGamal密码系统(续)

35 4.2 椭圆曲线ElGamal密码系统(续)

36 4.2 椭圆曲线ElGamal密码系统(续)

37 4.3 椭圆曲线数字签名算法(ECDSA)

38 4.3 椭圆曲线数字签名算法(ECDSA)(续)

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

40 5.1 椭圆曲线分解算法(续)

41 5.1 椭圆曲线分解算法(续)

42 5.1 椭圆曲线分解算法(续)

43 5.1 椭圆曲线分解算法(续)

44 5.1 椭圆曲线分解算法(续)

45 5.2 退化曲线

46 5.2 退化曲线(续)

47 5.2 退化曲线(续)

48 谢谢!