1.9 Khufu和Khafre快速软件加密算法

Khufu和Khafre快速软件加密算法是由R. C. Merkle在1990年美洲密码年会上提出的，类似于DES的多层迭代分组密码，迭代层数规定为8的整数倍，输入和输出分组均为64比特，加密速度在SUN 4/260上可达4～8 Mb/s。因为是软件加密算法，所以与硬件加密算法相比有更大的灵活性，其加密层数和密钥长度均没有具体规定，可根据被加密数据的价值，以及对安全性和加密速度的要求来确定。迭代层数可以是8～64之间的任意8的整数倍，一般用16层、24层或32层。密钥长度一般为64比特的整数倍。

Khufu和Khafre设计的基本思想是：面向软件、快速实现。当时R.C. Merkle认为还没有一种被大家普遍接受的软件加密算法，大部分商业加密软件都用软件仿效硬件实现DES加密算法。由于DES加密算法是面向硬件设计的，每层要并行进行8次查表（S盒代替），然后进行一次置换。而对于软件来说，8次查表也只能逐个进行，所以速度慢。R. C. Merkle估计，用软件实现DES加密算法的速度为安全性相当的、面向软件加密算法的1/10～1/5。

Khufu加密算法和Khafre加密算法基本相同，略有差别。在加密时，前者的S盒由密钥决定，后者的S盒固定不变；在使用时，前者用于大量成批数据的加密，后者用于少量数据的加密。

我们先介绍Khufu加密算法。把数据（明文）分为左、右两半，各32比特，分别记为L和R，加密的第一步是把明文与64比特的辅助密钥（Auxiliary Key, AK）进行模2加，然后进行n层变换，最后与另外64比特的辅助密钥进行模2加，最后得到输出密文。每层变换由一次查表和一次循环移位组成，把L最右边一个字节作为S盒的输入，输出32比特并与R进行模2加，然后L循环右移1个或多个字节，再变换左、右两部分，从而实现一层变换。Khufu加密算法如图1.9.1所示。

S盒是一个由256个32比特组成的RAM表，若把它看成4个长度为256字节的序列，则每列是0～255的一个排列。S盒的输入是1字节，把它作为地址码，从RAM表中取出相应的32比特作为输出。每经过8层变换，S盒就要更换一次，所以S盒的个数是由层数决定的。左部分1～8层的循环右移的字节数分别为2、2、1、1、2、2、3、3，经过8层循环右移后，数据回到原来位置，然后进行9～16层、17～24层…，不断重复上述循环右移的字节数。经过8层变化后，每个字节恰好作为一次S盒的输入。

R. C. Merkle在1990年美洲密码年会上发表的文章中对Khufu加密算法的密钥量没做规定，只是谈到从初始密钥算出128比特的辅助密钥和每8层变化一次的S盒，并没有介绍怎样从初始密钥计算辅助密钥。各层的S盒是从一个初始S盒出发，在初始密钥参与的情况下，按一定的算法生成的。初始S盒也是一个256×32比特的RAM表，每个字节列都是0～255的一个排列，生成S盒的过程可分为两步。

图1.9.1 Khufu加密算法

（1）生成一个足够长的伪随机字节序列。先从初始密钥得到64字节的初始值，采用Khufu加密算法，以分组连接的方式对这64字节进行加密，得到64个伪随机字节，再次加密后又可又得到64个伪随机字节…，直到伪随机字节序列足够长，在下面第（2）步中用它来决定第R[i]个字节的值。

（2）由伪随机字节序列来产生初始S盒。从初始S盒的每个字节列的第0个字节开始到第255个字节，对每个字节进行一次对换，第i个字节与该列的第R[i]个字节对换，其中R[i]是由第（1）步生成的相应伪随机字节决定的。经过这样变化后的S盒仍然保持每列是0～255的一个排列，用上述方法可以生成足够多的S盒。

Khufu加密算法的每层变化使用了一个较大的非线性S盒，S盒的输出与右半部分R进行模2加，经多层非线性变化后，达到了混乱的目的。又因为每层进行一次字节移位，经8层变化后，明文输入的每个字节都恰好用来查一次表，使变化后的每个密文的比特依赖于整个明文输入和密钥，达到了扩散的目的。

DES加密算法每层要查8个S盒，进行一次64比特的置换。Khufu加密算法针对软件实现的特点，把S盒的规模扩大，每层只查一次，并用循环移位来代替置换，这样同样达到了混乱和扩散的目的，但速度比DES加密算法快得多。

Khafre加密算法与Khufu加密算法类似，不同的是Khafre加密算法用一组固定的S盒，称其为标准S盒。在加密少量数据或只加密一个64比特分组时，由于不必计算S盒，所以速度快。另外，因为Khafre加密算法的S盒与密钥无关，所以除了在算法的开头和结束数据要和64比特的密钥进行模2加，每经过8层变换，都要用64比特的密钥与数据进行一次模2加。此外，由于S盒是固定的，因此Khafre加密算法要用更多层的变化才能得到与Khufu加密算法相同的安全性。