密码学实践-读书笔记四五
第四章 分组密码
一、分组密码简述：
1、分组密码是目前密码学领域研究较为深入和完善的部分。
2、密文块与明文块大小相同（例如本章后面会提到的DES与AES）。
3、分组密码是可逆的（即对于一个加密函数有对应的解密函数）。
4、分组密码主要用于信息的加密，对于较短的消息可以直接用分组密码进行加密，但对比其分组长度还长的消息，加密需要使用分组密码模式（在第五章会详细阐述）。
5、根据Kerckhoffs（柯克霍夫）原则，加密与解密的算法总是公开的。
6、可将分组密码加密看成是明密文对照表。因为可逆，使得一个密文值在该表中只出现一次。而该表也可看作置换—–所有可能值的重新排序。
二、攻击类型：
分组密码特有的攻击：
1、相关**攻击：攻击者可以访问几个加密函数，攻击者不知道每个加密函数的**，但是知道**之间的关系。
2、选择**攻击：攻击者先指定**的一部分，而后对**的其余部分完成相关**攻击。
三、理想的分组密码：
在定义安全性前，需要定义理想分组密码，一个理想的分组密码由每个**所对应的置换表组成，而且这些置换从所有可能的置换集合中完全随机选取。
（例如，一个128比特的分组密码就是一个2128个元素且每个元素均为128比特长的表）
然而现实：只要确定了置换的选择方法，那么这个理想的分组密码就不再是随机的。因此需要将其当作所有可能的分组密码上的均匀随机分布，与概率有关。
四、分组密码安全性的定义（非正式）：
1、 如果不存在攻击方法，则分组密码是安全的
2、 分组密码的攻击是一个区分分组密码与理想分组密码的非平凡的算法。（非平凡？）
将给定的分组密码X与一个具有同样分组大小和**长度的理想分组密码进行比较。将其中之一作为黑盒，某一个区分器算法就能区分它们。
区分器算法应该比在n比特上的穷举搜索更有效，也就是说计算量小于2n。而穷举搜索一半的**空间的计算量为2n-1，得到正确结论的可能性为75% = 0.5+0.5*0.5。（找到**则得到正确的结果，失败仍有50%的机会猜到结果），将区分器有部分**搜索进行比较，考虑计算量和区分能力之间的权衡。
五、置换的奇偶性：
奇偶攻击：对给定的**可以通过加密所有可能的明文获得这个置换，奇置换则是理想的分组密码，偶置换是一个真实的分组密码。
但是要确定置换的奇偶性，必须计算加密函数的一个明文密文对以外的其他所有明文密文对（最后一个可以由此导出），而实际上不允许计算如此多的明文密文对。文章倾向于将理想分组密码的定义进行适当的修改：
理想的分组密码实现为每一个**独立地选择一个随机偶置换。（经过偶数次交换元素得到的置换）
但是：这个定义是理想分组密码更难理解，只要不允许计算明文密文对。就不能区分奇偶置换。
最后说明：奇偶攻击的意义主要在于安全性的形式定义而不存在于实际系统，因此可以忘掉有关奇偶攻击的结果。
六、实际的分组密码：
1、DES（feistel结构）：
**长度为56比特
分组长度为64比特
过程：共16轮，将64比特明文分为32比特的块，右半部经过扩展函数将32位变为48位，然后将48比特的轮**与其异或，结果经过S盒变换为32比特，最后经过一个置换作用与左半部分异或。
各部分功能：
1、与轮**的异或保证了**数据的完全混合；
2、S盒提供了非线性；
3、S盒与扩展函数与置换保证了DES的扩散性。
互补性：原**的补作为**加密原明文的补得到的密文是原密文的补。
DES**长度不够，通过简单的穷举搜索可以寻找DES**。
3DES（三重数据加密算法）解决了DES的小**问题（56*3=168位），但是没有解决小的分组长度问题
C=Ek3(Dk2(Ek1(M))) ，可以注意到当k1，k2，k3相同时，就退化为DES（兼容）。
2、AES（Rijndael）：
15个算法首轮入选，5个算法进入决赛，Rijindael算法胜出。
过程：明文长度为16字节，首先将明文与16个字节的轮**异或，按字节将8比特映射为8比特的S盒，所有的字节对应的S盒相同，将这16个字节用一个指定的顺序重新排列。最后分为4个组用线性混合函数进行混合。（字节代换、行移位、列混合、轮**加）
薄弱环节：简单的代数结构，其加密是有限域上的封闭的代数公式，当能求解这些公式，则AES将被攻破。
3、Serpent：AES候选算法之一（相对保守）
AES强调简练与效率，而Serpent更加注重的是安全性。
共32轮，速度慢，为AES 的1/3。
在32轮中，每一轮并行查找32个S盒，共进行1024次查找，速度很慢，可以将S盒表示为布尔公式，将S盒的4位输出表示为4位输入的布尔函数。
4、Twofish：候选算法之一，也使用feistel结构，将128比特的明文分为4个32比特，速度几乎与AES一样，16轮，由于大量的**预计算，缺点是改变加***很不方便。
加上AES与不推荐的RC6、MARS共5种。
七、求解方程攻击：
将分组密码的加密写为有限域上的一组线性和二次方程，求解。
有人认为这些攻击仅仅是理论上的，实际不会成功。
八、**应为多大：
AES、Serpent、Twofish都有128比特、192比特、256比特或更长的**。
设计准则：要求有n比特的安全水平，所有的密码值至少应为2n比特。但很难遵守，（例如：为获得128比特的安全性确实想采用256比特的分组密码，但实际分组长度都为128比特）.
仍需进一步努力的方向。。。
XSL攻击：eXtended Sparse Linearization Attack（扩展稀疏线性化攻击），分组密码的一种密码分析，线性攻击属于已知明文攻击，通过寻找明密文之间的一个有效的线性逼近表达式将分组密码与随机置换区分开。
差分攻击通过比较分析有特定区别的明文在通过加密后的变化传播情况来攻击密码算法。
第五章 分组密码模式
分组密码只能加密固定大小的明文块，如果要加密的明文大小不是分组的大小，需要使用分组密码模式。
大部分模式要求明文的长度刚好是分组大小的整数倍，因此需要填充。
填充基本原则：填充必须可逆，即能够从填充后的消息唯一确定原始消息。
事实上，所有填充规则至少使明文长度增加一个字节。
填充方法：
1、先添加值为128的一个字节，然后添加一些0字节使得总长度为b的倍数。
2、首先确定组要填充的字节数n然后填充n个值为n的字节。
ECB：
电子密码本模式
存在严重的缺陷：当两个明文块相同的时候，它们对应的密文快也一定相同
CBC：
密码分组链接模式
C0 = IV（初始向量），不应使用固定的初始向量，否则每个消息的第一个块出现ECB的问题。
计数IV、随机IV、瞬时IV
瞬时IV：
首先，为每一个用改**加密的消息分配一个唯一的值，称为瞬时值。
然后，对瞬时值加密得到CBC必需的IV
OFB：
用随机**流进行加密的方式称为流密码。
首先用分组密码生成一个伪随机字节流，然后将其与明文进行异或运算得到密文。
OFB优点：加密运算与解密运行一样。不需要对明文填充。
危险：不同的消息使用了同一个IV，会被相同的**流加密。可以计算出两个明文之间的不同，从而从一个明文得到另一个明文。
如果**块重复出现，那么**块序列就会出现循环，对一个较大的消息，**块序列有可能陷入一个循环中，另外，如果一个消息的IV与另外一个消息所对应的**块序列中的某一个**块相同，则这两个消息的一部分就使用了相同的**块序列。
CTR：
与所有流密码一样，加密时必须使用某种形式的唯一瞬时值，而大多数系统都用消息编号与某些附加信息来生成瞬时值，来保证唯一性。
CTR也不能重复使用一个**和瞬时值组合
CBC与CTR都必须保证IV与瞬时值的唯一性
CTR易使用，加密函数与解密函数一样都是加密函数
PS: 这这本书中只是详细提到了ECB、CBC、OFB与CTR这四种工作模式。但还有CFB等。
需要注意的是，安全性的证明并不是证明这个系统是安全的，而是给出了一个安全性的规约。例如，证明的结论是如果可以在X时间内攻破某个工作模式，那么就可以在Y个时间内攻破基本的分组密码。
模式的选择
作者建议使用CBC与CTR模式，ECB是毋庸置疑的不安全，而OFB有短循环的问题，因此，应该选择CTR而不是OFB。
对于CTR与CBC：
（ECB与CBC都是需要在最后一块在加密前进行填充处理）
分组密码加密模式不是一个完整的加密系统，依赖于系统的其他部分（瞬时值由系统的其他部分提供）
加密模式仅仅提供的是机密性，无法阻止攻击者对数据的修改。
信息的泄露：
对于ECB：
如果两个明文块相同，那么对应的密文块也相同，因此舍弃
对于CBC：
每一个明文块先与前一个密文块异或，当有两个相同的密文块的时候
也就是说，两个明文块的差别等于对应密文块的异或，而攻击者知道了密文块的异或。
当两个密文块不相同的时候，蕴含了不等式 。
对于CTR也是有类似的性质，对于给定的两个密文块有 ，由于CTR中任意两个**块都不相同，所以两个密文块相同或者两个明文块相同并不能获得更多的信息，从而使得CTR没有碰撞问题。
对于OFB：
只要没有碰撞发生，与CTR类似，但是，一旦出现碰撞，即两个**块相同，那么后续的**块也发生碰撞。
碰撞的可能性：
M个明文块（块长n）
两两一对共M(M-1)/2个不同的对
两个块相同的概率为 2-n
密文块相同的数量的期望值为M(M-1)/2n+1
当M大约为2n/2的时候可以达到两个相等的密文块（生日悖论）