AES算法中S-box和列混合单元的优化及FPGA技术实现

AES算法中S盒和列混合单元的优化及FPGA技术的实现由于AES算法的安全级别较高，所以被用来替代DES和3-DES，以满足更加严格的数据加密需求。美国国家标准与技术研究院(NIST)于1997年1月提出开发AES(高级加密标准)加密算法，并于同年9月12日推出了AES的早期基础算法。在研究了一系列早期算法后，Rijndael算法被确定为高级加密标准(AES)。AES/EBU接口标准：3358 www.elecfans.com/article/87/107/2009/2009080182448.html同时，市场迫切需要AES的FPGA和ASIC的硬件解决方案，因为它比软件实现更安全、更省电。在一些应用中，如信用卡、手机、PDA等。硬件的复杂性是影响成本和能耗的一个非常重要的因素。因此，无论是加密还是解密，对AES的主要运算部分进行优化是非常必要的。在AES算法中，S盒是唯一的非线性单元，因此在加密和解密中需要分别进行S盒和逆S盒，尤其是在字节替换和逆字节替换中。构建一个1616的S盒，过去通常是通过查找表来实现的，占用了大量的硬件资源。因此，优化S盒是实现高效AES的重要步骤。本文首先通过在S盒和逆S盒中共享一个查找表来简化非线性单元的复杂度。然后，通过选择合适的约化多项式和GF(28)到GF(24)的同构映射来优化S盒的算法，并用组合逻辑电路实现优化后的S盒，显著降低了相同频率下的硬件资源消耗。同时介绍了一种降低列混合单元硬件复杂度的方案，可以明显减小列混合单元的设计面积。1 S盒的优化设计定义了AES标准算法中的两个大表。S盒和逆S盒。S-box用于两种应用：字节替换和密钥扩展。而反向S盒用于反向字节替换。这两个列表是不同的，所以必须设置两个不同的ROM(2568 b)来存储这两个列表。另外，AES设计采用并行结构，需要多个链表，使得硬件过于复杂，需要优化。S盒模块的结构优化如下。1.1盒和反S盒的组合在一个128 b的高速AES设计中，一般需要总共20个S盒模块和16个反S盒模块。其中16个S盒模块用于字节替换，4个S盒用于密钥扩展，16个逆S盒模块用于逆字节替换。在这种情况下，如果使用不同的列表进行字节替换和反向字节替换，将会占用大量的硬件资源。因此，非常需要一种降低硬件复杂度的方法。如AES标准中所述，S盒的运算过程可以表示为：由于乘法_逆是一个相当复杂的方程，所以实现S盒最常用的方法是用查找表从x中得到Y，方程(1)的逆方程如下：由于乘法_逆-1和乘法_逆相同，所以方程(3)可以表示为：最后必须求M-1，即矩阵M的有限域逆矩阵。根据有限域上逆矩阵的运算方法，可以计算出矩阵M的逆矩阵，命名为M’，如公式(5)所示：公式(1)和公式(6)中，只使用了一个共用的查找表，从而将S盒和逆S盒集成在一起，大大降低了字节替换和逆字节替换的硬件要求。图1显示了集成的S盒/反S盒模块，可用于AES的加密和解密。1.2盒单元中乘法求逆电路的优化从1.1节可以看出，S-box的生成电路由三个模块组成：加密仿射电路(实现out=(in c)M-1方程函数)、解密仿射电路(实现out=in m c方程函数)和乘法求逆电路。为了降低组合逻辑的复杂度，有必要对乘法和求逆电路进行优化。下面描述逆变电路的优化过程。S盒硬件实现的主要组件是乘法和求逆。

在有限域GF(28)上，乘法求逆是一个相当复杂的函数。如果直接在域GF(28)上生成S盒盒，组合逻辑的复杂度会很高，这将大大增加电路中逻辑电路的门数。根据有限域的性质，利用域GF(28)与GF[(24)2]的同构变换，将GF(28)的求逆转化为GF[(24)2]的求逆，从而生成S盒单元，可以降低逻辑关系运算的复杂度，优化S盒的面积。有限域GF(28)上乘法求逆电路模块的优化过程如图2所示。优化的乘法求逆过程可以表示为：(1)通过线性变换T将GF(28)的输入X映射到域GF(24)中的元素B和C；(2)在域GF(24)上构造对应的一次多项式，在域GF(24)上定义加、乘、求逆运算。域GF(24)中的元素B，C的逆元素P，Q是通过域GF(24)中的加法、乘法和求逆运算获得的。(3)构造线性变换T-1，将域GF(24)中的元素P和Q映射到域GF(28)中，从而得到域GF(28)中元素X的逆元素y=T-1(p，Q)。根据有限域的知识，复合域GF[(24)2]中的每一个元素都可以表示为一个系数在GF(24)上的一次多项式bx c。设定义了有限域GF[(24)2]的乘法的二次不可约多项式x2 Ax B，可以验证此时GF[(24)2]中任意元素bx c的乘法逆元为：其中：(b2B bcA c2)-1是GF(24)上b2B bcA c2的乘法逆元。各部分的逻辑实现过程可以描述为：(1)有限域GF(28)到复合域GF[(24)2]的映射。线性变换T由GF(28)上的不可约多项式p(x)=x2 Ax B构造，GF(28)的输入X根据公式(8)映射到GF(24)上的元素B，C:其中：B是GF(24)上的常数元素；T是一个88的矩阵，元素为0或1，T矩阵由B的值决定；A取1，B取8；(2)从GF [(24) 2]到GF(28)的逆映射。在线性变换T-1，GF(24)上构造逆P，Q映射到GF(28)上的逆元素Y，如公式(10)所示。乘法和传递步骤(1)中的线性变换T-1和线性变换T满足：TT-1=E.(3)通过域GF(24)上的运算求B，C的逆P，Q。首先，我们构造GF(24)，q(x)=x4 x 1作为原多项式，域GF(24)上的a(x)，d(x)，E (x) GF(24)。其中a(x)=a3x3 a2x2 a1x a0，d(x)=d3x3 d2x2 d1x d0，e (x)=域GF(24)上的加、乘、逆运算加法是按位异或。乘法是多项式乘法，那么用q(x)取模，用公式E (x)=A (x) D (x) Mod Q (x)进行运算；求逆根据公式A A-1=1 mod q (x)，计算GF(24)上元素A的逆A-1；构造GF(24)上的一次多项式bx c，利用GF(24)上的上述加、乘、求逆运算，计算GF(24)上元素B，C的逆P，Q。从公式(7)可以得出，P，Q的计算是S盒中最复杂的逻辑运算，占用了大量的逻辑关系。至于P，q .在这个设计方案中，求逆模块中使用的约化多项式p(x)和原多项式q(x)是不同的，降低了求逆模块的复杂度。根据理论分析，本文使用的p(x)和q(x)不会降低AES算法的安全性。2列混合单元的优化设计在列混合(MixColumn)和逆列混合(InvMixColumn)的运算中，有两个主要的运算是由下面两个公式定义的：公式(15)和(16)的运算和结果列于表1。从步骤1到5的结果中获得outx，然后从outx和w8中获得outy。因此，在执行过程中，操作所使用的硬件资源和获得的结果可以应用于步骤9和步骤10。如图3所示，这种新结构(字节-列混合模块)只需要8个加法器和4个乘法器。与原方案相比，该设计大大降低了硬件复杂度，节省了资源消耗。图3:Xt模块(AES中的乘法器)的计算公式如下：进一步会发现，要建立一个全局逆选择列混合模块，需要将四个字节列混合模块集成在一起，形成一个全新的字列混合模块(Word_MixColum

综合结果在相同频率要求的前提下，对S盒和柱形混合单元进行了优化，减小了设计面积。优化后的算法在ModelSimSE 6.2b下进行仿真，并在Xilinx Spartan 3系列FPGA上进行了全面验证。时钟频率达到166 MHz，占用3个212基本逻辑门(一个基本逻辑门相当于两个输入/输出与门)，比文献[1]的方法节省了52%。由于S-box和InvS-box共用本文的逆变电路，与文献[2]中的优化方法相比，节省了66%的硬件资源。硬件复杂度是门电路的数量。4结论在AES的经典算法中，S盒往往以查找表的形式实现，会占用大量的硬件资源。本文利用S盒和逆S盒的组合以及GF(28)到GF(24)的同构变换来优化S盒。同时，对AES中复杂的柱混合模块进行了整合和优化。优化后的方案在不降低密码算法安全性的前提下，降低了硬件复杂度，非常适合信用卡等对硬件规模有严格要求的应用。