基于65nm工艺的Rijndael加密算法ASIC设计

《基于65nm工艺的Rijndael加密算法ASIC设计》由会员分享，可在线阅读，更多相关《基于65nm工艺的Rijndael加密算法ASIC设计（78页珍藏版）》请在装配图网上搜索。

1、湖南大学硕士学位论文 基于65nm工艺的Rijndael加密算法ASIC设计 姓名：宁乃东申请学位级别：硕士 专业：微电子学与固体电子学 指导教师：王岩国20080501硕士学位论文摘要集成电路的发展已经进入了超大规模集成电路设计和SOC(Svstem OnChip)设计阶段。90nm、12英寸的生产线已经进入了规模化生产，而65nm技 术已经成熟，并应用于部分的芯片设计之中。目前，在65nm工艺的技术支持之 下，我国国内某些集成电路公司专用集成电路的单片规模已经可以达到1亿门以 上。芯片的制造技术得益于光刻技术、SOI(Silicon on Insulator)技术、铜互连 等技术的突破。集

2、成电路产业正在从已经达到了的65nm的工艺节点向更深的45nm节点前进。 集成电路产业已经延伸到信息领域的方方面面。随着网络技术，数据存储技术以及数据处理技术的飞速发展，信息社会中的信息安全越来越受到人们的重 视。有关网络通讯过程中个人机密信息以及便携存储设备的机密数据的保密措施 已经成为了一个研究的热点领域。有关加密硬盘、加密路由器等新技术的出现正 在酝酿着一场数字领域技术创新。更重要的是，这些加密措施都无法离开加密芯 片的作用。目前的各类加密芯片中，比较成熟的为基于三重DES(Data Encryption Standard)加密算法的加密芯片，但就算法本身的安全性而言，已经无法抵抗强 大

3、的破解攻击。作为新一代的高级加密标准的Rijndael加密算法，是目前公认的 最为安全的加密算法之一，基于该算法的加密ASIC(Application Specific Integrated Circuit)也成为研究的热点领域之一。针对上面的问题，论文设计出了一种基于混合设计思想的Ri_indael加密 ASIC。所谓混合设计思想是指从集成电路的65nm工艺水平特点以及Rijndael 算法本身特性两方面综合考虑，设计出的一种能够有效改进加密系统性能的设计 方法，是论文的创新点之一。该ASIC采用先进的IBM 65nm工艺，系统的最大 工作频率高达320MHz，数据处理能力可以达到4Gbps

4、一40Gbps。同时，设计中 还包含了65nm工艺条件下的低功耗的设计理念，最大程度的降低了芯片的功耗。 设计中还在部分实现环节上引入了技术上比较成熟的IP内核，使得系统的性能 有了进一步的提高。从整体上看，论文设计实现了一种高速，低功耗，高安全性 的65nm加密ASIC。论文最后还给出了下一步工作的建议，以期进一步完善 Rijndael加密AISC的性能。关键词：65nm工艺；专用集成电路；低功耗；Rijndael加密算法AbstractThe development of the integrated circuit has been in the stage of VLSI and SO

5、CThe 90nm characteristic size and 12 inch 0f the integrated circuit is made on a large scaleToday，65nm technology is growning up，and the technology is used inmuch 0f the designing 0f chipsUsing the technology leVel of 65nm，some of intergrated circuit company in our country can make a chip which cont

6、ains about onehundred million logic gatesThe development of the techn0109y of intergrated citcuit prOfit from the technology of semiconductor such as SOC etcThe intergrated cirtuit infiltrate into every place of information industryAlongwith the development of the technology of communication，data st

7、orage and data processor，the security of informations in the information society is much more regarded by peopleThe field of keeping indiVidual information security and keeping communication security becomes more and more popularThe apprearance of securityhard disk and security router means a new re

8、noVate in digital technologyThe most import thing is that，all the renoVate must run on encrypt chipsAt present，trioDES is one of the most maturity technology of encrypt chipsBut it can not protect informations under the mighty attackRij ndaelis the new advance encrypt standard，that is much more safe

9、 than【IESSo the Rijndael encryptchips are becoming more and more preVailIn order to solve this problem，this paper deals with a Rijndael emcrypt ASIC based on the Mixdesign ideaThe Mix-design means a design method that can inlprove the emcrypt system performanceIt is based on the factor of 65nmtechno

10、logy level and that of Rijndaels characteristicsThe ASIC uses IBM 65nmtechnologyThe system maxmum work frequency is 320MHzThe data throughput can achieve between 4Gbps and 40GbpsIn the design，this paper contains the low power deSign method of 65nm technologyThe method effectiVly reduces system power

11、 consumingThere are some IP cores which are used t0 improVe performance of the sVstemThese IP coreStechnology is Very matureThis paper schieVes a fast orking，low power and high security encrypt ASICIn the last part of this paper，there are some suggestions which used t0 guid the next stage of researc

12、hKey Words：65nm Technology；ASIC；Low Power Design；Rijndael硕士学位论文插图索引图21电子编码簿模式11 图22加密块链模式 12 图23输出反馈模式 12 图24 Rijndael加密算法结构图 13 图25 SBOX替换操作16 图26 Shift Row变换16 图27 Mix Column变换17 图28 Add Roundkey变换17 图29密钥扩展过程19 图210当Nb=6、Nk=4情况下的轮密钥选择 20 图211 Ri_indael直接解密算法结构图 20 图212 Inv Shift Row原理图 22图213 Inv

13、 MixColumn原理图 22 图31高速设计流程图 25 图32低功耗设计流程图 25 图33混合设计思想流程图 27图34 verilog源代码结构图28 图35 Svs scheduler逻辑电路一29 图36 Svs scheduler时序图 30 图37 Data processor逻辑电路3l 图38 Data processor时序图 32 图39 Shift Row逻辑结构图 33 图310 Mix Column的by pass结构 35 图311 Mix Column的逻辑电路 35 图312 Key Expanding中的关键路径 。36图313 Inv Svs sche

14、duler时序图38图314 Inv Data processor逻辑电路 38 图315 Inv Data processor时序图 ： 40 图316普通clockgating模型 43 图317通用IP clockgating模型 43 图41动态可配置密钥管理模块逻辑电路 46基于65nm工艺的刚ndael加密算法AsIc实现图42动态可配置密钥管理模块工作波形 47 图43 Register Array写操作时序 53 图44 Register Array读操作时序 53 图45基于Register Array的SBOX逻辑电路54 图46 Register Array的wrappe

15、r逻辑电路 55 图51系统验证平台结构 59 图52数据处理模块的VCS仿真波形 60 图53加密模式下的的VCS仿真波形61 图54解密模式下的的VCS仿真波形61硕士学位论文附表索引表21 Rijndael与三重DES对比 11 表22不同状态数组长度下的行位移量 16 表41 SBOX映射表 50 表42 Register Array类型表 52 表43 Register Array规格表 52Vm湖南大学 学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究 所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包 含任何其他个人或集体已经发表或撰写的成

16、果作品。对本文的研究做出 重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名： 洳眷日期： 碥年F月3 o日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同 意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许 论文被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存和汇编本学位论文。本学位论文属于1、保密口，在 年解密后适用本授权书。2、不保密团。 (请在以上相应方框内打“”)作者签名： 皆乃番日期：秒万年溯3。日导师签名：钢日

17、期：秒彳年厂月罗日7 U矿硕士学位论文第1章绪论11课题研究背景111集成电路的发展趋势集成电路的发展已经进入了纳米时代。随着工艺水平的不断进步，早期的人 工设计已逐渐的被CAD(Computer Aided Design)所取代，目前已经进入了超大 规模集成电路设计和SOC设计阶段。在集成电路设计技术中最重要的设计方法、 EDA(Electronic Design Automatic)工具及IP core三个方面都有新的发展：半制 定的正向设计已经成为集成电路设计的主流技术，而全制定一般应用在核心处理 器等对设计要求非常高的设计上，而EDA工具基本掌握在世界专业的EDA公司手 中，如Cade

18、nce、Synopsys等；世界IP产业同样初具规模，如英国的ARM以及美 国的DeSOC等。目前，90nm12英寸的生产线已经进入了规模化生产，而65nm技术已经成熟， 并应用于部分的芯片设计之中，采用65nm技术的产品已经出产。目前，在65nm 工艺的技术支持之下，我国国内某些集成电路公司专用集成电路(ASIC)的单 片规模已经可以达到1亿门以上。芯片的制造技术得益于光刻技术、SOI(Silicon on Insulator)技术、铜互连等技术的突破，目前已经达到了65nm的工艺节点正 在向更深的节点前进。在封装技术中，封装形式的主流已经转变，新型封装技术 的应用正在增多，以SIP(Sys

19、tem in Package)封装为代表的下一代封装形式已 经出现，封装与组装的界限已经变得模糊。伴随着软硬件协同设计技术、可测性设计技术等新型设计方法在EDA工具中 的体现，EDA工具将在集成电路设计领域得到更广泛的使用。EDA工具的应用将 进一步缩短电路生产周期，提高设计的可行性和可靠性，从而成为集成电路设计 必不可少的技术手段。据专家的分析，今后的5。10年集成电路仍将大体遵循摩尔定律所揭示的规律 发展，而集成电路设计则是体现这一定律至关重要的一个环节。目前主流的集成 电路设计尺寸已经达到了90nm，高端设计已经达到了65nm，芯片的集成度达到 了1矿一10数量级。根据国际集成电路厂商的

20、预测，2010年将实现45nm工艺、2013 年将实现32nm工艺，到2016年将实现22nm工艺条件下集成电路的量产。面向特征尺寸小于35nm的CMOS期间结构和工艺技术将会进入实用化水平。 这将包括SOI技术、双栅结构技术、应变硅基础、金属栅电极技术、高介电常数 (Hig-hK)栅介质技术、超浅结形成基础、低介电常数介质材料(LowK)技基于65nm工艺的刚ndaeI加密算法AsIc实现术以及铜互连技术的完善和化学机械平坦化(CMP，Chemical Mechanical Planarization)等。在各类技术的强力支持下，集成电路产业将继续向尺寸更小， 集成度更高的方向发展。112加

21、密算法的发展趋势随着网络技术，数据存储技术以及数据处理技术的飞速发展，信息社会中的 信息安全越来越受到人们的重视。有关网络通讯过程中个人机密信息以及便携存 储设备的机密数据已经成为了一个研究的热点领域。有关加密硬盘、加密路由器 等新技术的出现正在酝酿着一场数字领域的新的技术革命。更重要的是，这些加 密措施都无法离开加密芯片的作用。加密芯片在信息安全领域发挥了重要的作用。从人们熟悉的各类证件卡如社 保卡等小型IC，到大容量的高速数据硬盘再到多级多平面交换机等个大型网络 设备都可以找到加密芯片的身影。加密芯片主要可以分为两大类：一类是专用的， 一类是通用的。专用的加密芯片用于专门的实现某种算法或协

22、议的加密和解密芯 片；另一种则是通用的安全芯片它采用CPu作为主控制器，而其它模块如本文 实现的Rijndael算法和随机数产生模块等作为外围设备通过系统总线与主控制 器相连。本文设计的加密ASIC是一类专用的加密芯片，主要用于对数据安全十 分敏感的交换网络以及硬盘存取领域。在保证数据的信息安全方面，目前的国际标准是Rijndael加密算法。Rijndael 加密算法是由比利时的两位密码专家：国际质子中心的Joan Daemen博士以及来 自Katholieke大学电子工程系的博士后研究员ncent Rijnmen，发明的一种迭 代的，密钥加密分组的加密算法。该算法从最终的五个候选算法中脱颖而

23、出，被 NIST(美国国家标准与技术局)认定为新一代的高级公开的联邦信息处理标准 (FIPSFederal In formationP rocessingS tandard)，用于美国政府组织保护敏感信 息的一种特殊的加密算法。2000年10月2日，美国商务部部长NormanY Mineta 宣布，经过三年来世界著名密码专家之间的竞争，Rijndael数据加密算法最终获 胜。为此而在全球范围内角逐了数年的激烈竞争宣告结束。这一新加密标准的问 世将取代DES数据加密标准成为21世纪保护国家敏感信息的高级算法。Ri_indael具有安全，高效，方便，灵活的特点，这使它成为了AES(Advanced

24、 Encryption Standard)的合适选择。特别指出的是，Rijndael在不同的硬件以及软 件环境下可以表现出始终如一的良好性能，并且Rijndael对于内存的要求很低， 这使得Rijndael拥有更为广阔的使用空间。从其硬件结构上看，不但具有较高的 安全性而且充分体现AES算法的灵活性和可配置性，使得其既可以作为单独的 AES密码算法芯片又可以作为通用安全芯片的外围设备IP模块。例如目前的交换网络，Rijndael己成为网络路由器对数据加密的主要算法。2硕士学位论文加密是建立安全的数据网络的关键，而在日益强调安全性的今天更是如此。IPSec 在VPN中用于网络安全性，它同时需要控

25、制通道和数据通道支持。控制平面和 关键的交换可以利用运行在RISC引擎(如PowerPC处理器)上的软件来实现。但 数据通道需要以Gbps线速度进行处理的Rijndael和三重DES加密解密方案， 而这是软件所不可能达到的。因此用硬件快速实现Rijndael加密算法，对开发安 全路由器和安全加密卡有重要的意义。将Ri_indael固化于硬件之中主要出于两个原因：一是随着加密算法越来越复 杂，软件的实现速度越来越慢，对于一般的块加密算法，软件加密速度不超过100Mbps；二是算法固化于硬件之中，使得较软件更不容易修改大大提高了系统 的安全性。目前，将Rijndael嵌入硬件主要有两种方法，一种为

26、ASIC实现，一 种为FPGA实现。Verbauwhede、Schaumont和Kuo于2003年设计了第一块实现 AES算法的ASIC。相比之下，FPGA的实现要更加的容易，也更便宜，目前， 不少Rijndael的FPGA实现中，设计速度从294MBps到414MBps不等。为此， 如何快速的实现Rijndael已经成为当前信息安全领域研究的热点问题。12国内外研究现状自从NIST(美国国家标准与技术局)确认RijndaeI作为新一代加密标准之后， 国内外对该加密算法的研究便迅速展开了，Rijndael是一个算法公开的加密标 准，它有着易实现，难破解，安全性高的特点。目前国内外出现了很多基于

27、Rijndael加密算法的商用加密芯片，随着算法的不 断改进与完善，其芯片的处理性能也在不断的提高【11。但其中的部分Rijndael算 法硬件的设计都只实现了FIPS197规范，缺乏可配置性，不太适合作为通用安全 芯片的外设模块I引。例如有的设计只有加密单元没有解密单元，有的只支持某一 种工作模式。因此，有关商用ASIC的设计仍然有很大的发展空间。在商业市场上，有关Rijndael的加密芯片需求量也在不断的增加，如BenQ的 CPl365硬盘就采用了最先进的Rijndael加密芯片。可见，随着信息技术的发展， 有关信息安全的技术也在逐步的成为热点问题，而投入到商用加密领域的研发人 员也越来越

28、多。在目前的多种设计当中，AES的基本硬件结构都是基于流水线的，勿庸置疑 流水线结构可以提高芯片的时钟频率，从而使数据吞吐量得到大幅提高，但是基 于流水线的设计没有充分考虑AES的工作模式以及有关ASIC具体的性能。比如 说，Rijndael算法本身包含反馈工作模式以及非反馈工作模式，但基于流水线的 设计只能实现非反馈工作模式的Rijndael，在反馈模式中流水线结构不但不能改 善电路的性能，而且还会增大芯片的面积及功耗，增加设计成本。为此，本文在 设计时，充分考虑了这一点，采用了非完全流水线的混合设计思想，有效地改进3基于65nm工艺的剐ndael加密算法AsIc实现了芯片的整体性能。 自从

29、Verbauwhede、Schaumont和Kuo予2003年设计了第一块实现Rijndael算法的ASIC以来，基于Rijndael的商用芯片不断涌现，性能也在不断提高。数据吞吐 率从几百Mbps至上Gbps不等【31。值得比较的是，还有相当一部分设计采用了 FPGA实现，其中部分数据吞吐率可达15Gbps(基于virtexII 2V10004)。而本 文在设计上采用了先进的65nm半导体工艺，使系统工作时钟在320MHz以上，数 据吞吐率高达4Gbps。13论文的选题意义当今的时代是一个信息化的时代，互联网技术的飞速发展以及个人便携存储 技术的不断进步使得个人信息不断的在网络或存储介质上流

30、通。而最近频繁出现 的各类个人机密信息在移动存储设备或网络上的泄漏事件使得人们对信息传输 的安全性越来越重视。有关信息流通的保密技术已经不再是国家机关或政府机构 的专用，它将随着信息化的到来逐渐深入到生活的方方面面。目前，带有加密功 能的路由器以及加密硬盘正逐渐的出现在消费类电子市场上，而这些带有加密功 能的电子设备多数都采用内置的加密芯片实现，而且相当一部分的加密芯片仍然 采用传统的三重DES技术，如目前市场上出现的BenQ部分型号加密硬盘。加密技术的使用已经不再是金融机构以及政府机关的专用，加密技术越来越贴近日常的生活之中，这使得加密技术获得了前所未有的关注度。另一方面，随 着处理器速度的

31、不断提升以及互联网的普及，原有的三重DES已经不具备原有 的安全性，以目前的处理器运行速度，破解三重DES加密算法并不困难，三重 DES已经无法胜任当今信息化的安全要求。这样一来，信息领域内一场新的破 解与反破解之争正在展开。人们已经寻找出了一个替代三重DES加密算法的新 加密标准，称之为AES即高级加密标准，即本文所说的Rijnsael加密算法。至 此，伴随着新加密算法的颁布，如何使用硬件更快速更稳定更安全的实现新加密 标准成为了业界的热点问题。根据推算，Rijndael算法至少还能保证10年的安 全期，其间必然会不断地有更高速更稳定的加密芯片诞生。本文正是基于这样的一个出发点，考虑如何实现

32、基于Rijndael加密算法的高性能加密ASIC。 作为新一代的加密标准，Rijndael不论其安全性还是其硬件实现性都远远优于三重DES加密算法。而且有关Ri_indael加密算法的快速安全硬件实现也成为 了信息安全领域于集成电路领域的关键交叉点。目前，部分国外集成电路生产商 已经拥有了自己的Rijndael加密芯片，但在市场上该类IC种类不多并且性能参 差不齐。本文从65nm工艺作为切入点，设计一款基于Rijndael加密算法的加密ASIC。4硕士学位论文14本文主要工作及章节安排随着集成电路工艺水平的不断进步以及IP core技术的不断完善，在逻辑设计 优化能力有限的情况下，提高集成电路

33、的工艺水平可以在很大程度上提高芯片的 性能，但随着深亚微米带来的各种效应使得设计上必须综合考虑各种可能的不稳 定因素，并且通过逻辑设计有效的解决可能的缺陷。本文已经充分考虑了65nm 集成电路设计带来的各种挑战并通过逻辑改进以及采用已经非常成熟的IP core 等手段有效的改进了芯片系统的设计性能。加密芯片内执行得加密算法本身来 看，本文在实现手段上进行了各种的改进尝试，电路性能获得了有效的提高。本 文采用的是IBM的65nm工艺库，最差工作电压09V，最差温度140度。第二章首先分析了与加密算法关系非常密切的有限域卯f 28 1数学基础知识，包括有限域内多项式的加法与乘法，该理论的掌握对算法

34、的逻辑优化起到非常重 要的作用。随后分别介绍了Rijndael的加密模型与解密模型，并对算法的关键技 术如Byte Substitution，Shift Row，Mix Column以及Key Schedule进行了细致分 析，其中加密与解密是一个互逆的过程。在对Rijndael模型进行仔细分析的同时， 还将算法的逻辑模型与其数学模型相结合，挖掘出算法本身内在的优化潜力，为 后续的工作做足铺垫。第三章描述了本文的创新系统架构思想并讲解了ASIC的实现方法。本文从工艺水平以及逻辑算法两个方向去考虑，综合两者各自的优势，设计了一个符合 本文设计条件的系统架构即文中的混合设计思想。随后对Ri-ind

35、ael的ASIC前段 设计进行了详细分析，包括各个关键技术的实现。在有关Rijndael的ASIC设计 之中，采用了部分厂商提供的比较成熟的IPcore如Register Array，以及 clockgating技术，极大的改善了65nm下芯片的性能。第四章介绍了本文在设计上的创新点。动态可配密钥管理机制使得系统的灵活性大大增强，对应用环境有了更大的适应能力，同时动态可配置的密钥管理机 制在65nm，320MHz的系统时钟下提供了高达40Gbps的惊人数据吞吐能力；低 功耗时钟管理机制有效的解决了深亚微米工艺条件下引入的功耗问题，随着工艺 水平的不断进步，静态功耗与动态功耗的比例已经发生了显著

36、的变化，通过对系 统不同资源进行时钟管理，有效地降低了芯片内部的功耗以及可能的大散热量的 问题；有关基于RA(RegisterArray)的替代逻辑设计则体现了IP core的重用的 设计思想，采用了技术上性能上都比较成熟的Register Array代替了以往设计中 使用的ROM或复杂组合逻辑资源，实现了Rijndael加密算法中的替代操作。第五章采用了目前主流的专用集成电路验证方法搭建了模块级及系统级的验证环境，并通过Synopsys的仿真工具CVS获得ASIC的工作时序，并对时序 进行了系统的分析，结果表明该设计完全满足预定的时序要求。同时，本文采用5基于65nm工艺的Rijndael加

37、密算法AsIC实现了IBM的65nm PwcV090T125工艺库对设计进行了综合，并从综合报告中分析 得出，芯片实现了预期的低功耗设计并且在保证数据吞吐能力的前提下有效的控 制了设计的面积。6硕士学位论文第2章Rijndael加密算法分析21有限域数学基础知识人们已经利用有限域定义出多种公钥密码体制。本文所要讨论的Rijndael(读 作raindoU)加密算法中的加法和乘法同样是基于数学域论的，具体的讲，是基于有限域舒(28)。所以，了解有限域GF(28)的加法和乘法对硬件的实现及电路的优化来说，具有普遍的意义【41。卯(28)由一组从oxoo到。硝的256个值组成，加上加法和乘法，因此是

38、(28)。 卯代表伽罗瓦域，以发明这一理论的数学家命名。GF(28)的一个特性是一个加 法或乘法的操作必须在o枷 o珂这组数中，虽然域论是相当深奥的，但最终结果却很简单。(1)有限域的加法有限域GF(28)上的元素为多项式，两个元素的加法是通过将这两个元素的多项式表示中的对应幂的系数进行“加来实现的(用符号+表示)。这里的“加一 不同于普通意义的加法，而是将两个数相加在取2的模。因此，两个数的加相当 于二进制中异或操作。也就是说，有限域元素加法等价于异或的操作。对于字节口，吩，口4，口，口：，口。，口。与岛，吃，魄，钆，魄，62，2jI，和为c7，c6，c5，c4，c3，c2，q，co，这里c

39、j一色6i(f【o，7】)。例如，下面的3个等式是等价的：(，+矿+1)(矿+1)。，+，；(多项式) (21)00111001)o00001001一00110000；(二进制) (22)39o09)一30)；(十六进制) (23)(2)有限域的乘法卯(28)的乘法有点繁难。在多项式表达中，GF(28)上的乘法(用来表示)可解释为，将两个多项式相乘，其结果在对一个模为8的不可约分多项式取模。 如果一个多项式除数只有1和它本身的话，该多项式不可简约。在Rijndael算法 中，该不可约分多项式为：m(x)-，+z4+x3+x+1 (24)卯(28)乘法的数学描述如下：若口，6卯(28)，且口t口

40、7x7+口6矿+ +口1x+口o，7基于65nm工艺的Rijndael加密算法AsIc实现6-6727+66矿+ +扩x+60，则口与6的乘积与一般多项式相同。其差别为，若其 积的阶数等于或大于8时，必须以不可分解多项式肌(x)除之。故若c。口6，则c 可表示为： ，c一(口7x7+口6+：卜口1z+口o)(67工7+66+6lz+60) mod 聊(x)(25)例如，39)。09t)，其运算过程如下：(矿+z4+x3+1)(矿+1)l(p+x7+矿)+(，+，+1)(26)-p+z7+z6+，+z4+1(，+x7+矿+，+1)mod肌(x)一x7+矿+，+，+一(27)(3)有限域的特殊乘法

41、在卯(28)中，存在着一些特殊的乘法，了解并熟练使用这些乘法将会给本文后面的工作带来极大的方便。卯(28)中使用01)的乘法是特殊的，它等价于普通数学运算中用l的乘法， 其结果也同普通数学运算中的结果一样，即卯(28)中任何值乘以01都等于其自身。另外，在GF(28)中，我们来讨论一下关于02)的乘法，同加法的情况相同， 理论是深奥的，但结果却十分简单。只要被乘数的值小于80，这时乘法的结果 就是该值左移一个比特位。如果被乘的值大于或是等于80，乘法的结果就是该 值左移一个比特位，再用值扬去异或。这样的做法是防止“域溢出，并保证 乘法的乘积在卯f 28 l范围之内。在了解了01)与02)的乘法

42、之后，我们可以根据任意常量去定义乘法运算。 比如说，在使用03)做乘法运算时，可以将03分解为02的幂之和。因此，03 乘以任意字节6的乘法运算可以改写成：。 护p3凇烈眩8，一一(6。02)+(601)根据上面的推理，在212节所举的例子3909)-贸中，可以用另外一种方法求解。因为，39)01)-39)藩戮翠39)0202一49，39)02。02。02)d3因此。39)。09)一39。(01+08)一39)+d3(210)-贸8硕士学位论文可见，上述计算过程避免了取模操作，而是用简单的异或与左移操作来实现， 这样在很大程度上，为计算过程的硬件实现提供了方便【51。下面分析一下乞中的带系数的

43、多项式，在提到有限域的运算时，多项式的概 念比较重要，在随后的Rijndael算法中，应用很广泛。先看下面一个多项式：c(x)一c3，+c2x2+cl，+co(211)这里的多项式操作与前面提到的乘法中的多项式有些不同，这里需要分别介绍。 上式中的系数为有限域元素自己，就是说，如果有限域的元素为一个字节的话， 那么这个系数就是一个字节而不是单个比特。下面介绍一下关于多项式的加法和 乘法。首先定义一个与之相应的多项式：d(x)一d#3+d2工2+盔x1+do(212) 现在有两个多项式c(x)与d(x)，有关两个多项式的加法就是指将两个多项式对 应次幂的系数进行有限域的加法，即异或操作：c(x)

44、+d(石)一(cj o以)工3+(c：od：)z2+(c1 o吐)x1+(c。odo)(213)有关该多项式的乘法略显复杂，但总结起来可以分成如下步骤： 首先，将两个多项式做常规乘法，并将次幂相同的系数合并：c(x)d(x)一口626+口声5+口4工4+口，3+口2+口，1+口o(214)其中，该多项式的系数为相同次幂的系数和：口6c3以 吩一c34 oc2以 口4一c340c2彳20 c1以口3一c3成oc240 c1彳20co以(215)口2一c2么oq40co彳2 qq以oc04 口。一d00cb在经过一轮乘法后，多项式变成了七项，而并非是四项多项式。因此，还需要将 得到的七项多项式对四

45、项多项式，+1取模：modf，+1)一z删4(216)由此，便得到了两个多项式相乘的最终结果，此处相乘为了与普通多项式乘法进行去分，用c(x)d(z)表示，下面将乘法的结果表示如下：c(x)od(z)；哆声3+乞x2+qxl+(217)其中，各个次幂系数的值可表示为：9基于65nm工艺的Rijndael加密算法AsIc实现一(co九)o(q如)o(c：d：)o(c3盔)三二器黧戮葛乞一(c：或)o(c3以)o(cod：)o(c1盔)，汜岛一(c3毗)o(co以)o(cld：)o(c：曲)如果将上面的表达式转换为矩阵形式，会变得比较直观：九q盔(219)乞d2岛岛臼如白 勺q乞 勿白如臼磊比白如

46、 以 以上便是关于多项式的乘法操作，该部分数学运算将应用于Rijndael加密算法之中，具体实现将在后续章节逐一介绍。22 Rijndael简介1997年4月，美国国家标准和技术研究所(NIST)开始征集先进加密标准 (AES)算法来替代已不安全的DES算法。1998年5月，NIST宣布接收15个 新的候选算法并提请全世界密码研究界协助分析这些候选算法，包括对算法安全 性和效率特性进行初步检验I们AES的基本要求是比三重DES【7】快而且至少和三重DES一样安全，分组长度128比特，密钥长度为128、192和256比特。1998年8月20日NIST召开了第 一次候选大会，在NIST考察了这些初

47、步的研究成果后，选定MARS、RC6、 Rijndael、Serpent和Twofish这5个算法作为新的公开的联邦信息处理标准(FIPSFederalInformation Processing Standard)【引，用于没过政府组织保护敏感信息的一种特殊的加密算法【91。 通过对五种算法在安全性，软件实现速度、硬件实现速度和内存开销等方面进行综合测评后，于2000年10月2日选Rijndael算法作为AES。Rijndael算法 在评测中，安全性表现一般，但能满足NIST提出的要求。而且在硬件实现、软 件实现和内存需求方面都是最好的选择【10】。Rijndael加密算法是由比利时的两位密

48、码专家：国际质子中心的Joan Daemen 博士以及来自Katholieke大学电子工程系的博士后研究员ncent Rijnmen，发 明的一种迭代的，密钥加密分组的加密算法【111。该算法于2000年的10月从最终的五个候选算法中脱颖而出，被NIST(美国国家标准与技术局)认定为新一代 的高级加密标准(AES)【12】。Rijndael具有安全，高效，方便，灵活的特点，这使它成为了AES的合适选 择。特别指出的是，Rijndael在不同的硬件以及软件环境下可以表现出始终如一 的良好性能，并且Rijndael对于内存的要求很低，这使得Rijndael拥有更为广阔10硕士学位论文的使用空间【1

49、 31。Rijndael算法的原形是Square算法，它的设计策略是宽轨策略WideTrail Strategy，这种策略是针对搽粉分析和线型分析提出来的一个分组迭代密码，具 有可变的分组长度和密钥长度f1 41。Rijndael汇聚了安全性能、效率、可实现性和 灵活性等优点，对内存的需求非常低。Rijndael操作简单，并可抵御强大的攻击， 下面是Rijndael与目前正在服役的加密算法三重DES间的一些比较【15l：表21 RjndaeI与三重DES对比Rijndael 三重DES 算法类型 对称block密码对称fcistel密码 密钥大小 128、192或256112或168速度 高低

50、 消耗资源低 中正是因为Rijndael的高效率与低消耗，使得国际上许多公司已经决定使用 AES算法作为数据加密的标准。在说明Rijndael加密法之前，有必要看看Rijndael加密法的常见使用方法。 这样，应用方法就与特定的实现捆绑在一起。任何块加密算法(包括Rijndael 在内)可以以三种标准模式之一使用：电子编码簿模式，密文块链模式和输出反 馈模式。其实并不止这三种模式，但这是三种讨论最普遍的模式【16】。事实上， 美国国家标准与技术协会推荐了5种模式。一些新的模式正在吸引人们更多的注 意【171。电子编码簿模式(electfoniccodeb00k mode，ECB)是最简单的模式

51、。即每 个明文块加密成一个密文的一个块。图21演示了这种操作模式。上r上一!Key一Ek，Ek一卜 -一一Ek；l!I!I!；IiIiIf一I一I一图21电子编码簿模式加密一块一链(cipher-blockchaining，CBC)模式的实现更复杂(这是为了增 加安全性)。由于更安全，因此它是适用最普遍的块加密模式118】。在这种模式中， 来自上一块的密文与当前明文块做x0R逻辑运算，其结果就是加密的位块，这11基于65nm工艺的Rijndael加密算法AsIc实现有点像自动密钥加密法。图22演示了这种模式的操作。在该图中，第一个明文 块与0向量做XOR逻辑运算。这是CBC加密的最早方法，但不

52、安全。CBC更 安全的实现是适用初始向量(initial cector，IV)。EkpOPC1 C2 C3 董-上小工肽1(5图22加密块-链模式如果为每个消息传输选用不同的IV，那么两个相同的消息即使使用相同的密 钥，也将产生不同的密文。这大大提高了安全性。但问题是：接收端如何知道所 使用的IV呢?一种方法是在一个不安全的通道上来发送该IV。在这种情况下， IV只使用一次，且永不重复。另种更安全的方法是基于唯一数(nonce，number used once)的概念。唯一数是一个唯一的数字，永不重复使用相同的密钥。它不 一定非得保密，它可以是消息的数目等。用Rijndael加密法将唯一数加密

53、后生成 IV。如果唯一数附加到了密文的前面，接收端就可以还原Iv【19l。输出反馈模式(outputfeedback mode，OFM)使用块加密法来为流加密法 生成一个随机位流。密钥和块加密法的初始输入启动这个加密过程，如图23所 示，通过将块加密法的输出加密，为流加密法提供了附加的密钥位。KeyMir 一1 r 一1 r 一 i!i!iI1 ri Ri_一Ek L-一Ri+1 I一， 、I!I!l图23输出反馈模式硕士学位论文由于Rijndael算法的实现直接与相应的工作模式有关，因此两者必须结合起 来考虑。本文采用最普遍的，也比较复杂的CBC模式，因此，本文部分章节使 用Rijndael

54、 CBC表示工作与CBC模式下的Rijndael加密过程。Ri_indael是一种灵活的算法，其块的大小可变(128、192或256位)，密钥的 大小可变(128、192或256位)，迭代次数也可变(10、12或14)，而且迭代次 数与块和密钥的大小有关【201。正因为其灵活，Rijndael实际上有三个版本： AES128、AES192和AES256。常见的Rijndael结构如图24所示1211。Rijndael 不像DES那样在每个阶段中使用替换和置换，而是进行多重循环的替换、列混 合密钥加操作。从这来看，Ri_indael很像IDEA，没有进行包含置换操作的典型 Feistel轮(注意

55、，这里把术语AES和Rijndael视为等价的了，可以交替使用)。ExpandingEncryDt KeyEncrypt Key图24 Rijndaef加密算法结构图图24中的蓝色虚线将整个结构分为了三个部分：初始轮、中间轮以及最后 一轮。三者间的操作略有不同。Rijndael算法中每一轮的迭代运算由4种变换组 成，其中每一种变换被称为一个步骤，Rijndael算法中包括下面4个步骤：Add Roundkey、Byte Substitution、Shift Row和Mix Column。在加密的开始阶段，输 入的数据与初始密钥相加，我们这里称之为Add R0undkey。然后Rijndael根

56、据 密钥的长度执行相应次数的迭代运算。每一轮的迭代变换均以上一轮的转换结果 与一个轮密钥相加的结果作为输入，然后依次进行Byte Substitution、Shift Row 和Mix Column变换。最后一轮的迭代与前面的几轮略有区别。在最后一轮的迭 代中，仅需要3个步骤便完成了数组的转换，输出最终结果【221。针对轮转换，可用下面的C语言伪代码表示： Round(State，RoundKey)ByteSub(State)； ShiftRow(State)； MixColumn(State)；基于65nm工艺的Rijndael加密算法AsIc实现AddRoundKey(State，Roun

57、dKey)；) 最后一轮与前面几轮略有不同，需要注意：FinalRound(State，RoundKey) ByteSub(State)； ShiftRow(State)；AddRoundKey(State，RoundKey)； 从以上代码中可以看出，最后一轮相当于在前面轮次中少用一次列混合MixColumn。23 Rijndael加密模型分析Rijndael的加密解密要经过多次的数据变换操作，每一次变换操作都会产生 一个中间结果，我们称这个中间结果为状态。算法的所有操作都以状态为对象进 行，每个状态可由字节的矩阵列表示。这种矩阵列包含4行，矩阵列的列数目可 由Nb表示，并且Nb等于数据块的长度除以32。同理，密钥同样以一个包含4 行的矩阵列表示。密钥列数用Nk表示，它等于密钥的长度除以321231。从某种意义上讲，这些数据块也可以看作是4字节的一维向量，每个向量由 相应矩阵的一个列组成。Nb与Nk的可取值为4、6和8，下面以矩阵的形式列 出Nb不同取值情况下的数组结构：吣见吐口口a 皿皿岔口m nBm-4)(220)撕口 H口口口