第三讲 分组密码
分组密码
概述
明文消息，编码成二元数字序列后，划分为长度为m的一个个组块。
加密：每个长度为m的明文组块分别在密钥K的控制下变成一个个长度为n的密文组块
解密：每个长度为n的密文组块通过密钥K还原成一个个长度为m的明文组块
分组密码通常研究以下三种情况：
如果m>n 说明密文比明文短，存在数据压缩
如果m<n 说明密文比明文长，存在数据拓展
如果m=n 说明既没有数据压缩，也没有数据拓展
分组密码的常见设计方法
当今绝大多数的分组密码都是乘积密码。
所谓乘积密码，就是以某种方式连续执行两个或者多个密码。
常见的乘积密码都是迭代密码。
以下是两种用迭代法设计分组的常用方法
Feistel结构
DES采用此结构
上一轮的右半部分成为这一轮的左半部分。
上一轮的左半部分和一个复杂的值（右半部分和每一轮的密钥Ki进行运算）进行异或，异或后的结果成为这一轮的右半部分。
SPN结构
AES采用此结构
这种结构分两层：
第一层：S层，也称为替换层，主要起到扰乱的作用。
第二层：P层，也称为置换层，主要起到扩散的作用。
数据加密标准——DES
此加密方案由IBM公司提交，被美国国家标准局于1976年采纳。
算法描述
明文分组64位，有效密钥56位，输出密文64位，迭代16轮
算法流程
初始置换、16轮迭代、左右部分换位、初始逆置换
轮函数
上一轮的右半部分作为这一轮的左半部分，上一轮的右半部分再与轮密钥k进行指定的运算得到一个结果，这个结果再与上一轮的左半部分异或，得到这一轮的右半部分。（看图更直接）
子密钥
DES每一轮都使用不同的、从初始密钥K导出的48位子密钥。密钥是一个64位的分组，但是其中8位是用于奇偶校验的，所以密钥有效位只有56位。
子密钥的生成过程如下：
首先：
给定一个64比特的密钥K，删掉8个校验比特并利用一个固定的置换PC-1置换剩下的56位。把这56位分成两部分：C、D 各28位。
然后进入如下循环：
- 把上一轮生成的C和D两部分按照LS表中 每一轮对应的值 进行循环左移，得到本轮的C和D
- 把这一轮的C和D，根据PC-2置换表，置换得到本轮的轮密钥Ki
f函数
不难看出，DES加密每一轮其实只对左半部分做了打乱的操作，而对右半部分，只是简单地放到了这一轮的左边
f函数的过程如下：
先把右半部分32位进行位拓展，拓展为48位
再与轮密钥K进行异或运算。
运算结果分成8部分，每部分6比特。每部分进入到对应的S盒得到一个输出
假设6比特为：h1 h2 h3 h4 h5 h6
则（h1 h6）作为行号，（h2 h3 h4 h5）作为列号（转二进制）
结果转换成二进制（6比特进，4比特出）
高级加密标准——AES
1997年提出，代替DES，比DES更安全
AES的数学基础
AES算法的总体描述
分为AES128、 AES192 、AES256
方便二进制运算的算法
加解密使用相同的密钥，但不同的算法
整体属于SP结构
AES的算法流程分析
感谢B站的这个视频，讲的很透彻，演示很生动
【【AES加密算法】| AES加密过程详解| 对称加密| Rijndael-128| 密码学| 信息安全】 https://www.bilibili.com/video/BV1i341187fK/?share_source=copy_web&vd_source=73f97624c2b3ff1eb41ea26fb86c72ee
以AES128为例（10轮）
AES加解密主要有以下操作：
- 输入明文
- 初始变换
- 9轮循环运算
- 字节代换（SubBytes）
- 行移位（ShiftRows）
- 列混合（MixColumns）
- 轮密钥加（AddRoundKey）
- 1轮最终轮
- 字节代换（SubBytes）
- 行移位（ShiftRows）
- 轮密钥加（AddRoundKey）
- 输出密文
- 轮密钥加
- 字节代换
- 行位移
- 列混合
算法前九轮包含以上所有操作，最后一轮不进行列混合
初始变换
将明文生成的4*4矩阵（16字节）与密钥生成的4*4矩阵按字节进行异或操作
9轮循环
字节代换
把输入的矩阵，按照代换表逐个替换，替换规则如图所示
行移位
过程比较简单，第0行左移0位，第1行左移1位，第2行左移2位，第三行左移3位。
列混合
将输入的矩阵左乘一个给定的矩阵
按照给定的二进制乘法公式进行运算，其中的所有加法都是异或加法
轮密钥加（每轮的关键加密部分，只有这部分用到了轮密钥）
输入矩阵和轮密钥矩阵逐列进行异或运算
1轮最终轮
操作和前9轮一样，但是不进行列混合
密钥拓展
先把初始密钥填入如下矩阵，并设定第0列为W0
往后每一列的值按照如下公式运算
如果i不是4的倍数，运算比较简单；如果i是4的倍数，则要进行一个T函数的运算。
密钥拓展的中的T函数
字循环
把传入的Wi列进行如下变换
字节待换
轮常量异或
把上面的结果和本轮给定的轮常量Rcon[j]（j表示轮数）进行异或
分组密码的工作模式
电子密码本模式 ECB
用相同的密钥对明文分组单独加密
一段明文 分成几个明文分组，每个分组使用同样的密钥进行加密
密文分组链接模式 CBC
将前一个密文块和当前明文块进行异或运算后再加密
优点：每个分组加密依赖前一个密文块，具备数据完整性保护
缺点：但是一旦出错，后面所有的分组都会出错
密文反馈模式 CFB
将前一个密文块作为输入进行加密，生成一个密钥流，再与当前明文块进行异或运算得到密文块。
明文本身没有进入到加密算法当中，而是与加密算法的输出进行了异或
优点：加密操作长度可变、可以部分解密数据
缺点：一步错，步步错、不适合并行处理，需要保证初始向量的唯一性和完整性
输出反馈模式 OFB
将前一个加密算法的输出进行加密，生成一个密钥流，再与当前明文块进行异或运算得到密文块
优点：加密操作长度可变、对密文分组的错误不敏感
缺点：传输错误不可恢复、无法提供数据完整性保护、不支持并行加密
计数器模式 CTR
每一个明文分组都与一个经过加密的计数器进行异或。对后续每个分组，计数器+1
优点：并行处理、随机访问、不受错误传播影响
缺点：计数器必须唯一、密钥流和明文相关性弱