（计算机系统结构专业论文）idea算法的研究及其变种的实现.pdf

摘要 随着信息与通信技术的飞速发展，信息安全、通信保密尤其是网络安全日益 受到了人们的重视。本文主要是对i d e a 算法的研究及其变种的实现。本研究具 有一定的理论意义和实用价值。密码技术是信息安全技术的核心，分组密码又是 密码领域的重点研究内容之一，它在保护数据在存储与传输过程中的安全性是其 它类型的密码所不能代替的。a e s 的诞生和欧洲n e s s i e 密码计划的启动，使 得国际上叉掀起了一次研究分组密码的新高潮。本文正是在这一研究背景下对本 课题进行了比较深入的探讨与研究。 在分组密码的参数中，分组长度r l 是必须考虑的一项重要参数，分组密码要 是安全的，其分组长度n 必须足够大，以使其能阻止对其进行统计分析。长的明 文分组在实现效率上还具有其优势，i d e a 算法的明文分组为6 4 比特，在现阶 段来看，其安全性是足够的，但是考虑到未来计算机科学的发展趋势，选择构造 1 2 8 比特的对合置换，并利用其设计分组长度为1 2 8 比特的秘密密钥分组密码体 制，对分组密码的发展有积极意义，是未来发展的一种趋势。 本文首先概括介绍了国内外分组密码的研究现状，同时对其发展趋势进行了 分析；其次，详细地探讨与分析了分组密码的主要理论与技术，其中对当前国内 外一些重要的分组密码进行了研究与分析：然后，在这些工作的基础上，去粗存 精，通过对i d e a 算法的研究，对其在理论上和实现上进行详细的分析，给出其 理论上的支持，分析其具体的代数结构。在i d e a 算法的基础上，提出了两种方 案来构造单向散列函数，结合双密钥体制，在传输明文信息时，通过消息摘要， 实现了一种认证和数字签名的方案。在m a 结构的基础上提出了一种对合置换， 对其性质进行简要分析，在此基础上提出一种新的分组密码体制，并试验性的将 其应用到s s l 安全代理服务器中来验证其实用性。 关键词：秘密密钥分组密码体制，i d e a 算法，m a 结构，对合置换，h a s h 函数 a b s t 卧c t w i t l lt h e r a p i dd e v e l o p m e n t o fi n f o r m a t i o na n dc o m m u n i c a t i o nt e c h n o l o g y , p e o p l e a t t a c hm o r e i m p o r t a n c e t ot h e i n f o r m a t i o n & c o r r e s p o n d e n c es e c u r i t y , e s p e c i a l l yt on e t w o r ks e c u r i t y t h ed i s s e r t a t i o nr e s e a r c hm a i n l yi d e a a n dr e a l i z eo f i t sm u t a t i o n t h e a p p r o a c h h a st h e o r e t i c a ls i g n i f i c a n c e ，a n dh a sb e t t e rp r a c t i c a lv a l u e s f o ri n f o r m a t i o n ，c o m m u n i c a t i o na n dn e t w o r ks e c u r i t y c r y p t o g r a p h yt e c h n o l o g yi st h e c o r eo fi n f o r m a t i o ns e c u r i t y , a n db l o c kc i p h e ri so n eo fm o s ti m p o r t a n tr e s e a r c hi n c r y p t o g r a p h y , i t ss e c u r i t y , w h i c hp r o t e c t s d a t as t o r a g ea n dt r a n s m i s s i o n ，c a n tb e r e p l a c e db yo t h e rt y p e so fc i p h e r s t h eb o r no f a e sa n dt h el a u n c h i n go fn e s s i e p r o j e c t , b r i n g an e wc l i m a xo f b l o c k c i p h e rr e s e a r c ha l lo v e r t h ew o r l d s o ，t h et h e s i s s t u d i e sa n dd i s c u s s e st h es u b j e c td e e p l ya tt h i sr e s e a r c hb a c k g r o u n d i nt h ep a r a m e t e r so fb l o c kc i p h e r , b l o c kl e n g t h1 1i sa ni m p o r t a n tp a r a m e t e rt h a t m u s tb ec o n s i d e r e d t om a k eb l o c kc i p h e rs e c u r i t y , b l o c kl e n g t hnm u s tb el o n g e n o u g ht op r e v e n t i tf r o m b e i n g s t a t i s t i c a l a n a l y s i s l o n g e r b l o c k l e n g t h h a s a d v a n t a g e a tr e a l i z i n ge f f i c i e n c y , p l a i nt e x to f i d e ai s6 4 b i t s ，a t p r e s e n t ，i t ss e c u r i t yi s e n o u g h ，b u tc o n s i d e rt h ed e v e l o p m e n tt r e n do fc o m p u t e rs c i e n c ei nt h ef u t u r e ，i th a s p o s i t i v em e a n i n g sf o rt h ed e v e l o p m e n to fb l o c kc i p h e rt o c o n s t r u c ta ni n v o l u t i o n p e r m u t a t i o nw i t l l1 2 8 b i t sl o n ga n dt ou t i l i z ei td e s i g nas e c r e t - k e yb l o c kc i p h e rw i t h 12 8b i t sl o n g i ti sd e v e l o p m e n tt r e n d si nt h ef u t u r e f i r s t , t h et h e s i s i n t r o d u c e s s u m m a r i l yt h e s t a t u s q u o o fb l o c kc i p h e r , a n d a n a l y z e si t sd e v e l o p m e n tt r e n d s e c o n d ，i ta p p r o a c h e s t h em a i n t h e o r ya n dt e c h n o l o g y o f b l o c kc i p h e r , a n da n a l y z e ss o m ei m p o r t a n tb l o c k c i p h e r s a n dt h e n ，i tb a s e d o nt h e a b o v ed i s c u s s i o n ，d i s c a r dt h ed r o s sa n ds e l e c tt h ee s s e n t i a l ，t h et h e s i sa p p r o a c h e dt h e m a i n t h e o r ya n dt e c h n o l o g yo fi d e a ；p r e s e n t e d t w os c h e m e s o f u s i n g i d e a g r o u p i n g c i p h e ra r i t h m e t i ct ob u i l dh a s h i n gf u n c t i o na n dw i t hd o u b l ek e ys y s t e mt o a c h i e v e i d e m i t ya u t h e n t i c a t i o na n dd i g i t a ls i g n a t u r e ；c o n s t r u c t e da ni n v o l u t i o np e r m u t a t i o n w i t l l1 2 8b i t sl o n gb yu s eo f t h em a - s t r u c t u r ei ni d e a ，s i m p l ya n a l y s e si t sp r o p e r t i e s a n d p r e s e n t sa n e w s e c r e t - k e yb l o c kc i p h e rb a s i n g t h ei n v o l u t i o np e r m u t a t i o n k e yw o r d ：s e c r e t - k e yb l o c kc i p h e r ，i d e a ，m a - s t r u c t u r e ，i n v o l u t i o np e r m u t a t i o n ， h a s h - f u n c t i o n l j 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：刍垒1 日期：l 。5 年月2 日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名： 刍幺2 i d e a 算法的研究及其变种的实现 第一章引言 随着信息与通信技术的飞速发展及其应用，信息安全与通信保密日益受到人 们的重视，它的内涵也在不断的延伸，从最初的保密性发展到完整性、可用性、 可控性和不可否认性，进而又发展为“攻( 攻击) 、防( 防范) 、测( 检测) 、控( 控制) 、 管( 管理) 、评( 评估) ”等多方面的基础理论和实旋技术。信息安全是一个综合、 交叉学科领域，它要综合利用数学、物理、通信和计算机诸多学科的长期知识积 累和最新发展成果，进行自主创新研究，加强顶层设计，提出系统的、完整的， 协同的解决方案。 1 1 密码学概述 密码( 学) 技术是信息安全技术的核心，它主要由密码编码技术和密码分析 技术两个分支组成。密码编码技术的主要任务是寻求产生安全性高的有效密码算 法和协议，以满足对消息进行加密或认证的要求。密码分析技术的主要任务是破 译密码或伪造认证信息，实现窃取机密信息或进行诈骗破坏活动。这两个分支既 相互对立又相互依存，正是由于这种对立统一关系，才推动了密码学自身的发展。 目前人们将密码理论与技术分成两大类，一类是基于数学的密码理论与技术，包 括分组密码、序列密码、公钥密码、认证码、数字签名、h a s h 函数、身份识别、 密钥管理、p k i 技术、v p n 技术等；另一类是非数学的密码理论与技术，包括 信息隐藏、量子密码、基于生物特征的识别理论与技术等。 密码算法大体可分为两大类：秘钥( s e c r e tk e y ) 或分组密码算法，其中对加 密和解密这两个过程使用同一密钥；以及公钥或非公开密钥密码算法算法，其中 一个密钥用来加密，另一个用来解密。现在，标识发送方、认证和不可抵赖性 ( n o n - r e p u d i a t i o n ) 与信息隐藏一样重要。 1 1 1 分组密码加密算法 分组密码算法有时又叫对称密码算法，就是加密密钥能够从解密密钥中推算 出来，反过来也成立。在大多数对称算法中，加密解密密钥是相同的。这些算法 也叫秘密密钥算法或单密钥算法，它要求发送者和接收者在安全通信之前，商定 一个密钥。对称算法的安全性依赖于密钥，泄漏密钥就意味着任何人都能对消息 进行加密解密。只要通信需要保密，密钥就必须保密。对称算法的加密和解密表 i d e a 算法的研究及其变种的实现 示为： e k ( m ) = c d k ( c ) = m 对称算法可分为两类。一次只对明文中的单个位( 有时对字节) 运算的算法 称为序列算法或序列密码。另一类算法是对明文的一组位进行运算，这些位组称 为分组，相应的算法称为分组算法或分组密码。现代计算机密码算法的典型分组 长度为6 4 位一一这个长度大到足以防止分析破译，但又小到足以方便作用。 这种算法具有如下的特性： d k ( e k ( 1 v 0 ) = m 常用的采用对称密码术的加密方案有5 个组成部分( 如图1 1 所示) ： 图1 1 使用对称算法的加密和解密 ( 1 ) 明文：原始信息。 ( 2 ) 加密算法：以密钥为参数，对明文进行多种置换和转换的规则和步骤， 变换结果为密文。 ( 3 ) 密钥：加密与解密算法的参数， ( 4 ) 密文：对明文进行变换的结果。 ( 5 ) 解密算法：加密算法的逆变换， 为明文。 直接影响对明文进行变换的结果。 以密文为输入、密钥为参数，变换结果 对称密码术的优点在于效率高( 加解密速度能达到数十兆秒或更多) ， 算法简单，系统开销小，适合加密大量数据。 尽管对称密码术有一些很好的特性，但它也存在着明显的缺陷，包括： ( 1 ) 迸行安全通信前需要以安全方式进行密钥交换。这一步骤，在某种情况 下是可行的，但在某些情况下会非常困难，甚至无法实现。 i d e a 算法的研究及其变种的实现 ( 2 ) 规模复杂。举例来说，a 与b 两人之间的密钥必须不同于a 和c 两人 之间的密钥，否则给b 的消息的安全性就会受到威胁。在有1 0 0 0 个用户的团体 中，a 需要保持至少9 9 9 个密钥( 更确切的说是1 0 0 0 个，如果她需要留一个密 钥给他自己加密数据) 。对于该团体中的其它用户，此种倩况同样存在。这样， 这个团体一共需要将近5 0 万个不同的密钥! 推而广之，9 个用户的团体需要n 2 2 个不同的密钥。 通过应用基于对称密码的中心服务结构，上述问题有所缓解。在这个体系中， 团体中的任何一个用户与中心服务器( 通常称作密钥分配中心) 共享一个密钥。 因而，需要存储的密钥数量基本上和团体的人数差不多，而且中心服务器也可以 为以前互相不认识的用户充当“介绍人”。但是，这个与安全密切相关的中心服 务器必须随时都是在线的，因为只要服务器一掉线，用户间的通信将不可能迸行。 这就意味着中心服务器是整个通信成败的关键和受攻击的焦点，也意味着它还是 一个庞大组织通信服务的“瓶颈”。 1 1 2 公开密钥密码算法 非对称密码体制提供的安全性取决于难以解决的数学问题，例如，将大整数 因式分解成质数。公钥系统使用这样两个密钥，一个是公钥，用来加密文本，另 一个是安全持有的私钥，只能用此私钥来解密。也可以使用私钥加密某些信息， 然后用公钥来解密，而公钥是大家都可以知道的，这样拿此公钥能够解密的人就 知道此消息是来自持有私钥的人，从而达到了认证作用。 加密和解密都需要共享一个秘钥，这可能是分组密码体制的主要弱点。在非 对称密码算法或公钥密码算法中没有这样的问题。使用在数学上相关的两个密 钥，并通过用其中一个密钥加密的明文只能用另一个密钥进行解密的方法来使用 它们。通常，其中一个密钥由个人秘密持有，因此几乎没有必要共享密钥，从而 避免了对安全性的威胁。第二个密钥，即所谓的公钥，需要让尽可能多的人知道。 加密解密过程可以双向进行。即，我可以使用您的公钥加密某个信息以确 保只有您可以使用您的私钥来读取它。另外，还可以使用我的私钥来加密某个信 息，尽管从信息隐藏的观点来看，这是没有意义的实践一因为知道我公钥的任 何人都可以解密该消息，一但这是认证系统的基础，其确保了消息确实来自知道 我私钥的人那里，推测起来就是我。 本文主要是对分组密码进行研究，对公开密钥密码算法不再进行过多的阐 述。 i d e a 算法的研究及其变种的实现 1 2 国内外分组密码的研究现状及其发展趋势 在密码( 学) 技术中，数据加解密技术又是其核心。根据数据加解密所使用的 密钥的特点可将数据加解密技术分成两大类，一是基于单密钥的对称密码体制 ( 传统加密体制) ，它包括分组密码与序列密码；另一类是基于双密钥的公钥密码 体制。本章主要介绍目前国内外分组密码理论与技术的研究现状及发展趋势。 1 2 1 国内外主要的分组密码 美国早在1 9 7 7 年就制定了自己的数据加密标准：d e s 。随着d e s 的出现， 人们对分组密码展开了深入的研究和讨论。现已有大量的分组密码。如d e s 的 各种变形、i d e a 算法、s a f e r 系列算法、r c 系列算法、s k i p j a e k 算法、f e a l 系列算法、r e d o c 系列算法、l o k i 系列算法，c a s t 系列算法、k h u f u 、k 妇f r e 、 m m b 、3 ，a y 、t e a 、m a e g u f f m 、s h a r k 、b e a r 、u o n 、c a 1 1 、c r a b 、 b l o w f i s h 、g o s t 、s q u a r e 、m i s t y 、r i j n d a e l 算法、a e s1 5 种候选算法( 第 一轮) 以及n e s s i e 17 种候选算法( 第一轮) 等。 1 2 2a e s ( a d v a n c e de n c r y p t io ns t a n d a r d ) n i s t ( 美国国家标准技术研究所) 在1 9 9 7 年1 月2 日正式宣布了n s t 计划，该计划公开征集和评估新的数据加密候选标准( 新的标准称之为a e s ) 。作 为进入a e s 程序的一个条件，开发者必须承诺放弃被选中算法的知识产权。 a e s 密码算法的基本要求是：必须( 至少) 支持1 2 8 b i t s 分组加密，支持 1 2 8 1 9 2 2 5 6 b i t s 密钥( 密钥空间分别为3 4 x 1 0 3 8 6 2 x 1 0 5 1 i x 0 7 7 个密钥) ，比三 重d e s 快、至少与三重d e s 一样安全。n i s t 的评判规则大体可分为三大部 分：安全性、代价、算法实现特性。 ( 1 ) 安全性：评判算法的最重要因素，它包括：算法的抗分析能力( 抗破译能 力) 、稳固的数字基础、算法输出的随机性、与其它算法的对比特性； ( 2 ) 代价：是指授权合法使用的代价，在多种平台上的计算效率( 速度) ，占 用存储器数量； ( 3 ) 算法实现特性：指灵活性、软硬件兼容性、简单性。 根据上述评判规则，n i s t 对所有的候选算法进行了综合评判： ( 1 ) 1 9 9 8 年8 月2 0 日n i s t 召开了第一次a e s 候选会议，并公布了1 5 个官方a e s 候选算法：r i j n d a e l 、m a r s 、r c 6 、s e r p e m 、t w o f i s h 、s a f e r + 、 i d e a 算法的研究及其变种的实现 c a s t - 2 5 6 、c r y p t o n 、e 2 、l o k i 9 7 、d e a l 、m a g e n t a 、f r o g 、d f c 、h p c 。 根据研究和分析的结果，前9 种算法都有很好的安全性，而后6 种相对于前9 种而言存在有一些设计上的缺陷。表1 2 简要概括了这1 5 个分组密码的背景、 整体结构、设计特点及其有效性。 ( 2 ) 1 9 9 9 年8 月，n i s t 从中筛选出了5 个候选算法。它们是：r i j n d a e l 、 m a r s 、r c 6 、s e r p e n t 、t w o f i s h 。人们为了比较出最终算法发表了许多论文，公 布了大量的统计数据，每个算法都有它的优点和弱点。 ( 3 ) 2 0 0 0 年1 0 月2 日，n i s t 宣布获胜者为r i j m a d ( 发音为：“r a i nd o l l ) 算法，它的开发者是比利时密码专家v i n c e n t r i j m e n 和j o a n d a e m e n 。r i j n d a e l 的原形是s q u a r e 密码算法。它的设计策略是宽轨迹策略( w i d et r a i ls t r a t e g y ) ， 这种策略是针对差分密码线性密码分析提出的，它的最大优点是可以给出算法 的最佳差分特征的概率以及最佳线性逼近的偏差的界，由此可以分析算法抗击差 分分析及线性分析的能力。r i j n d a e l 是一个迭代分组密码，其数据分组与密钥长 度都是可变的。但为满足a e s 的要求，分组长度为1 2 8 b i t s ，密钥长度为 1 2 8 1 9 2 2 5 6 b i t s ，相应的轮数为1 0 1 2 1 4 。 ( 4 ) 2 0 0 1 年1 1 月2 6 日，n i s t 正式公布了新标准a e s ，其编号为f i p s p u b s l 9 7 。 表1 - 1a e s 第一轮的1 5 个候选算法 算洼田宣x q _ l整体路梅主要设计特点 有簸性搜仝性l r i j a - a - db i 咖i 为s h 鲳 宽孰瞳蕾睹s 国。爿o f 矿j 中的m “j 对当前的密码分析是壹垒的 m a l l su s a i b m 矗 非半茧的r i - 时 s - l a a a ( 髓机产生并测试j对当前的密码分析是兔痰的 r c 6u s a正广j 【f c 虹d基于盎掘拽捌的惦耳磐也 耐当前的密码分析是宣全的 s , , p a d u 勒_ r 艚q t 葛爱 s ph 蝽 共1 i i 于t 匝s 的$ 4 1 0 *对当前的躺分析是安生的 t w e 恼bu s 量笪 ，f c 自电l 可变的窖- | 珥与密例榴美j良好的安全惶 s f e 珥u s a 葛军 s p 时绪基于拊数和对敷的宁节运算对当前的密码分析是宣皇的 c a f f f - 2 5 6c s d s 嚣嚣 广j 【f c 自t d束一币同群的橱合运算s - b e a对当帅的密羁分析是壹全的 c r y p t o nr m x 盯一 乙主 s ，m 蠕宁节艳阵变攘s - b e t对当前的密码分圻是壹垒的 e 2 j s p s n 毫r d - d代替置换h 鲳窖b 嵋 对当前的密码分析墨兔疫的 l o k i9 7a u d n t s 适萏鼬融s h x 脆弱的安垒性 d e a lc a m d s 譬苎 6 y 出m l 重用d r ：& s - 日l a x脆弱的安全性 m 。孽n -g 村- m d ?芽斡 6 毫- p d - 吐 荽于快速p h t ( 。嗳选弓。变换j 脆弱的壹全性 f r o gc o ，- r i e , 五 非f c b d 结构姬过由部密制隐蕞六鼬分的爿算过程差的安生性 n f cf 删 h p cu s 墓 8 - 融d 墓子v m 锄i y 的拄帽关攻击技术 的 黏r e ( 5 1 2 b i 喀可避的二掘密制】 差的安全性 差的安全性 i d e a 算法的研究及其变种的实现 1 2 3n e s s i e ( n e we u r o p e a ns c h e m e sf o rs i g n a t u r e s i n t e g ri t y a n de n c r y p tio n ) 继美国征集a e s 结束之后，欧洲也开始进行称为n e s s i e 的密码大计划， 其主要目的是为了推出一系列安全的密码模块；另一个目的是保持欧洲在密码研 究领域的领先地位，并增强密码在欧洲工业中的作用。与a e s 相比，n e s s i e 涉 及的范围更广，不仅征集了分组密码，而且还征集序列密码、公钥密码、数字签 名、消息认证码以及杂凑函数。整个运作过程也是公开透明的，2 0 0 0 年3 月公 布了征集通告，2 0 0 0 年1 1 月1 3 - 1 4 日召开第1 次n e s s i e 会议，并公布了 征集到的所有算法。n e s s i e 共收到了】7 个分组密码，按照分组长度分为四部 分。表1 3 简要概括了这1 7 个分组密码的背景、整体结构、设计特点及其有 效性。从表中可以看出，日本提交了5 个算法，是递交数量最多的国家，这一 点显示了日本在分组密码领域的研究是非常活跃的。与a e s 的1 5 个候选算法 相比，n e s s i e 的1 7 个候选算法的设计比较单一，没有多少新思想，受a e s 的 影响比较大，整体结构主要采用f e l s t e l 变换与s p 网络，非线性主要靠s - 盒 来实现。 表1 2n e s s l e 的1 7 个分组密码候选算法 辣d ：霹象 b l k l 整体持均土嚣设汁特点 打效性f 加密遮瞳) c s t l i h t r f r a n c e 6 4 b i t s p 牌蠕 使逑尚u d c ，屯慢，m ns , - s o xg m b i t 坷p c a t i l l m l 3 3 ) i l i e r k r y p t - l ! j a p a n t a 4 h i t 蚌窝：i j ：s p1 4 捧 s - b e z t 3 9 m 你俨c 训打1 甥n i d e a s h i t z e r l i t l _ d 6 4 bj t c s p 旧维_ ：r i 爿 l ! 曲橱舟逆算s b e i3 i m b 州l h i “u m m 6 ) k h - 1 - d b r o i lb c l g j l u 阳 6 4 b h s p 维蹙轧墟谁培s - b o s6 ，7 m b h _ n ) e n d u r e s _ ) m i s t y l j a p a n 6 4 b i t 琏叫文皓枷s b o x 2 0 m h h 自( p c m i u m k l 0 ) h 堋b mb r a z i l 6 4 b i t , , s p 脚臻艉浓扣j 婶j 攫逆尊3 1 l b i 州l a t l u m l 帕j a 口a 略 b r z i l b e l g i u m 1 2 # b l t , s p 帑赶驴i 瞳笮略s b o i c a m d t i = j _ 口- d 【煞b h f c i q c i4 十叶、 0 帕s b o x g r n a dc r n i h q g j u m i2 8 b a t x s ph 蚺幺垃安龟砖，s - b o x h c r o c d p t - 3j a p m u 1 2 8 b i t s p 附播s - b o x n o t k e , e n l i e i g j n m i ：s b j “s pl 目t 矗t i l l s l i c e s b o x q u s a12 8 b i t x s p 州蚺h 沁s i i 曲，s - b o x s c 2 0 0 0 j a p 。h l ! s b j s s ，i l *s b o l s i t c a l g e m p l u s c o m p a n y i “l h t “ 1 丛禁；蠡蚋艟知艇拙 n u h l t 砒，j i r “a b l e s pl q 帑祚砷地辩淞舟 i t c 矗u s a v a l i a h t e f 翟f c i 嗵c l啦，是拙 ；窜4 饿船_ l 毒 濞i r e i t + n m n 加r l a n d * = u l a n e s p 碍 #s b o x 晶；：耐饥k i ! j 耳州l 般1 2 # ? 1 9 2 止5 6 ：c a m c t l i a ，s c 2 0 0 0 n u s i l ：1 2 8 ：l d i l - t k h a z a d m i s ly 1 。nj n l b d s n o r k c o n ； s i i c a l ：1 2 冀、5 1 2 ：3 2 n ( 4 。- n ：1 帅：a a 口b j ：1 ) j s c r e t j o n # i ：t ，k c 6 ：n a f e t 一：1 2 i ( 1 2 肌5 6 6 i d e a 算法的研究及其变种的实现 1 2 4 分组密码的分析 在分组密码设计技术发展的同时，分组密码分析技术也得到了空前的发展。 已有很多分组密码分析技术，如强力攻击( 穷尽密钥搜索攻击、字典攻击、查表 攻击、时间存储权衡攻击) 、差分密码分析、差分密码分析的推广( 截段差分密码 分析、高阶差分密码分析、不可能差分密码分析) 、线性密码分析、线性密码分 析的推广( 多重线性密码分析、非线性密码分析、划分密码分析) 、差分线性密码 分析、插值攻击、密钥相关攻击、能量分析、错误攻击、定时攻击等。穷尽密钥 搜索攻击是一种与计算技术密不可分的朴素密码分析技术，也是最常用的一种密 码分析技术。d e s 一经公布人们就认为它的密钥太短，仅为5 6 b i t s ，抵抗不住 穷尽密钥搜索攻击，事实已证明了这一点。1 9 9 7 年1 月2 8 日，美国的r s a 数据安全公司在r s a 安全年会上悬赏一万美金破译密钥长度为5 6 b i t s 的d e s 算 法。美国克罗拉多州的程序员v e r s e r 从1 9 9 7 年3 月1 3 日起，用了9 6 天的 时问，在i n t e m e t 上数万名志愿者的协同工作下，于1 9 9 7 年6 月1 7 日用穷 尽密钥搜索方法成功地找到了d e s 的密钥。这一事件表明依靠i n t e m e t 的分布 式计算能力，用穷尽密钥搜索攻击方法破译d e s 已成为可能。1 9 9 8 年7 月1 7 日，e f f ( 电子边境基金会) 使用一台2 5 万美元的电脑用穷尽密钥搜索攻击方法在 5 6 小时内破解了5 6 b i t s d e s 。1 9 9 9 年，在r s a 的会议期间，e f f 在不到2 4 小 时的时间里用穷尽密钥攻击方法找到了一个d e s 密钥。可见，寻找d e s 的替 代者已刻不容缓。 1 3 分组密码的重点研究方向 a e s 与n e s s i e 活动的相继启动，以及日本等一些发达国家也不甘落后地 启动了相关标准的征集和制定工作使得国际上又掀起了一次研究分组密码的新 高潮。同时国外如美国为适应技术发展的需求也加快了其它密码标准的更新f 如 s h a 一1 和f i p s l 4 0 1 ) 。我国在国家8 6 3 计划中也将制定密码的标准化问题列入 了议程。今后，分组密码的重点研究方向为： ( 1 ) 新型分组密码的研究： ( 2 ) 分组密码的实现研究，包括软件优化、硬件实现和专用芯片等； ( 3 ) 用于设计分组密码的各种组件的研究； ( 4 ) 分组密码安全性综合评估原理与准则的研究； ( 5 ) a e s 和n e s s i e 分组密码的分析及其应用研究。 i d e a 算法的研究及其变种的实现 分组密码理论研究主要包括： ( 1 ) 置换理论； ( 2 ) 分组密码安全评估： ( 3 ) 分组加密网络的伪随机性和超伪随机性； ( 4 ) 非平衡分组密码网络设计； ( 5 ) 专用于i c 卡的快速硬件加密体制等内容。 1 4 章节安排 第一章介绍了本课题的背景和一些情况，介绍了密码学的概况以及国内外分 组密码研究的现状； 第二章介绍了密码学的一些基本理论和技术，以便研究能够深入进行； 第三章详细介绍了几种常见的f e i s t e l 结构的分组加密算法； 第四章深入分析了i d e a 算法的实现原理，算法流程，算法的实现，以及它 的安全性： 第五章在i d e a 算法的基础上，提出了两种方案来构造单向散列函数； 第六章详细阐述了i d e a 算法的核心部件m a 结构，在m a 结构的基础上提 出了一种对合置换，并在次基础上提出一种新的分组密码体制； 第七章介绍了新的分组算法的实现以及该算法在k s s l 安全代理服务器中的 应用； 第八章是测试： 第九章对本文进行的总结； 最后是致谢和参考文献。 1 d e a 算法的研究及其变种的实现 第二章分组密码的理论和技术 2 1分组密码的抽象描述 用抽象的观点来看，分组密码就是一种满足下列条件的映射e ：f 2 0 s k f 2 ：对每个k s k ，e ( ，k ) 是从f 2 “到f 2 “的一个置换。可见，设计分组 密码的问题在于找到一种算法，能在密钥控制下从一个足够大且足够“好”的置 换子集含中，简单而迅速地选出一个置换。一个好的分组密码应该是既难破译又 容易实现，即加密函数e ( ，k ) 和解密函数d ( ，k ) 都必须容易计算， 但是至少要从方程y = e ( x ，k ) 或x = d ( y ，k ) 中求出密钥k 应该是一 个困难问题。 2 2 分组密码的设计原理 2 2 1 混乱和扩散 s h a n n o n 提出了两种隐藏明文消息中冗余度的基本技术：混乱和扩散。该原 理至今仍是分组密码算法的设计基石，同时也是密码工作的设计标准。 、混舌l ( c o n f u s i o n ) 用于掩盖明文与密文之间的关系。这可以挫败通过研究密文 以获取冗余度和统计模式的企图。做到这一点最容易的方法是通过“代替 f s u b s t i t u t i o n ) ”，一个简单的代替密码，如凯撒移位密码，其中每一个确定的明文 字符被一个密文字符所代替。现代的代替密码更复杂：一个长的明文分组被代替 成一个不同的密文分组，并且代替的机制随明文或密钥中的每一位发生变化。这 种代替也不一定就够了，德国的恩尼格马是一个复杂的代替算法，但在第二次世 界大战中就被破译了。利用差分与线性分析的策略，攻击者可以揭示明文、密文 和密钥三者之间的关系，而混乱则可以隐藏明文、密文和密钥之间的任何关系。 好的混乱使得复杂甚至强有力的密码分析工具都不能有效。 扩散( d i f f u s i o n ) 通过将明文冗余度分散到密文中使之分散开来。即将单个明 文或密钥位的影响尽可能扩大到更多的密文中去。这样就隐藏了统计关系同时也 使密码分析者寻求明文冗余度将会更难。产生扩散最简单的方法是通过换位( 也 称之为“置换( p e r m u t a t i o n ) ”o 一个简单的换位密码如列换位体制，只简单地重 新排列明文字符。现代密码也有这种类型的置换，但它们也利用其它能将部分消 息散布到整个消息的扩散类型。 i d e a 算法的研究及其变种的实现 仅使用混乱对安全性来说应是足够的，问题是需要很大的存储空间来存储密 钥相关表( 如对6 4 b i t s 明文到6 4 b i t s 密文的密钥相关表则需1 0 2 0 b y t e s 的存储 空间，更不用说1 2 8 b i t s 的密钥相关表了) 。分组密码算法的设计就是用较少的 存储空间来创建这样大的表。因此，分组密码一般既用到混乱又用到扩散( 通常 单独用扩散则易被攻破) 。技巧是在一个密码中以不同的组合方式多次混合使用 混乱和扩散( 用更小的表) 。有时由代替和置换层构成的分组密码被称为“代替 置换网络”或s p 网络。 2 2 2f e is t e l 网络及其结构 f e i s t e l 提出可以用乘积密码的概念近似简单的代替密码。乘积密码( p r o d u c t c i p h e r ) 就是以某种方式连续执行两个或多个密码以使得所得到的“乘积”从密码 编码的角度讲比其任意一个组成密码都更强。特别地，f e i s t e l 提出用代替和置 换交替的方式构造密码。实际上，这就是基于上述的s h a n n o n 的混乱和扩散原 理。值得注意的是：f e i s t e l 网络是基于s h a n n o n1 9 4 5 年的设想提出的，而现在 正在使用的几乎所有重要的分组密码都使用这种结构。其结构如下图： 1 0 i d e a 算法的研究及其变种的实现 图2 - 1f e i s t e l 网络 图2 1 给出了f e i s t e l 提出的结构。加密算法的输入是一个长度2 w 比特 的明文分组和一个密钥k ，明文分组被分为两个部分l 0 和r o 。数据的这两个 部分经过n 轮的处理后组合起来产生密文分组。每一轮i 以从前一轮得到 i d e a 算法的研究及其变种的实现 的“1 和融1 为输入，另外的输入还有从总的密钥k 生成的子密钥i c i 。一 般来说，子密磁不同于k ，它们彼此之间也不相同。 每一轮的结构都一样。对数据的右边一半进行代替操作，代替的方法是对数 据右边一半应用r o u n d 函数f ，然后用这个函数的输出和数据的左边一半做异 或。r o u n d 函数在每一轮中有着相同的结构，但是以各轮的子密钥k i 为参数形 成区分。在这个代替之后，算法做一个置换操作把数据的两个部分进行互换这种 结构是s h a n n o n 所提出的代替置换网络的一种特殊形式。 使用这种结构的密码有着一个非常重要的特点：即加密与解密可使用同一个 算法实现。 f e i s t e l 网络的具体实现依赖于对下列参数和设计特点的选择： ( 1 ) 分组大小：分组越大意味着安全性越高( 如果其他条件相同) ，但加密解 密速度也越慢。1 2 8 b i t s 的分组大小是一个合理的折衷，现在的分组密码设计中 它几乎是个通用的数值。 ( 2 ) 密钥大小：密钥长度越长则安全性越高，但加密解密速度也越慢。6 4 b i t s 的密钥长度现在已经被认为不够安全，1 2 8 1 9 2 2 5 6 b i t s 己经成为常用的长度。 ( 3 ) 迭代次数：f e i s t e l 密码的特点是一个循环不能保证足够的安全性，而循 环越多则安全性越高。通常采用1 6 轮循环。 ( 4 ) 密钥编排算法：这个算法越复杂则密码分析就应该越困难。 ( 5 ) r o u n d 函数：同样，复杂性越高则抗击密码分析的能力就越强。 ( 6 ) 快速的软件加密解密：在很多情况下，加密过程被以某种方式嵌入在应 用程序或工具函数中以至于无法用硬件实现，因此，算法的软件执行速度就成为 一个重要的考虑因素。 2 2 3 函数f 的设计 函数f 是f e i s t e l 密码的核心。就像d e s 一样，这个函数依赖于s 盒子 的使用。对于大部分其它的分组密码也是这样。本小节主要讨论函数f 的一般 性设计准则，下节专门讨论s 盒子的设计。函数f 在f e i s t e l 密码中主要起混 乱作用，因此函数f 应该是非线性的，非线性度越大则密码越难分析，因此安 全性越高。另外，函数f 的设计还应遵循雪崩准则与比特独立准则以便使它具 有很好的混乱效果。 2 2 4 s 一盒的设计 在分组密码的设计过程中一个最受关注的研究问题就是s 盒的设计，因为 i d e a 算法的研究及其变种的实现 在分组密码算法中s 盒通常是仅有的一个非线性步骤，它们给出了分组密码的 安全性( 抗差分线性分析) 。因此如何设计一个非线性度高的s 盒是分组密码的 设计关键。 一个s 盒就是一个简单的“代替”：将m 位输入映射到n 位输出f 记为m n 位s 盒) 。如d e s 具有6 4 位s 盒，b l o w f i s h 和c a s t 都具有8 3 2 位的s 一盒。一般来说，较大的s 盒对于差分线性密码分析的抗击力越强。另一 方面，m 越大则查询表越大( 指数级的) 。因而，通常m 限于8 到1 0 。另一个 考虑是s 盒越大实现它就越难。 s 一盒通常的组织方式与d e s 中的组织方式不同，一个m x n - 位s 一盒通常 由2 m 行的比特串组成，每行n 个比特。m 个比特的输入选中s 盒的一行， 该行的n 个比特就是输出。如在一个8 3 2 位的s 盒中，若输入为0 0 0 0 1 0 0 1 ， 则输出就