《密码编码学与网络安全原理与实践》第四章第六章第七章 对称加密体制

基础知识

对称加密包括分组密码和流密码

分组密码：信息被分块（block）进行加密和解密，连续的明文元素使用相同的密钥K来加密，密文$C=c_1{c}_2\dots =E_K(m_1)E_K(m_2)\dots$。分组密码可以看作是一个字符长度很大代换——如64比特或更多。大部分的分组对称密码都基于Feistel结构。可逆变换是必要条件。设计”安全”的密码算法不难,只要使用足够多的轮数就可以,但降低速度，因此所有问题就是平衡问题。

流密码：流密码中按照bit或者byte对信息进行加密和解密。产生一个密钥流$k=k_1{k}_2\dots$，密文$C=c_1{c}_2\dots =E_{K_1}(m_1)E_{K_2}(m_2)\dots$。Vigenere密码和Vernam密码都是流密码。又叫序列密码。

现有的大量密码为分组加密，分组加密的应用更为广阔，可以提供安全性/认证性的安全服务。我国颁布的商用密码标准算法中的序列密码算法和分组密码算法分别是ZUC和SM4算法，SM1，SM7。国外常见的序列密码算法有SNOW算法（如SNOW 2.0、SNOW 3G）、RC4等

Feistel提出交替使用替代和换位的方式构造密码，其理论基础是Shannon提出用混淆(confusion)和扩散(diffusion)交替的方式构造密码

Shannon在其1949年的文献中引入了代换-置换网络(SPN)，这是现代分组加密的基础，SP网络基于两个基本的密码学操作：代换（substitution，也称S盒子）、置换（permutation，也称P盒子）对消息和密钥进行混淆和扩散

混淆－使得密钥和密文之间的统计关系尽可能的复杂，阻止攻击者发现密钥。

扩散－使明文的统计特征消散在密文中，让每个明文影响尽可能多个密文。尽可能使得密文和明文间的统计关系更加复杂。

乘积密码：依次使用两个或者两个以上的基本密码，所得结果的密码强度将强于所有单个密码的强度

祖冲之算法：（流密码）

采用128比特的初始密钥和128比特初始向量作为输入参数，共同决定LFSR里$S_0$到$S_{15}$这16个字节的初始状态。随着电路时钟的变化，LFSR的状态被比特重排（BR）之后输入非线性函数F，每一拍时钟输出一个32比特的密钥码流字Z

上层：线性反馈移位寄存器（LFSR），产生小m序列，具有良好的随机性。LFSR的输出作为中层的输入。

中间层：比特重组（BR）从线性反馈移位寄存器的状态中取出128位，拼成4个32比特字（$X_0，X_1，X_2，X_3$），供下层的非线性函数F和输出密钥序列使用。

下层：非线性函数F，从BR接受3个32位字（$X_0，X_1，X_2$）作为输入，经过内部的异或、循环移位和模$2^{32}$运算，以及两个非线性S盒变换，最后输出一个32位字W。非线性函数F是祖冲之密码算法中唯一的非线性部件。

Feistel（分组密码结构）

Shannon在其1949年的文献中引入了代换-置换网络(SPN)，这是现代分组加密的基础，SP网络基于两个基本的密码学操作：代换（substitution，也称S盒子）、置换（permutation，也称P盒子）对消息和密钥进行混淆和扩散。

由Horst Feistel发明了Feistel密码基于可逆的乘积密码。目标是逼近简单代换密码.

进行多轮迭代，每轮都有相同的结构（如下图），

解密本质上与加密过程一致，只需将密文作为算法的输入，但是逆序使用子密钥$K_i$

分组大小：分组越长安全性越高，但是会降低加、解密的速度 。64位分组长度比较合理
密钥长度 ：密钥较长同样意味着较高的安全性，但会降低加、解密的速度。通常使用128位。
轮数：Feistel的本质在于单轮不能提供足够的安全性，多轮可以取得很高的安全性，典型值是16
子密钥产生算法：越复杂，密码分析攻击就越困难
轮函数：越复杂，抗攻击能力越强
快速软件加/解密
简化分析难度：指算法描述简洁清楚，其脆弱性就容易分析，可以开发出更强的算法

DES

DES分组长度64bit，密钥长度为56bit，16轮，具有feistel结构

(实际上这个密码函数希望采用64bit的密钥，然而却仅仅采用了56位，其余8位可以用作奇偶校验或随意设置)

其中初始置换和逆置换，是要对输入数据重排序，偶数位放在上半边，奇数位放在下半边，如下图所示：

每轮要进行的Feistel结构为：

$R_{i-1}$先经过表E进行扩充置换从32比特变成48比特，然后与密钥$k_i$进行异或，然后经过S盒进行代换/选择变成48比特，然后经过P盒进行置换，最终与$L_{i-1}$进行异或得到$R_i$，而原本的$R_{i-1}$变成了$L_i$。

其中表E如下图，32位输入分为4位×8组，每组从相邻两组中取得位置靠近的一位，成为6位，最终原本的32位就变成了48位。

S盒共8个，前四个如下图，每个S盒子实际上是4个小的4位盒子。6个比特中，第1位和第6位决定S盒子的行，第2，3，4，5位决定S盒子列，用行列交叉处的S盒子值进行代换，8个S盒子的输出为4×8=32比特。

而密钥要进行的运算，56位要分成左右两组，每组都要先左移再置换，生成了48位的密钥供加密系统使用，而移位之后左右两组再进行下一轮的运算

雪崩效应

雪崩效应：明文或者密钥的微小变化将对密文产生很大影响，是加密算法的核心需求

要求：输入或者密钥的1比特的变化，大约引起输出比特一半的变化

避免给密码分析者提供缩小搜索密钥或者明文空间的渠道

“好的”密码设计具有: 雪崩特性、不可预料性(avalanche, unpredictability )

差的密码设计缺乏随机性、具有太大的可预料性

严格雪崩准则(SAC)：对于任何$i,j$,当任何一个输入比特$i$变化时，一个S盒子的任何输出比特j变化的概率为1/2

位独立准则(BIC): 对于任意$i,j,k$,当任意输入比特变化时，输出$j$和$k$应当独立变化

双重DES加密

密钥空间为$2^{112}$

1992年被证明，双重DES所对应的映射不能为单DES所定义。

中间相遇攻击：已知明文攻击可以成功对付密钥长度为112位的双重DES，其付出是$2^{56}$数量级，比攻击单DES所需的$2^{55}$数量级多不了多少。（这种方法不依赖于DES的任何特殊性质，对所有分组密码都有效）（存在$X=E(K_1,P)=D(K_2,C)$等式成立，中间相遇攻击使用两组已知明密文对就可以猜出正确密钥的概率为$1-2^{112/64-64}=1-2^{-16}$，因此双重DES不能提高DES的安全性）

三重DES加密

使用三个K进行三次加密，已知明文攻击的代价将上升至$2^{112}$，密钥长度168位

使用三个K进行加密-解密-加密（EDE）：$C=E(K_3,D(K_2,E(K_1,P)))$

要想和单DES兼容，只需设$K_3=K_2$或$K_1=K_2$就可以了。

（为什么3DES中间是解密而不是加密：为了兼容普通的DES）

NIST在1999年发布新版DES标准（FIPS PUB46-3），指出DES只能用于遗留系统，3DES将取代DES成为新标准。

优点：密钥长度112bit,足够长、底层算法与DES相同，因此受密码分析时间远远长于其他加密算法，对密码分析攻击有很强免疫力、仅考虑安全性，3DES会成为未来数十年加密算法的合适选择

缺点：DES的设计主要针对硬件实现，而今在许多领域，需要用软件方法来实现它，在这种情况下，DES效率相对较低、分组长度64，似乎应该更长

因此，理论上，3DES不能成为长期使用的加密算法标准

IDEA：

设计原理：

IDEA是一个分组长度为64位，密钥长度为128位的分组密码算法，64位明文分成4块 $X_1,X_2,X_3,X_4$经8轮迭代，同一算法可加密解密，可以抵抗差分攻击

IDEA“混淆”和“扩散”设计原则来自三种运算：逐位异或、模$2^{16}$整数加、模$2^{16}+1$整数乘⊙

易于软、硬件实现

软件实现比DES快两倍，抗穷举攻击（软件实现比DES快两倍）、抗差分攻击（Lai证明了IDEA的第四轮以后对差分免疫）、存在极少的弱密钥

AES

比三重DES快、至少和三重DES一样安全

分组长度128比特，支持密钥长度为128/192/256比特，相应的轮数r为10/12/14；

核心是Rijndael算法（其原型是Square算法），可抗击差分分析和线性分析

NIST最终选择了Rijndael作为AES的标准，因为全面地考虑，Rijndael汇聚了安全，性能好，效率高，易用和灵活等优点

不是Feistel结构，加密解密算法不同

对于加密和解密：

均以轮密钥加作为开始、9轮迭代，每轮包括：

字节代换：S盒子 （代换，之前有密钥，属于混淆，非线性）

行移位：简单置换 （属于扩散，线性）

列混淆：利用域$GF(2^8)$上的算术特性（属于扩散，线性）

轮密钥加：当前分组 XOR 轮密钥 （Vernam密码，线性）

第10轮只包含 字节代换、行移位、轮密钥加

（扩散就是让明文中的每一位影响密文中的许多位，或者说让密文中的每一位受明文中的许多位的影响．这样可以隐蔽明文的统计特性。

混淆就是将密文与密钥之间的统计关系变得尽可能复杂，使得对手即使获取了关于密文的一些统计特性，也无法推测密钥。使用复杂的非线性代替变换可以达到比较好的混淆效果，而简单的线性代替变换得到的混淆效果则不理想。）

目的是满足算法的可逆性

仅在轮密钥加阶段使用密钥、每个阶段均可逆、具有非常明晰的代数结构

字节替换：

行移位：

列混淆：

AES在8位的字节上运算，两个字节的加定义为对位异或操作，两个字节的乘定义为有限域$GF(2^8)$内的乘法，如果乘法运算的结构是次数大于n-1的多项式，那么必须用某个次数为n的不可约多项式m(x)进行约化，即用m(x)去除并取余式，其中不可约多项式为$m(x)=x^8+x^4+x^3+x+1$。

注意这里的$0xd4\ast 02$就是$0xd4$左移一位，然后异或$0x1b$(0001 1011)，加法就是求异或

（乘法其实就是移位加上异或。乘法单位元是1。

例如111乘以101，基于乘法分配律:$111\ast 101=111\ast 100+111\ast 00+111\ast 1=11100+0000+111=11100\oplus 111=11011$）

轮密钥加：

实质上是一种Vernam密码形式，简单的比特异或将一个轮密钥作用在状态上，

其中轮密钥是通过密钥调度（主要为密钥扩展）过程从密码密钥中获得的

密钥扩展：

密钥扩展算法的输入值是4个字（16字节），输出值是一个44个字组成（176字节）的一维线性数组。

雪崩效应

雪崩效应：AES的雪崩效应比DES的强烈

AES能再8位处理器上非常有效得实现，即所有的操作都是基于字节的；对于32位处理器，若将操作定义在32位的字上，就能执行更有效的操作（可以用代数形式定义一轮的四个变换（矩阵运算））。

SM4

于2006年公开发布，目的是配合WAPI无线局域网标准的推广应用

是一个迭代分组密码算法，数据分组长度为128比特，密钥长度为128比特。

加密算法与密钥扩展算法都采用32轮迭代结构，是非平衡的Feistel结构（加解密算法相同，轮密钥的使用顺序相反）

设计上资源重用，密钥扩展过程和加密过程类似

加密算法由32次迭代运算和1次反序变换R组成；解密变换与加密变换结构相同，不同的仅是轮密钥的使用顺序。

适合软、硬件实现；适合32位处理器实现

可以抵抗差分分析、线性分析、代数攻击等密码分析方法

安全性与AES-128相当（AES轮数少且轮数可以选择，SM4实现更简单）

算法细节如下：

设明文输入为$(X_0,X_1,X_2,X_3)$，密文输出为$(Y_0,Y_1,Y_2,Y_3)$。

加密时，对i = 0,1,2,…,31执行：$X_{i+4}=F(X_i,X_{i+1},X_{i+2},X_{i+3},r{K}_i)=X_i\oplus T(X_{i+1}\oplus X_{i+2}\oplus X_{i+3}\oplus r{K}_i)$

密文：（其中R为反序变换函数）$(Y_0,Y_1,Y_2,Y_3)=R(X_{32},X_{33},X_{34},X_{35})=(X_{35},X_{34},X_{33},X_{32})$

密钥扩展算法迭代32轮，每轮产生一个轮密钥。

首先进行加密密钥初始化：$MK=(M{K}_0,M{K}_1,M{K}_2,M{K}_3);(K_0,K_1,K_2,K_3)=(M{K}_0\oplus F{K}_0,M{K}_1\oplus F{K}_1,M{K}_2\oplus F{K}_2,M{K}_3\oplus F{K}_3)$

其中$FK=(F{K}_0,F{K}_1,F{K}_2,F{K}_3)$是规定的128比特常数。

然后对$i=0,1,2,\dots ,31$执行$r{k}_i=K_{i+4}=K_i\oplus T^{\prime }(K_{i+1}\oplus K_{i+2}\oplus K_{i+3}\oplus C{K}_i)$

得到轮密钥$rk$，其中$C{K}_i$是32个32比特的固定常数。

分组密码工作模式

工作模式：

ECB模式：

应用：单个数据的安全传输

优点：简单、孤立，每个块单独运算。适合并行运算。传输错误一般只影响当前块。

缺点：同明文输出同密文，可能导致明文攻击。我们平时用的AES加密很多都是ECB模式的，此模式加密不需要向量IV。

CBC模式：

应用：对大量数据的加密和认证；

优点：每个密文分组均依据于之前的全部分组；对任意一个分组的改动都会影响后继的所有密文分组；需要初始向量（IV必须随机选择）

缺点：如果攻击者获得了IV，可以通过预先改变IV中的某些位，使得接收者的明文中部分位被取反，解决方法：在发送消息前用ECB来保护IV

CFB模式：

用途：流密码加密，认证

优点：适合数据流的加密，可以被视为流密码，但与流密码的典型构造不一致（不能依据初始值和密钥输出密钥流）；在已知全部密文时，解密过程可以并行

缺点：每得到s个输入比特，需要暂停进行分组加密；存在误差扩散：密文传输中某位发生错误，会影响后继的解密

OFB模式：

用途：有信道噪声环境下的流密码

优点：传输过程中，比特差错不会扩散；可以预计算分组，流加密时不需停顿

缺点：对抗消息流篡改攻击的能力弱于CFB：若对密文取反，则解密后的明文也取反；可以看作是一次一密的变形（Vernam密码）（所以绝对不能重复使用相同的密钥序列和IV）；发送方和接收方必须同步

CTR模式：

用途：高速网络加密

优点：高效；可以并行处理多块明文密文；可以预计算；随机访问：密文的第i个分组可以随机访问，不需知道前面i-1个密文组（比较：CBC）；可证安全：是CPA安全的

前提：使用了真正的随机数生成器，且每个计数器值绝不重用

缺点：密钥、计数器值绝不能重用

各工作模式的反馈特征：

要点

区分：代换、置换、扩散、混淆；分组密码与流密码
记忆：DES、AES、SM4的分组长度、密钥长度、加密轮数（以及每轮的主要步骤和功能）
常用分组模式以及其错误传输
雪崩效应与可逆变换
差分分析与中间相遇分析

相关题目

（答案仅供参考）

相关题库

（答案仅供参考）