（计算机应用技术专业论文）rijndael加密算法的研究及其dsp实现.pdf

r u n d 1 加密算法的研究及其d s p 实现 摘要 计算机技术和网络技术的迅速发展，使得现代社会高度信息化。在日常 生活中，使用电子装置储存重要资料的方式日渐普及。随之而来的是，信息 安全受到了人们的普遍关注。当使用者必须经由不可信任的通道传递秘密信 息时，人们总是使用密码系统保障信息的安全。 数据加密标准( d e s ) 自1 9 7 7 年被采用至今，已超过二十多年。面对各种 新的攻击方法，d e s 在某些应用上已不堪使用。因此，在2 0 0 0 年1 0 月，美 国国家标准技术局( n i s t ) 选定r u n d a e l 算法为新的高级加密标准，将获得广 泛地应用。本文的第二章介绍了与m i n d a e l 密码算法相关的数学基础知识、 算法的基本原理、算法的结构和程序流程。 由于r b n d a e l 加密算法的安全性，本文第三章研究了r j j n d a e l 算法的整 体结构，指出r 帕d a e l 算法在整体结构上是一种第一轮和最后一轮被特殊处 理的s p 网络结构，并对算法的s 层设计、p 层设计和密钥加层设计的技巧 进行了分析，这对于分组密码算法的设计具有一定的指导意义。 而在本文的第四章，首先对分组密码的分析做了概述，介绍了分组密码 攻击的分类、攻击复杂度的两个方面和一些常用的攻击方法，然后主要研究 了算法对现有的常用密码攻击手段的抗攻击能力，主要讨论了强力攻击、差 分密码攻击、线性密码攻击、s q u a r e 攻击和插值攻击等，之后又对砌i n d a e l 算法的弱密钥状况进行了分析。 r i i n d a e l 加密算法易于实现，本文第五章研究了该算法的d s p 实现。这 晕介绍了d s p 技术，阐述了d s p 程序设计的流程，并给出了算法在实现时 的优化方案。 针对实际应用，第六章又将r “n d a e l 算法和公钥加密算法r s a 结合，构 建了一个加密模型，之后，对d s p 平台下加密机的软件设计的相关内容做了 介绍。 关键词：r i j n d a e l 加密算法；高级加密标准；密码分析；d s p t m s 3 2 0 v c 5 4 1 6 ；密钥生成算法； r d n d a e l 加密算法的研究及其d s p 实现 a b s t r a c t 1 、h et e c h n o l o g yo fc o m p u t e ra n di n t e m e t d e v e l o p si k t ，w h i c hm a k e s m o d e ms o c i e t yh i 曲l yi n f o r m a t i o n a l i z e d n o w a d a y s ，d i g i t a li n f o r m a t i o n 掣o w s e x t f e m e l y i n o u r d a i l y l i f e ， a n dt h e i m p o r t a l l c e o f s e c u r i t y i n c r e a s e s e o r r e s p o n d i n g l y p e o p l ea l w a y sp r o t e c ti n f o r m a t i o nt r a n s f e r r e di n 出eu n l r u s f e d c h a n n e lf r o ml e a k a g eb yc r y p t o g r a p h i ca l g o r i t h r n s i th a sm o r et h a nt w e n t yy e a r ss i n c ed e s 、v a sa d o p t e di n19 7 7 d e si s n t u s e f u li ns o m ef i e l d sb e c a u s eo fn e wa t t a c k s t h e r e f o r e ，r 巧n d a e la i g or i t h mw a s s e l e c t e db yn l s to ft h eu l l i t e ds t a t e sa st l l ea d v a n c e de n c r y p t i o ns t a n d a r d ( a e s ) i tw i l lb e c o m et h em o s tw i d e s p r e a db l o c kc i p h e rs t a n d a r d i ti sv e r y i m p o r t a n tt os t u d ya l l da n a l y z et h ep o p u l 耵c r y p t o g r a p h i ca l g o r i t m 1 nc h a p t e r 2 ，i td c s c r i b e sm a t h e m a t i c a lb a s i s ，p r i n c i p l e ，a r c h i 把c u r ea n dt h en o w o fc r y p t j o n f o rt h es e c u r i t yo fr 硒n d a e la l g o r i m m ，i nc h a p t e r3i td e a l sw i t hi t sw h o l e s t r u c t u r e i t ss t r u c t u r ei sal 【i i l do fn e ts t r u c t l 鹏i t sn r s ta n d6 n a lr o u n dw a sa l l c h a n g e d i ta j l a l y z e st h ed e s i g np r i n c i p l eo ft h esl a y e r t h epl a y e ra n dt h ek e y a d d i t i o n ，w h i c hi so fi m p o n a r l c et oi d c s i g nt h eb l o c kc i p h e l i nc h a p t e r4 ，a tf i r s ti td e s c r i b e sm ea l l a l y s i so fb l o c kc i p h e r i ti n c l u d e st h e k i n d so fa t t a c k s ，t h et w oa s p e c t so fa t t a c k sc o m p l e x i t ya n ds o m ea t t a c km e t h o d s t h e n ，出ef e s i s t a n c ea 叠a i n s ta i ih l o 啪a t t a c k si sd i s c u s s e d t h e s em e t h o d sa r e d i 矗e r e n t i a lc r y p t a n a l y s i s ，“n e a rc r y p t a i l a l y s i s ，s q u a r ea t t a c ka n di n t c 叩o l a t i o n a t t a c k f i n a i ly t h ec i p h e ra n di t si n v e r s eu s cd i h b r e n tc o m p o n e n t sp r a c t i c a l l y e l j m i n a t et h ep o s s i b i l i t yf o rt i l e 、v e a l ( k e y sa 1 1 ds e m i _ w e a kk e y sa se x i t i n gf o r d e s r 巧n d a e la l g o r i t w h i c hh a st h eg r e a tf e a t u r ei se a s y t oi m p l e m e n t 1 n c h a p t e r5 ，h o wt oi m p l e m e n ti nd s pe n v i m m e m i sd i s c u s s e d t h e r ei td e s c r i b e s t h et e c h n o l o g yo fd s pa n dt h ef l o wo fd s pp r o g r a m a t1 a s t ，t h em e t h o dt o o p t i m i z e 哪n d a e la l g o r i 血mw h e ni m p l e n l e m e di sg i v e n f o rt h eu s e ，i nc h a p t e r6 ，t l l em o d e lo nt l l eb a s eo fr 幻n d a e la l g o r i t h ma n d r s ai sg i v e n t h e n ，nd e s c r i b e sh o wt od e s i g nt h es o r w a r eo fac i p h e r c a r di n i i 刚n d l 加密算法的研究及其d s p 实现 d s pe n v i m 砌e n t ， k e y w o r d s ：t h e e n c r y p t i o na l g o r i m mr 巧n d a e l ； a d v a n c e d e n c r y p t i o n s t a i l d a r d ( a e s ) ；c r y p t a r l a l y s i s ；d s p ；t m s 3 2 0 v c 5 4 1 6 ；剐n d a e lk e ys c h e d u l e i i r u n d a e i 加密算法的研究及其d s p 实现 1 1 引言 第一章绪论 二十一世纪是一个崭新的信息化世纪。随着i n t e r n e t 的迅速发展，计 算机网络在众多领域得到了广泛应用，人们在分享网络给他们带来丰富信 息的同时，也期盼对重要信息的保护。网络上传输数据的机密性( 即数据 在传输过程中不能被非授权者窃取) 、完整性( 即数据在传输过程中不能被 非法篡改) 、有效性( 即数据不可被否认，抗否认性) 、防伪冒性等方面的 要求越来越高。尤其是在电信、金融、证券、保险、邮电、供电、商贸、 税务、电力、交通、电子商务、政府等领域的业务系统中，必须提供更好 的安全环境。主要的解决方法是保护信息安全和网络安全的问题。 目前，国内自主开发网络安全产品的品种较少。防火墙技术是一种被 动的防卫技术，加密技术作为一种主动的防卫手段其优势就显示出来了。 研究结果表明，对数据进行加密保护不仅能防止传输数据被敌埘者窃取， 而且还能对用户的身份进行鉴别，防止非法用户入侵网络，窃走网络中存 储的数据信息或破坏数据的完整性。因此，加密技术成了计算机网络中实 现信息安全保护的核心技术。 支持6 4 位6 6 mp c i 总线的高速加密卡的研究与开发是本年度重点支 持的基会项目之一，而算法的实现是加密卡的基础。针对这种现状，纵观 目前国内市场的加密卡，我们提出硬件软件相结合的实现思路，自行研制 基于p c i 接口的安全卡，并将美国t i 公司的t m s 3 2 0 v c 5 4 1 6 芯片作为该安 全卡的核心密码处理器，从而有效的维护系统的正常运作。该安全卡承担 了全部输入输出数据的加解密，在t m s 3 2 0 v c 5 4 1 6 上实现了r s a 、d e s 、m d 5 、 a e s 密码算法。同时采用i c 卡记录权限和身份，能防止越权操作和提供事 务认证。 然而算法的研究与实现是加密卡的基础。r i j n d a e l 算法以设计简单、 密钥设置快、存储要求低、安全性、简易性和灵活性的特点成为新的加密 标准。以r i j n d a e l 算法作为加密算法的加密卡的研究f 成为研究热点。 r q n d a e l 加密算法的研究及其d s p 实现 1 2 高级加密标准( a e s ) 的开发背景和过程 1 9 9 7 年4 月1 5 日，( 美国) 国家标准技术研究所( n i s t ) 发起征集高 级加密标准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 ) 的活动，目的是确定一 个非保密的、可以公开技术细节的、全球免费使用的分组密码算法，作为 新的数据加密标准，以弥补d e s 退出后，数据加密标准留下的空缺。 1 9 9 7 年9 月1 2 日，美国联邦登记处公布了正式征集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 会议上，研讨了全球各机构和个人对1 5 个候选算法的 分析结果，并于1 9 9 9 年8 月将候选名单减少为5 个，这5 个算法是l c 6 、 r i j n d a e l 、s e r p e n t 、t w o f i s h 和m a r s 。2 0 0 0 年4 月1 3 1 ，第三次a e s 会 议上，对这5 个候选算法的各种分析结果进行了讨论。2 0 0 0 年1 0 月2 日， n i s t 宣布了获胜者r i j n d a e l 算法。于2 0 0 1 年11 月2 6 日发布了正式 1 9 7 号标准a e s 标准，在f i p sp u b s l 9 7 川中指出了标准生效的具体时间 为2 0 0 2 年5 月2 6 日。 至此，历时几年的遴选过程宣告结束，并确定比利时研究者v i n c e n t r i j m e n 和j o a nd a e m e n 研制的r i j n d a e l 算法为新的数据加密标准a e s 。 1 3 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 攻击的新理论和研究结果作了分析和讨论。目前的攻 击方法主要包括强力攻击、差分密码分析、线性密码分析、s q u a r e 攻击和 r u n d a e i 加密算法的研究及其d s p 实现 插值攻击等。差分密码分析( d c ) 和线性密码分析( l c ) 是攻击迭代密码最有 效的方法，对其研究的比较深入；s q u a r e 攻击是针对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 算法的实现大多是测试性或实验性的，、尚未见正式的 商业产品。已经用软件方法如c 语言、j a v a 语言实现，如在文献 4 中用c 语言完整地实现了r i j n d a e l 算法，而文献 5 中在v c + 十6 o 环境下实现了 该算法。国内很多单位也在用硬件方法来实现该算法，在文献 6 中采用 x i l i n x 公司s p a r t a n i i 结构的f p g a 实现并行加速，给出了两种a e s 并行加 速方法，并提供了相应的a e s 速率的测试数据，而在文献 7 中介绍和讨论 基于f p g a 的硬件技术实现分组加密算法时所采用的4 种结构及其性能，同 时对5 种a e s 候选算法的软件实现和f p g a 实现的结果和性能进行比较分析。 1 4 本论文的研究意义 通信和计算机技术的发展极为迅速，个人移动通信、电子邮件、网上 证券交易、电子商务、电子政务等都给人们的生活、学习和工作带来了极 大的方便，这些也都使人们对信息的安全传输、安全存储和安全管理更加 关注。信息安全已经成为人们关注和研究的重要课题。 信息安全的研究包括密码理论与技术、安全协议与技术、安全体系结 构理论、信息对抗理论与技术、网络安全与安全产品等领域，其中密码算 法的理论与实现研究是信息安全研究的核心。信息安全的特性决定了密码 算法的研究和开发必须本土化，只有这样我们才能消除对密码算法存在陷 门的担心，确认密码算法的可靠性、安全性，才能用来保障通信与信息系 统的安全。 虽然a e s 已经生效，但市场上a e s 的商用产品尚不多见，因此很有必 要研究自主知识产权的a e s 产品，那么现在对高级加密标准的理论和实现 刚n d a c i 加密算法的研究厦其d s p 实现 进行探讨和研究就具有较大的理论和实践意义，为其在加密卡和加密机中 的应用做技术储备。 1 5 本论文的研究内容和目标 本论文主要从以下方面的内容进行研究： ( 1 ) r i j n d a e l 算法的设计原理； ( 2 ) r i j n d a e l 算法的安全性； ( 3 ) r i j n d a e l 算法的优化及d s p 实现； ( 4 ) 应用rij n d a e l 算法的一个加密模型； r ij n d a e l 算法的设计原理研究主要分析算法在设计时遵循的设计原则 及其采用的整体结构确定a e s 是否存在陷门；r i j n d a e l 算法的安全性能研 究给出了算法抵抗现有己知攻击的能力；r i j n d a e l 算法的优化及d s p 实现 主要研究仿真= e l = 境下的d s p 混合编程技术以及在结合算法的数学结构做优 化使实现速度加快；最后根据实际应用给出了一个r i j n d a e l 算法的加密模 型。 本文的研究目标是在d s p 芯片t m s 3 2 0 v c 5 4 1 6 上实现r i j n d a e l 算法， 运用f i p sp u b s1 9 7 提供的测试向量进行正确性测试和加密性能测试，对 其速度和安全性进行分析与验证，并对其经验加以总结提出优化原则，为 其在加密卡和加密机中的应用做技术储备。 4 r i j n d i 加密算法的研究厦其d s p 实现 第二章r i j n d a e i 算法概述 2 1 数学基础知识 在r i j n d a e l 算法当中，各种操作都定义为字节操作，各字节操作在有 限域 昂1 ( 2 8 ) 当中处理每一个元素。有限域的元素可以进行加平乘的运算， 不过这些运算有别于数字的加和乘。 这里我们介绍一些有限域当中的基本的数学知识。 2 1 1 有限域 有限域是有有限个元素的域元素个数称为域的阶。q 阶域存在当且仅 当日= p “，p 为素数并称为有限域的特征，有限域记为g f ( p ”) 。 r i j n d a e l 算法中涉及两类如下形式的特征2 域上的多项式 6 ( x ) = 6 7 x7 十白6 x 6 + 6 5 x 5 + 6 4 x 4 + 如x 3 + 6 2 x 2 + 6 i x + 6 0 ，6 6 f ( 2 ) ( 21 ) “( x ) = 口 x 3 + d 2 x 2 + 删+ d o ，d f g f ( 2 8 ) ( 2 2 ) 其中b ( x ) 表示算法中的单字节( b y t e ) 数据，a ( x ) 表示箅法中的4 字 节( 4b v t e s ) 或字( w o r d ) 数据。单字节也口j 以用数据向量 弘，6 。，6 ，6 。，屯，6 ：，6 1 ，如 或十六进制数扣 表示。 21 2 加 有限域中两个元素的加法是通过将这两个元素的多项式表示中的对应 幂的系数进行“加”取2 的模来实现的，可以用异或操作柬执行( 用。表示) ， 即lol = o ，l0 0 = 1 ，以及o oo = o 。因此，多向式减法和多项式加法相侧。 对于两个字节矗，d 。叱4 口，口：玎l 口o 和慨坑也6 。如6 ，“ ，和为 c 7 c 6 c 5 c 4 f ) c 2 c i c o 可描述为c j = d j0 6 ( 即c 7 = n 70 6 t c 6 = “60 6 6 ， c o = o o ) 。 例如，下列表达式彼此尾对应的： ( j6 +z 4 + x 2 + x + 1 ) + ( x7 + x + 1 ) = j 7+z6+x4+x 2 ( 多项式表示) 呲0 1 0 l l l of 1 0 0 0 0 0 儿) = l 1 0 1 0 1 0 0 j ( 二进制表示) ( 5 7 ) o 8 3 ) = = d 4 ( 十六进制表示) ( 5 7 ) o 8 3 ) _ d 4 ) ( 十六进制表示) r u n d a e l 加密算法的研究及其d s p 实现 2 1 3 乘 在有限域g f ( 2 8 ) 当中，两个多项式的乘积必须是一个度低于1 5 的多 项式。因为对于有限域来说，乘积必须由它本身限制低于8 。因此在r i j n d a e l 算法中应将两个多项式相乘的结果再对一个模为8 的不可约分多项式 m ( x ) = x 8 + x 4 + x 3 + z + l ( 用十六进制表示为： 0 1 1 b ) 取模。一个多项 式是不可约简即该多项式的除数只有1 和它自己。 下面我们举一个例子，给出计算过程如下： ( x6 +x4+x 2 + z + 1 ) ( 上7 + 工+ 1 ) = ( x 1 3 + x ”+ x 9+x8+x 7 ) + ( x7 +x5 + x 3 + x 2 + x ) + ( x 6 + x4+x2 + x + 1 ) = x 1 3 + x ”+ x 9 + x8 十x 6 十x 5 + x4+x3 + 1 之后 ( x 1 3 + x “+ x 9 + x 8 + x 6 + 工5 + z 4 + x 3 + 1 ) m o d ( x 8 + x 4 + x3 + z + i ) = x 7 + x 6 + l 即 5 7 ) 8 3 = f c l ) 。 可见，对m ( x ) 取模保证了得到的结果是一个度小于8 的_ 二进制多项式， 这样就可以用一个字节来表示。 但是，与加法不同的是在字节层里没有简单的操作与乘法相对应。 2 14 乘x 运算 在多项式( 2 1 ) 中定义乘以多项式x ，我们得到： 6 7 x 8 + 氏x7 + 6 5 x 6 + 6 4 x 5 + 6 3 x 4 + 6 2 x 3 + 6 l x 2 + 6 0 x ( 2 3 ) 然而要得到x 6 ( x ) 的计算结果还需要将上式对m ( x ) 取模。 或者，乘x ( 即 0 0 0 0 0 0 1 0 ) 或 0 2 ) ) 运算也可以通过字节级的左移紧跟一 个有条件的与 l b ) 进行比特异或来实现，通常用x t i m e ( ) 来表示。而与x 的 更高次幂相乘可以通过重复执行x t i m e ( ) 运算来实现。通过将中间结果相 加，与任何常数相乘也是可以被实现。 例如计算， 5 7 ) 1 3 ) - f e ，因为 5 7 0 2 ) = x t i m e ( 5 7 ) = a e ) ， 5 7 ) 0 4 = x t i m e ( a e ) ) = 4 7 ) ， f 5 7 ) - 0 8 ) = x t i m e ( 4 7 ) ) = 8 e ) ， 5 7 l 1 0 ) = x t i m e ( 8 e ) ) = 0 7 ， 因此， r u n d a e l 加密算法的研究及其d s p 实现 5 7 1 3 _ 5 7 ( 0 1 o 0 2 ) o l o ) = 5 7 o a e o 0 7 二 f e ) 。 2 。1 5 g f ( 2 8 ) 中的带系数多项式 在g f ( 2 8 ) 中多项式可以通过系数来定义。在r i j n d a e l 算法当中一个4 字节向量对应一个度数低于4 的多项式，向量 d ( x ) = 3 x3 + 口2 工2 + 口_ x + 口o ，口，g f ( 2 8 ) 和 6 0 ) = x3 + 屯x2 + 缸+ 6 0 ，6 j g f ( 2 8 ) 在g f ( 2 8 ) 当中的乘积为 c ( x ) ( c ( x ) = 口( x ) 6 ( x ) ) ，即 c ( z ) = c 6 x 6 + c 5 x5 + c 4 了4 + c 3 x3 + c 2 x 2 + c l x + c o ，c ，g f ( 2 ) 其中，c o = 。氏，q = q 6 0e 口o 。岛，c 2 = 口2 6 00 l 6 lo 吼。6 2 ， c 3 = d 3 6 0o 口2 6 lo 口l 6 2o 口o 6 3 ，c 4 = 口3 6 lo 以2 6 2o d l 6 3 ， c 5 = 口3 6 2 0 口2 6 3 ，c 6 = a 3 6 3 。 相应的，存在一个度为4 的模多项式m ( x ) 使得c ( 工) 的度小于4 。在 r i j n d a e l 算法当中，这个多项式是m ( x ) ；工4 + 1 。那么可得到a ( x ) 6 ( x ) 的 积d ( x ) ，县i j d ( x ) ：c ( x ) ( l o d x 4 + 1 ) = d 3 x 3 + d 2 x 2 + d l x + d o d o = d o 6 d o 3 6 l o 口2 6 2 0 口l 6 3 面= q 6 0 0 0 6 1 0 q 6 2 0 口2 6 3 d 2 = d 2 。6 0 0 d i 6 i o 。6 2 0 口3 6 3 d ，= d 3 6 0 0 d 2 6 i o 口1 6 2 0 口o 6 3 可以将上式写成矩阵的形式，得到 2 2 算法规范l s qd ：q f 6 。 口，a ：0 巨 口：口， 日。 口，06 ： 3口2口i d o j l 6 3 r i j n d a e l 算法是迭代分组密码，其分组长度和密钥长度都是可变的， 均可独立地设定为3 2 比特的任意倍数，最小为1 2 8 比特，最大为2 5 6 比 特。a e s 将分组长度固定为1 2 8 比特，支持1 2 8 、l 9 2 或2 5 6 比特的密 r u n d i 加密算法的研究及其d s p 实现 钥长度。 r i j n d a e l 算法的明文分组以及每次变换的中间结果分组叫作状态。状 态可以用字节的一个矩形阵列表示，该阵列有4 行，a e s 算法列数为4 列， r i j n d a e l 算法的列数等于分组长度除以3 2 。密钥类似地用一个4 行的矩形 阵列表示，列数记为n k 并且等于密钥长度除以3 2 ，n k 可为4 ( 1 2 8 b jt s ) 、 6 ( 1 9 2 b i t s ) 或8 ( 2 5 6 b i t s ) 。明文和密钥如图2 1 按照列优先的顺序映射到 状态矩阵中。 a 0a 4 a 8a 1 2 a la 5a 9a 1 3 a 2a 6a l o a 1 4 a 3a 7a l la 1 5 k 0k 4k 8k 1 2 k 1 k 5k 9 k 1 3 k 2k 6 k l o k 1 4 k 3k 7 k l ik 1 5 图2 1 状态矩阵和密钥矩阵 2 2 1 轮变换 r i j n d a e l 密码算法由3 部分组成，初始轮密钥加、n r l 轮、结尾轮。 根据密钥长度的不同，n r 取值如下表 k e yl e n g t h1 2 8 b i t s1 9 2 b i t s2 5 6 b i t s n r1 01 21 4 表z 1n r 值与密钥长度的对应关系 通常每一轮的轮函数由四个不同的可逆变换组成，即字节替代 ( 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 ) 变换。最后结尾轮的轮函数没有列混合( m i x c 。l u m n ) ，其余 相同。轮函数的伪码如图2 2 ，a e s 的算法结构如图2 3 所示。 刚n d a e l 加密算法的研究及其d s p 实现 k e y a d d i t i o n ( s t a t e ，r 0 u n d k e y ) f o r ( i = 1 ；i 6 ，有 七j 一mos ( r ( 一1 ) ) oc ，m 嵋一mo s ( w 1 ) 如果f 6 时密钥扩展算法的区别在于，当i 满足i4 是n k 的整数倍时，在异或之前，要把a e s 的s 一盒作用到形。的每个字节。 2 ，2 8 算法流程 r i j n d a e l 密码算法由3 部分组成，即初始圈密钥加、n r _ 1 圈和结尾圈， 其结构流程如下图2 8 所示。 i 状态篁全_ j 皿l 扩展密钥 j1 鳖k 竺箜梦 i - l 臣茎) n r1，l、状奎眨拳型兰皇一) 扩展密钥+ n b i l 竺查k 重弱， 圈2 8r ij n d a e l 算法加密流程图 刚n d a e i 加密算法的研究及其d s p 实现 2 3 小结 本章开始介绍了与r i j n d a e l 密码算法相关的数学基础知识，在此基础 上给出了算法的程序流程，并详细地给出了字节替代( b yl e s u b ) 、行移位 ( s h i n l i o w ) 、列混合( m i x c o l u m n ) 和轮密钥加( a d d r o u n d k e y ) 变换和密钥调 度算法及密钥扩展的具体过程。 4 r o n d a e i 加密算法的研究及其d s p 实现 第三章r ij n d a ei 算法设计原理及分析 3 1 r ij n d a e i 算法的设计原则 j o a nd a e m e n 和v i n c e n tr i j m e n 在设计r i j n d a e l 算法时遵循了- 一定 的设计原则7 l ，主要是 ( 1 ) 抵抗现有的所有的已知密码攻击； ( 2 ) 在各种平台上编码紧凑、运行速度较快，都具有良好的性能； ( 3 ) 设计简单。 在分析一个密码算法时，应该了解其设计原则。r i j n d a e l 算法的整体 结构的精心设计确保了算法的安全性，简单性和对称性确保了算法易于实 现。可见r i j n d a e l 算法遵循了安全性原则和易于实现原则。 3 2 r i j n d a e i 算法的整体结构 3 2 1 迭代分组密码的整体结构 设计现代实用密码算法时，为了有效的抵抗通用攻击，一般都遵循香 农( s h a n n o n ) 所提出的混乱原则和扩散原则。 混乱原则是指人们所设计的密码应使得密钥和明文以及密文之间的依 赖关系相当复杂，以至于这种依赖关系对密码分析者来既无法利用。 扩散原则是指人们所设计的密码应使得密钥的每一位数字影响密文的 许多位数字，以防止对密钥进行逐段破译，而且明文的每一位数字也应该 影响密文的许多位数字，以便隐蔽明文数字的统计特性。 现代实用分组密码算法通常采用轮函数多次迭代的结构，如果轮函数 设计适当，经过若干次迭代后就可以提供必要的混乱和扩散，这种分组密 码称为迭代分组密码。迭代分组密码采用的迭代方式虽然一致，但具体密 码算法的整体结构不一定相同。迭代分组密码的整体结构主要可分为二类， 一类是以d e s 、r c 5 、b l o w f i s h 、c a s t 一2 5 6 、d e a l 等为代表的f e i s t e l 网络 结构，另一类是以s q u a r e 、s a f f e r 、s h a r k 、s e r p e n t 为代表的替换置换 ( s p ) 网络结构。不采用这两种网络结构的算法可归结为第三类，比如f o r g 刚n d a e l 加密算法的研究及其d s p 实现 算法和 p c 算法。这三类结构中占主要地位的是第一、第一类。r i j n d a e l 算法采用的是s p 网络结构。 3 2 2 r i j n d a e i 算法的s p 网络结构 s p 网络结构是近几年来应用比较广泛的一种结构，它的结构非常清晰， 每一轮由s 层和p 层组成，其一轮加密过程如图3 1 所示。 田 工 l 竺竺兰i 图3 1 一轮s p 密码的加密过程 s p 型密码轮变换时，首先将s 层作用于轮输入使其混乱，然后再被p 层作用使之得到扩散。图3 1 中的子密钥放在s 层，在实际实现中子密钥 可放在其它位置。s p 型密码具有一个很大的优点：在明确了s 和p 层的密 码指标后，设计者就能从理论上估计s p 型密码抵抗差分密码分析和线性密 码分析的能力，此外，s p 型密码经一轮变换后其输入的每一位均得到扩散， 这表明s p 型密码比f e i s t e l 型密码的扩散速度更快，但s p 型密码的加、 解密结构通常不相似。 在r i j n d a e l 密码算法当中，组成其每一轮变换的4 个函数分属于s 层、 p 层和密钥加层。s 层通常称为非线性层，由一个b y t e s u b 变换或i n v b y t e s u b 变换组成，其作用是确保多轮迭代后的高度混乱；p 层也称为线性层，它包 括s h i f t r o w 变换和m i x c o l u m n 变换或i n v s h i f t r o w 变换和i n v m i x c o l u m n 变换，其作用是确保多轮迭代后的高度扩散；密钥加层由a d d r o u n d k e y 变 换组成，起到密钥控制的作用，即实现密钥与明文或密文的结合。 许多密码分析方法对迭代分组密码的第一轮和最后一轮的处理方法与 中间各轮不一样，一般是首先猜测几比特密钥，根据假定的密钥值和明文、 密文进行运算，然后剥去密码的第一轮和最后一轮，再将攻击施加于剩下 6 r u n d a e i 加密算法的研究及其d s p 实现 的轮上，因此有必要对第一轮和最后一轮做特殊处理。r i j n d a e l 算法在第 一轮之前加了一个密钥控制下的前期变换a d d r ou 1 d k e y 变换，对最后一 轮则改动了p 层，去掉了其中的m i x c ol u m n 函数，因此r i j n d a e i 算法在整 体结构上是种第一轮和最后一轮被特殊处理的s p 网络结构。 3 3 rij n d a ei 算法整体结构中的几点分析 3 3 1 s 层设计 s 层是唯一的非线性层，s 层设计的关键是s 盒的构造。s 盒的构造对 整个密码算法极为重要：一方面决定了算法抵抗差分和线性密码攻击的能 力，另方面在很大程度上也决定了算法是否存在陷门。 为了使用户相信算法不存在陷门，同时也便于s 盒的性能分析，s 盒 的构造一般采用人们熟悉的数学函数，以使人们相信算法不存在陷门。返 些数学函数包括指数函数和对数函数、有限域g f ( 2 ”) 上的逆映射、有限域 上的幂函数等。 r i j n d a e l 算法采用了有限域g f ( 2 8 ) 上的逆映射为基础来构建s 盒。有 限域g ，( 2 ”) 上的逆映射f 定义为 一黯i 。 出于该式过于简单，且存在两个不动点o 和l ，所以易受到插值攻击。 为此r i j n d a e l 算法设计者在有限域g f ( 2 8 ) 上的逆映射基础上复合了一个 g f ( 2 ) 上的可逆仿射变换f ，f 为b = f ( f ( a ) ) ，令a = f ( x ) ，则b = f ( a ) 。 其矩阵表示为 r u n d l 加密算法的研究及其d s p 实现 y o y l y 2 y 3 y 4 儿 y 6 ll ol o o 0 0 l0 il l1 11 11 1l 01 0 0 o 0 1o l0 l1 l1 11 il 01 0 0 y ，ii l111o o 该仿射变换虽然对非线性度没有影响 的两个不动点，增加了s 盒代数表达式的复杂性 击。 + 除了g f ( 2 8 ) 上的逆映射 从而能有效抵抗插值攻 3 3 2 p 层设计 p 层也称为线性层，在r i j n d a e l 算法当中包括了s h i f l r o w 和m i x c 0 1 u m n 变换，目的是提供雪崩效应，起到扩散的作用，其构造遵循了最佳分支数 的原则。这里就分支数的概念做一简要介绍。令a 为字节矢量，f ( 口) 表示 对字节矢量进行的f 线性变换，( 盯) 、( f 0 ) ) 分别表示字节矢量a 变换 前和变换后的非零字节数，则称b ( f ) = m i n 。( 0 ) + ( f ( d ) ) ) 为f 的分支 数。 在一个差分特征中，如果s 盒的输入差分不为零，则称s 盒是活动的； 在线性密码分析中，攻击者总设法寻找明文、密文及密钥之间的线性逼近， 在这个过程中如果某个s 盒的一些输入和输出比特被涉及，则称此s 盒是 活动的。而上述定义反映了字节矢量变换前后的非零字节数，而非零字节 数又决定了差分密码分析和线性密码分析中的活动s 盒数，线性变换p 的 分支数越大活动s 盒的数目也越大这就意味着进行差分密码攻击和线性 密码攻击所需选择的明文字节就越多，这丁f 好表明了字节剐的扩散比较充 分。 在r i j n d a e l 算法的设计中，设计者就遵循上面这条设计准则，采用了 最佳分支的原则来构造p 层：在p 层中，m i x c 0 1 u m n 变换将状念阵列中的 一个字节扩散到该字节所在列的每个字节中，s h i f t r o w 变换则将原来处在 同一列上的字节扩散到不同的列中。 k悄蒜 o o o 1 1 1 1 l 旦 o o 1 1 1 l l o ， r u n d a e i 加密算法的研究及其d s p 实现 根据分支数的定义，输入时刻的状态至少有一个非零字节，s h i f t i o w 变换并没有改变状态的非零字节数。因此并不影响p 层的分支数；而 rl j n d a e l 算法中的状态为4 行多列阵列，经过m i x c 0 1 u m n 变换后的一列最 多有4 个非零字节，所以r i j n d a e l 算法p 层的最佳分支数为5 ，达到了这 种设计的最大可能值。因此，r i j n d a e l 算法p 层的设计起到了很好的扩散 作用，提高了抵抗差分密码攻击能力，这种设计同时也可有效抗击截短差 分攻击和s q u a r e 攻击。 3 ，33 密钥加层设计 密钥加层由密钥扩展和轮密钥的选取两部分组成。密钥扩展考虑了效 率、消除对称、扩散、非线性性和不存在弱密钥等因素。 在r i j n d a e l 算法中，密钥扩展采用了滑动窗口技术，令表示经第t 7 久扩展后得到的值，女。表示给定的初始密钥，则可定义滑动窗口变换， ，rl 矿( 七卜1 ) ，l s r5 尺腑 = i 七o ，r = o 其中r 。取决于给定的初始密钥。 采用滑动窗口技术，可以从任意次扩展的结果得到整个轮密钥表， 有利于在加密和解密时实现密钥扩展。r i j n d a e l 算法的密钥扩展中， r i j n d a e l 算法整体结构中的几点分析没有对每位比特进行操作，而是按字 节操作，有利于在各种平台上的实现，同时也能提高密钥扩展的速度，达 到良好的效率。 考虑到与密钥有关的密码攻击，通过在密钥扩展中使用r o t w o r d 变换， 执行字节的循环移位，可以达到将初始密钥的差分特性有效地扩散到轮密 钥中的目的；使用非线性变换s u b w o r d ，使得密钥扩展具有了足够的非线性 度，从而为密钥扩展提供了高扩散性和混乱性，能够抵御密钥相关攻击。 r j j n d a e l 算法中，子密钥的选取比较简单。吐i 于在高级加密标准中指 定分组长度为1 2 8 比特，因此只要每轮取与之相对应的1 2 8 比特即可。 d e s 存在弱密钥和半弱密钥，而r i j n d a e l 算法却没有，因此其密钥编 排也具有很好的安全性。 1 9 r u n d a e i 加密算法的研究及其d s p 实现 3 4 小结 本章首先从设计原则的角度出发得出r i j n d a e l 算法遵循了安全性原则 和易于实现原则，然后r i j n d a e l 算法在整体结构上是一种第一轮和最后一 轮被特殊处理的s p 网络结构，最后对r i j n d a e l 算法整体结构中的s 层、p 层和密钥加层几个方面的设计要点做了简要分析。 r 嬲鑫搴l 加密冀法的辑霓及英d s p