（通信与信息系统专业论文）基于arm的数据加密算法实现.pdf

硕士论文基于a r m 的数据加密算法实现 摘要 a e s 作为新一代的分组数据加密标准，以其没有显著的攻击方法、编码易于实现 和加、解密速度快等优点，满足了人们不同信息安全等级的需要。而随着嵌入式系统 的迅猛发展和广泛应用，信息越来越多地在嵌入式系统之间、嵌入式系统与各种终端 之间进行交换，在嵌入式系统中应用a e s 信息加密技术就显得尤为迫切。针对这种 现状，本文给出了一种将a l e s 算法在基于a r m 微处理器的嵌入式系统中高效实现 的方法。 本文首先介绍了a e s 算法的原理、设计原则，根据a e s 算法大量矩阵运算的特 点，改进了传统的基于查表运算来提高加解密速度的方法，并针对嵌入式系统的特点 给出了算法的两种优化实现方案。然后依据本文a e s 算法和一般嵌入式应用的需求， 设计了一个基于a r m 的嵌入式系统，并详细介绍了该系统硬件和软件的设计过程。 最后在所设计的嵌入式系统中对改进的a l e s 算法进行验证和测试。通过在不同硬件 平台上的对比测试，本文的算法在嵌入式系统中达到了较高的效率。 本文所提出的算法采用c 语言实现，可以方便地移植到其他的嵌入式系统中；本 文所设计的嵌入式系统具有一定的通用性，便于扩展以应用于其它多种场合。 关键词：a e s ，加密，嵌入式系统，a r m ，u c o s i i 硕士论文基于a r m 的数据加密算法实现 a b s t r a c t b yw a y o ft h en e wb l o c kd a t ac n e r y p t i o ns t a n d a r d ，t h ea e s ，w i t hs u c he x c e l l e n c ea s h a v i n gn oo b v i o u s l ya n a l y z i n gm e t h o d s ，b e i n ga p tf o rp r o g r a m m i n g ，a n db e i n gq u i c ki n e n e r y p t i n ga n dd e c r y p t i n g ，s a t i s f i e sp e o p l e sd e m a n do fi n f o r m a t i o nw i t hd i f f e r e n ts a f e t y g r a d e a se m b e d d e ds y s t e md e v e l o p sr a p i d l ya n da p p l i e sa b r o a d ，t h ed a t ai se x c h a n g e d m o r ea n dm o r eb e t w e e ne m b e d d e ds y s t e m so ra m o n gt h ee m b e d d e ds y s t e m sa n ds o r t so f t e r m i n a l s oi t sm o r eu r g e n tt ot a k ea d v a n t a g eo fa e st oe m b e d d e ds y s t e mf o r i n f o r m a t i o ne n c r y p t i n g r e g a r d i n gt h i sp r e s e n ts i t u a t i o n , t h i sp a p e rp u t sf o r w a r da n m e t h o do f a c c e l e r a t i n gt h ea l g o r i t h mo f a e so nt h eb a s i so f t h ee m b e d d e ds y s t e m t h i sp a p e rf i r s t l yi n t r o d u c e st h ep r i n c i p l ea n dd e s i g n i n gi d e a lo ft h ea e sa r i t h m e t i c a c c o r d i n ga sa e sa r i t h m e t i c sw a i to fm u c hm a t r i xc a l c u l a t i n g ，t h ep a p e ri m p r o v e st h e c o n v e n t i o n a lm e a n so f i n c r e a s i n gt h ee n e r y p t i n gs p e e db a s e do nt a b l e - l o o k i n g - u pm e t h o d ， a n dp u t sf o r w a r dt w op r e c e p t so fr e a l i z i n ga e sa r i t h m e t i ca e 2 0 r d i n gt oh a l l m a r k so f e m b e d d e ds y s t e m t h e nt h i sp a p e rd e s i g n s 触a r m - b a s e de m b e d d e ds y s t e mw h i c h a c c o r d sw i t hd e m a n d so ft h ea e sa r i t h m e t i ca n de m b e d d e da p p l i c a t i o n , a n dp a r t i c u l a r l y i l l u s t r a t e st h ed e s i g np r o c e s so ft h es y s t e m sh a r d w a r ea n ds o r w a r e t h ea e sa r i t h m e t i c t h i sp a p e rg i v e sw i l lb ec h e c k e db yt h es y s t e mi nt h ea n d t h r o u g hc o m p a r i s o nt e s t i n go n d i f f e r e n th a r d w a r ep l a t f o r m , t h ea e sa r i t h m e t i ca c h i e v e su p p e re f f i c i e n c y a st h ea r i t h m e t i ct h i sp a p e rg i v e si se x e c u t e db ya n s ici m p l e m e n t , i ti se x p e d i e n t l y t oa p p l yi nd i f f e r e n te m b e d d e dp l a t f o r m t h ee m b e d d e ds y s t e mt h i sp a p e rd e s i g n e di sa u n i v e r s a lp l a t f o r m , s oi ti se a s yt oe x t e n di tt oa p p l yt o o t h e rs i t u a f i o m k e y w o r d s ：a e s ，e n c r y p t i o n ，e m b e d d e ds y s t e m ，a r m ，u c o s - i i 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 已在论文中作了明确的说明。 研究生签名：猩i 袅加形年f 月2 7 日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论文的部分或全部内容，可以向有关部门或机构送 交并授权其保存、借阅或上网公布本学位论文的部分或全部内容。对 于保密论文，按保密的有关规定和程序处理。 研究生签名：独凌沙一多年月：7 日 硕士论文基于a r m 的数据加密算法实现 1 绪论 1 1 课题的应用背景及研究意义 随着计算机和通信技术的发展，用户对信息的安全存储、安全处理和安全传输的 需求越来越迫切。特别是随着i m c r n e t 的广泛应用，个人移动通信、电子邮件通信得 到普及，网上证券交易、银行电子自动转帐支付系统、电子商务、电子政务得以实现， 这为人们的生活、学习和工作带来了极大的方便，但人们也更加关心信息的安全传输、 安全存储和安全管理。信息安全已成为人们关注和研究的重要课题。 信息安全的研究包括密码理论与技术、安全协议与技术、安全体系结构理论、信 息对抗理论与技术、网络安全与安全产品等领域，其中密码算法的理论与实现研究是 信息安全研究的核心。一个好的安全系统如果不依赖于好的密码算法，将是不可想象 的。信息安全的重要性决定了密码算法的研究和开发必须本土化，只有这样才能确定 密码算法的可靠性、安全性，才能用来保障通信与信息系统的安全 a e s 作为替代d e s 的美国标准，已于2 0 0 2 年5 月正式生效。由于美国在信息领 域的领先地位，a e s 实际上也已经成为国际标准。为了与国际接轨，我国在商用密 码方面也将会采用a e s ，所以应对其安全性和实现技巧进行充分研究。 目前a e s 算法的实现研究主要集中在通用微处理器( p c 机) 实现、硬件实现、 d s p 实现和嵌入式微处理器实现这几个方面。 基于通用微处理器的软件实现具有实现容易、可移植性强、成本低廉、易于升级 等优点，其缺点是需要硬件资源的支持，并且体积庞大，功耗难以控制，不适用于对 环境和体积有较高要求的场合。 硬件实现是用专用集成电路( a s i c ) 或f p g a 实现，虽然运算的速度会快很多， 但开发和生产的成本非常高，并且在设计时为了提高计算效率，芯片的功能总是针对 某种特定算法的，因而通用性不强。 基于d s p 实现相对于采用硬件实现降低了成本，增加了设计的灵活性，缩短了开 发周期，在采用高端d s p 处理器( t i 公司的c 6 0 0 0 系列) 时能够获得很高的性能1 3 5 】， 但对于多数嵌入式应用而言成本较高，并且系统中通常还需要微处理器的支持，使得 系统复杂度增加 目前基于嵌入式微处理器的嵌入式系统的应用已经渗透到各个领域，对嵌入式系 统的需求也是多种多样，在嵌入式系统中应用数据加密算法已是必然趋势。基于嵌入 式微处理器实现a e s 算法具有实现简单、系统集成度高、体积小、易于移植等众多 优点，虽然其效率不如采用硬件和d s p 的实现方式，却可以有效地降低系统复杂度， 而且一些嵌入式应用场合对数据传输和处理速度的要求并不是很高，对于安全性和系 硕士论文 基于a r m 的数据加密算法实现 统体积的要求却日益增高。目前基于a e s 加密的嵌入式商用产品已经开发应用，但 基于嵌入式微处理器实现方案的产品非常少，而且事实上d e s 和三重d e s 还占领着 市场，因此很有必要研究自主知识产权的a e s 产品，那么现在对a e s 的理论和实现 进行探讨和研究就具有较大的理论和现实意义。 1 2 数据加密算法的发展 密码学广泛应用于通信安全保密和存储加密等领域。密码学的基本思想是对机密 信息进行变换，以保护信息在信道传送过程中不被非法窃取，解读和利用。 密码体制的分类方法有很多，一般是通过加密算法与解密算法所使用的密钥是否 相同的原则分为：非对称密钥密码体制和对称密钥密码体制。非对称密码在加密和解 密的过程中使用不同的密钥( 公钥和私钥，也称为公开密钥密码) ，其中公钥公开， 私钥保密，代表算法是r s a ：对称密码所用的加密密钥和解密密钥相同。对称密钥 密码体制从加密模式上又可分为序列密码和分组密码。应用在网络、通信环境中的数 据加密方法更多的是采用分组密码体制，其代表是d e s ( d a m e n c r y p t i o n s t a n d a r d ) ， 新一代的加密算法是a e s ( a d v a n c e de n c r y p t i o ns t a n d a r d ) 。分组密码算法通常由加、 解密算法和密钥扩展算法两部分构成，密钥扩展算法用于生成m 个子密钥。加密算 法由一个密码学上的函数厂对数据分组进行一系列变换之后，每次与一个子密钥迭 代，总共迭代r 次完成一次分组加密。 d e s 曾被美国国家标准局( n b s ，现为国家标准与技术研究所s t ) 确定为联 邦信息处理标准，使用广泛，特别是在金融领域，曾是对称密码体制事实上的世界标 准。d e s 处理的明文分组长度为6 4 位，密文分组长度也是6 4 位，使用的密钥虽然 要求“位，但实际只使用了5 6 位。由于计算机硬件的速度越来越快，d e s 密钥长 度太短的缺陷就显露出来，可以在不到一天的时间内被强行攻破【3 6 】口7 】。进入上世纪 九十年代后，另一种由d e s 衍生出来的算法一三重d e s ，被广泛的使用。但是它 的安全性并不意味着建立在1 6 8 位的密钥之上。研究表明，可以将其转化为对1 0 8 位密钥量的攻击；最重要的是三重d e s 的加密和解密时间消耗较大，其设计主要针 对硬件实现，不能很好地适应飞速增长的实时信息加密需求，也不适合如今日益增多 的需要软件实现的领域。 自1 9 9 7 年4 月1 5 日起，n i s t 开始征集新一代数据加密标准即高级数据加密标 准算法( 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 位。n i s t 用了3 年的时间对所有侯选算法做了大 量的分析和测试，经过两轮严格的淘汰，最终宣布选择来自比利时的r i j n d a e l 作为 a e s 算法。 2 硕士论文基于a r m 的数据加密算法实现 r i j n d a e l 算法是一种可交分组长度和密钥长度的迭代型分组密码，它的分组长度 和密钥长度均可独立地指定为1 2 8 位，1 9 2 位，2 5 6 位。a e s 的安全性目前仍在讨论 中，从目前的进展来看，尚无以知的安全性方面的攻击，也没有找到明显的安全漏洞。 a e s 在设计时已经考虑到差分攻击和线性攻击，3 种不同的可逆变换确保了多轮之上 的高度扩散，提供了线性密码分析和差分密码分析的能力，因此可以很好的抵御这两 种攻击。非线性层有1 6 个并行的s 一盒构成，起到了混淆的作用。r i j n d a e l 的密钥 建立时间极短且灵活性强，它极低的内存要求使其非常适合在存储器受限的环境中使 用，并且表现出很好的性能，非常便于软件的实现。而且r i j n d a e l 各运算部件都具有 良好的统计特性，并行执行度高，加、解密速度快，不需要繁琐的乘法运算，因而便 于硬件实现。 在非对称密码领域，r s a 方案是唯一被广泛接受并实现的通用公开密钥密码算 法，目前已成为公钥密码的国际标准。r s a 的基础是数论的欧拉定理，它的安全性 依赖于大数的因数分解的困难性。r s a 公开密钥密码体制所根据的原理是【l 】：根据数 论，寻求两个大素数比较简单，而分解它们的乘积则极其困难。对于r s a 体制的安 全，必须仔细选择每个参数。由于大整数因子的分解的能力日益增强，对r s a 公钥 密码的安全带来了威胁。 1 3a f u 旺微处理器简介 嵌入式系统以应用为中心、以计算机技术为基础，软、硬件可裁剪，适应应用系 统对功能、可靠性、成本、体积、功耗等严格要求的专用计算机系统翻。嵌入式系统 主要包括硬件和软件两部分。硬件包括处理器、存储器以及外设器件和f o 端口、图 形控制器等；软件部分包括操作系统( o s ) 和应用程序。嵌入式系统硬件的核心是 嵌入式微处理器，它的功能、外设集成度、速度、功耗、体积、成本、可靠性、电磁 兼容性等方面均受到应用要求的制约，是各个半导体厂商之间竞争的热点。 a r m ( a d v a n c e dr i s cm a c h i n e s ) ，既可以认为是一个公司的名字，也可以认为是 对一类嵌入式微处理器的通称，还可以认为是一种技术的名字。1 9 9 1 年a r m 公司成 立于英国剑桥，主要出售芯片设计技术的授权，作为知识产权供应商，本身不直接从 事芯片生产，靠转让设计许可由合作公司生产各具特色的芯片，世界各大半导体生产 商从a r m 公司购买其设计的a r m 微处理器核，根据各自不同的应用领域，加入适 当的外围电路，从而形成自己的a r m 微处理器芯片进入市场【3 l 【4 】。 a r m 处理器主要有a r m 7 、a r m 9 、a r m 9 e 、a r m l 0 e 、s e c u r c o r e 、i n t e l 的 x s c a l e 和s t r o n g a r m 等系列，功耗数量级为m w m i - i z ，每种系列提供一套相对独特 的性能来满足不同应用领域的需求。其中a r m 7 系列微处理器为低功耗3 2 位r j s c 处理器，最适合用于对价位和功耗要求较高的消费类应用。a r m 7 内核是冯诺依曼 3 硕士论文基于a r m 的数据加密算法实现 体系结构，数据和指令使用同一条总线。内核有一条3 级流水线，执行a r m v 4 指令 集。a r m 7 系列中的a r m 7 t d m i s 是目前最广泛使用的3 2 位嵌入式r i s c 处理器， 它提供了非常好的性能功耗比，其拥有1 6 位的t h u m b 指令集、快速乘法指令和嵌 入式i c e 调试技术，支持片上断点和调试点，给调试和开发都带来很大的方便。 目前，采用a i t m 技术知识产权( 口核) 的微处理器，即通常所说的a i t m 微处 理器，已遍及工业控制、消费类电子产品、通信系统、网络系统、无线系统等各类产 品市场，基于a r m 技术的微处理器应用约占据了3 2 位r j s c 微处理器7 5 以上的市 场份额，a r m 技术正在逐步渗入到生活的各个方面。目前，全世界有几十家大的半 导体公司都使用a r m 公司的授权，因此既使得a r m 技术获得更多的第三方工具、 制造、软件的支持，又使整个系统成本降低，使产品更容易进入市场被消费者所接受， 更具有竞争力。 1 4 课题的研究任务及要求 基于上述讨论，本文研究设计了一种通用的基于a r m 的嵌入式系统，完成了操 作系统的移植，并在该系统上采用先进的a e s 加密算法对输入输出数据提供有力的 安全保障机制。为了提高加密算法实用性，对算法进行了优化，大大提高了算法的效 率，使之满足嵌入式应用的要求。本文所设计的系统保留了很大的扩展空间，可以依 据应用系统的实际需求进行功能的添加。该系统主要针对的是一些实时性和数据安全 性要求较高，但数据量不是很大的嵌入式应用环境。 本课题要求完成以下工作： 1 高级数据加密算法( a e s ) 的优化。 2 在嵌入式系统中实现a e s 算法。 3 嵌入式系统的硬件设计与调试。 4 硬件设备的驱动程序开发。 5 嵌入式操作系统的移植。 1 5 本文的主要内容安排 本文正文各章节的内容安排如下； 第一章绪论。主要说明了本文的研究背景和意义，介绍了相关内容在当前国内 外的发展概况，包括数据加密算法和嵌入式系统发展现状和前景。同时提出了本文要 完成的主要任务，明确了本文研究方向。 第二章总体设计方案。分析了系统的总体需求，在此基础上提出了系统的总体 设计方案，对系统软硬件的设计实现做了具体的规划。 第三章a e s 算法的优化实现。首先阐述了a e s 算法的数学基础和算法的设计原 4 硕士论文基于a r m 的数据加密算法实现 则，在此基础上对算法有针对性地进行优化，并以c 语言的方式在嵌入式系统中将 其实现。对实现的算法，选择了三个测试平台综合对比算法的性能。最后对a e s 算 法的安全性能作了比较全面的分析，定量的给出了a e s 算法抵抗现有已知密码攻击 的能力。 第四章系统硬件设计与实现。主要规划了系统硬件的功能单元，对各个单元的 硬件特点和选择依据作了较详细的说明，并介绍了各个单元的设计方法。 第五章系统软件设计与实现。详细介绍了嵌入式系统的软件开发流程。分析了 系统启动代码的设计思路，讨论了u c o s - 操作系统的移植方法，实现了在u c o s - i i 操作系统上的驱动程序开发，并依据系统的功能需求设计了应用软件。 第六章系统调试。主要介绍了系统硬件和软件的调试方法过程，也介绍了一些 调试的方法和技巧。 5 硕士论文 基于a r m 的数据加密算法实现 2 总体设计方案 根据实际的需求，设计出有针对性的嵌入式应用系统，是面向应用的产品设计最 基本的要求。嵌入式应用系统的设计包含硬件和软件两部分，并且这两部分互相关联、 密不可分，要综合考虑和相互权衡。这也是嵌入式应用系统设计与纯粹的软件设计或 硬件设计最大的区别。 2 1 系统需求分析 课题所研究主要内容是在一个基于a r m 处理器的嵌入式系统中高效地实现a e s 数据加密算法，所以系统设计的目标并不是追求硬件性能的最大化，而是在确定的硬 件上实现算法性能的最大化。同时系统所设计的硬件应当具有通用性和较好的扩展 性，而且应当面向实际应用。本文所设计的嵌入式系统是一个完整的应用系统，系统 的整体架构如图2 1 1 所示： 图2 1 1 系统架构图 系统架构可以分为硬件层、驱动层和软件层三个部分。其中硬件层是整个系统的 基础，包括处理器、存储设备、输入输出设备以及扩展设备。硬件的规划和设计将从 根本上决定整个系统的性能和稳定性。由于系统是作为一个通用平台，性能的要求不 很苛刻，主要考虑的是系统的稳定性、功耗及扩展性，所以可将系统的基本要求确定 如下： 1 微处理器应当能流畅地运行所选定的操作系统和加密算法。处理器应当有较 高的集成度、很好的扩展性及丰富的内部外设，方便系统的扩展； 2 存储系统的容量要足够装载操作系统及其它软件，并有一定的保留空间； 3 有直观而便捷的显示单元： 4 有信息输入单元，方便手动输入信息和人工控制； 6 硕士论文 基于a r m 的数据加密算法实现 5 可以方便而快捷地与外部交换数据； 6 操作系统要求实时性高、体积小、简单易用； 7 软件的设计以易于实现和移植为原则。 2 2 系统总体设计方案 经过充分考虑系统的设计需求，本文将系统各功能单元的确定如下： 1 处理器：选择p h i l i p s 公司生产的基于a r m 7 t d m i s 内核的l p c 2 2 1 0 是微 处理器。l p c 2 2 1 0 微处理器是一款低功耗、高性能的产品。该处理器具有较高的性价 比，片上最大程度集成了所需的外围组件，可降低系统的成本及开发难度，提高系统 的稳定性。 2 存储系统单元：系统配置8 m b 的p s r a m 作为系统运行时的存储区，运行中 的系统及用户数据、堆栈均存于p s r a m 中；同时配置2 m b 的n o rf l a s h 用于存 放嵌入式操作系统、已调试好的用户程序及其它一些需要掉电保护的用户数据。 3 输入输出单元：配置2 2 英寸1 1 玎液晶屏作为显示模块，模块中自带液晶控 制驱动芯片，简化控制过程；采用了4 x 4 矩阵形式的1 6 键键盘，由键盘控制芯片控 制，支持最大扩展为8 8 矩阵的“键键盘。 4 数据交换单元：采用了u s b l 1 接口实现高速数据交换，并配置有一个主机 接口和一个设备接口，增强系统的扩展性。 5 嵌入式操作系统：选择u c o s i i 实时操作系统。u c o s i i 是一个易移植、可 裁减的占先式多任务内核，非常适合本课题的要求。 6 开发环境：本文主要考虑在w i n d o w s 操作系统环境下的系统开发。集成开发 环境选择a r m 公司的a d s i 2 集成开发工具，软件的实现主要采用c 语言，硬件采 用j t a g 接口的仿真调试方式。 对于系统软硬件各个单元模块的功能和结构，将在本文的第四章和第五章中进行 详细的描述。 2 3 小结 本章主要分析了本文所设计系统的需求，并在此基础上给出了系统各个模块的构 成。为下_ 步算法软件和硬件电路的实现提供设计依据。 7 硕士论文基于a r m 的数据加密算法实现 3a e s 算法的优化实现 a e s 算法是当前密码算法设计最高水平的反映，设计者在进行算法设计时主要 考虑了以下三点： ( 1 ) 要能抵抗现有己知的攻击方式。 ( 2 ) 在各平台上都具有良好的性能，如较快的速度、编码要紧凑等。 ( 3 ) 设计要简单。 第一点强调的安全性原则，而后一点强调的是实现性原则，这是a l e s 所遵循的 两个重要原则。a e s 在整体结构上采用的是替代置换( s p ) 网络的迭代结构方式， 在安全性方面能抵抗各种攻击。本章将详细描述a e s 算法的优化实现方案及该方案 的性能分析。 3 1a e s 算法数学基础 3 1 1 有限域g f ( 2 s ) 定义：结构 如果满足以下两个条件： ( 1 ) 町卜， 是一个交换环； ( 2 ) 除了 中的零元素0 以外，f 中的其他所有元素关于运算“”在f 中均存在逆元素； 就称这个结构f 为一个域。 在密码研究中所遇到的大多为元素个数有限的系统。若域f 中的元素个数有限， 则称这个域为有限域。域中元素的个数称为域的阶。m 阶域存在当且仅当m 是某素 数的幂，即存在某个整数n 和素数p ，使得m = p “。 具有相同阶数的有限域是同构的，即它们具有非常相似的代数结构，其区别仅在 于元素的表示：也就是说，对于任意素数的方幂m ，只有唯一的一个有限域，用g f f ) 表示，其余的所有表示是同构的。 有限域最直观的例子是素数p 阶域g f ( p ) ，其元素可以用整数l ，2 ，p - 1 来表示。 该域的两种运算规则是“模p 的整数加法”和“模p 的整数乘法”。对于阶数不是素 数的有限域，其加法和乘法运算不能表示为某个数的加法和乘法模。当n l 时，可以 选择有限域g f ( p ) 上的多项式表示法。 3 1 2 有限域上的多项式 域f 上的多项式形如： 6 ( 功= 6 h 】，1 + 屯一2 x ”。2 + + 6 2 x 2 + 6 i x + 6 b x 称为多项式的变元，鱼f 是多项式的系数。 窘 硕士论文基于a r m 的数据加密算法实现 可以仅将域上的多项式看作为抽象的实体而不参加计算。由于不对多项式中的各 项之和进行计算，因此即使多项式定义在2 特征域上，仍然使用符号“+ ”。 称一个多项式的次数为，如果对于w ，均有b ，= 0 ，并且，是具有此性质的最 小数。域f 上的多项式的集合用，【工】来表示，而域f 上次数小于，的多项式的集合用 f x 】l 来表示。 在计算机内存中，研明k 中的多项式可以通过将其，个系数作为一个字符串来实现 有效存储。 一 根据域f 上的多项式表示，一个字节可以看作一个系数在g f ( 2 ) 上的多项式： 6 7 6 6 6 5 钆岛6 26 1 6 0 6 ( 力 6 ( z ) = 6 7 x 7 + 6 6 + 6 5 矿+ 6 4 + 岛，+ 6 2 ，+ 岛工+ 6 0 所有可能的字节值的集合对应于次数小于8 次的全体多项式，即可以看作有限域 g f ( 2 8 ) 的元素。下面讨论相应的运算法则。 3 1 3 有限域g f ( 2 s ) 上的字节运算 下面定义g f ( 2 8 ) 上的字节运算。 ( 1 ) 加法运算：字节的加法定义为多项式的二元加法，即字节之和等于先对具有 相同x 次幂的系数在g f ( 2 ) 上求和，然后各项再相加。字节与字节之间可以用按位异 或来实现，即： ( a t a 6 a s a 4 a 3 a 2 a l a o ) + ( 6 7 6 6 6 5 6 6 3 6 2 岛) = ( c 7 c 6 c 5 c 4 c 3 c 2 q c o ) 其中，q = 口f o 玩，i - 0 ，1 ，7 。 ( 2 ) 乘法运算：字节乘法关于字节加法满足结合律、交换律和分配律。为使乘法 运算在f x 】l 上具有封闭性，选取约化多项式： r e ( x ) = 矿+ x 4 + ，+ x + i 则多项式口( 功和6 ( 力的乘法定义为模所力下的多项式代数乘积； c ( 功= 口( x ) 6 ( 力= 口( 6 ( 力m o dr e ( x ) 其中口( 工) 6 ( 工) 是普通多项式乘法，但系数运算可以看作比特的乘法和异或运算，即 看作域g f ( 2 ) 上的运算。 ( 3 ) 乘x 运算：乘x 是乘法运算的特例，即用x 乘以一个多项式再模m ( x ) 。乘x 可 用字节内左移与m ( x ) 的条件异或来实现。表示为： a ( 工) 2 嘞，+ a 6 x e + a 5 x + a 4 x ( + a 3 x 3 + a 2 x 2 + a l x + a o 工a ( x ) = a 6 x 7 + a s x 6 + q ，+ 码一+ a 2 x 3 + q x 2 + a o x ( 码= o ) 或z 口( x ) = ( 咏，+ a s x 6 + a 4 x 5 + a 3 x 4 + a 2 x 3 + q x ：+ a o x ) ( 9 d ( x )( q = 1 ) 其中d ( z ) = ，+ ，+ x + 1 。 9 硕十论文 基于a r m 的数据加密算法实现 3 1 4 有限域c r c 2 s ) _ l ：的字i g 算 在a e s 中，4 个字节的向量可以表示为系数在g f ( 2 8 ) 上的次数小于4 的多项式。 全体字集合及运算构成一个环： 字r = ( 码啦q ) iq e g f ( 2 8 ) ，。相应的加法 + ”) 和乘法 ”) 运算定义如下： ( 1 ) 加法( “+ ”) ： ( 吩口2 q ) + ( 岛6 2 6 1 6 0 ) = ( c ：2 q c o ) 其中，q = q + 6 j ，f = o ，l ，2 ，3 ，q = a j + 6 f 是g f ( 2 8 ) 中的加法运算。 ( 2 ) 乘法 “”) ： ( q 吒q 口o ) ( 岛6 2 岛6 0 ) = ( 白吃q 岛) 其中，岛，+ c 夕+ q x + c o = ( 码p + 码矿+ q x + ) ( 6 3 ，+ 6 2 矿+ a x + 6 0 ) m o d ( x + 1 ) 这里 的多项式乘法视为普通多项式乘法，但系数的运算是g f ( 2 8 ) 中运算。 3 2a e s 算法原理描述 迭代型分组加密算法是由轮变换通过多次迭代构成的，轮变换的构成包括非线性 层，扩散层和密钥调度等元素。这些设计是基于香农提出的设计原则：非线性替代与 线性混合函数交替进行。这样结合的结果导致来自密码的重要的统计特性必须是高度 。相关的和敏感的类型，即通过混合变换的扩散和混乱产生充分的混合，使加密后的分 组统计特性分布更均匀。 r i j n d a e l 是具有可变分组长度和可变密钥长度的分组密码。其分组长度和密钥长 度均可独立地设定为3 2 比特的任意整数倍，最小值为1 2 8 比特，最大值为2 5 6 比特。 而被标准a e s 采纳的r i j n d a e l 将分组长度固定为1 2 8 比特，而且仅支持1 2 8 、1 9 2 或 2 5 6 比特的密钥长度。本文所讨论的a e s 的分组不被限制三种固定长度。 分组数据块要经过多次数据转换操作，每一次转换操作产生一个中间结果，这个 中间结果叫做状态。状态可表示为二维字节数据，该数组共有4 行。状态中的列数记 为n b ，且n b 等于分组长度除以3 2 ，在标准a e s 里n b = 4 。密钥也可类似地表示为 二维字节数组，该数组也有4 行。密码密钥的列数记为n k ，它等于密钥长度除以3 2 。 状态和密钥数组的每一列都可以看作一个3 2 比特的字。轮数n r 依赖于密钥长度和分 组长度，具体值列于表3 2 1 中。 表3 2 i 不同n b 和n k 下的轮数值n r n rn b = 4 n b = 6 n b = 8 n k = 41 0 1 21 4 n k = 61 21 21 4 n k = 81 41 41 4 n k 为密钥包含的3 2 位字的个教 硕士论文基于a r m 的数据加密算法实现 3 2 1a e s 算法结构 a e s 算法的结构紧凑、规整，加密和解密过程相似，采用的是替代置换( s p ) 网络结构。算法的每一轮由三层组成： ( 1 ) 非线性层：进行s u b b y t e s 变换( 即s 盒置换) ，起到混乱的作用； ( 2 ) 线性混合层：进行线性s h i f t r o w s ( 行变换) 运算和m i x c o l u m n s ( 列变换) 运算以确保多轮之上的高度扩散； ( 3 ) 加密钥层：进行a d d r o u n d k e y ( 轮密钥加) 运算，将子密钥简单的异或到中 间状态上。 许多密码分析方法对迭代密码的第一轮和最后一轮的分析方法与中间的轮的分 析方法不同，一般根据假定的密钥值和明文、密文进行运算来剥去迭代密码的首轮和 末轮，为此a e s 算法对第一轮和最后一轮进行了特殊的处理，第一轮之前加了一个 密钥控制下的前期变换，而最后一轮则去掉其中的列混合运算，因此a e s 算法在总 体结构上采用了第一轮和最后一轮特殊对待的s p 结构。 加解密流程如图3 2 1 1 所示( 明文和密钥长度均为1 2 8 比特的情况) 。 图3 2 i 1a e s 的加密与解密 硕士论文基于a r m 的数据加密算法实现 从图3 2 1 1 可以看出，轮变换( r o u n d ) 由4 个基本变换组成( s 盒变换，行变 换，列变换和轮密钥加) 。最后一轮稍有不同，少了m i x c o l u m n s ( 解密算法中是第一 轮少了i n v m i x c o l u m n s ) ，下面分别介绍轮变换中各个基本变换。 1 字节替换( s u b b y t c s ) 字节替换s u b b y t e s 是a e s 中唯一的非线性变换，它包含一个作用在状态字节上 的s 盒，这里用s 。表示。s 。的设计应考虑非线性度、数学复杂度等因素，文献【3 8 】 中给出了几种特性良好的s 盒的构造方法，在本论文中所采用的s 盒由下式定义： g ：口一b = a 一1 其中乘法的逆a 1 可以由g f ( 2 8 ) 中的乘法运算得到，值0 映射到其自身。根据上 式的定义，g 的代数表达式非常简单，因此将s 盒构造为g 和一个可逆仿射变换，的 组合。厂对s 盒的非线性没有影响，但适当的选择，可以使& d 的代数表达式非常复 杂。所以，可以说s u b b y t e s 变换是由两个步骤组成( 假定输入状态为a ，输出状态为 c ： ( 1 ) 将状态a 中的每个字节映射为它在有限域g f ( 2 8 ) 中的乘法逆a i ，“0 ”被映射 为它自身。 ( 2 ) 对a - 1 中每个字节的每位做厂仿射变换，得到s 变换的输出b 。 由于，的选取范围很大【5 1 ，、所以附加了限制，即应当没有不动点，也没有相 反的不动点： s a e a 0 0 ，v a 【a 】0 a o x f f ，v a 最终选取的仿射变换为： 岛皇q o q “4 ) m o d 8a t “，) m 喇。0 口【，棚m o d 8 e a ( “，m o d 。0c 其中，c = 【c 7 c 6 c 5 0 c 3 c 2c l 白】= 【0 1 1 0 0 0 l1 6 】= 【6 3 明。上式用矩阵表示为： b = 厂( a ) 五 6 6 6 5 6 4 6 3 6 2 6 l 6 0 l1 o1 00 00 10 l1 11 l0 11 1l 11 11 o1 o 0 o o oo 1o 1l 11 l1 1l l1 11000 l m 吼 岛 以 呜 吒 q o s u b b y t e s 变换的这两步运算都是可逆的，因此s u b b y t e s 变换是可逆的。s u b b y t e s 8 l l l l o 0 o l 1 l o o o 1 硕士论文基于a r m 的数据加密算法实现 的逆运算称为i n v s u b b y t e s ，它由作用在状态字节上的逆s 盒s 。“组成逆s 盒号肋- 1 所执行的运算为：先进行仿射变换，的逆变换，然后计算g f ( 2 8 ) 中的乘法逆。 s 盒在本质上可以看作是一个多输出的布尔函数，可记作s ( x ) ：霹寸f ，其中 1 ms ”，因此若是用布尔函数来描述s 盒，则对于s 盒性能的研究主要包括非线性 次数、非线性度、线性结构和退化性、相关免疫性以及严格雪崩准则和扩散准则。如 果用m 、玩、d e g ，分别表示s ( x ) 的非线性度、差分均匀性和非线性次数，则s ( x ) 有 如下性质【6 】： 1 2 2 “一2 班 瓦= 【2 r - “* t , n 脚m 0 0 d d 2 2 * ：0 。 d e g ，= n - 1 非线性度反应了多输出布尔函数的某些分量的线性组合和线性函数之间的相关 程度，在密码算法分析上决定了密码算法抗击线性分析的能力；差分均匀性反应了多 输出布尔代数函数抗击差分密码分析的能力；非线性次数反应的是密码算法抵抗高阶 差分密码分析和插值攻击的能力，非线性次数越大，则抵抗高阶差分密码攻击和插值 攻击的能力越强。 2 行移位( s h i f f r o w s ) 行移位s h i f t r o w s 是一个字节换位，它将状态中的行按照不同的偏移量进行循环 移位：第0 行移动c 0 字节，第一行移动c l 字节，以此类推，从而使第纤f 第，列自q 字 节移动到( j - c j ) m o d m 。偏移量e 依赖于n b 的取值a 为了达到最佳的扩散性能，4 个偏移量必须互不相同。再依据简单性的准则，在 分组长度为1 2 8 比特的情况下，偏移量的取值应当取0 、1 、2 、3 。s h i f t r o w s 的操作 示意如图3 2 1 2 。 s h i f l r o w s i i i 一1 母2s 。3既墨如茸， 翮篓圈 硕士论文基于a r m 的数据加密算法实现 s h i r r o w s 运算显然是可逆的，其逆运算称为i n v s h i r r o w s 。它是底部三行的循环 移位，各行分别反向移动e 个字节。 3 列混合( m i x c o l u m n s ) 列混合m i x c o l u m n s 是对状态矩阵的列的运算，它将状态矩阵中的每个字节扩散 到该字节所在列的每个字节，实现香农的扩散原则。在列混合运算中，状态矩阵中的 每一列被看成是g f ( 2 8 ) 有限域上的4 次多项式，与一个固定的多项式c ( x ) 进行模x 4 + 1 的乘法运算，即： s 。( 功= c ( 力j ( 功m o d ( x 4 + 1 ) 其中，“x ) = 0 3 ，+ 0 2 工2 + 0 1 x + 0 2 ，系数是字节。该多项式与矿+ 1 互素，因此是 可逆的。用矩阵表示为： j 0 屯。 岛。 0 20 3 0 1 0 1 - 0 10 20 30 1l o lo l0 20 3l 0 30 1o l 0 2 j m i x c o l u m n s 的逆运算称为i n v m i x c o l t a n n s ，其变换方法与m i x c o l u m n s 完全类似， 只是固定多项式变为c 一1 ( 】：) = 0 b 矿+ 0 d 工2 + 0 9 x + o e 4 轮密钥加( a d d r o u n d k e y ) 轮密钥加是轮密钥与状态阵列中的对应字节按位异或的变换。轮密钥通过密钥扩 展方案，由种子密钥所生成，生成的轮密钥长度等于分组长度n b 。 3 2 2 密钥扩展方案 轮密钥的生成是由密钥扩展和轮密钥选择两部分构成，其基本原则是： ( 1 ) 轮密钥的总位数等于分组长度乘以( 1 + n r ) ，如分组长度为2 2 8 比特，轮数为 1 0 ，则轮密钥的总长度为2 2 8 x ( 1 0 + 1 ) = 2 4 0 8 比特； 。( 2 ) 种子密钥扩展为扩展密钥，种子密钥长度为4 x n k 个字节； ( 3 ) 轮密钥由以下方法从扩展密钥中获得：对第l 轮密钥由前n b 个字构成；第2 轮密钥由第二个n b 个字即第n b + 1 个字到第2 n b 个字构成；以下以此类推。 扩展密钥用数组w n b x 烈什1 ) 】表示，数组的元素为3 2 比特的字，前n k 个字是 种子密钥，其它的密钥字通过递归定义生成。由于密钥扩展函数取决于n k 的值，下 面将分别讨论n k 6 和n k 6 两种情况。 对于n k 6 ，用c 语言描述为： k e y e x p a n s i o n ( b y t ek e y