第三章密码学的信息论基础.ppt

密码学的信息论基础 本章主要内容 概率论基础 完全必威体育官网网址性 信息的度量（信息熵） 熵的基本性质 伪密钥与唯一解距离 乘积密码体制 3.1 概率论基础 一个试验可能产生多个结果，每个结果称为一个简单事件，所有可能结果的集合称为样本空间。根据需要，我们只考虑有限多个可能结果的离散样本空间。 定义1：样本空间S上的一个离散随机变量X，用P ( X＝x )表示随机变量取x时的概率，简记为P ( x )，对于任意的x∈S，则有0≤P ( X＝x )≤1，而且可以得到 定义2：一个事件E是样本空间S的一个子集，事件发生的概率记为P ( E )。特别的，当E是一个简单事件x时P ( E )＝P ( x )。事件E发生的概率P ( E )为： 定义3：假设X和Y分别是定义在样本空间S1和S2上的随机变量。联合概率P ( x, y )是X取x且Y取y时的概率。条件概率P ( x / y )表示当Y取y时X取x的概率。如果对于任意的x∈S1和y∈S2,有P ( x, y )＝P ( x ) P ( y ),则称随机变量X和Y是统计独立的。而且对于联合概率和条件概率存在以下关系： 贝叶斯定理（Bayes定理）：如果P ( y )＞0，那么 由定义3的条件概率和联合概率的两个关系，直接可得贝叶斯定理（Bayes定理）。而且由定义3可得推论： 推论1：X和Y是相互独立的随机变量，当且仅当对所有的x∈S1和y∈S2，有P ( x / y )＝P ( x )。 定义4：设S是一个样本空间，X是S上的一个随机变量，且X是一个从样本空间S到实数集R的函数；对于每一个简单事件x∈S，X分配一个实数X ( x )。X的数学期望定义为 3.2 完全必威体育官网网址性 完全必威体育官网网址性： 设R＝( P, C, K, E, D )是一个密码体制。如果对任意x∈P和任意y∈C，都有p ( x / y )＝p ( x )。则称密码体制R具有完善的必威体育官网网址性能，或者称为完全必威体育官网网址性。 假设( P, C, K, E, D )是一个特定的密码体制，密钥k∈K只用于一次加密。假设明文空间P存在一个概率分布。这样就为明文元素定义了一个随机变量，用X表示。 p ( X＝x )表示明文x发生的先验概率。同时假设以固定的概率分布选取密钥（通常密钥选取是随机的，因此所有的密钥都是等概率的，在这里假设不是等概率的）所以密钥也定义了一个随机变量，用K表示；p ( K＝k )表示密钥k发生的概率。假设密钥和明文是统计独立的随机变量。 同样可以把密文看成随机变量，用Y表示。通过明文X和密钥K可以计算出密文Y的概率p ( Y＝y )。 对于密钥k∈K，定义C ( k )＝{ Ek ( x ), x∈P }， 也就是说C ( k )代表密钥是k时所有可能的密文。对于任意的y∈C，我们有： 同样，对于任意的y∈C和x∈P，可如下计算条件概率p ( Y＝y / X＝x )（即给定明文x，密文y的概率）： 由贝叶斯公式计算p ( X＝x / Y＝y )（也就是给定密文y，明文x的概率）得 由上述公式可知道，只要知道了概率分布就可以求出在给出密文情况下明文的概率。 例：假设明文P＝{ a, b }满足p ( a )＝1/4，p ( b )＝3/4，设密钥K＝{ k1, k2, k3 }，p ( k1 )＝1/2，p ( k2 )＝1/4，p ( k3 )＝1/4，设密文C＝{1, 2, 3, 4}，则加密矩阵如下： 解：计算密文分布如下： p (1)＝(1/2) (1/4)＝1/8 p (2)＝(1/2) (3/4)＋(1/4) (1/4)＝7/16 p (3)＝(1/4) (3/4)＋(1/4) (1/4)＝1/4 p (4)＝(1/4) (3/4)＝3/16 则明文空间上的条件概率分布为： p (a/1)＝1 p (b/1)＝0 p (a/2)＝1/7 p (b/2)＝6/7 p (a/3)＝1/4 p (b/3)＝3/4 p (a/4)＝0 p (b/4)＝1 可以发现，只有密文y＝3时，p (a)＝p (a/3)，p (b)＝p (b/3)。也就是说对于密文y＝3满足完善必威体育官网网址性的定义，但是对于其他的密文不满足。 定理：假设移位密码中的26个密钥等概率使用，则对任意概率分布的明文，移位密码都具有完全必威体育官网网址性。 证明：这里令P＝C＝K＝Z26，对于0≤K≤25，加密函数ek定义为ek (x)＝( x＋K ) mod 26（x∈Z26）。先计算C上的概率分布。假设y∈Z26，