密码学基础 Chapter 1——古典密码学

Chapter 1 古典密码学

一、概念

1. 密码学是提供安全服务的关键理论和技术，包含：数据机密性、数据完整性、鉴别、不可否认等。
2. 密码学与隐写术的区别：隐写术通过隐藏消息的存在来保护消息，常用手段有：隐形墨水、字符格式变化、图形图像等，而密码学是将消息本身加密成为密文后发送，可以隐藏，也可以不隐藏，关键不在于隐藏，而在于解密。
3. 发送者将消息通过不安全信道发送给接受者，想要确保除了接受者之外没有其他人能够阅读发送的消息。
4. 明文：要传输的消息；密文：加密后的消息；加密：用某种方法伪装消息以隐藏其内容的过程；解密：将密文还原为明文的过程；秘钥：预先确定的用于加解密过程的参数。
5. 加密算法：对明文加密操作采用的一组规则；解密算法：对密文解密采用的一组规则；密码算法：用于加密和解密的数学函数。
6. 按明文处理方式可将密码分为分组密码和流密码。分组密码事先将明文分成若干组，对每组采用同样的加密方式加密，再将每组加密的密文相接形成密文。流密码分组后对每一组使用不同加密方式加密，然后将密文相接形成总的密文。按明文保密条件可分为受限制算法和基于秘钥算法。
   (1) 受限制的算法：安全性基于算法的保密性（这种密码实际上并不安全）
   (2) 基于密钥的算法：安全性基于密钥的安全性，算法本身可以公开。基于密钥的算法通常分为对称密码算法和公开密钥算法（Kerckhoffs假设）。其中对称加密算法是指加密密钥和解密密钥相同或可以互相推导的密码算法，公开密钥算法的加密密钥和解密密钥实质不同，已知信息下无法相互推导（非对称密钥算法）。
7. 加密通信模型：Alice和Bob双方通过加密机和解密机进行密文解密和明文加密，将密文通过不安全信道传输，不安全信道中有攻击者Oscar截获明文。对称密钥系统存在一个密钥源为Alice和Bob双方分配密钥，分配密钥的过程完全安全，Oscar无法窃听；非对称密钥系统中的密钥源是公开的，任何人都能够互获取，但Alice和Bob都有自己不公开的私钥用于解密。
8. 密码体制数学描述：
   一个五元组$$(P, C, K, E, D)$$满足条件：
   (1) P为可能明文的有限集（明文空间）
   (2) C为可能密文的有限集（密文空间）
   (3) K为一切可能密钥构成的有限集（密钥空间）
   (4) E是加密算法的有限集
   (5) D是解密算法的有限集
   (6) 对 $\forall k \in K , \exist e_k \in E, \exist d_k \in D \Rightarrow e_k: P \rightarrow C, d_k: C \rightarrow P, d_k(e_k(x)) = x (x \in P)$ （加密函数必须为单射函数，否则一个明文可能解密出多个密文）
9. 古典密码实现技术：
   (1) 代换：加密将明文字符按对应关系代换为对应的密文字符，解密则反过来操作。密钥为明密文字符之间的对照关系。包含：单表代换、多表代换（维吉尼亚密码）、多字符代换等。
   (2) 置换：将明文字符按照一定规则移动位置得到密文，字符本身不变。解密则反过来进行。密钥为移位规则。

二、几种古典密码

1. 移位密码
   将字母表中每个字母向后移动若干位作为密文字符。可通过密文字符频率分析破解或暴力破解（唯密文攻击）$a b$
   数学描述：
   $P = C = K = Z_{26}$
   对$k, x, y \in Z_{26}$，定义有
   $e_k(x) = (x+k) \mod 26$
   $d_k(y) = (y-k) \mod 26$
   k=3时称为凯撒密码
2. 代换密码
   建立一个明文字符与密文字符的一一对应关系，将明文对应字符替换为密文字符。也可以通过密文字符频率破解（唯密文攻击）
   数学描述：
   $P = C = Z_{26}$
   K是由26个数字0, 1, … 25所有可能的置换组成
   对任意置换$\pi \in K$，定义有
   $e_\pi(x) = \pi(x), d_\pi(y) = \pi^{-1}(y)$
3. 仿射密码
   其机制与移位密码类似，将明文字符通过模线性变换ax+b成为密文字符。可通过密文字符频率破解（唯密文攻击）
   数学描述：
   $P = C = Z_{26}$
   $K=\{(a,b)\in Z_{26}\times Z_{26}: \gcd(a,26)=1\}$
   对$\forall k=(a,b)\in K， x,y\in Z_{26}$，定义
   $e_k(x)=(ax+b)\mod 26, d_k(y)=a^{-1}(y-b)\mod 26$
   其中$\gcd(a,26)=1$是为了满足单射的条件。
   当a=1时即为移位密码
4. 维吉尼亚密码
   维吉尼亚密码选择一个字符串作为密钥，并将明文按照字符串长度分为长度相等的若干组，对于每一组中的明文字符，按照对应位置密文的字母确定移位数量。破解方式较上述三种复杂，但仍能进行唯密文攻击。
   数学表述：
   $P = C = K = (Z_{26})^m$，m为正整数
   对$\forall k=(k_1, k_2, ..., k_m)\in K, x = (x_1, x_2, ..., x_m)\in P, y=(y_1, y_2, ..., y_m)$，定义有
   $e_k(x)=(x_1+k_1, x_2+k_2, ...,x_m+k_m)$
   $d_k(y)=(y_1-k_1,y_2-k_2,...y_m-k_m)$
   (以上运算均在模26下进行)
5. 希尔密码
   希尔密码的加密方式可以说是仿射密码、移位密码、代换密码的超集。将明文字符串分为长度相等的若干组，对每一组进行相同的矩阵乘法（也就是一种较仿射密码更加复杂的线性变换），获取结果即为密文。
   数学描述：
   $P = C = (Z_{26})^m$，m为不小于2的正整数
   K是定义在$Z_{26}$上的$m\times m$可逆矩阵的集合
   取密钥$k \in K$，k为一个$m\times m$矩阵，记为$(k_{ij})$，对于$x=(x_1, x_2, ..., x_m)\in P, y=(y_1, y_2, ..., y_m)\in C$，定义有
   $e_k(x)=xk, d_k(y)=yk^{-1}$
   (以上运算均在模26下进行)
6. 置换密码
   将明文打乱顺序变为密文。
   数学描述：
   $P = C = (Z_{26})^m$，m为正整数
   K是由所有定义在集合{1, 2, …, m}上的置换组成
   对于任意密钥$\pi$，定义
   $e_\pi(x_1,x_2,...x_m)=(x_{\pi(1)},x_{\pi(2)},...,x_{\pi(m)})$
   $d_\pi(y_1,y_2,..,y_m)=(y_{\pi^{-1}(1)},x_{\pi^{-1}(2)},...,x_{\pi^{-1}(m)})$
   置换密码实际上是希尔密码的特殊形式，其置换矩阵与排列有关。置换矩阵的行数和列数等于一组字符数量，如果这一组中明文第i个位置被换成了第j个位置的元素，则第i列的第j个数为1。

三. 古典密码分析

• 概念
  密码分析：分析者在已知密码体制（密码算法及实现的全部详细资料）的前提下破译使用的密钥。
  常用密码分析攻击有4类：
  唯密文攻击（COA）：攻击者仅掌握密文的攻击
  已知明文攻击（KPA）：攻击者知道不由他控制的明文以及对应的密文
  选择明文攻击（CPA）：攻击者可以在一定程度上选择明文获取密文
  选择密文攻击（CCA）：攻击者可以在一定程度上选择密文获取明文
  这4种攻击方式依次增强，如果一种加密算法能够抵抗后面的攻击，那么也一定能够抵抗前面的攻击。
• 古典密码攻击要点
  只有当密文长度足够长时，才能够分析大多数古典密码。
  只能分析由有具体语义明文加密而来的密文，否则即使解密完成也不知道解密出来的是不是密文。
  通常需要使用英文字母频率分析与反复猜测。
• 英文字母频率规律
  第1档：E出现次数远多于其他字母
  第2档：TAOINSHR
  第3档：CUMWFGYPB
  第4档：VKJXQZ
  常见双字母固定序列：TH HE IN ER AN RE ED ON ES ST EN AT TO NT HA ND OU EA NG AS OR TI IS ET IT AR TE SE HI OF
  常见三字母固定序列：THE ING AND HER ERE ENT THA NTH WAS ETH FOR DTH
  根据经验，有些字母不可能组合出现与同一个单词之中，如j和所有辅音字母相邻的概率都极低。
  根据密文字母出现频率高低进行猜测和验证，得到密文越长，越符合统计规律

1. 仿射密码分析

分析仿射密码需要得到a与b的值，通过密文中字母的出现频率猜测出现频率最高的是什么字母，只需猜测两个字母便可以列方程组求解。注意解a须与26互素，否则猜测错误。

2. 代换密码分析

分析代换密码采用与仿射密码类似的方法，使用字频分析，逐一猜测，根据经验，最早被破译的通常是’the’，要查找文本看看有没有多次存在的3字符序列。

3. 维吉尼亚密码分析

维吉尼亚密码分析较为复杂。由于其是多表代换，因此需要首先确认每一组字符的长度，这里应该使用Kasiski测试法：在密文中找到相同的3字符或以上序列，找出它们所在的起始位置，对这些位置的差求公因数，这些公因数之一就很可能是密钥的长度。

确认密钥字长度m也可以使用重合指数法。

• 重合指数法
  • 在一个字符串X中随机取出两个字母，这两个字母恰好相同的概率记为$I_c(X)$
  • 对于完全随机字符串，$I_c(X)$=1/26，约为0.038
  • 对于英文文本，$I_c(X)=\sum_{i=0}^{25}p_i^2\approx 0.065$
  • 在单表代换密码中，密文的重合指数应该与明文相同。
    将密文按照密钥字长度分为m段，每一段的重合指数应该接近于0.065，通过尝试不同的m可以获取重合指数最为接近0.065的那一个m就是密钥字长度。
  • 对于一段确定的英文文本，计算重合指数的公式为：$I_c(X)=\frac{\sum_{i=0}^{25}f_i(f_i-1)}{n(n-1)}$，其中$f_i$为每个密文字母的出现次数（频数）
  • 确认密钥的长度之后，对于分出来的每一段密文，其中每一个密文字符相对于明文字符的偏移都是相同的。这里仍然可以使用重合指数法计算偏移量。计算方法：密文转换成明文之后，其明文的重合指数应该近似于0.065，因此对于每一个偏移量，均计算一次其与明文的重合指数，最接近于0.065的即为正确偏移量。计算公式：$M_g=\sum_{i=0}^{25}p_i\times \frac{f_{i+g}}{n'}$，其中$p_i$为每个字母在英文中出现的概率，$f_i$是每个字母在密文中出现的次数，$n'$是这一段密文的长度。

4. 希尔密码分析

破译希尔密码的关键是找到转换矩阵，其难以通过唯密文攻击破解，但可以很容易通过已知明文攻击破译。知道明文和密文之后，就可以直接计算出矩阵的值：$Y=XK\rightarrow K=X^{-1}Y$，前提是需要知道密钥矩阵的阶数。

四. 流密码

1. 概念

之前的古典密码中对于连续明文元素使用相同密钥K加密，与分组密码的区别是：需要设计复杂的加密函数提高安全性，而且经常需要对明文进行填充以确保分组长度完整。

流密码将明文看做字符串或者比特串，逐字符或逐位进行加密。为防止密钥穷举，使用与明文长度相等的密钥（无限）流进行加密。关键在于如何生成密钥流。

2. Vernam 密码

密钥与明文一样长且没有统计规律的加密。

加密：$C_i=P_i+K_i\mod 26, C_i=P_i\oplus K_i$
解密：$P_i=C_i-K_i\mod 26, P_i=C_i\oplus K_i$

需要构造与明文一样长的随机密钥。（这样的密钥不能重复，否则无法对抗已知明文攻击）

3. 流密码特点

运算简单，实时性强，安全性依赖于密钥流产生方法

4. 流密码分类

按照密钥周期性分类分为周期流密码和非周期流密码
周期流密码：存在某一个固定正整数r使得密钥流每隔r个字符以后重复
非周期流密码：对于任何正整数密钥都不重复，如一次一密乱码本

按照密钥产生方式分为同步流密码和异步流密码
同步流密码：密钥流的产生独立于消息流，如分组密码中的OFB（输出反馈）模式
异步流密码：每一个密钥字符都是由前面n个明文或密文字符推导出来的，其中n为定值。如分组密码中的CFB（密码反馈）模式

5. 同步流密码

使用某种算法，由一个初始密钥变换出于明文串相互独立的密钥流。数学定义如下：

同步流密码是一个六元组$(P,C,K,L,E,D)$和一个函数$g$，且满足以下条件：

1. $P,C,K$分别为明文、密文、密钥的有限集
2. $L$是密钥流字母表有限集
3. $g$是密钥流生成器，g使用密钥$k\in K$作为输入，产生无限长的密钥流$Z=z_1z_2...$，其中$z_1\in L$
4. 对于任意$z\in L$，都有一个加密规则（函数）$e_z:P\rightarrow C\in E$和相应的解密规则（函数）$d_z:C\rightarrow P\in D$，并且对于每个明文$x\in P$满足$d_z(e_z(x))=x$

6. 流密码与分组密码的关系

分组密码可以用于生成密钥序列
维吉尼亚密码可以看做流密码的一种特殊情况（一种短周期同步流密码，密钥流是周期为m的密钥序列）

7. 密钥流生成

多使用线性递推关系产生伪随机序列（与多种高级语言的随机函数类似），这一类随机函数需要一个种子，被称为初始向量，线性递推算法可以使用硬件实现，此硬件称为线性反馈移位寄存器（LFSR）

8. 异步流密码

同步流密码存在有周期问题，异步流密码的密钥流由于与明文元素或密文元素有关，因此不存在周期问题。

9. 自动密钥密码体制：异步流密码示例

一个六元组$(P,C,K,L,E,D)$，满足：

1. $P=C=K=L=Z_{26}$
2. 密钥流定义：$z_1=k\in K, z_i=x_{i-1}, i\ge 2$
3. 对于$\forall z\in K, x,y\in Z_{26}$，定义

$$e_z(x)=(x+z)\mod 26, d_z(y)=(y-z)\mod 26$$

10.线性移位反馈寄存器(LFSR)

对于流密码，需要通过随机序列进行加密，但真正随机的序列难以应用，一般使用一个种子生成出一个伪随机的流密钥。
这种方式可以通过硬件方式实现，即LFSR，第n+1位由前面n位中某些位的异或得到。

$$a_{n+1}=c_na_1\oplus c_{n-1}a_2\oplus ...\oplus c_1a_n$$

上式中的c_i是固定值。

定义1 周期序列：存在正整数t，满足对于任意的$k\ge 0,a_{k+t}=a_k$，其中最小的正整数t称为序列的周期，序列称为周期序列。
定义2 特征多项式：设q元n级线性反馈移位寄存器的递推公式为：

$$a_{n}=c_na_0\oplus c_{n-1}a_1\oplus ...\oplus c_1a_{n-1},c_i\in F_q,c_n=1$$

其变换矩阵T定义为

$$T=\begin{pmatrix}0 & 0 & 0 & ... & c_n\\ 1&0&0&...&c_{n-1}\\ 0&1&0&...&c_{n-2}\\ ...&...&...&...&...\\ 0&0&...&1&c_1\end{pmatrix}$$

$(a_0,a_1,...,a_{n-1})T=(a_1,a_2,...,a_n)$
矩阵T的特征多项式$f(x)=|xI-T|=x^n-c_1x^{n-1}-...-c_{n-1}x-c_n$称为n级线性反馈移位寄存器L的特征多项式
定义3 设T为F_q上n级LFSR的变换矩阵，I是n×n单位矩阵，使得T^k=I成立的最小的正整数k称为变换矩阵T的周期，记为$\rho(T)$。
定义4 可满足多项式：设$f(x)\in F_q[x],f(0)\ne 0$，如果$f(T)=0$，则称f(x)为T可满足的多项式。所有T可满足的多项式中，次数最低的首1多项式称为T的极小多项式（与信数的极小多项式定义不太相同，这里的多项式不一定不可约），满足$f(x)|x^k-1$的最小正整数称为$f(x)$的周期，记为$\rho(f)$
引理1 设$f(x)\in F_q[x]$是首1不可约多项式，$f(0)\ne 0$，则$\rho(f)$等于有限域$F_q[x]_{f(x)}$中元素x的阶。
引理2 设$f(x)\in F_q[x]$是首1多项式，$f(0)\ne 0,f(x)=g(x)^b$，其中$g(x)$为$F_q[x]$中的不可约多项式，$char(F_q)=p$，t是使得$p^t\ge b$的最小正整数，则有$\rho(f)=\rho(g)p^t$
证明：
$g(x)|x^{\rho(g)}-1$（拉格朗日定理）$\Rightarrow g(x)^{p^t}|(x^{\rho(g)}-1)^{p^t}$
$char(F_q)=p,p^t\ge b,g(x)^{p^t}|(x^{\rho(g)}-1)^{p^t}\Rightarrow f(x)|x^{\rho(g)p^t}-1$
另一方面，$f(x)|x^{\rho(f)}-1,\therefore f(x)|(x^{\rho(f)}-1,x^{\rho(g)p^t}-1)=x^{(\rho(f),\rho(g)p^t)}-1$
$\therefore \rho(f)=(\rho(f),\rho(g)p^t),\rho(f)|\rho(g)p^t$（信数定理，$\rho(f)$应该是满足$f(x)|x^m-1$的最小次数）
同样，$g(x)|f(x)\Rightarrow g(x)|x^{\rho(f)}-1\Rightarrow \rho(g)|\rho(f)$
这说明$\rho(f)$是形如$\rho(g)p^s(0\le s\le t)$的整数
设$\rho(f)=\rho(g)p^s,s<t,p^s<b,f(x)|x^{\rho(g)p^s}-1,g(x)^b|x^{\rho(g)p^s}-1=(x^{\rho(g)}-1)^{p^s}$
$g(x)^{b-p^s}|(\frac{x^{\rho(g)}-1}{g(x)})^{p^s}\Rightarrow g(x)|(\frac{x^{\rho(g)}-1}{g(x)})^{p^s}\Rightarrow g(x)|(\frac{x^{\rho(g)}-1}{g(x)})\Rightarrow g(x)^2|x^{\rho(g)}-1$（说明$x^{\rho(g)}-1$应该有重因式）
$(\rho(g),p)=1,(x^{\rho(g)}-1,(x^{\rho(g)}-1)')=1$
$\therefore x^{\rho(g)}-1$无重因式，矛盾（信数定理）。故原命题成立
引理3 设$f(x)\in F_q[x]$是首1多项式，$f(0)\ne 0$，且$f(x)=\prod_{i=1}^sf_i(x)$，其中$f_i(x)$是$F_q[x]$中两两互素的多项式，则$\rho(f)=[\rho(f_1),\rho(f_2),...,\rho(f_s)]$
证明：
$f_i(x)|x^{\rho(f_i)}-1,\rho(f_i)|[\rho(f_1),\rho(f_2),...,\rho(f_s)]$
$\Rightarrow f_i(x)|x^{[\rho(f_1),\rho(f_2),...,\rho(f_s)]}-1$
$\Rightarrow \rho(f)|[\rho(f_1),\rho(f_2),...,\rho(f_s)]$（$f_i(x)$两两互素！）
又$f_i(x)|f(x),f(x)|x^{\rho(f)}-1$
$\Rightarrow f_i(x)|x^{\rho(f)}-1\Rightarrow \rho(f_i)|\rho(f)$
$\Rightarrow [\rho(f_1),\rho(f_2),...,\rho(f_s)]|\rho(f)$
$\therefore \rho(f)=[\rho(f_1),\rho(f_2),...,\rho(f_s)]$
定理1 设$T$的极小多项式为$h(x)\in F_q[x]$，若$f(x)\in F_q[x]$满足$f(T)=0$，那么$h(x)|f(x)$
定理2 设$T$是$F_q$上n级线性反馈移位寄存器L的变换矩阵，T的特征多项式为$f(x)$，那么$f(x)$是T的极小多项式
定理3 设$T$是$F_q$上n级线性反馈移位寄存器L的变换矩阵，T的特征多项式为$f(x)$，那么$\rho(T)=\rho(f)$
定理4 给定$F_q$上任意一个非零周期序列$a$，可以找到一个能产生序列$a$的线性反馈移位寄存器L，它的特征多项式$f(x)$满足：对于可产生$a$的任意线性反馈移位寄存器，若其特征多项式为g(x)，都有$f(x)|g(x)$。满足上述条件的f(x)唯一
定义5 定理4描述的首1特征多项式f(x)为序列$a$的极小多项式
定理5 非零周期序列$a$的周期等于其极小多项式f(x)的周期

m序列的伪随机性：
(1) 若t为奇数，则0-1序列的一个周期内0的个数比1的个数多1个或少1个，若t为偶数则其个数相等
(2) 在长度为t的周期内，1游程的个数为游程总数的1/2，2游程的个数为总数的1/2²，以此类推。（n游程：连续的n个0或1序列，且前后为1或0。如00110001中第2~3为是一个1的2游程）
(3) 异相自相关函数为常数（自相关函数：定义在Z₂上的周期序列a₀a₁…则$c_a(\tau)=\sum_{i=0}^{t-1}\eta(a_i)\eta(a_{i+\tau}),\tau\in Z$，其中$\eta$是Z₂上的加法群到{1,-1}的乘法群的同构$\eta(0)=1,\eta(1)=-1$，有$\eta(a+b)=\eta(a)\eta(b)$）
平衡特性：m序列1个数比0个数多1
游程特性：1的最大游程为n游程，有且仅有1个；1个0的n-1游程。n>2时，设r为不超过n-2的任一整数，则任何1的r游程数目为$1+\sum_{r=1}^{n-2}2^{n-r-2}=2^{n-2}$；出现0游程的个数为$2^{n-2}$,游程总数为$2^{n-i}$
自相关特性：$c_a(\tau)=\sum_{i=0}^{2^n-2}\eta(a_i)\eta(a_{i+\tau})=2^n-1,\tau\equiv 0(\mod 2^n-1); =-1, \tau \ne 0(\mod 2^n-1)$

异步流密码的加密和解密是一个对称的加解密过程。

LFSR流密码分析：

分析目标为：获取LFSR的结构（即密钥——LFSR的初态z₀,z₁,…和递推公式[抽头序列c₁,c₂,…]），使用唯密文攻击较为困难，使用一直明文攻击。
$z_k=\sum_{j=1}^nc_jz_{k-j}$
如果能够得到长度不小于2n的明文-密文对，就容易求出其初态和抽头序列（假设n已知）
密钥比特流可以直接将明密文求和得到，其中前面的一组作为初态

$$(z_n,z_{n+1},...,z_{2n-1})=(c_n,c_{n-1},...,c_1)\begin{pmatrix}z_0 & z_1 & ... & z_{n-1}\\ z_1&z_2&...&z_n\\ ...&...&...&...\\ z_{n-1}&z_n&...&z_{2n-2}\end{pmatrix}$$

根据上式可计算$(c_n,c_{n-1},...,c_1)$的值