密码学基础 Chapter 2——香农理论（一）

Chapter 2 Shannon理论

评价密码体制的安全性：
- 计算安全性：从计算上衡量密码体制的安全性
- 可证明安全性：通常使用规约法证明方案安全性
- 无条件安全：提供无限计算资源也无法攻破
上面三种安全性依次递增。

一. 密文概率

在密文中出现某一个字符的概率，与明文分布和密钥分布决定，即$P(Y=y)$可以由$P(X=x),P(K=k)$推导

推广公式为：（全概率公式应用）

$$P(Y=y)=\sum_{k:y\in C(k)}P(K=k)P(X=d_k(y))$$

若密钥K随机等概率获取，则密文C不一定随机等概率。因为明文出现的概率未知。
若密文C等概率获取，则明文P不一定随机等概率。如下例：

	a	b	c	d	e
k1	e	d	c	b	a
k2	a	b	c	d	e

$$Pr[a]=0.1, Pr[b]=0.15, Pr[c]=0.2, Pr[d]=0.25, Pr[e]=0.3\\ Pr[k1]=Pr[k2]=0.5$$

密文等概率，但明文并不随机等概率

若明文P随机等概率获取，则密文C不一定随机等概率。证明如下：
如果$|P|=|C|$则一定等概率，否则不一定。
证明：
首先证明当$|P|=|C|$时，密文一定随机等概率
对于任意一密文字符$c\in C$，设密钥空间$K$中密钥$k_i$的概率为$t_i$，设$e_i(x_{j})=y_k$，所有明文字符取值概率均为$p$。由于对于任意$k_i\in K$，$|C|\rightarrow |P|$是一个双射，因此给定$k,\forall y\in C,\exist x\in P,e_k(x)=y$，即$\forall y\in C,\forall k\in K,\exist x\in P,e_k(x)=y$。故

$$Pr[y=y_k]=\sum_K k_ix_{j}=\sum_K k_ip=p$$

故所有密文字符取值概率相等。
当$|P|\ne |C|$时，举出以下反例：

	a	b	c
k1	1	2	5
k2	4	5	6

理解的关键在于此时$C\rightarrow P$不再是双射，对于一个密文可能不存在k能使其解密为任何一个明文，上面的算式就不成立了。

二. 完善保密性

一个密码具有完善保密性的必要条件：分析者无法通过观察密文得到明文。

单表代换密码不具有完善保密性，原因是明文和密文具有相同的概率分布特性。

定义：一个密码体制具有完全保密性，如果对于任意$x\in P$和$y \in C$，都有$Pr[x|y]=Pr[x]$，即密文字符随机变量与明文字符随机变量独立（或说明文x的后验概率等于其先验概率）

后验概率通过贝叶斯公式计算：

$$P(x|y)=\frac{P(xy)}{P(y)} =\frac{P(xy)}{\sum_{x_i\in X} P(x_i)P(y|x_i)} =\frac{P(x)P(y|x)}{\sum_{x_i\in X} P(x_i)P(y|x_i)} =\frac{P(x)\sum_{\{k:x=d_k(y)\}}P(K=k)}{\sum_{k:y\in C(k)} P(K=k)P(X=d_k(y))}$$

解释一下上式：
通过贝叶斯公式易得第三个等号后的式子，对于最后一个式子的变形：首先看分子，它表示明文字符为x且密文字符为y的概率。满足这种条件的密钥可能不止一个，因此可以将$P(y|x)$改写为满足这种条件的密钥的总概率，即$\sum_{\{k:x=d_k(y)\}}P(K=k)$。对于分母，它表示密文字符y的出现概率，对于每一个密钥，其都对应一个明文字符，使得该明文字符加密后成为该密钥字符y。因此可以将分母改写为密钥概率乘以对应明文出现概率。

定义的含义：

1. 明文x和对应密文y具有统计独立关系
2. 明密文之间的互信息$I(x,y)=0$（类似于相关系数）
3. 攻击者分析y的统计规律无法推导出x

例：对于下面的加密系统，判断是否完善保密。

	a	b	c	d
k1	1	2	3	4
k2	2	3	4	5
k3	3	4	5	1
k4	4	5	1	2
k5	5	1	2	3

其中$Pr[a]=\frac{1}{2},Pr[b]=\frac{1}{4},Pr[c]=Pr[d]=\frac{1}{8}$，密钥等概率。

解： 计算略，完善保密。因为每一个明文被加密为任何一个密文的概率相等，因此对于每一个密文，其对应的明文为x的概率即为明文出现的概率。

三、完善保密性相关定理

定理1：假设移位密码的26个密钥以相同概率随机使用，对于任意的明文概率分布，移位密码都具有完善保密性。

证明：

要证明完善保密性，即证明对于任意$x\in P$和$y \in C$，都有$Pr[x|y]=Pr[x]$，其等价于对于任意$x\in P$和$y \in C$，都有$Pr[y|x]=Pr[y]$。由于明文概率未知，因此$Pr[x]$无法确定，故证明其等价命题。

由全概率公式：
$Pr[y]=\sum_{k\in Z_{26}}Pr[K=k]Pr[X=d_k(y)=(y-k)\mod 26]\\ =\frac{1}{26}\sum_{k\in Z_{26}}Pr[X=(y-k)\mod 26]\\ =\frac{1}{26}$

$Pr[y|x]=Pr[K=(y-x)\mod 26]=\frac{1}{26}$

证毕。

定理2：假设密码体制$(P,C,K,E,D)$满足$|K|=|C|=|P|$（$|K|\ge |C|\ge |P|$是完全保密的必要条件）。这个密码体制是完善保密的，当且仅当每个密钥被使用的概率相等，均为$\frac{1}{|K|}$，且对于任意$x\in P,y\in C$，均存在唯一密钥$k$，使得$e_k(x)=y$。

证明：

充分性：见定理1的证明

必要性：该密码体制具有完全保密性，故$Pr[y|x]=Pr[y]$，这表示对于任意的$x\in P,y\in C$均存在$k\in K$使得$e_k(x)=y$（否则$Pr[y|x]=0$，与$Pr[y]>0$矛盾）
又如果存在有两个$k_1,k_2\in K$，均有$e_k(x)=y$，由于|C|=|K|，则就存在有$y^*\in C$，不存在$k\in K$，使得$e_k(x)=y^*$，与$Pr[y]>0$矛盾
故对于一个确定的$x\in P$，能够建立双射$Q:K\rightarrow C$，$Q(k)=y$表示$k(x)=y$。

k不变时，x与y对应证法
由于$Pr[y|x]=Pr[y]$，对于确定的$x$，$Pr[y|x]=Pr[k\in K:e_k(x)=y]=Pr[y]$。如果改变x的值，可以得到：对于确定的k，有$Pr[k]=Pr[y_1]=Pr[y_2]=...=Pr[y_n]$，对于每个$k$均是如此，故密钥取值概率相等，均为$\frac{1}{|K|}$

y不变时，x与k对应证法
由贝叶斯公式：

$$Pr[x_i|y]Pr[y]=Pr[y|x_i]Pr[x_i]\Rightarrow Pr[y]=Pr[y|x_i]=Pr[k\in K:e_k(x_i)=y]$$

遍历x时，也能够遍历k。故所有密钥概率均为$Pr[y]$

四、一次一密密码体制

定义：
$P=C=K=(Z_2)^n$
$e_k(x)=(x_1+k_1,x_2+k_2,...,x_n+k_n)\mod 2$
$d_k(x)=(y_1+k_1,y_2+k_2,...,y_n+k_n)\mod 2$
可根据定理2证明其完善保密性。

五、完善保密性判定定理

假设密钥只使用一次

定理1：对密码体制$(P,C,K,E,D)$，若对于任意$x\in P,y\in C$，有$\sum_{k:x=d_k(y)}Pr[k]=\frac{1}{|P|}$，则该密码完善保密。

证明：

$Pr[y|x]=\sum_{k:y=e_k(x)}Pr[k]=\frac{1}{|P|}$
由全概率公式：$Pr[y]=\sum_{k:y=e_k(x)}Pr[x]Pr[y|x]=\frac{1}{|P|}$

深层理解：定理1与定理4的区别是：定理1的条件是充分条件，但无需满足$|P|=|C|$的条件。如果$|P|\ne |C|$，上述结论仍可能成立，唯一的区别是$Pr[y|x]=Pr[y]\ne \frac{1}{|P|}$。由密码体系定义可知，对于任何密码系统，均有$|P|\le|C|$。对于给定的$x\in P$，由全概率公式可知：$Pr[x]=\sum_{y_i\in C} Pr[y_i]Pr[x|y_i]=\sum_{y_i\in C}Pr[y]Pr[k:e_k(x)=y_i]$，易得此时$Pr[y_i]$不可能恒为$\frac{1}{|P|}$，否则$\sum_C Pr[y_i]>1$，这显然不可能。

---

定理2：对于密码体制$(P,C,K,E,D)$，$K$等概率选取，若对于任意的$x\in P,y\in C,|{k:x=d_k(y)}|=\frac{|K|}{|P|}$，则该密码体制完善保密。

证明：

$Pr[y|x]=\sum Pr[k:x=d_k(y)]=\frac{1}{|K|}\cdot \frac{|K|}{|P|}=\frac{1}{|P|}$
$Pr[y]=\sum_{x_i\in P} Pr[x_i]Pr[y|x_i]=\frac{1}{|P|}$

深层理解：定理2与定理3的区别于定义1和定理4的区别类似，没有限定$|P|=|C|$。如果二者不等，则存在有密码体制满足$|{k:x=d_k(y)}|\ne\frac{|K|}{|P|}$，但也满足上述结论。当其等于$\frac{|K|}{|C|}$时易证其也成立。

---

定理3：对于密码体制$(P,C,K,E,D)$，$|P|=|C|$，$K$等概率选取，当且仅当对于任意的$x\in P,y\in C,|{k:x=d_k(y)}|=\frac{|K|}{|P|}$，该密码体制完善保密。

证明：充分性已证明。
必要性：若该密码体制具有完全保密性，则$Pr[y]=Pr[y|x]$，由于$K$等概率选取，因此对于任意$x\in P,y\in C$有$|{k:x=d_k(y)}|$均相等。由于此时$|P|=|C|$,因此对于给定的$x$，可将$k$分为数量相等（均为$|{k:x=d_k(y_i)}|$）的$|C|$份，每一份中的$k$加密$x$均可得到相同的$y$，不同份中的$k$加密$x$得到不同的$y$。因此显然有$|{k:x=d_k(y)}|=\frac{|K|}{|P|}$

---

定理4：对于密码体制$(P,C,K,E,D)$，$|P|=|C|$，且明文$|P|$等概率选取。当且仅当对于任意$x\in P,y\in C$，有$\sum_{k:x=d_k(y)}Pr[k]=\frac{1}{|P|}$，该密码体制完善保密。

证明：充分性已证明。
必要性：$Pr[y]=\sum Pr[k_i]Pr[x_j]=\frac{1}{|P|}\sum Pr[k_i]=\frac{1}{|P|}$

深层理解：这里需要两个条件，一个是明文空间和密文空间元素个数相等，另一个是明文等概率选取。如果明文不等概率会怎样呢？此时必要性就无法成立，那能否举一个不满足此充分条件又能够使结论成立的条件呢？。设第一个条件仍然成立，$x_i$的出现的概率为$Pr[x_i]$，此时证明$Pr[x]=Pr[x|y]$。对于给定的$x^*\in P$，$Pr[x^*]$已知，设为$P$，那么$Pr[x^*|y]=\frac{Pr[x^*y]}{Pr[y]}=\frac{\sum Pr[k:x^*=d_k(y)]Pr[x^*]}{Pr[y]}=P$。要使得$Pr[x^*|y]=Pr[x^*]$，则有$Pr[y]=\sum Pr[k:x^*=d_k(y)]$，即对于任意密文字符$y$，其出现的概率均等于能够将$y$解密为$x^*$的全部密钥的出现概率。

六、 自信息量

• 信息量
  • 对信息的直观认识
    • 信道上传送随机变化的值
    • 时间发生概率与信息量的关系
    • 消息间的依赖关系与相互之间的信息量
    • 信息消除不确定性
    • 信息可加

• 自信息量
  单符号离散信源的数学模型可用一位随机变量$X$的概率空间描述，即每个$x\in X$均对应一个概率$p(x_i)$，如果信源发出消息$x_i$的概率为$p(x_i)$，则其能提供的自信息量（自信息）为：（式中的底数可以换，这里由于使用比特作为信息媒介，因此使用2作为底数。如果使用10进制数字，则就应使用10作为底数，即底数由媒介的可能取值数决定）

$$I(x_i)=\log_2\frac{1}{p(x_i)}=-\log_2p(x_i)$$

理解：信源发出信号前信宿对消息的不确定，信源发出信息后提供给信宿的信息量，即消除不确定性所需要的信息量。如可能的情况一共8种，那么自然需要3个比特才能表示所有状态，能够确定这个信息属于什么状态。

• $I(x_i)$的性质：

  • 非负
  • $P(x_i)=1$时$I(x_i)=0$
  • $P(x_i)=0$时$I(x_i)=+\infty$
  • 是$p(i)$的单调递减函数

• 联合自信息量

  • 涉及多个随机变量$X_i$，其中每一个联合事件均有一个概率
  • $I(x_1x_2...x_n)=-\log_2p(x_1x_2...x_n)$
  • 当这些变量均独立时，$I(x_1x_2...x_n)=I(x_1)+I(x_2)+...+I(x_n)$

• 条件自信息量

  • 类比条件概率
  • 后验概率：$I(x_i|y_j)=-\log_2p(x_i|y_j)$
  • 信道转移概率：$I(y_j|x_i)=-\log_2p(y_j|x_i)$
  • $I(x_iy_j)=-\log_2p(y_j|x_i)p(x_i)=I(x_i)+I(y_j|x_i)=I(y_j)+I(x_i|y_j)$

• 互信息量

  • $I(x_i;y_j)=I(x_i)-I(x_i|y_j)=\log_2\frac{p(x_i|y_j)}{p(x_i)}$，即先验不确定度$-$后验不确定度

直观理解：

自信息量：信息本身发生的概率决定本信息的可识别度。信息发生的概率越高，可识别度越低，只需要很少的比特位就可以将其完全表示，提供给我们的信息也越少；信息发生的概率越低，可识别度越高，需要更多的比特位来表示，提供给我们的信息也越多。我们可以想象一下，如果一个事件一定发生，那这个时间对于我们没有价值，因为我们不需要任何信息就知道它一定发生；如果一个事件很难发生，比如中彩票，只要发生，就能提供具有很强识别度的信息，中彩票之后，你可以买车，买很多东西都可以，但是不中的话，也就只是不中而已，生活照常进行没有任何影响。我们可以粗略地将每一个比特位看成概率的划分，如对于2位比特位，其有00,01,10,11四种状态，可以将整个概率空间1分为4个部分，每个部分代表25%概率。假设有4个事件，概率均为25%，且任意两个事件不可能同时发生（想象成箱子中有4个球，随机拿一个球）。此时，如果我们只给出一个比特位，如0，它能确定我们拿出来的是什么球吗？显然不能，因为一个比特位只有两种状态：0和1。如果将2位比特位与摸出的球的编号一一对应，那么一位比特位就能够代表摸出某2个球，但不可能是剩下2个球。我们虽然不能通过1个比特位确定到底拿的是什么球，但至少缩小了范围，当然这还不够。如果我们能够知道两个比特位，那么我们就能够最终确定我们拿出来的是什么球。

注意！每一个比特位对于概率的分配都是均分，不存在对于一个比特位中0和1表示不同的概率。

我们考虑一种最为普通的情况：事件A发生的概率为90%，那么我们只需要1个比特位就能够确认事件A是否发生。如果将0代表为A发生，那么1就代表A一定不发生吗？那可未必。A发生的概率是90%，比特位为0的概率为50%，因此如果比特位为1，那么A发生的概率还有80%（条件概率），但是此时A是否发生就是不确定的了。不过我们并不需要考虑1的情况，因为0就足以确认A发生。如果我们要表示A不发生的概率，那么就至少需要4个比特位，4个比特位共有16种状态，其中至多可以有一个状态能被完全包含在A不发生的概率之中，这也就确定了A不发生。

联合自信息量：理解了自信息量之后，联合自信息量也就不难理解。不过是将一个随机变量变成了多个而已。

条件自信息量：需要分先验和后验进行理解。先验的条件自信息量以先验概率为基础计算，又称信道转移概率。举一个通俗的例子：假如在某地冬天，一天气温低于0度的概率为30%，在低于0度的情况下，附近一条河流结冰的概率为80%。如果我们抛开气温不管只看河流是否结冰，此时河流结冰的概率应为24%，通过河流结冰，我们能够获得较多信息，比如今天大概率很冷。但如果我们已经知道了今天温度低于0度，再看到河流结冰时，能够获取的信息就不多了，因为此时河流结冰几乎是自然而然发生的事情，不需要任何怀疑。相反地，后验的条件自信息量以后验概率为基础计算，与先验概率的理解类似。还是上面的例子，今天河流结冰了，那么如果今天温度高于0度，那就很值得研究了，因为这种情况理论上是不可能发生的。

互信息量：表现两个随机变量之间的联系。为随机变量X的先验不确定度$-$后验不确定度。如果互信息量大于0，说明Y的发生减少了X提供的信息量。如果小于0，说明Y的发生增加了X提供的信息量。因为X和Y如果有联系，那么Y的发生可能会改变X发生的概率。

七、熵

定义：随机变量X的信息熵定义为自信息量$I(x)$的数学期望，简称熵。

$$H(X)=E[I(x)]=-\sum_{x\in X}p(x)(\log_2p(x))$$

理解：

• 熵非负
• 信源发出前，表示信源的平均不确定度
• 信源发出后，表示信源提供的平均信息量
• 是一个统计量，反映了随机变量$X$的随机性

定理2.6

假设随机变量$X$的概率分布为$p_1,p_2,...,p_n$，则$H(X)\le \log_2n$，当且仅当$p_i=\frac{1}{n}$时等式成立

证明：
使用琴生（Jensen）不等式：在上凸函数中，有$\sum_{i=1}^na_if(x_i)\le f(\sum_{i=1}^na_ix_i),\sum_{i=1}^na_i=1,a_i>0$，当且仅当$x_1=...=x_n$时等号成立
由上述不等式可知

$$H(X)=\sum_{i=1}^np_i(\log_2\frac{1}{p_i})\le \log_2(\sum_{i=1}^n(p_i\cdot\frac{1}{p_i}))=\log_2n$$

当且仅当$p_i=\frac{1}{n}$时等式成立，证毕。

• 联合熵：两个随机变量的熵。性质：

$$\max[H(X_1),...,H(X_n)]\le H(X_1X_2...X_n)\le H(X_1)+...+H(X_n)$$

定理2.7

$H(XY)\le H(X)+H(Y)$，当且仅当$X$和$Y$统计独立时等号成立

证明：设$Pr[X=x_i,Y=y_j]=r_{ij},Pr[X=x_i]=p_i,Pr[Y=y_j]=q_j$
$H(XY)=\sum_{i=1}^m\sum_{j=1}^nr_{ij}\log_2\frac{1}{r_{ij}}$
$H(X)=\sum_{i=1}^mp_i\log_2\frac{1}{p_i}=\sum_{i=1}^m\sum_{j=1}^nr_{ij}\log_2\frac{1}{p_i}$
$H(Y)=\sum_{j=1}^nq_j\log_2\frac{1}{q_j}=\sum_{j=1}^n\sum_{i=1}^nr_{ij}\log_2\frac{1}{q_j}$
$H(XY)-H(X)-H(Y)=\sum_{i=1}^m\sum_{j=1}^nr_{ij}\log_2\frac{p_iq_j}{r_{ij}}\le \log_2(\sum_{i=1}^m\sum_{j=1}^np_iq_j)=0$

• 条件熵：$H(X|Y)=-\sum_{x\in X}\sum_{y\in Y}p(xy)\log_2p(x|y)$
  • 对于Y的任意取值y得到一个X上的条件概率分布，相应的随机变量即为$X|y$，可知

$$H(X|y)=-\sum_{x\in X}p(x|y)\log_2p(x|y)$$

- 上式对y加权平均即得到$H(X|Y)$的值

定理2.8

$H(XY)=H(Y)+H(X|Y)$

证明：两边分别展开易证

推论2.9

$H(X|Y)\le H(X)$，当且仅当$X$和$Y$统计独立时等号成立。

证明：

$$H(X|Y)=-\sum_{x\in X}\sum_{y\in Y}p(xy)\log_2p(x|y)=\sum_{x\in X}\sum_{y\in Y}p(xy)\log_2\frac{p(y)}{p(xy)}=\sum_{x\in X}\sum_{y\in Y}p(x)p(y|x)\log_2\frac{p(y)}{p(xy)}\\ H(X)=\sum_{x\in X}p(x)\log_2\frac{1}{p(x)}$$

即证

$$\sum_{x\in X}\sum_{y\in Y}p(y|x)\log_2\frac{p(y)}{p(xy)}\le \sum_{x\in X}\log_2\frac{1}{p(x)}$$

即证

$$\sum_{x\in X}\sum_{y\in Y}p(y|x)\log_2\frac{p(x)p(y)}{p(xy)}\le 0$$

即证

$$\sum_{x\in X}\sum_{y\in Y}p(y|x)\log_2\frac{p(y)}{p(y|x)}\le 0\\ \sum_{x\in X}\sum_{y\in Y}p(y|x)\log_2\frac{p(y)}{p(y|x)}\le \sum_{x\in X}\log_2(\sum_{y\in Y}p(y))=\sum_{x\in X}\log_21=0$$

证毕

八、平均互信息量

$I(X;Y)$定义为互信息量在联合概率空间上的数学期望

$$I(X;Y)=E[I(x;y)]=\sum_{x\in X}\sum_{y\in Y}p(xy)I(x;y)\\ =H(X)-H(X|Y)=H(Y)-H(Y|X)=H(X)+H(Y)-H(XY)$$

$$\sum_{x\in X}\sum_{y\in Y}p(xy)I(x;y)=\sum_{x\in X}\sum_{y\in Y}p(xy)\log_2\frac{p(xy)}{p(x)p(y)}\\ H(X)=\sum_{x\in X}p(x)\log_2\frac{1}{p(x)}=\sum_{x\in X}\sum_{y\in Y}p(xy)\log_2\frac{1}{p(x)}\\ H(Y)=\sum_{y\in Y}p(y)\log_2\frac{1}{p(y)}=\sum_{x\in X}\sum_{y\in Y}p(xy)\log_2\frac{1}{p(y)}\\ H(XY)=\sum_{x\in X}\sum_{y\in Y}p(xy)\log_2\frac{1}{p(xy)}$$

性质：

• 非负
• 对称：$I(X;Y)=I(Y;X)\le \min\{H(X),H(Y)\}$
• 当X,Y概率独立时，$I(X;Y)=0$
• 当X,Y存在有一一对应关系时，$I(X;Y)=H(X)=H(Y)$

平均条件互信息量：$I(X;Y|Z)=I(X;YZ)-I(X;Z)$