考研复习 Day 39 | 密码学--第四章 分组密码（上）
注：以下内容参考《新编密码学》范九伦 张雪锋 侯红霞 编著
第4章 分组密码
4.1 分组密码的设计准则
分组密码（Block Cipher）是现代密码学的重要组成部分，主要功能是提供有效的数据保护。分组密码对固定长度的一组明文进行加密，该固定长度称为分组长度。传统上，通过计算机实现的分组密码常选取64位作为分组长度，这是安全性与实用性的折中选择。近年来，随着计算能力提升，64位分组长度的安全性逐渐不足，许多分组密码开始采用128位作为分组长度。
分组密码的加密过程按分组长度 n 将明文分成若干组，对每组执行相同的加密操作，产生一个 n 位的密文分组。不同的 n 位明文分组共有 2^n 个。为保证可逆性（即解密可行性），每个明文分组应映射为唯一的密文分组，这种变换称为可逆变换或非奇异变换。
4.1.1 填充问题
当明文长度不是分组长度的整数倍时，需要进行填充。常见的填充方式有四种：
1.Zeros填充：填充字节全为0。不可逆（无法区分原始0与填充0）。
2.X923填充：填充字节中前若干字节为0，最后一个字节记录填充总字节数。可逆。
3.PKCS7填充：每个填充字节都等于所需填充的总字节数。可逆。
4.ISO10126填充：填充字节中前若干字节为随机数，最后一个字节记录填充总字节数。可逆。
4.1.2 Feistel分组密码结构
Feistel密码结构基于Shannon提出的扩散和混淆思想：
扩散：使明文与密文之间的统计关系复杂化，每个密文位与多个明文位相关。
混淆：使密文与密钥之间的统计关系复杂化，防止密钥推测。
Feistel分组密码的基本结构如图4-1所示。加密输入为 2L 位的明文分组和初始密钥 K，先将明文等分为左半部分 L0 和右半部分 R0，各 L 位。加密共进行 n 轮，第 i 轮以 L(i−1) 和 R(i−1) 为输入，并包含从初始密钥生成的子密钥 Ki。每轮操作如下：
解密过程与加密过程相同，但子密钥使用顺序相反（Kn,Kn−1,…,K1）。
Feistel密码的安全性取决于：
1.分组大小（越大越安全，但效率越低）
2.子密钥大小（至少128位）
3.循环次数（越多越安全）
4.子密钥生成算法的复杂度
5.轮函数 F 的复杂度（核心是S-盒的非线性）
4.1.3 轮函数 F 的设计准则
轮函数 FF 的核心是S-盒（替换盒）。设计准则包括：
1.非线性：非线性程度越高，算法越安全。
2.严格雪崩准则（SAC）：任一输入位改变时，任何输出位改变的概率为 1/2。
3.比特独立准则（BIC）：任一输入位改变时，任意两个输出位的变化相互独立。
4.保证雪崩准则（GAC）：输入改变1位时，输出至少有 2∼5 位发生改变。
4.2 数据加密标准——DES
DES（Data Encryption Standard）是最广泛使用的分组密码之一，对推动密码学发展起了重大作用。DES以64位为分组对数据进行加密，密钥长度为64位（实际有效56位，另8位为奇偶校验位）。DES包含16轮“替换—置换”操作。
4.2.1 DES的加密流程
一、初始置换（IP）：对64位明文进行置换（见表4-1）。
二、16轮Feistel结构加密：每轮使用48位子密钥，操作包括：
1、密钥置换与循环移位：56位密钥分为两半，根据轮数循环左移1或2位（见表4-3），再通过压缩置换（表4-4）生成48位子密钥（图4-5）。
2、扩展变换（E-盒）：将32位右半部分扩展为48位（表4-5）。
3、与子密钥异或。
4、S-盒替换：8个S-盒（表4-6），每个将6位输入映射为4位输出。输入的第1、6位决定行，第2–5位决定列（例4.1）。
【例4.1】假设对应第6个S-盒的输人序列为110011。其中，第1位和最后一位组合构成的序列为11，对应的十进制数字为3,说明对应的输出序列位于S-盒的第3行;中间的4位组合构成的序列为1001，对应的十进制数字为9，说明对应的输出序列位于S-盒的第9列。第6个S-盒的第3行、第9列处的数是14(注意:行、列的记数均从0开始，而不是从1开始)，14对应的二进制为1110，对应输人序列110011的输出序列为1110。
5、P-盒置换：对32位结果进行置换（表4-7）。
6、与左半部分异或并交换左右。
三、逆初始置换（IP⁻¹）：得到64位密文（表4-8）。
例4.2给出了明文computer、密钥program的完整加密过程示例。
4.2.2 DES的解密
DES的解密与加密使用相同算法，仅子密钥使用顺序相反：加密使用 K1,K2,…,K16，解密使用 K16,K15,…,K1。解密时初始密钥进行循环右移操作生成子密钥。
4.2.3 DES的安全性分析
1.S-盒：是非线性核心，设计标准最初保密。已知S-盒具有良好非线性，输入改变1位至少改变2位输出。
2.弱密钥：存在四种弱密钥（如全0或全1等）和若干半弱密钥。
3.密钥长度：56位密钥空间 2⁵⁶，已能通过穷举搜1.索破译（1999年EFF破译机22小时破译）。
4.2.4 密码分析方法的演进
1.第一阶段：利用互补性、弱密钥等，未构成实质威胁。
2.第二阶段：差分密码分析、线性密码分析出现，可破译8轮、12轮DES。
3.第三阶段：专用硬件穷举搜索（EFF破译机）可在两天内破译DES（2000年仅2小时）。
4.2.5 DES的贡献
1.展示了适应历史阶段信息安全需求的密码体制构造方法。
2.确立了“算法公开、密钥保密”的标准化原则。
3.证明了分组密码标准化的可行性。
4.确立了安全使用分组密码的若干准则。
5.推动了密码分析理论（差分分析、线性分析等）的快速发展。
4.2.6 DES的改进方法
改进方法一（密文反馈）：
对明文分组,(i=2，3,…,n)进行加密前，先将明文分组消息和前一组加密的密文分组序列 y-进行异或运算，然后对运算的结果序列进行加密操作。即
迭代结构分组加密流程如图4-7所示。
相应的解密过程为
迭代结构分组解密流程如图4-8所示。
对于改进方法一，由于采用了密文反馈的方式进行加密，当明文序列的结构有一定的固定格式时，相应的密文序列表现出的规律性会被隐藏，从而能有效改进加密算法的安全性。
改进方法二（多重DES）：
1、双重DES：最简单的双重 DES加密过程是采用两个不同的密钥分两步对明文分组消息进行加密。给定一个明文分组x和两个加密密钥K,和K，相应的密文消息y由下式得到:
密钥长度112位。但可被中间相遇攻击破解，工作量约 2⁵⁷。
2、三重DES（EDE模式）：在该加密算法中，加密过程用两个不同的密钥K,和K。对一个分组消息进行3次DES加密。首先使用第一个密钥进行 DES加密;然后使用第二个密钥对第一次的结果进行DES解密;最后再使用第一个密钥对第二次的结果进行 DES加密。
密钥长度112位，被广泛接受并用于密钥管理标准（ANSI X9.17, ISO 8732）。
4.2.7 AES的诞生
1997年，NIST发起征集DES替代算法——AES。经4年评选，最终选定比利时密码学家Daemen和Rijmen提出的Rijndael算法作为AES。
注：以上内容的理解和计算，如果有任何错误，希望各位读者和大佬指出改正，非常感谢！！！