公钥密码体制的研究 (2)

第二章预备知识第二章预备知识数学理论是现代密码学建立和发展的基础，包括复杂性理论、可证明安全理论等，这些理论中的许多概念在设计密码算法时是必不可少的。本章主要介绍本本文中可能会用到的一些基本概念和结论，并介绍公钥密码体制以及代理重加密体制的相关定义。最后，本章讨论了密码系统中存在的密钥泄露问题。2.1复杂性理论在计算机中，某一个算法执行的时间是以比特运算的形式来测量的。为完成某一个算法而需要的必要的比特运算数量，称为这个算法的计算复杂性或简称复杂性。它确切定义了求解一个问题是计算“容易”还是“困难”的，并由此对问题和算法的复杂性加以分类。由于算法的计算复杂性是正整数的函数，因此要比较两个算法的计算复杂性主要是比较当x充分大时，它们随x增大而增大的数量级。定义2.1令函数以及，如果∃是正整数，且c是常数，有时，则将记作，或简写为。是对算法复杂性的一个数量级分类，它表示算法所需的比特运算次数的上界，与计算机的操作时间，运行速度等固有的性质无关。在复杂性的分析过程中，我们需要知道执行某个算法的确切的比特运算次数。计算机执行某个算法所需的时间，是和比特元素的数量成正比的。这个比例常数和计算机的性能有关。在执行一个算法的过程中，基本的时间估计是多项式时间的，或简称多项式的。一般来说，由于这些算法是最快的算法，因此它们都是可取的，即多项式时间算法是有效的算法。多项式时间算法是对基本的加、减、乘、除运算而言的算法。然而，有些算法的复杂性是，其中，c为常数且f是一个关于的多项式，即为指数时间算法，或简称为指数的。一个亚指数时间算法是，其中，，，c为常数表示满足的函数。假设输入算法的最大比特长度为，则，这是指数时间算法。超多项式时间算法的概念为若一个算法的复杂性为，其中c为常数，是介于常数和线性函数之间的函数。对现在已知的密码体制有效的攻击算法都是超多项式时间算法，但是并没有证明不存在有效的多项式时间攻击算法。下面给出关于的一些性质：假定f和g是正多项式，则有(1)若，则有；(2)；(3)。证明：（1）若，则有常数和正整数，若，。因此，，可得，即。（2）令，，则存在和正整数，使得当时，，。因此，，，故可得。（3）令，，则存在和正整数，使得当时，，。因此，，即。上述性质中的（1）是（3）在下的特殊情况。同样，如果，则对任意的，成立。计算复杂性是计算机科学的重要组成部分，同时也是密码学的理论基础之一。Shannon曾指出，设计一个密码的本质上要寻找一个难解的问题。这一推断揭示了密码的安全性与计算复杂性之间的相互依赖关系。公钥密码的出现，开拓了直接利用NPC问题设计密码的技术路线。在当今的计算机网络时代，密码的编制和分析都利用计算机网络来进行。在这种情况下，计算复杂性理论的发展将直接影响到密码的安全，计算复杂性理论作为密码的一种理论基础将发挥越来越大的作用。2.2可证明安全理论本小节将列出本文可能涉及的各类困难问题，如无特殊说明，均假设这些问题是难解的，并称为对应的困难问题假设。然后，介绍形式化证明方法。2.2.1困难问题假设群：S是一个非空集合，表示异或操作，表示一个群，如果(1)闭包：；(2)结合性：；(3)恒等性：；(4)反身性：。阶：一个群中元素的个数称为阶。循环群：令为阶为q的群，各不相同，则称为循环群，g为群的生成元。定义2.2对任意已知元素，有，求整数，即为DL(Discrete第二章预备知识Logarithm)难解问题。离散对数假设意味着在群上的离散对数困难问题不能够被敌手以不可忽略的概率解决。定义2.3令为一个阶为q循环乘法群，群上的CDH（ComputationalDiffie-Hellman）问题是已知二元组（未知），求解。设在时间t内敌手成功输出的概率为：，其中是可忽略的。如果可忽略不计，则CDH问题是是难解的。定义2.4令为一个阶为q循环群，已知，其中不可知，判断输出与是否一致，即为DDH（DecisionalDiffie-Hellman）难解问题。定义2.5令为一个阶为q循环群，已知，求解，即s-CDH（s-ComputationalDiffie-Hellman）难解问题，其中是在中随机选择的。特别地，当s=2时，称s-CDH问题称为平方-CDH问题。定义2.6令为一个阶为q循环群，已知，其中是不可知的，P-CDH问题意味着计算是困难的。定义2.7令为一个阶为q循环群，已知，其中是不可知的，P-DDH问题意味着判断是否成立是困难的。定义2.8如果映射满足如下性质，则认为该映射是一个双线性映射（BilinearMap）：(1)都代表群，且具有相同的素数阶q；(2)对所有的，，等式成立；(3)该映射是非退化的，即；(4)映射e是高效可计算的。一般地，Weil对错误!未找到引用源。和Tate对错误!未找到引用源。可被用于构建双线性映射e。定义2.9令为循环加法群，阶为q，生成元为P，已知，其中是不可知的，求解，即中的CDH问题。定义2.10令为循环加法群，阶为q，生成元为P，已知，其中是不可知的，然后判定等式是否满足，即中的DDH问题。定义2.11令为循环加法群，阶为q，生成元为P，在DDHOracle的协助下，计算已知元组的CDH难题，即GDH（gapDiffie-Hellman）问题。定义2.12令为循环加法群，阶为q，生成元为P，已知，求解，即q-SDH（q-strongDiffie-Hellman）问题。令、分别是阶为q的循环加/乘法群，双线性映射以及群生成元为P：定义2.13已知，其中是不可知的，求解，即BDH（BilinearDiffie-Hellman）问题。定义2.14已知，，其中是不可知的，判定等式是否成立，即DBDH（DecisionalBilinearDiffie-Hellman）问题。定义2.15在DBDH预言机的协助下，求解给定的BDH问题，即GBDH问题。2.2.2形式化证明方法在可证明安全理论中，形式化安全模型被用来评估一个密码系统的安全性。一个形式化的安全模型包含两个定义错误!未找到引用源。错误!未找到引用源。：一方面，它必须指出任意概率的敌手如何与密码系统中的合法用户进行多项式时间的应答/响应；另一方面，它必须说明该攻击者要达到哪些目的，才能认定该密码系统被攻破。一般来说，有两种方式来描述形式化的安全模型。一种是基于游戏（game-based）的方式。在这种形式化安全模型中，攻击者需要与一个假定的概率算法（挑战者）进行交互。挑战者初始化密码系统中使用的全部密钥，可能响应来自攻击者的询问。当攻击者终止时，游戏结束，然后，评估此时的攻击者是否具备破坏该密码系统的能力。如果一个密码系统是安全的，那么我们必须给出说明任意一个攻击者能够弱化该密码系统的可能性都非常小。基于游戏的安全模型已经被广泛接受，且已被应用于多种类型的密码系统的安全性证明，包括数字签名、非对称加密和对称加密。本文所描述的形式化安全模型都是基于游戏的安全模型。基于游戏的安全模型的优点是容易理解和实现。然而，Canetti等错误!未找到引用源。发现基于游戏安全模型下的安全性证明只能独立的证明密码系统的安全性，无法说明当该密码系统部署于复杂环境下时也是可证明安全的。大部分密码方案都不是独立存在的，而是作为大型计算机系统的子程序。在这种情况下，为了确保所使用的密码算法的安全性，必须要在给定的复杂环境下进行安全性证明。因此，对于基于游戏的安全模型而言，它往往难以更好的表述大型复杂环境的安全需求。另一种是基于仿真(simulation-based)的方式。假设一个密码系统中一个任意概第二章预备知识率的攻击者能够与该密码系统中的每个算法进行多项式时间的交互，并且其它各方也可能多项式时间的访问密码系统的算法。我们假设存在一个理想化的密码系统，该密码系统永远都不会被攻破。它不是一个实际的系统，通常会涉及到使用一个抽象的可信第三方来确保数据被安全的传输，并且该可信第三方所进行的操作对攻击者和其它各方而言是透明的。为了判断一个密码方案是否安全，攻击者和其它各方需要分别与真实的密码系统和理想化的密码系统进行多项式时间的交互，然后，检查攻击者和其它各方的输出。由于理想化的密码系统不可能被攻破，如果在真实密码系统下攻击者和其它各方的输出与在理想化密码系统下的输出结果大致相同，那么这一真实的密码系统是可证明安全的。因此，我们认为一个密码系统是安全的，当且仅当上面两种输出是不可区分的或者可区分的概率极小。应该明确，基于仿真的安全模型比基于游戏的安全模型更强。特别地，基于仿真的安全模型提供的安全性证明考虑到了部署于复杂环境下密码系统，为该密码系统提供了更可靠的安全保障。目前，一些基于仿真的安全模型被广泛使用错误!未找到引用源。。然而，已被证明，某些密码函数无法在基于仿真的安全模型下可证明安全错误!未找到引用源。错误!未找到引用源。。显示一个密码体制安全的现代方法是可证明安全性。可证明安全性的目的在于证明：如果一个敌手能够攻破一个密码体制的某个安全概念，那么就可以利用该敌手解决某个工人的数学困难问题。例如，如果一个敌手能够在选择密文攻击下攻破RSA的语义安全性，那么就可以利用该敌手分解大整数；可证明安全的思想就是给定一个算法A，提出一个新算法C，C把A作为子程序。输入给C的是希望解决的困难问题，输入给A的是某个密码算法。然而，如果A是一个积极攻击敌手（选择密文攻击敌手或者适应性选择密文攻击敌手），即A可以对输入公钥进行解密预言机询问或签名预言机询问。算法C要想使用A作为子程序，就得对A的询问提供回答。算法C需要应对以下四个问题：为了回避这个问题，可以使用随机预言机模型。随机预言是一个理想的Hash函数。对于每一个新的询问，随机预言产生一个随机值作为回答，如果问相同的询问两次，那么回答仍然相同。在随机预言机模型中，假设敌手并不使用密码算法中定义的那个Hash函数。也就是所，即使将随机预言换成真实的Hash函数。敌手A也是成功的。对于A的解密预言询问或者签名预言询问，算法C是通过欺骗随机预言的回答来适合自己的需要的。随机预言模型为证明密码体制的安全性提供了一个很好的方法，但是随机预言模型并不反映真实世界的计算。在随机预言模型下安全的密码体制只能说是可能在真实的世界是安全的，不能确保一定在真实的世界是安全的。文献给出了在随机预言模型下安全的密码体制在真实的世界中不安全的例子。许多密码学研究者开始设计在标准模型（不依赖于随机预言模型）下安全的密码体制。移除随机预言模型是需要代价的，通常需要更强的困难问题假设，而且在标准模型下的密码体制通常效率较低。2.3公钥密码体制在对称密码体制中，或者与相同，或者可以容易地从中导出。从而，或者的泄露会导致系统的不安全。公钥密码体制错误!未找到引用源。（PublicKeyCryptography，PKC）的提出在整个密码学发展历史中具有里程碑式的意义。在公钥密码体制中，可以扎到一个密码体制，使得由给定的来求是计算不可行的。PKC的优势为通信发送发能够用通信接收方的公钥加密明文消息并发送给接收方，然后，接收方用其私钥解密。2.3.1PKE定义定义2.16公钥加密方案（PublicKeyEncryption，PKE）.一个PKE方案由概率算法、、组成:(1)密钥生成算法：输入，输出，记为；(2)加密算法：输入及，输出密文，记为；(3)解密算法：输入c以及sk，输出m或符号，表示解密失败，记为。对于每一个n，输出的每一组密钥对，以及每一个明文m，等式总是成立。2.3.2PKE安全性对于任一公钥加密方案（KeyGen，Enc，Dec），其安全性依赖于攻击者的能力。针对一个PKE方案的主动攻击有以下三种方式，这些方式被用于分析密码系统的安全性。定义2.17选择明文攻击（）已知一个加密预言机，敌手任意选取消息，并询问加密预言机，从而产生对应密文。当结束询问预言机后，敌手的目标是基于已经掌握的明-密文对破坏密码系统的安全性。定义2.18选择密文攻击（）选择密文攻击也称为午餐时间攻击，是一种比选择明文攻击稍强的攻击模型。在选择密文攻击中，敌手