第十二讲 密码执行(上).

Presentation on theme: "第十二讲 密码执行(上)."— Presentation transcript:

1 第十二讲 密码执行(上)

2 在某个特定代数结构上的密码方案的执行效率主要由以下几个因素决定：参数尺寸，时间与存储平衡，可以获得的处理能力，以及使用的数学算法。这一讲和下一讲主要讨论潜在用于密码方案中代数结构上关键计算的有效算法。

3 这里介绍的算法因为是实现密码系统的关键技术，所以在各种文献中有广泛研讨。虽然有些文献也试图指出各种算法的优势所在，但是通常并没有给出系统的比较。

4 本讲提要 素数问题 模幂

5 1 素数问题

6 1.1 Miller-Rabin 测试

7 1.1 Miller-Rabin测试(续)

8 1.1 Miller-Rabin测试(续)

9 1.1 Miller-Rabin测试(续)

10 1.1 Miller-Rabin测试(续)

11 1.1 Miller-Rabin测试(续)

12 1.1 Miller-Rabin测试(续)

13 1.1 Miller-Rabin测试(续)

14 1.2 素数产生 素数产生不同于前面的素性测试，但是通常与后者密切相关。前者允许被测试整数有固定的一些方式构造，这将有可能比随机选择测试整数更有效率。

15 1.2.1 随机搜索可能的素数

16 1.2.1 随机搜索可能的素数(续)

17 1.2.1 随机搜索可能的素数(续)

18 1.2.1 随机搜索可能的素数(续)

19 1.2.1 随机搜索可能的素数(续)

20 1.2.2 强素数

21 1.2.2 强素数(续)

22 1.2.2 强素数(续)

23 1.2.3 产生DSA素数

24 1.2.3 产生DSA素数(续)

25 1.2.3 产生DSA素数(续)

26 1.2.3 产生DSA素数(续)

27 1.2.3 产生DSA素数(续)

28 2 模幂

29

30 2.1 问题模型 2.1.1 加法链

31 2.1.2加-减法链

32 2.1.3 加法序列和向量加法链

33 2.1.3 加法序列和向量加法链(续)

34 2.1.3 加法序列和向量加法链(续)

35 2.2 一般模幂技术 2.2.1 二进制方法

36 2.2.1 二进制方法(续)

37 2.2.1 二进制方法(续)

38 2.2.1 二进制方法(续)

39 2.2.1 二进制方法(续)

40 2.2.1 二进制方法(续)

41 2.2.1 二进制方法(续)

42 谢谢!