5.1 HASH函数 – lmn

[TOC]
散列函数代表除了对称和非对称加密之外的第三种加密类型，我们可以称之为无密钥加密。hash函数就是把任意长的输入位（或字节）变化成固定长的输出字符串的一种函数。输出字符串的长度称为hash函数的位数。

哈希不能用于发现原始消息的内容或其任何其他特征，但可用于确定消息是否已更改。几乎所有使用的散列函数都是迭代散列函数，“理想的散列函数是从所有可能的输入值得到所可能的有限输出值几何的一个随机映射。”

较好的散列函数例如：SHA-1，SHA-224，SHA-256和SHA-512。

哈希函数指将哈希表中元素的关键键值映射为元素存储位置的函数。散列提供机密性，但不提供完整性。

给定一个消息m，将任意长度的消息m，映射为固定长度的h(m)，h(m)的长度一般为128位到1024位。
hash函数为单向函数，给定消息m可以很容易计算h(m)，但对于给定的x，不能求出满足x=h(m)的m。

https://tse1-mm.cn.bing.net/th/id/R-C.f7b2b7fa8c73124dfb11a0a9df2401a4?rik=HUYDTW%2bSWKyHiw&pid=ImgRaw&r=0

一对碰撞指：给定两个不一样的消息m1和m2，使得h(m1)=h(m2)。
HASH函数具有抗碰撞性，虽然会遇到碰撞，但是遇到的几率非常小。

0x01 散列

散列一般指Hash，是把任意长度的输入（又叫做预映射pre-image）通过散列算法变换成固定长度的输出，该输出就是散列值，这是一种压缩映射。
散列是通过计算哈希值，打乱元素之间原有的关系，使集合中的元素可以按照散列函数进行排列。

根据Wikipedia我们了解到，一个好的散列函数满足两个基本属性：

1. 计算速度非常高效

通常对于任何带有输入 x 的散列函数 h，h(x) 的计算是一个快速运算

2. 尽量减少输出值的重复，均匀分布键

哈希函数将任意长度的数据转换为固定长度。这个过程通常被称为散列数据。
散列比输入数据小得多，因此散列函数有时被称为压缩函数。

由于散列是较大数据的较小表示，因此也称为摘要。
哈希函数功能包括：

1. 将可变长度键转换为固定长度（通常是机器字长或更短）的值，方法是使用 ADD 或 XOR 等保持奇偶校验的运算符按字或其他单位折叠它们。
2. 对密钥的位进行加扰，以使结果值均匀分布在密钥空间中。
3. 将键值映射为小于或等于表大小的键值

0x02 哈希表

哈希表（Hash table，也叫散列表），哈希表中元素是由哈希函数确定，是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

0x03 hash函数构造方法

直接定址法

取关键字或关键字的某个线性函数值为哈希地址。

H(key) = key
H(key) = a·key + b

由于直接定址所得地址集合和关键字集合的大小相同，对于不同的关键字不会发生冲突。但适合査找表较小且连续的情况，在现实应用中，直接定址法虽然简单，但并不太常用。
缺点是，要占用连续地址空间，空间效率低。

乘取整法

首先用关键字key乘上某个常数A(0 < A < 1)，并抽取出key.A的小数部分；然后用m乘以该小数后取整。

该方法最大的优点是m的选取比除余法要求更低。比如，完全可选择它是2的整数次幂。虽然该方法对任何A的值都适用，但对某些值效果会更好。

平方取中法

取关键字平方后的中间几位为哈希地址。

通过平方扩大差别，另外中间几位与乘数的每一位相关，由此产生的散列地址较为均匀。这是一种较常用的构造哈希函数的方法。
[

](https://blog.csdn.net/m0_37925202/article/details/82015731)

除留余数法

取关键字被数p除后所得余数为哈希地址

H(key) = key MOD p (p ≤ m)

这是一种最简单，也最常用的构造哈希函数的方法，它不仅可以对关键字直接取模(MOD)，也可在折迭、平方取中等运算之后取模。在使用除留余数法时，对p的选择很重要。表长为m，p为小于等于p的质数。

随机数法

选择一个随机函数，取关键字的随机函数值为它的哈希地址。

H(key) = random (key)

其中random为随机函数，当关键字长度不等时采用此法构造哈希函数较恰当。

0x04 哈希函数的应用

加密散列函数广泛用于加密货币中以匿名传递交易信息。例如比特币，最原始和最大的加密货币，在其算法中使用了 SHA-256 加密哈希函数。同样，物联网平台 IOTA也有自己的加密哈希函数，称为 Curl。

哈希函数基于其加密属性有两种直接应用。

密码存储

将密码存储在常规文本文件中很危险，因此几乎所有站点都将密码存储为哈希值。

大多数登录进程不是以明文形式存储密码，而是将密码的哈希值存储在文件中。
当用户输入他们的密码时，会对其进行哈希处理，并将结果与存储在公司服务器上的哈希值列表进行比较。

入侵者只能看到密码的哈希值，即使他访问了密码。他既不能使用哈希登录，也不能从哈希值中导出密码，因为哈希函数具有抗原像的特性。

密码文件由格式为 (user_id, h(P)) 的对表组成。

https://www.tutorialspoint.com/cryptography/images/process_of_logon.jpg

数据完整性检查

数据完整性检查是散列函数最常见的应用之一。验证签名是用于验证数字文档或消息的真实性的过程。它用于生成数据文件的校验和，向用户提供有关数据正确性的保证。

满足先决条件的有效数字签名向其接收者提供强有力的证据，证明消息是由已知的发送者创建的，并且消息在传输过程中没有被更改。

https://www.tutorialspoint.com/cryptography/images/data_integrity_check.jpg

0x05 MD5

MD 系列包括散列函数 MD2、MD4、MD5 和 MD6。

MD5消息摘要算法是一种广泛使用的散列函数，可产生128位散列值。尽管 MD5 最初设计为用作加密哈希函数，但已发现它存在大量漏洞。它仍然可以用作校验和来验证数据完整性。

https://tse3-mm.cn.bing.net/th/id/OIP-C.HC6lMvMsKUVz2dP3pA2QYgHaCm?pid=ImgDet&rs=1

MD5 由Ronald Rivest于 1991 年设计，以取代早期的散列函数MD4，在MD4的基础上强化了抗攻击能力，并于 1992 年被指定为 RFC 1321。

任何加密散列函数的一个基本要求是，要找到两个散列到相同值的不同消息在计算上应该是不可行的。但目前MD5的这种碰撞可以在普通计算机上几秒钟内找到。

MD5的安全性

MD5 哈希函数的安全性具有严重问题。
MD5 存在碰撞攻击，可以在几秒钟内在具有 2.6 GHz Pentium 4 处理器的计算机上找到碰撞。此外，还有一种选择前缀冲突攻击，使用现成的计算硬件可以在几秒钟内对具有指定前缀的两个输入产生冲突。截至 2019 年，四分之一广泛使用的内容管理系统仍在使用 MD5 进行密码散列。

MD5的应用

MD5 消息摘要算法已在软件中广泛使用，以确保传输的文件已完好无损。例如，文件服务器通常会为文件提供预先计算的 MD5校验和，以便用户可以将下载文件的校验和与其进行比较。

大多数基于 unix 的操作系统在其分发包中包含 MD5 sum 实用程序；Windows 用户可以使用包含的PowerShell函数“Get-FileHash”，安装 Microsoft 实用程序或使用第三方应用程序。Android ROM 也使用这种类型的校验和。

https://en.wikipedia.org/wiki/File:CPT-Hashing-File-Transmission.svg

0x06 安全散列函数 (SHA)

最初的版本是 SHA-0，一个 160 位的散列函数，由美国国家标准与技术研究院 (NIST) 于 1993 年发布。缺点很少但没有变得很流行。1995 年晚些时候，SHA-1 旨在纠正所谓的 SHA-0 的缺点。

SHA-1 是现有 SHA 哈希函数中使用最广泛的一种。它用于多种广泛使用的应用程序和协议，包括安全套接字层 (SSL) 安全性。

2005 年，发现了一种在实际时间框架内发现 SHA-1 冲突的方法，这使得 SHA-1 长期受到质疑。

SHA-2 系列还有四个 SHA 变体，SHA-224、SHA-256、SHA-384 和 SHA-512，具体取决于其哈希值中的位数。虽然 SHA-2 是一个强大的哈希函数。虽然明显不同，但其基本设计仍然遵循 SHA-1 的设计。

2012 年 10 月，NIST 选择 Keccak 算法作为新的 SHA-3 标准。Keccak 提供了许多好处，例如高效的性能和良好的攻击抵抗力。

0x07 区块链中使用哈希

哈希用于反映区块链的实际状态，以保证区块链的不变性。
每笔交易包括发件人地址、收件人地址、数量时间戳等信息，该数据组合并进入散列函数，该函数产生一个特殊的散列值，称为支付散列或交易 ID。此哈希用于验证是否发生了某个交易，而不是在区块链上，并且可以验证。

区块链的第一个区块被视为区块头，它包含交易信息。通过添加所有交易生成一个新的哈希，每当生成第二个块时，此组合用于生成新块中所有付款的新匹配哈希，以合并块头的哈希。将所有块连接到行后，重复此步骤。并且使用先前的哈希产生新的哈希会产生依赖性。因为如果有人试图更改特定的数据，他们必须修改当前时刻之前的所有数据，这使得一个稳定和永久的区块链。

不同的区块链使用各种散列函数，例如比特币区块链，它使用 SHA-256 散列函数来保护信息。

参考文章：
https://www.tutorialspoint.com/cryptography/cryptography_hash_functions.htm
https://www.jianshu.com/p/07d9b19bb265
https://blog.csdn.net/m0_37925202/article/details/82015731