（计算机软件与理论专业论文）动态密钥协商协议的研究与实现.pdf

四川师范大学硕士学位论文 动态密钥协商协议的研究与实现 计算机软件与理论专业 研究生：郭现峰指导教师：袁丁 有效的安全机制是当前开放式网络中数据传输的必要保障，在信息安全领 域里，密钥是合法访问的唯一凭证，因此如 可为群组通信成员产生平等、有效 的组通信密钥，尤其为最为复杂的动态对等组生成有效通信密钥是当今的一个 热点研究问题。 本文对现有的适合群组通信的密钥产生协议进行了分析，并针对适合动态 对等通信组的密钥协商协议进行了较为深入的研究。在综合比较了各个密钥协 商协议的各项性能之后，采用基于树型结构和门限思想的组密钥协商协议 ( 1 t r s ) 作为研究方向。 t t s 协议客户端的计算量较小，适合现有嚼络环境，且采用门限思想，在 成员变动较大的时候，将密钥更新的工作减到了最小。改进的1 t r s 密钥协商协 议，以很小的计算代价使原t t s 协议在密钥证实性、源认证和抗同谋破解上有 了很大改善。 本文在前人成果的基础上做了如下工作： 在快速生成元查找算法的基础上，对有限域勿中窜阶生成元的的问题 进行了讨论，并针对p 、q 为大素数，q l p 一】的情况下，提出了一个高效的查 找有限域勿中g 阶生成元的算法。 将1 _ r s 密钥协商协议进行了改进，改进后的t r s 协议采用高效的单向 h a s h 函数和异或运算，仅以很小的计算代价，使其具有良好的密钥证实性、源 认证和抗同谋破解等安全属性。 四川师范大学硕士学位论文 本文在v c + + 6 0 中实现了改进的口晤密钥协商协议，并详细阐述了 各个功能模块算法和流程，解决了加密软件和高次模余以及s h a m i r 门限结构等 实现中涉及到的一些技术问题。 关键字：密钥协商门限体制动态对等通信 强素数生成元 密钥证实性源认证抗同谋破解密钥产生协议高次模余 婴型堕薹茎兰堡主笔垒堡兰一一 s t u d y a n d d e s i g n o ft h ek e y n e g o t i a t i o n p r o t o c o l m a j o r ：s o f t w a r ea n dt h e r o y o f c o m p u t e r g r a d u a t es t u d e n t ：g u o x i a n f e n gs u p e r v i s o r ：y u a nd i n g a tp r e s e n tt h ee f f e c t i v es e c u r i t ys c h e m ei st h ee s s e n t i a ls a f e g u a r do fd a t a t r a n s m i s s i o ni nt h eo p e nn e t w o r k t h eo n l yc r e d e n c eo fa c c e s si s s e c r e t k e y i n i n f o r m a t i o ns e c u r i t yf i e l d s oh o wt op r o v i d et h ee q u a la n de f f e c t i v eg r o u pk e yf o r c o m m u n i c a t i o nc l i e n t s ，e s p e c i a l l yf o r t h em o s t c o m p l e x d y n a m i cp e e rg r o u p b e c o m e so n eo ft h et o p i cs t u d yi s s u e si nn o w a d a y s 1 1 l i st h e s i sa n a l y z e st h ea v a i l a b l ek e ye s t a b l i s h m e n tp r o t o c o lw h i c hi ss u i t a b l e f o rg r o u pc o m m u n i c a t i o n , a n dm & k e sa d e e p r e s e a r c ho nt h ek e yn e g o t i a t i o n p r o t o c o l s u i t a b l ef o rd y n a m i cp e e rg r o u p a f t e rt h e c o m p r e h e n s i v ec o m p a r i s o no fe v e r y p e r f o r m a n c eo ft h ek e yn e g o t i a t i o np r o t o c o l ，t h ep a p e rd i s c u s s e st h er r s ，b a s e do n t h et r e es t r u c t u r ea n dt h r e s h o l dt h e o r y t h er r s p r o t o c o lh a s t h ea d v a n t a g ei nc o m p u t a t i o ni nc l i e n t s s of i tt oc o m m o n n e t w o r k c o n d i t i o n a d o p t i n g t h et h r e s h o l d t h e o r y ，i t r e d u c e st h ew o r ko f k e y r e g e n e r a t i o nt ot h en l i ：n l l m j nw h e n t h eg r o u pc h a n g e s + t h ei m p r o v e dt r s k e y n e g o t i a t i o np r o t o c o l ，w i t h s m a l lc a l c u l a t i o nc o s t , m a k e s g r e a tp r o g r e s s i n k e y v e r i f i c a t i o n ，d a t as o u r c ea u t h e n t i c a t i o na n dr e s i s ti n n e r sa t t a c k t h ei t l a i nw o r k si nt h i st h e s i si sa sf o t l o w s ： f i r s t , t h et h e s i sd i s c u s s e st h es u b j e c to fqe x p o n e n tp r i m i t i v er o o ti ng f o ) ， w h i c hb a s e do nt h ef a s t e ra l g o r i t h mo f f m d i n g t h e p r i m i t i v er o o t t h e ni f pa n dqa r e l a r g ep r i m e s ，i tp u t sf o r w a r do n ef a s t e ra l g o r i t h mw h i c hc a nf i n dt h eqe x p o n e n t p r i m i t i v e r o o ti no f ( p ) 1 1 1 一 四川师范大学硕士学位论文 s e c o n d t h e p a p e ri m p r o v e s t h ek e y n e g o t i a t i o np r o t o c o lo f r r s t h ei m p r o v e d t t sa g r e e m e n ta d o p t sh i g h e f f i c i e n to n e w a yh a s hf u n c t i o na n dx o ro p e r a t i o n ， m a k i n g i th a ss u c hs a f ea t t r i b u t e sa sk e yv e r i f i c a t i o n ，d a t as o u r c ea u t h e n t i c a t i o na n d r e s i s t si n n e r sa t t a c kj u s ta tt h ec o s to fas l i g h ti n c r e a s ei nc o m p u t a t i o n l o a d s f i n a l l y , t h ep a p e r d i s c u s s e sa n d p r e s e n t s t h e t h o u g h t ，m e t h o d s a n dt h e t e c h n i q u e s o i lh o wt oi m p l e m e n tt h ei m p r o v e d 傩k e y n e g o t i a t i o np r o t o c o lu n d e r v c + + 6 0 a n ds o l v e ss o m e t e c h n i q u ep r o b l e m s w h i c hc a nb ef o u n di ni m p l e m e n to f u s u a le n c r y p t i o ns o f t w a r e ，m o d u l a ro f l a r g ee x p o n e n ta r i t h m e t i ca n d t h ea r c h i t e c t u r e o fs h a m i rt h r e s h o l d k e y w o r e d s ：k e yn e g o t i a t i o n ；t h r e s h o l ds c h e m e ；d y n a m i c p e e r c o m m u n i c a t i o n ： s t r o n gp r i m e ；p r i m i t i v e r o o t ； k e y v e r i f i c a t i o n ；d a t a s o u r c ea u t h e n t i c a t i o n ；r e s i s ti n n e r sa t t a c k ； k e ye s t a b l i s h m e n tp m t o c o h m o d u l a ro f l a r g ee x p o n e n t 璺业堑蔓查堂堕圭兰竺丝苎一 第一章绪论 自从1 9 4 6 年第一台电子数字计算机e n i a c 诞生以来，计算机科学已经成 为当今世界发展最快的一门学科，尤其微型计算机的出现以及计算机网络的飞 速发展，使得计算机及其应用已渗透到社会的各个领域，有力的推动了社会信 息化的发展。 1 1 课题目的和意义 现在，越来越多的企业和政府机关组建了办公网。组建办公网的目的不仅仅 是共享网络资源，而且还可以用办公网来召开网络会议，提高工作效率。与传统 的集会式会议相比，网络会议既可以节约大量时间和金钱，提高生产率，也可以 提高团体协同、并行工作的能力，有其独特的优点。 在计算机网络深入普及的信息时代，信息本身就是时间，就是财富，但信息 的传输通过的是脆弱的公共信道，如何保护信息在开放的互联网中安全的传输和 使用，使之不被窃取、不被篡改或破坏，已经成为当今普遍关注的重大问题。 本文在分析了网络会议的广大用途，及其亟待解决的安全问题之后，对网络 会议中的密钥产生进行了一定的研究，并将适合当今网络现状的t r s 密钥协商协 议进行了一定的改进和实现，使其更加适合目前最为复杂的群组通信方式 动态对等通信。 我们知道，在信息安全体系中，密钥是合法访问的唯一凭证。k e r c k h o f f 密 码安全性分析假设“指出：一个信息安全系统的安全性取决于对密钥本身的保 护，而不是对系统或者通信硬件的安全保护。因此，密钥一旦泄漏，则安全系统 将被破坏，不但合法用户不能访问系统、提取信息，而且系统中的信息将会被非 法用户所窃取，危害到整个系统的安全。由此可见，安全的会议密钥管理方案在 安全通信系统中的地位是十分关键和极其重要的。会议密钥管理为参与会议的成 员生成、分发和更新会议密钥( g r o u pk e y ) 。会议密钥是所有与会成员都知道的密 钥，被用来对会议报文进行加密解密、认证等操作，以满足保密、会议成员认 证、完整性等需求。它不仅影响着系统的安全性，而且还将涉及系统的可靠性、 有效性和经济性等方面。 四川师范大学硕士学位论文 加之，密码学以及加密协议与其它科学最大的不同在于其研究及发展只能是 “本土化，的科学。对其它科学或技术，我们可以从外国引进。然而对密码算法 的使用与研究，除非能百分之百确信它在硬件及软件上没有“陷门”，否则贸然 使用可能会导致不可收拾的后果。1 。另外由于国外禁止出口密码算法和产品，所 谓出口的安全的密码算法，都是有破译手段的；而且任何人也不敢担保国外的算 法和产品中是否存在“陷门”，关键时刻是否会危害我国安全。因此我们应该开 发自己的加密系统，研制专业数据加密解密算法，制定一些必要的自己的加密 传输协议。 根据拓扑结构的不同可以把会议密钥管理方案分为3 大类：集中控制式、分 布式和分层分组式。我们采用的主要研究对象t r s 密钥协商协议，针对的是动态 对等通信成员，属分布式。 1 2 密钥协商协议国内外研究现状 密钥协商方案“1 ( k e ya g r e e m e n ts c h e m e ) 是一种能够让通信系统中的两卜或 多个参与主体在一个公开的、不安全的信道上通过通信协商联合建立一次会话 所用的临时会话密钥的通信机制。 有关如何构建快速安全的会议密钥方案方面，许多学者作了研究。1 9 4 9 年， c e s h a n n o n 第一次提出了著名的s h a n n o n 保密理论”1 ，指出了一次一密系统的 安全性和经常性更换密钥的重要性。而经常性的更换密钥在实际操作中却因为 过于繁琐而不可行。基于此，人们提出了“会话密钥”的概念。该密钥只在本 次通信过程中有效，通信一旦结束，该密钥即被销毁。而这个“会话密钥”也就 是会议密钥，如果该密钥由一个k d c 产生，然后分发给各个与会者，称为“密 钥分发”；但这个密钥是由各个与会者通过交换各自的秘密信息共同协商、计 算而产生，称为“密钥协商”。 有关如何以协商的方式产生会议密钥的问题，早在1 9 8 8 年就由b e r m e t t ， b r a s s a r d 和r o b e r t ”1 提出了保密增强的概念，后由b e n n e t t 、b r a s s a r d 加以推广。 所谓保密增强就是从部分保密的共享信息中提取出高度保密的共享信息的过 程，它是安全密钥协商协议”的最后个也是最重要的一个步骤。假设通信双 方a l i c e 和b o b 共享一个串s ，而敌手e v e 只了解关于该串的一部分信息。保 密增强的实现方法是：a l i c e 和b o b 通过在一个具有认证功能的公开信道上传 四川师范大学硕士学位论文 递一个合适的h a s h 函数h ，双方计算出s = h ( 5 ) ，使得e v e 所知道的关于s 的信息几乎可以忽略。 非认证信道上的安全密钥协商的实现最主要的是要防止敌手篡改通信双方 在公共信道上的协商内容，或敌手冒充一方来执行密钥协商协议。而要解决这 一问题最好的方法就是认证。使用传统的认证技术的前提条件是通信双方间共 享一个认证密钥，而安全密钥协商的目的就是要产生共享密钥，这是相互矛盾 的。所以，如何在不共享认证密钥的情况下来实现公共信道上的协商内容的认 证是安全密钥协商成功的关键。鉴于此，刘胜利、王育民在1 9 9 9 年基于纠错码 理论对无条件安全密钥协商中认证问题进行了研究。1 ，提出在敌手的信道比通 信双方的信道都差的条件下，总能够找到一种( ，k ，d ) 线性码来实现通信双方 的认证问题，并使得收方接受合法消息的概率至少为1 1 sz ，且拒绝非法消息 的概率至少为1 一x , “，其中，s 和s 均为大于1 的安全参数，并对所需的认证 符长度的下界与初始化阶段信道的误比特率、认证方案的传信率及安全参数间 的关系进行了一定的研究。 与此同时，i n t e m e t 工程任务组( i n t e m e te n g i n e e r i n gt a s kf o r c e ，i e t f ) 于 1 9 9 3 年3 月成立了i p s e c 工作组“，专门研究制定网络层上的安全标准。1 9 9 5 年8 月，i p s e c 工作组公布r f c l 8 2 5 - - 1 8 2 9 等，提出了i p s e c 最初的设计方案； 1 9 9 8 年1 2 月，该工作组推出r f c 2 4 0 1 2 4 1 2 等，对原方案进行了大量改进， i p s e c 的总体框架基本形成；2 0 0 0 年3 月，i p s p 工作组( 口s e c u r i t yp o l i c v w o r k g r o u p ) “”成立，继续讨论i p s e c 安全策略问题。在i p s e c 工作组制定i k m p 的标准化过程中，先后采用了很多方案，最后强制推行i k e 密钥管理方案。由 于i k e 使用计算量较大的d h “4 ( d i f f i eh e l l m a n ) 算法来协商相互间的公共会 话密钥( s e s s i o nk e y ) ，并且，i k e 使用数字签名来实现认证，计算量也很大， 较浪费时间，所以i k e 是一个“昂贵”的密钥协商协议，运行速度漫。 有关密钥协商的研究。除了以上所提出的有关工作，还有很多其他的密钥 协商方案，如c k d 协议、g d h 协议、t g d h 协议、s t r ( s t e e r , e ta 1 ) 协议、 b d 协议“”等，除此之外，还有改进型m g d h 2 协议“”以及基于k e r b e r o s 的密 钥协商协议“”等。 四川师范大学硕士学垃论文 1 3 本人所做的主要工作 本文在详细比较了现有各种适合群组通信的密钥管理协议之后，针对其中 的密钥协裔协议进行了深入豹研究，综合比较了k e 协议、g d h 协议、c k d 协议和t 瑙协议。对计算量较小，适合现有最为复杂的的群组，即动态通信组 ( d y n a m i cp e e rc o m m u n i c a t i o n ) 的密钥协商协议t t s 协议进行了改进，使 其更加适台当前的动态对等通信( d y n a m i cp e e rc o m m u n i c a t i o n ) ，具有更加完善 的安全性。 具体来说，本文所作工作如下： 在快速生成元查找算法的基础上，对有限域z p 中鼋阶生成元的的问题 进行了讨论，并针对p 、q 为大素数，q f p l 的情况下，提出了个高效的查 找有限域勿中q 阶生成元的算法。 将r r s 密钥协商协议进行了改进。与原有的r r s 协议相比，改进的r r r s 协议采用高效的单向h a s h 函数和异或运算，仅以很小的计算代价，具有良好 的密钥证实性、源认证和抗同谋破解等安全属性。 在v c + + 6 0 中实现了改进的t r s 密钥协商协议，解决了加密软件和 高次模余p a ) 及s h a m i r 门限结构等实现中涉及到的一些技术问题。实验结果证明， 改进的t i s 密锈协商协议的正确性，最后详细阐述了各个功能模块算法和流 程。 望丝堕薹奎兰竺圭兰竺笙苎 第二章相关数学理论及常用加密算法 2 1 相关数学理论 数论在计算机科学、组合数学、密码学、数字信号处理等领域都有广泛的应 用。下面我们仅简单介绍数论中有关整除、同余、f e r m a t 定理、欧拉( e u l e r ) 定 理等与密码学关系较为密切的内容。 21 1 素数以及互素的概念 定义2 1 ( 除数园子) 设z 为由全体整数而构成的集合，著6 ，0 ，且使得a = r o b ， 此时称b 整除a 。记为b l a ，还称6 为a 的除数( 因子) 。若= r o b + r 且o 0 ，由于小于1 6 i 的正整数只有有限个，以及1 整除 任一整数，所以这过程不能无限制地做下去，必定会出现某个n ，要么ir , 一， ( t 是的倍数) ，1 ，要么- 1 ，此时余数+ 1 = 0 。 由此得到如下推论： 推论：r n10 ，b ) 这是因为和，6 ) 一( 6 ，) 一( ，r ，) 一以。一，) ；( 。) ： 另外，由上得出 一a q t b0 f b f r 2 。b q 2 厂1 0 i 2 r 3 = 一窜3 r 2 0 1 ( r 3 为阿贝尔群。为了简便起 见，口+ b 简记为a b 。则佃b ) c = a ( b c ) ，可记为a b c 。 定义2 1 0 ( 有限域) f 是至少含有两个元素的集合，对f 定义两种运算“+ ” 和“一，并且满足以下三条件的代数系统cf ，+ ，+ ，称为域： 1 ) f 关于“+ ”运算构成一个阿贝尔群，且其单位元为0 ； 2 ) f 0 ) 关于“运算构成一个阿贝尔群； 3 ) 对于口，b ，c e f ，分配律成立，即 + 6 ) c 嚣口十c + 6 $ c c 十 + 6 ) 一c 4 + c 6 如果域f 中元素的个数有限，则称f 为有限域或伽罗瓦( g a l o i s ) 域，定义f 上元素的个数为f 的阶，计做i f i 。j 霸g f ( q ) c 表示g 阶的有限域。域中所有 非o 元素全体定是一个有限“群，群中每个元素的阶是有限的。 定义2 1 2 ( 生成元) 在有限域g f ( q ) 中，总能找到一个元素口，他的阶为 q 一1 ，即g t 1 ，他能生成域中所有q 一1 个非0 元素，则n 为有限域的生成元， 或称为本原元。 由上定义我们知道，如果口g f ( 口”) ，且为g f ( q “) 上的本原元，则 盘矿t 1 ，g f 国4 ) 中碍4 个元素可以表示为f 0 , 1 ，口，口2 ，口矿一2 。 定理2 1 2 ( 拉格朗日定理) ：设g 是有限群，而s 是g 的子群，又设i g 卜月， i s i m 。则m f n 。为叙述方便我们定义元素的阶为：k 。= 罂缈0 f 口；1 r o o d p t ， 称k 为元素的阶。 推论：设g 是模p 乘群，对任意的口属于g ，则元素4 的阶k 。是i g i ；肌的 因子，即k 。i 肌。 ， 证明：令s = 恤m o d p ，n 2 m o d p ，a 3 m o d p ，m o d p = 1 ，则s 是一个 以口为生成元，1 为幺元的模p 乘群，且是循环群。由于g 是群，根据群的封闭 性有s 是g 的子群- 根据拉格朗日定理，l s t k 。，所以k 。是l g l 的因子。 10 四川师范大学硕士学位论文 2 1 6 秘密共享和s h a m ir 门限结构 秘密共享是将共享的秘密在一组参与者之间进行分配，以达到多人掌管秘密 的目的。其思想是：将共享秘密s 进行分割成托份( 又叫“影子”) ，分发给 t 个 参与者，当他们同时出示各自的1 n 份秘密时，才能恢复出s ，如果使用任意t 个 参与者所用有的秘密片断可恢复出s ，则叫做( r ，n ) 门限方案。他的概念最早是 q b l a k e y o “和s h a i l l i r “”各自分别提出的，并给出了具体的( t ，n ) 门限秘密共享方 案，另外，很多专家学者在秘密共享的问题上进行了研究“”“。 一个( f ，n ) 门限秘密共享方案称作“完善的”是指任意少于t 个的参加者协 作都不能得到有关这个秘密s 的任何部分信息，而无论他有多大的计算能力。一 个门限秘密共享方案称作“无条件安全的”是指欺诈成功的概率被限定在一个指 定的概率，无论其有多大的计算能力”“。 s h a m i r 提出的( t ，n ) 门限，是基于有限域g “p ) 上多项式分解方案的， 设：， ) = a t _ i x 14 - 4 - a l x + a o m o d p ，其中s = ，( o ) 一a o 为秘密，p 为 大于s 的素数。a 1 ，a 2 ，a n 为选用的随机系数，这些需要保密，在生成n 个 秘密份额后即可销毁，通过计算多项式厂( z ) x c n 个不同的x ，值给出秘密份额 s f = f f ) m o dp ，“= l ，2 ，甩) 其中( s 。，工，) 为，上的点，可以看作是用户的标识由任意f 个点可唯一的 确定相应的t 一1 次多项式所以秘密s 可以从f 个秘密份额重构，给定任意f 个 秘密份额【s i l ，x f ，) ，( s i ：，x 。：) ，( s f ，x l ，) 由l a g r a n g e 插值公式可以重构多 项式： m ，2 酗t ，n 。，羞m 帅 从而可以恢复出共享的秘密信息 ”口0 - ，( o ) - 弘，h ， 一x i j x i ，一x 1 m o dp 四川| i l j 范大学硕士学位论文 2 2 常用密码算法 2 2 ，1 单向h a s h 函数概述 h a s h ( 哈希) 函数就是被设计为基于通过特定压缩函数的不断重复“压缩” 输入的分组和前一次压缩处理结果的过程，直到整个消息都被压缩完毕，最后的 输出作为整个消息的散列值。换句话说，就是输入一个长度不固定的字符串，返 回一串定长度的字符串，又称h a s h 值。尽管还缺乏严格的证明。但绝大多数业界 的研究者都同意，如果压缩函数是安全的，那么以上述形式散列任意长度的消息 也将是安全的。 任意长度的消息被分拆成符合压缩函数输入要求的分组，最后一个分组可能 需要在末尾添上特定的填充字节，这些分组将被顺序处理，除了第一个消息分组 将与散列初始化值一起作为压缩函数的输入外，当前分组将和前个分组的压缩 函数输出一起被作为这一次压缩的输入，而其输出又将被作为下个分组压缩函 数输入的一部分，直到最后一个压缩函数的输出，将被作为整个消息散列的结果。 由于非对称算法的运算速度较慢，所以在数字签名协议中，单向散列函数扮 演了一个重要的角色。只要通信的双方协商好使用的h a s h 函数和签名算法。就可 以使用h a s h 函数进行签名和认证。 签名方先对该数据文件进行计算其散列值，然后再对很短的散列值结果用非 对称算法进行数字签名操作。对方在验证签名时，也是先对该数据文件进行计算 其散列值，然后再用菲对称算法验证数字签名。 对h a s h 值，又称“数字摘要”进行数字签名，在统计上可以认为与对文件本 身进行数字签名是等效的。这样的协议有很多优点： 首先，数据文件本身可以同它的散列值分开保存，签名验证也可以脱离数据 文件本身的存在而进行。 其次，有些隋况下签名密钥可能与解密密钥是同一个，也就是说，如果对一 个数据文件签名，与对其进行非对称的解密操作是相同的操作，这是不安全的， 在特定情况下，恶意的攻击者可能将一个试图解密的文件发送给你，提出签名请 求，这样是很不安全的。因此，在任何情况下，对其h a s h 值进行签名都是安全的。 这样选择数字摘要进行数字签名，使得信息的接收者不仅可以解决用户身份 验证问题和完整性验证问题，还解决了不可抵赖性的问题。而不可抵赖性，能够 保证信息的发送者无法否认自己确实发送了这个信息。这些特性如同加密功能一 坚型堕蔓查堂堡主兰垡堡兰一 样是整个密码系统的最基本功能。 我们使用中对h a s h 函数的特殊要求是： 1 接受的输入报文数据没有长度限制； 2 对任何输入报文数据生成固定长度的摘要( 数字指纹) 输出： 3 从报文能方便地算出摘要； 4 难以对指定的摘要生成个报文，而由该报文可以算出该指定的摘要； 5 难以生成两个不同的报文具有相同的摘要。 2 2 2 数字摘要算法m d 5 2 2 2 1m d 5 简介 m d 5 ”6 1 ( m e s s a g ed i g e s t5 ) 是一种应用广泛的提取数字指纹的报文摘要算法 标准，由m t 的密码学专家、r s a 算法的发明人之一的r i v e s t 设计提出的，经m d 2 、 m d 3 和m d 4 发展而来。m d 5 算法是通过数学运算，把不同长度的信息转化到1 2 8 位编码中，形成h a s h 值，通过比较这两个数值是否相等，来确定通信双方的合法 性。这也可以说是数字签名，在数据传输后，可以通过比较h a s h 值来判断信息 途中是否被截获修改，是否由合法的发送人发送或者合法的接收入接收等。用这 种方法，可以防止密钥丢失的问题，因为它的加密部分是随机生成的，如果没有 正确的h a s h 值根本就无法解开加密部分，而且它还具备了数字签名的能力，可 以证明发送方和接收方的合法身份，具有不可抵赖性，很适用于商业信息的传递。 m d 5 的典型应用是对一段信息( m e s s a g e ) 产生信息摘要( m e s s a g e d i g e s t ) ，以防止 被篡改。它还被广泛用于加密和解密技术上。m d 5 要求发送方和接收方都要计算 整个报文的摘要。 2 2 2 2m d 5 算法原理 由于m d 5 对任意长度的信息输入，都将产生一个长度为1 2 8 b i t 的输出，因此 输出可以看作是原输入报文的报文摘要值( m e s s a g ed i g e s t ) 或数字指纹( d i g i t a l f i n g e r p r i n 0 。 根据算法的复杂性理论知道，m d 5 算法输出具有下列特征： ( 1 ) 两条不同的报文具有相同的报文摘要值的可能性极小； 四川师范大学硕士学位论文 佗) 对于预先给定的报文摘要值，要想寻找到一条报文使得其报文摘要值与 某个给定的报文摘要值相等，在计算上是不可能的： g ) 根据报文的摘要值，要想推测出原来的报文是极端困难的。 夺m d 5 算法处理报文摘要的过程如下： 步骤1 ：添加填充位。在消息的最后添加适当的填充位，使得数据位的长度 对5 1 2 求余的结果是4 4 8 ，即：l e n g t h = 4 4 8 m o d 5 1 2 。具体补位操作：补个1 ，然 后补0 至满足上述要求。 步骤2 ：补数据长度。原始消息长度( 二进制位的个数) ，用一个6 4 位的数字 表原始长度b ，把日用两个3 2 位数表示。并附加在步骤1 的结果后。由这两个步骤 得到长度为5 1 2 整数倍的报文。表示为个5 1 2 位的数据块：k ，k - l o 其长 度为l x 5 1 2 b i t s 。令= l x l 6 ，则长度为个3 2 位的字。令m o 一l l 表示以字 为单位的消息表示。 步骤3 ：初始化m d 5 参数。用四个个3 2 位的熬数( a ，b ，c ，d ) 计算信息摘 要。初始化为以下的1 6 进制值。a - - o x 0 1 2 3 4 5 6 7 ；b - - o x 8 9 a b c d e f ：c ：0 x f e d c b a 9 8 ： d = 0 x 7 6 5 4 3 2 1 0 。 步骤4 ：处理消息块( 5 1 2 位= 1 6 个3 2 位字) 。一个压缩函数是本算法的核心 ( h m o s ) ，它包括4 轮处理。四轮处理具有相似的结构，但每次使用不同的基本逻 辑函数，记为f ，g ，h ，i 。每一轮以当前的5 1 2 位数据块( k ) 和1 2 8 位缓冲值 a b c d 作为输入，并修改缓冲值的内容。每次使用6 4 元素表r 1 6 4l 中的四分 之一。该t 表由s i n 函数构造而成。f 的第i 个元素表示为r i 1 ，其值等于 2 3 2 x a b s ( s i n o ) ) 的整数部分，其中f 是弧度。m q = a b s ( s i n ( i ) ) 是一个。到1 之间的数，t 的每一个元素是一个可以表示成3 2 位的整数。t 表提供了随机化的 3 2 位模板，消除了在输入数据中的任何规律性的特征 t 表 t 1 】= d 7 6 a a 4 7 8 t 2 】= e 8 c 7 8 7 5 6 t 3 】= 2 4 2 0 7 0 d b t 4 = c 1 b d c e e e t 4 9 = f 4 2 9 2 2 4 4 t 5 0 】= 4 3 2 a f f 9 7 t 5 1 】= a b 9 4 2 3 a 7 t 5 2 j = f c 9 3 a 0 3 9 t 1 6 】= 4 9 b 4 0 8 2 1t 6 4 = e b 8 6 d 3 9 1 步骤5 ：输出结果。所有l 个5 1 2 位数据块处理完毕后，最后的结果就是1 2 8 14 四川师范大学硕士学位论文 位消息摘要。 2 2 2 3m