第3章 分组密码
最容易理解的部分&基本组件
在大多数应用中以"工作模式"来使用
3.1什么是分组密码
加密固定长度数据分组的加密函数
可逆且明密文的长度相同
Kerckhoff原则：
即使非数学上不可破解，系统也应在实质（实用）程度上无法破解。
系统内不应含任何机密物，即使落入敌人手中也不会造成困扰。
密匙必须易于沟通和记忆，而不须写下；且双方可以容易的改变密匙。
系统应可以用于电讯。
系统应可以携带，不应需要两个人或以上才能使用（应只要一个人就能使用）。
系统应容易使用，不致让用户的脑力过分操劳，也无需记得长串的规则。
假设用于加密和解密的算法是公开已知的
一个分组长度为k位的分组密码对于每一个密钥都对应一个k位值的置换。构成了庞大的映射表
32位分组——>16GB
64位分组——>1.5×108TB
分组密码的输出密文一般不能是明文字符串直接置换所得到的值。？要验证所有的太位输入的2*个可能值和对应的k位输出。？一般不会是直接置换
00000001—a—>01000000
00000001—b—>11011110
3.2攻击类型
分组密码在已知密文攻击条件下是安全的，但大多数分组密码面对明文攻击无效
相关密钥攻击 是一种对实际系统的攻击
攻击者：已知加密函数，未知密钥
攻击漏洞：在分组密码的标准协议中需要的两个密钥有如下关系∶一个密钥K是随机产生的，另一个密钥K'是K加上一个固定的常数。这使得同一系统的密钥间存在相关性而可以被猜测到，如一个系统通过将密钥+1的方式生成不同的（连续）密钥
选择密钥攻击 攻击策略？
攻击部分密钥，剩余部分采用相关密钥攻击，详见3.5.4
Davies-Meyer 构造：分组密码中构造散列函数的标准技术。
攻击者可以随时选择分组密码的密钥，进行相关密钥攻击和选择密钥攻击
分组密码应提供简单的接口，以确保所有的性质都可以被使用者合理地利用，并以交叉依赖的形式，允许接口增添其他复杂功能。
挑战：如何根据分组密码的功能需求确定合理的性质。
3.3理想分组密码
核心：随机置换
对于每个密钥值，分组密码都是一个随机置换，而且不同密钥对应的置换应该是完全独立的。
我们把理想分组密码当作在所有可能的分组密码集合上的均匀概率分布，它不能够在实践中获得，是一个在讨论安全性时使用的抽象概念
3.4分组密码安全的定义
一个安全的分组密码能够抵抗所有的攻击。
分组密码攻击是将分组密码从理想分组密码中分离开来的一种非通用方法。
理想分组密码能够为每一个密钥值实现独立选择的随机偶置换。
3.5实际分组密码
几乎所有分组密码都由一个弱分组密码的多次重复组成，每一次运算被称为一轮。经
过连续多轮的弱重复运算可以实现一个强分组密码。
同样地，大多数针对分组密码的攻击都是从轮数较少的版本开始
3.5.1DES
经典&应用广泛，56位密钥长度和64位分组长度提供的安全性无法满足现在的需求
当前采用3DES，分组长度不变，2个56位密钥长度，使用第一个加密，第二个解密，再用第一个加密
步骤
DES 算法有64 位明文，有16轮加密，分别被编号为1至16。每一轮使用一个48 位的轮密钥Ki。这16个轮密钥是从分组密码的 56 位密钥K中选择48位生成的，对于每一轮密钥，选择方式都是不同的。这个由主分组密码密钥生成轮密钥的算法称为子密钥生成器（key schedule）。
首先将明文进行IP 置换。然后将明文从中间分成左右两部分，分别是32位的L和R。在一轮加密结束后同样交换L和 R的序列以得到64 位的密文。
轮函数通过一系列的运算改变（L，R）的值。32位的R值首先要经过扩展函数得到48 位的输出。然后和轮密钥Ki，进行异或并将结果输入S盒。
S(substitution替代)盒是一个公开的查找表。48位的输入被分成一些组，每组大小约为4～6位。S盒将48位的向量通过非线性映射成为32位的向量。
这32位经过位变换函数后与L异或得到新的L，将此L和R的值互换，进入新一轮的加密。
image-20210321000554801
Feistel结构：每一轮通过L和F(Ki,R)的异或生成新的L，然后将L与R交换
方便硬件实现，可以使用相同电路进行加解密计算
扩散性能：输入F的任何一位发生变化都影响到输出密文的许多位（雪崩效应）
DES中由S盒、扩展函数、位变换函数的结合提供扩散性能
弱密钥性：每一轮的轮密钥都是由分组密码的主密钥的某些位生成的。
互补：如果使用取反的密钥加密取反后的明文值，那么所得到的密文是原密文的取反。
弱密钥性与互补性使得DES不安全，3DES也继承了这些弱点
3.5.2AES
Rinjdael算法，取代DES，没有采用Feistel结构
分组长度为128bit，密钥长度有128位、192位、256 位。使用128 位密钥加密10轮，192 位密钥加密 12轮，256 位密钥加密14轮
步骤
输入 16字节（128位）的明文，首先将明文与16字节的轮密码进行异或操作，在图中用④运算符来表示。
然后进入8位输入8位输出的S盒，这些S盒内部结构均是相同的。
输入后按照特定的顺序重新排列输出。
最后分为4个组，使用线性混合函数进行异或运算得到输出结果。
image-20210321001710399
结构优缺点：每一个执行步骤都包含了多个并行运算，可以实现高速运算;解密和加密运算完全不同，需要逆转 S盒的查找表，而且混合运算的逆运算也和原混合运算不同。
多轮次有助于AES的安全性，但从理论上AES已经被攻破
3.5.3 Serpent
相对AES更注重安全性，也更加缓慢，速度仅有AES的三分之一
执行32轮，同时每一轮需要32个S盒查找表，可以通过将S盒转换为布尔运算提高CPU的操作速度
3.5.4 Twofish
速度同AES且更安全，但由于会使用密钥进行大量预运算所以更改加密密钥代价大
轮函数由两个g函数、一个被称为PHT的函数和密钥相加运算构成。一个g函数包含4个S盒，然后是一个线性混合函数。S盒的结构依赖于密钥，预计算结果保存在内存中。PHT函数通过32位加运算混合两个g函数的输出结果。F函数的最后部分是对密钥进行加法。
image-20210321003028662
whitening（白化）技术：在密码算法的开始和结束使用额外的密钥加密数据，能以很小的代价使得算法更加难以攻破
3.5.5其他的AES候选算法
RC6
使用32位乘法，执行20论，AES竞争已经可攻破17轮
MARS
具有非均匀结构，使用不同种类运算，实现代价高
3.5.6如何选择分组密码
AES执行速度快，有一定安全性，而且由于成为标准，密码库支持程度高，容易使用和实现
3DES安全性不足，在限制64位分组长度的情况下是最好选择
为提高安全性可以使用双重加密，多种算法&多种轮次&多种密钥长度，应使用不同的、独立的密钥
对AES安全性的判断应参考后续分析建议。另外，AES的执行时间会透漏出密钥的一些位，所以应尽量隐瞒时间信息
3.5.7如何选择密钥长度
对于一个n位的安全等级，分组密码的长度应该为2n位长（参考2.7的生日碰撞攻击）
设计强度是128位并不代表采用256位长度的密钥
第4章 分组密码工作模式
分组密码只能加密固定长度，使用分组密码工作模式可加密非恰好分组长度的数据
可提供机密性，但不能进行认证。攻击会产生许多无意义垃圾信息，某些模式还允许针对性的明文修改，甚至许多数据格式可以通过局部地随机修改来操纵。
4.1填充
大多数模式要求明文长度是分组大小的整数倍，所以需要填充明文，但填充应可逆，以确保可用性
一个填充规则满足如果明文已经符合长度要求就无须进行填充是非常理想的，但这很难对所有情况都满足。对可逆的填充方案，都可以找到一些长度已适合但还需进行填充的消息，实际上所有填充规则都会给明文增加至少一个字节。不是很明白？？
填充方案
明文接下来的第一个字节中填充 128，然后填充0直到整个长度满足b的倍数。填充0的字节数介于 1，⋯，b-1 之间。
首先计算需要填充的字节数，该字节个数n满足1≤n≤b并且n+（P）是b的倍数。然后在明文后附加n个字节，每个字节填充的值为 n。
解密密文后填充部分须被移除。用于移除填充的代码还应该检测是否使用了正确的填充。
4.2 ECB
电子密码本（ECB）分别加密明文消息的每个分组。Ci=E(K, Pi) i= 1⋯,k
ECB有严重缺陷，明文分组相同使密文分组相同，这对攻击者是可见的。而由于编码或信息主题等问题，可能会出现大量重复分组而使信息泄露
4.3 CBC
密码分组链（CBC）通过将每个明文分组与前一个密文分组进行异或操作 Ci=E(K, Pi⊕Ci-1) i= 1⋯,k
通过前一个密文分组实现随机化，初始向量为C0或IV
4.3.1固定IV
实际应用中的消息经常会以相似或相同的分组开始，固定IV会使起始密文相同
4.3.2计数器IV
以计数器作为IV，但也可能重新生成相同的密文分组
4.3.3随机IV
选择随机IV并作为第一个密文块放在消息所对应的密文之前发送给接收者
C0=随机分组值
Ci=E(K,Pi⊕Ci-1) i= 1,…,k
解密Pi=D(K,Ci)⊕Ci-1) i= 1,…,k
主要缺点就是密文比明文多一个分组
4.3.4瞬时IV
瞬时值为每一个用该密钥加密的消息分配一个唯一的数，瞬时值是消息的某种编号
为消息分配一个消息编号。通常，消息的编号由一个从0开始的计数器提供，而计数器在任何时候都不能返回 0，否则就会破坏唯一性。
由消息编号构造唯一的瞬时值。对给定的密钥，瞬时值不仅在这台计算机中是唯一的，甚至在整个系统都是唯一的。例如，同一个密钥用于加密双向的通信，此时瞬时值应该由消息编号与消息的发送方向标识组成。瞬时值的大小应该是分组密码的单个分组大小。
用分组密码加密瞬时值得到IV。
在 CBC模式下使用此 IV 对消息加密。
在密文中添加足够的信息使接收者能够恢复这个瞬时值。有一种方法是在明文的前面附加消息编号，或者通过可靠信道传输密文，这时消息编号将是隐含的，IV值本身（公式中的C0）不需发送。
任何实际系统都需要确保瞬时值的唯一性。但是并不是说可以任意选取瞬时值，所以在大多数情况下就如加密消息一样使用相同的密钥加密瞬时值。
4.4 OFB
输出反馈模式（OFB）不是将消息作为加密函数的输入进行加密，而是使用分组密码生成一个伪随机字节流（称为密钥流），然后将其与明文进行异或运算得到密文。这种用生成随机密钥流进行加密的方案称为流密码。
K0:= IV
Ki:= E(K,Ki-1) i= 1,⋯,k
Ci:=Pi⊕Ki
优点
OFB的解密运算和加密运算完全相同，所以无须再实现解密函数。
OFB不需要对明文进行填充
缺点
一旦有两个不同的消息使用了同一个IV，那么这两个消息就被相同的密钥流加密。
如果一个密钥分组重复出现，那么随后密钥分组序列就与之前的重复了。
4.5 CTR
计数器模式(CTR) 也是流密码模式，但避免了短循环问题
Ki:= E(K,Nonce||i ) i=1,…, k
Ci:=Pi⊕Ki
生成密钥流：瞬时值与计数器值连接起来，然后进行加密产生密钥流的一个密钥分组
瞬时值与计数器值的连接不能超过单个分组的大小
典型的分配方案是消息编号占48位，瞬时值的附加数据占16位，而其余 64位用于计数器i。这样将把系统限制为使用一个密钥只能加密248个不同的消息，每个消息最多有268字节。
同OFB一样，必须保证IV或瞬时值的唯一性
由于CTR模式的密钥流中的任意一个密钥块都可以及时计算，可以非常容易地获取明文的任一部分
CTR的安全性也可以被认为就是分组密码的安全性
4.6加密与认证
CCM模式与GCM模式能够同时提供认证和加密，详见第七章
4.7如何选择工作模式
仅考虑使用CBC与CTR模式
CBC
优点：更强的健壮性，即使误用也能很好地工作
缺点：密文更长，明文需要填充，系统需要随机数生成器
CTR
优点：由一定健壮性，密文较短
缺点：依赖正确生成瞬时值，而在很多系统中较为困难
流量分析：攻击者获取并分析正在通信、在何时通信、通信的数据量、在和谁通信等信息
4.8信息泄露
ECB：如果两个明文分组相同（Pi=Pj），那么对应的密文分组也相同（Ci=Cj）。
CBC：由于每一个明文分组首先与前一个密文分组进行异或运算后再加密，从而使得相同的明文分组所对应的密文分组不一定相同。但这说明两个明文分组的差别等于对应密文分组的异或。如果存在大量冗余的数据，明文分组就可能被恢复。
CTR：由于任意两个密钥分组都不相同，所以从两个相同的密文分组或两个相同的明文分组并不能获取更多信息
OFB：只要密钥流分组没有碰撞发生，它与CTR模式一样会泄露同样多的信息;如果两个密钥流分组出现碰撞，那么后续的密钥流分组也会发生碰撞。
4.8.1碰撞的可能性
两个密文分组相同的概率分析：
假设总共加密M个明文分组。至于这 M个明文块是由几个长消息还是由很多个短的消息组成都无关紧要，重要的是分组的数量。在这M(M-1)/2个不同的分组对中，任意一对相等的可能性为2-n（n为分组长度)。因此，相同密文分组对数量的期望值是M（M-1）2"'。当M≈22时，这个期望值接近于1。这就是说大约加密2n/2个明文分组就很可能得到两个相等的密文分组。当n=128位时，大约加密264个明文块就可以期望得到两个相同的密文分组
考虑一般应用系统有30年寿命，未来人们可能会处理这么大的数值
加密较小的数据量会出现风险
假如处理240个分组（大约16TB的数据量），那么就有2-48次机会得到一对相同的密文分组。这是一个非常小的概率，但是对于攻击者来说，可以取定一个特殊的密钥，收集240个分组并检测重复的分组。这样成功的机会当然也很小，但是可以对大约248个密钥重复这个工作，攻击者要找到一个碰撞的计算量为240x248=288，远远小于128 位的设计强度。
4.8.2如何处理信息泄露
128位的安全等级难以真正达到，能够做到的是尽量接近期望的安全等级，尽量减轻有可能带来的危害。
CTR模式下，泄露较少，加密264分组会泄露一位信息
对策：限制单个密钥加密的信息总量、限制加密不超过260个分组
CBC模式下，一旦发送碰撞会泄露128bit的明文信息。
对策：降低碰撞概率，加密数据量为232个分组作用，使得泄露风险概率变为2-64
4.8.3关于数学证明
密码学的概率计算通常没有足够考虑独立性，但这样已经足够产生我们所需的精确程度