分组密码算法（块密码算法）

发布时间：2016-3-23 15:56
分类名称：PKI

下文，为汇总网络上各个博客文章。

这是一个加密算法的大致分类图：

对称加密又分为分组加密和序列密码。

• 分组密码，也叫块加密(block cyphers)，一次加密明文中的一个块。是将明文按一定的位长分组，明文组经过加密运算得到密文组，密文组经过解密运算（加密运算的逆运算），还原成明文组。
• 序列密码，也叫流加密(stream cyphers)，一次加密明文中的一个位。是指利用少量的密钥（制乱元素）通过某种复杂的运算（密码算法）产生大量的伪随机位流，用于对明文位流的加密。
• 解密是指用同样的密钥和密码算法及与加密相同的伪随机位流，用以还原明文位流。

本文介绍的是分组密码算法。

定义

分组密码算法是提供数据安全的基本构件。它以固定的分组长度作为基本的处理单元，但要加密的消息的长度可能要长得多。

为了将分组密码算法应用于实际，人们定义了很多工作模式。

例如：DES只解决了如何对一个64比特的明文分组进行加密保护的问题，对于比特殊不等于64比特的明文如何加密，并不关心。这个问题，就由分组密码的工作模式来解决。 

分组密码的工作模式是：根据不同的数据格式和安全性要求, 以一个具体的分组密码算法为基础构造一个分组密码系统的方法。分组密码的工作模式应当力求简单, 有效和易于实现。

详细模式介绍

在分组加密算法中，有ECB,CBC,CFB,OFB这几种算法模式。

电子本模式（ECB）electronic codebook mode

电码本模式（ECB）electronic codebook mode是最简单的模式，它直接利用加密算法分别对每个64位明文分组使用相同的64位密钥进行加密。

对于长于64位的报文，整个加密前需要把这个报文分成64位的分组，如果有必要的话对最后一个组做填充。

定义:

Enc(X,Y)是加密函数

Dec(X,Y)是解密函数

Key是加密密钥；

Pi ( i = 0,1…n)是明文块，大小为64bit；

Ci ( i = 0,1…n)是密文块，大小为64bit;

ECB加密算法可表示为：

Ci = Enc(Key, Pi)

ECB解密算法可以表示为：

Pi = Dec(Key,Ci)

使用 " 密码本 " 这个术语的原因是对每个64位的明文分组就有一个唯一的密文，因此可以想象一个巨大的密码本，其中对每一个可能的64位明文项就有一个密文项与之对应。

ECB加密

ECB解密

算法 特点:

• 每次Key、明文、密文的长度都必须是64位；
• 数据块重复排序不需要检测；  

  优点:

  1.简单；

  2.有利于并行计算；

  3.误差不会被传送，一个错误仅仅会对一个密文块产生影响；

缺点:

1.不能隐藏明文的模式；repetitions in message may show in cipher text/在密文中出现明文消息的重复；

2.可能对明文进行主动攻击，相同的明文块(使用相同的密钥)产生相同的密文块，容易遭受字典攻击；

在ECB模式下，加密算法的输入是明文，算法的输出将直接作为密文进行输出，不进行任何形式的反馈，每个明文分组的处理是相互独立的，这种方式也是分组密码工作的标准模式。

ECB模式的缺点是：在给定密钥k 下，同一明文组总是产生同一密文组，这会暴露明文组的数据格式。某些明文的数据格式会使得明文组有大量的重复或较长的零串，一些重要的数据常常会在同一位置出现，特别是格式化的报头、作业号、发报时间、地点等特征都将被泄露到密文之中，使攻击者可以利用这些特征。

该模式好的一面就是用同个密钥加密的单独消息，其结果是没有错误传播。实际上，每一个分组可被看作是用同一个密钥加密的单独消息。密文中数据出了错，解密时，会使得相对应的整个明文分组解密错误，但它不会影响其他明文。然而，如果密文中偶尔丢失或添加一些数据位，那么整个密文序列将不能正确的解密。除非有某帧结构能够重新排列分组的边界。

密码分组链接模式（CBC）cipher block chaining mode

如上所述，ECB 工作模式存在一些显见的缺陷。为了克服这些缺陷, 我们应用分组密码链接技术来改变分组密码的工作模式。

CBC 工作模式是在密钥固定不变的情况下，改变每个明文组输入的链接技术。在CBC 模式下，每个明文组mi 在加密之前, 先与反馈至输入端的前一组密文ci?1逐比特异或后再加密。

定义：

Enc(X,Y)是加密函数

Dec(X,Y)是解密函数

Key是加密密钥；

Pi ( i = 0,1…n)是明文块，大小为64bit；

Ci ( i = 0,1…n)是密文块，大小为64bit;

XOR(X,Y)是异或运算；

IV是初始向量（一般为64位）；

ECB加密算法可表示为：

C0 = Enc(Key, XOR(IV, P0)

Ci = Enc(Key, XOR(Ci-1, Pi)

ECB解密算法可以表示为：

Pi = XOR(Ci-1, Dec(Key,Ci))

P0 = XOR(IV, Dec(Key, C0))

CBC加密

这样, 密文组ci 不仅与当前的明文组有关,而且通过反馈的作用还与以前的明文组m1, m2,...mi.1 有关。这从密码学的本质上来说是一种混淆操作。

CBC解密

算法特点:

• 每次加密的密文长度为64位(8个字节);
• 当相同的明文使用相同的密钥和初始向量的时候CBC模式总是产生相同的密文;

优点：

1.可以使用不同的初始化向量来避免相同的明文产生相同的密文,一定程度上抵抗字典攻击; 不容易主动攻击,安全性好于ECB,适合传输长度长的报文,是SSL、IPSec的标准。

缺点：

1.密文块要依赖以前的操作结果，所以，密文块不能进行重新排列，无法并行计算； (在解密时，从两个邻接的密文块中即可得到一个平文块。因此，解密过程可以被并行化) 。

2. 需要初始化向量IV

3. 会出现错误传播(errorpropagation). 密文中任一位发生变化会涉及后面一些密文组. 但CBC 模式的错误传播不大, 一个传输错误至多影响两个消息组的接收结果 (思考).

关于错误传播的问题，我的理解是这样的。因为分组密码模式的分组特性导致了这一现象。每个组之间是独立的。所以如果在传输中即使有某一位发生了错误，也仅仅可以理解为某一组发生了错误，对其他组没有影响。

比如A组发生了位错乱，它最多影响到当前A这组明文和下一组B明文。而再下一组C就不受影响了，因为C组是根据B的密文作为输入的，但是B分组的位并没有发生错误，所以在CBC模式下错误传播最多持续2个分组

密码反馈模式（CFB）cipher feedback mode

分组密码算法也可以用于同步序列密码，就是所谓的密码反馈（Cipher-FeedBack, CFB）模式。在CBC 模式下，整个数据分组在接收完之后才能进行加密。对许多网络应用来说，这是个问题。例如，在一个安全的网络环境中，当从某个终端输入时，它必须把每一个字符马上传输给主机。当数据在字节大小的分组里进行处理时，CBC 模式就不能做到了。若待加密的消息必须按字符比特处理时，可采用CFB 模式。

加密反馈模式克服了需要等待8个字节才能加密的缺点，它采用了分组密码作为流密码的密钥流生成器；

定义：

Enc(X,Y)是加密函数

Dec(X,Y)是解密函数

Key是加密密钥；

Pi ( i = 0,1…n)是明文块，大小为64bit；

Ci ( i = 0,1…n)是密文块，大小为64bit;

Si ( i = 0,1…n)，大小为8bit，n个连续的Si组成加密位移寄存器，一般n=8;

Oi = Enc(Key, Si);

Lef(x) 为取数据x的最左8个bit位；

A(x,y)为合并x左移8位，空位用y填充

CFB加密算法可表示为：

S0 = IV；

Oi = Enc(Key, Si);

Ci = XOR( Ci, Lef(Oi));

Si = A(Si-1, Ci);

CFB解密算法可表示为：

S0 = IV；

Oi = Enc(Key, Si);

Ci = XOR( Ci, Lef(Oi));

Si = A(Si-1, Ci);

在CFB 模式下，每次加密s bit 明文。（1<= s<= 原来的固有长度）：

s = 8, L = 64/s

密文反馈（CFB，Cipher feedback）模式类似于CBC，可以将块密码变为自同步的流密码；工作过程亦非常相似，CFB的解密过程几乎就是颠倒的CBC的加密过程：

需要使用一个与块的大小相同的移位寄存器，并用IV将寄存器初始化。然后，将寄存器内容使用块密码加密，然后将结果的最高x位与明文的x进行异或，以产生密文的x位。下一步将生成的x位密文移入寄存器中，并对下面的x位平文重复这一过程。解密过程与加密过程相似，以IV开始，对寄存器加密，将结果的高x与密文异或，产生x位平文，再将密文的下面x位移入寄存器。

这个流程描述有些不清楚，下面贴了一段AES CFB8加解密的流程：

int mbedtls_aes_crypt_cfb8( mbedtls_aes_context *ctx,

int mode,

size_t length,

unsigned char iv[16],

const unsigned char *input,

unsigned char *output )

{

unsigned char c;

unsigned char ov[17];

while( length-- )

{

memcpy( ov, iv, 16 );

mbedtls_aes_crypt_ecb( ctx, MBEDTLS_AES_ENCRYPT, iv, iv );

ov[16] = *input;

c = *output++ = (unsigned char)( iv[0] ^ *input++ );

ov[16] = c;

memcpy( iv, ov + 1, 16 );

}

return( 0 );

}

特点:

• 每次加密的Pi和Ci不大于64位;
• 加密算法和解密算法相同，不能适用于公钥算法；
• 使用相同的密钥和初始向量的时候，相同明文使用CFB模式加密输出相同的密文;
• 可以使用不同的初始化变量使相同的明文产生不同的密文，防止字典攻击;
• 加密强度依赖于密钥长度;
• 加密块长度过小时,会增加循环的数量,导致开销增加;
• 加密块长度应时8位的整数倍(即字节为单位);
• 一旦某位数据出错,会影响目前和其后8个块的数据;

优点：

1.隐藏了明文模式;

2.分组密码转化为流模式;

3.可以及时加密传送小于分组的数据;

缺点:

1.不利于并行计算; 与CBC类似，解密过程是可以并行化的

2.误差传送：一个明文单元损坏影响多个单元;

3.唯一的IV;

输出反馈模式（OFB）output feedback mode

在CFB模式中，1位密文的传输错误会影响至少b+1位的明文，这种错误传播的影响对于有些应用来讲还是太大了。与CFB模式不同之处在于, 加密位移寄存器与密文无关了,仅与加密key和加密算法有关。做法是不再把密文输入到加密移位寄存器，而是把输出的分组密文（Oi）输入到一位寄存器；

从而克服了CBC和CFB模式带来的错误传播问题

定义：

Enc(X,Y)是加密函数

Dec(X,Y)是解密函数

Key是加密密钥；

Pi ( i = 0,1…n)是明文块，大小为64bit；

Ci ( i = 0,1…n)是密文块，大小为64bit;

Si ( i = 0,1…n)，大小为8bit，n个连续的Si组成加密位移寄存器，一般n=8;

Oi = Enc(Key, Si);

Lef(x) 为取数据x的最左8个bit位；

A(x,y)为合并x左移8位，空位用y填充

CFB加密算法可表示为：

S0 = IV；

Oi = Enc(Key, Si);

Ci = XOR( Ci, Lef(Oi));

Si = A(Si-1, Oi); 注意这里与CFB模式的不同

CFB解密算法可表示为：

S0 = IV；

Oi = Enc(Key, Si);

Ci = XOR( Ci, Lef(Oi));

Si = A(Si-1, Oi);

OFB模式实质上就是一个同步流密码，通过反复加密一个初始向量IV来得到密钥流。这种方法有时也叫"内部反馈"，因为反馈机制独立于明文和密文而存在的。

OFB 模式克服了CBC 模式和CFB 模式的错误传播带来的问题, 但同时也带来了序列密码具有的缺点,对密文被篡改难于进行检测。

（关于难于检测错误的问题我的理解是：防止错误传播和错误检测本来就是矛盾的，因为之所以能检测到错误，就是因为发生了错误传播，然后通过hash机制检测出错误。但是OFB能防止错误传播，即无法检测到错误传播，也就自然无法检测密文篡改等错误了）

由于 OFB 模式多在同步信道中运行, 对手难于知道消息的起始点而使这类主动攻击不易奏效。

OFB 模式不具有自同步能力, 要求系统保持严格的同步, 否则难于解密。OFB 模式的初始向量IV 无需保密, 但各条消息必须选用不同的IV。

每个使用OFB的输出块与其前面所有的输出块相关，因此不能并行化处理。然而，由于明文和密文只在最终的异或过程中使用，因此可以事先对IV进行加密，最后并行的将平文或密文进行并行的异或处理。
可以利用输入全0的CBC模式产生OFB模式的密钥流。这种方法十分实用，因为可以利用快速的CBC硬件实现来加速OFB模式的加密过程。

 特点:

• 与CFB类似,以下都是不同之处;
• 因为密文没有参与链操作，所以使得OFB模式更容易受到攻击；
• 不会进行错误传播，某位密文发生错误，只会影响该位对应的明文，而不会影响别的位；
• 不是自同步的，如果加密和解密两个操作失去同步，那么系统需要重新初始化；
• 每次重新同步时，应使用不同的初始向量。可以避免产生相同的比特流，避免"已知明文"攻击 ；

 优点:

1.隐藏了明文模式;

2.分组密码转化为流模式;

3.可以及时加密传送小于分组的数据;

缺点:

1.不利于并行计算;

2.对明文的主动攻击是可能的;

3.误差传送：一个明文单元损坏影响多个单元;

计数器模式（CTR）counter mode

CBC模式和和CFB模式都存在这样一个问题：不能以随机顺序来访问加密的数据，因为当前密文数据块的解密依赖于前面的密文块。而这个问题对于很多应用来说，特别是数据库的应用，是很难接收的。为此，又出现了另一种操作模式，即CRT模式。

与OFB相似，CTR将块密码变为流密码。它通过递增一个加密计数器以产生连续的密钥流，其中，计数器可以是任意保证不产生长时间重复输出的函数，但使用一个普通的计数器是最简单和最常见的做法。

CTR本质上和OFB很类似，只不过差别在与OFB中的密钥流是逐级反馈的。但是在CTR中，密钥流的产生之间是没有关联的，而是由计数器CTR来提供。

注意图中的"nonce（随机数）"与其它图中的IV（初始化向量）相同。IV、随机数和计数器均可以通过连接，相加或异或使得相同平文产生不同的密文。

CTR模式的特征类似于OFB，但它允许在解密时进行随机存取。由于加密和解密过程均可以进行并行处理，CTR适合运用于多处理器的硬件上。

CTR模式的主要有点如下：

1）随机访问性。可以随机地对任意一个密文分组进行解密，对该密文分组的处理与其他密文无关。

2）高效率

3）CTR可以处理任意长度的数据，只要相应调整CTR产生的密钥长度即可。而且加解密过程是对称的XOR。 

3. 不同模式的特点和用途

ECB 模式适用于对字符加密, 例如, 密钥加密。

OFB 模式常用于卫星通信中的加密。

由于对 CBC 和CFB 模式当改变一个明文分组xi则yi 与其后所有密文分组都会受到影响, 这一性质说明这两种模式都可用于认证系统。更明确的说, 这些模

式能被用来产生一个消息认证码, 即MAC。它能使消息接收方相信给定的明文序列的确来自合法发送者,而没有被篡改。这再次说明技术的两面性。

4. 其它模式和密码学概念

除了上文中提到的模式以外，还有很多其它的块密码工作模式。有的被公众所接受，有其详细描述了，甚至被标准化了，并在使用中；而有的则被认为是不安全的，而从未使用过；另外一些则并没有被分类为保密，认证或签名加密，例如密钥反馈模式（KFM，Key Feedback Mode）和AES-hash。NIST维护着一张块密码工作模式列表[23][24]。

磁盘加密通常使用特殊目的、专门设计的模式。可以调节的小数据块加密模式（LRW，XEX和XTS）和大数据块的模式（CMC和EME）是设计用于加密磁盘区块的。

块密码也可以用于其它加密协议中，在这些协议中，块密码的使用方式与前述工作模式相似。在一切协议中，为了保证其安全性，必须在构建工作模式时特别注意。

有数种方法可以用块密码构建密码散列函数，参见单向压缩函数。

消息认证码（MAC）通常由块密码得到，例如CBC-MAC，OMAC和PMAC。

认证加密也采用块密码作为其中的一部，其同时使用加密和MAC以提供保密性和数据完整性，例如IAPM，CCM，CWC，EAX，GCM和OCB。

5. 总评：

     （1）ECB模式简单、高速，但最弱，易受重发和替换攻击，一般不采用。

      （2）CBC，CFC，OFB模式的选用取决于实际的特殊需求。

      （3）明文不易丢信号，对明文的格式没有特殊要求的环境可选用CBC模式。需要完整性认证功能时也可选用该模式。

      （4）容易丢信号的环境，或对明文格式有特殊要求的环境，可选用CFB模式。

      （2）不易丢信号，但信号特别容易错，但明文冗余特别多，可选用OFB模式