数据结构之哈希函数

概念:

哈希(hash),也叫做散列、数据摘要等,是一种常见的数据结构。哈希的表的核心概念分为哈希表和哈希函数。

哈希表(hashTable)

哈希表之前讲过,有需要的可以参考:点击打开哈希表

哈希函数

哈希函数就是将某一不定长的对象映射为另一个定长的对象。能够做到这一点的函数有很多,那什么可以作为哈希函数?这里我们首先要明确下什么可以作为哈希函数。

如果两个不同的对象经过哈希函数计算后得到相同的哈希值,则这就是所谓的冲突。冲突会导致很多的异常,说一种极端的情况:如果一个哈希函数的计算记过经常为0,那么它根本无法帮助我们来区分对象,也就不能帮助我们快速查找对象了,也就违反了哈希的作用。

在设计哈希函数的时候我们主要关注两点:

  • 冲突少:很少出现不同的对象函数作用后得到相同的值。
  • 计算快:计算哈希能够快速找到对象。

 Hash函数还有另外的含义。实际中的Hash函数是指把一个大范围映射到一个小范围。把大范围映射到一个小范围的目的往往是为了节省空间,使得数据容易保存。除此以外,Hash函数往往应用于查找上。所以,在考虑使用Hash函数之前,需要明白它的几个限制:

  • Hash的主要原理就是把大范围映射到小范围;所以,你输入的实际值的个数必须和小范围相当或者比它更小。不然冲突就会很多。
  • 由于Hash逼近单向函数;所以,你可以用它来对数据进行加密。
  • 不同的应用对Hash函数有着不同的要求;比如,用于加密的Hash函数主要考虑它和单项函数的差距,而用于查找的Hash函数主要考虑它映射到小范围的冲突率。

从简单原则出发,我们首先考虑下字符串的哈希函数。我们知道字符串特指ASCII的编码字符串,他们哈希函数后值是不一样的。看一个简单的算法

djb2算法

unsigned int DJB_hash(char *str)    
{    
         unsigned int hash = 5381;    
    
         while (*str)    
         {    
                 hash += (hash << 5) + (*str++);    
         }    
    
         return (hash & 0x7FFFFFFF);    
} 

在看一个和djb算法相似的算法,sdbm算法

unsigned int SDBM_hash(char *str)    
{    
         unsigned int hash = 0;    
    
         while (*str)    
         {    
                 hash = (*str++) + (hash << 6) + (hash << 16) - hash;    
         }    
    
         return (hash & 0x7FFFFFFF);    
}  

虽然上面两种算法的很快,但是基于哈希冲突少的特点,djb算法和sdbm算法都没能提供理论的依据,而主要依赖于试验。

在哈希的应用中,还有一类特殊的哈希函数,叫做密码哈希函数。

密码学哈希函数

定义:

  Hash函数H将可变长度的数据块M作为输入,产生固定长度的Hash值h = H(M)。   称M是h的原像。因为H是多对一的映射,所以对于任意给定的Hash值h,对应有多个原像。如果满足x≠y且H(x)=H(y),则称为碰撞。

密码学Hash函数的应用

1、消息认证

  Hash码能够通过如下不同方法用于提供消息认证

 a) 使用对称密码E加密消息和Hash码,由于只有A和B共享密钥K,所以消息必然发自A处,且可通过验证Hash码证明数据在传输过程中未被更改。

    b) 使用对称密码只对Hash码加密。由于明文无需加密性的应用,这种方案大大减少了加密操作的负担。

    c) 不使用加密算法,仅使用Hash函数实现消息验证。该方案中,通信双方共享相同的秘密值S,发送方A将消息M和秘密值S串联后计算其Hash值,并将得到的Hash值附在消息M后发送。因为接收方B同时掌握S值,所以能够重新计算该Hash值进行验证。

    d) 在方案c的基础上将整个消息和Hash值加密,以提供保密性。

  处于成本和速度方面的考虑,人们越来越对那些不包含加密函数的方法感兴趣,因此b和c方案更受青睐,不过如果对整个消息有加密型要求,则a和d仍具有实际意义。

  实际应用中,消息认证通常使用消息认证码(MAC)实现。MAC函数将通信双方共享的密钥和数据块作为输入,产生Hash值作为MAC码,然后将MAC码和受保护的消息一起传递或存储。需要检查消息的完整性时,使用MAC函数对消息重新计算,并将计算结果与存储的MAC码对比。MAC提供安全保护,用于抵抗不知道密钥的攻击者的攻击。在实现中,往往使用比加密算法效率更高的特殊设计的MAC函数。

  2、数字签名

数字签名的应用比消息认证更加广泛。主要有如下两种方案:

 a) 使用发送方的私钥利用公钥密码算法对Hash码进行加密。这种方法也可提供认证;由于只有发送方可以产生加密后的Hash码,所以这种方法也提供了数字签名。

    b) 若既希望保证保密性又希望有数字签名,则先用发送方的私钥对Hash码加密,再用对称密码中的密钥对象消息和公钥算法加密结果进行加密,这种技术比较常用。

3、其他应用

  对于Hash函数,通常还被用于产生单向口令文件。在操作系统中,存储口令的Hash值而不是口令本身,当用户输入口令时,操作系统将比对输入口令的Hash值和存储在口令文件中的Hash值来进行用户验证。

  Hash函数还能用于入侵检测和病毒检测。将每个文件的Hash值H(F)存储在安全系统中(如CD-R),随后就能通过重新计算H(F)来判断文件是否被修改过。入侵者只能够改变F,而不能改变H(F)

  密码学Hash函数能够用于构建随机函数PRF或用作伪随机数发生器。基于Hash函数的PRF可用于对称密码中的密钥产生。

密码学Hash函数的安全性需求

弱Hash函数:只满足以上前五个要求的Hash函数。

强Hash函数:满足以上前六个要求的Hash函数。

  强Hash函数能够保证免受以下攻击:假设Bob写一条借据消息并发送给Alice,Alice在借据上签名认可。Bob如果能找到两条消息具有同样的Hash值,其中一个借据消息要求Alice归还金额较小,另一个金额很大,那么让Alice签下第一个小额借据后,Bob就能声称第二个借据是真实的(将Alice在第一个借据的签名附到第二个借据中)。

  下图展示了抗原像攻击、抗弱碰撞攻击和抗强碰撞攻击三者之间的关系

 在传统观念中并没有把伪随机性作为密码学Hash函数的安全性需求,但在实际应用中或多或少有所要求。密码学Hash函数通常用于密钥产生、伪随机数发生器以及消息完整性应用,上述三个应用都要求Hash函数的输出是随机的。

对Hash函数的攻击

1、穷举攻击

  a) 原像攻击和第二原像攻击

  攻击者对给定的Hash值h,试图找到满足H(y) = h的y。穷举攻击的方法是随机选择y,尝试计算其Hash值知道碰撞出现。对于m位的Hash值,穷举的规模大约是2m,对于攻击者平均尝试次数为2m-1,才能找到一个满足H(y)=h的y值。

b) 碰撞攻击

  对于碰撞攻击,攻击者试图找到两个消息或数据块x和y,满足H(x)=H(y),与原像攻击和第二原像攻击相比,其穷举的规模相对更小一些,这也通过数学上的生日悖论得到印证。本质上,如果我们在均匀分布的0到N-1的范围内选择随机整数变量,那么在N1/2次选择后发生重复的概率就会超过0.5。因此,对于m位的Hash值,如果我们随机选择数据块,预计在2m/2次尝试后就能找到两个具有相同Hash值的数据块。

  Yuval提出以下策略进行碰撞攻击:

    1、发送方A准备对文本消息x进行签名(尚未签名,但可预期要签名的文件内容),其使用的方法是:用A的私钥对m位的Hash码加密并将加密后的Hash码附于消息之后。

    2、攻击者产生该消息x的2m/2种变式x',每种变式都表达相同的意义,将这些消息以及对应的Hash值存储起来。

      产生多个具有相同意义的变式并不难,例如攻击者可以在文件的词与词之间插入若干“空格-空格-退格”字符对,然后在实例中用“空格-退格-空格”替代这些字符,从而产生各种变式。攻击者也可以简单地改变消息中的某些词但不改变消息的意义。

    3、攻击者准备伪造一条消息y,并想获取A的签名,只需要伪造y的变式y',然后计算H(y'),并与所有的H(x')进行比对,直到碰撞出现。

    4、攻击者将发生碰撞的消息x'提供给A签名,然后将该签名附于伪造消息y'后。这样攻击者就在不知道A密钥的情况下获得了有A数字签名的消息y',并可以此获利。

参考:密码hash函数

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏喔家ArchiSelf

全栈Python 编程必备

Python作为一种编程语言,被称为“胶水语言”,更被拥趸们誉为“最美丽”的编程语言,从云端到客户端,再到物联网终端,无所不在,同时还是人工智能优选的编程语言。

3685
来自专栏老司机的简书

老司机读书笔记——Effective Objective-C 2.0阅读笔记

比方说,在循环中不断地创建的临时对象。即便这些对象在调用完方法之后就就不在使用了,他们也依然处于存活状态,因为目前还在自动释放池里,等待系统稍后将其释放并回收。...

842
来自专栏程序员Gank

【译】使用RxJava实现延迟订阅

我越来越喜欢把RxJava的defer()操作符作为一个工具来使用,以确保Observable代码在被订阅后才执行(而不是创建后立即执行)。我之前写过一些有关d...

1564
来自专栏IMWeb前端团队

CrossBridge

介绍 CrossBridge是Adobe FlasCC的开源版本,它提供了一个完整的C/C++开发环境,目的是把C/C++程序编译成Flash程序,运行于Fl...

2230
来自专栏程序员Gank

【译】使用RxJava实现延迟订阅

我越来越喜欢把RxJava的defer()操作符作为一个工具来使用,以确保Observable代码在被订阅后才执行(而不是创建后立即执行)。我之前写过一些有关d...

1393
来自专栏安恒网络空间安全讲武堂

writeup | 强网杯web题目四道

0x01 web签到 0x02 streamgame1 0x03 streamgame2 0x04 Three hits 0x01web签到 md5碰撞 查看...

4036
来自专栏ChaMd5安全团队

Flare-On 2018 writeup(上)

签到关,jar程序,直接拖入jd,很直接的flag: GoldenTicket2018@flare-on.com

1274
来自专栏深入浅出区块链技术

Solidity 教程系列11 - 视图函数、虚函数讲解

Solidity 教程系列第11篇 - Solidity 视图函数、虚函数讲解。 Solidity 系列完整的文章列表请查看分类-Solidity。

521
来自专栏lhyt前端之路

Rxjs光速入门0. 前言1. Observable2. 产生数据源3. Hot & Cold Observable5. 操作符6. 弹珠图7. Subject总结

Rx指的是响应式编程的实践工具扩展——reactive extension,编程风格是响应式编程+函数式编程。Rxjs则是这种模式的js的实现,处理异步能力优...

2083
来自专栏极客猴

基础知识 | 使用 Python 将数据写到 CSV 文件

我们从网上爬取数据,最后一步会考虑如何存储数据。如果数据量不大,往往不会选择存储到数据库,而是选择存储到文件中,例如文本文件、CSV 文件、xls 文件等。因为...

992

扫码关注云+社区

领取腾讯云代金券