cryptography

现代密码学复习

概论

密码学学科分支

• 密码编码学（新思想，新结构）
• 密码分析学（新方法，新手段）
  • 恢复密文相应的明文
  • 恢复密钥

信息安全的基本属性

• 机密性
• 认证
• 完整性
• 不可否认性

保密通信系统模型

• 主动攻击：破坏双方的通信，比如插入、删除、修改通信的内容
• 被动攻击：收集通信内容

密码算法的分类

• 按功能
  • 加密算法（机密性）
  • 杂凑算法（完整性）
  • 数字签名（认证和不可否认）
• 按密钥使用方式
  • 对称密钥密码（加解密密钥相同；分组密码，流密码）
  • 非对称密钥密码（加解密密钥不同；公钥加密，数字签名）
• 按时间（保密性实现方法）
  • 古典密码（数据的保密基于加密算法的保密）
  • 现代密码（数据的保密依赖于对密钥的保密）

凯撒密码

移位密码，原文按字母表顺序右移三位为密码
ABC->DEF

密码体制的攻击方法

• 穷举攻击（通过试遍所有密钥来进行破译）
  • 增大密钥空间来对抗
• 统计分析攻击（分析密文和明文的统计规律来破译）
  • 使明文和密文的统计规律不一样
• 解密变换攻击（针对加密变换的数学基础，通过数学求解设法找到解密变换）
  • 选用具有坚实的数学基础和足够复杂的加密算法

1. 唯密文攻击
2. 已知明文攻击
3. 选择明文攻击
4. 选择密文攻击

安全的定义

无条件安全

无论截获多少密文，都没有足够信息来唯一确定明文，则该密码是无条件安全的，即对算法的破译不比猜测有优势

计算上安全

使用有效资源对一个密码系统进行分析而未能破译，则该密码是强的或计算上安全的

可用的密码算法

• 破译密文的代价超过被加密信息的价值
• 破译密文所花的时间超过信息的有用期

古典密码算法

• 置换（Permutation）
  对明文进行位置移动
• 代替（Substitution）
  用密文字母表代替明文字母

单表代替密码

• 加法密码 ($y = x + k \pmod {26}$)
• 乘法密码 ($y = kx \pmod {26}$)
  • 仅当 $gcd(k, 26) = 1$时能够解密成功
• 仿射密码 ($y = ax + b \pmod {26}$)
  • 仅当 $gcd(k, 26) = 1$时能够解密成功

流密码

利用种子密钥k产生一个密钥流$z = z_0z_1z_2…$
对明文串$x=x_0x_1x_2…$加密
$$y=y_0y_1y_2…=E_{z_0}(x_0)E_{z_1}(x_1)E_{z_2}(x_2)…$$

线性反馈移位寄存器 Linear Feedback Shift Register

密钥流序列应具有的性质

• 极大的周期
• 良好的统计特性
• 抗线性分析

LFSR性质

LFSR中的c不能全为0，否则$f(a_1, a_2, …, a_n) = 0$

n级LSFR状态数：$2^n$

n级LSFR状态周期：$\leq 2^n - 1$（不能全为0）

输出序列的周期 = 状态周期 $\leq 2^n - 1$

使周期达到最大值的序列成为m序列

RC4

密钥调度算法

初始化数据表S，S[i] = i (0 <= i <= 255)，通过种子密钥来随机化数据表S

// 初始化S表，长度为256
S[i] = i (0 <= i <= 255)

// 用种子密钥填充一个K表，长度为256，密钥长度不足时，重复使用密钥，如密钥为123，则K表为{1,2,3,1,2,3,...}
j = 0;
for (int i = 0; i <= 255; i++) {
  j = (j + S[i] + K[i]) % 256; // 将K表加入，增加随机性
  swap(S[i], S[j]); // 打乱S表
}

伪随机数生成算法

随机选取S表中的一个数，反复进行选取，直到生成的二进制位数量等于明文比特位数量（足够用于加密）

i = 0; j = 0;
i = (i+1) % 256;
j = (i + S[i]) % 256;
swap(S[i], S[j]);
t = (S[i] + S[j]) % 256;
k = S[t];
# 输出k

分组密码

找到一种算法，在密钥控制下，从一个足够大且足够好的置换子集中，简单迅速低选出一个置换，用来对输入的明文进行加密变换

##　安全性设计原则

• 混淆（Confusion）
  将密文，明文，密钥三者之间的统计关系和代数关系变得尽可能复杂

• 扩散
  将明文的统计规律和结构规律散射到相当长的一段统计中去

  明文的每一个位影响密文中尽可能多的位

分组密码算法应满足的要求：

• 分组长度n要足够大（每一个分组的长度）

  防止明文穷举攻击

• 密钥量要足够大

  消除弱密钥，防止密钥穷举攻击

• 由密钥确定置换的算法要足够复杂

  充分实现明文和密钥的扩散和混淆

• 加密和解密运算简单

  易于软件和硬件实现

• 数据扩展

  一般无数据扩展（密文和明文一样长）

• 差错传播尽可能小

  一个密文分组和错误尽可能少的影响其他密文分组的解密

DES (Data Encryption Standard)

明文分组长度 64bit
密文分组长度 64bit
密钥长度64bit，8bit奇偶校验，有效密钥长度56bit

1. 先对明文进行初始置换，打乱明文的顺序

2. 将明文分为两组L和R，每组32bit

3. 16轮的轮变换

DES轮结构

通过初始的密钥K生成16个轮密钥（48bit）

$L_i = R_{i-1}$

$R_i = L_{i-1} \oplus F(R_{i-1}, Ki)$

DES轮函数 $F(R_{i-1}, Ki)$

输入32位的消息

先扩展成48位

与48位的轮密钥异或后，通过S盒变成32位

S盒共有8个，每个S盒接受6bit的输入，输出4bit

48位的输入，分为8组，输出4*8=32位

再通过P盒置换，输出32bit的最终结果

S盒

6bit输入，第1和第6bit作为行号，剩下4bit作为列号，输出S盒对应位置的数据的二进制

P盒置换（打乱位置）

经过S盒变换后的32bit数据再进行P盒置换，置换后得到的32bit就是
f函数的输出

特点

• 每一行都来自于不同的输入块（S盒）
• 各输入块的4bit都分配到不同的输出快中
• 第t输出块的4个比特都不来自第t输入块

轮密钥生成

输入64bit的密钥（其中8位为奇偶校验位，56位为有效密钥）

经过置换选择变成56bit，去除了8位奇偶校验位

56bit分成C、D两部分，各28bit

C、D两部分各循环左移16次，每次左移的位数都有规定（查移位次数表）

第i次迭代           1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16
循环左移次数     1  1  2  2  2  2  2  2  1    2    2    2    2    2    2   1

C、D两部分再经过一次置换选择（丢弃8bit），最终生成16 个 48bit的轮密钥

DES密钥特点

• 互补性

  $y=DES_k(x)$

  对明文逐位取补，对k逐位取补，则最后密文也是对原密文的逐位取补，导致密码破译工作量减半，影响安全性

  $\overline{y} = DES_{\overline{k}}(\overline{x})$

• 弱密钥

  初始密钥导致每轮生成的轮密钥都相同，则为弱密钥

  DES存在4个弱密钥

  轮密钥生成时，将56位的密钥分成C、D两部分，各28bit做循环左移位，当C、D全1或全0时，循环移位生成的轮密钥是相同的，所以有4个弱密钥

  $E_k E_k = I$

  使用同一个密钥加密两次后变成明文

  $DES_k(DES_k(x)) = x$

双重DES

中间相遇攻击

如果已知明文和对应的密文 $(x_1, y_1)$
可以同时获得$k_1$, $k_2$

以$k_1$的$2^56$种取值加密$x_1$，将密文z存在一个表中

以$k_2$的$2^56$种取值解密$y_1$，每次解密结果在上述表中查找匹配的值，如果找到了就可以同时确定$k_1$, $k_2$

再找一个明文和密文验证就可以知道$k_1$, $k_2$是否正确

破解双重DES需要加密$2^56 + 2^56 = 2^57$，说明双重DES密钥空间为57位

三重DES

加密：$C=E_{k1}[D_{k2}[E_{k1}[P]]]$

$K_1$加密，$K_2$解密，$K_1$加密

解密：$P=D_{k1}[E_{k2}[D_{k1}[C]]]$

$K_1$解密，$K_2$加密，$K_1$解密

密钥空间为 112位

分组密码的工作模式

ECB (Electronic Codebook Book) 电码本模式

将明文分组，分别加密成密文，合并成一段长密文
解密时先分组，再解密

优点

• 可并行执行
• 实现简单

缺点

• 相同明文对应相同密文分组
• 不能隐藏明文分组的统计规律和结构规律，不能抵抗替换攻击，重放攻击

应用

• 可用于随机数的加密保护
• 单分组明文的加密

CBC (Cipher Block Chaining) 密码分组链接模式

加密

$$C_i = E_k(m_i \oplus C_{i-1})$$

解密

$$m_i = D_k(C_i) \oplus C_{i-1}$$

由于初始化向量$IV$的选择不同，相同的明文加密会得到不同的明文

各密文块不仅与当前明文块有关，还与前一个密文块有关

一个密文块错误传播最多影响2个密文块（自身和下一个密文块）

CFB (Cipher Feedback) 密码反馈模式

上面的模式分组大小都必须是64bit，也就是说明文必须64bit为一组加密，如果想要更改加密分组的大小就要使用CFB模式

可实现加密消息按j比特加密

第一个j比特分组p1的加密过程

先将初始化向量$IV$通过密钥k（64bit）进行DES加密，输出的结果取左边jbit，与jbit的明文异或，输出C1，完成对j比特明文的加密

第二个j比特分组p2的加密

初始化向量左移jbit，append C1，作为新的初始化向量

重复第一个j比特的加密过程

所谓的CFB，就是每次将上一次加密的密文反馈到下一个分组的加密中，反馈是通过修改初始化向量IV实现的

解密

由于加密是使用的异或，再进行一次异或就是解密

特点

• 选取的IV不同会导致相同的明文生成不同的加密输出
• 链接依赖性：密文组依赖与当前明文组和之前的明文组，重排密文组会影响解密
• 错误传播，一个或多个比特错误出现在任一个j比特的密文组中会影响这个组和后继 $\lceil n / j \rceil$ 个密文组的解密

OFB (Output Feedback) 输出反馈模式

类似与CFB，但向下一个分组加密反馈的内容是初始化向量和K的DES加密结果（共64bit，仅反馈前j比特）

特点：

• 选取的IV不同会导致相同的明文生成不同的加密输出
• 反馈的内容与明文无关，生成的密钥流独立于明文
• 一个或多个比特错误出现在任一个密文组中仅会影响这个密文组（无错误传播）

计数器模式

AES

AES加密的最后一轮没有 列混淆，这样加密和解密可以使用相同的硬件

轮密钥加

轮密钥和状态矩阵大小相同，相同位置的元素做 异或

字节替换

每个字节分成两部分，左边是行号，右边是列号

通过查S表，获取对应的值

行移位

4行的状态矩阵

第0行不动
第1行左移1字节
第2行左移2字节
第3行左移3字节

列混淆（最后一轮没有）

对状态矩阵的每一列 乘一个矩阵（多项式乘法），结果放回原位置

$$\begin{bmatrix}
02 & 03 & 01 & 01 \
01 & 02 & 03 & 01 \
01 & 01 & 02 & 03 \
03 & 01 & 01 & 02 \
\end{bmatrix}$$

密钥编排

通过初始密钥矩阵生成每一轮需要的密钥矩阵

非对称加密

RSA

密钥生成

1. 随机选取两个大素数$p$, $q$，计算$n = p \times q$，计算$\phi(n) = (p - 1)(q - 1)$
2. 随机选取一个整数e，满足 $1 < e < \phi(n)$，且 $gcd(e, n) = 1$
3. 计算 $ed \equiv 1 \pmod {\phi(n)}$
4. e为公钥，d为私钥

加密

$$c = m^e \pmod n$$

解密

$$m = c^d \pmod n$$

ElGamal

密钥生成

选择一个素数p，以及小于p的随机数x，g是$Z_p$的原根

$y = g^x \pmod p$
x为私钥，y为公钥

加密

取一个随机整数k，$1 \leq k \leq p-2$

$c_1 = g^k \pmod p$，$c_2 = my^k \pmod p$

解密

$$m = c_2 / c_1^x \pmod p$$

$$$$

Rabin

密钥生成

取两个大素数p, q, 满足$p \equiv q \equiv 3 \pmod 4$，

计算 $n = p \times q$

公钥为n，私钥为 $(p, q)$

加密

$$c = m^2 \pmod n$$

解密

利用中国剩余定理求解同余方程组

中国剩余定理

$x \equiv b1 \pmod {m1}$

$x \equiv b2 \pmod {m2}$

$x \equiv b3 \pmod {m3}$

$x \equiv b4 \pmod {m4}$

解法：
$m = m1 \times m2 \times … \times m_k$

$m = M_im_i$

$M’$是$M$模$m_i$的逆元，$MM’ \equiv 1 \pmod m_i$

$x \equiv b1M_1M’_1 + b2M_2M’_2 + … + b_kM_kM’_k \pmod m$

$M_1 = c^{(p+1)/4} \pmod p$

$M_2 = p - c^{(p+1)/4} \pmod p$

$M_3 = c^{(q+1)/4} \pmod q$

$M_4 = q - c^{(q+1)/4} \pmod q$

选择整数 $a = q \times (q^{-1} \pmod p)$，$b = p \times (p^{-1} \pmod q$

四个可能的解为：

$m_1 = (aM_1 + bM_3) \pmod n$

$m_2 = (aM_1 + bM_4) \pmod n$

$m_3 = (aM_2 + bM_3) \pmod n$

$m_4 = (aM_2 + bM_4) \pmod n$

椭圆曲线密码

P + Q的计算方法

$$\lambda = \begin{cases}
\frac{3x_1^2 + a}{2y_1}, P = Q \
\frac{y_2 - y_1}{x_2 - x_1}, P \neq Q \
\end{cases}$$

$x_3 = \lambda - x_1 - x_2$

$y_3 = \lambda(x_1 - x_3) - y_1$

数字签名

RSA签名

私钥加密，公钥解密

密钥生成

1. 随机选取两个大素数$p$, $q$，计算$n = p \times q$，计算$\phi(n) = (p - 1)(q - 1)$
2. 随机选取一个整数e，满足 $1 < e < \phi(n)$，且 $gcd(e, n) = 1$
3. 计算 $ed \equiv 1 \pmod {\phi(n)}$
4. e为公钥，d为私钥

签名

$$s = m^d \pmod n$$

验证

收到的签名是(m, s)

如果
$$m \equiv s^e \pmod n$$
则s是m的签名

DSS

ElGamal