（计算数学专业论文）基于aes和ecc的混合密码体制研究及应用.pdf

摘要 基于a e s 和e c c 的混合密码体制研究及应用 作者简介：张丞，男，1 9 8 0 年1 2 月出生，于2 0 0 4 年9 月师从于成都理工大学 乇新序教授，于2 0 0 7 年7 月获硕士学位。 摘要 随着电子商务的广泛应用，网络信息安全变得越来越重要，而网络信息安全 的核心在于密码技术。椭圆曲线密码体制是一种公钥密码体制，相对于以往基于 有限域上离散对数问题或大整数分解问题的传统公钥算法，椭圆曲线密码算法具 有安全性高、速度快、密钥短、实现时所需占用资源少的特点。另一方面，最新 的对称算法a e s 具有简洁、高效、安全性高等优点，是对称密码体制中的一个相 当好的标准。 本文通过对现有数据加密体制的分析，提出了一种将a e $ 算法和椭圆曲线密 码( e c c ) 体制相结合的混合数据加密体制，从而更为高效地实现了网络通信系统 中的信息加密、数字签名和身份验证，解决了密码体制中速度和安全性不能兼顾 的问题。文章首先在对目前信息安全的现状和数据加密技术的基本概念及数学模 型作了简单综述的基础上，研究分析了各种数据加密技术的思想、加解密流程， 给出了对称密码、公钥密码体系的数学背景及其特点；其次，针对数据加密方法 的特点，提出了基于a e s 与f f o c 的混合密码体制，并就这两种算法的数学原理、 算法实现、安全性能等方面进行了详细的讨论：同时还给出基于a e s 与f f c c 的混 合密码体制的工作原理；最后对a e s 和e c c 的混合密码体制运用于西南交通信息 网安全电子邮件的服务系统中的实现方案进行了论述。从而使e c c 密码体制密钥 短，计算开销少，带宽要求低、运算速度快的优点和a e s 算法的安全性能高的优 势充分的发挥，有效的解决了电子邮件的机密性、身份鉴别、完整性和不可否认 性。 关键词：a e s ；e c c ；混合密码体制；数字签名；安全电子邮件 成都理：【：大学硕十学位论文 r e s e a r c ha n da p p l i c a t i o no fm i x e d c r y p t o s y s t e m b a s e do nt h ea e sa n de l l i p t i cc u r v e c r y p t o g r a p h y a b s t r a c t a l o n g w i t ht h ee l e c t r o n i cc o m m e r c ew i d e s p r e a da p p l i c a t i o n ，t h en e t w o r k i n f o r m a t i o ns e c u r i t yc h a n g e sm o r ea n dm o r ei m p o r t a n t l y , b u tt h en e t w o r ki n f o r m a t i o n s e c u r i t yc o r el i e si nt h ep a s s w o r dt e c h n o l o g y e l l i p t i cc u r v ec r y p t o g r a p h y ( e c c ) s y s t e m s w h i c hi sap u b l i c k e ys y s t e m si sc h a r a c t e r i z e db yh i g h e rs a f e t yp r o p e r t y ， f a s t e r s p e e d ，s h o r t e rk e yl e n g t h sa n d f e w e r c o m p u t a t i o n a l r e s o u r c e sf o r i m p l e m e n t a t i o nt h a n o t h e rf o r m e rt r a d i t i o n a lp u b l i c - k e ya l g o r i t h m sb a s e do nt h e d i s c r e t el o g a r i t h mi n f i n i t ef i e l d so rt h eg r e a ti n t e g e rf a c t o r i z a t i o np r o b l e m o nt h e o t h e rh a n d ，t h ea d v a n c e de n c r y p t i o ns t a n d a r di sag o o ds y m m e t r yc r y p t o s y s t e m w i t hi t sa d v a n t a g e so fs i m p l i c i t y , h i g he f f i c i e n c ya n ds e c u r i t y t h ep r e s e n td a t ae n c r y p t i o ns y s t e m sa r ea n a l y z e di nt h ed i s s e r t a t i o nt op r o p o s e t h em i x e dc r y p t o s y s t e mb a s e do nt h ea e sa n de l l i p t i cc u r v ec r y p t o g r a p h y ，w h i c h w i l la c t u a l i z ee n c r y p t i o no fd a t a ，d i g i t a ls i g n a t u r ea n di d e n t i f i c a t i o nw i t hh i g h e f f i c i e n c yi ni n t e m e tc o m m m f i c a t i o n ，a n ds o l v et h ep r o b l e mo fa n t i n o m yo fs p e e da n d s e c u r i t yi nc r y p t o s y s t e m f i r s t ，t h i sd i s s e r t a t i o nr e s e a r c h e s a n d a n a l y z e so nt h e t h o u g h t ，t h em e t h o da n de c o l o g ya n df i e l do fa p p l i c a t i o n o fm a n yk i n d so fd a t a e n c r y p t i o nt e c h n o l o g ys h o wt h em a t h e m a t i c a ld e s c r i p t i o nt os y m m e t r yc r y p t o g r a m a n dp u b l i ck e yc r y p t o g r a ma n di t sc h a r a c t e r i s t i c sb a s e do nb r i e f l yo nt h ec u r r e n t s i t u a t i o no ft h ei n f o r m a t i o ns e c u r i t ya n dt h eb a s i cn o t i o na sw e l la sm a t h e m a t i c a l m o d e lo fd a t ae n c r y p t i o nt e c h n o l o g y ；s e c o n d l y , t h em i x e dc r y p t o s y s t e mb a s e do n a e sa n de c ci sb u i l df o r w a r di na c c o r d i n gw i t ht h ec h a r a c t e r i s t i co ft h ee n c r y p t i o n m e t h o do ft h ed a t at h ed e t a i l e dd i s c u s s i o ni sh o l do nt w om a t h e m a t i c a lp r i n c i p l e s ， a l g o r i t h mr e a l i z a t i o n ，s a f ep e r f o r m a n c e ，e t c a tt h es a n l et i m ei t sw o r kf l o wi sa l s o g i v e n ；f i n a l l y , t h ep l a nw h i c hi sa p p l i e dt ot h es e c u r i t ye m a i ls y s t e mo fs o u t h w e s t t r a f f i cn e t w o r ki se l a b o r a t e d t h ea d v a n t a g e so ft h ee c cc r y p t o s y s t e ms u c ha s s h o r t k e y , l o we x p e n s e s ，l o wr e q u e s to ft h eb a n d ，t h eq u i c ks p e e do fc a l c u l a t i o na n d t h eh i g hs u p e r i o r i t yo fa e sa l g o r i t h me f f e c t i v e l ys o l u t et h ep r o b l e mo ft h e c o n f i d e n t i a l i t y , t h ep e r s o n a li d e n t i f i c a t i o n ，t h ei n t e g r i t ya n dt h en o n r e p u d i a t i o no f e m a i l k e yw o r d s ：a e s ；e c c ；m i xc r y p t o s y s t e m ；d i g i t a ls i g n a t u r e ；s e c u r ee - m a i l i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得盛壑理 ：太堂或其他教 育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者导师签名： 多弘 学位做作者签名：芬垄 学位论文版权使用授权书 名月 f 一 本学位论文作者完全了解盛壑堡王太堂有关保留、使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和 借阅。本人授权盛壑堡太堂可以将学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名 年月 日 年 1， p加 第1 章引言 第1 章引言 1 1 课题的背景和学术意义 随着计算机和通信技术的迅猛发展，大量敏感信息常常通过公共通信设施 或计算机网络进行交换，特别是i n t e r n e t 的广泛应用、电子商务和电子政务的 迅速发展，越来越多的个人信息需要严格保密，如：银行帐号、个人隐私等。 因此，如何保护信息的安全使之不被窃取及不至于被篡改或破坏，己成为当今 被普遍关注的重大问题。而目前针对网络的攻击手段更是五花八门，攻击者可 以窃取网络上的信息，如用户口令、数据库信息等；伪造用户身份、否认自己 的签名，这对网络的进一步推广和应用构成了严重的威胁。 为了保护网络通信的安全，促进电子商务和电子政务的快速发展。因此， 对网络通信，特别是电子商务中的安全技术进行研究，发展自主的加密技术己 成为一个迫在眉睫的课题。近几年，有不少专家、学者致力于密码学的研究， 其安全理论和安全产品已有许多，为推动网络通信、电子文档的安全传输作出 了较大的贡献。 1 2 国内外研究现状 密码技术自古有之。目前己发展成为一门结合数学、计算机科学、电子与 通信、微电子等技术的交叉学科，使用密码技术不仅可以保证信息的机密性，而 且可以保证信息的完整性和确定性，防止信息被篡改、伪造和假冒。 信息安全服务依靠安全机制来完成，而安全机制主要依赖于密码技术，因此 密码技术是信息安全的核心。而密码算法( c r y p t o g r a p h ya l g o r i t h m ，用于加密 和解密的数学函数) 又是密码技术的核心。所以密码算法是保障信息安全的核 心之核心，其重要性不言而喻。 为此，世界各国对密码算法的研制都高度重视，1 9 7 7 年美国国家标准局 n i s t ( n a t i o n a l i n s t i t u t e o f s t a n d a r d s a n d t e c h n o l o g y ) 提出数据加密标准d e s ( d a t ae n c r y t i o ns t a n d a r d ) ，随后多种密码算法相继出现，这些算法有：r i j i n d a e l 、m a r s 、r c 6 、t w o f i s h 、s e r p e n t 、i d e a ( i n t e r n a t i o n a ld a t ae n c r y p t i o n a l g o r i t h m ) 、c s 2 c i p h e r 、姗b 、s k i p j a c k 、k a r n 等对称密码算法以及背包公 钥密码算法、r s a 、e i g a m a l 、椭圆曲线密码算法e c c ( e l l i p t i cc u r v e c r y p t o s y s t e m ) 、n t r u 等非对称密码算法。 以上这些算法有些已经遭到了破译；有些安全强度不高；有些强度不明， 成都理t 人学硕i 学位论文 有待于进一步完善。 1 2 1 对称算法现状 对称算法( s y m m e t r i ca l g o r i t h m ) ，有时又称传统密码算法。就是加密密 钥能够从解密密钥中推算出来，同时解密密钥也可以从加密密钥中推算出来。 而在大多数的对称算法中，加密密钥和解密密钥是相同的。所以也称这种加密 算法为秘密密钥算法或单密钥算法。它要求发送方和接收方在安全通信之前， 商定一个密钥。对称算法的安全性依赖于密钥，泄漏密钥就意味着任何人都可 以对他们发送或接收的消息解密，所以密钥的保密性对通信性至关重要。 对称加密的优点在于算法实现的效率高、速度快。 对称加密的缺点在于：第一，密钥量问题。在单钥密码系统中，每一对通 信者就需要一对密钥，当用户增加时，必然会带来密钥量的成倍增长，因此在 网络通信中，大量密钥的产生、存放和分配将是一个难以解决的问题。第二， 密钥分发问题。单钥密码系统中，加密的安全性完全依赖于对密钥的保护，但 是由于通信双方使用的是相同的密钥，人们又不得不相互交流密钥，所以为了 保证安全，人们必须使用一些另外的安全信道来分发密钥，例如用专门的信使 来传送密钥。这种做法的代价是相当大的，甚至可以说是非常不现实的，尤其 在计算机网络环境下，人们使用网络传送加密的文件，却需要另外的安全信道 来分发密钥，显而易见，这需要新的解决方法。常用的对称加密算法有d e s 、 d e a 和a e s 等。 d e s 算法由i b m 公司开发，并被美国国家标准局于1 9 7 7 年2 月采纳作为 “非密级”应用的一个标准，此后，d e s 成为全世界使用最广泛的加密标准。 d e s 算法加密时把明文以6 4 b i t 为单位分成块，采用美国国家安全局精心 设计的8 个s 盒( s ：s u b s t i t u t i o n ) 和p 置换( p ：p e r m u t a t i o n ) ，经过1 6 轮 迭代，最终产生6 4 比特密文，每轮迭代使用的4 8 比特子密钥由原始的5 6 比特 产生。d e s 的加密与解密的密钥和流程完全相同，区别仅仅是加密与解密使用的 子密钥序列的施加顺序正好相反。 d e s 算法在历史上曾发挥重要作用，但也存在以下问题： 1 ) d e s 密钥空间的规模2 5 6 对实际安全而言太小。2 ) d e s 的密钥存在弱 密钥、半弱密钥和互补密钥。3 ) d e s 里的所有计算，除去s 盒，全是线性的。s 盒的设计对密码算法的安全性至关重要。然而，美国国家安全局并没有公布s 盒 的设计原则，因此，有人怀疑s 盒罩隐藏了“陷门( t r a p d o o r s ) ”，如果是这样。 美国国家安全局就能轻易地解密消息。 此外，由于d e s 的密钥空间小，针对d e s 算法进行穷举攻击就可以取得成 2 第l 章引言 功。在1 9 9 8 年7 月，电子前沿基金会( e f f ) 使用一台2 5 万美元的电脑在5 6 小 时内破译了d e s 密钥。1 9 9 9 年1 月r s a 数据安全会议期间，e f f 通过遍布全 世界的1 0 万台计算机的协同工作，用2 2 小时1 5 分钟就宣告破解了一个d e s 的 密钥。 为了增强d e s 算法的安全性，密码设计者又提出了基于d e s 的 t r i p l e 2 d e s 、独立子密钥方法和推广的g d e s 算法等。这些改变有些作用不大， 有些还削弱了d e s 的安全性。总之，d e s 需要新的有效的加密标准来代替。 n i s t 于1 9 9 7 年1 月开始了遴选d e s 替代者高级加密标准a e 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 的确立过程简介如下： 1 ) 1 9 9 7 年9 月1 2 同，n i s t 在联邦登记处公布了征集a e s 候选算法的通告。 并对候选者提出以下基本要求：( 1 ) 比t r i p l e 2 d e s 快，且至少和t r i p l e 2 d e s 一样安全；( 2 ) 应当具有1 2 8 比特分组长度和1 2 8 1 9 2 2 5 6 比特密钥长度； ( 3 ) 具有较大的灵活性。 2 ) 1 9 9 8 年8 月2 0 日，n i s t 召开了第一次候选大会并公布了1 2 个国家的 1 5 个候选算法。 3 ) 1 9 9 9 年3 月2 2 日，n i s t 召开了第二次a e s 候选会议，从中选出5 个候选 算法：m a r s ( i b m ) 、r c 6 ( m i t ) 、s e r p e n t ( 英、以、美) 、t w o f i s h ( 美) 和 r i j n d a e l ( 比利时) 。 4 ) 2 0 0 0 年1 0 月2 日，n i s t 宣布比利时的密码学家j o a nd a e m e n 和v i n c e n t r i j m e n 设计的“r i j n d a e l 算法”最终获胜。 1 2 2 公钥密码算法现状 由于单钥密码系统存在难以解决的缺点，因此发展一种新的、更有效，更 先进的密码体制显得更为迫切和必要。在这种情况下，出现了一种新的公钥密 码体制，它突破性地解决了困扰着无数科学家的密钥分发问题。这一全新的思 想是本世纪7 0 年代，美国斯坦福大学的两名学者d i f f i e 和h e l l m a n 提出的， 该体制与单钥密码最大的不同是：在公钥密码系统中，加密和解密使用的是不 同的密钥( 相对于对称密钥，人们把它叫做非对称密钥) ，这两个密钥之间存在 着相互依存关系：即用其中任一个密钥加密的信息只能用另一个密钥进行解密。 这使得通信双方无需事先交换密钥就可进行保密通信。其中加密密钥和算法是 对外公开的，人人都可以通过这个密钥加密文件然后发给收信者，这个加密密 钥又称为公钥；而收信者收到加密文件后，它可以使用他的解密密钥解密，这个 成都理t 人学颂 学位论文 密钥是由他自己私人掌管的，并不需要分发，因此又称为私钥，这就解决了密 钥分发的闯题。 从以上的介绍可以看出，公钥密码体制的思想并不复杂，而实现它的关键 问题是如何确定公钥和私钥及加、解密的算法。我们假设在这种体制中，只是 公开信息，用作加密密钥，而& 需要由用户自己保密，用作解密密钥。加密算 法e 和解密算法d 也都是公开的。虽然& 与只是成对出现，但却不能根据坟计 算出& 。它们须满足条件： ( 1 ) 加密密钥最对明文x 加密后，再用解密密钥& 解密，即可恢复出明 文，或写为：d ( & ( e 只( x ) ) ) ：x ； ( 2 ) 加密密钥不能用来解密，即d ( 只( e 只( x ) ) ) x ； ( 3 ) 在计算机上可以容易地产生成对的只和& ； ( 4 ) 从已知的最实际上不可能推导出& ； ( 5 ) 加密和解密的运算可以对调，即：e ( 乓( d & ( x ) ) ) = x 。 从上述条件可看出，公开密钥密码体制下，加密密钥不等于解密密钥。加 密密钥可对外公开，使任何用户都可将传送给此用户的信息用公开密钥加密发 送，而该用户唯一保存的私人密钥是保密的，也只有他能将密文复原、解密。 虽然解密密钥理论上可由加密密钥推算出来，但这种算法设计在实际上是不可 能的，或者虽然能够推算出，但要花费很长的时自j 而成为不可行的。所以将加 密密钥公开也不会危害密钥的安全。 这种体制思想是简单的，但是，如何找到一个适合的算法来实现这个系统 却是一个真正困扰密码学家们的难题，因为既然只和& 是一对存在着相互关系 的密钥，那么从其中一个推导出另一个就是很有可能的，如果敌手能够从只推 导出& ，那么这个系统就不再安全了。因此如何找到一个合适的算法生成合适 的斥和& ，并且使得从斥不可能推导出& ，j 下是迫切需要密码学家们解决的 一道难题。这个难题甚至使得公钥密码系统的发展停滞了很长一段时间。 为了解决这个问题，密码学家考虑了数学上的陷门单向函数，根据关于陷 门单向函数的思想，学者们提出了许多种公钥加密的方法，它们的安全性都是基 于复杂的数学难题。根据所基于的数学难题，至少有以下三类系统目前被认为 是安全和有效的：即大整数因子分解系统( 代表性的有r s a ) 、椭圆曲线离散对 数系统( e c c ) 和离散对数系统( 代表性的有d s a ( d i g i t a l s i g n a t u r e a l g o r i t l u n ) ) 。 4 第1 章引言 1 3 本课题研究的主要内容和主要成果 本文首先在对目前信息安全的现状和数据加密技术的基本概念及数学模型 作了简单综述的基础上，研究分析了各种数据加密技术的思想、方法和应用领 域，给出了对称密码、公钥密码体系的数学描述及其特点；其次，针对数据加 密方法的特点，提出了基于a e s 与e c c 的混合密码体制，并就这两种算法的 数学原理、算法实现、安全性能等方面进行了详细的讨论；并给出基于a e s 与 e c c 的混合密码体制的工作原理；最后将a e s 和e c c 的混合密码体制运用于西 南交通信息网安全电子邮件的服务系统中。从而使公钥算法密钥易管理，密钥 短，计算开销少，带宽要求低，运算速度快的优点和对称算法的加、解密速度 快的优势充分的发挥，构造出安全、高效的密码系统，解决了电子邮件的机密 性、身份鉴别、完整性和不可否认性。 成都理t 大学硕f 学位论文 第2 章数据加解密体制综述 数据加密是以研究秘密通信和身份认证等为目的的，主要研究对传输信息 采取何种秘密的变换以防止第三者的窃取、破坏、篡改或否定等。本文所讨论 的数据加密技术是指传统密码技术基于计算机技术和现代数学( 如数论、近世代 数、组合数学等) 方法的数据加密技术，这些数学基础一方面为加密技术提供了 新的概念和工具，另一方面也为研究改进、破译现代密码系统的途径奠定了基 础。 2 1 对称密码体制 2 1 1 对称密码概述 对称密码又称保密密码或分组密码，它的一个显著特点是加密密钥和解密 密钥相同，对称密码比较典型和著名的有d e s ，i d e a ，a e s 等。以下将详细介 绍他们。 1 ) d e s d e s 由i b m 公司研制，1 9 7 7 年美国国家标准局正式批准其作为美国联邦信 息处理的非机密数据加密标准。自公布以来，d e s 一直超越国界成为国际上商 用保密通信和计算机通信最常用的加密算法，i s o 也将其作为数据加密标准。 d e s 是一个分组加密算法，它以6 4 位为分组对数据进行加密。同时d e s 也 是一个对称算法，即加密和解密用的是同一个算法。它的密钥长度是5 6 位，密 钥可以是任意的5 6 位的数，而且可以任意时候改变。其中有极少量的数被认为 是弱密钥，但是很容易避开他们。所以保密性依赖于密钥。 d e s 对6 4 ( b i t ) 位的明文分组m 进行操作，明文m 经过一个初始置换i p 置 换，将明文分成左半部分和右半部分，各3 2 位长。然后进行1 6 轮完全相同的 运算，这些运算被称为函数f ，在运算过程中数据与密钥结合。经过1 6 轮后， 左、右半部分合在一起经过一个末置换，最后所得到的输出即为密文。 在每一轮中，密钥位移位，然后再从密钥的5 6 位中选出4 8 位。通过一个 扩展置换将数据的右半部分扩展成4 8 位，并通过一个异或操作替代成新的3 2 位数据，再将其置换一次。这四步运算构成了函数f 。然后，通过另一个异或 运算，函数f 的输出与左半部分结合，其结果成为新的右半部分，原来的右半 部分成为新的左半部分。将该操作重复1 6 次，便实现了d e s 的1 6 轮运算。其 6 第2 章数据加解_ ；幸f 体制综述 图2 - id e s 算法流程图 2 ) i d e a i d e a 是1 9 9 0 年由瑞士联邦技术学院x j l a i 和m a s s e y 提出的建议标准算 法，称作p e s ( p r o p o s e de n c r y p t i o ns t a n d a r d ) 。l a i 和m a s s e y 在1 9 9 2 年 对p e s 进行了改进，强化了抗差分分析的能力后改称为i d e a 。它也是对6 4 b i t 大小的数据块加密的分组加密算法，密钥长度为1 2 8 位。i d e a 是基于“相异代 数群上的混合运算”设计思想，算法用硬件和软件实现都很容易且比d e s 在实 现上快。i d e a 自问世以来，已经经历了大量的详细审查，对密码分析具有很强 的抵抗能力，在多种商业产品中被使用。 这种算法是在d e s 算法的基础上发展出来的，类似于三重d e s 。发展i d e a 也是因为感到d e s 具有密钥太短等缺点，已不安全。i d e a 的密钥为1 2 8 位，这 么长的密钥在今后若干年内应是安全的。 类似于d e s ，i d e a 算法也是一种数据块加密算法，它设计了一系列加密轮 次，每轮加密都使用从完整的加密密钥中生成的一个子密钥。与d e s 的不同处 在于，它采用软件实现和采用硬件实现同样快速。 由于i d e a 是在美国之外提出并发展起来的，避开了美国法律上对加密技术 成都理t 人学硕l 学位论文 的诸多限制，因此，有关i d e a 算法和实现技术的书籍都可以自由出版和交流， 可极大地促进i d e a 的发展和完善。 ( 1 ) i d e a 算法密钥的生存 算法用了5 2 个子密钥( 8 轮中的每一轮需要6 个，其他4 个用与输出变换) 。 首先，将1 2 8 一位密钥分成8 个1 6 - 位子密钥。这些是算法的第一批8 个子密钥 ( 第一轮六个，第二轮的头两个) 。然后，密钥向左环移x 位后再分成8 个子密 钥。开始4 个用在第二轮，后面4 个用在第三轮。密钥再次向左环移2 5 位产生 另外8 个子密钥，如此进行直到算法结束。 i d e a 总共进行8 轮迭代操作，每轮需要6 个子密钥，另外还需要4 个额外 子密钥，所以总共需要5 2 个子密钥，这个5 2 个子密钥都是从1 2 8 位密钥中扩展 出来的。 首先把输入的k e y 分成8 个1 6 位的子密钥，1 6 号子密钥供第一轮加密 使用，7 、8 号子密钥供第二轮使用，然后把这个1 2 8 位密钥循环左移2 5 位，这 样k e y = k 2 6 k 2 7 k 2 8 k 2 4 k 2 5 。 把新生成的k e y 在分成8 个1 6 位的子密钥，1 - 4 号子密钥供第二轮加密使 用( 前面已经提供了两个) ，5 8 号子密钥供第三轮加密使用。到此我们已经得 到了1 6 个子密钥，如此继续，当循环左移了5 次之后已经生成了4 8 个子密钥， 还有四个额外的子密钥需要生成，再次把k e y 循环左移2 5 位，选取划分出来的 8 个1 6 位子密钥的前4 个作为那4 个额外的加密密钥。这样供加密使用的5 2 个子密钥生成完毕。 输入的6 4 位数据分组被分成4 个1 6 位子分组：x l ，x 2 ，x 3 和x 4 。这4 个 子分组成为算法的第一轮的输入，总共有8 轮。在每一轮中，这4 个子分组相 互相异或，相加，相乘，且与6 个1 6 位子密钥相异或，相加，相乘。在轮与轮 间，第二和第三个子分组交换。最后在输出变换中4 个子分组与4 个子密钥进 行运算。 ( 2 ) i d e a 算法的加密过程 在每一轮中，执行的顺序如下： a ) x l 和第一个子密钥相乘； b ) x 2 和第二个子密钥相加； c ) x 3 和第三个子密钥相加； d ) x 4 和第四个子密钥相乘； e ) 将第a ) 步和第c ) 步的结果相异或； f ) 将第b ) 步和第d ) 步的结果相异或； g ) 将第e ) 步的结果与第五个子密钥相乘； b 第2 章数据加解崭体制综述 h ) 将第( f ) 步和第g ) 步的结果相加； i ) 将第h ) 步的结果与第六个子密钥相乘； j ) 将第g ) 步和第i ) 步的结果相加； k ) 将第a ) 步和第i ) 步的结果相异或； m ) 将第c ) 步和第i ) 步的结果相异或； n ) 将第b ) 步和第j ) 步的结果相异或； o ) 将第d ) 步和第j ) 步的结果相异或。 每一轮的输出是第k ) 、m ) 、n ) 和o ) 步的结果形成的4 个子分组，将中间 两个分组交换( 最后一轮除外) 后，即为下一轮的输入。经过8 轮运算之后，有 一个最终的输出变换： a ) x 1 和第一个子密钥相乘 b ) x 2 和第二个子密钥相加 c ) x 3 和第三个子密钥相加。 d ) x 4 和第四个子密钥相乘。 最后，这4 个子分组重新连接到一起产生密文。 3 ) a e s a e s 是美国国家标准技术研究所n i s t 旨在取代d e s 的新一代的加密标准。 n i s t 对a e s 候选算法的基本要求是：对称分组密码体制，密钥长度支持1 2 8 、 1 9 2 、2 5 6 位，明文分组长度1 2 8 位，算法应易于各种硬件和软件实现。1 9 9 8 年 n i s t 开始a e s 第一轮征集、分析、测试，共产生了1 5 个候选算法。1 9 9 9 年3 月 完成了第二轮a e s 的分析、测试。1 9 9 9 年8 月n i s t 公布了五种算法( m a r s ， r c 6 ，r i j n d a e l ，s e r p e n t ，t w o f i s h ) 成为候选算法。最后，r i j n d a e l 这个由 比利时人设计的算法与其它候选算法在成为高级加密标准( a e s ) 的竞争中取得 成功，于2 0 0 0 年1 0 月被n i s t 宣布成为取代d e s 的新一代的数据加密标准即 a e s 。尽管人们对a e s 还有不同的看法，但总体来说，r i j n d a e l 作为新一代的 数据加密标准汇聚了强安全性、高性能、高效率、易用和灵活等优点。a e s 设 计有三个密钥长度：1 2 8 ，1 9 2 ，2 5 6 比特，相对而言，a e s 的1 2 8 比特密钥比 d e s 的5 6 比特密钥强1 0 2 1 倍。 对a e s 算法的详细描述请参见3 1 。 2 1 2 对称密码算法的特点 对称密码体制效率高，但通信双方需要事先交换密钥。在告诉接收方密钥 的过程中，还需要防止任何第三方发现或偷听密钥，此过程即密钥发布。此外 对称密钥加密体制中密钥的保存也极不方便，假设网上有n 个用户，为完成两 9 成都理t 人学颂i ：学位论文 两通信，需要n ( n - 1 ) 2 个密钥，每个用户需要记录n 1 个密钥，数量如此之大， 只能一记录在本子上或存储在计算机中，这本身又是极不安全的。 由此，对称密码体制的特点是； 1 ) 加密算法和解密算法互逆； 2 ) 加密密钥和解密密钥相同，效率较高，可以满足大量信息的加密需求； 3 ) 通信双方需要事先交换密钥，密钥容易泄漏而不能确保安全性； 4 ) 无法实现传输信息的不可否认性； 5 ) 密钥存储、使用和管理困难。 2 1 3 典型的传统密码算法d e s 和a e s 分析及其比较 d e s 和a e s 均为对称密码的分组密码，但由于数学原理不同，因此他们有 着各自的特点。 1 ) 在算法实现方面：d e s 软件实现困难，而硬件实现却非常容易，不耗资 源( 包括时间和空间) ；而a e s 在硬件实现和软件实现上，虽然占用空间资源多， 但运算速度快。 2 ) 在安全性方面：d e s 早已被破解，而a e s 在将来的一段时间内仍然安全。 3 ) 在密钥的长度方面：d e s 的密钥长度固定为6 4 ，而a e s 的密钥长度可变， 可为1 2 8 、1 9 2 、2 5 6 位。 2 2 公钥密码体制 2 2 1 公钥密码概述 由于对称密码体制需要事先传送加密密钥而使得保密性受到威胁，再加上 对称密码本身的不足无法实现不可否认的信息传输，因此，在计算机网络上传 输加密数据就迫切需要一种新的加密技术的出现。1 9 7 6 年，d i f f i e 和h e l l m a n 的文章“密码学的新方向”。掀起了公钥密码研究的序幕。 从数论的角度说，任何公钥系统的基础都建立在一个n p 问题之上，即对于 特定的问题我们没有办法找到一个多项式时间的算法求解该问题，一般求解此 类问题的算法都是指数时间或者亚指数时间，现有的计算机体系结构不适于求 解此类问题。正因为有了这个理论依据，才可以放心地将公开密钥发送给任何 人，而不用担心它利用公钥反推出私钥。 目前比较典型公钥密码体系主要是： 1 ) 基于整数因式分解的公钥密码技术，如r s a ； 1 0 第2 章数据加解街体制综述 2 ) 基于离散对数的公钥密码技术，如d s a ，d h ，e i g a m a l ； 3 ) 基于椭圆曲线的公钥密码技术，如e c c 。 公钥密码体系使用的加密技术的安全强度都是基于一些数学难题，这些难 题被专家们认为在短期内不可能得到解决。一些问题( 如因子分解问题) 至今己 有数千年的历史了。公钥密码采用公钥、私钥分别加、解密的方法，使加、解 密密钥分离，从而保证保密性。能够很好地解决对称密码所存在的问题。从技 术上打破了对称密码体制的限制。 2 2 2 基于大整数因式分解的的公钥密码技术 r s a 算法是r i v e s t ，s h a m i 和a d l e m a n 于1 9 7 7 年提出的一个比较完善的公 钥密码算法。r s a 的基础是数论中的欧拉定理，其安全性基于分解大整数的困 难性，即到目前为止尚无法找到一个有效的算法来分解两个大素数之积。 一般地讲，可将r s a 密码算法分成三个主要函数，即大素数的产生、密钥 对的产生和r s a 消息处理。 1 ) 大素数的产生 即产生两个大素数p 、q ，大素数的产生是r s a 算法体制中一个重要算法， 是基础。 2 ) 密钥对的产生 就是加密指数e 和解密指数d 的产生，二者满足e d ；l m o d ( n ) 密钥对的 产生是r s a 的关键，只有合适的密钥对，才能保证r s a 的安全。 3 ) 消息处理 消息处理是r s a 的核心，包括加密、解密、签名和验证四种，但实质上它 们是相通的，处理过程也类似。这里以对信息n ，的加解密为例，处理过程描 述如下。 将n 划分成若干个数据块m j ，观 n ( 此举是为了保e m j 在解密时的唯一 性) 。加密公式为： c ti 矿( m o d 加； 解密公式为： m | c ? ( m o d ) n 。 2 2 3 基于离散对数的的公钥密码技术 离散对数问题指的是对于给定大整数g ，x 和素数n ，计算y = g 。m o dn 是容 易的，而反过来，已知y 、g 和n ，求x 使之满足等式y = g 。m o dn 是困难的，离 成都理t 人学顾i ：学位论文 散对数问题是一个n p 完全问题。 基于这一技术最著名的算法是美国政府开发的签名算法d s a ，被美国n i s t 作为d s s ( d i g i t a ls i g n a t u r es t a n d a r d ) 。d s a 是基于整数有限域离散对数难题 的，其安全性与r s a 相比差不多。d s a 的一个重要特点是两个素数公开，这样， 当使用别人的p 和q 时，即使不知道私钥，也能确认它们是否是随机产生的， 还是作了手脚，而r s a 算法却作不到。 2 24 基于椭圆曲线的的公钥密码技术 1 9 8 5 年，n e i lk o b l i t z 和v i c t o rm i l l e r 分别提出了椭圆曲线密码系统 ( e e c e l h p t i cc u r v ec r y p t o s y s t e m ) 。椭圆曲线密码系统安全强度不但依赖于在 椭圆曲线上离散对数的分解难度，也依赖于曲线的选择和体制，目前1 6 0 比特 长的椭圆曲线密码体制己经有相当高的安全强度。 椭圆睦线密码体制是一种新的密码算法思想。与传统的密码算法不同的是， 它需要人为构造有限域和定义域中的运算，并将信息通过编码嵌入自构造的有 限域中。椭圆曲线密码体制的安全性由椭圆曲线上的离散对数问题( e c d l p e l l i p t i cc u r v ed i s c r e t el o g a r i t h mp r o b l e m ) 确保，这是一个n p 一完全问题， 解决这个问题的时间复杂度为指数级，远远超过了其他公钥密码算法的复杂程 度。 从上述分析可以归纳出公钥密码体制的特点为： 1 ) 通信双方不需要事先交换密钥，保密性好； 2 ) 可以实现数字签名，保证传输信息的不可否认性； 3 ) 算法基于数学难题，加密效率非常低； 4 ) 不适合大量信息的加密需求； 5 ) 密钥管理、信任关系确立需要权威机构支持。 2 2 5 几种典型的公钥密码技术及其特点b e 较 通过上述分析我们可以发现公钥密码体制的特点有着以下的共同点： 1 ) 通信双方不需要事先交换密钥，保密性好；2 ) 可以实现数字签名，保证传输 信息的不可否认性；3 ) 算法基于数学难题，加密效率非常低，4 ) 不适合大 量信息的加密需求：5 ) 密钥管理、信任关系确立需要权威的k d c 支持。但他 们由于采用的数学原理不同又有着各自的优点，表2 一l 比较了e c c ，r s a ，d s a 在等价安全强度下所需的密钥尺寸，假定已知解整数分解问题，离散对数问题 和椭圆曲线离散对数问题的最好算法，考虑需要基于某m i p s ( 每秒运算1 0 0 万 1 2 第2 章数据加解擀体综述 条指令) 年破解一个密钥这样的等价强度下的密钥尺寸。 表2 1 ：三种典型的公钥密码体系性能比较 破解密钥时间 r s a 、d s a 密钥长度e c c 密钥长度r s a 、e c c 密钥长度 ( m i p s 年)( b i t )( b i t ) 比 1 0 45 1 21 0 6 5 ：1 1 0 87 6 81 3 2 6 ： 1 1 0 1 11 0 2 41 6 07 ：1 1 0 2 02 0 4 8 2 l o1 0 ：1 1 0 7 82 1 0 0 06 0 03 5 ：l 1 ) 安全性能 加密算法的安全性能一般通过该算法的抗攻击强度来反映。e c c 和其他几 种公钥系统相比，其抗攻击性具有绝对的优势。椭圆曲线的离散对数计算困难 性( e c d l p ) 在计算复杂度上目前是完全指数级，而r s a 是亚指数级的。这体现 e c c 比r s a 的每b i t 安全性能更高。 2 ) 计算量和处理速度 在一定的相同的计算资源条件下，虽然在r s a 中可以通过选取较小的公钥 ( 可以小到3 ) 的方法提高公钥处理速度，即提高加密和签名验证的速度，使其 在加密和签名验证速度上与e c c 有可比性，但在私钥的处理速度上( 解密和签 名) ，e c c 远比r s a ，d s h 快得多。因此e c c 总的速度比r s a ，d s a 要快得多。同 时e c c 系统的密钥生成速度比r s a 快百倍以上。因此在相同条件下，e c c 有更 高的加密性能。 3 ) 存储空间 e c c 的密钥尺寸和系统参数与r s a ，9 s a 相比要小得多