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

九、密码学中的熵关系

定理2.10

设$(P,C,K,E,D)$是一个密码体制，那么有$H(K|C)=H(K)+H(P)-H(C)$
即截获密文后，密钥的熵等于明文的熵加密钥的熵减密文的熵（密钥含糊度）

证明：
由定理2.8：$H(K|C)=H(KC)-H(C)$
明文与密钥之间没有任何统计规律，故有$H(KP)=H(K)+H(P)$
由密码体制的性质，当明文和密钥已知时，密文也随之确定，则有$H(C|KP)=0$（信息量为0）
同理当密文与密钥已知时，明文也随之确定，故$H(P|KC)=0$
由定理2.8：$H(PKC)=H(P|KC)+H(KC)=H(KC),H(CKP)=H(C|KP)+H(KP)=H(KP)$
故有$H(KC)=H(KP)=H(K)+H(P)$
故$H(K|C)=H(K)+H(P)-H(C)$，证毕。

一般密码体制与熵有关的性质

1. $|P|\le|C|$（从明文空间到密文空间必为单射）
2. $H(P|KC)=H(C|KP)=0$（见定理2.10证明部分）
3. $H(PK)=H(P)+H(K)$（见定理2.10证明部分）
4. 定理2.10结论
5. $H(P)\le H(C)\le H(P)+H(K)$（$H(K|C)\le H(K)$，由定理2.10推出）
6. $H(P|C)\le H(K|C)$

推论：若$|P|=|C|$，且P随机等概率分布，则C一定随机等概率分布。此时$H(K|C)=H(K)$
对于完善保密体制，还有下面的性质：

7. $H(P|C)=H(P)$
8. $|P|\le |C|\le |K|(Pr[y|x]=Pr[y]>0)$
9. $H(P)\le H(C)\le H(K)$

6.证明：

$$H(K|C)=H(KC)-H(C),H(P|C)=H(PC)-H(C)\\ 即证H(KC)\ge H(PC)\\ H(KPC)=H(PC)+H(K|PC)=H(KC)+H(P|KC)\\ H(P|KC)=0,H(K|PC)>0\Rightarrow H(KC)\ge H(PC)$$

9.证明：密钥随机等概率分布且由8可知，$H(C)\le H(K)$
$H(P)=H(P|KC)+H(PK)+H(CP|K)=H(C|K)\le H(C)$(???)

上图中：
绿+紫=$I(X;Y)$；蓝+紫=$I(Y;Z)$；青+紫=$I(X;Z)$
绿=$I(X;Y|Z)$；蓝=$I(Y;Z|X)$；青=$I(X;Z|Y)$
红=$H(X|YZ)$；橙=$H(Y|XZ)$；黄=$H(Z|XY)$
紫=$I(X;Y;Z)$
红+青=$H(X|Y)$；橙+蓝=$H(Y|X)$；
红+绿=$H(X|Z)$；黄+蓝=$H(Z|X)$；
橙+绿=$H(Y|Z)$；黄+青=$H(Z|Y)$；
除黄所有=$H(XY)$；除红所有=$H(YZ)$；除橙所有=$H(XZ)$
青+紫+蓝=$I(XY;Z)$；绿+紫+蓝=$I(XZ;Y)$；绿+紫+青=$I(YZ;X)$
红+绿+橙=$H(XY|Z)$；红+青+黄=$H(XZ|Y)$；橙+蓝+黄=$H(YZ|X)$

十、伪密钥

明文串每个分组使用同一个密钥加密得到密文串，考虑唯密文攻击方式，明文为某自然语言时，分析者可以排除某些密钥，但依然存在多个密钥使得明密文满足加解密函数时，其中只有一个密钥是正确的。称其他那些可能但不正确的密钥为伪密钥。（如移位密码对于不同的密钥有不同语义的单词明文出现）
（获得同一密钥加密的密文越长，存在伪密钥的可能性越小）

十一、自然语言的熵

有随机符号序列$X=X_1X_2...X_n$，其中$X_i\in \{x_1,x_2,...,x_m\}$
单符号信源：仅有一个信号的信源，信号的种类服从一个概率分布。
多符号信源：有多个符号的信源。
非平稳信源——相同字符在不同位置的统计规律也不同：

$$H(X_1X_2...X_n)=H(X_1)+H(X_2|X_1)+H(X_3|X_2X_1)+...+H(X_n|X_1X_2...X_{n-1})$$

若各维联合概率分布与时间起点无关，则称为离散平稳信源。有

$$H(X_iX_{i+1}...H(X_{i+n-1}))=H(X_jX_{j+1}...X_{j+n-1})$$

无记忆信源：每个符号统计独立，其熵值等于每个符号的熵之和。
有记忆信源：每个符号的统计规律有一定的关联
极限熵：当序列长度趋近于无穷大时，其中每一个字符的平均熵值：

$$H_{\infty}=\lim_{n\rightarrow\infty}\frac{1}{n}H(X_1X_2...X_n)=\lim_{n\rightarrow\infty}\frac{1}{n}H(X_n|X_1X_2...X_{n-1})$$

马尔可夫信源：如果x_i只与前面的m个信号（x_i-1，…，x_i-m）相关，则称为马尔可夫信源

$$H(X_n|X_1X_2...X_{n-1})=H(X_n|X_1X_2...X_{n-m})$$

若英语中每个字母是随机使用的，则其熵$H_0=\log_226=4.7$。但实际上根据每个英文字母在英文中出现的概率计算，英文字母的熵为4.19。随着统计字母组的长度增加，字母平均熵值呈下降趋势，当长度达到一定量时，熵值趋于稳定。

若定义$P^n$为n字母序列的概率分布构成的随机变量，则$H(P^n)$表示以n个字母为统计对象的熵值，其除以n表示以n个字母为统计对象时，单字母的平均熵
定义自然语言L的熵为$H_L=\lim_{n\rightarrow\infty}\frac{H(P^n)}{n}$
统计得出大概范围为1.0~1.5，取1.25

自然语言冗余度：

$$R_L=1-\frac{H_L}{\log_2|P|}=\frac{H_0-H_L}{H_0}$$

其中$H_0-H_L$称为语言冗余
英语约为0.75

唯一解距离：使得伪密钥期望值为0所需要的密文分组数量，即在给定足够的计算时间下分析者能够唯一计算出密钥所需明文的平均数量。

$$H(K|C^n)=H(K)+H(P^n)-H(C^n)\\. H(P^n)=nH_L(P)=n(1-R_L)\log_2|P|,H(C^n)\le n\log_2|C|\\ H(K|C^n)\ge\log_2|K|-nR_L\log_2|P|$$

令$H(K|C^n)=0$得

$$n\ge \frac{\log_2|K|}{R_L\log_2|P|}$$

唯一解距离$n_0=\frac{\log_2|K|}{R_L\log_2|P|}$

十二、乘积密码体制

对于两个密码体制$S_1,S_2$，其明文空间和密文空间相同（内嵌式密码体制），$S_1=(P,P,K_1,E_1,D_1),S_2=(P,P,K_2,E_2,D_2)$，则$S_1$和$S_2$的乘积密码体制定义为$S_1\times S_2=(P,P,K_1\times K_2,E,D)$

$$e_{(k_1,k_2)}(x)=e_{k_2}(e_{k_1}(x))\\ d_{(k_1,k_2)}(x)=d_{k_1}(d_{k_2}(x))$$

（实际上就是将明文先用S₁加密后再用S₂加密。）

幂等密码体制

使用一个密码体制将明文加密两次即为S²，加密n次则为Sⁿ。
若S²=S则称该密码体制幂等，与自身做乘积无法提高算法安全性。
古典密码中的移位、代换、乘法、仿射、置换、维吉尼亚、希尔密码均为幂等。
若S₁和S₂为幂等的且为可交换的，则$S_1\times S_2$也是幂等的
如果密码体制不是幂等的，那么可以通过与自身作多次乘积运算（迭代）来提高安全性（注意：这里的相等定义要注意，不是说选择一个密钥，将一个明文加密两次和加密一次得到的密文相等）
一种构造简单非幂等密码体制的方法是对两个不同的简单密码体制做乘积（必须保证两个密码体制不是可交换的）

证明两个内嵌式密码体制相等的方法：首先二者的明文空间相同，其次存在一个双射函数使两者密钥空间中的密钥一一对应相等。（两个密钥空间相互包含也可证明两密钥空间相等）[K相等且同分布]