（应用数学专业论文）rsa密码体制及rsa系统短密钥的分析.pdf

ad i s s e r t a t i o ns u b m i t t e dt o 保密- k 2 年 t o n g j iu n i v e r s i t yi nc o n f o r m i t yw i t ht h er e q u i r e m e n t sf o r t h ed e g r e eo fm a s t e ro fs c i e n c e a n a l y s i so fr s ac r y p t o s y s t e m ，p u b l i c k e y a n dp r i v a t ek e y ( s u p p o r t e db yt h en a t u r a ls c i e n c ef o u n d a t i o no fc h i n a , g r a n tn o 1 0 4 7110 4 a n dt h ef o u n d a t i o no fs h a n g h a is c i e n c ec o m m i t t e e ，g r a n tn o 0 3 j c14 0 2 7 ) s c h o o l d e p a r t m e n t ：d e p a r t m e n t o f a p p l i e d m a t h e m a t i c s d i s c i p l i n e ：m a t h e m a t i c s m a j o r ：a p p l i e dm a t h e m a t i c s c a n d i d a t e ：h a n j u es h e n s u p e r v i s o r ：p r o f h o n g w e nl u j a n ，2 0 0 7 学位论文版权使用授权书 本人完全了解同济大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：j 施勉酞 年月日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名： 学位论文作者签名：沈盈啦 年月 e 1年 月日 同济大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名：泌蚀姐 年月日 摘要 摘要 随着i n t e r n e t 的迅速发展，资源共享广泛用于政治、军事、经济、电子商 务以及各个领域，大量在网络中存储和传输的数据需要保护。这些数据在存储 使用和传输过程中，都有可能被中断、截获、篡改和伪造。在传输过程中需要 有网络安全措施来保护数据。 r s a 算法被公认为是目前理论和实际应用中最为成熟和完善的一种公钥密 码体制，可以用来进行数字签名和身分验证。 本文的主要内容如下： 第一章介绍了通信网络信息安全技术。 第二章介绍了密码学的知识，包括数论的基础知识和模运算的概念。并且 谈到了密码学的发展历史和几种历史上有名的密码体制。 第三章介绍了r s a 密码算法体制。r s a 是一种公开密钥算法，其加密密钥和 算法本身都可以公开，解密密钥则归用户私人拥有。r s a 从诞生那天起就因为安 全强度高、使用方便等卓越性能受到关注，并得到广泛应用。 第四章是本文的重点。针对r s a 密码体制在商业，银行，网络信息安全上 的应用，分析了不合理设计r s a 系统的危害性，找到了将公钥，私钥的设计参 数都包含在内的条件，并在该条件下验证了r s a 系统的安全性。 第五章是本文的小结。介绍了对r s a 密码系统的前景和展望。 关键词r s a 系统公钥私钥安全性 a b s t r a c t a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fi n t e m e t ，r e s o u r c e s h a r i n gi sw i d e l yu s e di nt h e f i e l ds u c h 弱p o l i t i c s ，m i l i t a r y , e c o n o m y , e l e c t r o n i cc o n l m e r e ea n de t c ag r e a td e a lo f d a t ai ss a v e da n dt r a n s m i t t e dt h r o u g hi n t e m e t h o w e v e r , t h ed a t am a yb ei n t e r r u p t e d ， i n t e r c e p t e d ，c a p t u r e d ，t a m p e r e dw i t ha n dc o u n t e r f e i t e dd u r i n gt h ep r o c e s so fs a v i n g ， u s i n ga n dt r a n s m i t t i n gi nt h en e t w o r k t h e r e f o r e ，s a f e g u a r d i n gm e a s u r e ss h o u l db e a d o p t e dt op r o t e c td a t ad u r i n gt h et r a n s m i s s i o np r o c e s si nt h en e t w o r k a m o n g t h ev a r i o u sp u b l i ck e yc r y p t o s y s t e m ，r s aa l g o r i t h mi st h eb e s tc h o i c ei n b o t ht h e o r ya n da p p l i c a t i o n ，a n di ti so f t e nu s e di nd 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 n s y s t e m m yp a p e ri n c l u d e sf i v ec h a p t e r sa sb e l o w ： t h ef i r s tc h a p t e ri n t r o d u c e si n f o r m a t i o ns a f e t yt e c h n o l o g yi nc o m m u n i c a t i o n n e t w o r k t h es e c o n dc h a p t e rg i v e st h eb a s i cc o n c e p t so fc r y p t o g r a mi n c l u d i n gn u m b e r t h e o r ya n dm o d u l a ra r i t h m e t i c b e s i d e s ，i tg i v e sa n i n t r o d u c t i o no fh i s t o r yo f c r y p t a n a l y s i sa n ds o m em o s ti m p o r t a n tc r y p t o s y s t e m st h r o u g h o u t i t sh i s t o r y t h et l l i r dc h a p t e rp r e s e n t ss o m ed e t a i l sa b o u tt h er s aa l g o r i t h m ，w h i c hi sa p u b l i c - k e ya l g o r i t h mw i t hap a i ro fk e y sc a l l e dt h ep u b l i c - - k e ya n dt h ep r i v a t e - k e y i n t h i sa l g o r i t h m ，t h ep u b l i c - k e ya n da l g o r i t h mi t s e l fa r ea b l et ob eo p e n ，w i t ht h e p r i v a t e - k e yp o s s e s s e db yt h eu s e rh i m s e l f r o mi t sb i r t h ，r s ah a sa l w a y sb e i n g a p p l i e df o ri t se x c e l l e n tp e r f o r m a n c eo fh i g hs e c u r i t ya n dc o n v e n i e n tu s a g e a n ds oo n n o w a d a y sr s a i si n v o l v e di n t ol o t so fc r y p t o s y s t e m s t h ef o u r t hc h a p t e ri st h em a i np a r to ft h i st h e s i s i ta i m e da tt h ea p p l i c a t i o no ft h e r s ac r y p t o s y s t e mo nt h ef i e l do fb u s i n e s s ，b a n k ，a n di n t e r n e ta n di n f o r m a t i o n s a f e t y i ta n a l y z e dt h ed a n g e ro fi m p r o p e rd e s i g n a t i o no ft h er s ac r y p t o s y s t e m t h e c o n d i t i o ni n c l u d i n gp u b l i ck e ya n dp r i v a t ek e yh a sb e e nf o u n d t h es a f e t yo ft h er s a c r y p t o s y s t e mo nt h i sc o n d i t i o n h a sb e e na n a l y z e d t h el a s tc h a p t e ri sac o n c l u s i o no ft h ew h o l et h e s i s i tg i v e sf o r e g r o u n da n d p r o s p e c to f r s a k e yw o r d s ：t h er s ac r y p t o s y s t e m ，p u b l i ck e y ，p r i v a t ek e y ，s e c u r i t y i i 目录 目录 第一章通信网络信息安全技术概述1 1 1 计算机网络体系结构层次的安全性分析2 1 1 1 物理层的安全性2 1 1 2 数据链路层的安全性2 1 1 3 网络层的安全性3 1 1 4 传输层的安全性4 1 1 5 应用层的安全性。5 1 2 计算机网络系统面临的威胁5 1 。3 网络中的安全策略：7 1 4 网络安全中的关键技术9 第二章密码体制概述17 2 1 数论的基础知识1 7 2 1 1 因子的概念1 7 2 1 2 素数与合数1 8 2 1 3 公约数和最大公约数1 9 2 1 4 互质数1 9 2 1 5 模算术运算1 9 2 1 6 数域。2 1 2 1 7 多项式时间的复杂度2 l 2 2 密码学体制概述2 2 2 2 1 密码学中的相关概念2 2 2 2 2 对称算法体制和非对称算法体制2 3 2 3 信息保密技术及集中密码体制的介绍2 4 2 3 1 保密学基础2 5 i i i 目录 2 3 2 古典密码2 6 2 3 3 序列密码2 6 2 3 4 分组密码2 7 2 3 5 公钥密码2 9 2 3 6 流密码3 l 第三章r s a 公钥密码体制3 2 3 1r s a 公钥密码系统的数学基础3 3 3 1 1 陷门单向函数3 3 3 1 2 大素数相乘3 4 3 1 3 同余方程和中国剩余定理3 4 3 1 4 欧几里德算法3 5 3 1 5w is o n 定理3 7 3 1 6 欧拉函数3 9 3 1 7 平方剩余和j a c o bi 符号。4 0 3 2r s a 公钥系统4 2 3 2 1r s a 加密算法4 2 3 2 2r s a 安全性讨论4 3 3 3 大素数的产生4 4 3 4 因数分解4 6 3 4 1f e r m a t 因数分解法4 6 3 4 2 连分数因数分解法4 7 3 4 3 圆锥曲线分解整数算法4 7 3 4 4p - 1 方法分解整数算法一4 8 3 5 对r s a 体制中小指数的攻击4 8 第四章r s a 体制中小指数的攻击5 0 4 1 在d 0 且d i 口则d h 。 如果d i 口，则我们也可以说c 是d 的倍数。 如果d i 口并且d 0 ，则我们说d 是口的约数。一个整数口的约数的最小位1 ， 最大为i 口| 。例如，2 4 的约数有1 ，2 ，3 ，4 ，6 ，8 ，1 2 和2 4 。 每个整数口都可以被平凡约数1 和口整除。口的非平凡约数也称为口的因子。 例如：2 0 的因子有2 ，4 ，5 和1 0 。 1 7 第二章密码体制概述 2 1 2 素数与合数 对于某个整数p 1 ，并且因子仅为1 和p ，则我们称p 为素数( 或质数) 。 素数具有许多特殊性质，在数论中举足轻重。 不是素数的整数口 1 称为合数。类似地，整数0 和所有负整数既不是素数 也不是合数。 亚里士多德和欧拉已经用反证法非常漂亮地证明了“素数有无穷多个”。 若不计素数的排列顺序，任何大于1 的整数a 都能被因式分解为如下的唯一 形式，我们称为标准分解式： a = 计p ；2 p r 其中p f 为自然数中的的第i 个素数，p 。 p ： p ，且e ，为非负整数( 注 意e ；可以为o ) 。 常用的素数表通常只有几千个素数，这显然无法满足密码学的要求，因为密 码体制往往建立在极大的素数的基础上。所以我们要为特定的密码体制临时计算 符合要求的素数。这就牵涉到素性检测的问题。 判断一个整数是不是素数的过程叫做素性检测。目前还没有一个简单有效的 方法来确定一个大数是否是素数。理论上常用的方法有： ( 1 ) w i l s o n 定理：若( 刀一1 ) ! = 一l ( m o d n ) ，则n 为素数； ( 2 ) 穷举检测：若i 不是整数，且n 不能被任何小于i 的正整数整除， 则n 为素数； 但是这些理论上的方法在n 很大时，计算量太大，部适合密码学中使用。现 在常用素性检测的方法时数学家s o l o v a y 和s t r a s s e n 提出的概率算法。即在某个 区间上能经受得住某个概率检测的整数，就认为它是素数。因子分解问题是n p 困难问题。如果n 是2 0 0 位十进制数，那么对n 进行素数的因式完全分解大概要 花费几十亿年。所以，密码体制都是建立在大数的因式分解的基础上的【9 】【1 2 1 。 第二章密码体制概述 2 1 3 公约数和最大公约数 如果d 是a 的约数并且也是b 的约数，则d 是a 和b 的公约数。注意，1 是任 意两个整数的公约数。 两个不同时为0 的整数a 和b 的最大公约数表示成g e d ( a ，b ) 。如果口和b 不 同时为0 ，则g e d ( a ，b ) 是一个在1 与r a i n ( a i ，帅之间的整数。我们定义g e d ( 0 ，0 ) = 0 。 下面性质就是g e d 函数的基本性质： g c d ( a ，b ) = g e d ( b ，口) g e d ( a ，6 ) = g e d ( 一a ，b ) g c d ( a ，b ) = g e d ( 1 a i ，b 1 ) g c d ( a ，o ) = l a i g e d ( a ，勋) = l a l k z 如果a 和b 是不都为0 的任意整数，则g e d ( a ，b ) 是a 和b 的线形组合集合 沁+ b y ：x ，y z 中的最d , i e 元素。 对任意整数口和b ，如果d i 口并且d 1 6 ，则d l g c d ( a ，6 ) 。 对所有整数a 和b 以及任意非负整数n ，g o d ( a n ，b n ) = n g c d ( a ，b ) 。 对所有正整数口和b 以及正整数1 1 ，如果n a b 并且g o d ( 口，1 ) = 1 ，则n b 。 2 1 4 互质数 如果两个整数a 和b 仅有公因数1 ，即如果g c d ( a ，6 ) = l ，则a 和b 称为互质数。， 对任意整数a ，b 和p ，如果g c d ( a ，p ) = 1 且g c d ( b ，p ) = 1 ，则g e d ( a b ，p ) = 1 。 这说明如果两个整数中每一个数都与一个整数p 互为质数，则他们的积与p 互为 质数。 如果两个正整数都分别表示为素数的乘积，则很容易确定它们的最大公约 数。例如：3 0 0 = 2 2x3x5 ：1 8 = 2 3 2 ；g o d ( 1 8 ，3 0 0 ) = 2 x3 5 0 = 6 ； 确定一个大数的素数因子是不容易的，实践中通常采用e u c l i d e a n 和扩展的 e u c l i d e a n 算法来寻找最大公约数和各自的乘法逆元。 对于整数，刀：，如果对任何f 都有g e d ( n ，刀，) = 1 ，则说整数 ，l l ，刀2 ，l 两两互质。 2 1 5 模算术运算 已知一个整数n ，所有整数都可以划分为是1 1 的倍数的整数与不是n 的倍数 的整数。对于不是n 的倍数的那些整数，我们又可以根据它们除以r l 所得的余数 来进行分类，数论的的大部分理论都是基于上述分划的。 1 9 第二章密码体制概述 对任意整数a 和任意正整数n ，存在唯一的整数g 和，满足0 ，n ，并且 口= q n + r ，值g = q n + r ，值可= 阮j 称为除法的商，其中【工 表示小于等于x 的 最大整数。值，= a r o o d n 称为除法的余数，因此，对于任一整数，可表示为： a = a n 】n + ( a m o d n ) ： 或者 篱 a m o d n = a - a n n 如果( a m o d n ) = ( b m o d n ) ，则称整数口和b 模n 同余，记为a 兰b m o d n 。 模运算具有如下性质： 1 ， 若n l a b ，则a 暑b m o d n ； 2 ， ( a m o d n ) = ( b m o d n ) 等价于a 暑b m o d n ； 3 ，a 宣b m o d n 等价于b 兰a m o d n ； 4 ，若a 三b m o d n 且b 三c m o d n ，则口三c m o d n ； 从模运算的基本概念我们可以看出，模n 运算将所有整数映射到整数集合 o ，1 ，g 一1 ) ) ，那么，在这个集合内进行的算术运算就是所谓的模运算。 模运算类似于普通算术，它也满足交换率、结合率和分配率： 1 、 ( 口m o d n ) + ( b m o d n ) m o d n = ( 口+ b ) m o d n ； 2 、 ( a m o d n ) 一( b m o d n ) m o d n = ( a b ) m o d n ； 3 、 ( 口m o d n ) ( b m o d n ) m o d n = ( 口b ) m o d n ； 指数运算可看作是多次重复的乘法运算。 倒妻陷1 狮子蝴以m o d l 3 ，可按如下方法进行： 11 4 三4 2 暑3 m o d l 3 所缺说l 张犄每 难模2 l r 如闻结果与整个运算求模再化简模n 结果是一样的。 模运算的主要性质如表2 1 所示。 表2 1 模运算的主要性质 性质表达式 ( w + x ) m o d n = ( x + w ) m o d n 交换率 ( w xx ) m o d n = ( x w ) m o d n ( ( w + x ) + y ) m o d n = ( w + ( 石+ y ) ) m o d n 结合率 ( ( w x ) y ) m o d n = ( w ( x y ) ) m o d n 分配率 ( w ( x + y ) ) m o d n = ( ( w x x ) + ( w y ) ) m o d n ( 0 + w ) r o o d n = w r o o d n 恒等式 ( 1 w ) m o d n = w m o d n 第二章密码体制概述 2 1 6 数域 定义( 数域)设k 是某些复数所组成的集合。如果k 中至少包含两个不 同的复数，且k 对复数的加、减、乘、除四则运算是封闭的，即对k 内任意两 个数口、b ( an - - t - b ) ，必有口6 k ，a b k ，且当b o n ，al b k ， 则称k 为一个数域。 例典型的数域举例：复数域c ；实数域r ；有理数域q ；g a u s s 数域：q ( i ) = 口+ b ii 口，d q ) ，其中i = 。 2 1 7 多项式时间的复杂度 如果一个判定性问题的复杂度是该问题的一个实例的规模n 的多项式函数， 则我们说这种可以在多项式时间内解决的判定性问题属于p 类问题。p 类问题就 是所有复杂度为多项式时间的问题的集合。然而有些问题很难找到多项式时间 的算法( 或许根本不存在) ，比如找出无向图中的哈米尔顿回路问题，但是我们 发现如果给了我们该问题的一个答案，我们可以在多项式时间内判断这个答案是 否正确。比如说对于哈米尔顿回路问题，给一个任意的回路，我们很容易判断他 是否是哈米尔顿回路( 只要看是不是所有的顶点都在回路中就可以了) 。这种可 以在多项式时间内验证一个解是否正确的问题称为n p 问题。显然，所有的p 类 问题都是属于n p 问题的，但是现在的问题是，p 是否等于n p 这个问题至今还 未解决。 现在还不知道是否有p = n p 或者p o n p ，但是后来人们发现还有一系列的 特殊n p 问题，这类问题的特殊性质使得很多人相信p o n p ，只不过现在还无法 证明。这类特殊的n p 问题就是n p 完全问题( n p c 问题，c 代表c o m p l e t e ) 。 n p c 问题存在着一个令人惊讶的性质，即如果一个n p c 问题存在多项式时间的 算法，则所有的n p 问题都可以在多项式时间内求解，即p = n p 成立! ! 这是因 为，每一个n p c 问题可以在多项式时间内转化成任何一个n p 问题。比如前面 说的哈米尔顿回路问题就是一个n p c 问题。n p c 问题的历史并不久，c o o k 在1 9 7 1 年找到了第一个n p c 问题，此后人们又陆续发现很多n p c 问题，现在可能已经 有3 0 0 0 多个了。所以，我们一般认为n p c 问题是难解的问题，因为他不太可能 存在一个多项式时间的算法( 如果存在则所有的n p 问题都存在多项式时间算法， 这太不可思议了，但是也不是不可能) 。 2 1 第二章密码体制概述 2 2 密码学体制概述 密码学的历史极为久远，其起源可以追溯到远古时代，人类有记载的通信密 码始于公元前4 0 0 年。虽然密码是一门古老的技术，但自密码诞生直自第二次世 界大战结束，对于公众而言，密码始终处于一种未知的黑暗当中，常常与军事、 机要、间谍等工作联系在一起，让人再感到神秘之余，又有几分畏惧。 信息技术的发展迅速改变了这一切。随着计算机和通信技术的迅猛发展，大 量的敏感信息常常通过公共通信设施或计算机网络进行交换，特别是i n t e m e t 的 广泛应用、电子商务和电子政务的迅速发展，越来越多的个人信息需要严格保密， 如：银行帐号、个人隐私等。正是这种对信息的秘密性与真实性的需求，密码学 才逐渐掀去神秘的面纱，走进公众的日常生活当中【4 】【1 1 】。 2 2 1 密码学中的相关概念 在介绍各种密码体制之前，首先引入密码学上的相关概念。 明文：也就是消息。明文用m 或者p 表示，它可能是位序列、文本文件、 位图、数字化的语音序列或数字化的视频图像等。明文可以被传送或者存储，无 论哪种情况，r n 均指待加密信息。 密文：就是加密后的消息。密文用c 表示，有时和m 一样大，有时稍大( 除 非通过压缩和加密的结合，否则仅由加密，c 通常部可能比m 小) 。 密码算法：是用于加密和解密的数学函数，通常有两个相关函数，一为加密， 一为解密。 加密：用某种方法伪装信息以隐藏它的内容的过程。加密函数e ( ) 作用于明 文m 得到密文c ，用数学公式表示为 e ( ，z ) = c 解密：把密文转变为明文的过程。解密函数d ( ) 作用于密文c 产生明文m ， 用数学公式表示为 d ( c ) = m 密钥：包括加密密钥七，和解密密钥k d ，各是一组数据串，用k 统一表示。 加密密钥k ，和解密密钥k 。可以相同，也可以不同( 根据具体的密码体制决定) 。 加密密钥k ，确定某一加密算法e ( ) ，对明文加密，得到密文c ；解密时，必须通 过由解密密钥k d 确定的解密算法d ( ) ，结合解密密钥k d 才可以解密密文c ，得 到明文m 。有了密钥k 的概念，一个密码体制的安全就由基于算法的安全性转为 基于密钥的安全性，意味着算法可以公开这是现代密码体制的基本要求。 一个密码系统由算法以及所有可能的明文m 、密文c 和密钥k 组成。 第二章密码体制概述 2 2 2 对称算法体制和非对称算法体制 接下来介绍两种基于密钥的算法体制对称算法体制和非对称算法体制。 对称算法体制 对称算法的“对称，指的是加密密钥能够从解密密钥中推算出来，反之亦 然。故而加密密钥和解密密钥可视为“相同”。用k 表示。对称算法的安全性依 赖于密钥k ，泄漏密钥就意味着任何人都可以对信息进行加解密。 对称算法的加密和解密可以表示为 e t ( 历) = c d i ( c ) = m 对称算法又可以分为两类，一次只对明文的单个位( 有时是字节) 运算的称 为序列密码，一次对明文的一组位进行运算的则称为分组密码。 非对称算法体制 非对称算法，习惯称为公开密钥算法。这种密码系统的加密密钥k 。和解密密 钥k d 不同，并且解密密钥k 不能从加密密钥也中推算出来，之所以叫做公开密 钥算法，是由于加密密钥也可以公开，即任何人都可以用加密密钥t 加密信息， 但只有拥有相应的解密密钥k 。的人才可以解密信息。在公开密钥密码系统中， 加密密钥k 。叫做公开密钥，解密密钥k d 叫做私人密钥。 公开密钥密码系统不但可以用作加解密，同时还可以用于签名、认证。设公 开密钥密码系统中两用户a 和b ，由a 的公钥确定的加密算法为e 。( - ) ，私钥确 定的解密算法是d 一( ) ；同理定义( ) 和d 占( ) 。a 、b 的公钥和加密算法都是 公开的。 加解密过程如下所述：如果a 向b 传送信息m ，a 首先查得b 的公钥，得 到e 口( ) ，然后加密信息m b ( ) = c 得到密文c 。收端，只有用户b 用自己的私钥才可以解密c d 日( ) = m 得到明文m 。这样，一个加解密过程结束。 若a 向b 传送信息m ，b 想确认收到的信息是否为a 发送的，则a 必须附 上自己的签名。签名认证过程如下：首先，a 用自己的私钥对信息1 1 1 加密，得 到密文c ，并附上自己签名。然后用b 的公钥对这两部分加密，得到密文c 。 e ( m ) = c l 岛( ( ”，c 。) ) = c 第二章密码体制概述 将c 传送给b 。收端，b 用自己的私钥对密文c 解密，得到a 的签名及a 的私钥加密后的密文c 。最后，用a 的公钥解密c l ，即得到明文1 1 1 ，同时也可 以证明该消息是a 发出的， d 8 ( c ) = ( ”，c i ) e 爿( c i ) = m 公开密码系统的提出，是基于对称算法的不足之处。具体而言，对称算法有 三个问题难以解决 1 信息的发送方不能向对方或第三方证明，他的确发送了某一信息。 2 密钥必须通过某一信道进行交换或协商，而此信道的安全性要比正常传送 信息的信道的安全性要求高。这对信道提出了高要求。 3 大量用户需要安全信道时，双向的信道的数量以及密钥的数量会随着用户 的增多而非常之大。比如一个n 个用户的网络，每个用户想与其他用户安全的交 换信息，就需要n ( n 一1 ) 个对称密钥。当玎= 1 0 0 0 时，这个数值是9 9 9 0 0 0 。这给 密钥管理带来很大麻烦。 公开密钥密码系统把对称算法的三个不足之处都解决了。但同时又出现了新 的问题，就是公开密钥密码系统通常都是以数学上的某个难题为基础建立的，一 般都需要巨大的运算量。因此，实际工程应用中，往往将对称算法与公开密钥算 法结合在一起，互为补充，扬长避短，构造成混户密码系统。 比较典型的公开密钥密码系统由r s a 系统、背包系统、m c e l i e c e 系统、二 次剩余系统等等，其中r s a 是迄今为止理论上最成功、应用最广泛的一个。r s a 是r o n a l d l r i v e s t 、a d is h a m i r 和l e o n a r dm a d l e m a n 于19 7 8 年共同提出的。它 的安全性基础是数论和计算复杂性理论中的论断：在计算上求两个大素数的乘积 是容易的，但要从大素数的积分解出它的素因子是困难的。 2 3 信息保密技术及集中密码体制的介绍 信息保密是信息安全技术的核心技术。保密系统的目的是防止敌手破译系统 中的机密信息。在用密码技术保护的现代信息系统的安全性主要取决于对密钥的 保护，而不是对算法和硬件本身的保护，其密码算法的安全性完全寓于密钥之中。 本节注意介绍信息保密技术的基础知识以及古典密码、单钥分组密码、公钥 密码和流密码等概念和思想。 第二章密码体制概述 2 3 1 保密学基础 1 9 4 9 年s h a n n o n 发表的保密系统的通信理论，用信息论的观点对信 息保密问题作了全面的阐述。他以概率统计的观点对消息源、密钥源、接收和截 获的消息进行数学描述和分析，用不确定性和唯一解距离度量密码体制的保密 性，阐明了密码系统、完善保密性、纯密码、理论保密性和实际保密性等重要概 念，将密码学的研究纳入了科学的轨道。s h a n n o n 提出了保密系统的简化数学模 型如下图2 1 所示： 圈 图2 1 保密系统的简化数学模型 根据加密密钥和解密密钥是否相同或木质上等同，即从其中一个容易推出另 一个，可将现有的加密体制分为两种：一种是单钥( 私钥或对称) 加密体制，这 种体制的加密密钥和解密密钥或者相同或者本质上等同，即从其中一个容易推出 另一个，其典型代表是美国的数据加密标准( d e s ) ：另一种是双钥( 公钥或 非对称) 加密体制，这种体制的加密密钥和解密密钥不相同，并且从其中一个很 难推出另一个，这样加密密钥可以公开，解密密钥可由用户自己秘密保存，其典 型代表是r s a 体制【2 2 j 。 根据对明文的加密方式的不同，又将单钥加密体制分为两类：一类是流密码， 在这类体制中，明文按字符逐位地被加密；另一类是分组密码，在这类体制中， 先将明文分组( 每组含有多个字符) ，然后逐组地进行加密。公钥密码体制大都 是分组密码，一般不再按明文的加密方式对其进行分类。我们通常所说的分组密 码特指私钥分组密码。 下面我们简介下密码分析。 密码学包括密码编码学和密码分析学。密码分析学是在不知道密钥的情况 下，恢复明文的科学。成功的密码分析能分析出消息的明文或密钥。荷兰人 a k e r c k h o f f s 最早在1 9 世纪阐明了密码分析的一个基本假定，即假定密码分析 者已掌握密码算法及其实现的全部详细资料，密码系统的安全性完全寓于密钥之 第二章密码体制概述 中。也就是说，密码分析者除了不知道所使用的密钥外，了解整个密码系统。在 实际的密码分析中并不总是有这些详细信息的，不过应该如此假设。 常用的密码分析攻击有五类，当然，每一类都假设密码分析者知道所使用的 加密算法的全部知识： ( 1 ) 唯密文攻击：密码分析者拥有一个或更多的用同一密钥加密的密文， 通过对这些截获的密文进行分析得出明文或密钥。 ( 2 ) 已知明文攻击：除待解的密文之外，密码分析者拥有一些明文和用同 一密钥加密这些明文所对应的密文。 ( 3 ) 选择明文攻击：密码分析者可得到所需要的任何明文所对应的密文， 这些密文是与待解的密文用同一密钥加密得来的。 ( 4 ) 自适应选择明文攻击：这是选择明文攻击的特殊情况。密码分析者不 仅能选择被加密的明文，而且还能基于以前加密的结果修正这个选择。 ( 5 ) 选择密文攻击：密码分析者能选择不同的被加密的密文，并可得到对 应的解密的明文。 2 3 2 古典密码 古典密码是密码学的渊源，这些密码大都比较简单，可用手工或机械操作即 能实现加解密。研究这些密码的原理，对理解、构造和分析现代密码都是十分有 益的。 在计算机出现之前，密码学由基于字符的密码算法构成。现在事情变得复杂 多了，但原理还是没变。重要的变化是算法对位而不是对字符进行变换，实质上 这只是字母表长度的改变。 古典密码的基本运算有两种：代替( s u b s t i t u t i o n ) 和换位( t r a n s p o s i t i o n ) 。 代替是指每一个或一组字符被另一个或一组字符所取代；换位是不改变明文字 符，而按一定规则重新安排字符的次序。实际的密码算法是执行一系列这两种基 本运算的不同组合，即得到所谓乘积密码。比较有名的古典密码包括凯撒 ( c a e s a r ) 密码、维吉利亚( v i g e n e r e ) 密码、维尔南( v e m a m ) 密码、普莱费 厄( p l a y f a i r ) 密码和希尔( h i l l ) 密码等【l 引。 2 3 3 序列密码 序列密码的思想起源于二十世纪二十年代，它是一种私密钥密码系统，加密 过程可以简单描述为，先把报文、语音、图像和数据等原始信息转换为明文m ， 然后将明文m 与密钥序列k 逐位进行加密，得到密文c ，发送给接受者。解密时， 第二章密码体制概述 接收者使用相同的密钥序列k 队密文c 逐位解密，就可以恢复出明文序列1 1 1 。由 此可见，序列密码中的密钥k 与明文m 、密文c 等长。 序列密码又叫做流密码，因为它是实时地对信息流进行加密。通常，加解密 用的密码序列是伪随机序列。序列密码系统的加密解密过程如图2 2 所示。 明文序列m l 秘密住道 图2 2 序列密码系统加密和解密过程 列m l m 2 序列密码的安全性主要依赖于密钥序列z ( k ) ，一般z ( 七) 是由密钥k 通过确 定性算法产生的伪随机序列，因而设计序列密码系统的关键是设计密钥序列 z ( 七) 。目前，大多数密钥序列的产生基于移位寄存器，如g e f f e 发生器、钟控序 列等。 序列密码不存在数据扩展和错误传播，实时性好，加、解密实现也比较容易， 因而是一种应用广泛的密码系统。但由于密码序列是伪随机的，因此安全性有一 定限度。 2 3 4 分组密码 所谓分组密码，就是把整个明文序列分成若干个长为n 的数据组 m = ( m 。m 。m 剃) ，各组分别经过由密钥k 确定的加密算法也( ) 的处理，得到 长为n 的密文c = ( c l c ) 。一般来讲，分组密码中每组密文c 的每一位 都与对应明文组m 的所有位相关。 现代分组密码的研究始于二十世纪七十年代，至今已经近三十年的历史，期 间取得了丰硕的研究成果。d e s ( d a t ae n c r y p t i o ns t a n d a r d ，数据加密标准) 是早 期研究的重点，围绕它推出许多类似的算法，如f e a l ，g o s t 等，进入九十年代， 第二章密码体制概述 差分密码分析( d i f f e r e n t i a lc r y p y a n a l y s i s ) 和线性密码分析( l i n e a rc r y p t a n a l y s i s ) 的提出，迫使人们不得不研究新的密码结构，i d e a 、s q u a r e 、s h a r k 等应运而生。 1 9 9 7 年，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 ，高级加密标准) 的征集掀起了分 组密码研究的新高潮。经过三年的研究，2 0 0 0 年1 0 月，终于确定r i j i n d a e l 作为： 新一代的数据加密标准。 “ 分组密码的一般结构如图2 3 所示。 图2 3 分组密码结构 分组密码中，解密密钥k d 也可由加密密钥k 。推出，因此统称为密钥k ，密钥 k 的存储、传输等对整个密码体制的安全性至关重要。所以，必须使用可靠的方 法进行密钥管理。 分组密码具有速度快、易于标准化和便于软硬件实现等特点，通常是信息与 网络安全中现数据加密、数字签名、认证及密钥管理的核心体制，在计算机通信 和信息系统安全领域有最广泛的应用。但分组密码的密钥k 长度有限，随着计算 技术的发展和新的攻击方法的涌现，其安全性也越来越值得关注。 分组密码包括d e s 、i d e a 、g o s t 和b l o w f i s h 密码等，下面我们主要介绍 d e s 和i d e a 的设计思想及新一代数据加密标准a e s 。 数据加密标准d e s 数据加密标准d e s ( d a t ae n c r y p t i o ns t a n d a r d ) 是美国1 9 7 7 年公布实施 的第一个公开绝大部分加密原理和算法细节并得到广泛应用的最具有代表性的 分组密码体制，在密码学史上占有特殊的地位。它是一种对二元数据进行加密的 方法，数据分组长度为6 4 位，密文分组长度也是6 4 位，没有数据扩展。其算 法的基本设计思想是： 通过循环或迭代，将简单的基本运算( 例如左移、右移、模2 加法等) 和 变换( 选择函数、置换函数) 构造成数据流的非线性变换( 加密变换或解密变换) 。 d e s