散列算法(也叫摘要算法)

浅析散列函数MD5算法的原理及其碰撞攻击摘要随着网络技术的广泛应用，网络信息安全越来越引起人们的重视。

针对数据在存储时存在大量的安全问题，目前通常将需要存储的数据进行加密然后再存储，应用MD5算法是一个不错的选择。

本文详细介绍了MD5算法的概念，对MD5算法的原理、碰撞攻击以及MD5算法破解的重要意义进行探讨。

关键字：MD5 原理碰撞攻击一、引言现阶段，信息安全性已成为全社会共同关心的问题，密码学研究也越来越被人们所关注。

密码学主要研究的是通讯保密。

近年来，密码学研究之所以十分活跃，主要原因是它与计算机科学的蓬勃发展息息相关。

由于公共和私人的一些机构越来越多的应用电子数据处理，将数据存储在数据库中，因此防止非法泄露、删除、修改等是必须重视的问题。

对数据进行加密能够防止他人盗取需要保密的信息，但这只解决了一方面的问题，至于如何防止他人对重要数据进行破坏，如何确定交易者的身份，以及如何防止日后发生纠纷时交易者抵赖，还需要采取其它的手段，这一手段就是数字签名。

数字签名技术实际上是在数据加密技术基础上的一种延伸的应用。

数字签名经常和单向散列(Hash)函数一起使用，而单向散列(Hash)函数是现代密码学的核心。

最常见的散列算法有MD5，SHA和Snefru，MD5是当今非常流行的Hash 加密技术，因而本文选取MD5作为研究对象，详细介绍了MD5算法的概念，对MD5算法的原理、碰撞攻击以及MD5算法破解的重要意义进行探讨。

二、MD5算法的概念MD5的全称是Message -Digest Algorthm 5(信息--摘要算法), 即将任意长度的“字节串”变换成一个128bit的大整数, 是一种不可逆的字符串变换算法。

通过数学运算,把不同长度的信息转化到128位编码中,形成Hash值, 通过比较该数值是否正确,来确定通信双方的合法性, 即数字签名功能。

在数据传输后, 可以通过比较Hash值来判断信息途中是否被截获修改, 是否由合法的发送人发送或者合法的接收人接收等。

数字签名算法-RSA、DSA、ECDSA、ECDH数字签名算法介绍和区别原⽂阅读：数字签名是⼀个带有密钥的消息摘要算法，这个密钥包括了公钥和私钥，⽤于验证数据完整性、认证数据来源和抗否认，遵循OSI参考模型、私钥签名和公钥验证。

也是⾮对称加密算法和消息摘要算法的结合体，常见的数字签名算法主要有RSA、DSA、ECDSA三种，本⽂对数字签名算法进⾏详细介绍。

Hash⼜译散列、摘要等名，本⽂统⼀称Hash。

1. RSA数字签名算法RSA是⽬前计算机密码学中最经典算法，也是⽬前为⽌使⽤最⼴泛的数字签名算法，RSA数字签名算法的密钥实现与RSA的加密算法是⼀样的，算法的名称都叫RSA。

密钥的产⽣和转换都是⼀样的，包括在售的所有SSL数字证书、代码签名证书、⽂档签名以及邮件签名⼤多都采⽤RSA算法进⾏加密。

RSA数字签名算法主要包括MD和SHA两种算法，例如我们熟知的MD5和SHA-256即是这两种算法中的⼀类，具体如下表格分布1.1. MD2、MD4、MD5算法最常见的是我们熟知的MD5加密算法，MD5全称Message-Digest Algorithm 5（信息-摘要算法 5），⽬前⽐较普遍的Hash算法，是散列算法的基础原理，MD5的前⾝有MD2、MD3和MD4。

MD5算法法是输⼊任意长度字符，输出固定长度128位的算法。

经过程序流程，⽣成四个32位数据，最后联合起来成为⼀个128位Hash值，主要⽅式是通过求余、取余、调整长度、与链接变量进⾏循环运算进⽽得出结果。

1.2. SHA-1算法SHA-1是由NIST NSA设计为同DSA⼀起使⽤的，SHA-1设计时基于和MD4相同原理，并且模仿了该算法，SHA-1抗穷举(brute-force)性更好，它产出160位的Hash值，对于⾮线性运算、移位和加法运算也与MD5类似。

SHA-1也应⽤于包括TLS和SSL、PGP、SSH、S/MIME和IPsec等多种协议中，曾被视为是MD5的后继者。

MD5和Hash
不⽌⼀次有⼈问我与MD5的区别以及如何选择使⽤，今天有⼈问我了，其实这⽅⾯我懂的也不太多，基础的还是了解⼀些的，把我知道的记⼀下吧。

MD5和Hash的区别
⾸先，MD5与hash都是单向加密的算法，可以把⼀些信息进⾏单向加密成固定长度的散列码。

（hash算法即常说的散列算法，也被⼈翻译成哈希）其次，MD5也是hash算法的⼀种，常见的hash算法还有sha1,sha2等
MD5也被称为信息摘要算法，由于其算法复杂不够，容易被暴⼒破解的。

SHA1算法也存在和MD5⼀样的问题。

还有SHA2、SHA256、SHA512等，这些算法的复杂度相对要⾼，但是依然是可被破解的只是破解成本被增加了，但是⼀些常⽤的⽂本信息（⽐如密码）的散列码被⼀些专业⼚端记录下来了，还是容易被破解的，怎么办呢？加个密码盐呗，这样的话暴⼒破解⼏乎是搞不定了，即使搞定了可能也因为过去太久时间⽽变的没有价值
常⽤的密码攻击⽅式
常⽤的密码攻击⽅式有字典攻击、暴⼒破解、查表法、反向查表法、彩虹表等。

暴⼒破解：按照⼀定的顺序⼀个⼀个的去试
字典攻击：把常⽤的密码做成字典，破解时先看字典⾥是否存在，有效加快破解速度
查表法：使⽤⼀个⼤型字典，把每个p和对应的q都记录下来，按q做⼀下索引，直接查找匹配。

彩虹表：对于HASH的传统做法是把H(X)的所有输出穷举，查找H(X[y])H§，得出PX[y]。

⽽彩虹表则是使⽤散列链的⽅式进⾏。

说明：
"散列链"是为了降低传统做法空间要求的技术，想法是定义⼀个衰减函数 R 把散列值变换成另⼀字符串。

通过交替运算H函数和R函数，形成交替的密码和散列值链条。

TLS参数术语介绍TLS（Transport Layer Security）是一种用于保护网络通信的协议，它在传输层上提供了安全的数据传输。

TLS使用了多种加密算法和安全机制来确保通信的保密性、完整性和身份验证。

在TLS中有一些重要的参数和术语，下面将对这些参数和术语进行介绍。

1. 密码套件（Cipher Suite）密码套件是指TLS使用的加密算法和密钥交换算法的集合。

一个密码套件通常包括对称加密算法、散列算法、密钥交换算法和数字签名算法等。

在TLS握手过程中，客户端和服务器会协商选择一个适合双方的密码套件进行通信。

2. 对称加密算法（Symmetric Encryption Algorithm）对称加密算法是指在加密和解密时使用相同的密钥的算法。

在TLS中常用的对称加密算法有AES（Advanced Encryption Standard）、3DES （Triple Data Encryption Algorithm）和RC4（Rivest Cipher 4）等。

3. 散列算法（Hash Algorithm）散列算法是将任意长度的数据映射到一个固定长度的结果的算法。

在TLS中，散列算法用于计算消息摘要，以确保数据的完整性和一致性。

常用的散列算法有MD5（Message Digest Algorithm 5）和SHA（Secure Hash Algorithm）等。

4. 密钥交换算法（Key Exchange Algorithm）密钥交换算法是用于在通信双方之间安全地传递秘密密钥的算法。

在TLS中，密钥交换算法可以分为两种类型：非对称密钥交换算法和对称密钥交换算法。

常用的非对称密钥交换算法有RSA（Rivest-Shamir-Adleman）和Diffie-Hellman等，而常用的对称密钥交换算法有Pre-Shared Key（PSK）和Elliptic Curve Cryptography（ECC）等。

SHA1算法原理SHA-1（Secure Hash Algorithm 1）是一种密码学安全散列算法，用于为消息生成一个160位的哈希值（也称为摘要）。

它是公认的替代品MD5算法的一种选择。

SHA-1使用了一系列的逻辑运算和位操作，将输入消息不论其长度多长，都转换为一个固定长度的哈希值。

这个过程包括以下几个步骤。

1.数据填充：SHA-1算法首先将输入消息进行填充，使其长度能够被512位整除。

填充方式为在消息末尾添加1位"1"，接着填充0直到消息长度满足要求。

2.填充长度：SHA-1算法还需要将原始消息长度添加到填充后的消息末尾，以确保消息的完整性。

原始消息的长度是以二进制形式表示的。

通常情况下，这个长度值是64位的。

3.初始化变量：SHA-1算法使用了一个160位的初始化变量数组，也被称为缓冲区。

这个数组被SHA-1算法设计为预定义的常量。

4.消息分块：填充后的消息将被分成固定长度的512位块。

每个块会按顺序被处理。

5.压缩函数：SHA-1算法中的压缩函数是算法的核心部分。

它将每个块和当前的缓冲区作为输入，并经过一系列的逻辑运算和位操作，产生一个新的缓冲区。

6.迭代：SHA-1算法会迭代地处理每个块，依次将其与当前的缓冲区作为输入，生成新的缓冲区。

这个过程会不断重复，直到所有的块都被处理完毕。

7.输出：SHA-1算法的最终输出是压缩函数最后一个迭代得到的缓冲区。

这个缓冲区会被转换为一个160位的哈希值，作为算法的输出。

SHA-1算法的核心思想是将一个任意长度的消息映射为一个固定长度的哈希值，使得任意较小的输入变化都会导致输出哈希值的变化。

这样可以确保消息的完整性和不可逆性。

然而，由于SHA-1算法的安全性有所不足，它已被广泛认为是不安全的。

随着计算能力的提高和密码学攻击技术的发展，SHA-1算法存在被暴力破解和碰撞攻击的风险。

因此，现在通常建议使用更强大的哈希算法，如SHA-256、SHA-384或SHA-512，以提供更高的安全性。

数据摘要算法介绍(SHA、MD5和CRC32)一、数据摘要算法概述数据摘要算法是密码学算法中非常重要的一个分支，它通过对所有数据提取指纹信息以实现数据签名、数据完整性校验等功能，由于其不可逆性，有时候会被用做敏感信息的加密。

数据摘要算法也被称为哈希（Hash）算法或散列算法。

常用的数据摘要算法主要以下几大类：1、CRC8、CRC16、CRC32CRC（Cyclic RedundancyCheck，循环冗余校验）算法出现时间较长，应用也十分广泛，尤其是通讯领域，现在应用最多的就是 CRC32算法，它产生一个4字节（32位）的校验值，一般是以8位十六进制数，如FA 12 CD45等。

CRC算法的优点在于简便、速度快，严格的来说，CRC更应该被称为数据校验算法，但其功能与数据摘要算法类似，因此也作为测试的可选算法。

在 WinRAR、WinZIP 等软件中，也是以 CRC32 作为文件校验算法的。

一般常见的简单文件校验（Simple FileVerify – SFV）也是以CRC32算法为基础，它通过生成一个后缀名为 .SFV 的文本文件，这样可以任何时候可以将文件内容CRC32运算的结果与 .SFV 文件中的值对比来确定此文件的完整性。

与 SFV 相关工具软件有很多，如MagicSFV、MooSFV等。

2、MD2 、MD4、MD5这是应用非常广泛的一个算法家族，尤其是 MD5（Message-Digest Algorithm5，消息摘要算法版本5），它由MD2、MD3、MD4发展而来，由RonRivest（RSA公司）在1992年提出，目前被广泛应用于数据完整性校验、数据（消息）摘要、数据加密等。

MD2、MD4、MD5都产生16字节（128位）的校验值，一般用32位十六进制数表示。

MD2的算法较慢但相对安全，MD4速度很快，但安全性下降，MD5比MD4更安全、速度更快。

目前在互联网上进行大文件传输时，都要得用MD5算法产生一个与文件匹配的、存储MD5值的文本文件（后缀名为.md5或.md5sum），这样接收者在接收到文件后，就可以利用与 SFV类似的方法来检查文件完整性，目前绝大多数大型软件公司或开源组织都是以这种方式来校验数据完整性，而且部分操作系统也使用此算法来对用户密码进行加密，另外，它也是目前计算机犯罪中数据取证的最常用算法。

生成数字摘要的常用数学算法
数字信息摘要常见算法
编解码算法
1.Hex编码
将二进制数据按16进制转换为字符串，1字节=2个字符，编码后体积为2倍。

2.Base64
由MIME规范定义的编码算法，其将3个字节(24位)编码为4个字符。

字符集包括64个，可表示6二进制位的数据，因此一个字符对应一组6bit的数据。

编码后体积约为4/3倍，针对不足位数用=补齐。

HASH算法
通常也称散列算法，是一种将任意长度的消息变成固定长度的消息摘要算法，不可逆；
1.MD5
Message Digest Algorithm 5，流行度极高，但目前被发现存在碰撞冲突风险；
任意长度输出为128bit=16字节摘要
2.SHA1
SHA指Security Hash Algorithm，由美国国家安全局NSA设计的安全散列算法系列；
SHA1输出长度为160bit=20字节摘要
3.SHA256
继SHA1出现的算法(属于SHA-2类)，安全性较SHA1更高；
SHA256输出长度为256bit=32字节摘要。

MAC算法
Message Authentication Code，消息认证码算法，基于HASH算法之上，增加了密钥的支持以提高安全性。

具体算法包括HmacMD5/HmacSHA1/HmacSHA256等，输入包括数据及密钥，输出长度与HASH算法一致。

密钥可以是任意长度的数据。

散列函数、消息摘要与数字签名⼀，散列函数（Hash function）散列函数：任何⼀种能将任意⼤⼩数据映射为固定⼤⼩数据的函数，都能被称为散列函数。

散列函数的返回值称为散列值、散列码，摘要或者简单散列。

也就是说散列函数能将任意长度的输⼊变换成固定长度的输出，该输出就是散列值。

散列值空间通常远⼩于输⼊的空间。

散列函数的⼀些特性：消息的长度不受限制确定性：对于相同的输⼊（根据同⼀函数），它必须始终⽣成相同的散列值，如果两个散列值是不相同的，那么这两个散列值的原始输⼊也是不相同的，但是对于不同的输⼊可能会散列成相同的输出（哈希碰撞），所以不可能从散列值来确定唯⼀的输⼊值。

均匀性：良好的散列函数应该输⼊尽可能均匀的映射到输出范围上。

单向性：在加密应⽤程序中，通常期望散列函数实际上是不可逆的。

⼆，散列函数的应⽤1. 散列表散列函数通常与散列表（hash table）结合使⽤，使⽤散列表能够快速的按照关键字查找数据记录。

具体地，散列函数会先将关键字映射到地址集合中的某⼀个位置，然后通过这个地址来查找数据记录（也就是将关键字通过散列函数转换的地址来查找表中的数据）2. 加密散列函数由于散列函数的多样性，它们经常是专门为某⼀应⽤⽽设计的，⽐如为加密和验证信息完整性⽽设计的散列函数（⼜被称为单向散列函数、杂凑函数或者消息摘要函数），这种散列函数是⼀个“单向”操作：对于给定的散列值，没有实⽤的⽅法可以计算出⼀个原始输⼊，也就是说很难伪造，⽐如 MD5 这种散列函数，被⼴泛⽤作检测⽂件的完整性。

2.1 验证消息的完整性安全hash的⼀个重要应⽤就是验证消息的完整性：发送者将原⽂与摘要⼀起发送给接受者，然后接收者⽤同⼀个hash函数对收到的原⽂产⽣⼀个摘要，与发送者的摘要信息对⽐，如果相同，则说明收到的信息是完整的。

验证流程如下：在上述流程中，信息收发双发在通信前已经商定了具体的散列算法，并且该算法是公开的，如果消息在传递过程中被篡改，则该消息不能与已获得的数字指纹相匹配。

散列函数及其应⽤散列函数 散列，英⽂Hash，也有直接⾳译为“哈希”的，就是把任意长度的输⼊（⼜叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。

这种转换是⼀种压缩映射，也就是，散列值的空间通常远⼩于输⼊的空间，不同的输⼊可能会散列成相同的输出，所以不可能从散列值来确定唯⼀的输⼊值。

简单的说就是⼀种将任意长度的消息压缩到某⼀固定长度的信息摘要的函数。

散列函数的应⽤ 在算法竞赛中，我所接触到的主要有字符串hash⽤于把字符串“索引”为⼀个值，然后对复杂字符串进⾏操作，来加快遍历速度，降低算法复杂度。

把字符串匹配转移到了值匹配。

但是散列函数属于⼀种“概率型算法”，对于模的取值有⼀定概率出现碰撞。

所以在算法竞赛中不常使⽤，或者要多次测验避免碰撞。

在信息安全⽅⾯的应⽤主要体现在以下的3个⽅⾯： 1）⽂件校验 我们⽐较熟悉的校验算法有奇偶校验和CRC校验，这2种校验并没有抗数据篡改的能⼒，它们⼀定程度上能检测并纠正数据传输中的信道误码，但却不能防⽌对数据的恶意破坏。

MD5 Hash算法的"数字指纹"特性，使它成为⽬前应⽤最⼴泛的⼀种⽂件完整性校验和（Checksum）算法，不少Unix系统有提供计算md5 checksum的命令。

2）数字签名 Hash 算法也是现代密码体系中的⼀个重要组成部分。

由于⾮对称算法的运算速度较慢，所以在数字签名协议中，单向散列函数扮演了⼀个重要的⾓⾊。

对 Hash 值，⼜称"数字摘要"进⾏数字签名，在统计上可以认为与对⽂件本⾝进⾏数字签名是等效的。

⽽且这样的协议还有其他的优点。

3）鉴权协议 如下的鉴权协议⼜被称作"挑战--认证模式：在传输信道是可被侦听，但不可被篡改的情况下，这是⼀种简单⽽安全的⽅法。

散列函数的安全性 两个不同的输⼊，经过哈希算法后，得到了同样的哈希值，就叫做哈希碰撞。