密码学
密码学和数据安全导论
可靠的密码体制必须遵守Auguste Kerekhoffs在1883年提出的一个假说，即Kerekhoffs原理:
即使密钥外的整个系统的一切都是公开的，这个密码体制也必须是安全的。尤其是即使攻击者知道系统的加密算法和解密算法，此系统也必须是安全的。
需要强调的是，设计上一个隐藏细节的系统看似是更安全的。但是历史经验告诉我们这样的系统其实是很脆弱的，系统的细节可以通过逆向工程破解。这就是说为什么即使攻击者知道加密算法，加密方案仍必须保持安全的原因。
模运算与多种古典密码
模运算
几乎所有的加密算法都是基于有限个元素的运算。模运算就是在有限个数集中执行运算的简单方法：
定义：模运算
假设$a, r, m \in Z$(其中Z是所有整数的集合)，并且m>0。如果m除a-r，可记作：
$$a \equiv r \bmod m$$
其中m称为模数，r称为余数
其中$a \equiv b (\bmod m)$表示a与b对于m同余
等价类中所有成员的等价行为
对于一个给定模数m，选择等价类中任何一个元素用于计算的结果都是一样的。因此我们可以选择等价类中最易于计算的一个元素进行模运算
计算$3^8$模7的的结果：
- $3^8 = 6561 \equiv 2 \bmod 7$
- 下面使用等价类进行计算
$$3^8 = 3^4 \cdot 3^4 = 81 \cdot 81$$ - 然后将中间结果的81替换为同一等价类中的其他元素。在模数7的等价类中，最小的正元素是4(因为$81 = 11 \cdot 7 + 4$)，因此：
$$3^8 = 3^4 \cdot 3^4 \equiv 4 \cdot 4 \equiv 16 \bmod 7 \equiv 2 \bmod 7$$
通用的规则是：应该尽量使用模化简，使计算的数值尽可能小，这样做总是极具计算优势
整数环
定义：环
整数环$Z_m$由以下两部分组成：
- 集合$Z_m = (0, 1, 2, …, m-1)$
- 两种操作”+”和”×”，使得所有的$a, b \in Z_m$有
- 1)$a + b \equiv c \bmod m, (c \in Z_m)$
- 2)$a \times b \equiv d \bmod m, (d \in Z_m)$
环具有以下特征：
- 如果环内任何两个数相加或相乘得到的结果始终在环内，那么这个环是封闭的
- 加法和乘法是可结合的，例如对所有的$a, b, c \in Z_m$，都有$a + (b+c) = (a+b) + c$和$a \cdot (b \cdot c) = (a \cdot b) \cdot c$
- 加法中存在中性元素0，使得对每个$a \in Z_m$都有$a + 0 \equiv a \bmod m$
- 环中的任何元素a都存在一个负元素-a，使得$a + (-a) \equiv 0 \bmod m$，即加法逆元始终存在
- 乘法中存在中性元素1，使得对每个$a \in Z_m$都有$a \times 1 \equiv a \bmod m$
- 不是所有元素都存在乘法逆元，假设$a \in Z$，乘法逆元$a^{-1}$可以定义为：
$$a \times a^{-1} = 1 \mod m$$
如果某个元素的乘法逆元存在，则可以除以这个元素，因为$b/a \equiv b \cdot a^{-1} \bmod m$ - 寻找逆元比较困难，可以通过一种简单的方法判断一个元素a的逆元是否存在：
- 当且仅当$gcd(a, m) = 1$，一个元素$a \in Z$存在乘法逆元$a^{01}$，其中gcd表示最大公约数(Greatest Common divisor)，$gcd(a, m) = 1$就表示a和m(模数)互质
仿射密码
仿射密码是一种改善的移位密码，仿射密码的思路是将明文密码乘以密钥的一部分，然后再加上密钥的剩余部分
定义：仿射加密
假设$x, y ,a, b \in Z_26$(26个字母)
加密：$e_k(x) = y \equiv a \cdot x + b \bmod 26$
解密：$d_k(y) = x \equiv a^{-1} \cdot (y-b) \bmod 26$
密钥为：$k = (a, b)$，且满足限制条件gcd(a, 26)=1
gcd(a, 26)=1 这个限制是源于这样一个事实：加密时需要求密钥参数a的逆元。
通过尝试所有$a^{-1}$的可能值，直到$a \cdot a^{-1} \equiv 1 \bmod 26$即可得到逆元
因此仿射加密的确比移位加密复杂，但也是可暴力破解的
$$密钥空间 = (a的可能值) \times (b的可能值)$$
序列密码
对称密码学分成分组密码和序列密码两部分
- 序列密码
- 单独加密每个位
- 分组密码
- 每次使用相同的密钥加密整个明文位分组
序列密码加密与解密
定义：序列密码
明文、密文和密钥序列都是由单独的位组成，即$x_i, y_i, s_i \in {0, 1}$
加密：$y_i \equiv x_i + s_i \bmod 2$
解密：$x_i \equiv y_i + s_i \bmod 2$
加密解密推导：加密和解密用的是相同的函数
$$\begin{aligned}
d(y_i) &\equiv y_i + s_i \bmod 2 \
&\equiv x_i + s_i + s_i \bmod 2 \
&\equiv x_i + 2s_i \bmod 2 \
&\equiv x_i + 0 \bmod 2 \
&\equiv x_i \bmod 2 \
\end{aligned}$$
下面给出模2加法的真值表
| $x_i$ | $s_i$ | $y_i \equiv x_i + s_i \bmod 2$ |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
事实上模2加法与异或XOR是等价的，密文为0或1的概率是完全相等的
密钥序列$s_1, s_2, …,s_i$是序列密码安全的核心问题，在攻击者看来$s_i$必须的随机的
随机数与牢不可破的分组密码
随机数生成器
- 真随机数生成器(TRNG)
- TRNG的突出特征是它是输出是不可复制的
- 如拋100次硬币，世界上另一个人抛出和我相同的结果概率很低
- TRNG都是基于物理过程，主要例子包括抛硬币等
- TRNG的突出特征是它是输出是不可复制的
- (通用的)伪随机数生成器(PRNG)
- PRNG从一个初始种子值开始通过各种计算得到序列
- PRNG并不是真正意义上的随机，因为它们是可以算出来的
- 对PRNG的一个一般要求是：必须有良好的统计属性
- 即它的输出与真随机数序列相同
- 加密安全的伪随机数生成器(CSPRNG)
- 是一种不可预测的PRNG，即计算后续位在计算上是不可行的
一次一密
一个完美的密钥应该具有的特征：无条件安全。定义如下
如果一个密码体制在无限计算资源的情况下也不能被破译，则说明它是无条件安全的或信息论上安全的
一下是个简单的无条件安全的密码，这个密码是一次一密(OTP)，定义如下
一个序列密码成为一次一密，必须满足一下条件：
- 通过真随机数生成器得到密钥序列$s_1, s_2, …$
- 只有合法的通信方才知道密钥序列
- 每个密钥序列位$s_i$仅使用一次
一次一密是无条件安全的
证明OTP是无条件安全的方法如下
$$\begin{aligned}
y_0 &\equiv x_0 + s_0 \bmod 2 \
y_1 &\equiv x_1 + s_1 \bmod 2 \
…
\end{aligned}$$
每个单独的关系都是有两个未知数的线性等式模2,它们无法求解
OTP缺点如下，导致它在实际中很少使用：
- 需要真随机数生成器
- 每个密钥序列使用一次，需要多次交换密钥序列
关于实际序列密码
我们处理实际序列密码的方式就是使用伪随机数生成器(PRNG)代替真随机数生成器。实际上，所有已知的实际加密算法都不是无条件安全的。但是我们可以做到 计算安全
定义：计算安全
如果为破解一个密码体制，最好的一直算法需要至少t个操作，则说明次密码体制是计算安全的
这个定义看似合理但是存在若干问题。首先人们不知道对应的最好算法是哪一个，因此我们不知道是否存在更强大的攻击。
利用PRNG构建密码流
虽然PRNG可以用来生成密钥流，但对于序列密码而言都不足够，考虑下面的例子：
假设一个基于线性同余生成器的PRNG：
$$\begin{aligned}
S_0 &\equiv seed \
S_{i+1} &\equiv AS_i + B \bmod m, i = 0, 1, … \
\end{aligned}$$
设其中选择的m为100位长，$S_i, A, B \in {0, 1, …, m-1}$，我们通过仔细选择这些参数是的此PRNG具有良好的统计属性。密钥包含值(A, B)，可可能包含种子$S_0$，并且每个值的长度都是100，总共密钥长度就为200位。发送方使用一下方式加密：
$$y_i \equiv x_i + s_i \bmod 2$$
其中$s_i$为PRNG输出符号$S_j$的二进制表示的位
攻击者可以轻易发起攻击，如果攻击者知道明文的前300位(通过头文件、常用语等猜出部分明文)。那他可以利用下式计算密钥序列的前300位：
$$s_i \equiv y_i + x_i \bmod m, i = 1, 2, …, 300$$
于是就得到了:$S_1 = {s_1, …, s_{100}}, S_2 = {s_1, …, s_{200}}, S_3 = {s_3, …, s_{300}}$。攻击者现在可以得到两个等式：
$$\begin{aligned}
S_2 \equiv AS_1 + B \bmod m \
S_3 \equiv AS_2 + B \bmod m
\end{aligned}$$
对于一个基于$Z_m$的线性等式系统，拥有两个未知数A，B，我们可以得到：
$$\begin{aligned}
A &\equiv (S_2 - S_3)/(S_1 - S_2) \bmod m \
B &\equiv S_2 - S_1(S_2 - S_3)/(S_1 - S_2) \bmod m
\end{aligned}$$
在$gcd((S_1 - S_2), m) \neq 1$情况下可以得到多个解，如果已知明文的第四片段信息就可以唯一测出密钥。
这种类型的攻击正是发明CSPRNG表示方法的原因
利用CSPRNG构建密钥序列
CSPRNG可以确保密钥序列是不可预测的，但是相当一部分在密码学之外的伪随机数生成器不是密码学安全的，因此我们需要使用专门的伪随机数生成器来生成密码序列