14算机安全

14算机安全2008.6学术.技术1引言AES是美国标准技术研究所(NIST)于2000年10月2日宣布的一种保护敏感(无密级的)信息的、公开的、免费的，并且全球通用的分组加密算法，支持128位的分组长度和128、192、256位的密钥长度。利用软件实施加密算法已经成为实时安全系统的重要瓶颈。更为糟糕的是，标准的商品化CPU和DSP无法跟上数据加密算法的计算要求。此外，CPU和DSP需要完成太多的其他任务。基于FPGA高度优化的可编程的硬件安全性解决方案提供了并行处理能力，并且可以达到所要求的加密处理性能基准。本文将以AES算法为例，描述数据加密算法的电路逻辑模型建立方法，分析基于XILINX公司的VIRTEX-IIXC2V1000现场可编程器件(FPGA)AES算法的实现。2算法分析说明2.1AES算法概述AES具有128比特的分组长度，3种可选的密钥长度，即128比特、192比特和256比特。AES是一个迭代型密码；轮数Nr依赖于密钥长度。如果密钥长度为128比特，则Nr＝10；如果密钥长度为192比特，则Nr=12；如果密钥长度为256比特，则Nr＝14。AES算法的输入和输出及密钥都可以看作“0”、“1”序列。若将序列中连续8位看作一个单元，则算法的输入和输出及其密钥又可以视为字节（byte）序列，若将字节序列中连续的４字节看作一个单元，令这个单元为字（word），那么字节序列又可以视为字序列。在AES中，字节序列被映射成一个４行多列的二维矩阵，这个４行多列的矩阵也称为状态，如字节序列映射成二维状态矩阵后有如下状态，如图1所示。图1　状态矩阵由于二维矩阵的行数确定为４行，因此列数就可由字节序列的长度或“0”、“1”序列的长度来确定，令分组和密钥映射的二维矩阵的列数分别为Nb、Nk，由AES对分组和密钥长度规定可知Nb＝４，而Nk可为4、6、或8。在AES中，密钥长度不仅决定了Nk，同时也决定了迭代的轮数Nr，Nk、Nr与密钥长度的具体关系如表1所示。表1　密钥长度与Nk、Nr的关系2.2运算流程AES算法的参数有两个：状态矩阵和初始密钥，其中状态矩阵由字节序列映射得到，而初始密钥则用字（word）序列来表示。确定初始参数后，AES算法的加密过程可以分为轮变换和密钥扩展(KeyExpansion)两部分，AES算法FPGA实现分析唐金艺（海军计算技术研究所，北京100841）摘　要：该文介绍了标准AES算法工作流程，并给出了AES算法的具体FPGA实现设计方案。该方案是基于XILINX公司的VIRTEX-IIXC2V1000芯片提出的。关键词：分组加密算法；硬件实现；AES；XILINX；FPGAAnalysisofAES’sImplementationwithFPGATANGJin-yi(ComputingTechnologyInstituteofNavy,100841,P.R.China)Abstract:ThispaperintroducestheworkflowofAES,andgivesthedesignproposalofAES’simplementationwithFPGA.TheproposalisbasedonVIRTEX-IIXC2V1000chipsofXILINXCO..Keywords:blockencryptionalgorithm;hardwareimplement;AES;XILINX；FPGA152008.6计算机安学术.技术而轮变换又由字节替代（ByteSub）、行位移（ShiftRow）、列混合（MixColumn）和圈密钥加法（AddRoundKey）4个模块组成。在伪C代码记法中，有：Round(State,RoundKey){ByteSub(State);ShiftRow(State);MixColumn(State);AddRoundKey(State,RoundKey)}密码的结尾圈稍微有点不同，它是如下定义的：FinalRound(State,RoundKey){ByteSub(State);ShiftRow(State);AddRoundKey(State,RoundKey)}在这一记法中，“函数”（Round,ByteSub,ShiftRow,…）在指针（State,RoundKey）所指向的阵列上运算。可以看出，结尾圈等价于将列混合（MixColumn）这一步去掉的圈。(1)字节代替（ByteSub）字节代替（ByteSub）变换是一个非线性的字节代替，它在每个状态字上独立地进行运算。代替表（或Ｓ-盒）是可逆的，且是由两个变换的合成而构造出来的。首先在有限域GF(28)中取乘法逆。其次再经过定义的（GF(28)上的）仿射变换作用得到一个16×16的矩阵，其中行号与列号都用十六进制数字表示，行标号为Ｘ、列标号为Ｙ的项是∏s（ＸＹ）。如图2描述ByteSub变换结果。图2　字节代替(2)行位移（ShiftRow）ShiftRow函数对状态矩阵中的行独立进行循环移位，位移量取决于所在的行数r，第０行不移位，第一行循环移位１个字节，第二行循环移位２个字节，第三行循环移位３个字节。状态矩阵经ShiftRow函数作用，其效果可如图3所示。图3行移位(3)列混合（MixColumn）MixColumn函数对状态矩阵的列独立进行变换，经MixColumn函数变换后每列中的字节元素相当于变换前该列字节元素的一个线性组合，如图4所示效果。图4　列混合(4)圈密钥加法（AddRoundKey）AddRoundKey函数主要实现状态数据与子密钥的结合，即进行异或运算，效果如5图所示图5　圈密钥加法(5)密钥扩展(KeyExpansion)KeyExpansion函数主要的作用是进行密钥扩展，初始密钥和扩展后的整个密钥表可以看作是一个字（word）序列。密钥扩展是针对字进行的，为此又引入了两个对字进行处理的函数：字替代（subword）和字旋转（rotword）。字旋转将字的4个字节循环右移一个单位，如字（W[0],W[1]，W[2],W[3]）经过旋转后得到字(W[3],W[0],W[1],W[2])；字替代则对字中的4个字节分别进行字节替代。除字替代和字旋转两个函数外，在密钥扩展中还引入了一个轮常数Rcon(i/Nk)=(2i-1,00,00,00)，其中I表示扩展的次数，“00”表示十六进制的数，由此密钥扩展过各的伪Ｃ代码如下所示：KeyExpansion(byteKey[4*Nk],wordW[Nb*(Nr+1)]){for(i=0;iNk;i++)W[i]=Key[4*i],Key[4*i+1],Key[4*i+2],Key[4*i+3]);for(i=Nk;iNb*(Nr+1);i++){temp=W[i-1];if(i%Nk==0)temp=subword(rotword(temp))xorRcon[i/Nk];elseif((Nk6)&&(i%Nk==4))16算机安全2008.6学术.技术temp=subword(temp);W[i]=W[i-Nk]xortemp;i=i+1;}}3AES算法FPGA实现分析3.1　VIRTEX-IIXC2V1000优势(1)性能：利用Virtex-II(-4)FPGA实现的AES算法的基准测试表明比之前版本的FPGA实现的时钟要高出30％左右；(2)更多更大更宽的BlockRAM：32位宽的数据缓冲在Virtex-II块RAM中实施效率更高。例如，一个512x32缓冲器只需要一个Virtex-II块RAM就可以实现；(3)增强的CLB-MUXF7和MUXF8基本单元允许4个逻辑片组合快速实现多达8个输入宽度的任何逻辑功能。加密算法的逻辑功能通常输入比较宽，因此这可以使逻辑级更少并且使关键路径速度更快。(4)数字时钟管理器（DCM）：真正时钟频率合成允许加密数据块时钟可以调整到与最差PAR（布局布线）情况下的时序相匹配，从而优化加密吞吐能力。(5)设计实施更容易：Virtex-II器件的速度意味着实施LogiCORE66-MHzPCI总线逻辑时不需要PARGuide文件。3.2　FPGA外部接口设计FPGA的外部接口是由DSP/CPU来控制的，数据大多是以查询方式送入FPGA，因此对数据流控制的设计至关重要。FPGA的外部接口时钟也是由所在总线的速率决定的，而算法核的时钟是由最终设计出来算法的单步穿透逻辑层数所决定，两者往往会有很大的差异。解决这一问题的最好手段就是引入一个FIFO来进行不同时钟域的数据分割。XILINX提供的EDA软件ISE9.0之上版本免费提供了功能强大FIFO的IPCORE，该FIFO库不仅支持两端工作在不同的时钟之下，而且还支持两端数据宽度不同，大大降低了设计复杂度。针对分组算法AES的特性，可以在算法核的输入输出端各加一个FIFO单元来完成数据的处理。3.3　算法核电路设计采用FPGA方法实现的系统一般都可分为数据处理部分和逻辑控制部分，高级加密标准在整体系统上也不例外，下面就这两个部分进行设计。加密单元系统结构如图6所示。图6　加密单元系统结构3.3.1　数据处理部分设计一个密码算法的数据处理部分一般要完成如下工作：(1)数据的载入和输出以及中间状态结果的存储；(2)数据的加解密处理；(3)密钥调度。为了完成这3点工作，将密码算法的数据处理部分设计成3个大的模块：外部接口模块、加解密模块和密钥调度模块。一个完整的密钥调度模块要完成初始密钥设置、密钥扩展和轮子密钥存储，据此可以将密钥调度模块又可以细分为初始密钥设置、密钥扩展和轮子密钥存储3个比较独立的子模块。对于外部接口模块也可以分为比较独立的输入接口子模块和输出接口子模块，而加解密模块要实现的功能比较完整，所以不再细分。3.3.2　逻辑控制部分设计在密码算法设计中，各模块的相互关系比较清楚，因此逻辑控制部分的设计也比较简单，主要的工作是完成数据处理部分各模块的逻辑控制信号的传递和启动。这一部分用单独的一个控制模块就可以实现。3.3.3　算法核各模块设计分析(1)字节代替（ByteSub）字节代替可以有效利用FPGA上自带的BlockRAM资源设计成并行的16个独立的查找表单元。这里需要说明的是，只有逻辑前后分别具备寄存器才会被综合成BlockRAM，否则将会浪费大量的LUT资源。(2)行位移（ShiftRow）FPGA去做这样的移位操作就等价于去进行走线的调整，不占用到丝毫的逻辑穿透深度，比软件实现要高效了许多。(3)列混合（MixColumn）（下转20页）20算机安全2008.6学术.技术该步用到了一些算术的加法，需要进位，因此会增加逻辑深度。可以单独设计一个超前进位加法模块来提高效率，降低穿透的逻辑深度。(4)圈密钥加法（AddRoundKey）将2个寄存器进行异或操作。(5)密钥扩展与圈密钥加法将密钥扩展与圈密钥加法做在一个模块中可大量节省时间，进行密钥扩展的时候，没有采用一次性密钥扩展。把一个分组进行全部轮（含明文和初始密钥的异或操作）加密所需的密钥一次性全部计算出来，再保存在块RAM中，这样做的好处是实现方便，过程明晰；但由于存储器资源有限，另外异步操作会带来不可避免的竞争和冒险，不利于全局时钟触发。因此在每一轮运算过程中，同时进行下一轮轮运算密钥的生成较好。也就是第一轮进行明文与初始密钥的异或运算的同时，进行第二轮的密钥生成，以此类推，在分组进行第Ｎ轮运算时，并行计算第Ｎ＋１轮密钥加密所需的密钥。这样就降低了对存储器的需求，减少了毛刺的出现。轮密钥扩展流程图如图7所示。图7　轮密钥扩展流程图4结论下面是针对AES算法在各个环境下实现的速率，如表2所示。显而易见，由FPGA实现的AES算法的数据加密速率是最高的，这是因为DSP和CPU用来完成其他任务的时间太多了，而实际用于加密的系统时钟则是很少的一部分，但FPGA则在每一时钟都是用来处理算法，实现了芯片的专用。表2　各个环境下实现AES算法的速率比较加密算法是信息安全的基础，