数学理论复杂性.ppt

《数学理论复杂性.ppt》由会员分享，可在线阅读，更多相关《数学理论复杂性.ppt（79页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、北京师范大学北京师范大学 数学学院数学学院 杨进杨进 网络与信息安全网络与信息安全2023/5/28问题复杂性问题复杂性第第2 2章章 信息安全数学基础（计算复杂性）信息安全数学基础（计算复杂性）算法复杂性算法复杂性2023/5/28问题复杂性问题复杂性第第2 2章章 信息安全数学基础（计算复杂性）信息安全数学基础（计算复杂性）算法复杂性算法复杂性2023/5/28l为什么要学习计算复杂性？为什么要学习计算复杂性？l计算复杂性是研究密码分析对于计算量的需求和密码分计算复杂性是研究密码分析对于计算量的需求和密码分析的困难程度析的困难程度，从而得出这些密码技术和算法在现有，从而得出这些密码技术和算

2、法在现有可行的条件下是否具有足够的安全性。可行的条件下是否具有足够的安全性。l学习计算复杂性，需要掌握两个概念：学习计算复杂性，需要掌握两个概念：l问题问题l算法算法 计算复杂性计算复杂性2023/5/28问题（问题（problem）l（问题）定义：即需要回答的一般性提问（问题）定义：即需要回答的一般性提问:l它通常含有若干个参数。它通常含有若干个参数。l对于一个问题进行描述应该包括两方面的内容：对于一个问题进行描述应该包括两方面的内容：l必须对问题的所有给定参数给出一般性描述；必须对问题的所有给定参数给出一般性描述；l必须描述该问题的答案（或解）应该满足的性质。必须描述该问题的答案（或解）应

3、该满足的性质。l当问题的所有参数都有了确定的取值时，我们称得到了当问题的所有参数都有了确定的取值时，我们称得到了该问题的一个实例（该问题的一个实例（instance）。）。2023/5/28算法（算法（algorithm）l定义（算法）定义（算法）：即求解某个问题的一系列具体步：即求解某个问题的一系列具体步骤（通常被理解为求解所需的通用计算程序）。骤（通常被理解为求解所需的通用计算程序）。l算法总是针对具体问题而言的，求解一个问题的算法通算法总是针对具体问题而言的，求解一个问题的算法通常不止一个。常不止一个。l当某个算法能够回答一个问题的任何实例时，我们称该当某个算法能够回答一个问题的任何实例

4、时，我们称该算法能够回答这个问题。算法能够回答这个问题。l当一个问题至少有一个能够回答该问题的算法时，我们当一个问题至少有一个能够回答该问题的算法时，我们称该问题可解（称该问题可解（resolvable），否则称该问题不可解），否则称该问题不可解（unresolvable）。）。2023/5/28算法（算法（algorithm）（续）（续）l有关算法的几点注释有关算法的几点注释：l算法总有输入和输出算法总有输入和输出l算法输入大小一般用输入变量的长度（单位为位）算法输入大小一般用输入变量的长度（单位为位）来表示来表示l一般来说，算法用某种编程语言来实现的计算机程序一般来说，算法用某种编程语言来

5、实现的计算机程序l一般来说，我们仅仅关注解决问题最有效的算法一般来说，我们仅仅关注解决问题最有效的算法2023/5/28问题与算法问题与算法l问题：如何求解两个整数问题：如何求解两个整数a和和b的最大公约数？的最大公约数？l参数：a和bl问题实例：a20，b30l算法：利用因子分解求算法：利用因子分解求a20和和b30的最大公约的最大公约数数la225lb235l因此a和b 的最大公约数是25102023/5/28算法复杂性算法复杂性 l（算法复杂度）定义：即度量该算法所需的计算（算法复杂度）定义：即度量该算法所需的计算能力能力，包括：，包括：l时间复杂性时间复杂性T（time complex

6、ity）；）；l空间复杂性空间复杂性S（space complexity）；）；l信道带宽；信道带宽；l数据总量；数据总量；l2023/5/28算法复杂性（续）算法复杂性（续）l计算复杂性的表示符号为计算复杂性的表示符号为“O”（称为（称为“大大O”，即算法，即算法的阶号），表示计算复杂性的的阶号），表示计算复杂性的数量级数量级 好处：好处：l使算法复杂性度量与处理器的运行速度和指令运行时间无关；使算法复杂性度量与处理器的运行速度和指令运行时间无关；l明确地揭示了输入的数据长度对算法复杂性的影响。明确地揭示了输入的数据长度对算法复杂性的影响。2023/5/28算法复杂性（续）算法复杂性（续）l

7、算法常见复杂性分类算法常见复杂性分类l（1）常数算法（）常数算法（constant Algorithm）：）：l如果运行时间是如果运行时间是O(1)，即该算法的复杂性不依赖于，即该算法的复杂性不依赖于n。l（2）线性算法（）线性算法（linear Algorithm）：）：l如果运行时间是如果运行时间是O(n)。l（3）多项式算法多项式算法（polynomial Algorithm）：）：l如果运行时间是如果运行时间是O(nm)，其中，其中m是一个常数。具有多项式复杂性的算法是一个常数。具有多项式复杂性的算法族被称为多项式时间算法。族被称为多项式时间算法。l（4）超多项式算法（）超多项式算法（

8、superpolynomial Algorithm）：）：l如果运行时间是，其中如果运行时间是，其中c是一个常数，而是一个常数，而s(n)是关于是关于n的大于常数而小于的大于常数而小于线性的函数。线性的函数。l（5）指数算法指数算法（exponential Algorithm）：）：l如果运行时间是，其中如果运行时间是，其中t是大于是大于1的常数，的常数，f(n)是关于是关于n的多项式函数。的多项式函数。2023/5/28算法复杂性（续）算法复杂性（续）l算法常见复杂性分类算法常见复杂性分类l一般而言，常数算法、线性算法、多项式算法和超多一般而言，常数算法、线性算法、多项式算法和超多项式算法统

9、称为项式算法统称为多项式算法多项式算法。l所谓多项式，就是具有下列形式的一个函数：所谓多项式，就是具有下列形式的一个函数：其中，其中，k和和ck是常数，且是常数，且ci称称0为。当为。当k0时，时，k称为多项式的称为多项式的次数，次数，ci称为多项式的系数。称为多项式的系数。2023/5/28算 法 复 杂 性l算法的分类及其运行时间算法的分类及其运行时间 算法算法类类型型复复杂杂性性运算次数运算次数n106时间时间多多项项式算法式算法常数算法常数算法O(1)11微秒微秒线线性算法性算法O(n)1061秒秒二次多二次多项项式算式算法法O(n2)101211.6天天三次多三次多项项式算式算法法O

10、(n3)101832,000年年指数算法指数算法O(2n)1030103010301006年年算法复杂性（续）算法复杂性（续）2023/5/28算算 法法 复复 杂杂 性性l算法复杂度的增长速度算法复杂度的增长速度算法复杂性（续）算法复杂性（续）亚指数亚指数指数指数多项式多项式2023/5/28算法复杂性（续）算法复杂性（续）l研究问题的内在复杂性，即在研究问题的内在复杂性，即在图灵机图灵机上解决最难上解决最难的问题实例所需的最小时间和空间条件。的问题实例所需的最小时间和空间条件。l图灵机是一种具有无限读、写存储带的有限状态图灵机是一种具有无限读、写存储带的有限状态机，可以被当作一个实际可用的

11、计算模型机，可以被当作一个实际可用的计算模型。2023/5/28问题复杂性问题复杂性第第2 2章章 信息安全数学基础（计算复杂性）信息安全数学基础（计算复杂性）算法复杂性算法复杂性2023/5/28问题复杂性问题复杂性 l图灵机分为两类：图灵机分为两类：l确定性图灵机。确定性图灵机。l非确定性图灵机非确定性图灵机2023/5/28问题复杂性（续）问题复杂性（续）l确定性图灵机确定性图灵机。l确定性图灵机的输出结果只取决于输入和初始状态。确定性图灵机的输出结果只取决于输入和初始状态。因此，对于具有相同输入和初始状态，运行一个确因此，对于具有相同输入和初始状态，运行一个确定性图灵机所得到的结果是完

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

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

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

15、被数是否能被3整除。整除。2023/5/28图灵机（续）图灵机（续）l例如：请设计一个图灵机，用于证明某个非负整例如：请设计一个图灵机，用于证明某个非负整数是否能被数是否能被3整除。整除。2023/5/28图灵机（续）图灵机（续）l例如：请设计一个图灵机，用于证明某个非负整例如：请设计一个图灵机，用于证明某个非负整数是否能被数是否能被3整除。整除。2023/5/28图灵机（续）图灵机（续）l例如：请设计一个图灵机，用于证明某个非负整例如：请设计一个图灵机，用于证明某个非负整数是否能被数是否能被3整除。整除。2023/5/28图灵机（续）图灵机（续）l例如：请设计一个图灵机，用于证明某个非负整例

16、如：请设计一个图灵机，用于证明某个非负整数是否能被数是否能被3整除。整除。2023/5/28图灵机（续）图灵机（续）l例如：请设计一个图灵机，用于证明某个非负整例如：请设计一个图灵机，用于证明某个非负整数是否能被数是否能被3整除。整除。2023/5/28图灵机（续）图灵机（续）l例如：请设计一个图灵机，用于证明某个非负整例如：请设计一个图灵机，用于证明某个非负整数是否能被数是否能被3整除。整除。2023/5/28图灵机（续）图灵机（续）l例如：请设计一个图灵机，用于证明某个非负整例如：请设计一个图灵机，用于证明某个非负整数是否能被数是否能被3整除。整除。2023/5/28图灵机（续）图灵机（续

17、）l例如：请用例如：请用DIV3图灵机证明图灵机证明a12(二进制二进制1100)能被能被3整除。整除。2023/5/28图灵机（续）图灵机（续）l例如：请用例如：请用DIV3图灵机证明图灵机证明a12(二进制二进制1011)能被能被3整除。整除。当前状当前状态态纸带纸带上的符号上的符号下一步移下一步移动动下一个状下一个状态态q0（初（初态态）01空空右右右右响响铃铃或或终终止止q0q1q101空空右右右右输输出非整除信息出非整除信息q2q0q201空空右右右右输输出非整除信息出非整除信息q1q22023/5/28图灵机（续）图灵机（续）l例如：请用例如：请用DIV3图灵机证明图灵机证明a12

18、(二进制二进制1011)能被能被3整除。整除。当前状当前状态态纸带纸带上的符号上的符号下一步移下一步移动动下一个状下一个状态态q0（初（初态态）01空空右右右右响响铃铃或或终终止止q0q1q101空空右右右右输输出非整除信息出非整除信息q2q0q201空空右右右右输输出非整除信息出非整除信息q1q22023/5/28图灵机（续）图灵机（续）l例如：请用例如：请用DIV3图灵机证明图灵机证明a12(二进制二进制1011)能被能被3整除。整除。当前状当前状态态纸带纸带上的符号上的符号下一步移下一步移动动下一个状下一个状态态q0（初（初态态）01空空右右右右响响铃铃或或终终止止q0q1q101空空右

19、右右右输输出非整除信息出非整除信息q2q0q201空空右右右右输输出非整除信息出非整除信息q1q22023/5/28图灵机（续）图灵机（续）l例如：请用例如：请用DIV3图灵机证明图灵机证明a12(二进制二进制1011)能被能被3整除。整除。当前状当前状态态纸带纸带上的符号上的符号下一步移下一步移动动下一个状下一个状态态q0（初（初态态）01空空右右右右响响铃铃或或终终止止q0q1q101空空右右右右输输出非整除信息出非整除信息q2q0q201空空右右右右输输出非整除信息出非整除信息q1q22023/5/28图灵机（续）图灵机（续）l例如：请用例如：请用DIV3图灵机证明图灵机证明a12(二进

20、制二进制1011)能被能被3整除。整除。当前状当前状态态纸带纸带上的符号上的符号下一步移下一步移动动下一个状下一个状态态q0（初（初态态）01空空右右右右响响铃铃或或终终止止q0q1q101空空右右右右输输出非整除信息出非整除信息q2q0q201空空右右右右输输出非整除信息出非整除信息q1q22023/5/28图灵机（续）图灵机（续）l例如：请用例如：请用DIV3图灵机证明图灵机证明a12(二进制二进制1011)能被能被3整除。整除。当前状当前状态态纸带纸带上的符号上的符号下一步移下一步移动动下一个状下一个状态态q0（初（初态态）01空空右右右右响响铃铃或或终终止止q0q1q101空空右右右右

21、输输出非整除信息出非整除信息q2q0q201空空右右右右输输出非整除信息出非整除信息q1q22023/5/28图灵机（续）图灵机（续）l例如：请用例如：请用DIV3图灵机证明图灵机证明a13(二进制二进制1101)不能被不能被3整除。整除。2023/5/28图灵机（续）图灵机（续）l例如：请用例如：请用DIV3图灵机证明图灵机证明a13(二进制二进制1101)被被3整除。整除。当前状当前状态态纸带纸带上的符号上的符号下一步移下一步移动动下一个状下一个状态态q0（初（初态态）01空空右右右右响响铃铃或或终终止止q0q1q101空空右右右右输输出非整除信息出非整除信息q2q0q201空空右右右右输

22、输出非整除信息出非整除信息q1q22023/5/28图灵机（续）图灵机（续）l例如：请用例如：请用DIV3图灵机证明图灵机证明a13(二进制二进制1101)被被3整除。整除。当前状当前状态态纸带纸带上的符号上的符号下一步移下一步移动动下一个状下一个状态态q0（初（初态态）01空空右右右右响响铃铃或或终终止止q0q1q101空空右右右右输输出非整除信息出非整除信息q2q0q201空空右右右右输输出非整除信息出非整除信息q1q22023/5/28图灵机（续）图灵机（续）l例如：请用例如：请用DIV3图灵机证明图灵机证明a13(二进制二进制1101)被被3整除。整除。当前状当前状态态纸带纸带上的符号

23、上的符号下一步移下一步移动动下一个状下一个状态态q0（初（初态态）01空空右右右右响响铃铃或或终终止止q0q1q101空空右右右右输输出非整除信息出非整除信息q2q0q201空空右右右右输输出非整除信息出非整除信息q1q22023/5/28图灵机（续）图灵机（续）l例如：请用例如：请用DIV3图灵机证明图灵机证明a13(二进制二进制1101)被被3整除。整除。当前状当前状态态纸带纸带上的符号上的符号下一步移下一步移动动下一个状下一个状态态q0（初（初态态）01空空右右右右响响铃铃或或终终止止q0q1q101空空右右右右输输出非整除信息出非整除信息q2q0q201空空右右右右输输出非整除信息出非

24、整除信息q1q22023/5/28图灵机（续）图灵机（续）l例如：请用例如：请用DIV3图灵机证明图灵机证明a13(二进制二进制1101)被被3整除。整除。当前状当前状态态纸带纸带上的符号上的符号下一步移下一步移动动下一个状下一个状态态q0（初（初态态）01空空右右右右响响铃铃或或终终止止q0q1q101空空右右右右输输出非整除信息出非整除信息q2q0q201空空右右右右输输出非整除信息出非整除信息q1q22023/5/28图灵机（续）图灵机（续）l例如：请用例如：请用DIV3图灵机证明图灵机证明a13(二进制二进制1101)被被3整除。整除。当前状当前状态态纸带纸带上的符号上的符号下一步移下

25、一步移动动下一个状下一个状态态q0（初（初态态）01空空右右右右响响铃铃或或终终止止q0q1q101空空右右右右输输出非整除信息出非整除信息q2q0q201空空右右右右输输出非整除信息出非整除信息q1q22023/5/28问题复杂性问题复杂性 l借助于图灵机理论，问题复杂型实际上就是在图借助于图灵机理论，问题复杂型实际上就是在图灵机上解决最难的问题实例所需要的灵机上解决最难的问题实例所需要的l最小最小时间时间l最小最小空间空间2023/5/28图灵机（续）图灵机（续）l图灵机图灵机M识别一个长度为识别一个长度为n的输入串而移动的步数的输入串而移动的步数称为图灵机的称为图灵机的时间复杂性时间复杂

26、性，记为：，记为：l当图灵机当图灵机M识别一个长度为识别一个长度为n的输入串，其写操作的输入串，其写操作中读写头所访问的纸带单元数称为图灵机的中读写头所访问的纸带单元数称为图灵机的空间空间复杂性复杂性，记为：，记为：2023/5/28图灵机（续）图灵机（续）2023/5/28问题分类问题分类l如果一个问题在确定性图灵机上能够在多项式时如果一个问题在确定性图灵机上能够在多项式时间内得到处理，则称该问题时易处理的间内得到处理，则称该问题时易处理的（tractable）。）。l也既是说，能够用多项式时间解决的问题称之为易处理也既是说，能够用多项式时间解决的问题称之为易处理的。的。l不能够在多项式时间

27、内解决的问题是难处理的。不能够在多项式时间内解决的问题是难处理的。l因为随着输入尺寸的增加，求解这类问题需要的时间迅因为随着输入尺寸的增加，求解这类问题需要的时间迅速变得很长，以至于不可能有效的求解。速变得很长，以至于不可能有效的求解。l难处理的问题也被称为是难解的。难处理的问题也被称为是难解的。2023/5/28P类问题类问题l易处理问题的全体称为易处理问题的全体称为“多项式时间可解类多项式时间可解类”，记为记为P类。类。l复杂度类P包含所有能用多项式时间解决的问题。上述定义表明，如果上述定义表明，如果L是多项式时间内可识别的语言，则确定是多项式时间内可识别的语言，则确定性图灵机可以在多项式

28、时间内，判定一个字符串是否属于语言性图灵机可以在多项式时间内，判定一个字符串是否属于语言L。2023/5/28NP类问题类问题l有这样一类问题，虽然不能够用确定性图灵机来有效求有这样一类问题，虽然不能够用确定性图灵机来有效求解，但是却可以用非确定性图灵机在多项式时间内得到解，但是却可以用非确定性图灵机在多项式时间内得到处理处理l这类问题称为这类问题称为“非确定性多项式时间可解问题非确定性多项式时间可解问题”，简称，简称NP问题。问题。定义（定义（NP类）类）NP类表示用非确定性图灵机在多项类表示用非确定性图灵机在多项式时间内可以识别的语言类。式时间内可以识别的语言类。2023/5/28NP类问

29、题（续）类问题（续）l意义：能够通过非确定性的多项式时间算法对许多对称密意义：能够通过非确定性的多项式时间算法对许多对称密钥算法和所有公钥算法进行攻击。钥算法和所有公钥算法进行攻击。lNP完全问题完全问题：指：指NP中的任何一个问题都可以通过多项式中的任何一个问题都可以通过多项式时间转化为该问题时间转化为该问题。NP完全问题的全体被记为完全问题的全体被记为NPC。lNP完全问题是完全问题是NP问题中最难的问题。问题中最难的问题。定义（定义（NP完全类）如果任意完全类）如果任意:是非确定性多项式时间完全的（是非确定性多项式时间完全的（NP完全的）完全的）都可以多项式规约到语言，则称都可以多项式规

30、约到语言，则称:2023/5/28NP类问题（续）类问题（续）lNP中的任何一个问题都可以通过多项式时间转化为该问中的任何一个问题都可以通过多项式时间转化为该问题题。NP完全问题的全体被记为完全问题的全体被记为NPC。lNP完全问题是完全问题是NP问题中最难的问题。问题中最难的问题。2023/5/28算法复杂性算法复杂性l算法时间复杂度的度量方法算法时间复杂度的度量方法l图灵机解决问题所移动的步数（该时间称之为算法的运图灵机解决问题所移动的步数（该时间称之为算法的运行时间）行时间）l该度量方法的缺点：该度量方法的缺点：l没有考虑每一步具体的操作没有考虑每一步具体的操作l例如：加法和乘法的计算开

31、销是不同的例如：加法和乘法的计算开销是不同的l为此，引入算法为此，引入算法“按位按位”的计算复杂度度量方法：的计算复杂度度量方法：l考虑操作如果按位进行所需要执行的考虑操作如果按位进行所需要执行的“步数步数”2023/5/28算法复杂性（续）算法复杂性（续）2023/5/28算法复杂性（续）算法复杂性（续）2023/5/28算法复杂性（续）算法复杂性（续）2023/5/28算法复杂性算法复杂性-普通代数运算普通代数运算2023/5/28算法复杂性算法复杂性-模运算模运算2023/5/28算法复杂性算法复杂性-有限域有限域2023/5/28算法复杂性（续）算法复杂性（续）2023/5/28算法复

32、杂性（续）算法复杂性（续）2023/5/28算法复杂性（续）算法复杂性（续）2023/5/28算法复杂性（续）算法复杂性（续）2023/5/28算法复杂性（续）算法复杂性（续）2023/5/28算法复杂性（续）算法复杂性（续）2023/5/28算法复杂性（续）算法复杂性（续）2023/5/28算法复杂性（续）算法复杂性（续）2023/5/28算法复杂性（续）算法复杂性（续）如果将模运算视为基本运算单位（即一次模运算花费一个时间单位），则算法的时间复杂度为2max(|a|,|b|)。2023/5/28算法复杂性（续）算法复杂性（续）2023/5/28算法复杂性（续）算法复杂性（续）2023/5/

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

34、全性只有当密钥跟明文长度相香农证明过这种完美的安全性只有当密钥跟明文长度相等时，才能达到。等时，才能达到。l这种安全性限制下的密码体制，其应用是非常困这种安全性限制下的密码体制，其应用是非常困难。难。2023/5/28计算复杂性在信息安全中的应用（续）计算复杂性在信息安全中的应用（续）l在现代密码学当中，对安全性的判定是基于计算在现代密码学当中，对安全性的判定是基于计算复杂性的。复杂性的。l密文中是否包含明文的信息，这个问题对安全性来说并密文中是否包含明文的信息，这个问题对安全性来说并不重要。不重要。l关键是有没有有效的方法将密文中关于明文的信息提取关键是有没有有效的方法将密文中关于明文的信息

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

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

37、造合法的密文应该是一个难解的问题。的密钥构造合法的密文应该是一个难解的问题。l而很多加密算法是基于而很多加密算法是基于NP完全问题的，即这类型的算完全问题的，即这类型的算法中，分析和破译是一个法中，分析和破译是一个NP完全问题。完全问题。l我们称之为我们称之为NPP猜想。猜想。2023/5/28计算复杂性在信息安全中的应用（续）计算复杂性在信息安全中的应用（续）l如果如果NPP，则分析和破译加密算法是一个多项，则分析和破译加密算法是一个多项式时间问题，即易处理的问题。那么这些加密算式时间问题，即易处理的问题。那么这些加密算法将失去其安全性。法将失去其安全性。l因此，如果这个猜想不正确，现在密码

38、学将失去因此，如果这个猜想不正确，现在密码学将失去其一个至关重要的理论基础。其一个至关重要的理论基础。2023/5/28计算复杂性在信息安全中的应用（续）计算复杂性在信息安全中的应用（续）l另一方面，即使另一方面，即使NPP猜想成立，基于猜想成立，基于NP完全问完全问题难解性的密码算法也不一定是安全的。题难解性的密码算法也不一定是安全的。l例如：例如：l基于基于NP完全的著名的完全的著名的背包问题背包问题破解就是一个反例。破解就是一个反例。l这是因为即使一个问题只有可以忽略的少数困难实例，这是因为即使一个问题只有可以忽略的少数困难实例，该问题也被认为是困难的。该问题也被认为是困难的。l相反，密

39、码分析只要能破解不可忽略比例的实例，就认相反，密码分析只要能破解不可忽略比例的实例，就认为是成功的。为是成功的。l这就是为什么破解一个基于这就是为什么破解一个基于NP完全问题的密码体完全问题的密码体制未必导致其基于的制未必导致其基于的NP完全问题的求解。完全问题的求解。2023/5/28计算复杂性在信息安全中的应用（续）计算复杂性在信息安全中的应用（续）l基于复杂性理论中的困难性作为现代密码学的安基于复杂性理论中的困难性作为现代密码学的安全性基础是不充分的全性基础是不充分的l近年来，密码学界广泛推崇一种被称为近年来，密码学界广泛推崇一种被称为可证明安可证明安全性全性的密码系统。的密码系统。l这

40、种密码系统采用一种被称为这种密码系统采用一种被称为多项式规约技术多项式规约技术的形式化的形式化方法来证明一种密码体制的安全性。方法来证明一种密码体制的安全性。l在多项式规约技术中，将对密码体制的攻击规约到求解在多项式规约技术中，将对密码体制的攻击规约到求解一类已知的一类已知的NP问题的一个实例。问题的一个实例。l这种方法证明如果这种密码体制是可破译的，则它所基这种方法证明如果这种密码体制是可破译的，则它所基于的于的NP问题实例是可解的。问题实例是可解的。2023/5/28计算复杂性在信息安全中的应用（续）计算复杂性在信息安全中的应用（续）l例如，最常用的多项式规约技术，就是将密码算例如，最常用

41、的多项式规约技术，就是将密码算法的安全性规约到大整数分解困难性问题。法的安全性规约到大整数分解困难性问题。l由于人们广泛相信这种实例没有有效的解法，所以对于由于人们广泛相信这种实例没有有效的解法，所以对于考虑中的密码体制的安全性，这样的一个证明提供了很考虑中的密码体制的安全性，这样的一个证明提供了很高的可信度。高的可信度。2023/5/28教材与参考书教材与参考书l教材：教材：l李毅超李毅超 曹跃，网络与系统攻击技术曹跃，网络与系统攻击技术 电子科大出版社电子科大出版社 2007 l周世杰周世杰 陈伟陈伟 钟婷，网络与系统防御技术钟婷，网络与系统防御技术 电子科大出版社电子科大出版社 2007

42、 l参考书参考书l阙喜戎阙喜戎 等等 编著，信息安全原理及应用，清华大学出版社编著，信息安全原理及应用，清华大学出版社lChristopher M.King,Curitis E.Dalton,T.Ertem Osmanoglu（常晓波等译）（常晓波等译）.安全体系结构的设计、部署与操作，清华大学出安全体系结构的设计、部署与操作，清华大学出版社，版社，2003(Christopher M.King,et al,Security Architecture,design,deployment&Operations)lWilliam Stallings，密码编码学与网络安全原理与实践（第四，密码编码学

43、与网络安全原理与实践（第四版），电子工业出版社版），电子工业出版社l蔡皖东，网络与信息安全，西北工业大学出版社，蔡皖东，网络与信息安全，西北工业大学出版社，2004l李建平，小波分析与信息处理李建平，小波分析与信息处理-理论、应用及软件实现，理论、应用及软件实现，1997年年第一版，第一版，2001年第二版，年第二版，2003年第二版修订版。年第二版修订版。l张世永，网络安全原理与应用，科学出版社，张世永，网络安全原理与应用，科学出版社，2003l杨义先等，杨义先等，信息安全理论与技术信息安全理论与技术，邮电出版社，邮电出版社2023/5/28Any Question?Q&A2023/5/28