分组加密简介

分组密码是指将明文消息编码后的数字序列按顺序分成多个长为$n$的分组$P=(p0,p_1,…,p{n-1})$，各分组在密钥$K=(k0,k_1,…,k_t)$的控制下分别变换成等长的密文分组$C=(c_0,c_1,…,c{n-1})$

理想的分组密码可以定义明密文分组之间的任意可逆变换

若明密文分组为$n$位二进制序列，那么理想的分组密码可以定义$2^n!$种不同变换，当$n$足够大时，密文中明文语言的统计特征将被完全掩盖

然而理想的分组密码显然无法实现，仅仅$n=64$时，要将变换的映射关系存储下来就需要$64\times 2^{64}\approx 10^{21}bit$

因此密码学家Feistel建议使用乘积密码的概念来近似理想分组密码

扩散与混淆

为了对抗统计分析攻击，香农引入了扩散和混淆两个概念

扩散是指使明文的统计特征消散在密文中，通过让每个密文数字受多个明文数字影响可以做到

混淆是指尽可能使密文和密钥间的统计关系更加复杂，以组织攻击者通过密文推出密钥

香农提出交替使用代替和置换（混淆和扩散）的乘积密码思想，其产生的密码强度高于所有单独使用的基本密码系统

Feistel密码结构

Feistel加密/解密过程

基于上述香农的理论的Feistel密码结构，仍是当前大多重要对称分组密码的基本结构

如图所示为Feistel密码的基本结构

设明文分组长度为$|P|=2w$，Feistel经过$n$轮相同迭代输出等长密文分组$|C|=2w$

对于第$i$轮迭代，将其输入等分为左右两份，分别记为$LEi$和$RE_i$
则第$i$轮迭代输出分别为$LE{i+1}=REi,\ RE{i+1}=LEi\oplus F(K_i,RE_i)$
其中$K_i$第$i$轮迭代的子密钥，子密钥由总密钥$K$使用算法产生，子密钥互不相同
之后$LE{i+1}、RE_{i+1}$成为第$i+1$轮迭代的输入

最后一轮迭代后，将输出的$LE_n、RE_n$互换位置即得到最终密文分组输出

Feistel的解密过程与加密相同，只是逆序使用子密钥

以解密第一轮为例有如下推导，可以发现解密第1轮输出就是加密第n-1轮输出的左右交换

按同样思路推下去不难发现解密第$i$轮输出就是加密第$n-i$轮输出的左右交换

feistel

Feistel参数与安全性的关系

  • 分组长度：显然分组越长越安全，因为更长的分组意味着更好的扩散性，但是实际应用中过长的分组会降低运算速度，一般64位、128位比较常见
  • 密钥长度：显然密钥越长越安全，因为更长的密钥意味着更好的混淆性，通常需要至少128位
  • 迭代轮数：依据乘积密码思想迭代轮数越多越安全，但过多的轮数会使效率降低，常见轮数为16
  • 子密钥产生算法：越复杂的产生算法，混淆性越好
  • 轮函数F：同理越复杂的轮函数，抗攻击能力越好

分组密码的操作模式

电子密码本ECB

最简单的分组密码操作模式就是电子密码本（Electronic Code Book）模式

电码本模式一次加密一个分组，且每组使用的密钥相同
对于任意$b$位明文分组，显然有唯一的$b$位密文分组与之对应
就像一个密码本，给定任意明文，可以直接查到它的相应密文

显然ECB存在统计特征泄露的安全隐患
此外ECB也无法抵御对高度结构化消息的替换攻击
攻击者可能将密文中若干分组直接替换成其他密文分组而不被发现

但是ECB可以并行加密解密，效率高，因此也用于一些短消息（如密钥）的加密

blockcipher_ecb

密码分组链接CBC

密码分组链接（Cipher Block Chaining）是克服ECB弱点的一种简单方法

CBC的加密输入是当前明文分组与上一个密文分组的异或
解密则是先对密文分组解密，再将输出与上一个密文分组异或得到该明文分组

CBC流程如图所示，其中IV为初始向量
初始向量必须不可预测，且只能被收发双方拥有

相较于ECB，CBC能隐藏明文的统计特征，也能一定程度上防止篡改
但CBC只能串行加密，且可能产生错误传播，即一个密文分组传输出错，会影响后续该明文分组和下一个明文分组共两个分组

blockcipher_cbc

密文反馈CFB

密文反馈（Cipher Feedback）可将分组密码当作流密码使用

设传输单元为$s$位，明文也被分为$s$位的单元
加密函数的输入是$b$位的移位寄存器，寄存器中的初始值为$IV$

第1轮加密，加密函数的输出为$b$位的$O_1=E(K,IV)$
取其左侧$s$位与明文第一个单元$P_1$异或得到第一个密文单元$C_1=P_1\oplus O_1[b:b-s+1]$
然后令移位寄存器左移$s$位，并将$C_1$填充至其寄存器右侧，重复上述过程

形式化地说明如下

CFB的解密过程与加密相同，只是加密函数的输出需要与相应的密文单元异或
注意解密与加密用的是同一个加密函数，这一点很容易解释
已知$C_1=P_1\oplus E(K,IV)[b:b-s+1]$，则显然$P_1=C_1\oplus E(K,IV)[b:b-s+1]$，后续同理

blockcipher_cfb

输出反馈OFB

输出反馈模式（Output Feedback）和CFB很类似

OFB将加密函数的输出反馈到下一次加密函数的输入
且OFB对明文和密文分组进行运算，而不是CFB中的$s$位单元

OFB的表达式为

注意到图中$IV$标注为时变值，即每次加密$IV$都必须是唯一的
因为相同$IV$在OFB中产生的密钥流相同，攻击者很容易从中统计出特征

与CFB相比，OFB不会错误传播，即其中一个密文分组错误时，不会影响后续明文分组的解密结果

blockcipher_ofb

计数器模式CTR

计数器模式对每个分组应用一个计数器，每个计数器的输出与分组大小相同
计数器先被初始化为不同值，然后随着消息快的增加进行+1
解密时使用相同初值的计数器即可

CTR模式不包含反馈，所以每次加密的计数器初值都必须唯一

blockcipher_ctr

操作模式的对比

blockcipher