文章目录

• 复杂性理论基本概念
• • 问题(problem)
  • 算法
  • 算法复杂性
  • 算法分类
  • 问题复杂性
  • • 图灵机
    • 图灵机分类
    • 问题复杂性
    • • P问题
      • NP问题
      • NP完全问题(NPC问题)
      • 总结
• 密码学复杂性理论假设
• • 单向函数(OWF)
  • 伪随机生成器(PRG)
  • • 真随机数生成
    • 伪随机数生成器(PRG)
    • • 构造伪随机生成器
      • 测试伪随机性的方法
  • 单向函数与伪随机生成器的关系
  • 总结

复杂性理论基本概念

问题(problem)

  ①需要回答的一般性提问

  ②含有若干未定参数：

   如果给问题的所有参数指定了具体值，就得到该问题的一个实例。

算法

 ①求解某一个问题的一系列具体步骤。

  例如：高斯消元法、欧几里得算法

 ②如果一个算法可以解决一个问题的任何一个实例，则这个算法可以解答这个问题。

 ③如果针对一个问题，至少存在一个算法可解答这个问题，则这个问题是可解的(resolvable)；否则，是不可解的(unresolvable)。例如：停机问题、希尔伯特第十问题。

算法复杂性

 ①一般由算法所需求的**最大时间(T)和存储空间(S)**度量。

 ②同一问题，不同规模，时间与空间上存在差异。

  时间与空间表示成实例的规模n的函数

 ③符号"大O"(Big O)

 ④用数量级度量复杂度的优点：

  刻画时间与空间的需求受输入长度变化的影响；

  与所用处理系统无关

算法分类

 ①多项式时间算法：O(n^t)：其中t为常数，n为输入规模。

 ②指数时间算法：O(t^h(n))：其中h(n)为多项式。

 ③当h(n)大于常数而低于线性函数时，称为超多项式时间算法。

 ④多项式时间算法可认为是有效的。

问题复杂性

图灵机

 ①一条无限长的纸带TAPE。纸带被划分为一个接一个的小格子，每个格子上包含一个来自有限字母表的符号。

 ②一个读写头HEAD。该读写头可以在纸带上左右移动，它能读出当前所指的格子上的符号，并能改变当前格子上的符号。

 ③一套控制规则TABLE。它根据当前机器所处的状态以及当前读写头所指的格子上的符号来确定读写头下一步的动作，并改变状态寄存器的值，令机器进入一个新的状态。

 ④一个状态寄存器。它用来保存图灵机当前所处的状态。图灵机的所有可能状态的数目是有限的，并且有一个特殊的状态，称为停机状态。

图灵机分类

 ①确定型图灵机(DTM)：每一步操作结果的唯一确定的；

 ②非确定型图灵机(NTM)：每一步的操作及结果不是唯一的，可能是多种选择；

问题复杂性

 一个问题的复杂性由在图灵机上解决此问题的最难的实例所需的最小的时间和空间决定。

P问题

 确定型图灵机上可用多项式时间可解的问题，称为易处理的。易处理问题的全体称为确定性多项式时间可解类。

 补充：在确定型图灵机上不能用多项式时间系统地解出的问题，称为难处理的。

NP问题

 在非确定型图灵机上可用多项式时间可解的问题，称为非确定性多项式时间可解问题。

 ①NP问题的全体称为非确定性多项式时间可解类，记为NP。

 ②求解过程：猜测、验证

 ③所谓可解指的是，若机器猜测一个解，可在多项式时间内验证其正确性。

例如：背包问题(子集合问题)、可满足问题

NP完全问题(NPC问题)

 一个问题是NP完全的，如果NP中的任何一个问题都是可以在多项式时间内转化为该问题。

 ①NP完全问题是NP中**"最难"的问题**

总结

P类问题：能在多项式时间内可解的问题；

NP类问题：在多项式时间内“可验证”的问题。也就是说，不能判定这个问题到底有没有解，而是猜出一个解来在多项式时间内证明这个解是否正确。

NPC问题：存在这样一个NP问题，所有的NP问题都可以约化成它。换句话说，只要解决了这个问题，那么所有的NP问题都解决了。

P问题属于NP问题，但不等于

密码学复杂性理论假设

单向函数(OWF)

伪随机生成器(PRG)

随机性：均匀、独立、不可预测

真随机数生成

 一般通过测量不可预测的物理过程实现：电离辐射的脉冲检测

 缺点：效率低、成本高

伪随机数生成器(PRG)

 确定性算法，输入固定长度的真随机数(种子)，输出任意长度的字符串，且输出字符串的分布与均匀分布计算上不可区分。但并不能增加熵。

构造伪随机生成器

利用流密码、分组密码、Hash函数、公钥密码等

测试伪随机性的方法

 ①统计测试(必要不充分条件)

  16项检测：频率测试、序列测试、游程测试、自相关测试等

 ②可证明安全的伪随机生成器：基于数学困难问题的构造

  Blun-Micali伪随机数生成器：

  安全性基于破译RSA体制的困难性：

  二次剩余生成器：

单向函数与伪随机生成器的关系

 ①利用单向函数可构造伪随机生成器

 ②利用**伪随机函数(PRF)**构造安全MAC

总结

总结

以上是生活随笔为你收集整理的[密码学] 复杂性理论基础的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。