（信号与信息处理专业论文）基于ldpc的纠错密码研究与设计.pdf

北京交通大学硕士学位论文 中文摘要 摘要：近年来，随着通信技术的发展和互联网的普及，信息共享应用日益广 泛和深入，但同时信息安全问题也日渐突出和复杂。一些非常重要的信息在传输 过程中不仅要有很好的保密性，还要有一定的容错性能。传统上，我们可以先对 信息加密，在将加密信息送到编码信道，经纠错编码使密码具有容错能力。但是， 这种分两步操作的方法，一方面，增加了系统的复杂性，另一方面，会产生一定 的时延。因而将两步结合到一起会使加密和纠错变得更有效率。自从1 9 7 8 m c e l i e c e 提出了第一个基于代数编码理论的公钥密码体制将纠错与加密的结合到一起。纠 错和加密的结合一直受到国内外通信理论研究人员的重视，但是，如果这种结合 没有很好的设计，会使纠错能力和安全性都下降。所以，在过去的几十年里，如 何去设计将纠错和加密结合仍然是一个待解决的问题。 本文首先简单介绍了分组密码理论，l d p c 编译码理论，并列举了以前研究人 员将纠错与加密结合所作的工作。 然后，将有很高安全性的高级加密标准a e s 和在通信纠错领域性能优异的 l d p c 码结合，设计出了l d p c 纠错密码。并在此基础上，提出了l d p c 纠错密码 编解码系统。本文设计的l d p c 纠错密码是一个分组长度为2 5 6 比特，密文长度 为5 1 2 比特，六轮加密并采用宽轨迹策略的分组密码，密钥由1 2 8 比特a e s 密钥 和l d p c 码生成矩阵( 或校验矩阵) 组成。在密码的最后一轮的扩散层，我们使 用了l d p c 生成矩阵。因为l d p c 生成矩阵有着更好的扩散性能，使得我们所设 计的l d p c 纠错密码在更少的轮数下，能够和a e s 在抗线性、差分攻击时具有大 体相等的安全性。而且s q u a r e 攻击对它也没有意义。 在本文的最后，我们给出了l d p c 纠错密码编码译码实现的过程。提出了基 于l d p c 纠错密码的加密纠错系统，并分析了l d p c 纠错密码的安全性能和纠错 能力。 关键词：a e s ；l d p c 信道编码；加密纠错 一 北京交通大学硕士学位论文 二- _ 二二= 誓二_ 一 a b s t r a c t a b s t r a c t ：i nr e c e n ty e a r s ，w i t ht h ed e v e l o p m e n to fc o m m u n i c a t i o nt e c h n 0 1 0 9 y a n dw i t ht h ew i d e l ya p p l i c a t i o no fi n t e r n e t ，i n f o r m a t i o ns h a r i n gb e c o m e sm o r ea n d m o r ei m p o r t a n tt oa l m o s t e v e r yi n s t i t u t i o n a tt h es a m et i m e , t h ep r o b l e m so f i n f o r m a t i o ns e c u r i t ya r es t i c k i n go b rd a i l y i nt r a n s m i s s i o np r o c e s s ，s o m e i m p o r t a n t i n f o r m a t i o nn e e d sn o to n l ys e c u r i t yb u ta l s oe r r o rr e s i l i e n c e t r a d i t i o n a l l y , t h e s et w o s t e po p e r a t i o n s ：e n c r y p t i o nf o l l o w e db ye l l o rc o r r e c t i o n i n c r e a s i n gt h es y s t e m c o m p l e x i t yw h i l ep r o d u c i n gs o m en e t w o r kd e l a y s oj o i n t i n gt h et w oo p e r a t i o n s t o g e t h e rw i l lm a k et h es y s t e mm o r ee f f i c i e n c y m c e l i e c ej o i n te r r o r - c o r r e c t i n ga n d e n c r y p t i o nt o g e t h e rb a s e do na l g e b r a i cc o d i n gt h e o r yf i r s t l yi n1 9 7 8 t h e na t o r c o r r e c t i n gc i p h e r sh a sa t t r a c t e dc o n s i d e r a b l ea t t e n t i o ni nc o m m u n i c a t i o n s e c u r i t y h o w e v e r , i fs u c haj o i n ts y s t e mi sn o td e s i g n e dc a r e f u l l y , b o t he r r o rc o r r e c t i n gc 印a c i t y a n ds e c u r i t yc o u l db ec o m p r o m i s e d f o rt h i sr e a s o n ，t h ed e s i g no fe r r o rc o r r e c t i n g c i p h e r sh a sr e m a i n e da no p e np r o b l e mf o rt h ep a s t3 0y e a r s i nt h i sp a p e r , f i r s t l y , w eg i v ea s i m p l ei n t r o d u c t i o no ft h eb l o c kc i p h e rt h e o r ya n d t h ee n c o d i n g d e c o d i n gt h e o r yo fl d p c t h e nw ed e s c r i b et h ew o r k so fr e s e a r c h e r so n 也i sf i e l d s e c o n d l y , w ep r o p o s ea ne r r o rc o r r e c t i n gb l o c kc i p h e r ：t h el d p ce r r o rc o r r e c t i n g c i p h e r w ea l s op r e s e n ta ne r r o rc o r r e c t i n gc i p h e rs y s t e mm a i n l yb a s e do nt h el d p c e r r o rc o r r e c t i n ge i p h 既t h el d p ce r r o rc o r r e c t i n gc i p h e rw h i c hi sb a s e do nt h ew i d e t r a i ls t r a t e g yi sas i xr o u n db l o c k c i p h e rt h a te n c r y p t s2 5 6b i tp l a i n t e x t su s i n gs e c r e tk e y t op r o d u c e512b i tc i p h e r t e x t s ，a n dt h ek e yi sc o m p o s e do f12 8b i ta e s s e c r e tk e va n d l d p cg e n e r a t o rm a t r i x b yu s i n gt h el d p cg e n e r a t o rm a t r i xw i t h h i g hp e r f o r m a n c ei n d i f f u s i o np r o p e r t y , w em a d et h el d p ce r r o r c o r r e c t i n gc i p h e ra ss e c u r ea s t h e a 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 ) a g a i n s tl i n e a r , d i f f e r e n t i a la t t a c k si nf e w e r r o u n d s e v e nt h es q u a r ea t t a c kh a sn oe f f e c to na t t a c k i n gt h ec i p h e r l a s t l y , t h ep r o c e s so fe n c r y p t i n g d e c r y p t i n gl d p ce r r o rc o r r e c t i n g c i p h e ri s i m p l e m e n t e d ，t h ec i p h e re n c r y p t i o n d e c r y p t i o ns y s t e mw h i c hi s m a i n l yb a s e do nt h e l d p ce r r o rc o r r e c t i n gc i p h e ri si m p l e m e n t e d ，a l s ot h es e c u r i t ya n de r r o rc o r r e c t i o n c a p a c i t yi sa n a l i z e d k e y w o r d s ：a e s ；l d p cc h a n n e lc o d i n g ；e r r o rc o r r e c t i n gc i p h e r 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 签字日期：2 3 年 、 名弼 6 月痧日 导师签名： 喃杨 l 签字日期：9 ，绛知乡日 独创性声明 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名：签字日期：夕咖艿年月多f i象 致谢 本论文的工作是在我的导师肖扬教授的悉心指导下完成的，肖老师严谨的治 学态度和科学的工作方法给了我极大的帮助和影响。在读研究生期间，肖老师对 我严格要求，在各方面给予悉心指导和帮助，使我的科研和工作能力有了很大的 提高。对于我的论文肖老师也提出了许多的宝贵意见，在此表示衷心的感谢。 感谢我的父母，是他们的培养和支持使我取得今天的成绩。在此，深切地感 谢父母亲二十多年来的养育之恩和教导。 感谢侯妍颖、文心灵、冯炜、甄茂松、刘文涛、邹涵同学在我研究生学习和 生活期间给我无微不至的关心和帮助，他们提供的建议使我受益匪浅。 感谢师姐徐丹，师兄赵莹、范俊、曹振臻、孔令军，以及众位师弟师妹对我 的支持和帮助，他们为我提供了一个温暖的集体氛围，使我能更投入的完成论文。 最后向所有关心、帮助和支持我的人致以衷心的感谢! 北京交通大学硕士学位论文 序 “本论文的研究工作是在国家自然科学基金项目( 6 0 5 7 2 0 9 3 ) 的资助下完成， 在肖扬老师的大力帮助下，本文作者对分组密码、l d p c 码编译原理，加密纠错结 合进行了深入研究。密码与l d p c 纠错码的结合以其优异的安全性和纠错能力， 在今后的保密通信系统中具有潜在的应用前景，因此本论文研究内容具有理论和 实用意义。 本文在分别研究分组密码特别是高级数据加密标准a e s ，以及l d p c 编译码 理论的基础上，设计了l d p c 纠错密码，并实现了基于l d p c 纠错密码的编解码 系统的设计。本文设计的l d p c 纠错密码在实现保密通信的同时，还具有很好的 纠错性能。 引言 l 引言 本章简要介绍l d p c 码的研究现状，密码的背景知识以及保密通信的意义， 简要描述了加密纠错编码领域的相关工作及发展现状；最后总结了作者在攻读硕 士期间所做的主要工作并给出了本文内容安排。 1 1 研究的背景和意义 1 1 1l d p c 码的研究现状 低密度校验( l d p c ) 码是一类能够达到s h a n n o n 极限的线性分组码。长的 l d p c 码的性能甚至于比t u r b o 码的性能还要优越。l d p c 码的主要优点是存在一 种叫做“置信传播”( b e l i e fp r o p a g a t i o n ) 的迭代译码算法。这种译码算法的复杂 度随着码长呈线性增长，并且非常适合于并行实现。 l d p c 码最初是g a l l a g e r 于1 9 6 2 年在他的博士论文里提出的。后来t a n n e r 发 展了g a l l a g e r 的思想，用t a n n e r 图来表示码字，定义了变量节点和限制节点；w i b e r g 进一步发展了这种思想，引入了状态变量节点，使得传统的卷积码理论与“定义 在图上的码 ( c o d e sd e f i n e do ng r a p h s ) 联系起来。在被遗忘了3 0 多年后，m a c k a y 和n e a l 于1 9 9 5 年重新研究了l d p c 码，证明在利用和积( s u m - p r o d u c t ) 算法译 码时l d p c 码具有接近s h a n n o n 极限的性能。2 0 0 1 年，r i c h a r d s o n 等人提出了密 度进化方法用来分析和优化l d p c 码。c h u n g 等人在同一年提出了全高斯近似算 法来简化密度进化，并利用这种方法进行了二元非规则l d p c 码的设计。2 0 0 4 年， a r d a k a n i 提出了半高斯近似算法，并利用半高斯近似算法分析和设计了b p s k 调 制下的二元非规则l d p c 码。在2 0 0 0 年，b r i n k 首先介绍了外信息转移( e x i t ) 图技术，b r i n k 用e x i t 图技术分析和设计了二元非规则l d p c 码，并且利用e x i t 图技术设计了l d p c 编码的多数入多数出( m i m o ) 系统。2 0 0 4 年，l a n d 等人和 s u t s k o v e r 等人独立的对e x i t 图方法进行了信息论探讨，给出了e x i t 图技术的信 息论基础。 l d p c 码可以很自然的推广到高阶域。1 9 9 8 年，m a c k a y 和d a v e y 发现高阶域上 的l d p c 码的性能比最优的t u r b o 码的性能还要好。m a c k a y 和d a v e y 还介绍了蒙 特卡罗( m o m ec a r l o ) 仿真来分析高阶域上的l d p c 码在无限码长下的行为。 l d p c 码的译码算法有和积( s u m p r o d u c t ) 算法、最小和( m i n s u m ) 算法和 北京交通大学硕十学文论文 最大积( m a x p r o d u c t ) 算法等，k s c h i s c h a n g 等人在2 0 0 1 年用分解图( f a c t o r - g r a p h ) 理论统一了这些解码算法。在k s c h i s c h a n g 等人的论文中还介绍了二元l d p c 码的 对数域解码算法。b a m a u l t 等人和s o n g 等人在2 0 0 3 年独立的提出了高阶域上l d p c 码基于多维快速傅立叶( f f t ) 的解码算法。2 0 0 4 年，w y m e e r s c h 等人介绍了高 阶域l d p c 码的对数域解码算法。 在现代通信系统中，纠错码的设计是保证数据可靠传输的一个重要组成部分， 因为它可以检测并纠正信号传输过程中引入的错误。1 9 4 8 年，s h a n n o n 提出的编 码理论【l 】中证明：对于一个信道容量为c 的有扰信道，信息源产生信息的速率为r ， 只要r c ，则总可以找到一种信道编码和译码方式，使编码错误率随着码长的增 加，按照指数下降到任意小的值；若r - c ，则不存在能够实现无误码率传输的编 译码方式。但是s h a n n o n 定理并没有给出相应的实现方式。若干年来，随着通信 技术的高速发展和实际应用的不断提高，人们一致的努力寻找能够更加逼近 s h a n n o n 理论极限的优秀编译码方式，从最早的分组码、代数码到r s 码、卷积码， 直到今天的t u r b o 码、l d p c 码，系统性能与s h a n n o n 极限的差距越来越小。 虽然l d p c 码的理论及应用研究已经取得了不少进展，但仍然存在许多问题 需要解决，如码字结构优化，编码的复杂度，译码的复杂度以及实现。 1 1 2 密码背景简介 密码学是一门有着悠久历史的应用科学。传统上，密码学的研究内容包括密 码编码学和密码分析学两部分。密码编码学研究如何编制密码保护信息不外泄， 而密码分析学研究如何破译密码获取情报。两者相互依赖、相互促进。此外，近 几年密码学还出现了一个新的研究分支密码密钥学，它以密钥的产生、分发、存 储和销毁为研究内容。上述三个部分构成了现代密码学的研究框架。 密码学的历史可以追溯到公元前二十世纪的古埃及，那时的埃及人使用可以 变形的象形文雕刻法老王的墓碑。到公元前五百年左右，斯巴达出现了最原始保 密通信设备“s k y t a l e ”1 2 】所谓的“s k y t a l e ”实际上就是一对粗细相同圆木棒，发 信者把一根皮条缠绕在木棒上，然后沿着木棒的纵向在皮条上写信，写完后结下 皮条，这样上面的文字就是杂乱无章的。收信人将皮条从新缠绕在另一根木棒上 就能读取信件了。在罗马帝国时期，凯撒大帝为了避免军事文书在传递过程中被 泄露，亲自设计了“凯撒密码”。这是一种简单的置换密码，公元十世纪左右， 频度分析法诞生【3 】，可以有效的破译置换密码和单表替代密码【4 1 。在两次世界大战 中，密码也扮演了十分重要的角色，密码的的成功破译往往决定着战事的走向。 从己公开的史料看，盟国在二战中取得胜利，密码破译功不可没。 引言 1 9 4 8 年和1 9 4 9 年，香农先后发表了“am a t h e m a t i c a lt h e o r yo f c o m m u n i c a t i o n 和“c o m m u n i c a t i o nt h e o r yo fs e c r e c ys y s t e m s b , 5 】。这两篇论文奠定了密码学的 理论基础，代表了现代密码学的开端，从此密码学成为了一门真正的学科。1 9 7 6 年，d i 佑e 和h e l l m a n 提出了公钥密码学，开创了密码学研究的新方向，并且将密 码学的研究从幕后搬到了台前。一年后，根据公钥密码的思想，r i v e s t ，s h a m i r 和 a d l e m a n 三人提出了r s a 密码系统，它不仅可以用来加密信息还可以实现数字签 名。1 9 7 6 年，美国国家标准局颁布d e s ( d a t ae n c r y p t i o ns t a n d a r d ) 作为美国信息 加密标准。2 0 0 0 年，美国国家标准技术研究所( n i s t ) 正式公布了a e s 算法。 1 1 3 保密通信的意义 保密学或者从比较窄的范围内讲的密码学，是一门研究通信安全和保护信息 资源的既古老而又年青的科学与技术。它包括两个方面：密码编码学和密码分析 学。密码编码学是对信息编码以隐藏信息的一门学问；而密码分析学是研究分析 破译密码的学问。这二者既相互对立又相互促进，共同推动密码学的发展。 下图就是一张数字通信保密系统模型 图1 1 数字通信保密系统模型 f i g 1 1d i g i t a ls e c u r ec o m m u n i c a t i o ns y s t e mm o d e l 当今时代是信息的时代，随着电子计算机和通讯网络的广泛应用，人们对信 息的依赖程度越来越高；相应的，信息对社会的影响也越来越大。各种网络业务 ( 如电子商务、电子事务、电子政务、数字货币、网络银行等等) 的兴起，信息 安全问题再也不仅仅是保密的问题，它还需要保证信息的可靠性、可用性、可控 北京交通大学硕士学文论文 性、完整性等等。概括起来，信息安全应该是综合运用一切手段、使信息从信源 到新宿传输的整个过程中，在通信的各个层次和不同的观察角度，在获取、存贮、 显示、变换、处理、传递等各个环节上保证信息的可靠性、可用性、可控性、完 整性、秘密性的理论和技术。在享受信息化带给我们种种便利的同时，各种信息 安全问题也凸现出来。从大的方面来说，信息安全问题已经威胁到国家的政治、 经济、军事、文化、意识形态等领域；从小的方面来说，信息安全问题也是人们 能否保护自己个人隐私的关键。可见，研究信息安全技术具有重大的理论意义和 迫切的实际意义。 1 2 加密纠错编码领域的相关发展 纠错码与密码学是两门不同的学科。在7 0 年代以前它们几乎互不相关各自独 立的向前发展。1 9 7 6 年d i f f i e 和h e l l m a n 发表了在密码学领域内具有里程碑意义 的文章密码学的新方向【6 1 ，提出了新的密码思想，使得密码体制的安全性常常建 立在某个难解的数学问题之上，并提出了第一个公开密钥密码体制( 简称公钥体 制) 。随后，很多学者构造了许多不同的基于数学难解问题的公钥密码系统，如 r s a 、背包体制、e 1 g a m a l 方案等。1 9 7 8 年b e r l e k a m p 、m c e l i e c e 和t i l b r o g 等证 明了纠错码理论中一般线性码的译码问题是n p c 问题【_ 7 1 ，同年m c e l i e c e 根据一般 线性分组码的译码问题上一个n p c 问题，g o p p a 码具有快速译码的特点，利用 g o p p a 码构造了第一个公钥密码体制，简称m c e l i e c e 体制【8 】。自此以后，有关密 码学与纠错码相结合的研究，利用纠错码构造各种密码系统和认证系统的研究得 到迅速发展，从而把这两门原本无关的学科结合在一起。 1 9 8 4 年，t r r a o 提出了一个私钥密码体带l j t 9 ，该体制是m c e l i e c e 公钥体制的 变形，基本思想是将m c e l i e c e 公钥用于私钥密码体制。在大多数表决攻击下，攻 击者可有效地得到该体制的私钥。当r a o 私钥密码体制中的错误向量的重量大约 等于码长的一半时，大多数表决方法不能成功，基于此，r a o n a m 私钥密码体制 使用了预先定义的具有不同伴随式平均h a m m i n g 重量等于码长一半的错误向量 集，但存储限制了作为密钥的错误向量集容量，从而使得r a o n a m 私钥密码体制 的安全强度不够。李元兴和王新梅【lo 】提出了一个可用作加密盒认证的私钥密码体 制。l i w a n g 方案利用在r a o n a m 私钥密码体制中嵌入潜信道的方法来提供认证 功能，它比r a o n a m 私钥密码体制的功能多，但其安全性要比r a o n a m 私钥密码 体制的安全性低。王新梅教授在文献【l i 】中提出了具有纠错能力的私钥密码体制 m c 分组加密纠错体制。这一方案的思想是建立在m c e l i e c e 公钥密码体制基础上， 基本思想是对明文先进行纠错编码，再采用分组密码加密。 4 引言 1 3 本文的研究重点和所作的工作 本文结合前人的工作，采用理论分析和计算机仿真相结合的方法，对纠错与 加密的结合进行了深入研究。本文重点研究了采用宽轨迹策略的分组密码a e s 和 有着优异纠错能力的l d p c 码，结合二者的优点，设计l d p c 纠错密码，并以l d p c 纠错密码为基础构建了l d p c 纠错密码编解码系统。并在文章的最后给出了实验 结果，安全性分析和纠错能力分析。 全文共分为五章，具体安排如下。 第一章是引言，概述了本文所涉及到l d p c 码的研究现状，密码的相关背景 知识，保密通信的意义，并简要介绍了纠错与加密结合的发展。 第二章对本文研究的重点之一分组密码，尤其是a e s 给出了详细的描述，并 对本文涉及到的一些密码学的概念给出了理论分析，如款轨迹策略、f e i s t e l 结构、 雪崩效应等。最后详细的描述了前人在纠错与加密结合领域所作的工作。 第三章首先介绍了l d p c 码的理论背景，包括信道编码定理、纠错码和分组 码的基本原理。然后介绍了l d p c 码的定义及t a n n e r 图表示。在此基础上，介绍 了几种主要的l d p c 码的校验矩阵的构造方法，最后给出了l d p c 码的编译码方 法。 第四章首先给出了我设计的l d p c 纠错密码的结构，通过理论分析给出了设 计依据。然后给出了l d p c 纠错密码编码译码方法，并基于l d p c 纠错密码设计 了l d p c 纠错密码编解码系统。最后给出了l d p c 纠错密码的安全性分析、纠错 能力分析以及实验结果。 第五章对本文的工作进行总结并对以后的工作给出了展望。 研究背景及相关工作 2 研究背景及相关工作 这一章，我们首先介绍了密码的分类，然后详细描述了分组密码及其性质与 设计结构，尤其对高级加密标准a e s ，我们给出了细致的描述。接着我们讨论了 两种密码分析方法，差分分析和线性分析。最后我们在讨论了在纠错与加密相结 合这一领域的一些重要的研究成果。 2 1 密码的分类 密码是一个用来描述加密和解密两个泾渭分明的函数的算法或技术的术语。 加密是打乱信息的过程，明文，利用密码知识，密钥，转变成难以理解的密文形 式。解密是加密的反过程，密文通过利用相同的或不同的密钥将密文恢复成明文。 加密密钥和解密密钥不同的密码体制被称作公钥密码体制。r s a ，e l g a m a l ，e l l i p t i c c u r v e s 5 】是一些常见的公钥密码。另一方面，加密密钥和解密密钥相同的密码体制 被称作私钥密码体制或对称密码体制。d e s ，r c 4 和a e s 是一些常用的对称密码。 对称密码可以一次一个比特或分组的加密明文。对明文加密一次只加密一个比特 的密码称作流密码。例如，r c 4 密码就是一个流密码。对明文加密一次加密一个 分组的对称密码叫做分组密码。例如，a e s 分组密码每次加密1 2 8 b i t 明文。 密码 !叵 叵叵 围曰三 厂ip = i 图2 1 ：密码的分类 f i 9 2 1c l a s s i f i c a t i o no fc i p h e f 分组密码有很多运行模式。最常用的分组模式是电码本模式( e c b ) 和密码 分组链接模式( c b c ) 。但是，如果在流模式下使用分组密码，它也可以在加密明 7 北京交通大学硕士学文论文 文时每次只对- - l k 特加密。计数器模式( c t r ) 和输出反馈模式( o f b ) 是一些用 于分组密码的标准的流模式。图2 1 给出了密码的分类。 2 2 分组密码 分组密码加密明文时每次对一个分组加密。在大多数现代分组密码中，一个 本身并不安全的函数f ，经过反复使用一定的次数后，可以到达所需要的安全级 别。这种密码被称作迭代分组密码。 对于明文，p ，密文，c ，和密钥，足，密码提供的安全性是可以度量的， 条件熵h ( kc ) ，被称作密钥的疑义度，是在只有密文攻击【1 2 】的情况下密文中所 呈现的密钥的信息量。它由下面的公式给出， h ( kc ) = h ( k ) + 日( p ) 一日( c ) ( 2 2 1 ) 是熵函数。但是，当今的分组密码对于这类攻击都是安全的。还有其它种 类的攻击如已知明文的选择明文攻击和选择密文攻击。多数实际有效的密码分析 是通过将以上几种方法结合。例如，差分分析【l3 】是一种选择明文攻击，线性密码 分卡斤【1 4 】是一种己知明文攻击任何一种分组密码，如果对于所有已知的密码分析， 它在获取其密钥的计算上是不可行的，那么它就被认为是安全的。此外，这些年 研究者们还证明了一些可以被用来作为密码算法安全度量标准的重要性质。我们 将在接下来的章节中讨论这些性质。 2 2 1分组密码的性质 香农于1 9 4 9 年在他具有发展性的论文：保密系统的通信理论【5 】里描述了对密 码系统的一般设置。他建议了两个性质，扩散和置乱，作为设计密码的要点。直 到今天这些性质依然意义重大而且所有的现代分组密码都体现了这些性质。下面 是对扩散与置乱的简单描述。 1 扩散 扩散的性质揭示了导致其出现冗余的消息空间的统计结构消失在密文的大范 围的统计过程中。在量化概念上它指的是每一位明文和密钥比特所影响的密文比 特的数量。这使得明文和密文之间的关系尽可能的复杂。扩散一般可由重复置换 获得。完成扩散目的的轮函数f 被称作扩散层。扩散性质也会影响密码效率，只 是因为，如果我们用很少的操作就达到了扩散的目的，那么，我们只需要很少的 几个循环就到达了所需的安全级别。此外有的密码分析技术就利用了密码扩散比 较慢的特点，例如d e s 的差分分析就利用了其f e i s t e l 结构扩散满的缺点。 研究背景及相关工作 2 置乱 这更多的是一个定性的概念，从直观感觉上讲，期望所有的密文，明文和密钥 之间都是非线性的关系。置乱性质使得密文与密钥空间的关系变得非常复杂。在 分组密码中s 盒具有置乱性质。这些单元也往往是大多数分组密码中主要的非线 性部分。如果s 盒的每一比特输出之于每一比特输入都是非线性关系，反之亦然， 那么，这个s 盒就满足了置乱的标准。如果不是这样的话，s 盒中的偏差可能被用 来破坏密码。例如，线性分析首先通过寻找s 盒的近似线性表达式来搜集密钥信 息，然后在把它扩展到整个密码。所以s 盒的设计对于维护分组密码的整体安全 是至关重要的。 3 雪崩效应 术语雪崩是由f e i s t e l ”】提出来的，里面提到输入的微小变化会在输出时引 起巨大的改变。输入的一个比特的改变在一轮迭代后引起多个比特的改变，第二 轮后更多的比特被改变，这样下去，直到有大约分组的一半都随机改变了。对于 任何分组密码，我们都希望一个单独的输入比特能够影响到每一个输出比特：如 果有一个比特的改变，我们希望输出的一半比特都能改变( 扩散) 而且还不依赖 于比特的位置( 置乱) 。所以雪崩效应在密码中作为研究加密函数的标准得到广泛 的应用。在下一节中，我们将给出两种用于设计分组密码的基本策略的概述，以 及他们是如何产生及传播雪崩效应的。 2 2 2 著名大分组密码设计方案 两种最著名的分组密码设计方案是f e i s t e l 密码结构和宽轨迹策略。在这一节， 我们会简短的介绍两种策略。 1 f e i s t e l 结构 这是被广泛用于分组密码设计的之中策略。像d e s ，b l o w f i s h ，r c 5 和 f e a l 9 1 等分组密码都是基于这种结构的。在f e i s t e l 结构里，在每轮迭代i 中，明 文被分成两个部分x ，= x ? l ix ，左右两部分，在每轮迭代中，只有一半的输入 分组参与运算。任何非线性，函数都可以应用在f e i s t e l 结构中，而f 函数使用密 钥非线性的转换一半的明文。那就是，f ： o ，1 2 0 ，1 ) ”一 0 , 1 1 酬2 ，m 是密钥比 特数。f e i s t d 结构中的轮函数可以如下描述，x 川= ( ；( x 产) ox f ) l ix 产。其中k ， 是循环子密钥。这种设计使得加密和解密过程是相似的，除了在解密时要逆序使 用密钥。对明文不均等分割的f e i s t e l 结构，我们称作不平衡f e i s t d 结构。f e i s t e l 结构的主要弱点是对于每一轮迭代，输入分组的一些迭代总是固定不变。这被用 于很多密码攻击。例如对d e s 的差分密码分析【1 3 】和线性密码分析【1 4 1 就利用了这一 9 北京交通大学硕士学文论文 弱点将一次循环的差分和线性特征延伸到多次循环。 2 宽轨迹策略 宽轨迹策略【1 6 】是部分基于替换置换网络【1 7 】。在每轮迭代中整个输入分组都进 行变换。虽然这种方法相对于f e i s t e l 结构每轮迭代更繁重，但是却能减少加密所 需的迭代轮数。像r i j n d a e l t l8 1 ，s q u a r e t l 9 】和s h a r k 2 0 1 等分组密码都是基于这种策略 的。 大多数的密码分析攻击都利用了从密文的差异相关性到明文或密钥的差异相 关性的不均衡映射。宽轨迹策略的目的就是在很少几轮迭代中就将差异相关性散 布到整个密文中。这种方法能有效的阻止利用输入分组中次级分组的差异相关性 的传播进行密码分析攻击。密码的扩散层的扩散强度是达到宽轨迹策略的关键。 然而，扩散仅仅是个概念。为了度量扩散，我们经常使用一个叫做分支数的度量 尺度。分支数是输入和输出活动字节( 输入输出分组中非零差异) 的总合。宽轨 迹策略提出了一种简单的技术，用很少的几轮迭代最大化活动字节的和值。活动 字节和值的下界给出了密码抗密码分析攻击的下界。实际上，r i j n d a e l 分组密码就 是基于宽轨迹策略的并被选做a e s 加密标准。接下来我们将给出a e s 加密的概述。 2 2 3 高级数据加密标准( a e s ) 1 9 9 7 年1 月2 日，美国国家标准和技术协会( n i s t ) 宣布征集一个新的对称 密钥分组密码算法作为取代d e s 的新的加密标准。这个新的算法将被命名为高级 加密标准( a e s ) 。经过公众评论，决赛筛选，于2 0 0 0 年l o 月2 开，n i s t 宣布 选中了r i j n d a e l 来建议作为a e s 。r i j n d a e l 是由两个比利时密码学家d a e m e n 和 r i j m e n 共同设计的，它是具有分组长度和密钥长度均可变的分组密码。密钥长度 和分组长度可以独立地指定为1 2 8 比特、1 9 2 比特或2 5 6 比特。为简化期间，我们 只讨论最小，即密钥长度1 2 8 比特、分组长度1 2 8 比特时的情形。我们所限定的 描述无损于r i j n d a e l 密码工作原理的一般性。 在这种情况下，1 2 8 比特的消息( 明文，密文) 分组被分成1 6 个字节( 一个 字节是8 比特，所以有1 2 8 = 1 6 x8 比特) ，记为： 输入分组= m o ，m ，m s 密钥分组也是这样： 输出密钥= k o , k ，k ， 内部数据结构的表示是一个4 x4 矩阵： 1 0 研究背景及相关工作 输入分组= 输入密钥= 同d e s ( 以及最现代的对称密钥分组密码) 一样，r i j n d a e l 算法也是由基本的变换 单位“轮 多次迭代而成。在消息分组长度和密钥分组均为1 2 8 比特的最小情况， 轮数是1 0 。当消息长度和密钥长度变大的时候，轮数也相应增加。黜i n d a e l 中的轮 变换记为r o u n d ( s t a t e ，r o u n d k e y ) 。 这里s t a t e 是轮数据矩阵，既被看作是输入，也被看作是输出；r o u n d k e y 是轮 密钥矩阵，他是由输入密钥通过密钥表导出的。一轮的完成将导致s t a t e 的元素改 变值( 也就是改变它的状态) 。对于加密( 对应地，解密) ，输入到第一轮中的s t a t e 就是明文( 对应地，密文) 消息矩阵输入分组，而最后一轮中输出的s t a t e 就是密 文( 对应地，明文) 消息矩阵。 轮( 除最后一轮) 变换有四个不同的变化组成，这些变换是将要介绍的内部函 数： r o u n d ( s t a t e ，r o u n d k e y ) s u b b y t e s ( s t a t e ) ； s h i f t r o w s ( s t a t e ) ； m i x c o l u m n s ( s t a t e ) ； a d d r o u n d k e y ( s t a t e ，r o u n d k e y ) ； ) 最有一轮有点不同，记为： f i n a l r o u n d ( s t a t e ，r o u n d k e y ) 它等于不使用m i x c o l u m n s 函数的r o u n d ( s t a t e ，r o u n d k e y ) 。下面我们给出r i j n a e l 密码内部函数的简单介绍。 1 内部函数s u b b y t e s ( s t a t e ) 这个函数为s t a t e 的每一个字节( 就是x ) 提供了一个非线性代换，任一非零数 据z ( 只。) 被下面对变换所代换： y = a x 一1 + b ( 2 2 2 ) 、，j， 他u m m八叫刈i叫 掰m m 所 t 霸霸 脓加加肿 脓鼬巾 m m m m 豇后尼后 o l 2 3 1 r 1 i 鼍 北京交通大学硕十学文论文 这里 a = o 0 o o 1o l1 11 1l 11 ol 和b ： 如果x 是零字节，那么y = b 就是s u b b y t e s 变换得结果。 我们应该注意到在式子( 2 2 2 ) 中变换的非线性仅仅来自于工，如果这个变 换直接作用于x ，那么在式子( 2 2 2 ) 中的仿射方程将绝对是线性的! 因为8 8 常数矩阵彳式可逆的( 也就是说，它的行在只。中是线性无关的) ，所 以式子( 2 2 2 ) 中的变换是可逆的，因此函数s u b b y t e s ( s t a t e ) 是可逆的。 2 内部函数s h i f t r o w $ ( s t a t e ) 这个函数在s t a t e 的每行上运算。对于1 2 8 比特分组长度的情形，他就是下面 的变换： s o ，0 s l ，0 s 2 ，0 s 3 ，0 s o ，1 s l ，1 s 2 ，1 s 3 ，l s o ，0 s l ，i s 2 ，2 s 3 ，3 s o ，1 s o ，2 j 2 3 s 3 ，0 s o ，2 s o ，3 s 2 ，0 s 3 ，i s o ，3 s o ，0 s 2 ，1 s 3 ，2 ( 2 2 3 ) 这个运算实际上是一个换位密码，它只是重排了元素的位置而不改变元素本 身：对于在第i ( i = 0 ，1 ，2 ，3 ) 行的元素，位置重排就是“循环向右移动”4 - i 位置。 既然换位密码仅仅重排了元素的位置，那么这个变换当然是可逆的。 3 内部函数m i x c o l u m n s ( s t a t e ) 这个函数在s t a t e 的每列上作用，所以对于( 2 2 3 ) 式中右边的矩阵的四列 s t a t e ，m i x c o l u m n s ( s t a t e ) 迭代四次。下面只描述了对- y u 的作用，一次迭代的输 出仍是一列。 首先，令 s o j l s 2 j 3 1 2 1 1 0 o o 1 1 o 1 l l l 0 o o 1 1 1 1 o o o 1 1 l 1 o o 0 1 l l l o 0 o 1 1 1 l 0 1 1 1 1 1 o o l l 1 1 1 o o o 专 、 3 3 3 3 仉 k 厶 炙 鄢瓯兜如 2 2 2 2 仉 h 厶 舅 s j s j 研究背景及相关工作 是式( 2 2 3 ) 中右边矩阵中的一列，注意到为了表述清楚我们已经省略了列数。 把这一列表示为3 次多项式： s ( x ) = s 3 x 3 + s 2 2 2 + j l x + s o x 注意到因为j ( 功的系数是字节，也就是说是只。上的，因此不是r i j n a e l 中的元素。 列s ( x ) 上的运算定义为将这个多项式乘以一个固定的3 次多项式c ( x ) ，然后模 z 4 + 1 ： c ( 工) 5 ( x ) ( m o d x 4 + 1 ) ( 2 2 4 ) 这里固定的多项式c (