MD5消息摘要算法实现及改进.doc

图 1 MD5 消息摘要算法传统运算流程图 2 改进后的 MD5 算法流程2012-07-19#2012刘-俊0辉7-19#2#0#12-07-19#( 中国工商银行泉州市分行福建 泉州362000 )【摘 要】: MD5 消息摘要算法通过对一个任意长度的消息进行处理产生一个固定长度的 消息摘要 , 可利用该 消息摘要 进行数字签名和密码加密。本文在传统算法流程的基础上作了进一步的改进, 提高了该算法的运算效率。【关键字】:MD5 算法, 消息摘要, 实现与改进1. MD5 算法简介MD5 消息摘要算法由麻省理工学院( MIT) 计算机科学实验 室的 R.Rivest 提出, 被互 联 网 电 子 邮 件 保 密 协 议 ( PEM) 指 定 为消息压缩值算法之一, 用于数字签名前对消息进行安全的压缩;且为不可逆算法。2. MD5 算法描述MD5 算法是以任意长度的消息作为输入, 输出一个长度固 定为 128bit 的消息摘要, 其传统运算流程见图 1。MD5Operation(M, Context); End;3.1 参数的定义与初始化鉴于对 MD5 算法的运算流程做了改进。因此, 有必要先对 运算中所用到的一系列参数进行数据结构的定义和初始化。3.1.1 定义参数我们定义一个名为 MD5Content 的数据类型。MD5Content = Record ChaVar:MD5ChaVar; Len: MD5Len;Buffer: MD5Buffer;End;其中,MD5ChaVar 为含有 4 个元素的 DWORD 数组,分别表示四个链接变量; MD5Len 由 2 个 DWORD 元素组成, 共 64位, 用于存放消息长度; MD5Buffer 为含有 64 个元素的 BYTE 数 组, 共 512 位, 存放当前待处理的报文分组内容。3.1.2 初始化参数MD5ParaReady 函数用于初始化所有的参数, 它包含了传统 流程中附加填充比特、附加消息长度和初始化 MD 缓存区三个步骤中的部分操作。关键代码如下:Procedure MD5ParaReady(Var Context: MD5Content) BeginWith Context doBegin/对链接变量赋值,InitChaVar($67452301,$efcdab89, $98badcfe, $10325476);/初始化 64 位的消息长度Len0 := 0; Len1 := 0;/ 将分组存储区的内容全部清零ZeroMemory(Buffer, SizeOf(MD5Buffer); End;End;3.2 划分、处理报文分组MD5Operation 函数主要根据消息长度的不同进行报文分组 的划分和逻辑处理。伪代码如下:MD5Operation(M:String; Context:MD5Content);/M 为初始消息Begin/ 两种情况If Length(M)=64 thenBeginPreTreatment(M, Context); GroupDisposal(Context.Buffer, Context.ChaVar); End;/ 两种情况ElseBeginCycleDisposal(M, Context); PreTreatment(M, Context);GroupDisposal(Context.Buffer, Context.ChaVar); End;/输出消息摘要GetMD();3. MD5 算法实现及改进由图 1 可知,传统的算法运算流程是先对初始消息进行预处理( 使其长度变为 512bit 的整数倍) , 再进行报文分组的划分和逻辑处理。而本文对此作了改进, 具体流程如图 2 所示。首先 根据初始消息长度的不同将其分为: 初始长度512bit, 且初 始长 度448bit; 初 始 长 度512bit, 且 448bit512bit, 且剩余消息( 初始消息在划分、处理 完所有满足分组条件后的剩余部分) 的长度448bit; 初始长 度512bit, 且 448bit剩余消息长度512bit 四种情况。若为初始消息的长度小于等于一个分组长度的情况,消息进行填充和分组运算 ( 包 括分组的划分和逻辑处理) ; 若直接对初始为情况则有所不同,首先运用循环结构不断地将初始消息中满足分组划分条件的内容 拷 贝 到 一 个 事 先 定 义 好 的512bit 大的分组存储区中进行分组的逻辑处理,然后对剩余消 息 进 行 填 充 和 分 组 划 分 , 并将前面处理所得到的中间变量代入分组进行运算,最后得到128bit 消息摘要的输出。同时,在编程实现时, 将大量的计算和查找操作直接用相应值代替。这样既避免占用过多的系统资源, 又大大降低了算法的运算强度,度。改进后算法的伪代码如下:MD5EncryptString(M: String) Var同时提高了算法的运行速Context: MD5Content;End;2012-0Be7gin-19#2012-07-上1述9伪#代码#中#的#P#re#T2re#a0tm#1ent2、G-rou0pD7isp-os1al、9Cy#cle#Di#spo#sal#/初始化参数图 3 MD5 报文分组逻辑处理表 1 基本函数变换表循环函数构成, 每个循环函数运算 16 次, 共 64 次。下面为 FF 函数为例进行介绍( 其余的三个循环函数与此类似) 。Procedure FF (Var A: DWORD; BB, CC, DD, Mj: DWORD; Si: BYTE; Ti: DWORD); BeginInc(A, F(BB, CC, DD) + Mj + Ti);LeftRot(A, Si); Inc(A, BB); End;其中, F 为四个基本函数(输入 3 个 32bit, 产生 1 个 32bit 的输出)之一, 其变换情况见表 1。Mj表示消息的第 j 个子分组; S i表示参数循环左移的位数; Ti值由式子 生成, 这样做是为了 通过正弦函数和幂函数来进一步消除变换中的线性; LeftRot 函 数的作用是将 32 位的参数 A 循环左移 Si 位。始消息, 也可能是剩余消息) 长度的不同进行预处理。伪代码如下:Function PreTreatment( M:String, Context: MD5Content)BeginIf Length(M)56) and (Length(M)=64) thenBegin/填充当前分组CopyMemory(Context.Buffer0, pChar(M)0, Length(M); CopyMemory(Context.BufferLength(M),Padding,64- Length(M);/由于只定义了一个 512bit 大的分组存储区,后再将四个中间变量代入下一个分组。故需先对当前分组进行处理GroupDisposal(Context.Buffer, Context.ChaVar);在具体实现时, 为了提高算法的运行速度和降低运算强度,不再进行 Mj、Ti和 Si的计算、查找和替换, 而是直 接 将 相 应 的值代入函数中。3.2.3 分组循环处理函数CycleDisposal 函数用于 当 消 息 长 度 大 于 一 个 分 组 长 度 时 ,对消息不断地进行分组的划分和逻辑处理。CycleDisposal( M:String;Context:MD5Content)Begin/Count, 记录当前处理到消息 M 的哪个位置Count:=0;/不断地将消息拷贝入分组存储区并处理While Count + 63 Length(M) doBeginCopyMemory(Context.Buffer0, pChar(M)Count, 64); GroupDisposal(Context.Buffer0, Context.ChaVar); Inc(Count, 64);End; End;4. MD5 安全性分析MD5 算法不基于任何的假设和密码体制, 采用直接构造方 法, 以 32 位字为基本运算单元, 非常实用且应用广泛。尽管王小 云教授找出了 MD5 的缺 陷 , 但 分 析 其 机 制 , 我 们 得 知 : MD5没被破解, 找到的只是 MD5 的碰撞, 无法逆推得到明文, 但却可 以伪造身份; MD5 碰撞的发现, 仅对随机内容产生影响, 而对 有特殊意义或者格式的内容仍是安全的。/对 新 增 的 分 组 进 行 填 充 和 附 加 长 度0, Padding64- Length(M), 56); CopyMemory(Context.Buffer56, Context.Len, 8);End;End;3.2.2 报文分组逻辑处理函数GroupDisposal 函数用于对每个报文分组进行逻辑处理, 具 体流程见图 3。其中, AA, BB, CC, DD 为处理过程中所用到的中 间变量,分别被赋予 ChaVar03的值。CopyMemory(Context.Buffer伪代码如下:Procedure GroupDisposal(Buffer: Pointer; Var ChaVar: MD5ChaVar); VarAA, BB, CC, DD: DWORD;/定义四个中间变量Begin/ Evaluate 函数将四个链接变量分别赋值给四个中间变量Evaluate(AA,BB,CC,DD, ChaVar0,ChaVar1,ChaVar2,ChaVar3); MainLoop(AA、BB、CC、DD);/将得到的中间变量赋值给链接变量Evaluate(ChaVar0,ChaVar1,ChaVar2,ChaVar3,AA,BB,CC,DD);!( 上接第 117 页)的热点。数据库上的关键词检索标志着数据库与 IR 的结合, 用IEEE Press, 2003. 633- 644.4. G. Halotia, A. Hulgeri, C. N akhey, S. Chakrabarti, S. Sudar- shan. Key- word searching and browsing in databases using BAN KS. In: Proc. of the18th ICDE. San Jose: IEEE Press, 2002. 431- 440.5. S. Agrawal, S. Chaudhuri, G. Das. DBXplorer: a system for keyword - based search over relational databases. In: Proc. of the 18th ICDE. San Jose: IEEE Press, 2002. 5- 16.6. V. Hristidis, Y. Papakonstantinou. DISCO VER : keyword search in rela- tional databases. In: Proc. of the 28th VLDB. Hong Kong: Morgan Kauf- mann Publishers, 2002. 670- 681.7. C. Palmer, J. Steffan. Generating network topologies that obey power law. In: Proc. of GLO BECO M. San Francisco: IEEE Press, 2000. 434 -438.户查询数据库不再需要关心数据库的模式结构,只需要输入一组关键词, 就能获得与查询相关的元组连接树。基于关系数据库上的关键词检索,我们提出了一种 P2P 环境下共享数据库的新框 架 , 大 大 简 化 了 不 同 节 点 之 间 的 数 据 库 模 式 映 射 。 接 着 将Top- k 查询扩展到 P2P 环境下的数据管理系统上,数据库的查询统一起来, 提供统一的查询接口。 参考文献:将文档集和1. S. Gribble, A. Halevy, et al. What Can Database Do for Peer- to - Peer?In: Proc. of the 4th WebDB. Santa Barbara, 2001. 31- 36.2. A. Halevy, Z. Ives, D. Suciu, and I. Tatarinov. Schema mediation in peer data management systems. In: Proc. of the 19th ICDE. Bangalore: IEEE Press, 2003. 505- 518.3. W. S. N g, B. C. O oi, K. L. Tan, and A. Zhou. PeerDB: A P2P- based system for distributed data sharing. In: Proc. of the 19th ICDE. Bangalore:Your request c