目录
一. 介绍
二. 举例：移位密码
（1）密文概率
（2）明文概率
三. 举例：多字母的移位密码
四. 完美安全
五. 举例：双子母的移位密码
六. 从密文角度看完美安全
七. 完美保密性质
一. 介绍
在密码学中，K代表密钥，M代表明文，C代表密文，每个都有各自的概率分布。
密钥是通过密钥生成算法Gen产生的，通常而言都是均匀且随机的形式选择密钥，如下：
明文的分布通常跟密码方案是无关的，而是跟加密/解密方相关，也可以看成敌手（adversary）的不确定性，如下：
比如，军队传递消息，明文可能是以下两者之一：
attack today don't attack
这两者的概率有可能也不一样，比如：
Pr[M=attack today]=0.7 Pr[M=don't attack]=0.3
密钥K是由密码方案决定的，也就是由Gen确定。明文M取决于外部条件，所以，密钥K和明文M分布上通常是互相独立的。
当确定了加密方案和明文分布，那么密文分布也就确定了，如下：
或者写做：
Pr[C=c]
二. 举例：移位密码
移位密码，写做shift cipher，在网络安全领域很常见
假定密钥K只有26种情况，K={0,...,25}，每个密钥取到的概率均相等，也就是：
Pr[K=k]=1/26
假定明文只有两种情况a和z，其概率分布满足如下：
（1）密文概率
请分析密文为B的概率？
解：
当密文为B时，很明显只有两种情况可能：
明文M=a，且密钥K=1
明文M=z，且密钥K=2
根据明文M和密钥K之间是互相独立的，可计算：
第一个等号：M与K之间的独立
第二个等号：带入明文的概率以及密钥的概率
同理可计算另一种情况为：
综合两者情况相加可得：
（2）明文概率
当看到密文是B时，请推断明文为a的概率?
解：
很明显该题为条件概率。根据Bayes定理，可得：
第一个等号：条件概率的性质
第二个等号：明文为a的概率为0.7,密文为B的概率第一问已经计算完
如果给定明文M=a时，只有当密钥K=1，其概率为1/26时，密文才是C=B，所以可得：
Pr[C=B|M=a]=1/26
三. 举例：多字母的移位密码
如刚才的例题，我们还是采纳移位密码，但此时明文M的分布如下：
请求密文C=DQQ的概率？
解：
只有两种情况可以保证密文C=DQQ。
情况1：明文M=ann，密钥K=3
情况2：明文M=boo，密钥K=2
容易计算以上概率为：
当然如果想计算当看到密文为DQQ时，明文为ann的概率，依旧可以使用Bayes定理计算：
Pr[M=ann|C=DQQ]=0.4
四. 完美安全
完美安全，Perfect secrecy
假设敌手已知明文M的概率分布，加密方案也是全局公开的。敌手唯一不知道的就是所使用的密钥。
首先一个诚实用户选择明文并加密，接着把该密文传递给另外一方，在这其中敌手可以进行窃听并获得密文，也就是一种唯密文攻击（ciphertext-only attack）。完美安全要求敌手在获得密文后，不能知道其中的明文。换句话说，已知密文推明文的后验概率（posteriori probability）跟明文本身的前验概率（priori）是一样的。
以上表明密文不会泄露明文的任何信息，形式化的定义如下：
其中Pr[C=c]>0只是保证条件概率的分母不为0
五. 举例：双子母的移位密码
证明：双子母的移位密码无法实现完美安全
解：
该题的本质则是证明：
其实很容易证明。我们此处举一个简单的例子，假设明文有两种情况aa或者是ab
很明显当密文为XX时，其明文绝对不可能是ab，也就是：
Pr[M=ab|C=XX]=0
但是:
Pr[M=ab]=1/2
证明完毕
六. 从密文角度看完美安全
如果密文的分布与明文分布无关，其实也能说明完美安全性。
假定有两个明文m和m'，如下：
如果加密明文m形成的分布，与加密m'形成的密文分布一样的话，则可以得到：
注意以上概率分布来源于密钥K的选择以及加密算法Enc的随机性。也就是以上概率分布仅取决于加密方案，与明文分布M无关。换句话说，密文不包含明文m的任何信息，从而无法区分m和m'形成的密文，这不就是完美保密性想表达的内容。
七. 完美保密性质
推论
给定明文空间为M，加密方案为（Gen,Enc,Dec），如果以上m与m'的条件满足的话，那么该密码方案是完美安全的（perfect secret）
证明：
首先所有的概率均为正数：
Pr[M=m]>0
已知明文推断密文的概率可计算为：
第一个等号：密文随机变量C的定义
第二个等号：明文M=m
第三个等号：密钥K与明文M相互独立
以上概率为：已知明文m，遍历密钥空间K，使其加密结果刚好为c
根据条件概率的性质，可得：
证明充分性。
已知完美安全性，所以可得：
带入上式子，可得：
Pr[C=c|M=m]=Pr[C=c]
由此进一步可得：
充分性证明完毕。
证明必要性：
如果明文m的概率恰好为0时，可得：
如果明文m的概率非0时，定义一个新的概率如下：
由此可计算为：
必要性证明完毕。
推荐阅读
发表评论