《数学理论复杂性》PPT课件.ppt

2020 3 31 北京师范大学数学学院杨进goodskyfly 网络与信息安全 2020 3 31 问题复杂性 第2章信息安全数学基础 计算复杂性 算法复杂性 2020 3 31 问题复杂性 第2章信息安全数学基础 计算复杂性 算法复杂性 2020 3 31 为什么要学习计算复杂性 计算复杂性是研究密码分析对于计算量的需求和密码分析的困难程度 从而得出这些密码技术和算法在现有可行的条件下是否具有足够的安全性 学习计算复杂性 需要掌握两个概念 问题算法 计算复杂性 2020 3 31 问题 problem 问题 定义 即需要回答的一般性提问 它通常含有若干个参数 对于一个问题进行描述应该包括两方面的内容 必须对问题的所有给定参数给出一般性描述 必须描述该问题的答案 或解 应该满足的性质 当问题的所有参数都有了确定的取值时 我们称得到了该问题的一个实例 instance 2020 3 31 算法 algorithm 定义 算法 即求解某个问题的一系列具体步骤 通常被理解为求解所需的通用计算程序 算法总是针对具体问题而言的 求解一个问题的算法通常不止一个 当某个算法能够回答一个问题的任何实例时 我们称该算法能够回答这个问题 当一个问题至少有一个能够回答该问题的算法时 我们称该问题可解 resolvable 否则称该问题不可解 unresolvable 2020 3 31 算法 algorithm 续 有关算法的几点注释 算法总有输入和输出算法输入大小一般用输入变量的长度 单位为位 来表示一般来说 算法用某种编程语言来实现的计算机程序一般来说 我们仅仅关注解决问题最有效的算法 2020 3 31 问题与算法 问题 如何求解两个整数a和b的最大公约数 参数 a和b问题实例 a 20 b 30算法 利用因子分解求a 20和b 30的最大公约数a 2 2 5b 2 3 5因此a和b的最大公约数是2 5 10 2020 3 31 算法复杂性 算法复杂度 定义 即度量该算法所需的计算能力 包括 时间复杂性T timecomplexity 空间复杂性S spacecomplexity 信道带宽 数据总量 2020 3 31 算法复杂性 续 计算复杂性的表示符号为 O 称为 大O 即算法的阶号 表示计算复杂性的数量级好处 使算法复杂性度量与处理器的运行速度和指令运行时间无关 明确地揭示了输入的数据长度对算法复杂性的影响 2020 3 31 算法复杂性 续 算法常见复杂性分类 1 常数算法 constantAlgorithm 如果运行时间是O 1 即该算法的复杂性不依赖于n 2 线性算法 linearAlgorithm 如果运行时间是O n 3 多项式算法 polynomialAlgorithm 如果运行时间是O nm 其中m是一个常数 具有多项式复杂性的算法族被称为多项式时间算法 4 超多项式算法 superpolynomialAlgorithm 如果运行时间是 其中c是一个常数 而s n 是关于n的大于常数而小于线性的函数 5 指数算法 exponentialAlgorithm 如果运行时间是 其中t是大于1的常数 f n 是关于n的多项式函数 2020 3 31 算法复杂性 续 算法常见复杂性分类一般而言 常数算法 线性算法 多项式算法和超多项式算法统称为多项式算法 所谓多项式 就是具有下列形式的一个函数 其中 k和ck是常数 且ci称 0为 当k 0时 k称为多项式的次数 ci称为多项式的系数 2020 3 31 算法复杂性 算法的分类及其运行时间 算法复杂性 续 2020 3 31 算法复杂性 算法复杂度的增长速度 算法复杂性 续 亚指数 指数 多项式 2020 3 31 算法复杂性 续 研究问题的内在复杂性 即在图灵机上解决最难的问题实例所需的最小时间和空间条件 图灵机是一种具有无限读 写存储带的有限状态机 可以被当作一个实际可用的计算模型 2020 3 31 问题复杂性 第2章信息安全数学基础 计算复杂性 算法复杂性 2020 3 31 问题复杂性 图灵机分为两类 确定性图灵机 非确定性图灵机 2020 3 31 问题复杂性 续 确定性图灵机 确定性图灵机的输出结果只取决于输入和初始状态 因此 对于具有相同输入和初始状态 运行一个确定性图灵机所得到的结果是完全相同的 非确定性图灵机 能够进行猜测 求解一个问题分两个阶段 猜测阶段和验证阶段 2020 3 31 图灵机 图灵机包括一个有限状态控制单元 k 1 条纸带 Tape 和k个读写头 Tapehead 有限状态控制单元控制每个读写头访问一条纸带 并沿着纸带左右移动图灵机求解问题的输入是一个有限长度的字符串 该输入占据每条纸带无限个单元的最左边的有限个单元 读写头对纸带的一次访问称之为一个合法移动 Move 2020 3 31 图灵机 续 图灵机求解问题时 被赋予一个初始状态 InitialState 且一步一步地移动 从而完成对输入的扫描 如果图灵机最终扫描了整个输入串 且满足了中止条件而停止下来 则称图灵机识别了该输入 否则 图灵机在某一点没有合法移动 因此会没有识别输入串而停止下来 此时称图灵机无法识别该输入 图灵机所识别的一个输入 称为一种可识别语言的一个实例 2020 3 31 图灵机 续 例如 请设计一个图灵机 用于证明某个非负整数是否能被3整除 2020 3 31 图灵机 续 例如 请设计一个图灵机 用于证明某个非负整数是否能被3整除 2020 3 31 图灵机 续 例如 请设计一个图灵机 用于证明某个非负整数是否能被3整除 2020 3 31 图灵机 续 例如 请设计一个图灵机 用于证明某个非负整数是否能被3整除 2020 3 31 图灵机 续 例如 请设计一个图灵机 用于证明某个非负整数是否能被3整除 2020 3 31 图灵机 续 例如 请设计一个图灵机 用于证明某个非负整数是否能被3整除 2020 3 31 图灵机 续 例如 请设计一个图灵机 用于证明某个非负整数是否能被3整除 2020 3 31 图灵机 续 例如 请设计一个图灵机 用于证明某个非负整数是否能被3整除 2020 3 31 图灵机 续 例如 请设计一个图灵机 用于证明某个非负整数是否能被3整除 2020 3 31 图灵机 续 例如 请用DIV3图灵机证明a 12 二进制1100 能被3整除 2020 3 31 图灵机 续 例如 请用DIV3图灵机证明a 12 二进制1011 能被3整除 2020 3 31 图灵机 续 例如 请用DIV3图灵机证明a 12 二进制1011 能被3整除 2020 3 31 图灵机 续 例如 请用DIV3图灵机证明a 12 二进制1011 能被3整除 2020 3 31 图灵机 续 例如 请用DIV3图灵机证明a 12 二进制1011 能被3整除 2020 3 31 图灵机 续 例如 请用DIV3图灵机证明a 12 二进制1011 能被3整除 2020 3 31 图灵机 续 例如 请用DIV3图灵机证明a 12 二进制1011 能被3整除 2020 3 31 图灵机 续 例如 请用DIV3图灵机证明a 13 二进制1101 不能被3整除 2020 3 31 图灵机 续 例如 请用DIV3图灵机证明a 13 二进制1101 被3整除 2020 3 31 图灵机 续 例如 请用DIV3图灵机证明a 13 二进制1101 被3整除 2020 3 31 图灵机 续 例如 请用DIV3图灵机证明a 13 二进制1101 被3整除 2020 3 31 图灵机 续 例如 请用DIV3图灵机证明a 13 二进制1101 被3整除 2020 3 31 图灵机 续 例如 请用DIV3图灵机证明a 13 二进制1101 被3整除 2020 3 31 图灵机 续 例如 请用DIV3图灵机证明a 13 二进制1101 被3整除 2020 3 31 问题复杂性 借助于图灵机理论 问题复杂型实际上就是在图灵机上解决最难的问题实例所需要的最小时间最小空间 2020 3 31 图灵机 续 图灵机M识别一个长度为n的输入串而移动的步数称为图灵机的时间复杂性 记为 当图灵机M识别一个长度为n的输入串 其写操作中读写头所访问的纸带单元数称为图灵机的空间复杂性 记为 2020 3 31 图灵机 续 2020 3 31 问题分类 如果一个问题在确定性图灵机上能够在多项式时间内得到处理 则称该问题时易处理的 tractable 也既是说 能够用多项式时间解决的问题称之为易处理的 不能够在多项式时间内解决的问题是难处理的 因为随着输入尺寸的增加 求解这类问题需要的时间迅速变得很长 以至于不可能有效的求解 难处理的问题也被称为是难解的 2020 3 31 P类问题 易处理问题的全体称为 多项式时间可解类 记为P类 复杂度类P包含所有能用多项式时间解决的问题 上述定义表明 如果L是多项式时间内可识别的语言 则确定性图灵机可以在多项式时间内 判定一个字符串是否属于语言L 2020 3 31 NP类问题 有这样一类问题 虽然不能够用确定性图灵机来有效求解 但是却可以用非确定性图灵机在多项式时间内得到处理这类问题称为 非确定性多项式时间可解问题 简称NP问题 定义 NP类 NP类表示用非确定性图灵机在多项式时间内可以识别的语言类 2020 3 31 NP类问题 续 意义 能够通过非确定性的多项式时间算法对许多对称密钥算法和所有公钥算法进行攻击 NP完全问题 指NP中的任何一个问题都可以通过多项式时间转化为该问题 NP完全问题的全体被记为NPC NP完全问题是NP问题中最难的问题 定义2 3 3 NP完全类 如果任意 是非确定性多项式时间完全的 NP完全的 都可以多项式规约到语言 则称 2020 3 31 NP类问题 续 NP中的任何一个问题都可以通过多项式时间转化为该问题 NP完全问题的全体被记为NPC NP完全问题是NP问题中最难的问题 2020 3 31 算法复杂性 算法时间复杂度的度量方法图灵机解决问题所移动的步数 该时间称之为算法的运行时间 该度量方法的缺点 没有考虑每一步具体的操作例如 加法和乘法的计算开销是不同的为此 引入算法 按位 的计算复杂度度量方法 考虑操作如果按位进行所需要执行的 步数 2020 3 31 算法复杂性 续 2020 3 31 算法复杂性 续 2020 3 31 算法复杂性 续 2020 3 31 算法复杂性 普通代数运算 2020 3 31 算法复杂性 模运算 2020 3 31 算法复杂性 有限域 2020 3 31 算法复杂性 续 2020 3 31 算法复杂性 续 2020 3 31 算法复杂性 续 2020 3 31 算法复杂性 续 2020 3 31 算法复杂性 续 2020 3 31 算法复杂性 续 2020 3 31 算法复杂性 续 2020 3 31 算法复杂性 续 2020 3 31 算法复杂性 续 如果将模运算视为基本运算单位 即一次模运算花费一个时间单位 则算法的时间复杂度为2max a b 2020 3 31 算法复杂性 续 2020 3 31 算法复杂性 续 2020 3 31 计算复杂性在信息安全中的应用 在信息安全中 很难界定一个密码体制是否是安全的 在经典密码学中 安全性的判定是基于信息论的 信息论关注的是密文当中到底包含多少关于明文的信息 密文中关于明文的信息量越大 密码体制就越不安全 而只有当密文中不包含关于明文的信息时 密码体制才是绝对安全的 香农证明过这种完美的安全性只有当密钥跟明文长度相等时 才能达到 这种安全性限制下的密码体制 其应用是非常困难 2020 3 31 计算复杂性在信息安全中的应用 续 在现代密码学当中 对安全性的判定是基于计算复杂性的 密文中是否包含明文的信息 这个问题对安全性来说并不重要 关键是有没有有效的方法将密文中关于明文的信息提取出来 换句话说 基于计算复杂性的密码学所关心的不是密码分析者是否有可能破译算法 实际上 除了一次一密外 所有的密码体制都是有可能被破译 而是关心密码分析者是否具有相应的资源和时间来破译算法 2020 3 31 计算复杂性在信息安全中的应用 续 例如 如果一个密码算法的破译只是一个P类问题 这个算法当然会被认为是不安全 一个需要宇宙年龄那么长的时间才能破译的算法 当然有理由认为是安全的 2020 3 31 计算复杂性在信息安全中的应用 续 基于复杂性理论的现代密码学将NP P作为一个必要条件 加密算法中 拥有正确加密 解密密钥的用户进行加密 解密是易处理的问题 而对于密码攻击者或分析者 从密文中提取明文或不用正确的密钥构造合法的密文应该是一个难解的问题 而很多加密算法是基于NP完全问题的 即这类型的算法中 分析和破译是一个NP完全问题 我们称之为NP P猜想 2020 3 31 计算复杂性在信息安全中的应用 续 如果NP P 则分析和破译加密算法是一个多项式时间问题 即易处理的问题 那么这些加密算法将失去其安全性 因此 如果这个猜想不正确 现在密码学将失去其一个至关重要的理论基础 2020 3 31 计算复杂性在信息安全中的应用 续 另一方面 即使NP P猜想成立 基于NP完全问题难解性的密码算法也不一定是安全的 例如 基于NP完全的著名的背包问题破解就是一个反例 这是因为即使一个问题只有可以忽略的少数困难实例 该问题也被认为是困难的 相反 密码分析只要能破解不可忽略比例的实例 就认为是成功的 这就是为什么破解一个基于NP完全问题的密码体制未必导致其基于的NP完全问题的求解 2020 3 31 计算复杂性在信息安全中的应用 续 基于复杂性理论中的困难性作为现代密码学的安全性基础是不充分的近年来 密码学界广泛推崇一种被称为可证明安全性的密码系统 这种密码系统采用一种被称为多项式规约技术的形式化方法来证明一种密码体制的安全性 在多项式规约技术中