MDI5算法简介及主要实现.docx

MD5算法简介及其实现Abstract ：With the abroad application of computer technology, more and more people have been depending on the information systems, the research of data encryptiontechnology has been paid more and more attention by people as well. Data security is not only need in the military, political and the diplomatic, but also everywhere in science, technology research and development, trade and so on. Cryptology technique is the core of safeguarding information security, and digital signature is always companioned with Hash functions, which is a kernel of modern Cryptography. MD5 is a typical Hash encryption technique which is quite popular. The paper mainly gives detail discussion of the MD5 encryption algorithms principle and its realization.Keywords：MD5 digital signature摘 要：随着计算机在社会各个领域的广泛应用，人们对信息系统的依赖程度越来越高，数据加密技术的研究也越来越受到人们重视，数据安全保密问题己不仅仅出于军事、政治和外交上的需要，科学技术的研究和发展及商业等方面，无一不与数据安全息息相关。信息产业的核心技术之一就是密码算法，单向散列（Hash）函数是现代密码学的核心，而基于 Hash 函数的 MD5 数据加密算法是目前研究的热点之一。本文主要详细的论述了 MD5 算法的基本原理、应用实现,并提供了主要代码。关键字： MD5 数字签名1. MD5 算法简介MD5的全称是 Message-Digest algorithm 5（信息-摘要算法），MD5是一种不可逆的法，即对生成的密文求逆，对应着无穷个可逆。在 90 年代初由 MIT Laboratory for Computer Science（IT 计算机科学实验室）和 RSA Data Security Inc（RSA 数据安全公司）的 Ronald L. Rivest 开发出来，经 MD2、MD3 和MD4 发展而来。它的作用是让大容量信息在用数字签名软件签署私人密钥前被“压缩”成一种保密的格式（就是把一个任意长度的字节串变换成一定长的大整数）。不管是 MD2、MD4 还是MD5，它们都需要获得一个随机长度的信息，并产生一个128位的信息摘要。虽然这些算法的结构或多或少有些相似，但是MD2的设计与MD4 和MD5 完全不同，是因为MD2 是为 8 位机器做过设计优化的，而 MD4 和MD5 却是面向 32 位的电脑。这三个算法的描述和C语言源代码在 internet rfcs 1321 中有详细的描述，这是一份最具权威的文档，由 Ronald L. Rivest 在 1992 年 8 月向 IEFT 提交。Rivest在 1989 年开发出 MD2 算法，在这个算法中，首先对信息进行数据补位，使信息的字节长度是 16 的倍数，然后，以一个 16 位的检验和追加到信息末尾，并且根据这个新产生的信息计算出散列值。后来，Rogier和Chauvaud 发现如果忽略了检验和将产生MD2冲突。MD2算法的加密后结果是唯一的-即没有重复的。为了加强算法的安全性，Rivest在1990年又开发出MD4算法。MD4算法同样需要填补信息以确保信息的字节长度加上448后能被512 整除（信息字节长度mod512 = 448）。然后，一个以64位二进制表示的信息的最初长度被添加进来。信息被处51位迭代结构的区块，而且每个区块要通过三个不同步骤的处理。Den Boer和Bosselaers 以及其他人很快的发现了攻击MD4版本中第一步和第三步的漏洞。Dobbertin 向大家演示了如何利用一部普通的个人电脑在几分钟内找到MD4完整版中的冲突（这个冲突实际上是一种漏洞，它将导致对不同的内容进行加密却可能得到相同的加密后果）。毫无疑问，MD4就此被淘汰掉了。尽管MD4算法在安全上有个这么大的漏洞，但它对在其后才被开发出来的好几种信息安全加密算法的出现却有着不可忽视的引导作用。除MD5以外，其中比较有名的还有 SHA-1、Snefru 以及Haval等。一年以后，即1991年，Rivest开发出技术上更为趋近成熟的MD5算法。它在MD4的基础上增加了安全-带子（safety-belts）的概念。虽然 MD5比MD4 稍微慢一些，但却更为安全。这个算法很明显的由四个和MD4设计有少许不同的步骤组成。在MD5算法中，信息-摘要的大小和填充的必要条件与MD4完全相同。Den Boer 和 Bosselaers曾发现MD5算法中的假冲突（pseudo - collisions），但除此之外就没有其他被发现的加密后结果了。Van Oorschot 和 Wiener 曾经考虑过一个在散列中暴力搜寻冲突函数（brute-force hash function），而且他们猜测一个被设计专门用来搜索MD5 冲突的机器（这台机器在 1994 年的制造成本大约是一百万美元）可以平均每24天就找到一个冲突。2. MD5用途MD5用途： 1、防止被篡改： 1）比如发送一个电子文档，发送前，我先得到MD5的输出结果a。然后在对方收到电子文档后，对方也得到一个MD5的输出结果b。如果a与b一样就代表中 途未被篡改。2）比如我提供文件下载，为了防止不法分子在安装程序中添加木马，我可以在网站上公布由安装文件得到的MD5输出结果。3）SVN在检测文件 是否在CheckOut后被修改过，也是用到了MD5。 2、防止直接看到明文：现在很多网站在数据库存储用户的密码的时候都是存储用户密码的MD5值。这样就算不法分子得到数据库的用户密码的MD5值，也无法知道用户的密码(其实这 样是不安全的，后面我会提到)。（比如在UNIX系统中用户的密码就是以MD5（或其它类似的算法）经加密后存储在文件系统中。当用户登录的时候，系统把 用户输入的密码计算成MD5值，然后再去和保存在文件系统中的MD5值进行比较，进而确定输入的密码是否正确。通过这样的步骤，系统在并不知道用户密码的 明码的情况下就可以确定用户登录系统的合法性。这不但可以避免用户的密码被具有系统管理员权限的用户知道，而且还在一定程度上增加了密码被破解的难度。） 3、防止抵赖（数字签名）：这需要一个第三方认证机构。例如A写了一个文件，认证机构对此文件用MD5算法产生摘要信息并做好记录。若以后A说这文件不是他写的，权威机构只需对此文 件重新产生摘要信息，然后跟记录在册的摘要信息进行比对，相同的话，就证明是A写的了。这就是所谓的“数字签名”。3 . MD5算法的基本原理MD5算法以512 位分组来处理输入文本，每一分组又划分为16个32位子分组。算法的输出由4个32 位分组组成，将它们级联形成一个 128 位散列值。 第 1 步：填充 MD5 的第 1 步是在原消息中增加填充位，目的是使原消息长度等于一个值，即比 512 的倍数少 64 位。例如，如果原消息长度为 1000 位，则要填充 472 位，使消息长度为 1472 位，因为 64+1472=1536，是 512 的倍数（1536=512*3）。 这样，填充后，原消息的长度为 448 位（比 512 少 64），960 位（比 1024少 64 位），1472 位（比 1536 少 64 位），等等，如下图 2-1 所示。 原始消息 填充（1-512位） 原始消息 填充图 2-1填充过程填充对用一个 1 位和多个0位。注意填充总是增加，即使消息长度已经是比 512 的倍数少64。因此，如果消息长度已经是448，则要填充512位，使长度变成960位。因此，填充长度为1512 的值。填充对用一个 1 位和多个 0 位。注意填充总是增加，即使消息长度已经是比512的倍数少64。因此，如果消息长度已经是 448，则要填充 512 位，使长度变成 960 位。因此，填充长度为 1512 的值。 第 2 步：添加长度 增加填充位后，下一步要计算消息原长，将其加进填充后的消息末尾。先计算消息长度，不包括填充位（即增加填充位前的长度）。例如，如果原消息1000位，则填充472 位，使其变成比 512 的倍数（1536）少 64 位，但长度为 1000，而不是 1472。 这个消息原长表示为 64 位值，添加到加进填充后的消息末尾。如果消息长度超过 264 位（即 64 位无法表示，因为消息太长），则只用长度的低 64 位，即等于计算 length mod 264。 可以看到，这时消息长度为 512 的倍数，成为要散列的消息。如图 2-2 所示。 长度原始消息 填充（可选） 长度 64位 要散列的数据（摘要）+原始消息 填充（可选）图2-2 添加长度第 3 步：将输入分成 512 位的块。 下面要将输入分成 512 的块，如图 2-3 所示。块1 块2 块3 . . 块n 512位 512位 512位 512位 512位要散列的数据（已摘要）图2-3将数据分成512块第4步：初始化链接变量第4步要初始化四个链接变量，分别称为A，B，C，D，它们都是32位的数字，这些链接变量的初始十六进制值如表 2-1 所示，低位的字节在前面。 表 2-1链接变量A十六进制01234567B十六进制89ABCDEFC十六进制FEDCBA98D十六进制76543210注意低位的字节在前面指的是Little Endian 平台上内存中字节的排列方式，而在程序书写时，要写成： A=0x01234567B=0x89abcdefC=0xfedcba98D=0x7654321 第5步：处理块 初始化之后，就要开始实际算法了。这是个循环，对消息中的多个512位块行。 5.1 步：将四个链接变量复制到四个变量 a，b，c，d 中，使a=A，b=B，c=C,d=D，如图 2-4所示。实际上，这个算法将 a，b，c，d 组合成 128 位寄存器（abcd），寄存器（abcd）在实际算法运算中保存中间结果和最终结果，如图 2-5所示实际上，这个算法将 a，b，c，d 组合成128位寄存器（abcd），寄存器（abcd）在实际算法运算中保存中间结果和最终结果，如图 2-5 所示）ABCDabcd图 2-4 将四个链接变量复制到四个变量中abcd a b c d 抽象视图 内部视图图 2-5 链接变量抽象视图5.2步：将当前512位块分解为16个子块，每个子块为32位32位 32位 . 32位 块1（512位）子块1 子块2子块16 图 2-6 将当前 512 块分解为 16 个字块 5.3 步：主循环有四轮，每轮很相似。每一轮进行 6 次操作，处理一个块中的16个子块。每一轮的输入如下：（a）16 个子块；（b）变量 a，b，c，d；（c）常量 t，如图 2-7 和 2-8 所示。这四轮中的第 1 步进行不同处理，其他步骤是相同的。 每一轮有16个输入子块 M0，M1，.，M15，或表示为 Mi，其中i为115。每个子块为32位。 t 是个常量数组，包含64个元素，每个元素为32位。把数组t的元素表示为t1，t2，.，t64，或 ti，其中 i 为 164。由于有四轮，因此每一轮用64个t 值中的16个。16个子块其他常量t一轮 a b c d 图 2-7 每一轮处理ABCD 消息分组 第4轮 第2轮 第1轮 第3轮图 2-8 MD5主循环以下是每次操作中用到的四个线性函数（每轮一个），简单的说，就是布尔运算。 F(x,y,z) = (x&y)|(x)&z) G(x,y,z) = (x&z)|(y&(z) H(x,y,z) = xyz I (x,y,z) = y(x|(z) （&是与，|是或，是非，是异或）这些函数是这样设计的：如果x，y 和 z 的对应位是独立和均匀的，那么结果的每一位也是独立和均匀的，函数 F 是按逐位方式操作；如果X，那么Y，否则 Z，函数 H 是逐位奇偶操作。设 Mi表示消息的第 i 个子分组（从 0 到 15），S 表示循环左移S位，则四种操作为：FF(a,b,c,d,Mi,s,ti) 表示 a=b+(a+(F(b,c,d)+ Mi+ ti)s)GG(a,b,