刘松 夏树村

该文提出一种有效的基于内容可寻址存储器（CAM）的S/S-1盒查找表的实现方法，可以应用于AES的加密和解密运算，与基于RAM的S/S-1盒查找表相比，其复杂性显著降低。同时还提出一种关键路径上只有5个异或门延迟的列/逆列混合复用的硬件结构,大大节省了芯片面积。

AES；内容可寻址存储器；S/S-1盒；列/逆列混合

1.引言

随着AES算法的推广，其应用的范围越来越广泛。一般的硬件实现方案都是采用并行运算的形式，虽然提供了很高的数据吞吐率，但是资源消耗却很大，这就使得AES在便携设备等对硬件开销要求苛刻的领域中的应用受到限制。

为了能够高效、低成本的实现AES算法，本文提出一种新颖的基于内容可寻址存储器（CAM）的S/S-1盒查找表方法，仅使用一个查找表就可以实现AES的加密和解密运算。与基于RAM的S/S-1盒查找表相比，这种存储器的复杂性显著地降低。同时还提出一种低复杂度的硬件结构来实现列/逆列混合变换，使得解密过程能够充分利用加密的硬件资源，进一步有效地减少了芯片面积。

本文组织结构如下：第2节简要介绍AES算法；第3节重点介绍基于CAM的S/S-1盒查找表的体系结构，并与单独实现S盒与S-1盒查找表的方法进行比较；第4节详细介绍列/逆列混合的优化设计；第5节总结全文。

2.AES算法

AES是一种对称分组密码算法，其分组长度和密钥长度均可变，支持任意组合的128bit、192bit和256bit的分组长度和密钥长度。根据不同的密钥长度，AES的圈数分别为10、12和14。数据分组被分割成字节阵列，每一次运算都是面向字节的运算。基本的轮运算包括：字节代替/逆字节代替、行移位/逆行移位、列混合/逆列混合和圈密钥加。

无论进行加密或解密运算，数据分组首先与初始密钥进行异或，然后进行N-1圈迭代轮运算，其中 取决于密钥长度，最后一圈进行除列/逆列混合之外的其它三个变换。

字节代替变换是一个关于字节的非线性变换，将状态中的每一个字节非线性地变换为另一个字节，代替表（S盒）是可逆的，且由两个可逆变换复合而成。首先，将每一个字节变换为有限域中的乘法逆，规定00变换到其自身；其次，将上一步的结果在上做仿射变换。

逆字节代替变换是字节代替变换的逆变换。首先对每一个字节在上做仿射变换的逆变换，然后返回其在有限域中的乘法逆元素。

行移位变换就是加密时将一个状态的第 行循环左移 个字节，解密时循环右移 个字节即为逆行移位变换。

列混合变换对一个状态逐列进行变换，它将一个状态的每一列视为有限域GF(2^8)上的一个多项式且与一个固定多项式相乘。

加密时的列混合变换可表示为：解密时的逆列混合变换为：

圈密钥加就是简单地将一个圈子密钥按位异或到一个状态上。圈子密钥按顺序取自扩展密钥，扩展密钥由初始密钥经过扩展后得到。

3.字节代替的优化设计

内容可寻址存储器（CAM）具有固有的并行性，允许并行地存取和比较存储器中的内容。本节提出一种新颖的基于CAM的查找表来执行S盒与S-1盒的查表操作。通过比较说明这种实现方法比使用两个单独的S盒与S-1盒查找表的复杂性显著降低。

A.内容可寻址存储器（CAM）

内容可寻址存储器（CAM）[2]是一种并行模式的匹配电路，能同时搜索存储器中的所有内容，并返回匹配数值的存储地址。CAM被视为一种并行处理器，用来加速实现图像处理和数据库搜索等应用。

CAM除拥有传统的存储器如RAM的读写功能外，还具有一种特殊的功能，它能够并行地比较其中存储的数据和数据线上的数据，返回满足比较条件的地址。

本文设计了一个8bit的CAM来实现S/S-1盒查找表。图1所示为CAM单元第bit的逻辑电路。在查找内容前，将匹配信号（match）复位为1。图中，连接数据线连接数据线。可知，。如果，则那么匹配信号接地，即=0。否则那么=1。进行写操作时，地址线被激活，通过数据线，数据被写入CAM单元中（数据被存储在和中）。进行读操作时，选取相应的地址线，通过数据线获得存储器中的内容。

B.基于CAM的S/S-1盒查找表

AES加密过程定义了一个S盒查找表，包含8bit的256个置换值。解密过程同样也定义了一个S-1盒。我们提出一种新颖的基于CAM的S/S-1盒查找表的体系结构。

在CAM单元阵列中，用地址线来表示S盒的输入，存储的数据作为其输出值。每行为8bit，共有256行。在配置时将查找表的初始值加载到CAM中。当进行S盒查表操作时，选择相应的地址线，通过数据线读出数值。例如，要找到字节{00}的置换值，地址线00被激活，通过数据线可以读出输出值为{63}。当进行S-1盒查表操作时，将使用CAM的搜索功能。例如，为了找到字节{63}的逆置换值，将63装入比较寄存器，开始并行搜索。CAM将匹配数值63，并返回相应的地址{00}，于是可以使用{00}作为{63}的逆置换值。这样，S盒与S-1盒就可以通过一个查找表来实现，显著降低了查找表的复杂性，大大节省了芯片面积。

图2为本文提出的基于CAM的S/S-1盒查找表的体系结构。在图2中，有一个8bit的比较寄存器，用来存储被比较的数据，通过数据线与CAM相连。我们注意到，被比较的数据被连接到数据线时是取反的，这是由于CAM单元的逻辑结构所致。如果数据与CAM中的相匹配，相应的匹配信号变为1，匹配标记（match flag）被标注。CAM的相应地址线可以通过地址译码器来获得，返回一个8bit的地址值。

与使用两个查找表来实现S盒与S-1盒的方法相比，基于CAM的S/S-1盒查找表的复杂性显著降低。表1比较了基于RAM和CAM实现方式的存储空间的复杂性，可以看出在加解密过程中，使用一个基于CAM的查找表，比RAM方式实现的S/S-1盒查找表减少了25%的硬件资源。

表1不同的查找表实现方式的资源比较

4.列/逆列混合的优化设计

AES中定义了x乘,即用x乘以一个多项式，可以用字节内左移一位和紧接着的一个与“1b”的按位异或来实现，记为。

可将上式统一表示为：

的电路结构如图3所示。

利用，对加密的列混合变换进行化简：

显然，化简后的列混合变换的关键路径仅为3个异或门延迟。

对解密的逆列混合变换来说，我们设计了和两个模块[3]，分别为：

的电路结构分别如图4、5所示，均为2个异或门延迟。

图4结构图图5结构图

由此，逆列混合变换可化简为：

可见，逆列混合的实现可以利用列混合的电路结构，降低了结构的复杂性，而且通过共享部分硬件资源，有效地减少了芯片面积。如此一列状态需要（3+6+9?+8?）?=364个2输入异或门，其关键路径上的延迟为5个异或门，如图6所示。

如上提出的结构只是完成字节的列/逆列混合变换，要实现整个列/逆列混合变换，首先要集成4个字节列/逆混合模块，组成一个新的字列/逆列混合模块，如图7所示。然后再集成4个字列/逆列混合模块，组成一个128bit的分组列/逆列混合模块。图8即为并行分组列/逆列混合模块，其中ed为模式选择信号，ed=1时进行列混合变换，ed=0时进行逆列混合变换。

5.结论

本文提出了一种新颖的基于内容可寻址存储器（CAM）的AES S/S-1盒的实现方法，将S盒与S-1盒的置换结合成一个查找表，可以同时应用于加密和解密运算，与RAM方式实现的S/S-1盒查找表相比，其复杂性显著降低，面积大幅度减少。通过对列/逆列混合变换的化简，在逆列混合变换中复用了列混合变换，使得AES的解密过程能够充分利用加密的硬件资源，进一步地节约了芯片面积，降低了成本。

[1]“Advanced Encryption Standard (AES)”Federal Information Processing Standards Publication 197, Nov. 26, 2001.

[2]Hua Li.”A New CAM Based S/S-1-Box Look-up Table in AES”.Circuits and Systems.ISCAS 2005.IEEE International Symposium on.pp.4634-4636.Vol.05.2005.05

[3]陈俊，王晶，曾晓洋，韩军.低复杂度先进密码算法的VLSI实现[J]计算机工程.2007.33