密码学的安全性

发表于2020-07-02更新于2020-07-03字数统计2.5k阅读时长17分阅读次数

Free Talk

这次做综合课设的时候，队员发了一篇关于安全性的文章，我看完觉得有一种豁然开朗的感觉。这篇文章用非常通俗的语言，总结了密码系统的安全性，把我在密码学课上零散的知识给整合了起来。我在这边的文章的基础上，做了一些简单的调整修改。原文链接
NqodIJ.png

密码系统安全性的评估方法

无条件安全性

这种评价方法考虑的是假定攻击者拥有无限的计算资源，但仍然无法破译该密码系统。

计算安全性

这种方法是指使用目前最好的方法攻破它所需要的计算远远超出攻击者的计算资源水平，则可以定义这个密码体制是安全的。

可证明安全性

这种方法是将密码系统的安全性归结为某个经过深入研究的数学难题（如大整数素因子分解、计算离散对数等），数学难题被证明求解困难。

这种评估方法存在的问题是它只说明了这个密码方法的安全性与某个困难问题相关，没有完全证明问题本身的安全性，并给出它们的等价性证明。

实际安全性

对于实际应用中的密码系统而言，由于至少存在一种破译方法，即强力攻击法，因此都不能满足无条件安全性，只提供计算安全性。密码系统要达到实际安全性，就要满足以下准则：

  1. 破译该密码系统的实际计算量（包括计算时间或费用）十分巨大，以致于在实际上是无法实现的。
  2. 破译该密码系统所需要的计算时间超过被加密信息有用的生命周期。

例如，战争中发起战斗攻击的作战命令只需要在战斗打响前需要保密；
重要新闻消息在公开报道前需要保密的时间往往也只有几个小时。

  1. 破译该密码系统的费用超过被加密信息本身的价值。

如果一个密码系统能够满足以上准则之一，就可以认为是满足实际安全性的。

可证明安全性

可证明安全性体系的三大要素

在可证明安全体系中，有三大要素：安全模型，安全性定义和困难性问题。
安全模型分为安全目标和敌手能力。
安全目标描述了安全模型要达到什么程度的安全，例如，对于加密算法的不可区分性（Indistinguishablity 简称 IND）、对于签名算法的存在性不可伪造（Existable Unforgeble 简称 EU）等。

其中不可区分性（IND）也称为语义安全（Semantic scurity），其定义如下。
敌手即使获得了密文，也不能得到其对应明文的任何信息，哪怕是 1bit 的信息。
其形式化的表示方法为：已知 m0，m1以及 Cb=Enc(pk，mb)，其中 m0是 m0或 m1中的任意一个，即 Cb是 m0、m1其中之一的密文，敌手无法有效判断加密过程中 b 到底是 0 还是 1。

安全性定义

刻画敌手的能力，主要有四类，选择明文攻击（Chosen Plaintext Attacke 简称 CPA）、选择密文攻击（Chosen Ciphertext Attack 简称 CCA）、惟密文攻击（Ciphertext-Only Attack）、已知明文攻击（Known Plaintext Attack）。常用的刻画敌手能力是前面两类，选择明文攻击（CPA）是指由敌手选择明文并且可以得到对应的密文。选择密文攻击（CCA）是指敌手不仅可以选择明文获得密文，还能选择有限次的密文，获得对应的明文。CCA比 CPA 描述敌手的能力更强。

下面介绍一下常用的安全性定义。

CPA 安全。我们把选择明文攻击（CPA）描述成一个游戏以方便我们更好的理解。首先声明一点，这个游戏的目的是在选择明文攻击的前提下攻破系统的不可区分性（Indistinguishablity），所以下面简称这个游戏为 IND-CPA。其次，还要定义两个角色挑战者 C 和敌手 A。挑战者（challenger）的任务相当裁判，主持游戏并且对敌手的行为进行反馈。敌手顾名思义，就是去攻击当前系统，而且对于这个游戏来说是采用选择明文攻击的方法进行攻击。游戏的描述如下：

  1. 初始化：挑战者 C 创建 IND-CPA 系统，并且将公钥发送给敌手 A。

  2. 敌手 A 选择两个长度相同的明文 m0，m1发送给挑战者 C。挑战者 C 随机选择 b∈｛0,1｝，并将 mb加密记作 cb，然后将密文cb发送给敌手 A。

  3. 敌手 A 猜测挑战者 C 上一步进行加密的明文是 m0还是 m1，并且将猜测结果输出，输出结果记为 b‘。若 b‘=b，那么敌手攻击成功。

敌手攻击的优势可以定义为如下函数：
NqbGY4.png
其中 w 是加密方案密钥的长度。因为随机猜测就有1/2的概率赢得 IND-CPA 游戏。所以
Nqbtp9.png
才是敌手经过努力得到的优势。如果对任何多项式时间的敌手 A，存在一个可忽略的优势σ，使得
NqbrkD.png
那么就称这个加密算法在选择明文攻击下具有不可区分性，或者称为 IND-CPA 安全。

困难问题

有了安全模型和安全性定义，通常使用规约到困难问题的方法来进行安全性证明。密码学中常用的困难问题有离散对数困难问题（discrete logarithm problem，简称 DLP）、CDH 问题（Computational Diffie-Hellman） 、DDH 问题（Decisional Diffie-Hellman）以及 BDH 问题（Bilinear Diffie-Hellman）。

可证明安全性理论

有了前面叙述了安全模型，安全性定义，困难性问题，可证有了前面叙述了安全模型，安全性定义，困难性问题，可证明安全体系也变得可行。
可证明安全性是指利用**“规约”**的方法，将攻击密码算法或安全协议的方法规约到一个攻击困难问题上。首先确定加密体制的安全目标，如签名体制的安全目标是签名的不可伪造性（Existable Unforgeble），加密体制的安全目标是信息的不可区分性（Indistinguishablity）。然后根据安全性定义确定敌手的能力构建一个安全性模型。

规约是复杂性理论中的概念， 一个问题P1规约到问题P2是指，已知解决问题 P1的算法 M1，我们能构造另一算法 M2，M2可以以 M1作为子程序，用来解决问题 P2。

将规约的方法应用在密码算法或安全协议的安全性证明上，例如，可以将敌手对密码算法或安全协议（P1）的攻击规约到一些已经得到深入研究的困难问题（P2）。即若敌手能够对算法或协议发起有效的攻击，就可以利用敌手构建一个算法来攻破困难问题，然而困难问题是已经被证明无法攻破的，这样就出现矛盾。根据反证法，敌手可以攻破算法或协议假设不成立，证明完毕。

一般来说，为了证明方案 1 的安全性，我们可以将方案 1 规约到方案 2，即如果敌手 A 可以攻破方案 1，那么敌手 B 同样也可以攻击方案 2，而方案 2 已经被证明是安全的，或者是一个难题。

证明过程通过一个思维游戏来描述。首先，挑战者创建方案2，B 表示方案 2 中的敌手，A 表示方案 1 中的敌手。B 为了攻破方案 2，利用 A 作为子程序来攻击方案 1。B 想要利用 A，就需要对 A 进行训练，所以 B 模拟了 A 的挑战者。
Nqbotg.png
例如，如果要对加密算法进行安全性证明，那么方案 1 就是具体的加密算法 。 假设安全目标是信息的不可区分性（Indistinguishablity），敌手 A 的能力是可以选择明文攻击，即 CPA。敌手 B 模拟敌手 A 的挑战者，与 A 进行 IND-CPA 游戏。在游戏过程中，B 为了实现自己的目的利用 A。如果 A 无法判断自己是与 B 还是与挑战者做游戏，那么称 B 的模拟是完备的。

对于其他加密算法或加密协议，我们必须首先确定它想要实现的安全目标，例如签名方案的不可伪造性，然后根据安全性定义确定敌手的能力构建一个安全性模型，再把对加密算法或加密协议的攻击规约到已被证明的困难问题上。 这就是可证明安全性。

结语

可证明安全性理论是密码学理论与计算复杂性理论的一次完美结合，也是现代密码学的基石。在过去的 30 年终，现代密码学最大的突破就是把密码学体系建立在计算复杂理论上，这使得密码学从一门艺术发展成为一门严谨的学科。