密码学假设.doc

可证明安全性理论信息安全是信息社会赖以生存的根基，现代密码学是信息安全技术的核心，它建立在保证合法用户算法的有效性和敌手恢复被保护信息的不可行性之间的鸿沟之上，引入了计算复杂度理论，将攻破的“不可能性”转化为“不可行性”，因此也有人称之为复杂度理论密码学。可证明安全性正是基于计算“不可行性”构建起来的理论，它将密码学方案的安全性归约为公认的计算难题，不仅是一种证明方法，也是一种设计协议的方法。它使密码学从一门艺术变成为一门科学，并且也成为现代密码学领域中理论工作的主线。特别是人们对国际密码标准进行大量分析之后，越来越意识到可证明安全性的重要性，可证明安全性也已成为任何一个密码协议的基本要求。它对密码学的影响重大，并且对密码学实践也有重要的意义。目前多数密码体制的设计采取的做法是：提出一种方案后，基于某种假设对方案做出具体的安全性分析，然后给出其安全性论断，如果该方案在较长时间内不能被破解，大家就广泛接受其安全性论断;如果在一段时间后发现安全漏洞，就对方案再作必要的修改，然后继续使用。这种做法让人们对方案的安全性增加了不可靠感，而且从根本上难以避免受到新技术的分析和攻击.可证明安全性理论就是针对上述问题而提出的一种解决方案，可证明安全可理解为密码方案或协议的安全性可以被证明，换一句说，可证明安全理论的目的是要构建一种可以被证明是安全的体制，它能防止一些未知攻击。安全性是可以证明的思想最初是由Goldwasser和Micali提出，他们将概率引入了密码学，强调多项式时间和可忽略的成功概率等。随着对可证明安全性的进一步研究，密码学界意识到它不但对密码学的理论影响重大，且对密码学实践也有重要的意义，目前已成为了国内外密码学界最为关注的问题之一，同时可证明安全性也己成为了设计密码协议的公认要求。可证明安全性理论是一种归约方法，它通过定义适当的安全目标(一般地，加密方案的安全目标是保密性，签名方案的安全目标是不可伪造性)，然后在一定的敌手模型下证明方案或协议能够达到既定的安全目标。它的基本思路是:由于公钥密码体制的安全性是基于某种计算复杂性假设(基础难解问题假设)的，如果存在方案的攻击敌手(算法)A，就可以利用算法A构造出攻破基础难解问题的算法B，但基于计算复杂性假设，这样的算法是不存在的。也就是说，可以通过将算法风多项式归约为算法B来实现方案的安全性证明。1计算复杂性与密码学的安全性计算复杂性理论是公钥密码学的基础，几个与此相关的几个概念：多项式时间算法：时间复杂性为O(nk)的算法，其中k为常数，n为问题规模。指数时间算法：时间复杂性为O(nk)的算法，其中t为常数，h(n)是多项式。多项式时间归约:对于两个问题X和Y，用T(X)和T(Y)均表示它们的时间复杂度。如果T(Y)=f(T(X)，其中f是一个多项式函数，则称Y可以在多项式时间内归约到X。记为Y=pX。P问题：指所有可以在多项式时间内求解的问题，或者说在确定的图灵机上用多项式时间可解的问题。NP问题：指所有可以在多项式时间内验证的问题，或者说在非确定的图灵机上用多项式时间可解的问题。NP难问题:如果对于某个问题X和任意NP问题Y，如果Y=pX，则称X是NP难的问题。通俗地讲X至少和Y一样难。NP完全问题：对于某个问题X，如果NP类中每个问题都可以在多项式时间内归约到X，则称X是NP完全问题。NP完全问题的全体记作NPC。计算复杂性理论在密码学研究领域中起了十分重要的作用，特别是公钥密码学。密码学中的安全性分为理论安全性和计算安全性(实际安全性)，计算安全性就是基于NP难问题的。目前的公钥密码体制是计算安全的，也就是说公钥密码体制的安全性是基于某种难解问题的假设，其代表性的主要有：大整数因子分解、有限域上的离散对数问题和椭圆曲线离散对数问题。2 Random Oracle模型随机预言(Random Oracle，简称RO)模型是Bellare和Rogaway基于Fiat和Shamir86的思想提出的一种方法论，它是一种非标准的计算模型.目前的可证明安全的密码体制大都基于随机预言模型，RO模型是一种探索性分析一个密码学原型和协议的方法，它为密码学理论和实践提供了一座桥梁。在RO模型中，Hash函数被形式化为一个随机预言机，对每一个询问，将得到一个随机的应答。该方法的过程是首先通过形式化定义方案的安全目标和攻击模型;然后为一个概率多项式时间 (Probabilistic Pulynomial-Time，PPT)敌手提供一个理想的模拟环境(随机预言模型)，在敌手看来，该模拟环境与实际环境是多项式时间不可区分的，通过模拟环境回答敌手的所有询问;最后利用敌手的攻击结果解决基础困难性问题。相对标准模型而言，随机预言模型更具有实际意义，当然，随机预言模型也有争议，主要原因是Hash函数的真随机性问题。3密码体制的安全目标实现安全性证明的首要工作是为密码体制定义适当的安全目标，加密方案的安全目标是机密性。对于加密方案的机密性目标，可以分为如下层次:一单向性(OW)：由密文不能恢复相应的明文。一不可区分性(IND)：对敌手给定的两个明文，加密者随机选择其中一个进行加密，敌手无法从密文中知道是对哪个明文的加密。一语义安全性(SEM)：:敌手在知道密文的情况下，能计算出明文的信息量并不比他在不知道密文的时候多，除了明文的长度。一不可延展性(NM)：敌手无法构造与已给密文有关系的新密文。一明文可愈识性(PA)：敌手不能以一个不可忽略的概率，在不知道相应明文的情况下，构造出一个密文。4敌手模型的定义对于加密方案，敌手攻击类型主要有:一选择明文攻击(CPA):敌手可加密所选的任何明文，获得相应的密文。显然在公钥体制下，敌手只要知道公钥就可进行这种攻击。一非适应性选择密文攻击(CCAl):敌手在得到挑战密文C*之前可以选择密文询问解密机，以获得相应的明文，但在得到C*后就不能再询问解密机。一适应性选择密文攻击(CCA2):敌手在得到挑战密文C*前后都可以询问解密机，以获得相应的明文，但在得到C*后，不能询问C*的明文。对于加密方案的安全目标，不可区分性和语义安全性是等价的。对于加密方案，目前普遍接受的安全性是适应性选择密文攻击下的不可区分性(IND-CCA2)，通常所说的选择密文安全是指创IND-CCA2安全，所以具有语义安全的加密方案是指该方案具有IND-CCA2安全性。IND-CCA2安全性的证明可以用以下的对局实现:l)密钥生成器生成系统的公钥和私钥，公钥向敌手A公开而私钥对其保密。2)敌手A选择密文向解密机进行一系列的询问，对每一个询问，解密机用私钥解密并将解密结果给敌手。敌手可以任意的方式构造这些密文，不一定用加密算法来构造。3）敌手A也可以向加密机进行一系列的询问。敌手选择两个长度相同的消息M0和M1交给加密机，该加密机随机选bR0，l，然后对M。进行加密得到密文交给敌手A