（电力电子与电力传动专业论文）rijndael算法硬件实现的优化设计及应用.pdf

a b s t r a c t t h i sp r o ，iect b a s e du p o nt h er e s e a r c hr e s u l t so fc r y p t o g r a p h y t o k e ng e n e r a l i z a t i o nt h e o r ya n dm e t h o do f t h ei n s t i t u t eo fc a m p u si c c a r ds t a n d a r d i z a t i o no fe d u c a t i o nm a n a g e m e n ti n f o r m a t i o nc e n t e r i nm i n i s t r yo fe d u c a t i o n ，i sm a i n l yd e s i g n e dt os o l v et h ep r o b l e mo f o p t i m i z a t i o nd e s i g no fe n c r y p t i o nc h i p w h i c hi sn e e dw h e nr a d i o f r e q u e n c yc a r de q u i v a l e n tr e a l i z a t i o nf i n a n c ec a r ds t a n d a r d r i - i n d a e l a l g o r i t h mw i l ls u b s t i t u t ef o rd e s i nt h ef u t u r es e v e r a ld o z e n s y e a r s t o t a k et h em a i n s t r e a mo ft h es y m m e t r i c a le n c r y p t i o na l g o r i t h ma n di t r e p r e s e n t st h eh i g h e s tl e v e li nb l o c kc i p h e ra tp r e s e n t t h ed e s i g nf o r r i i n d a e la l g o r i t h mh a r d w a r ee n c r y p t i o nc h i pa n d i t su t i l i z a t i o ni nt h e p r o c e s s o ff i n a n c i a lt r a d eh a v et h e i m p o r t a n t r e a l i s t i cv a l u e s i m u l t a n e o u s l yw i l lh a v et h ei m p o r t a n tt h e o r ys i g n i f i c a n c ef o ru st o d e s i g ni n d e p e n d e n tc i p h e ra l g o r i t h ma n dc h i pi nt h ef u t u r e 0 nt h eb a s i so ft h ea n a l y z a t i o no f r i j n d a e la l g o r i t h m ，t h i sa r t i c l e f i r s ta r g u ea b o u tt h ef e a s i b i l i t yo f i r e p r o v i n gt h ed e c i p h e ra l g o r i t h m r o u n dt r a n s f o r m a t i o no r d e ra n dt h em i x c o l u m nt r a n s f o r m a t i o na n d t h e nt h e s i g n i f i c a n c e o ft h eh a r d w a r e r e a l i z a t i o n s e c o n d l y , i n a c c o r d a n c ew i mt h ep r e v i o u st r a n s m u t a t i v ea l g o r i t h m i tp r o p o s e dt h e c o n c r e t ee n c r y p t i o n d e c r y p t i o nh a r d w a r er e a l i z a t i o ni nt h ei n t e g r a t e d c i r c u i ts t r u c t u r ea sw e l la sf o u rd i f f e r e n tt r a n s f o r m a t i o n so fr o u n d t r a n s f u r m a t i o n ，t h ec o n t r o lm o d u l e ，t h ek e ye x p a n s i o na n dt h ei n p u t o u t p u tm o d u l e so p t i m i z e dd e s i g nm e t h o da n d e a c hm o d u l er e a l i z a t i o n e l e c t r i cc i r c u i ts t r u c t u r e t h e nu s e st h ev h d l h a r d w a r ed e s c f i p t i o n l a n g u a g et oc a r r yo n t h ed e s c r i p t i o nt ot h es y s t e m ，t a k ef p g a a st h e a l g o r i t h mc a r r i e r , a n dc a r r yo n t l l es i m u l a t i o ni nm a x + p l u s l i f i n a l l y d e s i g n t h ea p p l i c a t i o nm o d e lo f t h i sh a r d w a r e e n c r y p t i o nc h i pi nr a d i o f r e q u e n c y c a r de q u i v a l e n tr e a l i z a t i o nf i n a n c ec a r ds t a n d a r d k e yw o r d s ：刚n d a e la l g o r i t h m ，h a r d w a r er e a l i z a t i o n ，f p g a ， s i m u l a t i o n ，f i n a n c i a ls t a n d a r d ，s m a r tc a r d 狸翌鑫堂亟熊塞 1 引言 1 1 项目研究背景 在信息化的社会里，大量的信息需要进行存储和传输，为了 有效地保护信息的安全，建立完善的信息安全体系势在必行。特 别是在通信、金融、军事等领域，许多服务器、网络交换机、智 能卡( s i n 卡、金融卡) 等都需要加解密芯片。本项目就是基于 教育部教育管理信息中心校园卡标准化研究所密码组件泛化理论 与方法的研究成果，重点解决射频i c 卡等效实现金融卡规范时需 要的加密芯片的优化设计问题。 当今，校园食堂就餐收费、公交车乘车收费基本上都是采用 射频i c 卡，且已经形成了庞大的用卡群体和方便的用卡环境，拥 有众多的系统开发商，因此想大面积地升级卡型短期内不太可能。 这种行业支付应用没有规范可循，电子钱包和操作流程的设计都 由开发商自行负责，安全性、稳定性和可靠性都没有保障，甲方 单位对设备无法选型，选型不当造成巨大损失的事例比比皆是。 如果自行制订一套行业规范，既不具备可信度和说服力，也承担 不起可能出现的风险。如果遵循中国人民银行于1 9 9 8 年发布的 中国金融集成电路( i c ) 卡规范，又与金融c p u 卡的卡型 不符。面对这种既要沿用金融系统规范，又不能改变卡型的矛盾， 我们在分析金融c p u 卡消费交易有效安全计算模型的基础上，提 j 采用射频i c 卡的等价模型及等价终端解决方案让3 。具体来说就 是对射频i c 卡添加等价硬件中问件，通过等价硬件中间件来实现 计算功能。硬件中间件由单片机与专用加密芯片组成，加密芯片 的性能与所选择的加密算法有直接关系。而a e s ( a d v a n c e d e n c r y p t i o ns t a n d a r d 高级加密标准) 标准一r i j n d a e l 算法o 【“ 在未来几十年里将取代d e s 作为主流的对称加密算法，是目前分 组加密算法的最高水平反映，因此设计r i j n d a e l 算法的硬件加密 芯片，并研究其用于金融交易中可信计算的实现方法，具有重要 的现实价值，同时对于我们将来设计具有自主性的密码算法及芯 片，具有重要的理论意义。 湘翌太堂亟途塞 1 2r ij n d a e l 算法硬件实现的研究现状 1 2 1r i j n d a e l 算法的背景 鉴于d e s 的没落，美国政界和商界一直在寻求高强度、高效 率的替代算法。1 9 9 7 年4 月1 5 日，美国国家标准技术研究所( n i s t ) 发起征集高级加密标准a e s 的活动，活动目的是确定一个非保密 的、可以公开技术细节的、全球免费使用的用于保护敏感的( 无 密级的) 信息的对称密钥加密算法，作为新的数据加密标准。1 9 9 7 年9 月1 2 日，美国联邦登记处公布了正式征集a e s 候选算法的通 告。作为进入a e s 候选过程的一个条件，开发者承诺放弃被选中 算法的知识产权。对a e s 的基本要求是：比三重d e s 快、至少与 三重d e s 一样安全、数据分组长度为1 2 8 比特、密钥长度为 1 2 8 1 9 2 2 5 6 比特。1 9 9 8 年8 月1 2 曰，在首届a e s 会议上指定了 1 5 个候选算法。1 9 9 9 年3 月2 2 日第二次a e s 会议上，将候选名 单减少为5 个，这5 个算法是r c 6 ，r i j n d a e l ，s e r p e n t ，t w o f i s h 和h i a r s 。2 0 0 0 年4 月1 3 日，第三次a e s 会议上，对这5 个候选 算法的各种分析结果进行了讨论。2 0 0 0 年1 0 月2 日，n i s t 选择 r i j n d a e l 算法作为美国国家高级加密标准( a e s ) 1 4 1 5 1 。 r i j n d a e l 是从它的两个开发者v i n c e n tr i j m e n 和j o a n d a e m e n 的名字得来的，他们都是公认的国际密码界顶尖高手。纵 观r i j n d a e l 的安全性和其他各种性能，该算法易于实现，灵活性 强，所以成为a e s 的最佳选择方案。无论在反馈模式还是非反馈 模式中使用r i j n d a e l ，其软件和硬件对计算环境的适应性强，性 能稳定，密钥建立时间优良，密钥灵活性强。存储需求量低，即 使在空间有限的环境使用也具备良好的性能。 1 2 2 r i j n d a e l 算法硬件实现的研究现状 r i j n d a e l 是一种迭代分组密码算法，r i j n d a e l 算法本身支持 可变的分组长度和密钥长度，而a e s 只采用了1 2 8 位分组长度和 1 2 8 ，1 9 2 或2 5 6 位的密钥长度。 r i j n d a e l 采用的是代替一置换网络( s p n ) 结构，每轮操 湘湮太堂殛逾塞 作由四层组成，第一层( 字节替换) 为非线性层，用s 盒对每一 轮中的单个字节分别进行替换；第二层( 行移位) 和第三层( 列 混合) 是线性混合层，对当前的状态阵按行移位，按列混合；第 四层( 密钥加层) 用子密钥与当前状态阵进行字节上的异或。 我们所谓的r i j n d a e l 算法硬件实现是指应用e d a ( e l e c t r o n i c d e s i g na u t o m a t i o n 电子设计自动化) 设计技术设计硬件加密芯片， 即用硬件描述语言将r i j n d a e l 算法进行系统设计和编码，然后用 适当的e d a 工具进行仿真和综合，最后用a s i c 或f p g a c p l d 等恰当的方式实现。 当前还处于新旧密码算法交替的时期，尽管r i j n d a e l 算法已 经在某些软件中得到了应用，但是相应的硬件产品却较少。美国 的g m u 和n s a 等大学和机构提供了有关a e s 的i p 核。其中以g m u 大学的i p 核性能最为优越，具有以下特点”1 ： ( 1 ) 支持n i s t 所要求的三种不同密钥长度； ( 2 ) 加密和解密功能采用了资源共享； ( 3 ) 密钥调度与加密( 或解密) 并行进行； ( 4 ) 在有限的电路面积下具有很高的速度( 吞吐量) ； ( 5 ) 外部接口简单通用。 所以，人们在硬件设计的时候大多将g m u 大学的i p 核作为参考。 另外还有一些公司也推出了各自的a e s 核以供测试，主要有 h e l i o n 技术有限公司、d c r y p t p t e 技术有限公司及o c e a nl o g i c p t y 技术有限公司。这些公司提供的a e s 在性能上与各大学和研 究机构所提供的相似，只是在外部接口有所不同。 目前，国内在a e s 硬件实现方面主要研究r i j n d a e l 算法s 盒、列混合及其逆变换和整个轮变换的优化实现n 3 。在不改变算 法本质的前提下，将算法的代数运算转换成适应硬件平台的形式， 改变数据存放方式使之与硬件存取数据特点相符，从而以较小的 空间代价换取速度上的较大的提高。如文献 8 中主要研究针对电 子密码本( e c b ) 模式，明文分组和密钥都是1 2 8 位的情况下，a e s 加密算法的f p g a 高速实现。采用同步时钟脉冲触发，通过对内部 流水线布局的平衡优化，实现异步时序电路的同步化，并充分利 用器件本身的资源，达到算法的并行快速实现。文献 9 中主要研 搁湮盔堂亟主淦塞 究一种扩展的r i j n d a e l 算法的4 个变换及密钥扩散的设计策略， 重点研究了列混合变换及其逆变换的设计；在此基础上，研究了 列混合变换中字节模乘运算的实现算法，根据这种扩展算法加密 轮的4 个变换的特征，提出了两种快速实现方案，并在d s p 平台 实现了该扩展算法。 1 2 3r i j n d a e l 算法硬件实现存在的问题 就硬件实现方面而言，r i j n d a e l 算法的加密与解密的动作， 仅有部分能使用相同的电路来完成。 解密过程与加密相比，它要占用较多的代码和周期，几乎不 适于在资源限制较多的装置上实现( 尽管如此，与其他密码相比， 解密过程甚至也是非常快的) 。 1 3 r i j n d a e l 算法硬件优化实现方案 总的来说，算法的硬件优化设计可以从两个方面入手。一方 面是对算法本身的优化，即在不降低算法安全性的基础上，针对 每一轮变换中的四层变换进行变型，使得算法更适合于硬件实现： 另一方面是从硬件实现的电路结构及加解密运算的实现技巧上 进行优化，以提高算法的效能和速度。 算法的优化主要考虑解决r i j n d a e l 原型算法的加密与解密 不一致的问题，通过对原算法解密过程的修改，使得加密与解密 的电路结构相近，从而提高硬件资源的利用率及解密速度。 一个加密算法的硬件实现可以有多种电路结构，常用的有以 下几种。 ( 1 ) 重复环路结构。 这种结构是将分组加密算法许多迭代轮中的一轮用组合逻辑 或者查表法在一个时钟周期里实现，如图1 1 。这种结构是将输入 的数据通过多路器送入电路中的寄存器，并且存放起来，在接下 来的一个时钟周期里完成加解密运算，如果迭代轮数满足了要 求，则结果输出，否则再送入多路器，在下一个时钟周期里再迭 il1寓i 斑le 二 f 冒哥 水线 圈1 3 部分流水线结构 搁淫太堂亟诠塞 r i j n d a e l 算法本身设计得适合在专用硬件上实现，因此，硬 件实现电路结构的优化可以根据应用的具体性能要求，在面积与 速度之间进行选择，本文在面积和速度之间进行折衷考虑，采用 带有子流水线的部分流水线结构。算法的实现技巧方面主要包括： 字节变换时通过s 盒的预先构造，大大加快计算速度；轮变换的 高效实现等。 1 4 本论文的主要内容 本文在分析了r i j n d a e l 算法的基础上，设计并验证了变型的 r i j n d a e l 算法的硬件优化实现。具体解决的问题包括：列混合运 算在硬件实现中的变型及优化；等效解密算法的优化实现；密钥 生成与加解密运算的硬件并行实现；算法的部分流水线结构的优 化实现。 本论文首先在引言部分论述了项目的立项背景，并由此阐述 了r i j n d a e l 算法硬件优化实现的意义和可行的设计方案。第2 章 主要对r i j n d a e l 算法的数学基础及算法的加解密过程进行了说 明。第3 章重点讨论为了使算法更好地用硬件实现而进行的两个 变型。第4 章首先介绍了算法实现的硬件选择、f p g a 的电路结构 特点及e d a 设计方法，然后结合第3 章中提出的变型算法，首先 提出具体的加解密的硬件实现整体电路结构，然后讨论轮变换中 的四层变换、控制模块、密钥扩展及输入输出模块的优化设计方 法及各个模块的实现电路结构。第5 章主要介绍系统的v h d l 实 现及仿真。第6 章主要介绍了r i j n d a e l 算法加密芯片在射频i c 卡等效实现金融卡规范中的应用。 溜湮盔堂亟主丝毫 2 r i j n d a e l 算法 2 1 r i j n d a e i 算法的数学基础 r i j n d a e t 中的某些操作是在字节级上定义的，字节表示有限 域g f ( 2 8 ) 中的元素，一个字节中有8 位。其它操作都根据4 字 节字定义。 2 1 1 字节运算 由b t b 。b 。b 。b 。b 。b 。b 。构成的字节可以用有限域g f ( 2 8 ) 上的多项式 6 7 x7 + 6 6 x 6 + 以z5 + b 4 x 4 + 6 ，x 3 + 6 2 x 2 + b l 茁+ b o 来表示。所有这些多项式 的集合记为s 。 在多项式表示中，g f ( 2 8 ) 上的两个元素的和仍然是一个次数 不超过7 的多项式，其系数是原来两个元素对应系数的模2 加( 比 特异或) 。g f ( 2 8 ) 上的两个元素的乘积是这两个多项式模m ( x ) 的 积。其中m ( x ) 是g f ( 2 ) 上的一个8 次不可约多项式， r e ( x ) = x 8 + x 4 + x 3 + x + l ，m ( x ) 的十六进制表示为“l l b ”，二进制表 示为9 比特1 0 0 0 1 1 0 1 1 川。 2 1 2 四字节字运算 四个字节的向量可以表示为系数在g f ( 2 8 ) 上的次数小于4 的 多项式。多项式的加法就是4 字节向量的逐比特异或。两个多项 式的乘法是这两个多项式模j i i ( x ) 的积，m ( x ) = x 4 + 1 ，这样使得次 数小于4 的多项式的乘积仍然是一个次数小于4 的多项式i l l | 。 2 2 r i j n d a e l 算法描述 r i j n d a e l 是一个迭代型分组密码，其分组长度和密钥长度都 可变，各自可以独立地指定为1 2 8 比特、1 9 2 比特、2 5 6 比特。虽 然r i j n d a e l 与d e s 同样是使用f 移位j 、替换j 、异或运 算j 、 f 乘法运算j 的组合来作加解密的工作，但与d e s 密码系 塑湮盍堂亟主途塞 统比较，仍有下面两项特点“： ( 1 ) 结构不同于d e s 所使用的f e is t e l 结构，r i j n d a e l 采用s q u a r e 架构。在每轮( r o u n d ) 都对整个状态( b l o c k ) 作 处理。其轮变换是由三个不同的可逆一致变换组成，称之为层， 所谓“一一致变换”是指状态的每个比特都是用类似的方法进行处 理的。不同层的特定选择大部分是建立在宽轨迹策略的应用基础 上的，为实现宽轨迹策略，轮变换三个层中每一层都有它自己的 功能： 线性混合层：确保多轮之上的高度扩散。 非线性层：将具有最优的“最差情形非线性特性”的s 盒 并行使用。 密钥加层：单轮子密钥简单地异或到中间状态上。 而d e s 则是将密钥分成两部分，每一轮只对其中一半作处理， 另一半则只有跟轮处理完之后的密钥k e y 做异或。 ( 2 ) 弹性r i j n d a e l 的加密密钥长度可为1 2 8 、1 9 2 、2 5 6 b i t s ，分别重复运算1 0 、1 2 、1 4 次，而d e s 的密钥长度及重复运 算次数则是固定的。 此外r i j n d a e l 密码还具备下列三项特点： ( 1 ) 抗所有已知的攻击； ( 2 ) 在多个平台上都能快速实现，编码紧凑； ( 3 ) 设计简单。 2 2 1 状态、密钥种子和轮数 r i j n d a e l 的明文分组称为状态，所有的操作都是在状态之问 进行。状态可以用以字节为元素的矩阵阵列图表示，该阵列有4 行，列数记为n 。，n b 等于分组长度除以3 2 。 密钥种子( 密码密钥) 类似的用一个以字节为元素的矩阵阵 列图表示，该阵列有4 行，列数记为n k ，n k 等于分组长度除以3 2 。 图2 1 所示是n b _ 6 的状态和n k = 4 的密钥种子。 塑墨态堂亟主途塞 s 0 0s 0 1s 0 2s 0 3s 0 4s 0 5 s i os i ls 1 2s i 3s s 1 5 s 2 0s 2 1s2 2s2 3$ 2 4$ 2 5 s 3 0s 3 1s 3 2s 船s 3 4 s 3 5 k 。 k o ik 们k 0 3 k l ok 1 1k 12 k 1 3 k 2 0k 2 l k 2 2k 。 k 3 0k 3 。k 3 2k 3 3 图2 1n 。= 6 的状态和n f 4 密钥种子 一个明文分组按s o o s 。s2 0 s a o ；s m s s s ；的顺序影射到状态 阵列中。同理，密钥种子按k o o k k k ；k o l k t 。k 。k ；的顺序影射 到密钥种子阵列中。在最后输出密文分组时，也是按相同的顺序 从状态阵列中取出各字节的。将密文分组看作4 n 。维向量，每一个 分量是一个字节，记为( t o t ，t 。t 。) 。则密文分组的第n 个分 量对应于状态阵列的第( j ，k ) 位置上的元素，其中n = j + 4 k ，0 j 3 。 迭代的轮数记为n r ，n ，与n b 和n k 有关，以下的表2 1 给出了 n r 与n b 和n k 的关系。 2 2 2 轮变换 表2 1 迭代轮数n 。为n 。和n 。的函数 n 。 n b - 4 n h - 6 n b = 8 n k 一41 0 1 21 4 n ：- 6 1 21 2 1 4 n k - 81 41 2 1 4 r i j n d a e l 加密过程中的轮变换由四个不同的变换组成，它们 分别是：字节代替( b y t e s u b ) 、行移位( s h i f t r o w ) 、列混合 ( m i x c o l u m n ) 、加密钥( a d d r o u n d k e y ) 。 轮变换的伪c 代码如下】： 第一轮之前执行a d d r o u n d k e y ( s t a t e ，r o u n d k e y ) r o u n d ( s t a t e ，r o u n d k e y ) ( b y t e s u b ( s t a t e ) ： s h i f t r o w ( s t a t e ) ： m i x c o l u i n f l ( s t a t e ) ： a d d r o u n d k e y ( s t a t e ，r o u n d k e y ) ： ) 加密算法的最后一个轮回稍有不同。它由以下代码定义： f i n a l r o u n d ( s t a t e ，r o u n d k e y ) b y t e s u b ( s t a t e ) ： s h i f t r o w ( s t a t e ) ： a d d r o u n d k e y ( s t a t e ，r o u n d k e y ) ： 在以上的伪c 代码记法中，“函数”r o u n d 、f i n a l r o u n d 、 b y t e s u b 、s h i f t r o w 、m i x c o l u m n 、a d d r o u n d k e y 都是指针 s t a t e ，r o u n d k e y 所指向的阵列上进行运算。b y t e s u b 变换是非线 性字节交换，各自作用于每个s t a t e 字节上。在s h i f t r o w 中， s t a t e 的行按不同的偏移量循环移位。在m i x c o l u m n 中，将 s t a t e 的列视为g f ( 2 8 ) 多项式，然后乘以固定多项式c ( x ) 并 模除x 4 + 1 ，其中c ( x ) = 0 3 x 3 + 0 1 x 2 + o l x + 0 2 。 这个多项式与x 4 + 1 互质，因此是可逆的。下面就轮变换中的 四个不同的变换分别进行详细介绍“。 1 字节代替变换( b y t e s u b ) 字节代替变换是将状态阵列的每个字节做相同的变换，该变 换由以下两个变换所合成： ( 1 ) 首先将字节看作g f ( 2 8 ) 上的元素，映射到自己的乘法逆； 0 字节映射到它自身。 ( 2 ) 其次，将字节做如下的( g f ( 2 ) 上的：可逆的) 仿射变 换： 湘霍盔主亟主丝奎 + 如图2 2 所示，以上两个子变换合成的实现，我们利用s 盒 ( s - b o x ) 对状态中的每个字节做转换。即将字节代替变换 b y t e s u b ( ) 对各种可能字节的变换结果排成一个表，如表2 2 所 示，该表称为r i j n d a e l 的字节代替表或s 盒。s 盒是可逆的，是 一个1 6 1 6 包含了2 5 6 个8 - b i t 数值的表格；查询时我们将每 个字节的左边4 个h i t 拿来当做行，右边4 个b i t 当做列的索 引，查出所对应的数值。如果状态中的一1 个字节为x y ，则s 盒中 的第x 行第y 列的字节就是b y t e s u b ( ) 的输出。如表2 2 所示， 假设s n ：5 3 ，则b y t e s u b ( ) 的输出为s 盒中第5 行第3 列的字节 e d 。 s - b o x 中的对应关系是由以上介绍的g f ( 2 8 ) 上的交换而来， 目的是为了防止一些已知的密码破解方式。由于这些值都是固定 的，做成表格的形式直接查表能增快系统效能。 图2 2 字节代替变换 峁五却期期岛|蕞新 ；l；0 o o l ；o o o i l l l o o 0 j l l i o o o i i l l o o 0 l l l l l o o l l i i l o o ll，o o l ll l o o 0 | f h扎捣凡雎儿妈 涠湮态堂亟主诠塞 表2 2r i j n d a e l 的s 盒一字节x y 的代替值 2 行移位变换s h i f t r o w ( ) 行移位变换是将状态阵列的各行进行循环移位，不同状态行 的位移量不同。第0 行不移动，第一行循环左移c 。个字节，第二 行循环左移c 。个字节，第三行循环左移c 。个字节。位移量( c - 、 c 。、c 3 ) 的选取与n 。有关，当n 。= 4 或6 时一般取c 。、c z 、c 。) = ( 1 ， 2 ，3 ) 。如图2 3 所示。 图2 3 行移位变换 3 列混合变换m i x c o l u m n ( ) 列混合变换是利用矩阵乘法来做位元转换，将状态阵列的每 捆埋丕堂亟主迨塞 - - y , j 视为系数在g f ( 2 8 ) 上、次数小于4 的多项式，被同一个固定 的多项式c ( x ) 进行模x 4 + 1 乘法。当然要求c ( x ) 是模x 4 + 1 可逆的 多项式，否贝j y , j 混合变换就是不可逆的，因而会使不同的明文分 组具有相同的对应密文分组。r i j n d a e l 设计者给出的c ( x ) 为( 系 数用1 6 进制数表示) ： c ( x ) = 0 3 x 3 + 0 1 z 2 + 0 1 x + 0 2 c ( x ) 与x 4 十1 互素，因此是模x 4 + 1 可逆的。列混合运算可以表 示为g f ( 2 8 ) 上的可逆线性变换： 0 20 3 0 10 2 0 10 1 0 3m 0 l0 1 0 3 0 1 0 2 0 3 0 l0 2 跏黾l 啦 嘶s l ，1 函2 是，0 & 1 鼬 瓠os 3 ，i 哂鞋t 如瞄s s i ts bs 黾 嘞岛嘞呸 岛黯- 跻鞋， s 主j2 ( 2 ) o ( 3 s 1 ，) 0 嘶。甄， s i 。j = 嘶0 ( 2 s t ，) ( 3 s z j ) os a ， ，j2 05 1 ，o ( 2 ，) 0 ( 3 s 3 ，1 ) ，= ( 3 s o j ) 0 5 i ，o 觐，0 ( 2 s 3 , 1 ) 这个运算需要做g f ( 2 8 ) 上的乘法，但由于所乘的因子是三个 固定的元素0 2 0 3 0 1 ，所以这些乘法运算仍然是比较简单 的( 注意到乘法运算所使用的模多项式为r e ( x ) = x s + x 4 + + x + 1 ) 。 设一个字节为( b ，b 。b 。b 。b 。b 。b 。b 。) ，则 ( b ，b 6 b 5 b a b 。b ：b ，b 。) 0 1 = ( b 如。b 。b 。b 。b 2 b 。b 。) ； ( b ，b 6 b s b 4 b 。b z b 。b 。) 0 2 = ( b 。b s b 。b 。b 。b ，b 。0 ) + ( 0 0 0 b ，b ，o b ，b ，) ； ( b t b e b s b t b a b t b b 。) 0 3 = ( b t b s b s b 。b 。b 。b ，b o ) o1 + ( b ，b 。b 。b 。b 。b 。 b , b 。) 0 2 。 因此，在加密过程中c ( x ) 系数0 l 、0 2 、 0 3 的设 计k k m i x c o l u m n0 只需要用移位及异或就能实现，增加了加密时的 = 词d 捌 效能。经过m i x c o l u m n 0 之后，每个元素都被充分的“混合”，会 受到同一行中的其它元素影响。所以在m i x c o l u m n 与s h i f t r o w 的 搭配一f ，能确保经过几个轮变换之后，输出的任何一个b y t e 都会 与输入的每个b y t e 有关系。 4 加密钥a d d r o u n d k e y ( ) 如图2 4 所示轮密钥加法变换是简单地将单轮子密钥阵列按 位异或到一个状态上。轮密钥通过密钥调度从加密密钥( c i p h e r k e y ) 得到。轮密钥长度( 四字节字数) 等于n b 。 2 2 3 密钥调度 图2 4 轮密钥加法变换 轮密钥通过密钥调度从加密密钥获得，密钥调度有两个组成 部分：密钥扩展( k e ye x p a n s i o n ) 和轮密钥选择( r o u n dk e y s e l e c t i o n ) 。其基本原理如下： 加密密钥的长度为4 n b ( n r + 1 ) 字节( 例如，分组长度等于1 2 8 位，1 0 次轮回，那么就需要1 4 0 8 个轮密钥位) ； 将密码密钥扩展成一个扩展密钥； 轮密钥是按下述方式从扩展密钥中取出的：第一个轮密钥 由最前面的n 。个字组成，第二个轮密钥由接下来的n b 个字组成， 如此继续下去。 i 密钥扩展 r i j n d a e l 的4 n n ( n r + 1 ) 字节加密密钥需要用4 n k 字节密钥种子 经密钥扩展算法得到。将密钥种子阵列的每一列称为一个字，则 密钥种子共有n k 个字，要将其扩展为n 。( n r + 1 ) 个字的加密密钥， 1 4 涠湮盔堂亟土迨塞 其中前n k 个字的加密密钥就是密钥种子阵列，后面的字是根据前 面的字递归定义的。扩展算法有针对n k 4 6 和针对n k ) 6 的两个版 本。 针对n 。6 ，扩展算法为 k e y e x p a n s i o n ( b y t ek e y 4 * n k w o r dw n b * ( n r + 1 ) ) 将加密密钥种子加入 f o r ( i = 0 ：i n k ：i + + ) we i = ( k e y 4 i ，k e y 4 i + i ，k e y 4 i + 2 ，k e y 4 i + 3 ) ： 计算剩下的w o r d f o r ( i = n k ：i 6 ，扩展算法为 k e y e x p a n s i o n ( b y t ek e y 4 * n k w o r dw n b * ( n r + 1 ) ) 将加密密钥种子加入 f o r ( i = 0 ；i n k ：i + + ) w i = ( k e y 4 i ，k e y 4 i + 1 ，k e y 4 i + 2 ，k e y 4 i + 3 ) 计算剩下的w o r d f o r ( i = n k ；i 6 与n 。4 6 的密钥调度方案的差别在于，对是n k 的整数倍 的i 一4 ，异或之前对w i 一1 进行了s u b b y t e 变换。 2 。轮密钥选择 如图2 6 所示轮密钥i 是由轮密钥缓冲字w n b * i 到 w n b 木( i + 1 ) 给出的。 l i r o u n dk e ydr o u n dk e y i 图2 6n b = 6 ，n k = 4 密钥扩展与轮密钥选择 2 2 4r i j n d a e l 加密算法 r i j n d a e l 密码的加密过程由以下三个部分组成；一个初始轮 密钥加；n ，一1 轮迭代；一个结尾轮。如图2 7 所示。 用伪c 代码表示为： r ij n d a e l ( s t a t e ，c i p h e r k e y ) k e y e x p a n s i o n ( c i p h e r k e y ，e x p a n d e d k e y ) ： 先做一次a d d r o u n d k e y a d d r o u n d k e y ( s t a t e ，e x p a n d e d k e y ) ： 进行n r 一1 次的轮变换 f o r ( i = l ：i n r ：i + + ) r o u n d ( s t a t e ，e x p a n d e d k e y + n b , i ) ： f i n a l r o u n d ( s t a t e ，e x p a n d e d k e y 十n b * n r ) ： 密钥扩展可以事先进行，如果已经预先执行了密钥扩展，则 r ij n d a e l 加密可以用这一扩展密钥来进行描述： r ij n d a e l ( s t a t e ，e x p a n d e d k e y ) ( 扭湮态堂亟迨塞 一 a d d r o u n d k e y ( s t a t e ，e x p a n d e d k e y ) ： f o r ( i = 1 ：i oii 一一) i _ r o u n d ( s t a t e ，l _ e x p a n d e d k e y + n b * i ) ： 拥翌态堂亟迨塞 i _ f i n a l r o u n d ( s t a t e ，i _ e x p a n d e d k e y ) ； 逆密钥扩展的伪c 代码描述如下： i _ k e y e x p a n s i o n ( c i p h e r k e y ，i _ e x p a n d e d k e y ) k e y e x p a n s i o n ( c i p h e r k e y ，l _ e x p a n d e d k e y ) f o r ( i = l ：i o ：i 一一) i _ r o u n d ( s t a t e ，l _ e x p a n d e d k e y + n b * i ) ： l _ f i n a l r o u n d ( s t a t e ，ig x p a n d e d k e y ) ： r i j n d a e l 密码的解密算法为顺序完成以下操作：初始的密钥 加；( n r 1 ) 轮迭代；一个结尾轮。 逆密钥扩展的伪c 代码描述如下： l _ k e y e x p a n si o n ( c i p h e r k e y ，l _ g x p a n d e d k e y ) k e y e x p a n s i o n ( c i p h e r k e y ，l _ e x p a n d e d k e y ) f o r ( i = l ：i n r ：i + + ) i n v m i x c o l u r n n ( i _ g x p a n d e d k e y 十n b * i ) ： ) 设加密算法的初始密钥加、第一轮、第二轮、第n r 轮的 字密钥依次为： k ( 0 ) ，k ( 1 ) ，k ( 2 ) ，k ( n r 一1 ) ，k ( n r ) 则解密算法的初始密钥加、第一轮、第二轮、第n r 轮的 字密钥依次为： k ( n r ) ，i n v m i x c o l u m n ( k ( n r i ) ) ，i n v m i x c o l u m n ( k ( n r 一2 ) ) ， i n v m i x c o l u n m ( k ( 1 ) ) ，k ( 0 ) 逆密钥扩展中除第一轮和最后一轮之外，所有轮密钥都要进 行i n v m i x c o l u m n 变换。因此解密算法的密钥扩展比加密算法的密 钥扩展要慢。 综上所述，等价的r i j n d a e l 密码的解密算法与加密算法的大 的计算网络都相同，只是将各计算部件换为对应的逆部件。 湘型盔堂亟逾塞 3 2 列混合变换的优化 由第2 章的介绍可知，列混合变换是在g f ( 2 8 ) 上乘0 3 、0 1 、 0 2 ，利用x t i m e 0 就可以快速的完成。而解密过程中的逆列混 合变换相对予加密过程中的列混合变换要复杂得多，它需要在 g f ( 2 8 ) 上乘0 9 、0 e 、0 b 、0 d 。这些运算比较复杂，直接 影响着解密的速度。 为此，提出一种较好的c ( x ) = d ( x ) 的算法 1 5 1 ，选取 c ( x ) ：d ( ) ：0 1x3 0 2 t 工2 + 0 1 石+ 0 3 。，它不仅简单而且性质好。这时对应 的列混合矩阵为 0 30 1 0 l0 3 0 20 l 0 10 2 0 20 1 o l0 2 0 30 1 0 10 3 这时不仅解密电路变简单了，且加，解密可以共用更多的电路 或代码，文献 1 5 1 e e 对这样改进的可行性进行了论证，并且进行 了安全性分析，得出了此改进并不影响算法的抗差分能力的结论。 瀣湮盔堂亟途塞 4 r ij n d a e l 算法的f p g a 优化设计 4 1 硬件选择 我们的设计任务是用e d a 设计技术设计r i j n d a e l 算法加密j 苎： 片，完成输入分组长度为1 2 8 比特，密钥长度是1 2 8 比特的 r i j n d a e l 算法的加密与解密的优化实现。 传统硬件数据加密方法主要有两种，一种是基于可编程体系 结构的芯片( 如单片机，d s p ) 采用软件编程的方式实现密码算法； 另外一种是设计专用的硬件逻辑芯片完成加密算法呻3 。对于可编 程体系结构的芯片，拥有丰富的指令集和已固化流水线，可以方 便灵活的进行各种数学运算，但固化流水不能充分利用计算资源， 加密速度较慢。而基于专用逻辑芯片，则可以根据算法自身的特 点设计，算法与运算电路可以得到很好的配合。另外r i j n d a e l 算 法本身没有大量复杂的乘法运算，可以通过查表操作和组合逻辑 实现各种变换的运算部件。因此，我们设计专用的加密硬件逻辑 芯片。 专用的硬件逻辑芯片的设计最简便的方法