-
ＡＥＳ算法中Ｓ—ｂｏｘ和列混合单元的优化及ＦＰＧＡ实现
夏克维，李
冰
（东南大学集成电路学院江苏南京２１００９６）
摘要：由于
ＡＥＳ算法的硬件实现较为复杂，在此提出一种优化算法中Ｓ—ｂｏｘ和列混合单元的方法。其中Ｓ—ｂｏｘ通<
/p>
过组合和有限域映射的方法进行优化，列混合单元使用算式重组的方法进行优化。这些优化
设计通过组合逻辑实现，经过
仿真并在Ｘｉｌｉｎｘ
Ｓｐａｒｔ
ａｎ
３系列ＦＰＧＡ上进行综合验证，可以将结构简化，使ＡＥＳ电路面积得到优化，明
显节约硬件资源。
关键词：ＡＥＳ算法；Ｓ—ｂｏｘ；列混合；结构优化；ＦＰＧＡ实现
中图分类号：ＴＮ７１０
文献标识码：Ｂ
文章编号：１００４—３７３Ｘ（２００９）２４—０１１一０４
Ｏｐｔｉｍｉｚａｔ
ｉｏｎ
ｏｆ
Ｓ—ｂｏｘ
ａｎｄ
< br>ＭｉｘＣｏｌｕｍｎ
Ｂｌｏｃｋｓ
ｉｎ
Ａ
ＥＳ
Ｅｎｃｒｙｐｔｉｏｎ
Ａｌｇｏｒｉｔｈｍ
ａｎｄ
ＦＰＧＡ
Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ
ＸＩＡ
Ｋｅｗｅｉ。Ｉ．１
Ｂｉｎｇ
< br>（Ｉｎｓｔｉｔｕｔｅ
ｏｆ
Ｉｎｔｅｇｒａｔｅｄ
Ｃｉｒｃｕｉｔ，Ｓｏｕｔｈｅａｓｔ
Ｕｎｉｖｅｒｓｉｔｙ，Ｎａｍｉｎｇ，２１００
９６．Ｃｈｉｎａ）
ｏｆ
ｉｔ
ｉｓ
ｃｏｍｐｌｅｘ，ａｎ
ｏｐｔｉｍｉ—
Ａｂｓｔｒａｃｔ：ＡＥＳ
ｅｎｃｒｙｐｔｉｏｎ
ａｌｇｏｒｉｔｈｍ
ｉｓ
ａｎ
ａｄｖａｎｃｅｄ
ｅｎｃｒｙｐｔｉｏ
ｎ
ａｌｇｏｒｉｔｈｍ．Ｂｅｃａｕｓｅ
ｔｈｅ
ｓｔｒｕｃｔｕｒｅ
ｚａｔｉｏｎ
ｏｆ
ｔｈｅ
ａｌｇｏｒｉｔｈｍ
ｉｓ
ｐｒｅ
ｓｅｎｔｅｄ．Ｔｈｅ
ｉｍｐｌｅｍｅｎｔａｔｉｏｎ
ｏｆ
Ｓ—ｂｏｘ
ａｎｄ
ＭｉｘＣｏｌｕｍｎ
ｂｌｏ
ｃｋｓ
ｉｎ
ｔｈｅ
ＡＥＳ
ｅｎｃｒｙｐｔ
ｉｏｎ
ｉｓ
ｏｐｔｉｍｉｚｅｄ
ｂｙ<
/p>
ｔｈｅ
ｃｏｍｂｉｎａｔｉｏｎａｌ
ｌｏｇｉｃ<
/p>
ｍｅｔｈｏｄ．Ｔｈｅ
ｃｉｒｃｕｉｔ
ｄｅｓｉｇ
ｎ
ｉｓ
ｓｕｃｃｅｓｓｆｕｌｌｙ
ｓｙｎｔｈｅ ｓｉｚｅｄ
ｉｎ
ｔｈｅ
Ｘｉｌｉｎｘ
< p>Ｓｐａｒｔａｎ
３
ＦＰＧＡ
ｄｅｖｉｃｅ< /p>
ａｎｄ
ｔｈｅ
ａｒｅａ
ｏ
ｆ
ＡＥＳ
ｃｉｒｃｕｉｔ
ｉｓ
ｆｉｎｅｌ
ｙ
ｏｐｔｉｍｉｚｅｄ．
Ｋｅｙｗｏｒｄｓ：ＡＥＳ
ｅｎ ｃｒｙｐｔｉｏｎ
ａｌｇｏｒｉｔｈｍ；Ｓ—ｂｏｘ；ｍｉｘ
ｃｏｌｕｍ
ｎ；ｏｐｔｉｍｉｚａｔｉｏｎ；ＦＰＧＡ
ｉｍｐｌｅｍｅｎｔａｔｉｏｎ
美国国家标准与技术局（Ｎａｔｉｏｎａｌ
Ｓｔａｎｄａｒｄ
ａｎｄ< /p>
Ｉｎｓｔｉｔｕｔｅ
ｏｆ
择合适的即约多项式，进
行域ＧＦ（２８）到ＧＦ（２４）的同构
映射，对Ｓ—ｂｏｘ的算法进行优化，并采用组
合逻辑电路
实现，使优化后的Ｓ—ｂｏｘ在同等频率条件下较显著地
减少了硬件资源的消耗。同时介绍了一种减小列混合
（ＭｉｘＣｏｌｕｍｎ）单元硬
件复杂度的方案，可以明显地减
少列混合单元的设计面积。
１<
/p>
Ｔｅｃｈｎｏｌｏｇｙ，ＮＩＳＴ）于１９９７年１月提出
发展Ａ
ＥＳ（Ａｄｖａｎｃｅｄ
Ｅｎｃｒｙｐｔｉｏｎ
Ｓｔａｎｄａｒ
ｄ）加密算法，
并于同年９月１２日推出ＡＥＳ的早期基本算法。在研
< br>究了一系列早期算法之后，Ｒｉｊｎｄａｅｌ算法被确定为先进
加密标准（Ａｄｖ
ａｎｃｅｄ
Ｅｎｃｒｙｐｔｉｏｎ
Ｓｔａｎｄａｒｄ，ＡＥＳ）
。由
于其较高的保密级别，ＡＥＳ算法被用来替代ＤＥＳ和
３一
ＤＥＳ，以适应更为严苛的数据加密需要。
与此同时，市场迫切需要ＡＥＳ的ＦＰＧＡ和
ＡＳＩＣ
的硬件解决方案，因为其与用软件实现相比更安全而且
更省电。在一些应用，如：信用卡，手机，ＰＤＡ等中，硬
件的复杂度是影响成本和能耗
的一个非常重要的因素。
因此。在加密和解密中都非常需要优化ＡＥＳ的主要操
作部分。在ＡＥＳ算法中，Ｓ—ｂｏｘ是惟一的非线性单
元，在加密解密
，特别是字节替代和逆字节替代操作时
需要分别执行Ｓ—ｂｏｘ和逆Ｓ—ｂｏｘ。建立一
个１６×１６
的Ｓ—ｂｏｘ，以往通常采用查找表的方式实现，占用大量
硬件资源。因此，对Ｓ—ｂｏｘ进行优化是实现高效ＡＥＳ
的重要步骤。
在此首先通过在Ｓ—ｂｏｘ和逆Ｓ—ｂｏｘ中共用一个
ｌｏｏｋ—ｕｐ
列表，简化非线性单元的复杂度，然后通过选
收稿日期：２００９一０６—１８
Ｓ—ｂｏｘ的优化设计
在ＡＥＳ标准算法中定义了两个较大的列表。Ｓ—
ｂｏｘ和逆Ｓ—ｂｏｘ。将Ｓ—ｂｏｘ用于两个应用：字节替代
和密钥扩展。而逆Ｓ—ｂｏｘ则用于逆字节替代。这两个
列表是不相同的，因此必须建立
两个不同的ＲＯＭ
（２５６×８
ｂ），用以存储这两个列表。另
外，在ＡＥＳ设计
中使用平行结构，这就需要用到多个列表，这样会使硬
件过于复杂，需要对其进行优化。以下主要对Ｓ—ｂｏｘ
模块进行结构优化。<
/p>
１．１
Ｓ—ｂｏｘ和逆Ｓ—ｂｏｘ的组合
在一个高速１２８
ｂ的ＡＥＳ设计中，一般需要总共
２０个Ｓ—ｂｏｘ模
块和１６个逆Ｓ—ｂｏｘ模块。其中，１６个
Ｓ—ｂｏｘ模块用于实现字节替代的功能，
４个Ｓ—ｂｏｘ用
于实现密钥扩展的功能，而１６个逆Ｓ—ｂｏｘ模块用于实
现逆字节替代功能。在这种情形下，如果字节替代和逆
字节替代时使用不同
的列表，就会占用大量的硬件资
１
１
万方数据<
/p>
源。所以非常需要一种减少硬件复杂性的方法。
就如ＡＥＳ标准所
描述的那样，Ｓ—ｂｏｘ的操作过程
可以表示为：
Ｙ＝Ｍ?ｍｕ
ｌｔｉｐｌｉｃａｔｉｖｅ＿ｉｎｖｅｒｓｅ（ｘ）＋ｃ
（１）
其中：
１
１
１
１
１
Ｏ
Ｏ
０
Ｏ
１<
/p>
１
１
１
１
Ｏ
Ｏ
Ｏ
Ｏ
１
１
１
１
１
Ｏ
Ｍ＝
Ｏ
Ｏ
Ｏ
１
１
１
１
１
（２）
１
Ｏ
Ｏ
Ｏ
１
１
１
１
１
１
０
Ｏ
０
１
１
１
１
１
１
Ｏ
Ｏ
０
１
１
１
１
１
１
Ｏ
Ｏ
Ｏ
１
０
０㈤１
Ｍ，一Ｍ＿
１一Ｉ
㈦１
ｏ
１
ｏ
ｏ
１
０：１｜］
< br>ｏ
１
ｏ
㈦㈦１
< br>１
ｌ（５）
１２
万方数据
图１
Ｓ—ｂｏｘ／逆Ｓ—ｂｏｘ模块
Ｓ—ｂｏ
ｘ硬件实现时的主要部件是乘法求逆。在有
限域ＧＦ（２８）上，乘法求逆是一种相当复
杂的函数．直接
在域ＧＦ（２８）上生成Ｓ—ｂｏｘ盒，组合逻辑复杂度高，会
使电路中逻辑电路的门数大大增加。根据有限域的性
质，利用域ＧＦ（２
８）与ＧＦ［（２４）２］的同构变换，把
ＧＦ（２８）上的求逆转化在ＧＦ［（２４）
２］上的求逆运算，从
而生成Ｓ—ｂｏｘ单元。可以降低逻辑关系运算的复杂度，
优化Ｓ—ｂｏｘ的面积。
所采用有限域ＧＦ（２８）上的乘法求逆电路
模块优化
过程如图２所示。优化的乘法求逆过程可表述如下：
（
１）通过线性变换丁将ＧＦ（２８）的输入Ｘ映射到
域ＧＦ（２
４）上的 元素ｂ，（；
（２）构建相应的域ＧＦ（２
４）的一次多项式，定义域< /p>
ＧＦ（２４）上的加法、乘法和求逆运算。利用域（；Ｆ（２
４）
上
的加法、乘法和求逆运算，得到域ＧＦ（２４）上元素ｂ，Ｃ的
逆元素Ｐ，ｑ；
（３）构建线性变换ｒ１，将域ＧＦ（２
４）上的元素 Ｐ，ｑ
映射到域ＧＦ（２８）上，得到域ＧＦ（２８）上的元素ｚ的逆元
素Ｙ＝Ｔ’１（Ｐ，ｑ）。
图２
ＧＦ（２５）求逆电路优化
由有限域的知识可知。复合域ＧＦ［（２４）２］中每个元
素都可表
示为系数在ＧＦ（２４）上的一次多项式６ｚ＋Ｃ。
设定义有限域ＧＦＥ（２４）２］的
乘法的二次不可约多项式
ｚ２＋Ａ丁＋Ｂ，可验证此时ＧＦ［（２４）２］中的任一元素
６ｚ＋Ｃ的乘逆元素是：
（ｂｚ＋Ｃ）～一ｂ（ｂ２Ｂ＋ｂｃＡ
＋Ｃ２）叫ｚ＋
（Ｃ＋ｂＡ）（ｂ２Ｂ＋出Ａ＋Ｃ２）＿１
（７
）
式中：（６２
Ｂ＋ｂｃＡ＋ｆ２）＿１是ｂ２Ｂ＋ｂｃＡ＋ｃ
２在ＧＦ（２４）
上的乘法逆元。各部分的逻辑实现过程可描述如下：
< br>（１）有限域ＧＦ（２８）到复合域ＧｖＥ（２
４）２］映射。通
过ＧＦ（２８）上的即约多项式户（ｚ）一．３７２十Ａ丁＋ｊ；构造线
性变换Ｔ。根据
式（８）将ＧＦ（２８）的输入ｚ映射到
ＧＦ（２４）上的元素ｂ，Ｃ：
｛ｂＥ３：ｏｌ，ｃＥ３：０３｝一如
（８）
式中：Ｂ
是ＧＦ（２
４）上的常量元素；Ｔ是一个８×８的矩
阵，矩阵的元素是０
或ｌ，Ｔ矩阵由Ｂ的取值决定；Ａ取
１，Ｂ取８；
１
Ｏ
Ｏ
Ｏ
１
１
１
Ｏ
Ｏ
１
１
Ｏ
０
Ｏ
０
Ｏ
Ｏ
Ｏ
Ｏ
Ｏ
Ｏ
Ｏ
< p>Ｏ
１
Ｏ
Ｏ
１
Ｏ
１
Ｏ
Ｏ
Ｏ
Ｔ：＝
／～
９
、Ｊ
０
Ｏ
Ｏ
０
ｌ
１
Ｏ
Ｏ
１
Ｏ
０
１
Ｏ
１
１
Ｏ
Ｏ
１
１
Ｏ
１
０
０
Ｏ
Ｏ
Ｏ
Ｏ
１
Ｏ
１
（２）ＧＦＥ（２４）２］到ＧＦ（２８
）的逆映射。构造线性变
换Ｔ－１，ＧＦ（２４）上的逆Ｐ，ｑ映射到ＧＦ（２８）上的
逆元素
Ｙ，如式（１０）所示。其中，线性变换ｒ１和乘法求递
步骤（１）中的线性变换Ｔ满足：玎一一Ｅ。
Ｙ＝Ｔ－１｛户［３：ｏ］，ｑＥ３：ｏ］
｝
（１０）
其中：
１
Ｏ
Ｏ
０
１
０
Ｏ
Ｏ
Ｏ
Ｏ
Ｏ
Ｏ
< br>１
１
Ｏ
１
Ｏ
１
Ｏ
Ｏ
１
１
Ｏ
１
Ｏ
１
Ｏ
Ｏ
Ｏ
１
１
Ｏ
Ｔ－１＝
／～
ｌ
●●■
、Ｊ
Ｏ
１
Ｏ
ｌ
１
１
Ｏ
１
Ｏ
０
１
Ｏ
ｌ<
/p>
ｌ
Ｏ
Ｏ
０
ｌ
１
１
１
Ｏ
Ｏ
１
Ｏ
Ｏ
ｌ
Ｏ
１
１
Ｏ
１
（３）通过域ＧＦ（２４）上的运算，求ｂ，ｃ的逆Ｐ，ｑ。首
< br>先构建ＧＦ（２４），ｇ（ｚ）一一＋Ｘ＋ｌ作为域ＧＦ（２４）上的
本源多项式
，口（ｚ），ｄ（ｚ），已（ｚ）Ｅ－ＧＦ（２４）。其中，
口（ｚ）＝ａ３２３如２２
２＋ａｌｚ＋ａｏ，ｄ（ｚ）一ｄ３２３＋ｄ２２２＋
ｄｌｚ＋ｄｏ，Ｐ（ｚ）＝ｅ３２
３＋ｅ２２２＋ｅｌｚ＋ｅｏ定义域ＧＦ（２４）
上的加法、乘法、逆运算。
①加法为按位异或。
②乘法为多项式相乘后用ｑ（ｚ）取模，按公式
Ｐ（ｚ）＝ｎ（ｚ）ｏ
ｄ（ｘ）ｍｏｄ
ｑ（ｚ
）进行运算；
③求逆根据公式公式口?ａ－１＝１
ｍｏｄ
ｇ（ｚ），计算
ＧＦ（２４）上元素ａ的逆ａ～；
构造ＧＦ（２４）上的一次多项式妇＋Ｃ，并利用上述
ＧＦ（２４）上的加法、乘法
和求逆运算进行运算，得到
ＧＦ（２４）上的元素ｂ，ｆ的逆Ｐ，ｑ，由式（７）可得：
（如＋ｆ）一１＝６（８ｂ２＋缸＋Ｃ２）－１２４－
（ｆ＋６
）（８ｂ２＋ｂｃ＋ｆ２）＿１
（１２）
Ｐ＝６（８ｂ２＋＆＋
Ｃ２）一
（１３）
ｑ＝（ｆ＋６）（８ｂ２＋ｂｃ＋ｆ２）一１
（１４）
Ｐ，ｑ的计算是Ｓ—ｂｏｘ中最复杂的逻辑运算，占用
了大量的逻辑关系，关于Ｐ，ｑ的分量元素计算是由上述
算法中
的分量元素代入式（１３）、式（１４）求得。
在这种设计方案中，求逆运算模块中所选
用的即约
万方数据
多项式户（ｚ）和本源多项式ｑ（ｚ）不同，
减低了求逆模块
的复杂度。根据理论分析，本文中用到的户（ｚ）和口（ｚ）
不会减低ＡＥＳ算法的安全性。
２列混合单元的优化设计
< br>在列混合（ＭｉｘＣｏｌｕｍｎ）和逆列混合（ＩｎｖＭｉｘ
Ｃｏｌｕｍｎ）的操
作中，由以下两式定义了两个主要操作：
ｏｕｔ。＝Ｅｚ
３
１
１］?［口ｂ
ｆ
ｄ］Ｔ<
/p>
（１５）
以及：
’
ｏｕｔ，一［Ｅ
Ｂ
Ｄ
９］?Ｅａ
ｂ
ｃ
ｄ］Ｔ
（１６
）
在设计中，可以将两式重组并表示如下：
ｏｕｔ。一２（口＋
６）＋ｂ＋（ｆ＋ｄ）
（１７）
和：
ｏ
ｕｔ，＝４（２（口＋６）＋２（Ｃ＋ｄ）＋（口＋ｆ））＋
２（口＋６）＋ｂ＋（ｆ＋
ｄ）
（１８）
将式（１５）和式（１６）所做的操作及结果列于
表１中，
由步骤１～步骤５处理的结果得到ｏｕｔ。，接着由ｏｕｔ。和
硼。得到ｏｕｔ，。因此，在执行过程中，操作所用到的硬件
资源及其所得结果
可以应用到步骤９，步骤１０中。如
图３所示，这种新型结构（字节一列混合模块）仅需
８个
加法器和４个乘法器。与原方案相比，此设计大大减少
了硬
件复杂度并显著节省了资源的消耗。
裹１对式（１１）和式（１２）的重组操作
步骤
操作
步骤
操作
１
Ｚ０１一ａ—ｌ－ｂ
６
< br>∞６一Ｗ２＋Ｗ４＋ｔ啦
２
∞２＝ａ＋ｆ
７
＂Ｗ７一＂６×２
３
Ｗ３＝
ｃ＋ｄ
８
Ｗ８＝Ｗ７×２
４
批＝∞ｌ×２
９
ｏｕｔ，一”３＋ｔ￡，４＋ｂ<
/p>
５
讹＝ｗ３×２
１０
ｏｕｔ，＝Ｏｕｔ．－＋撕
占
’丫７
ｌ、爪
ｕ｛７、
．厂ｈ
一７
Ｗ
７Ｗ
，７删７丫：。
ｃ
一。，，
，、
十
。，一
ｔ束ｗ
７＼
｝
．。厂了］
‘一ｎ［７＇Ｏ］冈ｏｕｔ［７＂Ｏ，］
图３
字节一列混合模块
图３中：Ｘ，模块（ＡＥＳ中的乘法器）的计算公
式为：
ｏｕｔ［－７：ｏ］一｛ｉｎ［－６：４３，ｉｎ［＇３
：ｏ］Ａ｛ｉｎＥ７］，ｉｎＥ７］，
０，ｉｎ［Ｚ］），ｉｎ［Ｚ］）
更进一步，会发现，要建立一个全局的逆选择列混
合模块，需要将４个字节一列
混合模块集成在一起，形成
一个全新的字一列混合模块（Ｗｏｒｄ—ＭｉｘＣｏｌｕｍｎ
模块），
如图４所示。
这种模块设计可以通过部分分享硬件来同
时实现
】３
列混合和逆列混合的功能，实现了硬件资源的节省。
-
-
-
-
-
-
-
-
-
上一篇：基于电平检测的上电复位电路
下一篇：RF螺旋电感参数的提取方法