安徽工程大学 信息安全原理及应用 第3讲 密码学的复杂性理论基础

1、第3章 密码学的复杂性理论基础 1密码技术和算法复杂性 计算复杂性：研究密码分析对于计算量的需求和密码分析的困难程度 ，从而得出这些密码技术和算法在现有可行的条件下是否具有足够的安全性： 算法复杂性；问题复杂性。密码协议、方案和体制的安全性证明：零知识证明理论。问题（problem） 即需要回答的一般性提问:它通常含有若干个参数。对于一个问题进行描述应该包括两方面的内容：必须对问题的所有给定参数给出一般性描述；必须描述该问题的答案（或解）应该满足的性质。当问题的所有参数都有了确定的取值时，我们称得到了该问题的一个实例（instance）。 算法（algorithm） 即求解某个问题的一系列具体

2、步骤（通常被理解为求解所需的通用计算程序）。算法总是针对具体问题而言的，求解一个问题的算法通常不止一个。当某个算法能够回答一个问题的任何实例时，我们称该算法能够回答这个问题。当一个问题至少有一个能够回答该问题的算法时，我们称该问题可解（resolvable），否则称该问题不可解（unresolvable）。 算法复杂性 即度量该算法所需的计算能力 ，包括：时间复杂性T（time complexity）；空间复杂性S（space complexity）； 随机位数目；信道带宽；数据总量； 算法的复杂性通常用n的数量级表示。如果存在正常数k1, k2及N使得对一切nN有：k1h(n)f(n)k2h

3、(n) 则称f (n)与h (n)为同数量级的，记为f(n)=O(h(n)。容易证明，当f(n)是n的k次多项式时，则f(n)=O(nk)，即所有低阶项与常数项可忽略不计。多项式时间算法：f(n)=O(nk)指数时间算法：f(n)=O(h(n)(1)算法复杂性 算法复杂性 计算复杂性的表示符号为“ O ”（称为“大O ”），表示计算复杂性的数量级。 好处：使算法复杂性度量与处理器的运行速度和指令运行时间无关； 明确地揭示了输入的数据长度对算法复杂性的影响。 算法复杂性算法的分类及其运行时间 运算次数宇宙年龄的问题复杂性 研究问题的内在复杂性，即在图灵机上解决最难的问题实例所需的最小时间和空间条

4、件。 图灵机是一种具有无限读写存储带的有限状态机，可以被当作一个实际可用的计算模型 。确定性图灵机。 非确定性图灵机：能够进行猜测。求解一个问题分两个阶段：猜测阶段和验证阶段。 问题分类易处理的（tractable） ：确定性图灵机上能够在多项式时间内得到处理的问题。称易处理问题的全体为“多项式时间可解类”，记为P。 非确定性图灵机上能够在多项式时间内得到处理的问题被称为“非确定性多项式时间可解问题”，简称NP问题。NP问题的全体被称为“非确定性多项式时间可解类”，记为NP。NP问题 意义：能够通过非确定性的多项式时间算法对许多对称密钥算法和所有公钥算法进行攻击。 NP完全问题：指NP中的任何

5、一个问题都可以通过多项式时间转化为该问题 。NP完全问题的全体被记为NPC 。NP完全问题是NP问题中最难的问题。 不确定型图灵机工作分猜测与验证2个阶段，所谓一个问题在不确定型图灵机上可用多项式时间解决，是指若图灵机猜测一个解，则它可以在多项式时间内验证(不是求出)此解正确与否。例：背包问题：一种组合优化的NP完全问题。 给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高 给定n个整数的集合A和一个整数N，决定是否存在一个子集S，使得S中的所有数之和为N。解：因为对于一个给定的子集S，可在多项式时间内验证其和是否为N。然而要找A的一个子集S使

6、其和等于N，其时间复杂性T=O(2n) ，这是因为A共有2n个不同的子集。NP问题 零知识证明 证明者能够在不向验证者提供任何有用的信息的情况下，使验证者相信某个论断是正确的。实质上是一种涉及两方或更多方的协议，即两方或更多方完成一项任务所需采取的一系列步骤。 零知识“洞穴”零知识“洞穴” （1）V站在A处； （2）P走进洞穴，到达C处或D处；（3）当P消失在洞穴中时，V走到B处；（4）V呼叫P，要求P：（a）从左通道出来；或者（b）从右通道出来；（5）P答应V的呼叫，并在有必要的情况下用咒语打开C与D之间的秘密之门；（6）重复步骤（1）（5）次。 基本的零知识协议过程假设P知道一部分信息，并且该信息是一个难题的解法 ：（1）P用自己的信息和一个随机数将这个难题转变为与之同构的新难题，然后用自己的信息和这个随机数这个新难题；（2）P利用位承诺方案提交对于这个新难题的解法；（3）P向V透漏这个新难题，V无法通过