密码学基础：完美保密性和唯一解密性

1、完美保密性

什么是完美保密？

• 一个在明文空间M上的加密方案（Gen，Enc，Dec），如果对于每个明文 m ∈ M，对每个密文 c ∈ C，其中Pr[C=c]>0，有：Pr[ M = m | C = c ] = Pr[ M = m ]，则称这种加密方案是完美保密。
• 换句话说，即在“已知了密文的情况下，得到明文的概率”和“在不知道密文的情况下，得到明文的概率”是相等的。

完美保密性（Perfect Secrecy）与实际保密性（Practical Secrecy）：

• 完美不可区分：关于完美不可区分性的定义是基于一个涉及对手A的实验，并形式化了A无法区分一种明文加密和另一种明文加密;因此我们称之为对抗性的不可分辨性。
• 我们加密一个消息，最终的目的是什么呢？最直观地感觉就是，最终目的是不让别人在没有密钥的条件下，从加密结果中恢复出原始的消息 。
  这个定义的意思是，对于任意等长的消息m，只要这个m属于消息空间（就是说用这个加密算法可以加密m），那么用加密密钥k加密后，加密结果“看起来都一样”，没法看出来这是从m，还是从其他什么消息加密得来的。
  密码学中证明了，唯一能达到这个安全条件的加密算法叫做一次一密，一次一密的问题在于加密时使用的密钥长度至少要跟消息长度一样才行。我们知道密钥必须是秘密传输的。我靠，我都能秘密传输一个等长度的密钥了，我为什么还要用这个密钥加密呢？我直接把消息秘密发送给对方不就完了… 所以说，一次一密在实践中是没有什么应用价值的。
  那怎么办呢？我们换种想法，上面那个定义说的是加密结果让谁看，“看起来都一样”。那干脆，我们选一个迄今为止计算能力最强的人来看加密结果，要是他都觉得“看起来都一样”，是不是就够了？到现在为止，计算能力最强的就是计算机了，我们就让一个计算机来看，如果他觉得“看起来都一样”，那估计没问题了。这就是我们所说的实际保密性。
• 即可抵御无限计算能力的攻击者 。密文没有泄露任何明文信息，因此敌手截获一个密文不能得到关于明文的任何信息的情况。

完美保密的局限性：

• 完美保密的加密方案的密钥长度至少要和明文的长度一样大

香农定理（用于判断是否是完美保密）
假设对明文空间M上的加密方案Π(Gen, Enc, Dec)有|M| = |K| = |C|，则这种加密方案是完美保密当且仅当：

• 对任意密钥k ∈ K，k 被选中的概率都相等，都等于 1/|K|
• 对于任意的明文m ∈ M，以及任意的密文c ∈ C，则存在一个唯一的密钥 k ∈ K使得Enc_k(m) = c

2、唯一解密性

什么是唯一解密性？

• 唯一解密性 意味着对于每个密钥，加密函数 f(clear, key) 定义域中的每个元素恰巧是一个明文的加密。即对于每一个密钥k，f(key=k)是一个可逆函数。
• 如何判断是否具有唯一解密性？ 与判断完美保密相似，区别在于一个是固定明文以密钥作为变量得到的函数，另一个是固定密钥以明文作为变量得到的函数。
• 固定密钥，唯一可解密：是否存在一个密钥以及两个映射到相同密文的明文。
  密钥5，明文6和8对应的密文都是0。
• 固定明文，唯一可解密钥：是否存在一个明文以及两个不同的密钥会映射到同一密文。
  明文2，密钥6，8都会对应密文0。