密码学与信息安全

密码学与信息安全

可证明安全性

根据所基于的不同理论，可分为信息论安全（Information Theory Security）和计算复杂性安全（Computational Complexity Security）两大类。

信息论安全由C.Shannon 在其开创性的文献[12]中给出定义，一个方案如果满足信息论安全，那么无论攻击者具有什么样的计算能力都无法破解，所以信息论安全又被称为无条件安全。虽然信息论安全在安全上是完美的，但却有着难以实用的缺点，因而只是用在军事和外交等对信息保密极度敏感的领域。

计算复杂性安全是基于复杂性理论之上的一套模型，它将攻击者的能力限定为多项式时间，一个方案是否安全取决于攻击者成功的优势能否规约到以不可忽略的概率解决某个已知困难问题，例如大整数分解，二次剩余，离散对数等。

计算复杂性安全虽然并不能保证无条件安全（例如在量子计算机中大数分解问题不再是困难的），并且对攻击者的能力加以了限制，但在理论下的攻击者的计算能力实际上已远远超过现实当中存在的攻击者，因而计算复杂性安全模型下的方案在实际应用中仍然是可以信赖的。因而在现实环境当中，攻击者在计算能力上并无任何特别的优势可言。

标准模型

早期基于计算复杂性安全的密码方案一般是基于标准模型（Standard Model ）下，该模型首先对方案中攻击者的能力加以定义，而且必须强调攻击者一定是自适应性的。然后假设该攻击者成功的概率为某个多项式时间不可忽略的值，然后通过一定的步骤利用该攻击者，将攻击者的能力转化为攻破某已知困难问题的优势。由于该困难问题在多项式时间下无法求解，因而可以得出存在攻击者以不可忽略概率攻破方案这一假设与事实相矛盾。

不幸的是，基于标准模型的密码方案往往需要大量的计算，难以实用。如现有最高效的标准模型下安全的公钥加密方案，数字签名方案，仍然没有广泛加以使用。如何设计一个面向具体应用的密码方案，同时平衡可证明安全性和实用性，成为了密码方案设计中首要考虑的问题。因为一个低效率的方案与不安全的方案一样，都无法在实际当中被广大用户接受并广泛使用。

随机预言机模型的定义

虽然计算复杂性安全模型下的方案已经比信息论安全模型下的方案更加实用，但仅从标准模型下的现有绝大部分方案来看，都无法在实际当中推广开来，造成了密码学理论和实践中的一个鸿沟.

原因在于有许多广泛应用的方案虽然无法给出标准模型下的证明，但在长期应用中抵御住了实际的攻击者，取得了大众的信任。同时标准模型下设计一个安全的方案十分困难，没有形成一套方法论，方案的设计成为一种科学艺术, 而非工程。

这种状况在1993年，Bellare 和Rogaway 创造性地提出随机预言机模型后[1]，取得了飞跃性的进步。

随机预言机（Random Oracle）的定义是一个确定性的公共可访问的随机均匀分布函数（Uniformly Distributed ），对于任意长度的输入，在输出域中均匀选择一个确定性长度的值作为询问的回答。

随机预言机模型是在标准模型的基础上增加了一个公共可访问的随机预言机，将方案中所使用的散列函数（Hash Function ）理想化为随机预言机，攻击者（Adversary ）只能通过询问随机预言机来获得所需要的散列值（Hash Value ）。然后仿真者（Simulator ）通过一定

的步骤利用该攻击者，将攻击者的能力转化为攻破某已知困难问题的优势（Advantage ）。

在实际应用中, 一般用一个安全的散列函数来替代随机预言机, 方案的安全性便基于可证明安全的规约结果和散列函数本身与随机预言机的可区分性之上。

散列函数与随机预言机相似的性质（快速，确定，单向，均匀分布）使其在密码方案设计中扮演了非常重要的角色。实际上，对某个消息进行散列运算之后再处理可以增加该消息的冗余度，从信息论安全的角度来看是十分有益的。

同时与标准模型下可证明安全的方案相比较，方案的计算开销也会因为随机预言机模型下许多紧规约技巧而大大降低。

虽然随机预言机模型仍然是基于计算复杂性理论，但为了加以区分，我们将计算复杂性安全模型中没有使用随机预言机的称之为标准模型（Standard Model）

随机预言机模型一经提出，便成为了平衡密码方案可证安全性和实用性的重要途径。在随机预言机模型下设计一个实用，高效并且安全的方案不再是不可平衡的矛盾。许多广泛应用的密码方案都是基于随机预言机模型安全的，如数字签名方案[2]，公钥加密方案RSA-OAEP[2,3]，密钥分配协2议[1]。

[1]M.Bellare and P.Rogaway.Random oracles are practical-a paradigm for designing efficient protocols.In Proceedings of the First ACM Conference on Computer and Communications Security,pages 62–73,1993.

[2]M.Bellare and P.Rogaway.The exact security of digital signatures-how to sign with rsa and rabin. In U.Maurer, editor,Advances in Cryptology-Proceedings of EUROCRYPT’96,volume LNCS 1070,pages 399–416,1996.

[3]M.Bellare and P.Rogaway.Optimal asymmetric encryption —how to encrypt with rsa.In Advances in Cryptology – EUROCRYPT’94,volume LNCS 950,pages 92–111.Springer-Verlag,1995.

[4]E.Fujisaki and T.Okamoto.Secure integration of asymmetric and symmetric en- cryption schemes.In Advances in Cryptology-Crypto’99,volume LNCS 1666,pages537–554,1999.

随机预言机模型下可证明安全过程

由于事先确定的挑战包含有仿真者可用来解答方案所基于的困难问题的知识（Knowledge ），如果仿真游戏成功的概率为不可忽略的值，那么必然方案所基于的困难问题在给定攻击者的环境下不再是困难的，这与现实环境中该已知困难问题的不可计算性（Computational Intractable ）相矛盾，因而该攻击者实际是不存在的，方案在模型下是安全的。

随机预言机的类型

在基于随机预言机模型下的密码方案的证明当中，使用随机预言机的方法也有不同，从仿真者对随机预言机加以控制的程度不同可以分为以下三种类型：

(1) 无控制型:此类型下，仿真者无法截取攻击者提出的询问，也不能控制随机预言机的输出信息，该模式下的随机预言机与现实中密码学散列函数（Cryptographic HashFunction ）最为接近.

(2)部分控制型在一些方案中，仿真者可以知道攻击者提出的询问，但不能控制随机预言机的输出，该模式相当于仿真者可以窃听攻击者，在现实中需要仿真者对攻击者的通信完全可知，在大多数的内网环境或存在木马、后门程序的情况下，具有合理性。

(3)完全控制型:在大多数的方案中，要求仿真者对随机预言机完全控制，对于每一个询问，仿真者可以按照一定规则返回输出值给攻击者。该模式下的随机预言机实际上已无法直

接由实际中的任何散列函数加以替换。

随机预言机模型下可证明安全规约方法

与标准模型相比，除了提高效率之外，随机预言机模型另外一个显著优势就在于方案的安全性证明成为了一套可以重复使用的方法论。

安全性证明的规约方法集中在了将方案中的散列函数替换为随机预言机，然后按照一定的规则返回询问请求。对于询问回答的要求是确定性，并且在攻击者看来是输出域均匀分布的。所以在随机预言机模型下的密码方案往往可以规约到比较著名的困难问题（例如离散对数，计算Diffie-Hellman 问题），而在标准模型下的方案一般都需要一些特殊的困难问题假设（例如Strong RSA假设[等）。

下面我们将会介绍随机预言机模型下最具代表性、最有效的几种证明方法，这些方法都具有启发性，因而被广泛用在密码学方案的设计、证明过程中。

分叉引理规约方法

在一段相当长的时期里，ElGamal 及其各种类似的数字签名方案（例如Schnorr 签名,DSS 签名）都没有形式化的证明方法, 将方案的安全性规约到某个已知并充分研究过的困难问题。

人们只是相信攻破ElGamal 类数字签名与解决大素数有限域上某个密码学子群的离散对数问题是等价的。

直到1996年，Pointcheval 和Stern 在文献[1]中给出了形式化的证明方法，将ElGamal 类数字签名方案的安全性规约到离散对数问题上。他们给出的证明方法是基于随机预言机模型的，并且该证明方法具有很好的移植性，对于所有ElGamal 三元组性质的数字签名方案都可以采用此证明方法。

由于在证明过程中使用到了随机预言机回答分叉规约技术（Forking Reduction Technique ），所以该证明方法又被广泛称之为分叉引理（Forking Lemma）。

在2000年，Pointcheval 和Stern 在文献[2]中进一步完善了ElGamal 类数字签名方案的分叉引理，并将该证明方法扩展到盲签名方案上。

分叉引理规约方法

[1]D.Pointcheval and J.Stern.Security proofs for signature schemes.In U.Maurer,editor,Advances in Cryptology-Proceedings of EUROCRYPT’96,volume LNCS1070,pages 387–398,1996.

[2]D.Pointcheval and J.Stern.Security arguments for digital signatures and blind sig-natures. Journal of Cryptology,13(3):361–396,2000.