（通信与信息系统专业论文）数字签名中单向散列算法的研究.pdf

摘要 摘要 随着计算机网络技术的飞速发展，人们为了提高工作效率，提出了电子商 务和电子政务，这就要求实现对文件和票据实现数字签名。数字签名在上世纪 的早期就提出了，并在世界上一些发达国家得到了法律的认可，但是到如今数字 签名很少应用到电子商务和电子政务中，最主要的原因就是数字签名技术中一 项关键技术单向散列算法的安全性成了技术瓶颈。虽然现有很多产生签名 摘要的散列函数，但是安全的散列函数几乎没有，曾一度被认为安全的m d 5 算 法和s h a 系列算法，也不断地受到攻击，这些算法已被部分或全部破译，这样 使电子商务和电子政务的发展陷入僵局。 本文分析了已有的主要单向散列函数的不足之处，在m d 5 基础上提出了一 种新的安全散列算法t - m d 。对t m d 算法的设计思想、t m d 算法的过程描述及 t m d 算法的设计原理作了详细的介绍。从理论上论证了t m d 具有单向散列函 数要求的几种特性：严格雪崩效应性；o 一1 平衡性；高非线性性；输出的互不 相关性；布尔函数组的函数之间的线性非等价性。本文还通过计算机程序仿真 来实现t m d 算法和m d 5 算法，同时验证了t m d 算法的某些特性，并通过和m d 5 算法作比较来验证t m d 算法是否具有可运行性和优越性。仿真结果表明，t m d 算法在严格雪崩效应、0 - 1 平衡性、运算速度等方面都优于m d 5 算法。 关键字：数字签名，m i ) 5 ，t m d ，单向散列算法 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 ft h et e c h n o l o g yo fc o m p u t e rn e t w o r k s ，p e o p l e r a i s ee - c o l n l n e r c ea n de - g o v e r n m e n tf o rh i g h e rw o r ke f f i c i e n c y , w h i c ha s k su st o i m p l e m e n td i g i t a ls i g n a t u r ef o rf i l e sa n dn o t e s t h o u g hd i g i t a ls i g n a t u r ew a sp u t f o r w a r de a r l yi nl a s tc e n t u r ya n di tw a sa d m i t t e di nl e g a l l y , i th a sb e e nh a r d l ya p p l i e d i ne - c o m m e r c ea n de - g o v e m m e n tf o rt h es e c u r i t yo ft h ek e yt e c h n o l o g y “o n e - w a y h a s hf u n c t i o n i ns p i t eo f b e i n gm a n yh a s hf u n c t i o n s ，b u tt h e ya l la r en e a r l yu n s a f e a n de v e nm d 5a n dt h es e r i a lo fs h at h a ta r er e g a r d e da st h es e c u r e s ta l g o r i t h m sa r e c o n s t a n t l ya t t a c k e d t h e s ea l g o r i t h m sh a v eb e e ne x p o s e dp a r t l yo rw h o l l y , w h i c h l a r g e l yr e s t r i c t st h ed e v e l o p m e n to fe - c o m m e r c ea n de - g o v e r n m e n t i nt h ep a p e r , t h ea u t h o rd e s c r i b e st h es h o r t c o m i n g so fs o m em a i ns i n g l e w a y h a s hf u n c t i o n sa n dr a i s e san e wa n ds e c u r ea l g o r i t h mt - m db a s e do nt h ea l g o r i t h m m d 5 ，a n db a t sa r o u n dt h et h i n k i n g ，p r o c e d u r ea n dp r i n c i p l eo ft - m d t h e o r e t i c a l l y , t h ea u t h o rd e m o n s t r a t e st l l a tt = m dh a ss o m ep r o p e r t i e so fs i n g l e w a yh a s hf u n c t i o n ， i n c l u d i n gs t r i c ta v a l a n c h ec r i t e r i o n ，t h eb a l a n c eo fo 一1 ，h i g h e rn o n - l i n e a r i t y ，o u t p u t n o n - r e l a t i v i t ya n dn o n - e q u i v a l e n c ei nas e r i a lo f b o o lf u n c t i o n s i nt h ep a p e r , e m u l a t o ri sa p p l i e dt oi m p l e m e n tt h ea l g o r i t h m st - m da n dm d 5 ， a n dv e r i f i e ss o m ep r o p e r t i e so ft - m d c o m p a r e dw i t hm d 5 ，t h ef e a s i b i l i t ya n d s u p e r i o r i t yo ft - m da r ev a l i d a t e d t h er e s u l to fe m u l a t o rd e m o n s t r a t e st h a tt - m di s b e t t e rt h a nm d 5i nc e r t a i np r o p e r t i e ss u c ha ss t r i c ta v a l a n c h ec r i t e r i o n ，t h eb a l a n c eo f o - 1 ，c o m p u t i n gs p e e da n d s oo n k e yw o r d s ：d i g i t a ls i g n a t u r e ，m d 5 ，t - m d ，o n e - w a yh a s ha l g o r i t h m i i 学位论文版权使用授权书 本人完全了解同济大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 经指导教师同意，本学位论文属于保密，在多年解密后适用 本授权书。 同济大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 第一章绪论 第一章绪论 本章作者首先阐述了论文的研究背景及意义，然后概述了论文主要的研究 内容，最后对论文的组织结构作了一个简述。 1 1 研究背景及意义 自从数字签名提出以来，备受世界各国的重视，特别是发达国家，为了使 数字签名和手写签名具有同样的法律效应，许多国家纷纷立法认同数字签名。 然而，数字签名在全世界并没有得到广泛运用，包括发达的欧美国家。大多数 文件，票据签名仍然采用手写签名。这主要是由于数字签名方案中往往需要对 文件产生散列值相当于手写签名的“指纹 或图章，而现在产生摘要的函 数单向散列函数没有一种可以保证安全，虽然单向散列函数在操作系统加 密等方面有所应用，但涉及到安全度较高的文件、电子商务及电子政务等方面 还没有得到广泛应用。 单向散列函数要求具备这几个特性1 7 1 ：( 1 ) 函数的输入可以是任意长度的消 息：( 2 ) 函数的输出是固定长度的；( 3 ) 给定消息m ，很容易根据散列函数h 计算 出散列值h ，即h ( m ) = h ；( 4 ) 给定h ，根据h ( m ) = h 很难推导出m ；( 4 ) 给定m ， 要找到另一个消息m 并满足h ( m ) = h ( m ) 很难；( 5 ) 要找到两个随机的消息m 和m ，使h ( m ) = h ( m ) 很难。在这些条件中，对于条件( 1 ) ( 2 ) ( 3 ) 几乎现存 的所有单向散列函数但满足，但是条件( 4 ) ( 5 ) 就很难满足，这两个条件看似容 易实现人们普遍认为应该属于穷举攻击。但是现代密码学的攻击者，往往 不走穷举攻击这条路而是采用差分分析和线性分析对一些算法实施攻击【2 i 】，这 样比较容易实现对单向散列函数的部分或全部攻击。 现有的单向散列函数，有r a l p hm e r k l e 提出的s n e f r u 算法；同本电报公司 提出的n h a s h 算法；r i v e s t 提出的m d 2 ，m d 3 ，m d 4 ，m d 5 算法；欧共体提出的 r i p e 。m d 算法；由yz h e n g ，j p i e p r z y k 和j s e b e r r y 提出的h a v a l 算法：由c 砌 m e y e r 提出的d a v i e s m a y e r 算法；由i b m 提出的m d c 2 和m d 4 ；n i s t 提出 的s h a 0 ，s h a 1 ，s h a 2 等算法，等等。其中最常用最流行的是m d 5 算法和s h a 系列算法。事实上m d 5 和s h a 系列中的s h a 0 也受到了不同程度的攻击【6 1 【7 1 【9 1 ， 第一章绪论 自从m d 5 在2 0 0 4 年8 月被破译后，人们开始放弃使用m d 5 。 以上列举的这些主要的单向散列算法，相继被部分或全部破译，往往是由 于单向散列函数的结构单一化、算法的轮数较少、算法不满足严格雪崩效应( 将 在的第三章定义) 、轮函数非线性性不高等原因造成的。作者在本文提出的t - m d 算法将解决这些方面的问题，以使算法具有更高的安全性。 1 2 本文研究内容 首先，本文将对现有的数字签名的产生、发展及它存在的意义进行描述， 并对数字签名方案中用到的公钥密码技术和单向散列函数进行简单的介绍。然 后列举现有的主要单向散列函数，分析其存在的问题及已经受到的攻击。 接着，作者将在m d 5 基础上，借鉴了m d 5 非线性函数的设计方式、移位 方式以及加入常量使信息扩散等方式。提出了一种新的单向散列算法t m d ，该 算法采用了多个7 变量高非线性布尔函数，运算的轮数由m d 5 的4 轮增加为6 轮，位移由m d 5 的左移改为循环右移，增加了摘要的长度( m d 5 的两倍) ，并且 增加了置换函数，使其结果接近或满足映射分布均匀性，特别是利用了b e n t 函 数的特性，使算法满足了数字签名中的单向散列函数的几个特性：0 1 平衡性， 严格雪崩效应，高非线性性，函数间的线性非等价性，输出互不相关性。并对 这些特性进行了一一论证。这些特性增加了线性分行和差分分析的攻击难度， 并且大大增加了穷举攻击( 包括生同攻击) 的难度。并从其设计思想、设计过程、 设计原理和安全性分析进行阐述。 最后，t - m d 算法是在m d 5 的基础上提出的，作者从理论上论证了t - m d 算法满足单向散列算法的各种特性，并对t o m d 算法及其特性进行程序仿真，仿 真试验结果表明，t - m d 算法在严格雪崩效应性、运算速度等方面均优于m d 5 。 从而说明了作者设计的t o m d 算法达到了预期的目的。 1 3 本文的组织结构 第一章：绪论 本章简要概述本文的研究背景及意义、文章的研究内容和文章的章节安排。 第二章：数字签名函数中的单向散列函数 2 第一章绪论 本章将先对单向散列函数的定义、条件和工作原理进行描述，然后将介绍 两类生同攻击，接着简述现有的主要的散列函数及其不足之处，并对m d 5 算法 进行详细描述。 第三章：一种新的单向散列函数t m d 本章将详细描述t - m d 算法的设计思想、设计过程和设计思想，并对t m d 是 否满足的数字签名的散列函数特性进行了一一论证。 第四章：t m d 算法及特性的仿真实现 本章首先对t - m d 算法进行了仿真，然后对t m d 算法是否满足单向散列函 数的某些特性进行了仿真验证。 第五章：总结与展望 本章对全文所论述的问题进行了一个概括和总结，然后提出了对单向散列函 数技术的进一步考虑。 第二章数字签名中的单向散列函数 第二章数字签名中的单向散列函数 本章将首先介绍数字签名的发展、意义及技术瓶颈，由此引出单向散列函数 的存在意义；接着，介绍了单向散列函数的定义、满足的条件及工作原理：然 后，描述了穷举攻击方法之一生r 攻击的两种类型；并对已有的单向散列 函数及存在的不足进行了简述；由于作者在第三章提出的t - m d 算法是在m d 5 基 础上改进的，所以本章的最后对m d 5 算法作了详细描述。 2 1 数字签名的发展、意义及技术瓶颈 随着计算机网络技术的迅速发展及广泛应用，人们对计算机的依赖程度就 越来越高，许多文件由原来的手写稿件变成了现在的电子文档，并且随着社会 的发展，国内外贸易往来同益增加。国家与国家之间、公司与公司之间以及其 他各个组织之间的文件签署日益增多，如果还是采用原来的亲笔手写签名的话， 会严重影响办事效率，阻碍社会的发展。因此，一些发达的西方国家在2 0 世纪 9 0 年代后就提出了一种代替传统的手写签名的方法数字签名，并且从法律 上给予认可。数字签名最早是用在国防部门，其中之一就是用在美国和前苏联 签订的禁止核试验条约的验证i s 】。随后在电子商务和电子政务方面得到了广泛应 用。 2 0 0 4 年8 月2 8 同，我国在十届全国人大常委会第十一次会议表决通过了电 子签名法。这部法律规定，可靠的电子签名与手写签名或者盖章具有同等的法 律效力。电子签名法的通过，标志着我国首部“真正意义上的信息化法律”已j 下式 诞生，将于2 0 0 5 年4 月1 只起施行。 数字签名是由公钥密码发展而来，它是公钥密码技术和散列函数( h a s h f u n c t i o n ) 技术的结合体。为了数字签名得到广泛而安全的应用，许多专家、学者 进行了相关研究并取得了一定的成就。在公钥密码技术方面，美国麻省理工大 学的三位学者r i v e s t ，s h a m i r , a d l e m a n 提出的r s a 算法是最流行的公开密钥算法 1 8 】，它既可以用于加密，也可以用于数字签名；而在1 9 9 1 年n i s t 提出的数字 签名算法( d s a ，d i g i t a ls i g n a t u r e a l g o r i t h m ) 作为一种标准算法，成为了数字签名 标准( 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 ) 的一部分，它是一种无专利的算法，因而得 4 第二章数字签名中的单向散列函数 到了广泛应用【7 】。而在散列函数技术方面，有r a l p hm e r k l e 提出的s n e f r u 算法； 同本电报公司提出的n h a s h 算法；r i v e s t 提出的m d 2 ，m d 3 ，m d 4 ，m d 5 算法； 欧共体提出的r i p e m d 算法；由yz h e n g ，j p i e p r z y k 和j s e b e r r y 提出的h a v a l 算法；由c a r lm e y e r 提出的d a v i e s m a y e r 算法；由i b m 提出的m d c 2 和m d - 4 ； n i s t 提出的s h a 系列算法，等等。 多年以来，公钥密码技术和散列函数技术都在不断地发展与完善，然而一 些攻击者也在不断地挑战这两项技术，公钥密码算法的代表r s a 也在不断受到 攻击【2 3 】【2 4 1 ，但是这些攻击仅限于局部或假定的理想状态，总体上还是相当安全的， 事实上，r s a 已成为了公钥密码算法的标准 8 1 。但是散列函数技术就没那么幸 运了，其代表m d 5 和s h a 系列中的s h a 0 也受到了不同程度的攻击【6 j 【7 】【9 】。 特别是在2 0 0 4 年8 月1 7 日的国际密码学年会( c r y p t o2 0 0 4 ) 上，来自中国的 王小云、来学嘉等教授宣布文献【9 1 的相关内容，声称能在极短时间内使算法m d 5 、 h a v a l 一1 2 8 、m d 4 以及r i p e m d 一1 2 8 算法产生碰撞。这一消息的发布，世界密码学 界的专家、学者感到极为震惊。m d 5 的设计者，同时也是国际著名的公钥加密算 法r s a 的第一设计者r r i v e s t 在邮件中写道：“这些结果无疑给人非常深刻 的印象，她应当得到我最热烈的祝贺，当然，我并不希望看到m d 5 就这样倒下， 但人们必须尊重真理。 原来m d 5 的专项破解网站h t t p ：w w w m d 5 c r k c o m 也 就此关闭。尽管现在还有s h a 一1 可使用，但是它的设计思想至今仍未公布，并 且s h a 一0 已经受到各种不同的攻击，我们不能保证s h a 的设计思想一直都成为 秘密。由于m d 5 的破解，人们开始放弃m d 5 ，现在世界各国都在呼吁：尽快发明 一种安全的散列算法来保证数字签名的安全性。 数字签名的安全性是当今社会的电子商务和电子政务中的技术瓶颈，提出 一种安全的散列函数算法来保证数字签名的安全性就尤为重要，可以这样说， 数字签名将在国际社会的政治、经济、文化生活中扮演着十分重要的角色，而 散列函数算法是否安全可靠将直接关系到这个角色扮演的成败。提出一种相对 安全的单向散列算法就是作者撰写这篇论文的目的所在。 2 2 散列函数的定义及其满足的条件 单向散列函数( h a s hf u n c t i o n ) 是指将任意长度的消息m 映射成一个固定长 度的值h 的函数： 第二章数字签名中的单向散列函数 h = h ( m ) 称这个固定长度的值h 为消息摘要( m e s s a g ed i g e s t ) 或散列值。消息摘要在许 多签名算法及签名方案中的得到广泛应用，它是基于单向散列函数的。在数字 签名中单向散列函数必须满足以下条件： ( 1 ) 函数的输入可以是任意长度的消息： ( 2 ) 函数的输出是固定长度的； ( 3 ) 给定m ，很容易计算h ； ( 4 ) 给定h ，根据h ( m ) 兰h 很难推导出m ； ( 5 ) 给定m ，要找到另一个消息m 并满足h ( m ) = h ( m ) 很难； ( 6 ) 单向散列函数抗碰撞的条件：要找到两个随机的消息m 和m ，使h ( m ) = h ( m ) 很难。 在这些条件中，条件( 1 ) ( 2 ) ( 3 ) 是散列函数用于消息认证的基本要求；条件 ( 4 ) 是要求函数满足单向性；条件( 5 ) ( 6 ) 要求函数无碰撞，所谓无碰撞，是指函 数输入任意两个不同的消息都不会产生相同的消息摘要。相反，如果一个函数 输入两个不同的消息产生相同的摘要，就称函数具有碰撞性。 2 3 单向散列函数的工作原理 在实际应用中，单向散列函数是建立在压缩函数之上的。假定需要处理的 消息m 的长度为k 位，单向散列函数的输出长度为位。压缩函数处理消息之 前，现将消息m 分成m l ，m 2 ，m n 分组，每一个分组都是等长的，最后一个 分组可能长度不够，需要对其填充，它还包括消息的长度值。 压缩函数的输入是消息的分组和前一组的输出( 第一个压缩函数中此部分为 一个初始化向量) 。对于第一个压缩函数，其输入为消息分组m l 和初始化向量； 第二个压缩函数的输入是第一个压缩函数的输出散列值和第二个消息分组m 2 ， 并且它的输出作为第三个压缩函数的输入之一，如此循环直到最后一个 压缩函数产生输出散列值，即整个消息的散列值( 消息摘要) 。每一个压缩函数的 输出散列值是到该点的所有分组的散列值，即分组m i ( 1 5 i n ) 的散列值为： h i = f ( m i ，h i 1 ) 其工作原理如图2 1 所示。 6 第二章数字签名中的单向散列函数 消息分组m 1l 消息分组m 2 i 消息分组m n + 填充位 初始向。昂刊压缩函州压缩函划 叫压缩函剡p 消息摘要 图2 1 单向散列函数的：作示意图 消息摘要的信息应该包含整个消息长度的某种二进制消息。这种方法消除 了由不同长度的消息可能会具有相同的散列值所带来的潜在的安全问题【1 l 【2 l 。 2 4 生日攻击 首先引出以下两个问题： ( 1 ) 已知单向散列函数h 有n 个可能的等概率输出，h ( x ) 是一个特定的输出， 如果对函数h 随机取k 个输入，则至少有一个输入y ，且y x ，使得h ( y ) = h ( x ) 的概率为0 5 时，k 有多大? ( 2 ) 已知单向散列函数h 有n 个可能的等概率输出，如果在函数h 的k 个输 入中至少有两个取值x ，y ( y x ) 的函数输出相同的概率大于0 5 ，则k 至少多大? 称问题( 1 ) 中对散列函数h 寻找上述y 的攻击为第1 类生同攻击。称问题( 2 ) 中寻找散列函数h 的具有相同输出的两个任意不同输入的攻击方式为第1 i 类生 同攻击。 2 4 1 第1 类生日攻击分析 下面对问题( 1 ) 进行数学分析。 。函数h 有1 1 个等概率输出 。输入y 时，h ( y ) = h ( x ) 的概率为1 n 输入y 时，h ( y ) h ( x ) 的概率为1 1 n 当y 取k 个随机值时，均有h ( y ) h ( x ) 的概率为 ( 1 1 n ) 。 。当y 取k 个随机值时，至少有一个y 值满足h ( y ) = h ( x ) 的概率为 1 ( 1 - l n ) k 由高等代数中的泰勒定理知，当i q l l 时， ( 1 + q ) 1 + q k 7 第二章数字签名中的单向散列函数 当r l 很大时，有ii ni 1 ，则 1 ( 1 i n ) k 1 - ( 1 - - k n ) = k n 当k n - - 0 5 时，有k = n 2 。即y 取r 9 2 个随机值时，至少有一个y 值满足 h ( y ) = h ( x ) 的概率为o 5 。 由此可知，假想单向散列函数输出的散列值为m 一位( 0 ，1 值) ，那么可能输 出的个数为2 m ，则当输入取值限制在2 m 。1 个时，则至少有一个输出和已知输出 相同的概率为0 5 。所以，在设计单向散列函数时，我们尽量增加输出的位数， 使输入的消息个数很大的情况下才会产生散列函数碰撞。稍后谈到的m d 5 的输 出位数为1 2 8 - 位，产生第1 类生同攻击的输入需要2 坦1 。而s h a 算法的输出是 1 6 0 - 位，要产生第1 类生r 攻击的输入需要2 1 5 9 个信息，这个数字对现有的计 算机运算速度( 假定每秒运算百万次) 来说，要实现第1 类生同攻击是不可能的。 2 4 2 第1 i 类生日攻击分析 先考虑这样一个问题：已知变量x 在1 到n 之间等概率随机取值，若变量 x 的k 次取值中至少有两个取值相同的概率为0 5 ，则k 至少多大? 由概率论知，变量x 的k 次取值都不相同的概率为： 渺k 南 那么x 的k 次取值中，至少有两个取值相同的概率为： 卜兰 ( 2 1 ) -一 一 i ，_ j ( 刀一七) ! ，z 。 在式( 2 i ) 中，当n = 3 6 5 ，k = 2 3 时，式( 2 1 ) 0 5 ，这就是所谓的生 同悖论口。即，只需要2 3 人，他们中至少有两个人生同相同的概率达到0 5 。 如果此时取k = 1 0 0 ，他们中至少两人生同相同的概率达到o 9 9 。因为当人数k 给定时，得到的至少有两人生日相同的概率比我们想象的要大得多。 再讨论本节开始提出的问题( 2 ) ，当式( 2 1 ) = 0 5 时，可得k = 1 1 8 胛 石= 1 1i 2 。 设散列函数h 有m - 位( 0 ，1 取值) 输出摘要，所以其可能的输出有2m 个，那 么h 的k 个随机输入中至少有两个产生相同输出的概率大于0 5 ，则k 8 第二章数字签名中的单向散列函数 2 ”。这就是第1 i 类生日攻击，即只需要输入2 吡个消息，散列函数产生碰撞 的概率就会达到o 5 。 所以，对于m d 5 算法，由于输出是1 2 8 位，输入2 6 4 个消息中，散列函数 产生碰撞的概率就会达到0 5 ；而s h a 算法输入2 舳个消息，散列函数产生碰撞 的概率才能达到o 5 ，但进行2 舳次运算，在实际上是不可行的。所以在抗第1 i 类生同攻击方面，s h a 强于m d 5 ，同时也表明散列函数的设计者应该考虑适当增 加散列函数输出的位数，以增强抗生日攻击性。 在上一节中，讨论了单向散列函数的条件，其中条件( 5 ) 就是要求抗第1 类 生同攻击；条件( 6 ) 就是要求抗第1 i 类生r 攻击。 2 5 已有的散列函数 在这一节中，作者将简单介绍现有的主要的单向散列函数，并且简述它们各 自的不足之处。 2 5 1 $ n e f r u 算法 1 s n e f r u 算法简述 s n e f r u 算法是r a l p hm e r k l e 设计的一种单向散列函到2 6 1 ，它可以输入任意 长度的消息，而输出是1 2 8 位或2 5 6 位散列值。 首先将消息进行分组，若输出是1 2 8 位散列值，则消息分组长为3 8 4 位；若 输出为2 5 6 位，则消息分组为2 5 6 位。如果最后一个分组的长度没有达到要求 的分组长度时，需要用0 来填充。 算法的核心是函数h ，它将5 1 2 位值散列成1 2 8 位或2 5 6 位。h 输出的前 一部分是这一分组的散列值，后一部分丢弃。而下一消息分组就附加在上一分 组的散列值后，然后又进行散列( 初始分组附在一串0 之后) 。如此循环，直到 最后一个消息分组，在最后一个分组运算以后，将最先的m 位( m 为散列值的长 度) 附在消息长度的二进制表示之后进行最后一次运算。 2 s n e f r u 算法安全分析 b i h a m h e 和s h a m i r 利用差分密码分析证明了两轮s n e f r u ( 1 2 8 位散列值) 是 不安全的【2 7 】。在数分钟内他们找到了散列函数的碰撞。 对四轮或更少轮的1 2 8 位的s n e f r u 算法，能够找到比穷举攻击更好的办法。 9 第二章数字签名中的单向散列函数 而对s n e f r u 算法的第1 i 类生同攻击需要2 “操作，而差分密码分析用2 2 8 。5 操作能找 到三轮s n e f r u 算法具有相同的散列值的一对消息，在四轮找到碰撞需要2 4 4 5 次操 作。由前面讨论的生同攻击理论知，用穷举攻击寻找一给定散列值的消息需要2 1 2 8 次操作，差分密码分析对三轮s n e f r u 算法需要2 5 6 次操作，对四轮s n e f r u 分析需 要2 翮次操作 尽管b i h a m 和s h a m i r 没有分许2 5 6 位散列值，但他们已将分析扩展至2 2 4 位。对于两轮s n e f r u 和需要2 1 1 2 次操作的第1 i 类生同攻击比较，他们仅需要2 1 2 5 次操作就找到了函数碰撞。而三轮s n e f r u 分析只需2 3 3 次操作，对四轮也只需 2 8 1 次操作。 这些研究结果表明，s n e f r u 算法是不安全的。 2 5 2n - i i a s h 算法 1 n - h a s h 算法描述 n - h a s h 算法是由r 本电报公司的研究人员发明的。n - h a s h 算法使用1 2 8 一 位消息分组及一个与f e a l 类似的复杂随机函数【2 ，并产生1 2 8 一位散列值。 其每组消息分组的散列函数膨为： 只= g ( m ，q 1 ) o m ，o h f - l 其中，1 j n ，m i 是消息分组，h o 是一个随机初始值，函数g 是一个复杂 函数。最后一个消息分组的散列值h n 就是整个消息的散列值。初始化时，上一 个分组m i - l 输出的1 2 8 - 位散列值的左半部分6 4 一位和右半部分6 4 一位交换，然后 与1 0 1 0 1 0 1 0 ( 1 2 8 - 位) 二进制异或，再与本轮消息分组m i 异或。该值级联 进入轮处理。轮处理的另一个输入是上一个分组散列值与8 个二进制常数值之 一的异或结果。 互n - h a s h 算法的安全分析 b e r td e nb o e r 发现了一种在n - h a s h 的轮函数中产生碰撞的方法【2 8 】。b i h a m 和s h a m i r 用差分密码分析破解了6 轮n - h a s h 2 7 1 。他们的攻击方法对被3 整除的 轮数能其作用，对小于1 5 的轮数比生同攻击更有效。 同样的攻击对于1 2 轮n - h a s h 需要2 5 6 次操作能找到碰撞，而穷举攻击需要 2 6 4 次操作。1 5 轮n - h a s h 对差分密码分析是相对安全些，攻击需要2 7 2 次操作。 这些研究结果表明，n - h a s h 在轮数较少时是不安全的。 i o 第二章数字签名中的单向散列函数 2 5 3i i a v a l 算法 1 h a v a l 算法简述 h a v a l 是一种散列值可变长的单向散列函数【3 0 l 。h a v a l 以1 0 2 4 一位分组处理 消息，是m d 5 的两倍。它有8 个链接变量，也是m d 5 的两倍。运算的轮数可在3 ， 4 ，5 轮中变化，产生的散列值可以为1 2 8 一位，1 6 0 - 位，1 9 2 - 位，2 2 4 位或2 5 6 一 位。 h a v a l 用非线性的多变量函数取代了m d 5 的简单非线性函数，且每一个函数 均能满足严格雪崩效应。每轮使用不同的函数，该算法同样有两种循环位移方 式。可变的轮数和可变的输出长度意味着该算法有1 5 种不同的形式。 2 h a v a l 安全分析 ( 1 ) 由于对其中一个链接变量采用了循环位移，b e r td e nb o e r 和a n t o o n b o s s e r l a e r s 对m d 5 的攻击，对h a v a l 不起作用； ( 2 ) 对h a v a l 的一个简化版攻击由p r k a s s e l m a n 和w t p e n z h o r n 给 出，这由h a v a l 一1 2 8 的最后一轮( 摘要) 构成1 2 9 】。 ( 3 ) 王小云等教授只通过大约2 6 次h a v a l 计算就破坏了整个h a v a l - 1 2 8 算法【9 i 。 由此可见，h a v a l 也是不安全的。 除了以上的散列算法和2 5 节将介绍的m d 5 算法外，还有其他一些散列算法， 如：用于俄罗斯联邦数字签名的g o s t 散列算法 3 1 1 ；欧共体研制的r i p e m d 算法 1 2z 1 ；由c a r lm e y e r 提出的d a v i e s m a y e r 算法【2 1 1 ；由算法研究公司提出的a l l 算 法【2 1 1 ，等等。由于篇幅有限，作者在次不作一一介绍。 2 6g d 5 算法 由于作者研究的算法是建立在m d 5 算法基础之上，所以在此对m d 5 算法 作一个详细的介绍，以便以后作详细比较。 第二章数字签名中的单向散列函数 2 6 1l i d 5 的由来 m d 5 的全称是m e s s a g e d i g e s ta l g o r i t h m5 ( 消息一摘要算法) ，在9 0 年代初 由麻省理工大学计算机系和r s a 数据安全组织成员r o n l r i v e s t 开发出来， 经m d 2 、m d 3 和m d 4 发展而来。它的作用是让大容量信息在用数字签名软件签署 私人密匙前被散列成一种保密的格式( 就是把一个任意长度的字节串变换成一 定长的大整数) 。不管是m d 2 、m d 4 还是m d 5 ，它们都需要获得一个随机长度的信 息并产生一个1 2 8 位的消息摘要。虽然这些算法的结构或多或少有些相似，但 m d 2 的设计与m d 4 和m d 5 完全不同，那是因为m d 2 是为8 位机器做过设计优化的， 而m d 4 和m d 5 却是面向3 2 位的电脑。 r i v e s t 在1 9 8 9 年开发出m d 2 算法。在这个算法中，首先对信息进行数据补 位，使信息的字节长度是1 6 的倍数。然后，以一个1 6 位的检验和追加到信息 末尾。并且根据这个新产生的信息计算出散列值。后来，r o g i e r 和c h a u v a u d 发 现如果忽略了检验和将产生m d 2 冲突。m d 2 算法的加密后结果是唯一的，即没有 重复。 为了加强算法的安全性，r i v e s t 在1 9 9 0 年又开发出m d 4 算法。m d 4 算法同 样需要填补信息以确保信息的字节长度加上4 4 8 后能被5 1 2 整除( 信息字节长 度m o d5 1 2 = 4 4 8 ) 。然后，一个以6 4 位二进制表示的未处理时信息的长度被 添加进来。信息被处理成5 1 2 位d a m g f i r d m e r k l e 迭代结构的区块，而且每个区 块要通过三个不同步骤的处理。d e nb o e r 和b o s s e l a e r s 以及其他人很快发现了 攻击m d 4 版本中第一步和第三步的漏洞。d o b b e r t i n 向大家演示了如何利用一部 普通的个人电脑在几分钟内找到m d 4 完整版本中的冲突( 这个冲突实际上是一 种漏洞，它将导致对不同的内容进行加密却可能得到相同的加密结果) 。毫无 疑问，m d 4 就此被淘汰掉了。 尽管m d 4 算法在安全上有个这么大的漏洞，但它对在其后才。被开发出来的 好几种信息安全加密算法的出现却有着不可忽视的引导作用。除了m d 5 以外， 其中比较有名的还有s h a l 、r i p e - m d 以及h a v a l 等。 1 9 9 1 年，r i v e s t 开发出技术上更为趋近成熟的m d 5 算法。它在m d 4 的基 础上增加了“安全带子 ( s a f e t y b e l t s ) 的概念。虽然m d 5 比m d 4 稍微慢一 些，但却更为安全。这个算法很明显的由四个和m d 4 设计有少许不同的步骤组 成。在m d 5 算法中，信息摘要的大小和填充的必要条件与m d 4 完全相同。 1 2 第二章数字签名中的单向散列函数 2 6 2m d 5 算法的描述 很多专家学者设计过单向散列函数，但其中绝大部分已被破译或部分破译。 如：s n e f r u 算法，被b i h a m 和s h a m i r 利用差分密码分析证明了两轮s n e f r u ( 1 2 8 一 位散列值) 是不安全的【3 】；n - h a s h 算法，已被b i h a m 和s h a m i r 用差分密码破解 了前六轮3 1 1 4 1 ；b i d 4 算法，己被b e r td e nb o e r 和a n t o o nb o s s e l a e r s 对算法三 轮中的后两轮进行了成功的密码分析，并且r a l p hm e r k l e 成功地攻击了前两轮 【5 】，等等。 m d 5 是m d 4 的改进版，它比m d 4 更加复杂，但设计思想相似，也产生1 2 8 - 位散列。为了说明作者改进的算法，在此把m d 5 算法实现作详细介绍，以便于 比较。 m d 5 以5 1 2 - 位分组来处理输入文本，每一分组又划分位1 6 个3 2 - 位子分组。 输出是四个3 2 - 位分组级联组成1 2 8 一位散列值。m d 5 算法可用图2 ：2 表示。 l _ 。! ! ! 丝! 道星丛11 整壅丝! ! 塑：噬! 丝丝! 塑昼篓鏖i 锣j 始向量 图2 2m d 5 算法简易表示 消息摘要 如图2 2 所示，首先填充消息m 使其长度恰为一个比5 1 2 的倍数小6 4 位的 数。其方法是：在消息m 后附加一个l ，后面附加o ，直到其后只剩6 4 位用来 存放消息的长度值，当原消息的长度大于2 6 4 时，消息的长度位km o d2 6 4 。填 充后整个长度是消息m 、填充位和消息长度位之和，它必须是5 1 2 的倍数。同时 可以看出，不同的消息在填充后的信息也必定不同。 填充后的消息长度是5 1 2 的倍数，首先需要对它以5 1 2 位为单位进行消息 分组，b l ，b 2 ，b n 1 ，b n ，因为第i ( 1 9 ) 个压缩函数h m d 5 的输入是前一个 压缩函数的输出和第i 个消息分组b ；，输出是固定长度1 2 8 位，而第一个压缩 1 3 第二章数字签名中的单向散列函数 函数的输入是初始向量和第一个消息分组b 。，最后一个压缩函数的输出就是消 息摘要m d 。 算法运算时需要用到四个3 2 - 位的变量( 称为链接变量) a ，b ，c ，d ，并且每一 个变量按l i t t l e - b i a d e n ( 低位字节在前) 的顺序存放，运算前将其初始化初始向 量i v ： a = 0 x 0 1 2 3 4 5 6 7 b = o x 8 9 a b c d e f c = o x f e d c b a 9 8 d = 0 x 7 6 5 4 3 2 1 0 首先，将运算的初始向量i v 中的a ，b ，c ，d 复制到另外四个变量a ，b ，c ，d 中， 然后进行算法的主循环，循环次数是消息的分组组数。每个主循环有四轮，每 轮相似，只是每轮使用的非线性函数不同而已。如图2 3 所示。 图2 3m d 5 主循环 因为消息是按5 1 2 位分组的，每一轮中的子循环是对消息分组b i 的3 2 位 子分组m i 操作的，所以每一轮要完成消息分组b i 的操作就必须有1 6 次子循环操 作，每次操作是针对上次操作的结果和本次操作的消息子分组。第j ( 1 匀s 1 6 ) 次 操作对a ，b ，c ，d 中的三个作一次非线性函数运算，然后将所得结果加上未作 非线性运算的那个变量、消息分组b i 的一个子分组m j 和一个常数t k = ( 2 3 2 a b s ( s i n ( k ) ) ) ，其中1 蝴，然后将所得的结果左移一个不定位s ，然后加上a ，b ， c ，d 中的一个。最后将所得的结果取代a ，b ，c ，d 中的一个，并进行下一次的 操作。具体操作如图2 4 所示。当该轮的所有子循环( 1 6 次) 结束后，进行下一 轮运算，直到四轮主循环结束，将a ，b ，c ，d 分别加上a ，b ，c ，d ，作为下一消 息分组m i + i 主循环的初始化向量a ，b ，c ，d ，直到所有消息分组运算完毕，得到的 1 4 第二章数字签名中的单向散列函数 输出就是消息摘要。 a | ra | lm ji t tk ll b b x，j r1 i r八夕 c c dd 图2 4m d 5 子循环一次操作 1 - - - 4 轮使用的非线性函数分别是： f ( x ，y ，z ) = ( x y ) v ( ( x ) a z ) g ( x ，y ，z ) = ( x z ) v ( y ( z ) ) h ( x ，y ，z ) = xo yoz i ( x ，y ，z ) = y o ( x v ( z ) ) 其中， 表示按位与；v 表示按位或；表示按位反；o 表示按位异或。 在每一轮的每一次操作时它的左循环的位数不一样，表2 1 所示。 表2 1 子循环中每次左移的位数 步数 1234567891 0l l1 21 31 41 51 6 轮数 171 2 1 72 27 1 21 72 271 21 72 271 2