第3章密码学的信息论基础
第3章 密码学的信息论基础
31保密系统的数学模型 信源}"编码器」信道}译码器"信宿」 干扰器 图3.1通信系统模型 信源]m加密器C信道解密器}"接收者] 密钥k 分析者 图3.2保密系统模型
3.1 保密系统的数学模型 信 源 编码器 m 信 道 译码器 信 宿 m 干扰器 图3.1 通信系统模型 信 源 加密器 m 信 道 解密器 接收者 m 分析者 图3.2 保密系统模型 密钥 k c c
分析者 发送者}m加密」无噪信道解密m·接收者 信源 k安全信道 k 密钥源 图3.3 Shannon的保密系统模型
无噪信道 安全信道 密钥源 加 密 分析者 发送者 解 密 接收者 信 源 k k m m c m 图3.3 Shannon的保密系统模型
数学模型 样本空间 ∈M,1≤l≤ P(m)=p(m,m2,…,mz)=∏p(m) 密钥空间C=y 密文空间C=(mmer ()=∑pk(k)p(d4(c) ∈C
• 数学模型 – 样本空间 – 密钥空间 – 密文空间 P M m m m mL ml M l L L = = = ( 1 , 2 , ) ,1 = = = L l pP m p m m mL p ml 1 1 2 ( ) ( , ,, ) ( ) ' L C = Y Ck = ek (m)m P = Ck k c C K P k p (c) p (k) p (d (c))
在给定密文发生的条件下,某个明文发 生的条件概率 Pp(m)∑Pk(k) Pp(mc) (k m=dk(c)) ∑Pk(k)p(ak(c) kc∈Ck
• 在给定密文发生的条件下，某个明文发 生的条件概率 = = k k k c C K P k k m d c P K P p k p d c p m p k p m c ( ) ( ( )) ( ) ( ) ( ) ( )
3.2信息量和熵 定义3.1设随机变量x={=12…,n,x出现 的概率为p(x)≥0且∑mx)=1。则Ⅹ的不确 定性或熵( Entropy)定义为 H(X)=∑p(x,)g2p(x,)
3.2 信息量和熵 • 定义3.1 设随机变量 ，出现 的概率为 。则 X 的不确 定性或熵（Entropy）定义为 X = xi i =1,2, ,n i x = = n i i i p x p x 1 ( ) 0,且 ( ) 1 = = − n i i i H X p x p x 1 2 ( ) ( )log ( )
反映了集中事件出现的平均不确定性,或为确 定集中出现一个事件平均所需的信息量(观测 之前),或集中每出现一个事件平均给出的信 量(观测之后)。如果从编码的角度来考虑 的鞋成用最优的三进的编妈形式表示 0·log20=0 采用以2为底的对数时,相应的信息单位称作 比特(Bt)。 如果集X为均匀分布时,即p1=1/n,1≤i≤n, 则H(X)=lg2n H(X)≥0,当X为确定性的事件时,即X概率 分布为p(X=a)=1,则H(X)=0
• 反映了集中事件出现的平均不确定性，或为确 定集中出现一个事件平均所需的信息量（观测 之前），或集中每出现一个事件平均给出的信 息量（观测之后）。如果从编码的角度来考虑， 熵也可以理解成用最优的二进制编码形式表示 所需的比特数。 • 采用以2为底的对数时，相应的信息单位称作 比特（Bit）。 • 如果集X为均匀分布时，即 ， 则 。 • ，当X为确定性的事件时，即X概率 分布为 ，则 。 0log 2 0 = 0 pi =1/ n, 1 i n H(X) = log 2 n H(X ) 0 p(X = a) = 1 H(X ) = 0
例3.1设有一个密码系统明文空间P={ab}的概率分布 为p(a)=1/4,p,(b)=3/4; 密钥空间K={,k2k3的概率分布为()=12p1(k2)=P(k)=14 密文空间C={2,34},且假定加密函数为 e()=(b)=22(a)=2,ek)=3ek(a==4。P(187/1614|3/16 可用右边的加密矩阵表示: 则按公式31和3.2我们很容易计算出密文空间的概率分布及 关于明文的条件分布: 1)密文空间的概率分布表如下: a b 2)明文关于密文的条件分布帅表如下:412 2|3 明文空间的熵为: k334 H(P)=-log log27=2-,(og23)≈081 cⅦma 类似地可计算 0 1/7 6/7 H(K)=1.5且H(C)≈1.85 1234 1/4 3/4 0
• 例3.1 设有一个密码系统明文空间 的概率分布 为 ； 密钥空间 的概率分布为 。 密文空间 ，且假定加密函数为 。 可用右边的加密矩阵表示： 则按公式3.1 和3.2我们很容易计算出密文空间的概率分布及 关于明文的条件分布： 1） 密文空间的概率分布表如下： 2）明文关于密文的条件分布 表如下： 明文空间的熵为： 类似地可计算 () pC c 1 2 3 4 1/8 7/16 1/4 3/16 1 k 2 k 3 k a b 1 2 2 3 3 4 c\m a b 1 1 0 2 1/7 6/7 3 1/4 3/4 4 0 1 P = a,b pP (a) =1 / 4, pP (b) = 3 / 4 K = k1 , k2 , k3 pK (k1 ) =1/ 2, pK (k2 ) = pK (k3 ) =1/ 4 C = 1,2,3,4 ( ) 1, ( ) 2; ( ) 2, ( ) 3; ( ) 3, ( ) 4 1 1 2 2 3 3 ek a = ek b = ek a = ek b = ek a = ek b = p(mc) (log 3) 0.81 4 3 2 4 3 log 4 3 4 1 log 4 1 ( ) H P = − 2 − 2 = − 2 H(K) =1.5且 H(C) 1.85
定义32设X={x=12…,,x出现的概率 为以(x)20且∑以(x)=1。Y={=12…,m},y出 的概率为p()≥0且∑m)=1,则联合事件集 Xy=y=12…nj=12…;m,令xy的概率 为p(xy)≥0,此时∑∑xy)=1。集X和γ的联合熵 定义为 H(X)=H(X,y)=∑∑(xy)kog2p(xy) 集相对于事件的条件熵定义为 H(Xy)=2P(x, v)log2 p(x, y,) 集相对于集的条件熵定义为 H(xy)=2py, ) H(ry)=-2Ep(y, )p(x, v,)log, p(x, py 2(x
• 定义 3.2 设 ， 出现的概率 为 。 ， 出现 的概率为 ，则联合事件集 ，令 的概率 为 ，此时 。集X和Y的联合熵 定义为 集相对于事件的条件熵定义为 集相对于集的条件熵定义为 X = xi i =1,2, ,n i x = = n i i i p x p x 1 ( ) 0,且 ( ) 1 Y = y j j =1,2, ,m j y = = m j j j p y p y 1 ( ) 0,且 ( ) 1 XY = xi y j i =1,2, ,n; j =1,2, ,m i j x y p(xi y j ) 0 = = = n i m j i j p x y 1 1 ( ) 1 = = = = − n i m j i j i j H XY H X Y p x y p x y 1 1 2 ( ) ( , ) ( )log ( ) ( ) ( )log ( ) 1 2 i j n i j i j H X y p x y p x y = = − ( ) ( ) ( ) ( ) ( )log ( ) 1 1 2 1 i j m j n i j i j m j j j H X Y p y H X y p y p x y p x y = = = = = −
若将X视作一个系统的输入空间,y视作 是系统的输出空间。在通信中,通常将 条件熵H(XY)称作含糊度 ( Equivocation),将条件熵H(|x)称为 散布度( Divergence),×和Y之间的平 均互信息八X1)=H(x)-HX表示×熵减少量
• 若将X视作一个系统的输入空间，Y视作 是系统的输出空间。在通信中，通常将 条件熵H(X|Y)称作含糊度 (Equivocation)，将条件熵H(Y|X)称为 散布度（Divergence），X和Y之间的平 均互信息 I(X,Y) = H(X) − H(X Y) 表示X熵减少量