可证明安全理论及方法——密码算法

第1章 绪论 本章主要内容 (1)可证明安全理论的概述：可证明安全性理论的产生、可证明安全性概念、可证明安全的方法论。 (2)基本攻击类型：密码加密系统、敌手对密码加密方案的基本攻击模型。 (3)安全性概念：精确形式化有关概念、加密方案的安全性概念。 (4)密码加密方案的安全性证明：密码加密方案的安全性证明概述、私钥加密方案的安全性设计、私钥加密方案的可证明安全性、公钥加密方案的可证明安全性。 (5)证明技术：混合论证概述、三模型证明系统、基于编码的博弈技术概述。 1.1 可证明安全理论的概述 1.1.1 可证明安全理论的产生 随着全球信息化程度的日益提高，信息已经成为一种战略资源，空间网络的信息安全问题，已经由国家、团体、个人机密保护问题上升为国家的战略性问题。美国、德国等很多国家相继制定了本国空间网络安全的战略。密码方案和密码协议是解决空间网络安全*直接、*有效的手段之一，是构建安全信息系统的基本要素。 怎样分析和判断一个密码方案或密码协议的安全性？从历史来看，密码方案或密码协议的分析方法主要经历了几个发展阶段。 (1)早在1949年，Shannon在《保密通信的信息理论》中，首先提出了密码系统“安全性”分析的理念和方法，开创了密码学领域的新篇章。在《保密通信的信息理论》一文中，Shannon给出了“完善保密性”思想，提出用密文中所含明文的信息熵来分析密码加密方案安全性；并利用“完善保密性”概念，证明了“一次一密”是无条件安全的，即攻击者即使拥有无限计算能力和无限存储资源，也无法破译该密码体制。 但是，随着信息技术的不断发展和广泛应用，信息安全性的内容不断扩展和完善。从*初的保密性，逐渐发展产生了完整性、可用性、可控性和不可否认性等，于是作为信息安全核心理论和技术的密码学也不断发展，产生了序列密码、分组密码、公钥密码、杂凑函数、消息认证码、同态加密等各种密码方案，以及数字签名、零知识证明、比特委托、不经意传输、多方计算、密钥协商、秘密共享、混淆等各种密码协议，而Shannon理论已经远远不能满足这些密码方案和密码协议的安全性分析与证明。 (2)曾经一段时间，密码方案和密码协议的设计及其安全性分析情况如图1.1所示。设计者首先提出一个密码方案或密码协议，然后在实践中攻击者试图破译，一旦发现安全问题再进行修补，进而周而复始地不断被破译和修补。这样，设计的密码方案和密码协议存在以下问题。 图1.1 早期证明密码方案或密码协议安全性的思路 ①设计的密码加密方案和密码协议容易有比较微妙的弱点，而且不易在正常操作中检测到。 ②新的分析方法和分析技术的提出时间是不确定的，在任何时候都有可能提出新的分析方法和分析技术。 ③很难确信密码方案和密码协议的安全性，反反复复地修补，更增加了人们对安全性的担心，也增加了实现和使用的成本。 怎么解决密码方案和密码协议的设计过程中周而复始不断修补的问题呢？人们开始探讨可以证明密码方案和密码协议安全性的设计方法，在这个过程中，有人提出了形式化的逻辑方法，该方法在寻找某类型密码方案和很多密码协议漏洞方面很有成效，而且可以实现自动化。然而，一旦抽象的密码运算实例化，逻辑正确的证明并不意味着密码方案或密码协议本身必然是正确的，也就是说缺乏严格的安全性证明。 (3)于是，人们开始采用一种崭新的思路来设计和分析密码方案与密码协议，就是用可证明安全理论与技术。20世纪80年代初，Goldwasser等首先比较系统地阐述了可证明安全性这一思想，并给出了具体可证明安全的加密方案和签名方案，如图1.2所示，这种方法就是在某个假设下，证明设计的密码方案和密码协议没有攻击方法，因此是安全的。 图1.2 可证明安全理论证明的思路 然而，Goldwasser等介绍的可证明安全的加密方案和签名方案以严重牺牲效率为代价，极大地制约了可证明安全理论的发展。直到20世纪90年代中期，出现了“面向实际的可证明安全性(Practice-oriented Provable-security)”概念，使得可证明安全理论迅速在实际应用领域取得重大进展，特别是Bellare等提出了著名的随机预言机(Random Oracle，RO)模型方法论，使得仅作为纯理论的可证明安全理论，迅速在实际应用领域取得了重大突破，一大批快捷有效的安全方案和安全协议相继提出，还产生了另一个重要概念“具体安全性(Concrete Security or Exact Security)”。其意义在于，我们不再仅仅满足于安全性的渐近度量，而是可以确切地得到较准确的安全度量。这方面的研究在证明密码方案和密码协议的基本安全目标方面已取得了巨大的成功，被国际学术界和产业界广泛接受。例如，Bleichenbacher 给出了著名的公钥密码标准PKCS#l中存在的一个安全漏洞。为此，RSA公司吸收了*优非对称加密填充(OAEP)的思想，把该标准更新为PKCS#2，新旧标准之间的差别就在于新的公钥密码标准是可证明安全的。另外，符合可证明安全的OAEP还被应用到著名的电子协议标准SET 中。同时，OAEP和PSS 1721还被提名为公钥加密方案标准IEEE 1363中的候选算法之一。 总之，可证明安全理论是一种研究安全密码方案和安全密码协议的科学公理化方法。一方面看，可证明安全理论与技术是一种安全可靠的分析方法；它在适当的模型下，把高层的密码方案和密码协议的复杂安全性归约为底层的“极微本原(Atomic primitives)”的简单安全性。另一方面看，可证明安全理论与技术又是一种科学高效的密码设计方法：其模块化的设计思路使得密码设计人员不再拘泥于极为困难的“极微本原”的设计，而是直接以“极微本原”为工具，以形式化的安全性定义为参照，再结合具体的模型来设计高层的密码方案和密码协议，从而大大提高了设计效率。 1.1.2 可证明安全性概念 可证明安全性实质上是一种归约证明方法，具体定义如下。 定义1.1 可证明安全性(Provable Security)。可证明安全性是指这样一种“归约”方法。 (1)确定一个密码方案或密码协议的安全目标，例如，加密方案的安全目标是有两个不同消息加密后密文的不可区分性，数字签名协议的安全目标是签名的不可伪造性。 (2)根据敌手的能力，构建一个形式化的安全模型，并且定义它对安全方案或安全协议的安全性“意味”着什么。对某个基于“极微本原”(或者称“极微原语”)的特定密码方案或密码协议，再基于以上形式化的安全模型去分析，其中“归约”论断是其基本工具。这个极微本原，是指安全方案或安全协议的*基本组成构件或模块。 (3)指出如果敌手能成功攻破该密码方案或密码协议，则存在一种算法在多项式时间内破译或解决“极微本原”。 概括成一句话，可证明安全性是指通过归约方法，分析密码方案或密码协议，在一定的敌手模型下，能够达到特定的安全目标。 ？ 显然，定义1.1说明可证明安全性的概念有三个基本元素。 (1)安全性定义(或概念)：安全目标和敌手攻击模型决定了安全性定义。因此，定义合适的安全目标、建立适当的敌手模型是讨论可证明安全性的前提条件。 另外，“安全性”的精确形式化有多种形式，一般在计算复杂性理论框架下加以讨论，如主要考虑：①概率多项式时间(Probabilistic Polynomial-Time，PPT)的敌手A；②转换算法；③“可忽略不计”的成功概率。这种精确形式化是一种“渐近”观点，有着广泛的适用范围。 (2)“基础假设”或“公理”：往往选取的是存在“好”的“极微本原”，或者说是在多项式时间内难以破译或解决的问题。 选取“基础假设”或“公理”的原则是“越弱越好”，通常称弱假设为标准假设。 (3)归约：是一种方法论，是研究可证明安全性的工具。如图1.3所示，就是敌手的攻击模型与“密码方案或密码协议”(统称密码系统)安全性之间的归约关系。 图1.3 归约方法 可证明安全理论是一种研究安全密码方案和安全密码协议的科学公理化方法，可证明安全理论在密码方案和密码协议的设计与分析应用中，需要注意几点。 (1)用可证明安全理论分析密码方案和密码协议是以某一“基础假设”或“公理”为基础的，一旦该“基础假设”或“公理”靠不住了，安全性证明就没有意义了(图1.2)。 (2)用可证明安全理论设计密码方案和密码协议时，有几点需要注意。 ①往往忽略设计的方案和协议的效率，这是可证明安全性自身的一个弱点。 ②用可证明安全理论设计密码方案和密码协议时采用模块化的设计思路，使得设计人员不再拘泥于极为困难的“极微本原”的设计，而是直接以“极微本原”为工具，这样，“极微本原”不可靠造成密码方案或密码协议不安全。另外，即使“极微本原”可靠，设计的密码方案或密码协议本身也不一定安全。 ③要想设计好的密码方案和密码协议，必须注意安全模型规划，注意所建立的安全模型都涵盖了哪些攻击。 (3)可证明安全理论不是万能的，有些情况可证明安全理论是没有办法证明、发现或者解决的，例如：①无法证明或发现“实现不正确的密码系统”或“被误用的密码系统”；②无法证明或发现密码系统的密钥被折中；③不能发现在安全模型中没有涵盖而真实存在的攻击；④不能发现或纠正错误的证明。 值得一提的是：本书主要讨论可证明安全理论在密码加密方案的设计和分析中的应用，不再考虑其他密码方案和密码协议的情况。 1.1.3 可证明安全的方法论 目前在可证明安全理论研究领域内，主要采用标准模型和随机预言机(RO)模型的方法论。 1. 标准模型方法 标准模型方法是在计算复杂性理论框架内，严格依据复杂性理论的证明方法，其证明过程通常是根据敌手可能具有的能力，把敌手形式化为某概率多项式时间算法，利用归约论断、证明、敌手攻击某个密码方案或密码协议的成功概率是安全参数的可忽略不计函数，从而证明了密码方案或密码协议的安全性。这是一种“渐近”分析观点，具有广泛的适用范围。 自从Cramer 和Shoup 提出了**个比较实际的标准模型下可证明安全的公钥加密方案后，出现了一系列标准模型下可证明安全的密码方案和密码协议，从而大大推进了标准模型方法论。Cramer 和Shoup 提出的**个标准模型下可证明安全公钥加密方案的困难假设是判定性Diffie-Hellman 问题，其安全性归约是在标准的(抗碰撞)杂凑函数假设下得到的，不依赖于RO模型。该方法就是把杂凑函数视为具有某些特定性质的随机函数，既充分利用了RO安全论断的优点，又不依赖于RO模型。遗憾的是，标准模型中可证明安全的密码方案或密码协议往往以大量丧失效率和简洁性为代价，使得这类密码方案或密码协议在现实世界中缺乏竞争力。近几年，基于双线性对、多线性映射等技术的标准模型下可证明安全的公钥加密方案，得到更深入的研究和探索，取得一系列成果。 2. 随机预言机模型方法 随机预言机(RO)模型方法论是Bellare和Rogaway在1993年基于Fiat和Shamir建议的基础上提出的，它是一种非标准化的计算模型。 定义1.2 预言机(Oracle)。预言机M 是能够向外界询问的一种机器，它的询问始终由一些称为预言的函数:来回答。如果预言机的询问为x，它得到的回答为f（x），就说预言机得到了预言f。通常一个确定性预言机是带有一个附加带(称为预言带)和两个特殊状态的图灵机。两个特殊状态分别是预言求解状态和预言呈现状态。当输入为x，预言为f 时，预言求解状态的计算是某个形式的有限或无限序列（s0 ，t0 ，i0），（