《计算机系统与网络安全：第2章 信息安全数学基础（计算复杂性）》由会员分享，可在线阅读，更多相关《计算机系统与网络安全：第2章 信息安全数学基础（计算复杂性）（79页珍藏版）》请在金锄头文库上搜索。
1、2024/8/10问题复杂性问题复杂性第第2 2章章 信息安全数学基础（计算复杂性）信息安全数学基础（计算复杂性）算法复杂性算法复杂性2024/8/10问题复杂性问题复杂性第第2 2章章 信息安全数学基础（计算复杂性）信息安全数学基础（计算复杂性）算法复杂性算法复杂性2024/8/10 古书古书孟子孟子离娄上离娄上有这样的记载：有这样的记载：淳于髡曰：男女授受不亲，礼與？淳于髡曰：男女授受不亲，礼與？孟子曰：礼也。孟子曰：礼也。曰：嫂溺则授之以手乎？曰：嫂溺则授之以手乎？曰：嫂溺不授，是豺狼也。男女授受不亲，礼曰：嫂溺不授，是豺狼也。男女授受不亲，礼也；嫂溺授之以手，权也。也；嫂溺授之以手，权
2、也。虽然有虽然有“男女授受不亲男女授受不亲”的原则存在，但嫂子落的原则存在，但嫂子落水快淹死时，必须拉她、救她，这是水快淹死时，必须拉她、救她，这是“权权”(变通变通)，否则，见死不救，就是豺狼。，否则，见死不救，就是豺狼。曰：今天下溺矣，夫子之不援何也？曰：今天下溺矣，夫子之不援何也？曰：天下溺援之以道；嫂溺援之以手。子欲手援曰：天下溺援之以道；嫂溺援之以手。子欲手援天下乎？天下乎？计算复杂性基础计算复杂性基础2024/8/10l为什么要学习计算复杂性？为什么要学习计算复杂性？l计算复杂性是研究密码分析对于计算量的需求和密码分计算复杂性是研究密码分析对于计算量的需求和密码分析的困难程度析的困
3、难程度 ，从而得出这些密码技术和算法在现有，从而得出这些密码技术和算法在现有可行的条件下是否具有足够的安全性。可行的条件下是否具有足够的安全性。l学习计算复杂性，需要掌握两个概念：学习计算复杂性，需要掌握两个概念：l问题问题l算法算法 计算复杂性计算复杂性2024/8/10问题（问题（problem） l（问题）定义：即需要回答的一般性提问（问题）定义：即需要回答的一般性提问:l它通常含有若干个参数。它通常含有若干个参数。l对于一个问题进行描述应该包括两方面的内容：对于一个问题进行描述应该包括两方面的内容：l必须对问题的所有给定参数给出一般性描述；必须对问题的所有给定参数给出一般性描述；l必须
4、描述该问题的答案（或解）应该满足的性质。必须描述该问题的答案（或解）应该满足的性质。l当问题的所有参数都有了确定的取值时，我们称得到了当问题的所有参数都有了确定的取值时，我们称得到了该问题的一个实例（该问题的一个实例（instance）。）。 2024/8/10算法（算法（algorithm） l定义（算法）定义（算法） ：即求解某个问题的一系列具体步：即求解某个问题的一系列具体步骤（通常被理解为求解所需的通用计算程序）。骤（通常被理解为求解所需的通用计算程序）。l算法总是针对具体问题而言的，求解一个问题的算法通算法总是针对具体问题而言的，求解一个问题的算法通常不止一个。常不止一个。l当某个算
5、法能够回答一个问题的任何实例时，我们称该当某个算法能够回答一个问题的任何实例时，我们称该算法能够回答这个问题。算法能够回答这个问题。l当一个问题至少有一个能够回答该问题的算法时，我们当一个问题至少有一个能够回答该问题的算法时，我们称该问题可解（称该问题可解（resolvable），否则称该问题不可解），否则称该问题不可解（unresolvable）。）。 2024/8/10算法（算法（algorithm）（续）（续） l有关算法的几点注释有关算法的几点注释：l算法总有输入和输出算法总有输入和输出l算法输入大小一般用输入变量的长度（单位为位）算法输入大小一般用输入变量的长度（单位为位）来表示来表
6、示l一般来说，算法用某种编程语言来实现的计算机程序一般来说，算法用某种编程语言来实现的计算机程序l一般来说，我们仅仅关注解决问题最有效的算法一般来说，我们仅仅关注解决问题最有效的算法2024/8/10问题与算法问题与算法l问题：如何求解两个整数问题：如何求解两个整数a和和b的最大公约数？的最大公约数？l参数：a和bl问题实例：a20，b30l算法：利用因子分解求算法：利用因子分解求a20和和b30的最大公约的最大公约数数la225lb235l因此a和b 的最大公约数是25102024/8/10算法复杂性算法复杂性 l（算法复杂度）定义：即度量该算法所需的计算（算法复杂度）定义：即度量该算法所需
7、的计算能力能力 ，包括：，包括：l时间复杂性时间复杂性T（time complexity）；）；l空间复杂性空间复杂性S（space complexity）；）； l信道带宽；信道带宽；l数据总量；数据总量； l2024/8/10算法复杂性（续）算法复杂性（续）l计算复杂性的表示符号为计算复杂性的表示符号为“ O ”（称为（称为“大大O ”，即算法的，即算法的阶号），表示计算复杂性的阶号），表示计算复杂性的数量级数量级 好处：好处：l使算法复杂性度量与处理器的运行速度和指令运行时间无关；使算法复杂性度量与处理器的运行速度和指令运行时间无关； l明确地揭示了输入的数据长度对算法复杂性的影响。明确
8、地揭示了输入的数据长度对算法复杂性的影响。 2024/8/10算法复杂性（续）算法复杂性（续）l算法常见复杂性分类算法常见复杂性分类l（1）常数算法（）常数算法（constant Algorithm）：）：l如果运行时间是如果运行时间是O (1)，即该算法的复杂性不依赖于，即该算法的复杂性不依赖于n。l（2）线性算法（）线性算法（linear Algorithm）：）：l如果运行时间是如果运行时间是O(n)。l（3）多项式算法多项式算法（polynomial Algorithm）：）：l如果运行时间是如果运行时间是O(nm)，其中，其中m是一个常数。具有多项式复杂性的算法是一个常数。具有多项式
9、复杂性的算法族被称为多项式时间算法。族被称为多项式时间算法。l（4）超多项式算法（）超多项式算法（superpolynomial Algorithm）：）：l如果运行时间是，其中如果运行时间是，其中c是一个常数，而是一个常数，而s(n)是关于是关于n的大于常数而小于的大于常数而小于线性的函数。线性的函数。l（5）指数算法指数算法（exponential Algorithm）：）：l如果运行时间是，其中如果运行时间是，其中t是大于是大于1的常数，的常数，f(n)是关于是关于n的多项式函数。的多项式函数。2024/8/10算法复杂性（续）算法复杂性（续）l算法常见复杂性分类算法常见复杂性分类l一般
10、而言，常数算法、线性算法、多项式算法和超多一般而言，常数算法、线性算法、多项式算法和超多项式算法统称为项式算法统称为多项式算法多项式算法。l所谓多项式，就是具有下列形式的一个函数：所谓多项式，就是具有下列形式的一个函数：其中，其中，k和和ck是常数，且是常数，且ci称称0为为。当。当k0时，k称称为多多项式的式的次数，次数，ci称称为多多项式的系数。式的系数。 2024/8/10算 法 复 杂 性l算法的分类及其运行时间算法的分类及其运行时间 算法算法类型型复复杂性性运算次数运算次数n106时间多多项式算法式算法常数算法常数算法O(1)11微秒微秒线性算法性算法O(n)1061秒秒二次多二次多
11、项式算式算法法O(n2)101211.6天天三次多三次多项式算式算法法O(n3)101832,000年年指数算法指数算法O(2n)1030103010301006年年算法复杂性（续）算法复杂性（续）2024/8/10算算 法法 复复 杂杂 性性l算法复杂度的增长速度算法复杂度的增长速度算法复杂性（续）算法复杂性（续）亚指数亚指数指数指数多项式多项式2024/8/10算法复杂性（续）算法复杂性（续）l研究问题的内在复杂性，即在研究问题的内在复杂性，即在图灵机图灵机上解决最难上解决最难的问题实例所需的最小时间和空间条件。的问题实例所需的最小时间和空间条件。l图灵机是一种具有无限读、写存储带的有限状
12、态图灵机是一种具有无限读、写存储带的有限状态机，可以被当作一个实际可用的计算模型机，可以被当作一个实际可用的计算模型 。2024/8/10问题复杂性问题复杂性第第2 2章章 信息安全数学基础（计算复杂性）信息安全数学基础（计算复杂性）算法复杂性算法复杂性2024/8/10问题复杂性问题复杂性 l图灵机分为两类：图灵机分为两类：l确定性图灵机。确定性图灵机。l非确定性图灵机非确定性图灵机2024/8/10问题复杂性（续）问题复杂性（续）l确定性图灵机确定性图灵机。l确定性图灵机的输出结果只取决于输入和初始状态。确定性图灵机的输出结果只取决于输入和初始状态。因此，对于具有相同输入和初始状态，运行一
13、个确因此，对于具有相同输入和初始状态，运行一个确定性图灵机所得到的结果是完全相同的。定性图灵机所得到的结果是完全相同的。l非确定性图灵机非确定性图灵机 ：l能够进行猜测。能够进行猜测。l求解一个问题分两个阶段：猜测阶段和验证阶段。求解一个问题分两个阶段：猜测阶段和验证阶段。2024/8/10图灵机图灵机l图灵机包括一个有限状态控制单元、图灵机包括一个有限状态控制单元、k（1）条纸）条纸带（带（Tape）和）和k个读写头（个读写头（Tapehead）。）。l有限状态控制单元控制每个读写头访问一条纸带，并沿有限状态控制单元控制每个读写头访问一条纸带，并沿着纸带左右移动着纸带左右移动l图灵机求解问题
14、的输入是一个有限长度的字符串，该输图灵机求解问题的输入是一个有限长度的字符串，该输入占据每条纸带无限个单元的最左边的有限个单元。入占据每条纸带无限个单元的最左边的有限个单元。l读写头对纸带的一次访问称之为一个合法移动读写头对纸带的一次访问称之为一个合法移动（Move）。）。2024/8/10图灵机（续）图灵机（续）l图灵机求解问题时，被赋予一个初始状态（图灵机求解问题时，被赋予一个初始状态（Initial State），且一步一步地移动，从而完成对输入的），且一步一步地移动，从而完成对输入的扫描。扫描。l如果图灵机最终扫描了整个输入串，且满足了中止条件如果图灵机最终扫描了整个输入串，且满足了中
15、止条件而停止下来，则称图灵机识别了该输入。而停止下来，则称图灵机识别了该输入。l否则，图灵机在某一点没有合法移动，因此会没有识别否则，图灵机在某一点没有合法移动，因此会没有识别输入串而停止下来，此时称图灵机无法识别该输入。输入串而停止下来，此时称图灵机无法识别该输入。l图灵机所识别的一个输入，称为一种可识别语言的一个图灵机所识别的一个输入，称为一种可识别语言的一个实例。实例。 2024/8/10图灵机（续）图灵机（续）l例如：请设计一个图灵机，用于证明某个非负整例如：请设计一个图灵机，用于证明某个非负整数是否能被数是否能被3整除。整除。2024/8/10图灵机（续）图灵机（续）l例如：请设计一
16、个图灵机，用于证明某个非负整例如：请设计一个图灵机，用于证明某个非负整数是否能被数是否能被3整除。整除。2024/8/10图灵机（续）图灵机（续）l例如：请设计一个图灵机，用于证明某个非负整例如：请设计一个图灵机，用于证明某个非负整数是否能被数是否能被3整除。整除。2024/8/10图灵机（续）图灵机（续）l例如：请设计一个图灵机，用于证明某个非负整例如：请设计一个图灵机，用于证明某个非负整数是否能被数是否能被3整除。整除。2024/8/10图灵机（续）图灵机（续）l例如：请设计一个图灵机，用于证明某个非负整例如：请设计一个图灵机，用于证明某个非负整数是否能被数是否能被3整除。整除。2024/
17、8/10图灵机（续）图灵机（续）l例如：请设计一个图灵机，用于证明某个非负整例如：请设计一个图灵机，用于证明某个非负整数是否能被数是否能被3整除。整除。2024/8/10图灵机（续）图灵机（续）l例如：请设计一个图灵机，用于证明某个非负整例如：请设计一个图灵机，用于证明某个非负整数是否能被数是否能被3整除。整除。2024/8/10图灵机（续）图灵机（续）l例如：请设计一个图灵机，用于证明某个非负整例如：请设计一个图灵机，用于证明某个非负整数是否能被数是否能被3整除。整除。2024/8/10图灵机（续）图灵机（续）l例如：请设计一个图灵机，用于证明某个非负整例如：请设计一个图灵机，用于证明某个非
18、负整数是否能被数是否能被3整除。整除。2024/8/10图灵机（续）图灵机（续）l例如：请用例如：请用DIV3图灵机证明图灵机证明a12(二进制二进制1100)能被能被3整除。整除。2024/8/10图灵机（续）图灵机（续）l例如：请用例如：请用DIV3图灵机证明图灵机证明a12(二进制二进制1011)能被能被3整除。整除。当前状当前状态纸带上的符号上的符号下一步移下一步移动下一个状下一个状态q0（初（初态）01空空右右右右响响铃或或终止止q0q1q101空空右右右右输出非整除信息出非整除信息q2q0q201空空右右右右输出非整除信息出非整除信息q1q22024/8/10图灵机（续）图灵机（续
19、）l例如：请用例如：请用DIV3图灵机证明图灵机证明a12(二进制二进制1011)能被能被3整除。整除。当前状当前状态纸带上的符号上的符号下一步移下一步移动下一个状下一个状态q0（初（初态）01空空右右右右响响铃或或终止止q0q1q101空空右右右右输出非整除信息出非整除信息q2q0q201空空右右右右输出非整除信息出非整除信息q1q22024/8/10图灵机（续）图灵机（续）l例如：请用例如：请用DIV3图灵机证明图灵机证明a12(二进制二进制1011)能被能被3整除。整除。当前状当前状态纸带上的符号上的符号下一步移下一步移动下一个状下一个状态q0（初（初态）01空空右右右右响响铃或或终止止
20、q0q1q101空空右右右右输出非整除信息出非整除信息q2q0q201空空右右右右输出非整除信息出非整除信息q1q22024/8/10图灵机（续）图灵机（续）l例如：请用例如：请用DIV3图灵机证明图灵机证明a12(二进制二进制1011)能被能被3整除。整除。当前状当前状态纸带上的符号上的符号下一步移下一步移动下一个状下一个状态q0（初（初态）01空空右右右右响响铃或或终止止q0q1q101空空右右右右输出非整除信息出非整除信息q2q0q201空空右右右右输出非整除信息出非整除信息q1q22024/8/10图灵机（续）图灵机（续）l例如：请用例如：请用DIV3图灵机证明图灵机证明a12(二进制
21、二进制1011)能被能被3整除。整除。当前状当前状态纸带上的符号上的符号下一步移下一步移动下一个状下一个状态q0（初（初态）01空空右右右右响响铃或或终止止q0q1q101空空右右右右输出非整除信息出非整除信息q2q0q201空空右右右右输出非整除信息出非整除信息q1q22024/8/10图灵机（续）图灵机（续）l例如：请用例如：请用DIV3图灵机证明图灵机证明a12(二进制二进制1011)能被能被3整除。整除。当前状当前状态纸带上的符号上的符号下一步移下一步移动下一个状下一个状态q0（初（初态）01空空右右右右响响铃或或终止止q0q1q101空空右右右右输出非整除信息出非整除信息q2q0q2
22、01空空右右右右输出非整除信息出非整除信息q1q22024/8/10图灵机（续）图灵机（续）l例如：请用例如：请用DIV3图灵机证明图灵机证明a13(二进制二进制1101)不能被不能被3整除。整除。2024/8/10图灵机（续）图灵机（续）l例如：请用例如：请用DIV3图灵机证明图灵机证明a13(二进制二进制1101)被被3整除。整除。当前状当前状态纸带上的符号上的符号下一步移下一步移动下一个状下一个状态q0（初（初态）01空空右右右右响响铃或或终止止q0q1q101空空右右右右输出非整除信息出非整除信息q2q0q201空空右右右右输出非整除信息出非整除信息q1q22024/8/10图灵机（续
23、）图灵机（续）l例如：请用例如：请用DIV3图灵机证明图灵机证明a13(二进制二进制1101)被被3整除。整除。当前状当前状态纸带上的符号上的符号下一步移下一步移动下一个状下一个状态q0（初（初态）01空空右右右右响响铃或或终止止q0q1q101空空右右右右输出非整除信息出非整除信息q2q0q201空空右右右右输出非整除信息出非整除信息q1q22024/8/10图灵机（续）图灵机（续）l例如：请用例如：请用DIV3图灵机证明图灵机证明a13(二进制二进制1101)被被3整除。整除。当前状当前状态纸带上的符号上的符号下一步移下一步移动下一个状下一个状态q0（初（初态）01空空右右右右响响铃或或终
24、止止q0q1q101空空右右右右输出非整除信息出非整除信息q2q0q201空空右右右右输出非整除信息出非整除信息q1q22024/8/10图灵机（续）图灵机（续）l例如：请用例如：请用DIV3图灵机证明图灵机证明a13(二进制二进制1101)被被3整除。整除。当前状当前状态纸带上的符号上的符号下一步移下一步移动下一个状下一个状态q0（初（初态）01空空右右右右响响铃或或终止止q0q1q101空空右右右右输出非整除信息出非整除信息q2q0q201空空右右右右输出非整除信息出非整除信息q1q22024/8/10图灵机（续）图灵机（续）l例如：请用例如：请用DIV3图灵机证明图灵机证明a13(二进制
25、二进制1101)被被3整除。整除。当前状当前状态纸带上的符号上的符号下一步移下一步移动下一个状下一个状态q0（初（初态）01空空右右右右响响铃或或终止止q0q1q101空空右右右右输出非整除信息出非整除信息q2q0q201空空右右右右输出非整除信息出非整除信息q1q22024/8/10图灵机（续）图灵机（续）l例如：请用例如：请用DIV3图灵机证明图灵机证明a13(二进制二进制1101)被被3整除。整除。当前状当前状态纸带上的符号上的符号下一步移下一步移动下一个状下一个状态q0（初（初态）01空空右右右右响响铃或或终止止q0q1q101空空右右右右输出非整除信息出非整除信息q2q0q201空空
26、右右右右输出非整除信息出非整除信息q1q22024/8/10问题复杂性问题复杂性 l借助于图灵机理论，问题复杂型实际上就是在图借助于图灵机理论，问题复杂型实际上就是在图灵机上解决最难的问题实例所需要的灵机上解决最难的问题实例所需要的l最小最小时间时间l最小最小空间空间2024/8/10图灵机（续）图灵机（续）l图灵机图灵机M识别一个长度为识别一个长度为n的输入串而移动的步数的输入串而移动的步数称为图灵机的称为图灵机的时间复杂性时间复杂性，记为：，记为：l当图灵机当图灵机M识别一个长度为识别一个长度为n的输入串，其写操作的输入串，其写操作中读写头所访问的纸带单元数称为图灵机的中读写头所访问的纸带
27、单元数称为图灵机的空间空间复杂性复杂性，记为：，记为：2024/8/10图灵机（续）图灵机（续）2024/8/10问题分类问题分类l如果一个问题在确定性图灵机上能够在多项式时如果一个问题在确定性图灵机上能够在多项式时间内得到处理，则称该问题时易处理的间内得到处理，则称该问题时易处理的（tractable）。）。l也既是说，能够用多项式时间解决的问题称之为易处理也既是说，能够用多项式时间解决的问题称之为易处理的。的。l不能够在多项式时间内解决的问题是难处理的。不能够在多项式时间内解决的问题是难处理的。l因为随着输入尺寸的增加，求解这类问题需要的时间迅因为随着输入尺寸的增加，求解这类问题需要的时间
28、迅速变得很长，以至于不可能有效的求解。速变得很长，以至于不可能有效的求解。l难处理的问题也被称为是难解的。难处理的问题也被称为是难解的。 2024/8/10P类问题类问题l易处理问题的全体称为易处理问题的全体称为“多项式时间可解类多项式时间可解类”，记为记为P类。类。l复杂度类P包含所有能用多项式时间解决的问题。上述定义表明，如果上述定义表明，如果L是多项式时间内可识别的语言，则确定是多项式时间内可识别的语言，则确定性图灵机可以在多项式时间内，判定一个字符串是否属于语言性图灵机可以在多项式时间内，判定一个字符串是否属于语言L。2024/8/10NP类问题类问题l有这样一类问题，虽然不能够用确定
29、性图灵机来有效求有这样一类问题，虽然不能够用确定性图灵机来有效求解，但是却可以用非确定性图灵机在多项式时间内得到解，但是却可以用非确定性图灵机在多项式时间内得到处理处理l这类问题称为这类问题称为“非确定性多项式时间可解问题非确定性多项式时间可解问题”，简称，简称NP问题。问题。定义（定义（NP类）类）NP类表示用非确定性图灵机在多项类表示用非确定性图灵机在多项式时间内可以识别的语言类。式时间内可以识别的语言类。2024/8/10NP类问题（续）类问题（续）l意义：能够通过非确定性的多项式时间算法对许多对称密意义：能够通过非确定性的多项式时间算法对许多对称密钥算法和所有公钥算法进行攻击。钥算法和
30、所有公钥算法进行攻击。 lNP完全问题完全问题 ：指：指NP中的任何一个问题都可以通过多项式中的任何一个问题都可以通过多项式时间转化为该问题时间转化为该问题 。NP完全问题的全体被记为完全问题的全体被记为NPC 。lNP完全问题是完全问题是NP问题中最难的问题。问题中最难的问题。 定定义2.3.3（NP完全完全类）如果任意）如果任意: 是非确定性多项式时间完全的（是非确定性多项式时间完全的（NP完全的）完全的）都可以多项式规约到语言，则称都可以多项式规约到语言，则称:2024/8/10NP类问题（续）类问题（续）lNP中的任何一个问题都可以通过多项式时间转化为该问中的任何一个问题都可以通过多项
31、式时间转化为该问题题 。NP完全问题的全体被记为完全问题的全体被记为NPC 。lNP完全问题是完全问题是NP问题中最难的问题。问题中最难的问题。2024/8/10算法复杂性算法复杂性l算法时间复杂度的度量方法算法时间复杂度的度量方法l图灵机解决问题所移动的步数（该时间称之为算法的运图灵机解决问题所移动的步数（该时间称之为算法的运行时间）行时间）l该度量方法的缺点：该度量方法的缺点：l没有考虑每一步具体的操作没有考虑每一步具体的操作l例如：加法和乘法的计算开销是不同的例如：加法和乘法的计算开销是不同的l为此，引入算法为此，引入算法“按位按位”的计算复杂度度量方法：的计算复杂度度量方法：l考虑操作
32、如果按位进行所需要执行的考虑操作如果按位进行所需要执行的“步数步数”2024/8/10算法复杂性（续）算法复杂性（续）2024/8/10算法复杂性（续）算法复杂性（续）2024/8/10算法复杂性（续）算法复杂性（续）2024/8/10算法复杂性算法复杂性-普通代数运算普通代数运算2024/8/10算法复杂性算法复杂性-模运算模运算2024/8/10算法复杂性算法复杂性-有限域有限域2024/8/10算法复杂性（续）算法复杂性（续）2024/8/10算法复杂性（续）算法复杂性（续）2024/8/10算法复杂性（续）算法复杂性（续）2024/8/10算法复杂性（续）算法复杂性（续）2024/8/
33、10算法复杂性（续）算法复杂性（续）2024/8/10算法复杂性（续）算法复杂性（续）2024/8/10算法复杂性（续）算法复杂性（续）2024/8/10算法复杂性（续）算法复杂性（续）2024/8/10算法复杂性（续）算法复杂性（续）如果将模运算视为基本运算单位（即一次模运算花费一个时间单位），则算法的时间复杂度为2max(|a|,|b|)。 2024/8/10算法复杂性（续）算法复杂性（续）2024/8/10算法复杂性（续）算法复杂性（续）2024/8/10计算复杂性在信息安全中的应用计算复杂性在信息安全中的应用 l在信息安全中，很难界定一个密码体制是否是安在信息安全中，很难界定一个密码体
34、制是否是安全的。全的。l在经典密码学中，安全性的判定是基于信息论的。在经典密码学中，安全性的判定是基于信息论的。l信息论关注的是密文当中到底包含多少关于明文的信息。信息论关注的是密文当中到底包含多少关于明文的信息。l密文中关于明文的信息量越大，密码体制就越不安全。密文中关于明文的信息量越大，密码体制就越不安全。l而只有当密文中不包含关于明文的信息时，密码体制才而只有当密文中不包含关于明文的信息时，密码体制才是绝对安全的。是绝对安全的。l香农证明过这种完美的安全性只有当密钥跟明文长度相香农证明过这种完美的安全性只有当密钥跟明文长度相等时，才能达到。等时，才能达到。l这种安全性限制下的密码体制，其
35、应用是非常困这种安全性限制下的密码体制，其应用是非常困难。难。2024/8/10计算复杂性在信息安全中的应用（续）计算复杂性在信息安全中的应用（续） l在现代密码学当中，对安全性的判定是基于计算在现代密码学当中，对安全性的判定是基于计算复杂性的。复杂性的。l密文中是否包含明文的信息，这个问题对安全性来说并密文中是否包含明文的信息，这个问题对安全性来说并不重要。不重要。l关键是有没有有效的方法将密文中关于明文的信息提取关键是有没有有效的方法将密文中关于明文的信息提取出来。出来。l换句话说，基于计算复杂性的密码学所关心的不是密码分析者换句话说，基于计算复杂性的密码学所关心的不是密码分析者是否有可能
36、破译算法（实际上，除了一次一密外，所有的密码是否有可能破译算法（实际上，除了一次一密外，所有的密码体制都是有可能被破译），而是关心密码分析者是否具有相应体制都是有可能被破译），而是关心密码分析者是否具有相应的资源和时间来破译算法。的资源和时间来破译算法。2024/8/10计算复杂性在信息安全中的应用（续）计算复杂性在信息安全中的应用（续）l例如例如:l如果一个密码算法的破译只是一个如果一个密码算法的破译只是一个P类问题，这个算法类问题，这个算法当然会被认为是不安全。当然会被认为是不安全。l一个需要宇宙年龄那么长的时间才能破译的算法，当然一个需要宇宙年龄那么长的时间才能破译的算法，当然有理由认为
37、是安全的。有理由认为是安全的。2024/8/10计算复杂性在信息安全中的应用（续）计算复杂性在信息安全中的应用（续）l基于复杂性理论的现代密码学将基于复杂性理论的现代密码学将NPP作为一个必作为一个必要条件，加密算法中，拥有正确加密要条件，加密算法中，拥有正确加密/解密密钥的解密密钥的用户进行加密用户进行加密/解密是易处理的问题，而对于密码解密是易处理的问题，而对于密码攻击者或分析者，从密文中提取明文或不用正确攻击者或分析者，从密文中提取明文或不用正确的密钥构造合法的密文应该是一个难解的问题。的密钥构造合法的密文应该是一个难解的问题。l而很多加密算法是基于而很多加密算法是基于NP完全问题的，即
38、这类型的算完全问题的，即这类型的算法中，分析和破译是一个法中，分析和破译是一个NP完全问题。完全问题。l我们称之为我们称之为NPP猜想。猜想。2024/8/10计算复杂性在信息安全中的应用（续）计算复杂性在信息安全中的应用（续）l如果如果NPP，则分析和破译加密算法是一个多项，则分析和破译加密算法是一个多项式时间问题，即易处理的问题。那么这些加密算式时间问题，即易处理的问题。那么这些加密算法将失去其安全性。法将失去其安全性。l因此，如果这个猜想不正确，现在密码学将失去因此，如果这个猜想不正确，现在密码学将失去其一个至关重要的理论基础。其一个至关重要的理论基础。2024/8/10计算复杂性在信息
39、安全中的应用（续）计算复杂性在信息安全中的应用（续）l另一方面，即使另一方面，即使NPP猜想成立，基于猜想成立，基于NP完全问完全问题难解性的密码算法也不一定是安全的。题难解性的密码算法也不一定是安全的。l例如：例如：l基于基于NP完全的著名的完全的著名的背包问题背包问题破解就是一个反例。破解就是一个反例。l这是因为即使一个问题只有可以忽略的少数困难实例，这是因为即使一个问题只有可以忽略的少数困难实例，该问题也被认为是困难的。该问题也被认为是困难的。l相反，密码分析只要能破解不可忽略比例的实例，就认相反，密码分析只要能破解不可忽略比例的实例，就认为是成功的。为是成功的。l这就是为什么破解一个基
40、于这就是为什么破解一个基于NP完全问题的密码体完全问题的密码体制未必导致其基于的制未必导致其基于的NP完全问题的求解。完全问题的求解。2024/8/10计算复杂性在信息安全中的应用（续）计算复杂性在信息安全中的应用（续）l基于复杂性理论中的困难性作为现代密码学的安基于复杂性理论中的困难性作为现代密码学的安全性基础是不充分的全性基础是不充分的l近年来，密码学界广泛推崇一种被称为近年来，密码学界广泛推崇一种被称为可证明安可证明安全性全性的密码系统。的密码系统。l这种密码系统采用一种被称为这种密码系统采用一种被称为多项式规约技术多项式规约技术的形式化的形式化方法来证明一种密码体制的安全性。方法来证明
41、一种密码体制的安全性。l在多项式规约技术中，将对密码体制的攻击规约到求解在多项式规约技术中，将对密码体制的攻击规约到求解一类已知的一类已知的NP问题的一个实例。问题的一个实例。l这种方法证明如果这种密码体制是可破译的，则它所基这种方法证明如果这种密码体制是可破译的，则它所基于的于的NP问题实例是可解的。问题实例是可解的。2024/8/10计算复杂性在信息安全中的应用（续）计算复杂性在信息安全中的应用（续）l例如，最常用的多项式规约技术，就是将密码算例如，最常用的多项式规约技术，就是将密码算法的安全性规约到大整数分解困难性问题。法的安全性规约到大整数分解困难性问题。l由于人们广泛相信这种实例没有
42、有效的解法，所以对于由于人们广泛相信这种实例没有有效的解法，所以对于考虑中的密码体制的安全性，这样的一个证明提供了很考虑中的密码体制的安全性，这样的一个证明提供了很高的可信度。高的可信度。 2024/8/10教材与参考书教材与参考书l教材：教材：l李毅超李毅超 曹跃，网络与系统攻击技术曹跃，网络与系统攻击技术 电子科大出版社电子科大出版社 2007 l周世杰周世杰 陈伟陈伟 钟婷，网络与系统防御技术钟婷，网络与系统防御技术 电子科大出版社电子科大出版社 2007 l参考书参考书l阙喜戎阙喜戎 等等 编著，信息安全原理及应用，清华大学出版社编著，信息安全原理及应用，清华大学出版社lChristo
43、pher M.King, Curitis E.Dalton, T. Ertem Osmanoglu（常（常晓波等译）晓波等译）. 安全体系结构的设计、部署与操作，清华大学出版社，安全体系结构的设计、部署与操作，清华大学出版社，2003(Christopher M.King, et al, Security Architecture, design, deployment & Operations )lWilliam Stallings，密码编码学与网络安全原理与实践（第四版），密码编码学与网络安全原理与实践（第四版），电子工业出版社，电子工业出版社l蔡皖东，网络与信息安全，西北工业大学出版社，蔡皖东，网络与信息安全，西北工业大学出版社，2004l李建平，小波分析与信息处理李建平，小波分析与信息处理-理论、应用及软件实现，理论、应用及软件实现，1997年第年第一版，一版，2001年第二版，年第二版，2003年第二版修订版。年第二版修订版。l张世永，网络安全原理与应用，科学出版社，张世永，网络安全原理与应用，科学出版社，2003l杨义先等，杨义先等，信息安全理论与技术信息安全理论与技术，邮电出版社，邮电出版社2024/8/10Any Question?Q&A
