ＯＭ Ｐ ＵＴ ＥＩ《 曩Ｊ鼹Ｉ Ｙ｜髓 ｌＩ ■一己：— ● ＹＡＥ５算法的硬件实现分析与设计 郭建军 ，刘昌明’，石颖 ，卢霞 ，。 （１．中国人民９２７２３，北京１００８４１，２．中国人民９１７３１，北京１０２２０４） 摘 要：分析了ＡＥＳ算法的结构特点，对算法的不同硬件实现方式进行了对比分析，分析结果表明，不同的实现方式在算法 应用模式支持、运行频率、资源占用、吞吐量方面各有优缺点，需要根据具体应用需求采用合适的实现方式。对ＡＥＳ算法不 同实现方式的分析以及提出的设计结构对于其他类似的分组密码算法实现也具有参考价值。 关键词：ＡＥＳ算法；硬件实现；分析 Ｈａｒｄｗａｒｅ ＩｍｐＩｅｍｅｎｔａｔｉｏｎ Ａｎａｌｙｓｉｓ ａｎｄ Ｄｅｓｉｇｎ ｏｆ ＡＥＳ Ａｌｇｏｒｉｔｈｍ ＧＵＯ Ｊｉａｎ－ｊｕｎ ，ＬＩＵ Ｃｈａｎｇ－ｍｉｎｇ ，ＳＨＩ Ｙｉｎｇ ，ＬＵ Ｘｉａ ，ＺＨＡＮ（｝Ｊｉａｎ ，ｆ Ａ ｊ Ａｒｍｙ，Ｂｅ啪ｇ １００８４１．Ｃ／￣／）Ｔａ：２ Ａ ９ ５｝Ａ／ｍｙ，日￡晌ｇ １０２２￣●４．国荫ａ Ａｂｓｔｒａｃｔ：Ｔｈｅ ｓｔｒｕｃｔｕｒａｌ ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ ｏｆ ｔｈｅ ＡＥＳ ａｌｇｏｒｉｔｈｍ ａｒｅ ａｎａｌｙｚｅｄ．Ｄｉｆｆｅｒｅｎｔ ｈａｒｄｗａｒｅ ｉｍｐｌｅｍｅｎｔａｔｉｏｎｓ ｏｆ ｔｈｅ ａｌｇｏｒｉｔｈｍ ａｒｅ ｃｏｍｐａｒｅｄ ａｎｄ ａｎａｌｙｚｅｄ．Ｔｈｅ ａｎａｌｙｓｉｓ ｓｈｏｗｓ ｔｈａｔ ｄｉｆｆｅｒｅｎｔ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｈａｓ ｉｔｓ ｏｗｎ ａｄｖａｎｔａｇｅｓ ａｎｄ ｄｉｓａｄｖａｎｔａｇｅｓ ｕｎ ａｐｐｌｉｃａｔｉｏｎ ｍｏｄｅ ｓｕｐｐｏｒｔ，ｒｕｎｎｉｎｇ ｆｒｅｑｕｅｎｃｙ．ｒｅｓｏｕｒｃｅｓ ｕｓｅｄ ａｎｄ ｔｈｒｏｕｇｈｐｕｔ ＳＯ ａｐｐｒｏｐｒｉａｔｅ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｍｅｔｈｏｄ ｍｕｓｔ ｂｅ ｃｈｏｓｅｎ ａｃｃｏｒｄｉｎｇ ｓ ｅｃｉｆｉｃ ａｐｐｌｉｃａｔｉｏｎ ｒｅｑｕｉｒｅｍｅｎｔｓ．Ｓｕｃｈ ａｎａｌｙｓｉｓ ａｎｄ ｔｈｅ ｐｒｏｐｏｓｅｄ ｄｅｓｉｇｎ ｓｔｒｕｃｔｕｒｅ ｃａｎ ｂｅ ｒｅｆｅｒｅｎｃｅ ｆｏｒ ｏｔｈｅｒ ｂｌｏｃｋｅｄ ｃｒｙｐｔｏｇｒａｐｈｉｃ ａｌｇｏｒｉｔｈｍ． Ｋｅｙ ｗｏｒｄｓ：ＡＥＳ ａｌｇｏｒｉｔｈｍ，ｈａｒｄｗａｒｅ ｉｍｐｌｅｍｅｎｔａ￣ｉｏｎ，ａｎａｌｙｓｉｓ ０引言 发展，采用硬件实现算法越来越广泛。与传统的软 ＡＥＳ是美国国家标准局与技术研究所（ＮＩＳＴ） 件加密方法相比，硬件实现加密具有安全性好、计 提出的高级加密标准…，２０００年ｌ０月，ＮＩＳＴ宣 算速度快、效率高、性能可靠等优点。通常，ＡＥＳ 布以比利时人Ｊｏａｎ Ｄａｅｍｅｎ和Ｖｉｃｅｎｔ Ｒｉｊｉｎｅｎ 算法硬件实现主要是通过提高时钟频率来提高吞 提交的ＲｉｊＩ１ｄａｅｌ算法作为高级加密标准（ＡＥＳ）。 吐量。但是在实际应用中，为了保证整个加密系统 Ｒｉｊｎｄａｅｌ是具有可变分组长度和可变密钥长度的分 的稳定性，通常系统时钟频率较低，不可能达到 组密码算法，其分组长度和密钥长度均可以地 算法的仿真频率，如ＰＣＩ接口电路时钟频率只有 设定为３２ｂｉｔ的任意整数倍，最小值为１２８ｂｉｔ，最 ３３ＭＨｚ或６６ＭＨＺ，因此实际数据吞吐量受限于接 大值为２５６ｂｉｔ。ＡＥＳ标准采纳的Ｒｉｊｎｄａｅｌ将分组 口时钟频率。 长度固定为１２８ｂｉｔ，而且仅支持ｌ２８ｂｉｔ、１９２ｂｉｔ和 本文根据ＡＥＳ算函数良好的并行特性有利 ２５６ｂｉｔ的密钥长度 。 于硬件设计与实现的结构特点，对其硬件实现进行 本文将主要讨论分组长度和密钥长度为１２８ｂｉｔ 基于吞吐量的比较分析，之后，给出一种高速ＡＥＳ 的情况。在这种情况下，算循环次数为ｌ０次， 算法核设计方案。该方法采用优化设计轮函数和数 其他密钥长度的算法区别在轮循环次数和密钥长度 据并行技术以及结构解耦技术，在较低的系统时钟 上有所不同。 频率下，可以达到较高的数据吞吐量。ＡＥＳ算法是 ＡＥＳ算法设计简单，没有复杂的乘法运算，易 一个典型的分组密码算法，对其硬件实现进行分析， 于实现，灵活性强，自从提出之后，得到了大量应 对于提高该算法的设计性能具有重要意义，同时对 用，尤其是随着可编程技术及高速集成电路的不断 于其他分组密码算法的实现也具有借鉴意义。 ２ ０ １ ２．０ ７ 圃口团圈Ｖ＾Ｖｗ ｒｑｓｃ．ｏｒｇ ｃｎ Ｉ｝ ８ ｅ≤’糖ｐｉｊ 鼗 Ｓ馘《 娃ｌ １ ＡＥＳ算法结构特点分析 ＡＥＳ算法是一个迭代型分组算法，结构紧凑、 规整，采用的是替代／置换（ＳＰ）网络结构 。算 法的每一轮由三层组成： （１）非线性层：完成字节替代（Ｓｕｂｓｔｉｔｕｔｅ Ｂｙｔｅｓ），即Ｓ盒置换，起到混乱的作用； （２）线性混合层：完成行移位（Ｓｈｉｆｔ Ｒ０ＷＳ） 和列混合（Ｍｉｘ Ｃｏｌｕｍｎｓ），以确保多轮之上的高 度扩散； （３）加密钥层：完成轮密钥加（Ａｄｄ Ｒｏｕｎｄ Ｋｅｙｓ），将子密钥异或到中间数据。 ＡＥＳ算法加密流程结构如图１所示，将输入的 明文分成１２８ｂｉｔ，在第一个轮密钥加变换后进入ｌ０ 轮迭代。前９轮完全相同，依次经过字节替代、行 移位、列混合、轮密钥加，最后一轮不同，跳过了 列混合。解密过程与加密过程类似。 明文鞭｝岳 明寓教搪 ｝蛙蝴加 轮舒锄口 反字节咎代 字嚆咎代 良奸 世 秆硌位 蒜 …．．到竭专 －．…．． 鹾列混合 蛭舒调加 皑啬 加 鹱事书簪代 字节咎 爱秆硌位 行睁世 Ｉ蛇 加 Ｉ 皑密铆口 啬文数据 ∞加密过程 ｊ 舒毡程 图１ ＡＥＳ算法流程结构图 Ａ ＥＳ算法的具体执行过程为输入初始密钥，进 行密钥扩展，使用扩展子密钥进行若干轮的轮函数 运算。因此，对于ＡＥＳ算法的硬件实现优化，主 要针对这两个过程，即密钥扩展和轮函数运算过程 进行优化设计，以达到提高吞吐量的目的。 ２ ＡＥＳ算法硬件实现分析 ２．１密钥扩展实现分析 ２ ０ １ ２．０ ７ ９ ｝ｗｗｗ ｎｓｃ ｏｒｇ ｃｎ 固｜＝］皿圈 Ａ ＥＳ算法每次轮操作需要一组子密钥，而每一 组子密钥的产生只与上一组子密钥相关。密钥扩展 是将初始密钥作为种子密钥，经过计算产生ｌＯ轮 迭代子密钥。算法实现时，可以考虑同步进行密钥 扩展和加密过程，这样无需存储器资源存储扩展子 密钥，可以节约ＦＰＧＡ的存储器资源，但这样做在 算法运行过程中，扩展密钥过程会一直运行，增加 了ＦＰＧＡ芯片的动态功耗。另外，ＡＥＳ算法解密 运算是从最后一轮子密钥开始，只有扩展出所有子 密钥才能启动解密运算，因此，制约了解密过程的 实现，而且加密和解密实现结构也不一致。通常情 况下，对于大包数据加／解密会采用同一初始密钥， 加／解密多包数据可共享同一密钥扩展结果，同时， 由于ＦＰＧＡ器件存储器资源丰富，为存放子密钥 提供了足够的存储空间，因此，实现中可先进行密 钥扩展，将子密钥保存到块ＲＡＭ中，使用时依次 从块ＲＡＭ中读取。这种方式实现了密钥扩展过程 和加解密过程的解耦，不受加解密实现过程的， 灵活性强，非常适合用于算法的ＦＰＧＡ实现。 访问块ＲＡＭ读取子密钥需要时间，为了避免 算法第一个轮密钥加过程的延时，可以采用如图２ 所示的密钥扩展结构，将加密过程第一组子密钥（ 即初始密钥）和解密过程第一组子密钥（即密钥扩 展得到的最后一组子密钥）在写入块ＲＡＭ的同时， 分别保存在两组寄存器中。这样，加／解密时可以 直接利用寄存器暂存结果进入第一轮迭代，无需访 问块ＲＡＭ过程的等待，从而减少运算时间。 图２密钥扩展结构 ２．２轮函数实现分析 加密系统中体现数据处理速度的一个重要性能 《：薯Ｊｌ鼍Ｉ Ｙ蟹圈 ■ ■■￡：— 一 ＴＹＩＪＴＩ￣ＩＩ指标是数据吞吐量，其计算公式为：算法时钟频率 ×（分组数据长度／每分组运算时钟周期数）。提 高数据吞吐量是改善加密性能的关键，也是加密算 法硬件实现技术的重要内容。由上述计算公式得出， 吞吐量成正比于时钟频率，成反比于每分组运算时 钟周期数。对ＡＥＳ算法加解密速度优化将集中于 提高算法时钟频率，降低每分组运算时钟周期数。 ２．２．１算函数的不同实现方式 ＡＥＳ算法的加解密过程核心为ｌ０次轮操作， 前一轮操作的输出即为下一轮操作的输入。每次对 一个分组数据进行加解密，当采用Ｅ Ｃ Ｂ（Ｅｌｅｃｔｒｉｃ Ｃｏｄｅｂｏｏｋ）模式时，前后数据块之间不存在相关性， 存在高度的数据并行性。优化轮函数设计，降低时 钟周期，是提高算法时钟频率的关键，而采用合适 的控制结构，充分利用硬件资源使算法能够处理更 多分组数据是降低每分组运算周期数的关键。ＡＥＳ 算法的轮操作特点使得在用硬件实现时可以有如下 多种方式： （１）串行方式 轮函数用组合逻辑实现，ｌ０轮迭代过程直接相 连，前一轮结果直接作为下一轮的输入，１个时钟 周期内完成一个分组运算输出一个运算结果。但由 于ｌ０个轮函数同时工作，整个逻辑延时与１０个轮 函数逻辑路径叠加和成比例，时钟频率非常低，整 体吞吐量并不高，同时由于全部ｌ０个轮函数逻辑 — 均需硬件实现，还需要大量的寄存器资源和组合逻 辑资源的支持，一般ＦＰＧＡ芯片也难以满足容量的 要求，所以这种方法不适合加密算法的硬件实现。 ＼ ———————一ｔ—————————Ｊ 图５串行方式示意图 （２）基本迭代方式 为提高算法的时钟频率，可以采用轮问反馈模 式，每次迭代只实现一个轮函数模块，整个逻辑延 时与单个轮函数逻辑路径成比例，可以实现较高的 时钟频率，对于单个轮函数逻辑还实现了复用，资 源占用较少，但是一次分组运算需要１０个时钟周期， 但每个分组运算时间比较长，吞吐量仍然相对较低。 图４基本迭代方式示意图 （３）宏观流水方式 由于上述串行方式的路径延时比较长，算法的 时钟频率较低，基本迭代方式时钟频率较高，但是 产生分组运算结果的周期数较多，二者数据吞吐量 都不高。因此，考虑将其整个运算过程的轮迭代路 径进行切分，采用轮外宏观流水方式实现算法。例 如，可以将ＡＥＳ算法的１０轮迭代过程分为前后两 个操作段，每个操作段可作为一级流水线，前一个 操作段结束后，将结果直接送入第二个操作段，同 时去处理下一个分组数据，两个操作段互不影响， 并行执行。此种实现方式的路径延时和５个轮函数 逻辑路径叠加和成比例，时钟频率高于串行方式。 并且在完全流水后每个周期产生一个分组运算结果， 吞吐量也要高于串行方式和基本迭代方式。在逻辑 资源占用上，它需要实现单操作段５个轮函数逻辑， 同时实现两个操作段，仍相当于ｌ０个轮函数逻辑 均需硬件实现。 图５宏观流水万式示意图 （４）微观流水方式 上述宏观流水方式实现的算法时钟频率不高， 但是每个周期产生一个分组运算结果。为提高时钟 频率，微观流水方式的实现中，将一个轮函数由单 周期实现，１０个轮函数仍通过１０个周期的运算完 成，但是通过控制模块实现若干个周期后中间数据 转向下一流水段。例如，可以将ＡＥＳ算法的１０轮 迭代过程分为前后两个操作段，每个操作段可作为 一级流水线，但是此时一个流水段由微观上的５个 ２ ０ １ ２．０ ７ 丽Ｉ＝＝伍圈ｆ１０ 《 Ｏ髓ｐ鼍ｊ 魏 《 ｉ鏖藿ｌ 时钟周期完成，前一个操作段结束后，将结果直接 送入第二个操作段，同时前一个操作段可以接收下 一个分组数据。此种实现方式，需要控制电路完成 周期计数实现输入数据控制，同时需要两套轮函数 逻辑并行运算。其时钟频率高于宏观流水方式，但 是单分组数据产生周期数长于宏观流水方式，在吞 吐量上与宏观流水方式相比并无实质性提升，但其 硬件资源占用明显少于宏观流水方式。 —～ ————一 图６微观流水方式示意图 （５）轮内流水线方式 此种方法在串行方式基础上，将轮函数逻辑进 行切分，在轮函数中插入寄存器，将每一轮运算分 成多个操作段，每个时钟完成一个操作段，其优点 是可以提高算法运行的时钟频率。但轮内各级流水 部件不能同时执行，因此增加了算法运行的时钟数 目。如果轮内切分级数越多，时钟数目也越多，虽 然算法仿真频率可以达到很高，但由于受硬件加密 系统全局时钟的影响，吞吐量并无实质提升。 图７轮内流水线方式示意图 （６）数据并行方式 此种实现方式在轮函数实现上与轮内流水线方 式相同，将轮函数逻辑切分成多段，不同之处在于 通过控制电路使得算法能够依次接收多路数据进行 加解密运算，能够充满轮内流水时产生的空闲操作 段，使得算法能够以猝发的方式，每隔若干个周期 依次产生多个分组运算结果，降低了每个分组运算 结果产生的平均周期数，同时，将一个轮函数逻辑 路径进行切分，可以提高时钟频率，此种实现方式 兼具轮内流水线方式的高时钟频率特点，同时利用 数据并行的方式，提高了整体吞吐量。此种实现方 式，在逻辑资源的占用上，与轮内流水方式的差别 ２ ０ １ ２．０ ７ １１ 固口圃隔 ＷＷＷ ｎＳＣｏｒｒ￣，３ ｃｎ 主要是控制电路的不同，同时，由于可以依次接收 多组数据进行运算，可能存在同时访问Ｓ盒的情况， 若Ｓ盒采用存储资源实现，需要使用多端口的存储 器。若将多个轮函数作为一个整体实现流水，则可 提供更高的吞吐量，同时，也需要占用更多的逻辑 资源实现多个轮函数逻辑。 图８数据并行方式示意图 ２．２．２不同实现方式的对比 假设单个轮函数逻辑路径长度为Ｌ，可切分为 ｎ段，一个分组运算需要ｉ３３轮，可分为Ｓ个宏观流 水段实现，数据并行方式将ｋ个轮函数逻辑作为一 个整体实现流水。由于吞吐量ＴＰ成正比于频率Ｆ， 成反比于一个分组结果产生周期数Ｒｔ，可得出如 表１所示的吞吐量对比。 根据表１的对比分析，对于本文中的ＡＥＳ算法， 若ｌ０轮运算（ｍ：１０）宏观上切分为两个流水段 （Ｓ：２）实现，单个轮函数内部切分成两段（ｎ＝２）， 两个轮函数作为整体（ｋ＝２）实现数据并行流水， 则数据并行方式的算法就实现了最高的吞吐量。 ２．３启示 对于ＥＣＢ方式的分组密码算法，由于不同分组 数据之间存在并行性，在实现方式的选择上，可以 根据时钟频率、资源占用、吞吐量等因素综合考虑， 采用合适的实现方式。如果分组密码算法应用模式 中前后分组之间存在运算关系，则一般只能采用串 行方式或基本迭代方式。 以上基于吞吐量的分析，主要建立在轮函数逻 辑数据的优化设计上，这需要在算法核设计上采用 密钥扩展过程和轮函数计算过程的解耦，保证设计 优化集中在轮函数逻辑实现上。在实际开发中，有 可能控制通路成为关键路径，则还应注意优化其他 关键路径。同时，在实际开发中，为了保证整个加 １）１１ ＰＩＪ Ｔ曼鼍ｌ ！￣ＩＹＩ墨 — ●— — 一 …密系统的稳定性，通常全局时钟频率较低，不可能 达到算法的仿真频率，如ＰＣＩ接口电路时钟频率只 有３３ＭＨｚ或６６ＭＨｚ，因此实际数据吞吐量仍然较 低。因此，根据ＡＥＳ算法的结构特点及硬件系统 的特点，可以采用输入／输出ＦＩＦＯ实现算法核和 外围总线的解耦，在较低的系统时钟频率下，提高 算法核的内部运行频率，从而提高应用数据加解密 速度。 表１吞吐量对比分析 妄现专式 频星Ｆ 单＿哥参运尊 乃 正比子 王比 厨 数 ， 奉行 １ ｍＬ ｌ １ ｔｌｉｌ 基本迭发 ｌ上 鲋 １＇ｍＬ 宏观 壹呔 ｓ ｍＬ １ ￡ 墩观漫糸 １ ｍ Ｓ Ｓ＇ｍＬ 轮内浇水 ７ｔＬ ， ｊ １ Ⅳ旺 数据并行 Ｌ ｔｌｌｔｉ＋］ｏ１．１）蒋” 川 Ｚ ｒ ７卜膏 卜１） ３数据并行方式的ＡＥＳ算法ＦＰＧＡ实现 基于上述硬件实现对比分析，本文实现了数据 并行方式的ＡＥＳ算法，将轮函数切分为２段，依 次接收２路数据后进行运算，２０个周期后依次给 出２组运算结果。实现过程中，采用了密钥扩展和 轮函数的过程解耦，以及使用输入／输出ＦＩＦ０实 现算法核和外围总线的解耦。ＡＥＳ算法的Ｓ盒是一 个８入８出的查找表，算法的并行运算需要３２个 Ｓ盒，如果用逻辑资源实现，不但占用大量的硬件 资源，而且使结构复杂，增加了延时。而用存储器 资源实现Ｓ盒，不需占用其他逻辑硬件资源，并且 可以减少延时。本文的实现中使用了存储器资源实 现Ｓ盒，这样正好也实现了算函数内部的２级 切分。同时，设计中将加／解密过程的Ｓ盒设计在 同一个块ＲＯＭ内，加密Ｓ盒内容置于块ＲＯＭ的 前８ｂｉｔ，解密Ｓ盒内容置于块ＲＯＭ的后８ｂｉｔ，这 样可以使存储器块的数目比分别使用块ＲＯＭ设计 时减少一半，提高了硬件资源利用率。 在Ｘｉｌｉｎｘ公司的ｘｃ４ｖｌｘ２５型号ＦＰＧＡ上实现 该算法，采用Ｓｙｎｐｌｉｆｙ Ｐｒｏ ９．６．２进行综合，采 用Ｍｏｄｅｌｓｉｍ６．０进行模拟仿真，综合后算法的 ＬＵＴ占用比为９％，仿真频率可超过２００ＭＨｚ。该 算法实现在２００ＭＨｚ的稳定时钟下，数据吞吐量可 以达到２．４Ｇｂｐｓ。 ４结束语 本文分析了ＡＳＥ算法的结构特点，对不同方式 算法硬件实现进行了对比分析，分析结果表明，不 同的实现方式在算法应用模式支持、运行频率、资 源占用、吞吐量方面各有优缺点，需要根据具体应 用需求采用合适的实现方式。最后，采用ＦＰＧＡ实 现了数据并行方式的Ａ ＥＳ算法，采用数据并行方 式实现分组密码算法，可以提高数据吞吐量，使加 密算法的硬件实现过程不再是传输速度的瓶颈，整 个设计具有很强的实用性。本文对ＡＥＳ算法不同 实现方式的分析以及提出的设计结构对于其他类似 的分组算法ＦＰＧＡ实现也具有一定的参考价值。 参考文献 …Ｄａｎｍｅｎ Ｊ，Ｐ，ｉｉｊｍｅｎ Ｖ．ＡＥＳ Ｐｒｏｐｏｓａｌ：ｇｉｊｎｄａｅ１．ＡＥＳ ａｌｇｏｒｉｔｈｍ ｓｕｂｍｉｓｓｉｏｎ，ＡＥＳ ｈｏｍｅ ｐａｇｅ：ｈｔｔｐ：／／ｗｗｗ．ｎｉｓｔ．ｇｏｖ／ａｅｓ， １ ９９９一Ｏ９． ［２］基于ＡＲＭ的数据加密算法实现．南京理工大学硕士学 位论文，２００６． ［５】戴尔蒙，瑞蒙著．谷大武，徐胜波译．高级加密标准 （ＡＥＳ）算法——ＲＩｊｎｄａｅｌ的设计．北京：清华大学出版社， ２ＯＯ 作者简介：郭建军（１ ９８ ），男，博士，工程师，主要研 究方向：计算机系统结构 信息安全，嵌入式系统。 收稿日期：２０】２－０６—０４ ２ ０ １ ２ Ｏ ７ 圃｜＝ｗⅥ ＝西圉ｎＳＣ Ｏｒｇ ｃｎｌ ｌ１２
