（应用数学专业论文）欧洲分组密码标准camellia算法的代数性质分析.pdf

欧洲分组密码标准c 姗e l l i a 算法的代数性质分析 摘要 近年来，随着信息化的迅速发展和信息技术运用的深入和普及，信 息安全变得越来越重要。密码学作为保障和实现信息安全的核心技术， 受到了各国普遍的重视。由于分组密码算法具有易于标准化、速度快等 优点，更是处于优先发展的地位。1 9 9 7 年4 月，美国国家标准技术研究 所发起了征集高级加密标准算法的活动，并于2 0 0 0 年1 0 月2 日公布了 最终的高级加密标准算法一一r i j n d a e l 算法。紧接着，2 0 0 1 年1 月，欧 洲启动了规模更大的n e s s i e 工程，希望推出一套不仅包括分组密码， 还包括流密码、h a s h 函数、消息认证码、数字签名和公钥加密等在内的 强安全性的密码标准。由于c a m e l l i a 算法在各种平台都表现出了卓越的 密码性能，并且经受住了来自各种攻击的考验。2 0 0 2 年2 月，c a m e l l i a 算法被遴选为普通型分组密码标准。 本文对c a m e l l i a 算法进行了深入的研究，主要成果有： 1 对c a m e l l i a 算法进行了详细的介绍，包括加密算法、解密算法 和密钥编排方案，并阐述了其设计理念和设计准则。 2 系统地总结分析了c a m e l l i a 算法的安全性，主要是其抵抗现有 多种攻击方法的现状。 3 从多输出布尔函数这一角度对此算法中唯一的非线性部件一s 盒 进行了研究，得出了s 盒的代数表达式和布尔函数表达式，并通过对s 盒的一系列密码性质的分析，揭示了c a m e l l i a 算法被选为欧洲普通型分 组密码标准并能抵抗多种攻击方法的内在原因。 通过本文的研究，我们认为，c a m e l l i a 算法是一个相当优秀的分组 密码算法，短时间内被攻破的可能性不大。只有在密码分析学理论上取 得大的突破和创新，才可能产生对c a m e l l i a 算法构成实际威胁的攻击方 法。 关键词：分组密码；c a m e l l i a 算法；安全性；s 盒：多输出布尔函数 i i 硕上学位论文 a b s t r a c t i nr e c e n ty e a r s ，w i t ht h er a p i dd e v e l o p m e n to fi n f o r m a t i o na n dt h e a p p l i c a t i o na n dp o p u l a r i t yo fi n f o r m a t i o nt e c h n 0 1 0 9 y ，i n f o r m a t i o ns e c u r i t y b e c o m e sm o r ea n dm o r ei m p o r t a n t a st h ec o r et e c h n o l o g yo fs u p p o r t i n g a n da c h i e v i n gi n f o r m a t i o ns e c u r i t y ， c r y p t o l o g yh a sw o nw i d eh e e db y c o u n t r i e sa 1 1 o v e rt h ew o r l d b l o c kc i p h e ri se v e ni nt h e p r i o r i t y d e v e l o p m e n ts t a t i o nb e c a u s eo fi t sm o d u l a ra n dr a p i ds p e e d n a t i o n a l i n s t i t u t eo fs t a n d a r d sa n dt e c h n o l o g yl a u n c h e dt h ec a m p a i g no fs e l e c t i n g a d v a n c e de n c r y p t i o ns t a n d a r di n a p r i l 19 9 7 ，a n dt h e np r o c l a i m e dt h e r i jn d a e la l g o r i t h ma st h ef i n a la d v a n c e de n c r y p t i o ns t a n d a r do n0 c t o b e r 2 ，2 0 0 0 n e x t ，e u r o p e s t a r t e dn e w e u r o p e a n s c h e m e sf o r s i g n a t u r e s ， i n t e g r i t y ，a n de n c r y p t i o ne v e nm o r el a r g ei nj a n u a r y2 0 01 t h e yw a n t e dt o i s s u eas e r i e so fs t r o n gs e c u r i t yc i p h e rs t a n d a r d s ，i n c l u d i n gn o to n l yb l o c k c i p h e r ，b u ta l s os t r e a mc i p h e r ，h a s hf u n c t i o n ，m e s s a g ea u t h e n t i c a t i o nc o d e ， d i g i t a ls i g n a t u r e ，p u b l i ck e yc i p h e ra n ds oo n c a m e l l i aw a sc h o s e na s e u r o p e a nb l o c kc i p h e rs t a n d a r di nf e b r u a r y2 0 0 2b e c a u s eo ft h ee x c e l l e n t p e r f o r m a n c ei nv a r i o u sp l a t f o r ma n di t sw i t h d r a w i n gm a n ya t t a c kw a y s t h i st h e s i sh a sad e t a i l i n v e s t i g a t i o no nc a m e l l i aa n dt h ec e n t r a l c o n t r i b u t i o ni sa sf o l l o w s ： 1 ad e t a i li n t r o d u c t i o no fc a m e l l i ai sp r e s e n t e d ，i n c l u d i n ge n c r y p t i o n a l g o r i t h m ，d e c r y p t i o na l g o r i t h ma n dk e ys c h e d u l ea l g o r i t h m ，a n da l s o ，t h e d e s i g ni d e aa n dd e s i g np r i n c i p l ei sp r e s e n t e d 2 as y s t e m i cs u m m a r yo ft h e s e c u r i t yo nc a m e l l i ai sp r e s e n t e d ， m o s t l yt h es t a t u sq u oo fw i t h s t a n dm a n ya t t a c kw a y s 3 t h eo n l yn o n - 1 i n e a rp a r to ft h ea l g o r i t h m s - b o xi sr e s e a r c h e di n t h ev i e wo fm u l t i o u t p u tb 0 0 1 e a nf h n c t i o n ，a n dt h ea l g e b r a i ce x p r e s s i o na n d b o o l e a nf h n c t i o ne x p r e s s i o no ft h es - b o xa r eo b t a i n e d a f t e ra n a l y z i n ga s e r i e so ft h ec i p h e rp r o p e r t i e so ft h es b o x ，t h ei n n e rc o u r s et h a tc a m e l l i a c o u l db ec h o s e na s e u r o p e a nb l o c kc i p h e rs t a n d a r da n dc o u l dw i t h s t a n d m a n ya t t a c kw a y se f f e c t i v e l yi sr e v e a l e d i i i 欧洲分组密码标准c 蛐e i l j a 算法的代数性质分析 b a s e do nt h ep r o d u c t i o no ft h i s t h e s i s ，w eb e l i e v et h a tc a m e l l i ai s e x c e l l e n ta sab l o c kc i p h e ra l g o r i t h ma n du n l i k e l i n e s sb eb r e a c h e di nr e c e n t y e a r s t h ea t t a c k w a yt h a t c a nt h r e a tt h e s e c u r “yo fc a m e l l i aw o n t d i s c o v e ru n t i lag r e a tb r e a k t h r o u g hb em a d eo nt h et h e o f yo fc r y p t a n a l y s i s k e yw o r d s ： b l o c kc i p h e r ；c a m e l l i a ；s e c u r i t y ； sb o x ；m u l t i - o u t p u t b o o l e a nf u n c t i o n l v 硕士学位论文 插图索引 图2 1c a m e l l i a 算法中函数f 的结构图1 1 图2 2c a m e l l i a 算法的加密过程( 密钥为1 2 8 比特时) 1 2 图2 3c a m e l l i a 算法的密钥编排方案( 部分) l3 图2 4 一轮f e i s t e l 型密码的加密过程15 v 插表索引 表1 1 候选分组密码5 表4 1严格雪崩准则性能指标3 2 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研 究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文 不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完 全意识到本声明的法律后果由本人承担。 作者签名：；长迥星弋日期： 册6 年 ，月 弓日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许沦文被查阅和借阅。本人授权湖南大学可以将本学位论文的全部 或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等 复制手段保存和汇编本学位论文。 本学位论文属于 1 保密口，在一年解密后适用本授权书。 2 不保密回。 ( 请在以上相应方框内打”) 作者签名：f 弗_ 望己日期：和6 年 月日 导师签名：i 夕孑穆日期：五6 年j 一月 j ) 日 硕士学位论文 第1 章绪论 党的十六届四中全会认为，国家安全包括四个方面的内容：政治安全、经济 安全、文化安全和信息安全。信息安全的重要性由此可见一斑。无独有偶，2 0 0 5 年1 1 月，在中国国家信息化领导小组会议上审议并通过的2 0 0 6 到2 0 2 0 年中国国 家信息化发展战略中，信息安全成为其中十分重要的一个方面。近年来，随着信 息化的迅速发展和信息技术运用的深入和普及，信息安全一词越来越多地出现在 各类期刊杂志上，信息安全人才也变得炙手可热。信息安全的问题由来已久，在 网络世界中表现尤甚。产生网络信息安全问题的原因在于电子政务、电子商务、 电子银行等基于网络的技术不断发展，而作为数据通信和资源共享的重要平台 因特网所使用的t c p i p 协议是在假定的可信安全环境下、为网络互联而专门 设计的。本身缺乏考虑安全措施，因此在网络中存储和传输的大量数据都需要加 以保护，以免被盗用、暴露、篡改和伪造。除此之外，基于网络的信息交换还面 临着身份认证和防否认等安全需求。所有这些信息安全问题是制约信息化社会快 速健康发展的瓶颈。 密码学是保障和实现信息安全的核心技术，是保护数据最重要的工具之一。 在数字世界中，机密性就像大门上的锁，它可以阻止非法者闯入用户的文件夹读 取用户的的敏感数据或盗窃钱财( 如信用卡号或网上证券账户信息) 。数据完整性 提供了一种当某些内容被修改时可以使用户得知的机制，相当于报警器。通过认 证，可以验证实体的身份，就像从银行取钱时需要用户提供合法的身份( i d ) 一 样。基于密码体制的数字签名具有防否认功能，同样具有法律效力，可使人们遵 守数字领域的承诺。这些思想都是密码技术在保护信息安全方面所起作用的具体 体现。当前信息安全的主流技术和理论都是基于以算法复杂性理论为特征的现代 密码学。 1 1 什么是密码学 1 1 1 密码学的定义 “密码”一词对人们来说并不陌生，人们可以举出许多使用密码的例子。如保 密通信设备中使用“密码”，个人在银行取款使用“密码”，在计算机登录时使用“密 码”，开启保险箱使用“密码”，玩电子游戏中使用“密码”等等。但以上所说的“密 码”，并不都是真正的密码。除了保密通信设备中使用的密码以外，其它使用的并 不是密码，而是一种特定的暗号或口令。 那么，什么是密码呢? 在辞海( 1 9 9 9 年版) 中对密码是这样定义的：“按 特定法则变成，用以对通信双方的信息进行明密变换的符号”。换而言之，密码是 欧洲分组密码标准c m e i l i a 算法的代数性质分析 隐蔽了真实内容的符号序列。就是把公开的、标准的信息编码表示的信息( 明文) 通过一种变换手段( 加密算法) ，将其变为除通信双方以外其他人所不能读懂的信 息编码( 密文) ，这种独特的信息编码就是密码。 严格说来，密码学是研究密码系统或通信安全的一门学科。它主要包括两个 分支，即密码编码学和密码分析学。密码编码学的主要目的是寻求保证消息保密 性或认证性的方法，密码分析学的主要目的是研究加密消息的破译或消息的伪造。 1 1 2 密码学的发展历程 密码学的发展大致经历了三个阶段【l 】：古代加密方法、古典密码和近现代密 码。 ( 1 ) 古代加密方法( 手工阶段) 古代加密方法大约起源于公元前4 4 0 年出现在古希腊战争中的隐写术。当时 为了安全传送军事情报，奴隶主剃光奴隶的头发。将情报写在奴隶的光头上，待 头发长长后将奴隶送到另一个部落，再次剃光头发，原有的信息便复现出来，从 而实现这两个部落之间的秘密通信。 密码学用于通信的另一个记录是斯巴达人于公元前4 0 0 年应用s c y t a l e 加密 工具在军官间传递秘密信息。s c y 协l e 实际上是一个锥形指挥棒，周围环绕一张羊 皮纸，将要保密的信息写在羊皮纸上。解开羊皮纸，上面的信息杂乱无章、无法 理解，当将它缠在另一个同等尺寸的棒子上后，就能看到原始的信息。 我国古代也早有以藏头诗、藏尾诗、漏格诗及绘画等形式，将要表达的真正 意思或“密语”隐藏在诗文或画卷中特定位置的记载，一般人只注意诗或画的表面 意境，而不会去注意或很难发现其中的“话外之音”。 古代加密方法主要基于手工的方式实现，因此称为密码学发展的手工阶段。 ( 2 ) 古典密码( 机械阶段) 古典密码的加密方法一般是文字置换，使用手工或机械转换的方式实现。古 典密码系统已经初步体现出近代密码系统的雏形。它比古代加密方法复杂。古典 密码的代表密码体制主要有：单表代替密码、多表代替密码及转轮密码。c a e s a r 密码就是一种典型的单表加密体制；多表代替密码有v i g e n e r e 密码、h i l l 密码； 著名的e n i g m a 密码就是第二次世界大战中使用的转轮密码。 阿拉伯人是第一个清晰地理解密码学原理的人，他们设计并且使用代替和换 位加密，并且发现了密码分析中的字母频率分布关系。到了2 0 世纪2 0 年代，随 着轮转密码机( r o t o r ) 的发明，传统密码学有了很大的发展，利用机械转轮可以 开发出极其复杂的加密系统。 ( 3 ) 近现代密码( 计算机阶段) 密码学的理论基础之一是1 9 4 9 年c l a u d es h a n n o n 发表的“t h ec o m m u n i c a t i o n t h e o r yo f s e c r e c ys y s t e m s ”【2 】一文，这篇论文用信息论的观点对信息保密问题作了 硕士学位论文 全面的阐述，使信息论成为研究密码学的一个重要理论基础，对密码学的研究产 生了巨大的影响，从此密码学成为一门新的学科。1 9 7 6 年w d i m e 和m h e l l m a n 发表了“n e wd i r e c t i o n si nc r y p t o g r a p h y 【3 】一文，这篇文章导致了密码学上的一场 革命。在这篇文章中，d i m e 和h e l l m a n 建议利用计算复杂性设计加密算法，并 首次证明了在发送端和接收端无密钥传输的保密通信是可能的，从而开辟了公钥 密码学的新领域。受他们的思想启迪，1 9 7 7 年由r i v e s t ，s h 砌i r 和a d l e m a n 提出 了第个比较完善的公钥密码算法，这就是著名的r s a 算法【4 】。同年，美国国家 标准局( n b s ，现在是美国国家标准技术研究所，即n i s t ) 正式公布实施了美国 的数据加密标准( d a t ae n c r y p t i o ns t a r i d a r d ，d e s ) 【5 j ，并批准用于政府等非机密 单位及商业上的保密通信。上述两篇重要的论文和美国数据加密标准d e s 的实 施，标志着密码学理论与技术的革命性变革，宣布了近代密码学的开始。 1 1 3 密码学的分类 密码学的理论与技术主要包括两部分，即基于数学的密码理论与技术( 包括 公钥密码、分组密码、序列密码、认证码、数字签名、h a s h 函数、身份识别、密 钥管理、p k i 技术等) 和非数学的密码理论与技术( 包括信息隐形，量子密码， 基于生物特征的识别理论与技术) 。 对于一个密码体制，加密和解密算法的操作通常都是在一组密钥控制下进行 的，分别称之为加密密钥和解密密钥。根据密钥的特点，s i m m o n s 将密码体制分 为对称和非对称密码体制两种【6 l 。对称密码体制又称私钥密码体制，非对称密码 体制又称公钥密码体制。在私钥密码体制中。加密密钥和解密密钥是一样的或彼 此之间容易相互确定。按加密方式又可将私钥密码体制分为流密码和分组密码两 种。在流密码中，将明文消息按字符逐位地加密。在分组密码中，将明文消息分 组( 每组含有多个字符) ，逐组地加密。在公钥密码体制中，加密密钥和解密密钥 不同，从一个很难推出另一个，可将加密和解密能力分开。 自从1 9 7 6 年公钥密码的思想提出以来，国际上已经提出了许多种公钥密码体 制，比较流行的主要有两类：一类是基于大整数因子分解问题的，其中最典型的 代表是r s a ；另一类是基于离散对数问题的，如e l g a m a l 公钥密码和非常有潜力 的椭圆曲线公钥密码。公钥密码主要用于数字签名和密钥分配。 对称密码体制的安全性主要取决于两个因素：加密算法足够安全，使得不 必为算法保密，基于密文和加密，解密算法的知识能破译出消息的做法是不可行 的；密钥的安全性：密钥必须保密并保证有足够大的密钥空间。其中序列密码 主要用于政府、军队等国家要害部门，由于一些数学工具( 比如代数、数论、概 率等) 可用于研究序列密码，其理论和技术相对而言比较成熟。分组密码具有速 度快、易于标准化和便于软硬件实现等优点，通常是信息与网络安全中实现数据 加密、数字签名、认证及密钥管理的核心体制，在计算机通信和信息系统安全领 欧洲分组密码标准c 撇e l l i a 算法的代数性质分析 域有着非常广泛的应用。 1 2 分组密码算法的历史与现状 1 9 7 3 年5 月1 5 日，美国国家标准局( n b s ，现在是美园国家标准技术研究所， 即n i s t ) 在联邦记录中公开征集密码体制，这一举措晟终导致了数据加密标准 ( d e s ) 的出现，d e s 【5 】曾经成为世界上最广泛使用的密码体制。d e s 由i b m 开 发，它是对早期被称为l u c i f e r 【7 】体制的改进。d e s 在1 9 7 5 年3 月1 7 日首次被公 布在联邦记录中，在做了大量的公开讨论后于1 9 7 7 年1 月1 5 日正式批准并作为 美国联邦信息处理标准，即f i p s 4 6 ，同年7 月1 5 日开始生效。规定每隔五年由 美国国家保密局作出评估，并重新批准它是否继续作为联邦加密标准。d e s 的最 后次评估是在1 9 9 9 年1 月。美国已经决定不再使用d e s 。 在1 9 9 7 年4 月，美国国家标准技术研究所( n i s t ) 发起征集a e s 算法的活 动，并专门成立了a e s 工作组，经过三年多的努力，n i s t 终于在2 0 0 0 年1 0 月 2 日公布了最终的a e s 标准r “n d a e l 【8 】算法，并于2 0 0 1 年1 1 月2 6 日作为美 国新的数据加密标准对外公布。 继美国征集a e s 活动之后，欧洲和日本等国家也不甘落后地启动了相关密码 标准的征集和制定工作。特别值得一提的是欧洲大计划n e s s i e 工程【9 1 。 2 0 0 1 年1 月，欧洲委员会从信息社会技术( i s t ) 规划中出资3 3 亿欧元支持 了一项称之为n 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 r i t y ，a n d e n c r y p t i o n ) 的工程，希望推出一套不仅包括分组密码，还包括流密码、h a s h 函 数、消息认证码、数字签名和公钥加密等在内的强安全性的密码标准。n e s s i e 组织者先后组织召开了4 次n e s s i e 专题研讨会( 2 0 0 0 年1 1 月、2 0 0 1 年9 月、 2 0 0 2 年1 1 月和2 0 0 3 年2 月) n e s s i e 工程已于2 0 0 3 年3 月公布了最终的评估结果。他们把选出的安全算 法集称为n e s s i e 算法套件，该套件包括1 2 个决选算法和5 个已经成为或即将成 为标准的算法( 用“”标出) ，共1 7 个算法： 1 )分组密码：m i s t y l 、c a m e l l i a 、s h a c a l 2 和a e s ( u s a f i p s1 9 7 ) 。 2 )公钥密码：a c ee n c r y p t 、p s e c k e m 和r s a k e m ( i s o i e cl8 0 3 3 - 2 草案) 。 3 ) m a c 算法和h a s h 函数：t w o t r a c k m a c 、u m a c 、c b c m a c + ( i s o i e c 9 7 9 7 1 ) 、h m a c ( i s 0 i e c9 7 9 7 2 ) 、w h i r l p o o l 和s h a 2 5 6 、3 8 4 、 5 1 2 + ( u s af i p s1 8 0 2 ) 。 4 ) 数字签名算法：e c d s a 、r s a p s s 和s f l a s h 。 5 ) 识别方案：g p s 。 n e s s i e 工程共征集到1 7 个分组密码( 参见表1 1 ) ，并决定把t r i 口l e d e s 4 硕士学位论文 和a e s 纳入评估过程，作为评估其它分组密码的参考标准。经过近一年的评估， 在2 0 0 1 年9 月召开的第二次会议上，n e s s i e 公布了进入第二轮评估的算法，过 渡型的有i d e a 、a e s 、和s a f e r + + 6 4 和t r i p l e d e s ，普通型的有c a m e l l i a 、 r c 6 、a e s 和s a f e r + + 1 2 8 ，高级型的有r c 6 、a e s 、s h a c a l l 和s h a c a l 2 。 2 0 0 2 年2 月公布了最终决选结果：过渡型的分组密码为m l s t y l ，普通型的分组密 码为c a m e l l i a 和a e s ，高级型的分组密码为s h a c a l 2 。 表t 1 候选分组密码 算法名称国家( 组织) 整体结构设计特点 c s - c i p h e r 法国s ps 盒 h i e r o c r y p t l 1 日本s ps 盒 i d e a 瑞士s p 不同群中的运算 k h a z a d 比利时 s ps 盒 m i s t y l 日本递归s 盒 n i m b u s 巴西s p 乘法和异或 a n u b i s 巴西、比利时 s ps 盒 c a m e n i a 日本 f e i s t e ls 盒 g r a n dc r u 比利时 s ps 盒 h i e r o c r y p t 一3 日本 s ps 盒 n o e k e o n 比利时 s p逻辑运算或s 盒 q美国 s ps 盒 s c 2 0 0 0 日本 s ps 盒 s h a c a l g e m p l u s 公司 以杂凑函数为基础 n u s h 俄罗斯s p 各种运算混合 r c 6 美国广义f e i s t e l 乘法数据相依循环 s a f e r + + 瑞士s ps 盒 在对算法进行评估及对算法傲取舍时，n e s s i e 工程重点考查以下几项： 1 ) 算法抵抗现有攻击的能力。算法应能很好地抵抗现有的所有攻击，如密钥 穷搜索攻击f 】、差分攻击【12 1 、截段差分攻击13 1 、不可能差分攻击14 1 、高阶差分 高阶【”】、线性攻击【16 1 、差分一线性攻击【17 1 、相关密钥攻击【18 1 、插值攻击19 1 、滑 动攻击【2 们、模n 攻击2 n 、s q u a r e 攻击2 孙、积分攻击2 、代数攻击2 5 】和能量攻 击【2 6 】等。 2 ) 算法的设计思想和设计的透明性。在评估时，设计清楚、直接、以充分研 究过的数学和密码学原则为基础的算法，更容易得到信任。 3 ) 对算法的变形进行评估。比如说，改变或删除算法的一个模块，减少迭代 的轮数等。对变形的分析可以间接地推论得到关于原算法的一些结论。 欧洲分组密码标准c a i l l e l l i a 算法的代数性质分析 4 ) 在相同的运行环境中对各算法的安全性做比较。n e s s i e 宣称尽力保证公 平地评估每一个算法。 5 ) 算法的统计测试结果。分析统计测试的结果，其目的是查看算法的密码学 特性有无突出的异常现象。 1 3 本文的研究背景及意义 密码技术是信息安全的核心技术，各个国家都不会放弃自主权和控制权，都 在争夺霸权地位。而目前我国在密码技术的应用水平方面与国外还有一定的差距。 国外的密码技术必将对我们有一定的冲击力，特别是在全球化的浪潮中这种冲击 力只会有增无减。因此，我们必须要有我们自己的算法，自己的一套标准，自己 的一套体系，来对付未来的挑战。实用密码技术的基础是密码基础理论，没有好 的密码理论不可能有好的密码技术、也不可能有先进的、自主的、创新的密码技 术。因此，首先必须持之以恒地坚持和加强密码基础理论研究，与国际保持同步， 不能再采用闭门造车的做法。另一方面，密码理论研究也是为了应用，没有应用 的理论是没有价值的。我们应在现有理论和技术基础上充分吸收国外先进经验形 成自主的、创新的密码技术以适应国民经济的发展。 借鉴n e s s i e 工程评估过程的先进经验、分析n e s s i e 工程选出的安全算法 对我国实施密码标准化和确立自己的密码算法有积极的促进意义。 1 4 本文的主要工作与章节安排 作为欧洲分组密码标准之一的c a m e l l i a 算法，有着许多优秀的密码性质。本 文首先详细介绍了c a m e l l i a 算法( 包括加密算法、解密算法和密钥编排方案) ， 阐述了其设计理念和准则。然后系统地总结分析了c a m e l l i a 算法的安全性。最后 我们从多输出布尔函数这一角度对此算法中唯一的非线性部件一一s 盒进行了研 究，运用l a g r a n g e 插值法，我们计算出了s 盒的代数表达式，然后我们证明了s 盒的正交性、不含非零线性结构等性质，并且计算出了s 盒的代数次数、差分均 匀度、鲁棒度、严格雪崩准则等密码性能的相关指标参数，通过对s 盒的一系列 密码性质的分析，揭示了c a m e l l i a 算法被选为欧洲分组密码标准并能有效抵抗多 种攻击方法的内在原因。 本文的具体章节安排如下： 第2 章介绍了c a m e l l i a 算法详细情况( 包括加密算法、解密算法和密钥编排 方案) ，阐述了其设计理念和准则。 第3 章系统地总结分析了c a m e l l i a 算法的安全性，主要是其抵抗现有多种攻 击方法的现状。 第4 章从多输出布尔函数这一角度对此算法中唯一的非线性部件一一s 盒进 硕士学位论文 行了研究，得出了s 盒的代数表达式和布尔函数表达式，并通过对s 盒的一系列 密码性质的分析，揭示了c a m e l l i a 算法被选为欧洲普通型分组密码标准的内在原 因。 7 欧洲分组密码标准c a m e l 【i a 算法的代数性质分析 第2 章c a m e l l i a 算法 2 0 0 0 年日本电报电话公司和三菱电机公司( m i t s u b i s h i ，m i t s u b i s h ie l e c l r i c c o r p o r a t i o n ) 联合向n e s s i e 提交了c a m e l l i a 。c a m e l l i a 最早公布于2 0 0 0 年的s a c 会议上。c a m e i l i a 的设计目标类似于a e s 的要求，即分组长度是1 2 8 、1 9 2 及2 5 6 比特三种规模的密钥长度：比三重d e s 快而且至少和三重d e s 一样安全。2 0 0 3 年2 月c a m e l “a 被选定为欧洲普通型分组密码标准。2 0 0 3 年2 月c a m e “i a 被 c r y p t r e c ( c r y p t o g r a p br e s e a r c ha n de v a i u a t i o nc o m m i t t e e ，密码研究与评估委 员会) 采纳。2 0 0 5 年5 月c a m e l l i a 被i s o ( 1 m e r n a t i o n a lo r g a n i z a t i o n f o r s t n d a r d i z a t i o n ，国际标准化组织) 接纳为加密标准算法。由此可见，c a m e l l i a 算 法在全球范围内正在得到越来越广泛的应用。 2 1 本章所用的符号介绍 凰，：分别表示数据x 的左半部分和右半部分； o ，n ，u ：分别表示位布尔代数中的异或，与，或运算； | | ；表示比特串的连接； 。，( 。：分别表示比特串右循环移h 位或左循环移n 位； o x ：表示十六进制； 越。) t 表示数据j 的长度为月比特位。 2 2c a m e l l i a 算法详解 2 2 1c a m e l l i a 算法的基本模块 s 盒 c a n l e l l i a 的四个s 盒& 、& 、岛、函和有限域霹上的逆函数在仿射意义下等价 它们的代数表达式如下： 它们的代数表达式如下： s 。f ；砖 。( g ) 卜 ( g ( - 厂( 0 x c 5 0 。( 8 ) ) ) o o x 6 e ) s ，砖j 日 。( a ) 卜q ( 。( 8 ) ) i ， s 4 。避避 。( 钟卜j 1 碍) f ( 五( 3 2 ) | jx r ( 3 2 ) ，埘 3 2 ) l l 肼r ( 3 2 ) ) 卜e ( 3 2 刈3 2 ) ， 、l；lll，毛乙毛 ，。l p = j ； ，。，、，l，l 坝士学位论文 其中 乓( 3 2 ) = ( ( z ( 3 2 ) n 肼( 3 2 ) ) 1 ) ox r ( 3 2 ) ， 圪( 3 2 ) 2 ( ( 3 2 ) u 肼r ( 3 2 ) ) ox ( 3 2 ) 函数凡。1 函数凡d 的定义如下： f p ：f x f 譬 f 譬 ( 圪( 3 2 刈( 3 2 ) ，材( 3 2 刈( 3 2 ) ) x l ( 3 2 刈z r ( 3 2 ) ， 其中 也( 3 2 ) 2 ( 3 2 ) u 盯r ( 3 2 ) ) o 虼( 3 2 ) ， 以( 3 2 ) = ( ( x l ( 3 2 ) n 船( 3 2 ) ) 异或，并被拆分成左右两个等长的子块o ( 6 4 ) 和异o 6 4 ) ，即 m 1 2 8 ) 0 ( 枷l ( 6 4 ) l i 枷2 ( 6 4 ) ) = 上o ( 6 4 ) 0r o ( 6 4 ) 。 然后，当，= 1 2 4 ( 其中r 6 ，1 2 ，1 8 ) 时执行 三，= 震，1of ( 上，1 ，b ) b = 工，1 当r = 6 ，1 2 和1 8 时执行 三，= 尺，io h 上，一1 ，岛) 1 2 硕士学位论文 r ：= 三r 1 厶= 儿( t ，射2 ，) i 1 毋= 凡j ( r ：，肼2 ，6 ) 最后，输出密文c ( 1 2 3 ) = ( r 2 4 ( 6 4 ) i | 工2 4 ( 6 4 ) ) o ( 七w 3 ( 6 4 ) j 晰4 ( 6 4 ) ) 。 2 2 3c a m e l l i a 的解密算法 解密算法与加密算法的步骤相同，只是轮密钥的使用顺序相反，解密轮密钥 是加密轮密钥的逆序。 2 2 4c a m e l l i a 的密钥编排算法 首先介绍两个1 2 8 比特变量k “1 2 8 ) 、k r ( 1 2 8 ) 和4 个6 4 比特变量k ( 6 4 ) 、k m ( 卵 足昱( 6 4 1 和足m ( “ ：k l ( 1 2 s ) 。世n ( “) 0k 口( “) ，足r ( m ) = k m 似) i 足m ( h ) ； 它们与种子密钥丘，：。) 、& 。，：) 和丘z * ) 有如下关系： 当密钥为1 2 8 比特时，足( 1 2 8 ) = 足( 1 2 8 ) ，丘r ( m ) = o ； 当密钥为1 9 2 比特时，k ( 1 9 2 ) = k l ( 1 2 8 ) i f 世n ( “) ，k m 州) = k n ( “f 当密钥为2 5 6 比特时，2 ) = k l ( 1 2 8 ) l i 世r ( 1 2 8 ) 。 图2 | 3c a m e l l i a 算法的密钥编排方案( 部分) 利用这些变量生成两个1 2 8 比特的变量k 郇2 8 ) 和k 叩：。) ，其中j 0 ( 。) 仅在密钥长 度为1 9 2 比特和2 5 6 比特时用到。在生成过程中用到了6 个6 4 比特的常数f ， 它们分别是第f 个素数的平方根的十六进制表示的小数点后第2 位至第1 7 位。具 1 3 欧洲分组密码标准c a m e l l i a 算法的代数性质分析 体数值如下： l ( 64 ) = o x a 0 9 e 6 6 7 f 3 b c c 9 0 8 b ，2 ( 6 4 ) = 0 x b 6 7 a e 858 4 c a a 7 3 8 2 ， e3 ( 64 ) = 0 x c 6 e f37 2 f e 9 4 f 8 2 b e ，4 ( 64 ) = 0 x 5 4 f f 53 a 5 f 1 d36 f 1 c ， 5 ( 6 4 ) = o x lo e 5 2 7 f a d e 6 8 2 d 1 d ，6 ( 6 4 ) = o x b 05 6 8 8 c 2 8 3 e 6 c 1 f d 首先将墨m 8 】、k 刖2 8 l 异或，然后以常数1 ( 6 4 ) 和2 ( 6 4 ) 为密钥做两轮加密，加密 结果和t ( 。：。1 异或后再以常数3 ( 6 4 ) 和4 ( 6 4 ) 为密钥做两轮加密，输出结果为 k ( 1 2 8 1 。最后足邮2 8 ) 和k 心2 8 ，异或后再以常数5 ( 6 4 ) 和6 ( 6 4 ) 为密钥做两轮加密，输 出结果为j 乙( 1 2 8 ) 。其中k 圳2 b ) 的构建过程参见图3 。子密钥由k 加2 8 ) 、k 州2 8 ) 、 x 圳：。) 和k 即：。) 循环移位生成。具体的编排方案参见附录b 。 2 3c a m e l l i a 算法的设计原理 2 3 1 分组密码的一般设计原则 ( 1 ) 针对安全性的设计原则。影响安全性的因素很多，诸如分组长度m 和密钥 长度f 等。但有关实用密码的两个一般的设计原则是s h a n n o n 提出的混乱原则和 扩散原则【2 j 。 混乱：人们所设计的密码应使得密钥和密文以及明文和密文之间的依赖关系 相当复杂以至于这种依赖性对密码分析者来说是无法利用的。 扩散：人们所设计的密码应使得密钥的每一位比特影响密文的许多位比特以 防止对密钥进行逐段破译，而且明文的每一位比特也应影响密文的许多位比特以 便隐蔽明文比特的统计特性。 ( 2 ) 针对实现的设计原则。分组密码可以用软件和硬件来实现。硬件实现的 优点是可获得高速率，而软件实现的优点是灵活性强、代价低。基于软件和硬件 的不同性质，分组密码的设计原则可根据预定的实现方法来考虑。 软件实现的设计原则：使用子块和简单的运算。密码运算在子块上进行，要 求子块的长度能自然地适应软件编程，比如8 、1 6 和3 2 比特等。在软件实现中， 按比特置换是难以实现的，因此应尽量避免。子块上所进行的一些密码运算应该 是一些易于软件实现的运算，最好是用一些标准处理器所具有的一些基本指令， 比如加法、乘法和移位等。 硬件实现的设计原则：加密和解密可用同样的器件来实现。尽量使用规则结 构，因为密码应有一个标准的组件结构以便其能适应于超大规模集成电路实现。 乘积密码t 1 9 】是实现s h a n o n 提出的混乱原则和扩散原则的一种有效的方法。 所谓乘积密码就是两种或两种以上简单密码的逐次应用。由合理选择的许多子密 码构成的乘积密码既可实现良好的混乱又可实现良好的扩散。当今大多数分组密 码都是乘积密码体制。通常使用的技术是将代换密码和置换密码做乘积。 当今多数分组密码的整体结构都采用f e i s t e l 结构，c 啪e l l i a 算法也不例外。 硕士学位论文 f e i s t e l 结构是由h o r s tf e i s t e l 在设计l u c i f e r 分组密码时发明的，并因d e s 的使 用而流行。对一个分组长度为2 n 比特的r 轮f e i s t e l 型密码，它的加密过程如图4 所示。具体描述如下： ( 1 ) 给定明文p ，记p = 工o r o ，这里三。是p 的左边竹 比特，r d 是p 的右边玎比特。 ( 2 ) 进行r 轮完全相同的运算，在这里数据和密钥 相结合。我们根据下列规则计算皿。，l s f 9 ： 厶= r f 1 r 。= 厶1of ( 尺，l ，k f ) 这里毋表示两个比特串的异或，f ：g h 2 ) ”g 以2 ) “ 一g 尺2 ) ”是轮函数，世l ，”，厨是由种子密钥生成的子密 钥，为子密钥的长度。 ( 3 ) 输出密文c - r r 上，。 在加密的最后一轮，为了使算法同时用于加密和解 密，略去“左右交换”。 “加解密相似”是f e i s t e l 型密码的显著优点。 2 3 2c a m e l l i a 算法的设计目标 r i 1 图2 4 一轮f e i s t e l 型 密码