分组密码的工作模式

2019-11-09 15:03:05

字体：大中小

来源：转载

供稿：网友

一、理论基础1.概述密码学中，块密码的工作模式允许使用同一个块密码密钥对多于一块的数据进行加密，并保证其安全性。块密码自身只能加密长度等于密码块长度的单块数据，若要加密变长数据，则数据必须先被划分为一些单独的密码块。通常而言，最后一块数据也需要使用合适填充方式将数据扩展到符合密码块大小的长度。一种工作模式描述了加密每一数据块的过程，并常常使用基于一个通常称为初始化向量的附加输入值以进行随机化，以保证安全。工作模式主要用来进行加密和认证。对加密模式的研究曾经包含数据的完整性保护，即在某些数据被修改后的情况下密码的误差传播特性。后来的研究则将完整性保护作为另一个完全不同的，与加密无关的密码学目标。部分现代的工作模式用有效的方法将加密和认证结合起来，称为认证加密模式。虽然工作模式通常应用于对称加密，它亦可以应用于公钥加密，例如在原理上对RSA进行处理，但在实用中，公钥密码学通常不用于加密较长的信息，而是使用混合加密方案。2.历史和标准化最早出现的工作模式，ECB，CBC，OFB和CFB可以追溯到1981年。2001年，NIST修订了其早先发布的工作模式工作列表，加入了AES，并加入了CTR模式。最后，在2010年1月，NIST加入了XTS-AES，而其余的可信模式并没有为NIST所认证。例如CTS是一种密文窃取的模式，许多常见的密码学运行库提供了这种模式。ECB，CBC，OFB，CFB，CTR和XTS模式仅仅提供了机密性；为了保证加密信息没有被意外修改或恶意篡改，需要采用分离的消息验证码，例如CBC-MAC。密码学社群认识到了对专用的保证完整性的方法的需求，NIST因此提出了HMAC，CMAC和GMAC。HMAC在2002年通过了认证，CMAC在2005年通过，GMAC则在2007年被标准化。在发现将认证模式与加密模式联合起来的难度之后，密码学社区开始研究结合了加密和认证的单一模式，这种模式被称为认证加密模式（AE，Authenticated Encryption），或称为authenc。AE模式的例子包括CCM，GCM，CWC，EAX，IAPM和OCB。现在，工作模式为许多国家和国内的标准认证实体所定义，其中最有影响力的来源是美国的NIST，而其它有影响力的组织包括ISO，IEC，IEEE，美国的ANSI，以及IETF。3.初始化向量（IV）初始化向量（IV，Initialization Vector）是许多工作模式中用于随机化加密的一块数据，因此可以由相同的明文，相同的密钥产生不同的密文，而无需重新产生密钥，避免了通常相当复杂的这一过程。初始化向量与密钥相比有不同的安全性需求，因此IV通常无须保密，然而在大多数情况中，不应当在使用同一密钥的情况下两次使用同一个IV。对于CBC和CFB，重用IV会导致泄露平文首个块的某些信息，亦包括两个不同消息中相同的前缀。对于OFB和CTR而言，重用IV会导致完全失去安全性。另外，在CBC模式中，IV在加密时必须是无法预测的；特别的，在许多实现中使用的产生IV的方法，例如SSL2.0使用的，即采用上一个消息的最后一块密文作为下一个消息的IV，是不安全的。4.填充 (密码学)块密码只能对确定长度的数据块进行处理，而消息的长度通常是可变的。因此部分模式（即ECB和CBC）需要最后一块在加密前进行填充。有数种填充方法，其中最简单的一种是在平文的最后填充空字符以使其长度为块长度的整数倍，但必须保证可以恢复平文的原始长度；例如，若平文是C语言风格的字符串，则只有串尾会有空字符。稍微复杂一点的方法则是原始的DES使用的方法，即在数据后添加一个1位，再添加足够的0位直到满足块长度的要求；若消息长度刚好符合块长度，则添加一个填充块。最复杂的则是针对CBC的方法，例如密文窃取，残块终结等，不会产生额外的密文，但会增加一些复杂度。布鲁斯·施奈尔和尼尔斯·弗格森提出了两种简单的可能性：添加一个值为128的字节（十六进制的80），再以0字节填满最后一个块；或向最后一个块填充n个值均为n的字节。CFB，OFB和CTR模式不需要对长度不为密码块大小整数倍的消息进行特别的处理。因为这些模式是通过对块密码的输出与平文进行异或工作的。最后一个平文块（可能是不完整的）与密钥流块的前几个字节异或后，产生了与该平文块大小相同的密文块。流密码的这个特性使得它们可以应用在需要密文和平文数据长度严格相等的场合，也可以应用在以流形式传输数据而不便于进行填充的场合。二、分组工作模式1.电子密码本（ECB）最简单的加密模式即为电子密码本（Electronic codebook，ECB）模式。需要加密的消息按照块密码的块大小被分为数个块，并对每个块进行独立加密。

Ecb encryption.png

Ecb decryption.png

本方法的缺点在于同样的平文块会被加密成相同的密文块；因此，它不能很好的隐藏数据模式。在某些场合，这种方法不能提供严格的数据保密性，因此并不推荐用于密码协议中。下面的例子显示了ECB在密文中显示平文的模式的程度：该图像的一个位图版本（左图）通过ECB模式可能会被加密成中图，而非ECB模式通常会将其加密成右图。

原图使用ECB模式加密提供了伪随机性的非ECB模式右图是使用CBC，CTR或任何其它的更安全的模式加密左图可能产生的结果—与随机噪声无异。注意右图看起来的随机性并不能表示图像已经被安全的加密；许多不安全的加密法也可能产生这种“随机的”输出。ECB模式也会导致使用它的协议不能提供数据完整性保护，易受到重放攻击的影响，因此每个块是以完全相同的方式解密的。例如，“梦幻之星在线：蓝色脉冲”在线电子游戏使用ECB模式的Blowfish密码。在密钥交换系统被破解而产生更简单的破解方式前，作弊者重复通过发送加密的“杀死怪物”消息包以非法的快速增加经验值。2.密码块链接（CBC）1976年，IBM发明了密码分组链接（CBC，Cipher-block chaining）模式。在CBC模式中，每个平文块先与前一个密文块进行异或后，再进行加密。在这种方法中，每个密文块都依赖于它前面的所有平文块。同时，为了保证每条消息的唯一性，在第一个块中需要使用初始化向量。

Cbc encryption.png

Cbc decryption.png

若第一个块的下标为1，则CBC模式的加密过程为 $C_i = E_K(P_i /oplus C_{i-1}), C_0 = IV$

而其解密过程则为

$P_i = D_K(C_i) /oplus C_{i-1}, C_0 = IV$ CBC是最为常用的工作模式。它的主要缺点在于加密过程是串行的，无法被并行化，而且消息必须被填充到块大小的整数倍。解决后一个问题的一种方法是利用密文窃取。注意在加密时，平文中的微小改变会导致其后的全部密文块发生改变，而在解密时，从两个邻接的密文块中即可得到一个平文块。因此，解密过程可以被并行化，而解密时，密文中一位的改变只会导致其对应的平文块和下一个平文块中对应位发生改变，不会影响到其它平文的内容。3.填充密码块链接（PCBC）填充密码块链接（PCBC，PRopagating cipher-block chaining）或称为平文密码块链接（Plaintext cipher-block chaining），是一种可以使密文中的微小更改在解密时导致平文大部分错误的模式，并在加密的时候也具有同样的特性。

Pcbc encryption.png

Pcbc decryption.png

加密和解密算法如下： $C_i = E_K(P_i /oplus P_{i-1} /oplus C_{i-1}), P_0 /oplus C_0 = IV$ $P_i = D_K(C_i) /oplus P_{i-1} /oplus C_{i-1}, P_0 /oplus C_0 = IV$ PCBC主要用于Kerberos v4和WASTE中，而在其它场合的应用较少。对于使用PCBC加密的消息，互换两个邻接的密文块不会对后续块的解密造成影响。正因为这个特性，Kerberos v5没有使用PCBC。4.密文反馈（CFB）密文反馈（CFB，Cipher feedback）模式类似于CBC，可以将块密码变为自同步的流密码；工作过程亦非常相似，CFB的解密过程几乎就是颠倒的CBC的加密过程： $C_i = E_K (C_{i-1}) /oplus P_i$ $P_i = E_K (C_{i-1}) /oplus C_i$ $C_{0} = / /mbox{IV}$

Cfb encryption.png

Cfb decryption.png

上述公式是描述的是最简单的CFB，在这种模式下，它的自同步特性仅仅与CBC相同，即若密文的一整块发生错误，CBC和CFB都仍能解密大部分数据，而仅有一位数据错误。若需要在仅有了一位或一字节错误的情况下也让模式具有自同步性，必须每次只加密一位或一字节。可以将移位寄存器作为块密码的输入，以利用CFB的自同步性。为了利用CFB制作一种自同步的，可以处理任意位情况错误的流密码，需要使用一个与块的大小相同的移位寄存器，并用IV将寄存器初始化。然后，将寄存器内容使用块密码加密，然后将结果的最高x位与平文的x进行异或，以产生密文的x位。下一步将生成的x位密文移入寄存器中，并对下面的x位平文重复这一过程。解密过程与加密过程相似，以IV开始，对寄存器加密，将结果的高x与密文异或，产生x位平文，再将密文的下面x位移入寄存器。下式中Si是移位寄存器的第i个状态，a << x是指将a移位x位，head(a, x)是指a的高x位，n则是指IV的位数。 $C_i = /mbox{head}(E_K (S_{i-1}), x) /oplus P_i$ $P_i = /mbox{head}(E_K (S_{i-1}), x) /oplus C_i$ $S_i = / ((S_{i-1} << x) + C_i) /mbox{ mod } 2^n$ $S_{0} = / /mbox{IV}$ 若密文的x位发生错误，则密码在移位寄存器恢复与加密时的状态相同之前，输出不正确的结果，而当寄存器状态恢复后，密码即可以重新同步，恢复正常输出，因此最多只有一块数据发生错误。与CBC相似，平文的改变会影响接下来所有的密文，因此加密过程不能并行化；而同样的，与CBC类似，解密过程是可以并行化的。在解密时，密文中一位数据的改变仅会影响两个平稳块：对应平文块中的一位数据与下一块中全部的数据，而之后的数据将恢复正常。CFB拥有一些CBC所不具备的特性，这些特性与OFB和CTR的流模式相似：只需要使用块密码进行加密操作，且消息无需进行填充（虽然密文窃取也允许数据不进行填充）。5.输出反馈（OFB）输出反馈模式（Output feedback, OFB）可以将块密码变成同步的流密码。它产生密钥流的块，然后将其与平文块进行异或，得到密文。与其它流密码一样，密文中一个位的翻转会使平文中同样位置的位也产生翻转。这种特性使得许多错误校正码，例如奇偶校验位，即使在加密前计算而在加密后进行校验也可以得出正确结果。由于XOR操作的对称性，加密和解密操作是完全相同的： C_i = P_i /oplus O_i

$O_i = / E_K (O_{i-1})$ $O_{0} = / /mbox{IV}$

Ofb encryption.png

Ofb decryption.png

每个使用OFB的输出块与其前面所有的输出块相关，因此不能并行化处理。然而，由于平文和密文只在最终的异或过程中使用，因此可以事先对IV进行加密，最后并行的将平文或密文进行并行的异或处理。可以利用输入全0的CBC模式产生OFB模式的密钥流。这种方法十分实用，因为可以利用快速的CBC硬件实现来加速OFB模式的加密过程。6.计数器模式（CTR）注意：CTR模式（Counter mode，CM）也被称为ICM模式（Integer Counter Mode，整数计数模式）和SIC模式（Segmented Integer Counter）。与OFB相似，CTR将块密码变为流密码。它通过递增一个加密计数器以产生连续的密钥流，其中，计数器可以是任意保证不产生长时间重复输出的函数，但使用一个普通的计数器是最简单和最常见的做法。使用简单的、定义好的输入函数是有争议的：批评者认为它“有意的将密码系统暴露在已知的、系统的输入会造成不必要的风险”。目前，CTR已经被广泛的使用了，由输入函数造成的问题被认为是使用的块密码的缺陷，而非CTR模式本身的弱点。无论如何，有一些特别的攻击方法，例如基于使用简单计数器作为输入的硬件差错攻击。CTR模式的特征类似于OFB，但它允许在解密时进行随机存取。由于加密和解密过程均可以进行并行处理，CTR适合运用于多处理器的硬件上。注意图中的“nonce（随机数）”与其它图中的IV（初始化向量）相同。IV、随机数和计数器均可以通过连接，相加或异或使得相同平文产生不同的密文。

Ctr encryption.png

Ctr decryption.png

三、扩展内容1.误差传播在消息验证码和认证加密的广泛应用之前，常常有人讨论块密码工作模式的“误差传播”特性，作为工作模式性能的一部分。例如，若密文传输中一个数据块的错误会导致采用ECB模式生成的平文中同样一个块的错误，而CBC模式中会导致两个平文块出错。有人认为这样的特性在应对随机误差（例如传输噪声）时会是有益的，而还有人认为这样的特性使得攻击者更容易篡改消息的一部分。无论如何，若使用了适当的完整性保护措施，这样的误差很可能会导致整个消息重发。若需要应对随机误差，则应当在发送密文之前增加错误校正码。2.认证加密一些工作模式在设计中希望将保密性和认证性结合起来，例如XCBC，ACBC，APM，OCB，EAX，CWC，CCM和GCM。认证加密模式被可以分为单次处理和两次处理两种类型。然而，对密码学用户社群而言，不幸的是，许多单次处理的认证加密算法，例如OCB，是为专利所保护的。另外，有的模式也允许为未加密的关联数据进行认证，因此被称为AEAD（Authenticated-Encryption with Associated-Data，用于关联数据的认证加密）。例如，EAX是一种两次处理的AEAD方法，而OCB模式是单次的。3.其它模式和密码学概念除了上文中提到的模式以外，还有很多其它的块密码工作模式。有的被公众所接受，有其详细描述了，甚至被标准化了，并在使用中；而有的则被认为是不安全的，而从未使用过；另外一些则并没有被分类为保密，认证或签名加密，例如密钥反馈模式（KFM，Key Feedback Mode）和AES-hash。NIST维护着一张块密码工作模式列表。磁盘加密通常使用特殊目的、专门设计的模式。可以调节的小数据块加密模式（LRW，XEX和XTS）和大数据块的模式（CMC和EME）是设计用于加密磁盘区块的。块密码也可以用于其它加密协议中，在这些协议中，块密码的使用方式与前述工作模式相似。在一切协议中，为了保证其安全性，必须在构建工作模式时特别注意。有数种方法可以用块密码构建密码散列函数，参见单向压缩函数。消息认证码（MAC）通常由块密码得到，例如CBC-MAC，OMAC和PMAC。认证加密也采用块密码作为其中的一部，其同时使用加密和MAC以提供保密性和数据完整性，例如IAPM，CCM，CWC，EAX，GCM和OCB。转自：http://blog.163.com/kevinlee_2010/blog/static/16982082020113853451308/

上一篇：PBOC3.0中使用的国密SM2算法

下一篇：算法（一）时间复杂度