第2章_信息安全数学基础(复杂性)[教育研究]

1、电子科技大学电子科技大学 计算机科学与工程学院计算机科学与工程学院 计算系统与网络安全计算系统与网络安全 Computer System and Network SecurityComputer System and Network Security 1章节课堂 古书古书孟子孟子离娄上离娄上有这样的记载：有这样的记载： 淳于髡曰：男女授受不亲，礼與？淳于髡曰：男女授受不亲，礼與？ 孟子曰：礼也。孟子曰：礼也。 曰：嫂溺则授之以手乎？曰：嫂溺则授之以手乎？ 曰：嫂溺不授，是豺狼也。男女授受不亲，礼曰：嫂溺不授，是豺狼也。男女授受不亲，礼 也；嫂溺授之以手，权也。也；嫂溺授之以手，权也。 虽然有虽

2、然有“男女授受不亲男女授受不亲”的原则存在，但嫂子落的原则存在，但嫂子落 水快淹死时，必须拉她、救她，这是水快淹死时，必须拉她、救她，这是“权权”(变通变通)， 否则，见死不救，就是豺狼。否则，见死不救，就是豺狼。 曰：今天下溺矣，夫子之不援何也？曰：今天下溺矣，夫子之不援何也？ 曰：天下溺援之以道；嫂溺援之以手。子欲手曰：天下溺援之以道；嫂溺援之以手。子欲手 援天下乎？援天下乎？ 计算复杂性基础计算复杂性基础 2章节课堂 l为什么要学习计算复杂性？为什么要学习计算复杂性？ l计算复杂性是研究密码分析对于计算量的需求和密码分计算复杂性是研究密码分析对于计算量的需求和密码分 析的困难程度析的困难

3、程度 ，从而得出这些密码技术和算法在现有，从而得出这些密码技术和算法在现有 可行的条件下是否具有足够的安全性。可行的条件下是否具有足够的安全性。 l学习计算复杂性，需要掌握两个概念：学习计算复杂性，需要掌握两个概念： l问题问题 l算法算法 计算复杂性计算复杂性 3章节课堂 第第2 2章章 信息安全数学基础（计算复杂性）信息安全数学基础（计算复杂性） 4章节课堂 第第2 2章章 信息安全数学基础（计算复杂性）信息安全数学基础（计算复杂性） 5章节课堂 问题（问题（problem） l（问题）定义：即需要回答的一般性提问（问题）定义：即需要回答的一般性提问: l它通常含有若干个参数。它通常含有若

4、干个参数。 l对于一个问题进行描述应该包括两方面的内容：对于一个问题进行描述应该包括两方面的内容： l必须对问题的所有给定参数给出一般性描述；必须对问题的所有给定参数给出一般性描述； l必须描述该问题的答案（或解）应该满足的性质。必须描述该问题的答案（或解）应该满足的性质。 l当问题的所有参数都有了确定的取值时，我们称得到了当问题的所有参数都有了确定的取值时，我们称得到了 该问题的一个实例（该问题的一个实例（instance）。）。 6章节课堂 算法（算法（algorithm） l定义（算法）定义（算法） ：即求解某个问题的一系列具体步：即求解某个问题的一系列具体步 骤（通常被理解为求解所需的

5、通用计算程序）。骤（通常被理解为求解所需的通用计算程序）。 l算法总是针对具体问题而言的，求解一个问题的算法通算法总是针对具体问题而言的，求解一个问题的算法通 常不止一个。常不止一个。 l当某个算法能够回答一个问题的任何实例时，我们称该当某个算法能够回答一个问题的任何实例时，我们称该 算法能够回答这个问题。算法能够回答这个问题。 l当一个问题至少有一个能够回答该问题的算法时，我们当一个问题至少有一个能够回答该问题的算法时，我们 称该问题可解（称该问题可解（resolvable），否则称该问题不可解），否则称该问题不可解 （unresolvable）。）。 7章节课堂 算法（算法（algorit

6、hm）（续）（续） l有关算法的几点注释有关算法的几点注释： l算法总有输入和输出算法总有输入和输出 l算法输入大小一般用输入变量的长度（单位为位）算法输入大小一般用输入变量的长度（单位为位） 来表示来表示 l一般来说，算法用某种编程语言来实现的计算机程序一般来说，算法用某种编程语言来实现的计算机程序 l一般来说，我们仅仅关注解决问题最有效的算法一般来说，我们仅仅关注解决问题最有效的算法 nlogn 2 当一个变量 用二进制来表示时，其长度 8章节课堂 问题与算法问题与算法 l问题：如何求解两个整数问题：如何求解两个整数a和和b的最大公约数？的最大公约数？ l参数：a和b l问题实例：a20，

7、b30 l算法：利用因子分解求算法：利用因子分解求a20和和b30的最大公约的最大公约 数数 la225 lb235 l因此a和b 的最大公约数是2510 9章节课堂 算法复杂性算法复杂性 l（算法复杂度）定义：即度量该算法所需的计算（算法复杂度）定义：即度量该算法所需的计算 能力能力 ，包括：，包括： l时间复杂性时间复杂性T（time complexity）；）； l空间复杂性空间复杂性S（space complexity）；）； l信道带宽；信道带宽； l数据总量；数据总量； l 10章节课堂 算法复杂性（续）算法复杂性（续） l计算复杂性的表示符号为计算复杂性的表示符号为“ O ”（称

8、为（称为“大大O ”，即算法，即算法 的阶号），表示计算复杂性的的阶号），表示计算复杂性的数量级数量级 好处：好处： l使算法复杂性度量与处理器的运行速度和指令运行时间无关；使算法复杂性度量与处理器的运行速度和指令运行时间无关； l明确地揭示了输入的数据长度对算法复杂性的影响。明确地揭示了输入的数据长度对算法复杂性的影响。 11章节课堂 算法复杂性（续）算法复杂性（续） l算法常见复杂性分类算法常见复杂性分类 l（1）常数算法（）常数算法（constant Algorithm）：）： l如果运行时间是如果运行时间是O (1)，即该算法的复杂性不依赖于，即该算法的复杂性不依赖于n。 l（2）线性

9、算法（）线性算法（linear Algorithm）：）： l如果运行时间是如果运行时间是O(n)。 l（3）多项式算法多项式算法（polynomial Algorithm）：）： l如果运行时间是如果运行时间是O(nm)，其中，其中m是一个常数。具有多项式复杂性的算法是一个常数。具有多项式复杂性的算法 族被称为多项式时间算法。族被称为多项式时间算法。 l（4）超多项式算法（）超多项式算法（superpolynomial Algorithm）：）： l如果运行时间是，其中如果运行时间是，其中c是一个常数，而是一个常数，而s(n)是关于是关于n的大于常数而小于的大于常数而小于 线性的函数。线性的

10、函数。 l（5）指数算法指数算法（exponential Algorithm）：）： l如果运行时间是如果运行时间是 ，其中，其中t是大于是大于1的常数，的常数，f(n)是关于是关于n的多项式的多项式 函数。函数。 ( ) () f n O t 12章节课堂 算法复杂性（续）算法复杂性（续） l算法常见复杂性分类算法常见复杂性分类 l一般而言，常数算法、线性算法、多项式算法和超多一般而言，常数算法、线性算法、多项式算法和超多 项式算法统称为项式算法统称为多项式算法多项式算法。 l所谓多项式，就是具有下列形式的一个函数：所谓多项式，就是具有下列形式的一个函数： 1 110 ( ). kk kk

11、f nc ncnc nc 其中，其中，k和和ck是常数，且是常数，且ci0。当。当k0时，时，k称为多项式的次数，称为多项式的次数， ci称为多项式的系数。称为多项式的系数。 13章节课堂 算 法 复 杂 性 l算法的分类及其运行时间算法的分类及其运行时间 算法类型算法类型复杂性复杂性运算次数运算次数 n106 时间时间 多项式算法多项式算法 常数算法常数算法O(1)11微秒微秒 线性算法线性算法O(n)1061秒秒 二次多项式算二次多项式算 法法 O(n2)101211.6天天 三次多项式算三次多项式算 法法 O(n3)101832,000年年 指数算法指数算法O(2n)1030103010

12、301006年年 算法复杂性（续）算法复杂性（续） 14章节课堂 算算 法法 复复 杂杂 性性 l算法复杂度的增长速度算法复杂度的增长速度 算法复杂性（续）算法复杂性（续） ln lnlnln ,01 1lnlnlnexp n nncnnnc cc nnnnncnc 对任意常数 ， 其中，有： 亚指数亚指数 指数指数 多项式多项式 15章节课堂 算法复杂性（续）算法复杂性（续） l研究问题的内在复杂性，即在研究问题的内在复杂性，即在图灵机图灵机上解决最难上解决最难 的问题实例所需的最小时间和空间条件。的问题实例所需的最小时间和空间条件。 l图灵机是一种具有无限读、写存储带的有限状态图灵机是一种

13、具有无限读、写存储带的有限状态 机，可以被当作一个实际可用的计算模型机，可以被当作一个实际可用的计算模型 。 16章节课堂 第第2 2章章 信息安全数学基础（计算复杂性）信息安全数学基础（计算复杂性） 17章节课堂 问题复杂性问题复杂性 l图灵机分为两类：图灵机分为两类： l确定性图灵机。确定性图灵机。 l非确定性图灵机非确定性图灵机 18章节课堂 问题复杂性（续）问题复杂性（续） l确定性图灵机确定性图灵机。 l确定性图灵机的输出结果只取决于输入和初始状态。确定性图灵机的输出结果只取决于输入和初始状态。 因此，对于具有相同输入和初始状态，运行一个确因此，对于具有相同输入和初始状态，运行一个确

14、 定性图灵机所得到的结果是完全相同的。定性图灵机所得到的结果是完全相同的。 l非确定性图灵机非确定性图灵机 ： l能够进行猜测。能够进行猜测。 l求解一个问题分两个阶段：猜测阶段和验证阶段。求解一个问题分两个阶段：猜测阶段和验证阶段。 19章节课堂 图灵机图灵机 l图灵机包括一个有限状态控制单元、图灵机包括一个有限状态控制单元、k（1）条纸）条纸 带（带（Tape）和）和k个读写头（个读写头（Tapehead）。）。 l有限状态控制单元控制每个读写头访问一条纸带，并沿有限状态控制单元控制每个读写头访问一条纸带，并沿 着纸带左右移动着纸带左右移动 l图灵机求解问题的输入是一个有限长度的字符串，该

15、输图灵机求解问题的输入是一个有限长度的字符串，该输 入占据每条纸带无限个单元的最左边的有限个单元。入占据每条纸带无限个单元的最左边的有限个单元。 l读写头对纸带的一次访问称之为一个合法移动读写头对纸带的一次访问称之为一个合法移动 （Move）。）。 20章节课堂 图灵机（续）图灵机（续） l图灵机求解问题时，被赋予一个初始状态图灵机求解问题时，被赋予一个初始状态 （Initial State），且一步一步地移动，从而完成），且一步一步地移动，从而完成 对输入的扫描。对输入的扫描。 l如果图灵机最终扫描了整个输入串，且满足了中止条件如果图灵机最终扫描了整个输入串，且满足了中止条件 而停止下来，则

16、称图灵机识别了该输入。而停止下来，则称图灵机识别了该输入。 l否则，图灵机在某一点没有合法移动，因此会没有识别否则，图灵机在某一点没有合法移动，因此会没有识别 输入串而停止下来，此时称图灵机无法识别该输入。输入串而停止下来，此时称图灵机无法识别该输入。 l图灵机所识别的一个输入，称为一种可识别语言的一个图灵机所识别的一个输入，称为一种可识别语言的一个 实例。实例。 21章节课堂 图灵机（续）图灵机（续） l例如：请设计一个图灵机，用于证明某个非负整例如：请设计一个图灵机，用于证明某个非负整 数是否能被数是否能被3整除。整除。 22章节课堂 图灵机（续）图灵机（续） l例如：请设计一个图灵机，用

17、于证明某个非负整例如：请设计一个图灵机，用于证明某个非负整 数是否能被数是否能被3整除。整除。 23章节课堂 图灵机（续）图灵机（续） l例如：请设计一个图灵机，用于证明某个非负整例如：请设计一个图灵机，用于证明某个非负整 数是否能被数是否能被3整除。整除。 24章节课堂 图灵机（续）图灵机（续） l例如：请设计一个图灵机，用于证明某个非负整例如：请设计一个图灵机，用于证明某个非负整 数是否能被数是否能被3整除。整除。 25章节课堂 图灵机（续）图灵机（续） l例如：请设计一个图灵机，用于证明某个非负整例如：请设计一个图灵机，用于证明某个非负整 数是否能被数是否能被3整除。整除。 26章节课堂

18、 图灵机（续）图灵机（续） l例如：请设计一个图灵机，用于证明某个非负整例如：请设计一个图灵机，用于证明某个非负整 数是否能被数是否能被3整除。整除。 27章节课堂 图灵机（续）图灵机（续） l例如：请设计一个图灵机，用于证明某个非负整例如：请设计一个图灵机，用于证明某个非负整 数是否能被数是否能被3整除。整除。 28章节课堂 图灵机（续）图灵机（续） l例如：请设计一个图灵机，用于证明某个非负整例如：请设计一个图灵机，用于证明某个非负整 数是否能被数是否能被3整除。整除。 29章节课堂 图灵机（续）图灵机（续） l例如：请设计一个图灵机，用于证明某个非负整例如：请设计一个图灵机，用于证明某个

19、非负整 数是否能被数是否能被3整除。整除。 30章节课堂 图灵机（续）图灵机（续） l例如：请用例如：请用DIV3图灵机证明图灵机证明a12(二进制二进制1100) 能被能被3整除。整除。 31章节课堂 图灵机（续）图灵机（续） l例如：请用例如：请用DIV3图灵机证明图灵机证明a12(二进制二进制1011) 能被能被3整除。整除。 当前状态当前状态纸带上的符号纸带上的符号下一步移动下一步移动下一个状态下一个状态 q0（初态）（初态） 0 1 空空 右右 右右 响铃或终止响铃或终止 q0 q1 q1 0 1 空空 右右 右右 输出非整除信息输出非整除信息 q2 q0 q2 0 1 空空 右右

20、右右 输出非整除信息输出非整除信息 q1 q2 32章节课堂 图灵机（续）图灵机（续） l例如：请用例如：请用DIV3图灵机证明图灵机证明a12(二进制二进制1011) 能被能被3整除。整除。 当前状态当前状态纸带上的符号纸带上的符号下一步移动下一步移动下一个状态下一个状态 q0（初态）（初态） 0 1 空空 右右 右右 响铃或终止响铃或终止 q0 q1 q1 0 1 空空 右右 右右 输出非整除信息输出非整除信息 q2 q0 q2 0 1 空空 右右 右右 输出非整除信息输出非整除信息 q1 q2 33章节课堂 图灵机（续）图灵机（续） l例如：请用例如：请用DIV3图灵机证明图灵机证明a1

21、2(二进制二进制1011) 能被能被3整除。整除。 当前状态当前状态纸带上的符号纸带上的符号下一步移动下一步移动下一个状态下一个状态 q0（初态）（初态） 0 1 空空 右右 右右 响铃或终止响铃或终止 q0 q1 q1 0 1 空空 右右 右右 输出非整除信息输出非整除信息 q2 q0 q2 0 1 空空 右右 右右 输出非整除信息输出非整除信息 q1 q2 34章节课堂 图灵机（续）图灵机（续） l例如：请用例如：请用DIV3图灵机证明图灵机证明a12(二进制二进制1011) 能被能被3整除。整除。 当前状态当前状态纸带上的符号纸带上的符号下一步移动下一步移动下一个状态下一个状态 q0（初

22、态）（初态） 0 1 空空 右右 右右 响铃或终止响铃或终止 q0 q1 q1 0 1 空空 右右 右右 输出非整除信息输出非整除信息 q2 q0 q2 0 1 空空 右右 右右 输出非整除信息输出非整除信息 q1 q2 35章节课堂 图灵机（续）图灵机（续） l例如：请用例如：请用DIV3图灵机证明图灵机证明a12(二进制二进制1011) 能被能被3整除。整除。 当前状态当前状态纸带上的符号纸带上的符号下一步移动下一步移动下一个状态下一个状态 q0（初态）（初态） 0 1 空空 右右 右右 响铃或终止响铃或终止 q0 q1 q1 0 1 空空 右右 右右 输出非整除信息输出非整除信息 q2

23、q0 q2 0 1 空空 右右 右右 输出非整除信息输出非整除信息 q1 q2 36章节课堂 图灵机（续）图灵机（续） l例如：请用例如：请用DIV3图灵机证明图灵机证明a12(二进制二进制1011) 能被能被3整除。整除。 当前状态当前状态纸带上的符号纸带上的符号下一步移动下一步移动下一个状态下一个状态 q0（初态）（初态） 0 1 空空 右右 右右 响铃或终止响铃或终止 q0 q1 q1 0 1 空空 右右 右右 输出非整除信息输出非整除信息 q2 q0 q2 0 1 空空 右右 右右 输出非整除信息输出非整除信息 q1 q2 37章节课堂 图灵机（续）图灵机（续） l例如：请用例如：请用

24、DIV3图灵机证明图灵机证明a13(二进制二进制1101) 不能被不能被3整除。整除。 38章节课堂 图灵机（续）图灵机（续） l例如：请用例如：请用DIV3图灵机证明图灵机证明a13(二进制二进制1101) 被被3整除。整除。 当前状态当前状态纸带上的符号纸带上的符号下一步移动下一步移动下一个状态下一个状态 q0（初态）（初态） 0 1 空空 右右 右右 响铃或终止响铃或终止 q0 q1 q1 0 1 空空 右右 右右 输出非整除信息输出非整除信息 q2 q0 q2 0 1 空空 右右 右右 输出非整除信息输出非整除信息 q1 q2 39章节课堂 图灵机（续）图灵机（续） l例如：请用例如：

25、请用DIV3图灵机证明图灵机证明a13(二进制二进制1101) 被被3整除。整除。 当前状态当前状态纸带上的符号纸带上的符号下一步移动下一步移动下一个状态下一个状态 q0（初态）（初态） 0 1 空空 右右 右右 响铃或终止响铃或终止 q0 q1 q1 0 1 空空 右右 右右 输出非整除信息输出非整除信息 q2 q0 q2 0 1 空空 右右 右右 输出非整除信息输出非整除信息 q1 q2 40章节课堂 图灵机（续）图灵机（续） l例如：请用例如：请用DIV3图灵机证明图灵机证明a13(二进制二进制1101) 被被3整除。整除。 当前状态当前状态纸带上的符号纸带上的符号下一步移动下一步移动下

26、一个状态下一个状态 q0（初态）（初态） 0 1 空空 右右 右右 响铃或终止响铃或终止 q0 q1 q1 0 1 空空 右右 右右 输出非整除信息输出非整除信息 q2 q0 q2 0 1 空空 右右 右右 输出非整除信息输出非整除信息 q1 q2 41章节课堂 图灵机（续）图灵机（续） l例如：请用例如：请用DIV3图灵机证明图灵机证明a13(二进制二进制1101) 被被3整除。整除。 当前状态当前状态纸带上的符号纸带上的符号下一步移动下一步移动下一个状态下一个状态 q0（初态）（初态） 0 1 空空 右右 右右 响铃或终止响铃或终止 q0 q1 q1 0 1 空空 右右 右右 输出非整除信

27、息输出非整除信息 q2 q0 q2 0 1 空空 右右 右右 输出非整除信息输出非整除信息 q1 q2 42章节课堂 图灵机（续）图灵机（续） l例如：请用例如：请用DIV3图灵机证明图灵机证明a13(二进制二进制1101) 被被3整除。整除。 当前状态当前状态纸带上的符号纸带上的符号下一步移动下一步移动下一个状态下一个状态 q0（初态）（初态） 0 1 空空 右右 右右 响铃或终止响铃或终止 q0 q1 q1 0 1 空空 右右 右右 输出非整除信息输出非整除信息 q2 q0 q2 0 1 空空 右右 右右 输出非整除信息输出非整除信息 q1 q2 43章节课堂 图灵机（续）图灵机（续） l

28、例如：请用例如：请用DIV3图灵机证明图灵机证明a13(二进制二进制1101) 被被3整除。整除。 当前状态当前状态纸带上的符号纸带上的符号下一步移动下一步移动下一个状态下一个状态 q0（初态）（初态） 0 1 空空 右右 右右 响铃或终止响铃或终止 q0 q1 q1 0 1 空空 右右 右右 输出非整除信息输出非整除信息 q2 q0 q2 0 1 空空 右右 右右 输出非整除信息输出非整除信息 q1 q2 44章节课堂 问题复杂性问题复杂性 l借助于图灵机理论，问题复杂型实际上就是在图借助于图灵机理论，问题复杂型实际上就是在图 灵机上解决最难的问题实例所需要的灵机上解决最难的问题实例所需要的

29、 l最小最小时间时间 l最小最小空间空间 45章节课堂 图灵机（续）图灵机（续） l图灵机图灵机M识别一个长度为识别一个长度为n的输入串而移动的步数的输入串而移动的步数 称为图灵机的称为图灵机的时间复杂性时间复杂性，记为：，记为： l当图灵机当图灵机M识别一个长度为识别一个长度为n的输入串，其写操作的输入串，其写操作 中读写头所访问的纸带单元数称为图灵机的中读写头所访问的纸带单元数称为图灵机的空间空间 复杂性复杂性，记为：，记为： ( ) M Tn ( ) M Sn 46章节课堂 图灵机（续）图灵机（续） 47章节课堂 问题分类问题分类 l如果一个问题在确定性图灵机上能够在多项式时如果一个问题

30、在确定性图灵机上能够在多项式时 间内得到处理，则称该问题时易处理的间内得到处理，则称该问题时易处理的 （tractable）。）。 l也既是说，能够用多项式时间解决的问题称之为易处理也既是说，能够用多项式时间解决的问题称之为易处理 的。的。 l不能够在多项式时间内解决的问题是难处理的。不能够在多项式时间内解决的问题是难处理的。 l因为随着输入尺寸的增加，求解这类问题需要的时间迅因为随着输入尺寸的增加，求解这类问题需要的时间迅 速变得很长，以至于不可能有效的求解。速变得很长，以至于不可能有效的求解。 l难处理的问题也被称为是难解的。难处理的问题也被称为是难解的。 48章节课堂 P类问题类问题 l

31、易处理问题的全体称为易处理问题的全体称为“多项式时间可解类多项式时间可解类”， 记为记为P类。类。 l复杂度类P包含所有能用多项式时间解决的问题。 上述定义表明，如果上述定义表明，如果L是多项式时间内可识别的语言，则确定是多项式时间内可识别的语言，则确定 性图灵机可以在多项式时间内，判定一个字符串是否属于语言性图灵机可以在多项式时间内，判定一个字符串是否属于语言 L。 49章节课堂 NP类问题类问题 l有这样一类问题，虽然不能够用确定性图灵机来有效求有这样一类问题，虽然不能够用确定性图灵机来有效求 解，但是却可以用非确定性图灵机在多项式时间内得到解，但是却可以用非确定性图灵机在多项式时间内得到

32、 处理处理 l这类问题称为这类问题称为“非确定性多项式时间可解问题非确定性多项式时间可解问题”，简称，简称 NP问题。问题。 定义（定义（NP类）类）NP类表示用非确定性图灵机在多类表示用非确定性图灵机在多 项式时间内可以识别的语言类。项式时间内可以识别的语言类。 50章节课堂 NP类问题（续）类问题（续） l意义：能够通过非确定性的多项式时间算法对许多对称密意义：能够通过非确定性的多项式时间算法对许多对称密 钥算法和所有公钥算法进行攻击。钥算法和所有公钥算法进行攻击。 lNP完全问题完全问题 ：指：指NP中的任何一个问题都可以通过多项式中的任何一个问题都可以通过多项式 时间转化为该问题时间转

33、化为该问题 。NP完全问题的全体被记为完全问题的全体被记为NPC 。 lNP完全问题是完全问题是NP问题中最难的问题。问题中最难的问题。 LNP 0 LNP 定义定义2.3.3（NP完全类）如果任意完全类）如果任意: 是非确定性多项式时间完全的（是非确定性多项式时间完全的（NP完全的）完全的） 都可以多项式规约到语言，则称都可以多项式规约到语言，则称: 51章节课堂 NP类问题（续）类问题（续） lNP中的任何一个问题都可以通过多项式时间转化为该问中的任何一个问题都可以通过多项式时间转化为该问 题题 。NP完全问题的全体被记为完全问题的全体被记为NPC 。 lNP完全问题是完全问题是NP问题中

34、最难的问题。问题中最难的问题。 52章节课堂 算法复杂性算法复杂性 l算法时间复杂度的度量方法算法时间复杂度的度量方法 l图灵机解决问题所移动的步数（该时间称之为算法的运图灵机解决问题所移动的步数（该时间称之为算法的运 行时间）行时间） l该度量方法的缺点：该度量方法的缺点： l没有考虑每一步具体的操作没有考虑每一步具体的操作 l例如：加法和乘法的计算开销是不同的例如：加法和乘法的计算开销是不同的 l为此，引入算法为此，引入算法“按位按位”的计算复杂度度量方法：的计算复杂度度量方法： l考虑操作如果按位进行所需要执行的考虑操作如果按位进行所需要执行的“步数步数” 53章节课堂 算法复杂性（续）

35、算法复杂性（续） 54章节课堂 算法复杂性（续）算法复杂性（续） 55章节课堂 算法复杂性（续）算法复杂性（续） 56章节课堂 算法复杂性算法复杂性-普通代数运算普通代数运算 57章节课堂 算法复杂性算法复杂性-模运算模运算 58章节课堂 算法复杂性算法复杂性-有限域有限域 59章节课堂 算法复杂性（续）算法复杂性（续） 求最大公因子的欧几里得算法 输入：整数 ab0 输出：gcd(a, b) 算法描述： 00 gcd(a, b) 01 if b=0 return(a); 02 return(gcd(b, a mod b) 60章节课堂 算法复杂性（续）算法复杂性（续） 61章节课堂 算法复杂

36、性（续）算法复杂性（续） 62章节课堂 算法复杂性（续）算法复杂性（续） 63章节课堂 算法复杂性（续）算法复杂性（续） 64章节课堂 算法复杂性（续）算法复杂性（续） 24602/2 23/2/2 11111 1. 22222 kkkkkd kk rrrrrr 65章节课堂 算法复杂性（续）算法复杂性（续） 0 /2/2 11 1 22 k kk rra /2 2 k a 66章节课堂 算法复杂性（续）算法复杂性（续） 67章节课堂 算法复杂性（续）算法复杂性（续） 如果将模运算视为基本运算单位（即一次模运算花费一 个时间单位），则算法的时间复杂度为2max(|a|,|b|)。 68章节课堂

37、 算法复杂性（续）算法复杂性（续） 求最大公因子的欧几里得算法 输入：整数 ab0 输出：gcd(a, b) 算法描述： 00 gcd(a, b) 01 if b=0 return(a); 02 return(gcd(b, a mod b) 69章节课堂 算法复杂性（续）算法复杂性（续） 3 2 (log ) ) a 求最大公因子的欧几里得算法 输入：整数 ab0 输出：gcd(a, b) 算法描述： 00 gcd(a, b) 01 if b=0 return(a); 02 return(gcd(b, a mod b) 70章节课堂 计算复杂性在信息安全中的应用计算复杂性在信息安全中的应用 l

38、在信息安全中，很难界定一个密码体制是否是安在信息安全中，很难界定一个密码体制是否是安 全的。全的。 l在经典密码学中，安全性的判定是基于信息论的。在经典密码学中，安全性的判定是基于信息论的。 l信息论关注的是密文当中到底包含多少关于明文的信息。信息论关注的是密文当中到底包含多少关于明文的信息。 l密文中关于明文的信息量越大，密码体制就越不安全。密文中关于明文的信息量越大，密码体制就越不安全。 l而只有当密文中不包含关于明文的信息时，密码体制才而只有当密文中不包含关于明文的信息时，密码体制才 是绝对安全的。是绝对安全的。 l香农证明过这种完美的安全性只有当密钥跟明文长度相香农证明过这种完美的安全

39、性只有当密钥跟明文长度相 等时，才能达到。等时，才能达到。 l这种安全性限制下的密码体制，其应用是非常困这种安全性限制下的密码体制，其应用是非常困 难。难。 71章节课堂 计算复杂性在信息安全中的应用（续）计算复杂性在信息安全中的应用（续） l在现代密码学当中，对安全性的判定是基于计算在现代密码学当中，对安全性的判定是基于计算 复杂性的。复杂性的。 l密文中是否包含明文的信息，这个问题对安全性来说并密文中是否包含明文的信息，这个问题对安全性来说并 不重要。不重要。 l关键是有没有有效的方法将密文中关于明文的信息提取关键是有没有有效的方法将密文中关于明文的信息提取 出来。出来。 l换句话说，基于

40、计算复杂性的密码学所关心的不是密码分析者换句话说，基于计算复杂性的密码学所关心的不是密码分析者 是否有可能破译算法（实际上，除了一次一密外，所有的密码是否有可能破译算法（实际上，除了一次一密外，所有的密码 体制都是有可能被破译），而是关心密码分析者是否具有相应体制都是有可能被破译），而是关心密码分析者是否具有相应 的资源和时间来破译算法。的资源和时间来破译算法。 72章节课堂 计算复杂性在信息安全中的应用（续）计算复杂性在信息安全中的应用（续） l例如例如: l如果一个密码算法的破译只是一个如果一个密码算法的破译只是一个P类问题，这个算法类问题，这个算法 当然会被认为是不安全。当然会被认为是不

41、安全。 l一个需要宇宙年龄那么长的时间才能破译的算法，当然一个需要宇宙年龄那么长的时间才能破译的算法，当然 有理由认为是安全的。有理由认为是安全的。 73章节课堂 计算复杂性在信息安全中的应用（续）计算复杂性在信息安全中的应用（续） l基于复杂性理论的现代密码学将基于复杂性理论的现代密码学将NPP作为一个必作为一个必 要条件，加密算法中，拥有正确加密要条件，加密算法中，拥有正确加密/解密密钥的解密密钥的 用户进行加密用户进行加密/解密是易处理的问题，而对于密码解密是易处理的问题，而对于密码 攻击者或分析者，从密文中提取明文或不用正确攻击者或分析者，从密文中提取明文或不用正确 的密钥构造合法的密

42、文应该是一个难解的问题。的密钥构造合法的密文应该是一个难解的问题。 l而很多加密算法是基于而很多加密算法是基于NP完全问题的，即这类型的算完全问题的，即这类型的算 法中，分析和破译是一个法中，分析和破译是一个NP完全问题。完全问题。 l我们称之为我们称之为NPP猜想。猜想。 74章节课堂 计算复杂性在信息安全中的应用（续）计算复杂性在信息安全中的应用（续） l如果如果NPP，则分析和破译加密算法是一个多项，则分析和破译加密算法是一个多项 式时间问题，即易处理的问题。那么这些加密算式时间问题，即易处理的问题。那么这些加密算 法将失去其安全性。法将失去其安全性。 l因此，如果这个猜想不正确，现在密码学将失去因此，如果这个猜想不正确，现在密码学将失去 其一个至关重要的理论基础。其一个至关重要的理论基础。 75章节课堂 计算复杂性在信息安全中的应用（续）计算复杂性在信息安全中的应用（续） l另一方面，即使另一方面，即使NPP猜想成立，基于猜想成立，基于NP完全问完全问 题难解性的密码算法也不一定是安全的。题难解