精华内容
下载资源
问答
  • 哈希函数
    2022-04-01 16:43:54
    • 本文出自 AC.HASH 团队,AC<=>Adaptive Creator,适应性创作者,旨在于能够在未来新领域下创造出新的哈希算法以应对未来局面。
    • 产出本文的成员:
      • 中原工学院大二在校生(昵称:莫凡)
    • 我们在OpenHarmony成长计划啃论文俱乐部里,通过啃论文方式学习hash技术


    什么是哈希函数?

    一个哈希函数 H H H是一个变换,取一个可变大小的输入 m m m,返回一个固定大小的字符串,称为哈希值 h h h( 即 h = H ( m ) h = H ( m ) h=H(m))。具有这种性质的哈希函数具有多种通用的计算用途,但在密码学中使用时,通常选择哈希函数具有一些附加性质。

    一个密码哈希函数的基本要求是:

    输入可以是任意长度的,
    输出具有固定长度,
    H ( x ) H(x) H(x)对于任意给定的 x x x相对容易计算,
    H ( x ) H(x) H(x)是单向的,
    H ( x ) H(x) H(x)是无碰撞的。

    一个哈希函数 H H H据说是单向的,如果很难求逆,其中‘很难求逆’是指给定一个哈希值 h h h,在计算上很难找到一些输入 x x x使得 H ( x ) = h H ( x ) = h H(x)=h

    如果给定一个消息 x x x,在计算上不可能找到一个不等于 x x x的消息 y y y使得 H ( x ) = H ( y ) H ( x ) = H ( y ) H(x)=H(y),则称 H H H是一个弱无碰撞哈希函数。

    一个强的无碰撞哈希函数 H H H,它在计算上不可行地找到任意两个消息 x x x y y y使得 H ( x ) = H ( y ) H ( x ) = H ( y ) H(x)=H(y)

    哈希值简明地表示计算它的较长消息或文档;可以把一个消息摘要看作较大文档的‘数字指纹’。著名哈希函数的例子有MD2和MD5(see here)以及SHA(see here)。

    也许加密哈希函数的主要作用在于提供数字签名。由于哈希函数一般比数字签名算法要快,因此,
    在文档的哈希值上,通过计算签名来计算某些文档的数字签名是经典的,与文档本身相比,哈希值很小。此外,一个信息摘要可以公开,而不需要揭示其来源的文献内容。这在数字时间戳(see here)中很重要,因为使用哈希函数,可以在不向时间戳服务透露文档内容的情况下得到时间戳。


    什么是birthday attack?

    birthday attack是用来指一类暴力攻击的名称。它从惊人的结果中得到它的名字,即23人一组中的两个或两个以上的人共享同一个生日的概率大于 1 2 \frac{1}{2} 21;这样的结果被称为生日悖论(birthday paradox)。

    如果某种函数,当供给一个随机输入时,返回 k k k古典概型值中的一个,那么通过对不同输入的函数反复评估,我们期望在约 1.2 k 1 2 1.2k^{\frac{1}{2}} 1.2k21获得相同的输出。对于上述生日悖论,用365替换k。

    birthday attack常被用来发现哈希函数的碰撞。


    哈希值的长度如何影响安全性?

    哈希函数的基本密码属性是它既是单向的,也是无冲突的。我们可以对哈希函数进行的最基本的攻击是随机地选择输入到哈希函数中,直到我们找到一些输入能够得到我们正在寻找的目标输出值( 从而与单向属性相矛盾 ),或者找到两个产生相同输出的输入( 从而与无碰撞属性相矛盾 )。

    假设哈希函数产生一个 n n n位长的输出。如果我们试图找到一些能产生某种目标输出值y的输入,那么由于每一个输出都是同样可能的,我们期望要尝试 2 n 2^{n} 2n个可能的输入值。

    如果我们试图找到一个冲突,那么根据生日悖论,我们会预期在尝试了 2 n 2 2^{\frac{n}{2}} 22n可能的输入值之后,我们会发生一些冲突。Van Oorschot 和Wiener 展示了如何实施这种残酷的力量攻击。

    关于在提供数字签名时使用哈希函数,Yuval 基于生日悖论提出了以下策略,其中n为消息摘要的长度:
    1.攻击者选择Alice很可能要签名的无害目标消息。
    2.攻击者生成 2 n 2 2^{\frac{n}{2}} 22n个无害消息( 例如 ,做一些小的编辑修改 )的变体,所有这些变体都传达相同的含义 和 它们对应的信息摘要。然后,他生成要替换的目标消息的相等数量的变化。
    3.根据生日悖论,无害消息的变化之一与目标消息的变化之一匹配的概率大于 1 2 \frac{1}{2} 21
    4.攻击者然后在无害消息的变化上获得Alice的签名。
    5.从无害消息中取出签名,并附加到产生相同消息摘要的目标消息的变体中。被攻击者在没有运用加密密钥的情况下成功伪造了消息。
    6.为了避免依赖于蛮力方法的攻击,哈希函数的输出必须足够长。


    什么是压缩函数?

    Damg�rd 和 Merkle 定义过一个哈希函数被称为所谓的压缩函数,极大地影响了密码哈希函数的设计。压缩函数取固定长度的输入,返回较短的、固定长度的输出。然后可以通过压缩函数的重复应用来定义一个哈希函数,直到整个信息被处理完。在这个过程中,一个任意长度的信息根据压缩函数被分割成一定长度的块,并进行"填充(padded)" (出于安全原因),使得信息的大小是块大小的倍数。然后对这些块进行顺序处理,将迄今为止的哈希结果和当前的信息块作为输入,最终输出为信息的哈希值。


    什么是冲突(pseudo-collisions)?

    冲突是位于迭代哈希函数核心的压缩函数的碰撞。哈希函数的压缩函数的碰撞在构造哈希函数本身的碰撞时可能是有用的,但通常情况并非如此。虽然冲突可能被视为哈希函数的不幸属性,但一个伪冲突(pseudo-collision)并不等同于碰撞,哈希函数仍然可以是安全的。MD5 是一个哈希函数的例子,伪碰撞已经被发现,但是仍然被认为是安全的。


    什么是MD2、MD4和MD5?

    MD2、MD4和MD5是Rivest开发的信息摘要算法。它们是针对数字签名应用而言的,在一个大的消息被用私钥签名之前,必须以安全的方式‘压缩’。这三种算法都接收任意长度的消息,并生成128位消息摘要。虽然这些算法的结构有些相似,但MD2的设计与MD4和MD5完全不同,那是因为MD2是为8位机器做过设计优化的,而MD4和MD5却是面向32位的电脑。三种算法的描述和源代码可以在Internet RFCs 1319 - 1321找到。

    MD2由Rivest于1989年开发。信息首先被填充(数据部位),使其字节长度是16的倍数。然后在信息末尾追加一个16字节的校验和,并在这个新产生的信息上计算哈希值。Rogier和Chauvaud发现,如果省略校验和的计算,MD2的碰撞可以被构造出来。这是MD2已知的唯一的密码分析结果。

    MD4是Rivest于1990年开发的。对信息进行填充,保证信息在加上448后的长度可以被512整除。然后将信息原始长度的64位二进制表示添加到信息中。该消息在Damg�rd / Merkle迭代结构中以512位块进行处理,每个块以三个不同的步骤进行处理。Den Boer和Bosselaers等人非常迅速地开发了对MD4版本的攻击,其中第一轮或最后一轮丢失。Dobbertin 已经在一个典型的PC机上显示了如何在一分钟内就能发现MD4全版本的碰撞。显然,现在MD4被认为是被打破了。

    MD5由Rivest于1991年开发。它在md4的基础上增加了"安全-带子"(safety-belts)的概念,虽然比MD4稍慢,但更安全。该算法由4个截然不同的步骤组成,其设计与MD4略有不同。信息摘要大小以及填充要求保持不变。Den Boer和Bosselaers 发现了MD5的伪碰撞,但没有其他已知的密码分析结果。

    Van Oorschot 和 Wiener在哈希函数中考虑了对碰撞的粗暴力搜索,他们估计专门为MD5设计的碰撞搜索机(1994年耗资 1000万美元)可以在平均每24天内找到一个MD5的碰撞。一般的技术可以应用于其他哈希函数。


    什么是安全哈希算法(SHA和 SHA-1)?

    安全哈希标准(SHS)中规定的算法——安全哈希算法(SHA)由NIST开发,并作为联邦信息处理标准( FIPS PUB 180 )出版。SHA-1是对1994年出版的SHA的修订。修订纠正了SHA中一个未发表的缺陷。它的设计与Rivest开发的MD4哈希函数族非常相似。

    该算法取长度小于 2 64 2^{64} 264位的消息,产生160位的信息摘要。该算法比MD5稍慢,但较大的信息摘要使其更安全地抵抗蛮力碰撞(brute-force collision)和反转攻击(inversion attacks)。


    还有哪些其他哈希函数?

    为了在这里作一个简要的概述,我们注意到哈希函数往往根据其设计分为三类:
    围绕分组密码构建的哈希函数(those built around block ciphers),使用模块化算术的哈希函数(those built around block ciphers,),以及那些具有所谓的“专用”设计的哈希函数(those which have what is termed a “dedicated” design)。

    通过在分组密码周围构建哈希函数,意在通过使用DES(数据加密标准)等信任良好的分组密码可以获得安全和信任良好的哈希函数。所谓Davies-Meyer哈希函数就是一个围绕DES的使用而构建的哈希函数的例子。

    在第二类哈希函数中使用模块算术是为了在哈希函数与同样使用模块算术的数字签名算法一起使用时节省实现成本。遗憾的是,从安全角度来看,这类哈希函数的跟踪记录并不好,在这第二类中也没有哈希函数可以推荐。

    第三类中的哈希函数,有了它们所谓的‘专用’设计,往往速度很快,相对于那些围绕使用一个分组密码而设计的算法,给出了相当大的优势。与MD5和SHA-1一样,RIPE-MD 和 HAVAL是专用的哈希函数,也具有类似MD4的设计。


    参考资料

    http://x5.net/faqs/crypto/

    更多相关内容
  • 哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。具体的介绍网上有很详细的描述,如闲聊哈希...
  • 正在学习区块链,如果我哪里有错误希望大家指出,如果有任何想法也欢迎留言。这些笔记本身是在typora上写的,如果有显示不正确的敬请谅解...比特币用的哈希函数是SHA-256。  一共有三点,其中前两点都很简单,于算法而
  • 通过引入一个强抗碰撞哈希函数来提高加密部分和签名部分的耦合性,并对消息的哈希值进行数字签名处理,避免了仲裁者进行的存在性伪造攻击.改进方案在基本保持原方案计算和空间开销的同时,还具备强保密性、抗仲裁者...
  • 哈希函数

    万次阅读 多人点赞 2018-03-01 08:12:14
    在某种程度上,散列是与排序相反的一种操作,排序是将集合中的元素按照某种方式比如字典顺序排列在一起,而散列通过计算哈希值,打破元素之间原有的关系,使集合中的元素按照散列函数的分类进行排列。在介绍一些集合...

    什么是 Hash

    Hash(哈希),又称“散列”。

    散列(hash)英文原意是“混杂”、“拼凑”、“重新表述”的意思。

    在某种程度上,散列是与排序相反的一种操作,排序是将集合中的元素按照某种方式比如字典顺序排列在一起,而散列通过计算哈希值,打破元素之间原有的关系,使集合中的元素按照散列函数的分类进行排列。

    在介绍一些集合时,我们总强调需要重写某个类的 equlas() 方法和 hashCode() 方法,确保唯一性。这里的 hashCode() 表示的是对当前对象的唯一标示。计算 hashCode 的过程就称作 哈希。

    为什么要有 Hash

    我们通常使用数组或者链表来存储元素,一旦存储的内容数量特别多,需要占用很大的空间,而且在查找某个元素是否存在的过程中,数组和链表都需要挨个循环比较,而通过 哈希 计算,可以大大减少比较次数

    这里写图片描述

    举个栗子:

    现在有 4 个数 {2,5,9,13},需要查找 13 是否存在。

    1.使用数组存储,需要新建个数组 new int[]{2,5,9,13},然后需要写个循环遍历查找:

        int[] numbers = new int[]{2,5,9,13};
        for (int i = 0; i < numbers.length; i++) {
            if (numbers[i] == 13){
                System.out.println("find it!");
                return;
            }
        }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    这样需要遍历 4 次才能找到,时间复杂度为 O(n)。

    2.而假如存储时先使用哈希函数进行计算,这里我随便用个函数:

     H[key] = key % 3;
    
    • 1
    • 2

    四个数 {2,5,9,13} 对应的哈希值为:

     H[2] = 2 % 3 = 2;
     H[5] = 5 % 3 = 2;
     H[9] = 9 % 3 = 0;
     H[13] = 13 % 3 = 1;
    
    • 1
    • 2
    • 3
    • 4
    • 5

    然后把它们存储到对应的位置。

    当要查找 13 时,只要先使用哈希函数计算它的位置,然后去那个位置查看是否存在就好了,本例中只需查找一次,时间复杂度为 O(1)。

    因此可以发现,哈希 其实是随机存储的一种优化,先进行分类,然后查找时按照这个对象的分类去找。

    哈希通过一次计算大幅度缩小查找范围,自然比从全部数据里查找速度要快。

    比如你和我一样是个剁手族买书狂,家里书一大堆,如果书存放时不分类直接摆到书架上(数组存储),找某本书时可能需要脑袋从左往右从上往下转好几圈才能发现;如果存放时按照类别分开放,技术书、小说、文学等等分开(按照某种哈希函数计算),找书时只要从它对应的分类里找,自然省事多了。

    哈希函数

    哈希的过程中需要使用哈希函数进行计算。

    哈希函数是一种映射关系,根据数据的关键词 key ,通过一定的函数关系,计算出该元素存储位置的函数。

    表示为:

    address = H [key]

    几种常见的哈希函数(散列函数)构造方法

    • 直接定址法 
      • 取关键字或关键字的某个线性函数值为散列地址。
      • 即 H(key) = key 或 H(key) = a*key + b,其中a和b为常数。
      • 比如这里写图片描述
    • 除留余数法 
      • 取关键字被某个不大于散列表长度 m 的数 p 求余,得到的作为散列地址。
      • 即 H(key) = key % p, p < m。 
      • 比如这里写图片描述
    • 数字分析法 
      • 当关键字的位数大于地址的位数,对关键字的各位分布进行分析,选出分布均匀的任意几位作为散列地址。
      • 仅适用于所有关键字都已知的情况下,根据实际应用确定要选取的部分,尽量避免发生冲突。
      • 比如 这里写图片描述
    • 平方取中法 
      • 先计算出关键字值的平方,然后取平方值中间几位作为散列地址。
      • 随机分布的关键字,得到的散列地址也是随机分布的。
      • 比如 这里写图片描述
    • 折叠法(叠加法) 
      • 将关键字分为位数相同的几部分,然后取这几部分的叠加和(舍去进位)作为散列地址。
      • 用于关键字位数较多,并且关键字中每一位上数字分布大致均匀。 
      • 比如 这里写图片描述
    • 随机数法 
      • 选择一个随机函数,把关键字的随机函数值作为它的哈希值。
      • 通常当关键字的长度不等时用这种方法。 

    构造哈希函数的方法很多,实际工作中要根据不同的情况选择合适的方法,总的原则是尽可能少的产生冲突

    通常考虑的因素有关键字的长度分布情况哈希值的范围等。

    如:当关键字是整数类型时就可以用除留余数法;如果关键字是小数类型,选择随机数法会比较好。

    哈希冲突的解决

    选用哈希函数计算哈希值时,可能不同的 key 会得到相同的结果,一个地址怎么存放多个数据呢?这就是冲突。

    常用的主要有两种方法解决冲突:

    1.链接法(拉链法)

    拉链法解决冲突的做法是: 
    将所有关键字为同义词的结点链接在同一个单链表中。

    若选定的散列表长度为 m,则可将散列表定义为一个由 m 个头指针组成的指针数组 T[0..m-1] 。

    凡是散列地址为 i 的结点,均插入到以 T[i] 为头指针的单链表中。 
    T 中各分量的初值均应为空指针。

    在拉链法中,装填因子 α 可以大于 1,但一般均取 α ≤ 1。

    这里写图片描述

    2.开放定址法

    用开放定址法解决冲突的做法是:

    用开放定址法解决冲突的做法是:当冲突发生时,使用某种探测技术在散列表中形成一个探测序列。沿此序列逐个单元地查找,直到找到给定的关键字,或者碰到一个开放的地址(即该地址单元为空)为止(若要插入,在探查到开放的地址,则可将待插入的新结点存人该地址单元)。查找时探测到开放的地址则表明表中无待查的关键字,即查找失败。

    简单的说:当冲突发生时,使用某种探查(亦称探测)技术在散列表中寻找下一个空的散列地址,只要散列表足够大,空的散列地址总能找到

    按照形成探查序列的方法不同,可将开放定址法区分为线性探查法、二次探查法、双重散列法等。

    a.线性探查法

    hi=(h(key)+i) % m ,0 ≤ i ≤ m-1 

    基本思想是: 
    探查时从地址 d 开始,首先探查 T[d],然后依次探查 T[d+1],…,直到 T[m-1],此后又循环到 T[0],T[1],…,直到探查到 有空余地址 或者到 T[d-1]为止。

    b.二次探查法

    hi=(h(key)+i*i) % m,0 ≤ i ≤ m-1 

    基本思想是: 
    探查时从地址 d 开始,首先探查 T[d],然后依次探查 T[d+1^2],T[d+2^2],T[d+3^2],…,等,直到探查到 有空余地址 或者到 T[d-1]为止。

    缺点是无法探查到整个散列空间。

    c.双重散列法

    hi=(h(key)+i*h1(key)) % m,0 ≤ i ≤ m-1 

    基本思想是: 
    探查时从地址 d 开始,首先探查 T[d],然后依次探查 T[d+h1(d)], T[d + 2*h1(d)],…,等。

    该方法使用了两个散列函数 h(key) 和 h1(key),故也称为双散列函数探查法。

    定义 h1(key) 的方法较多,但无论采用什么方法定义,都必须使 h1(key) 的值和 m 互素,才能使发生冲突的同义词地址均匀地分布在整个表中,否则可能造成同义词地址的循环计算。

    该方法是开放定址法中最好的方法之一。

    哈希的应用

    • 哈希表
    • 分布式缓存

    哈希表(散列表)

    哈希表(hash table)是哈希函数最主要的应用。

    哈希表是实现关联数组(associative array)的一种数据结构,广泛应用于实现数据的快速查找。

    这里写图片描述

    用哈希函数计算关键字的哈希值(hash value),通过哈希值这个索引就可以找到关键字的存储位置,即桶(bucket)。哈希表不同于二叉树、栈、序列的数据结构一般情况下,在哈希表上的插入、查找、删除等操作的时间复杂度是 O(1)。

    查找过程中,关键字的比较次数,取决于产生冲突的多少,产生的冲突少,查找效率就高,产生的冲突多,查找效率就低。因此,影响产生冲突多少的因素,也就是影响查找效率的因素。 
    影响产生冲突多少有以下三个因素:

    1. 哈希函数是否均匀;
    2. 处理冲突的方法;
    3. 哈希表的加载因子。

    哈希表的加载因子和容量决定了在什么时候桶数(存储位置)不够,需要重新哈希。

    加载因子太大的话桶太多,遍历时效率变低;太大的话频繁 rehash,导致性能降低。所以加载因子的大小需要结合时间和空间效率考虑。

    在 HashMap 中的加载因子为 0.75,即四分之三。

    分布式缓存

    网络环境下的分布式缓存系统一般基于一致性哈希(Consistent hashing)。简单的说,一致性哈希将哈希值取值空间组织成一个虚拟的环,各个服务器与数据关键字K使用相同的哈希函数映射到这个环上,数据会存储在它顺时针“游走”遇到的第一个服务器。可以使每个服务器节点的负载相对均衡,很大程度上避免资源的浪费。

    在动态分布式缓存系统中,哈希算法的设计是关键点。使用分布更合理的算法可以使得多个服务节点间的负载相对均衡,可以很大程度上避免资源的浪费以及部分服务器过载。 使用带虚拟节点的一致性哈希算法,可以有效地降低服务硬件环境变化带来的数据迁移代价和风险,从而使分布式缓存系统更加高效稳定。

    Thanks

    http://www.nowamagic.net/librarys/veda/detail/1273

    http://blog.csdn.net/cywosp/article/details/23397179/

    http://www.cnblogs.com/qiaoshanzi/p/5295554.html

    http://baike.baidu.com/view/549615.htm

    https://books.google.co.jp/books?id=wCWmdhdX1AYC&pg=PA214&lpg=PA214&dq=%E6%95%B0%E5%AD%97%E5%88%86%E6%9E%90%E6%B3%95&source=bl&ots=5ieOT99Dob&sig=UcYbua2lwYocCQr32HF0XDF34h4&hl=zh-CN&sa=X&ved=0ahUKEwj104zw__fPAhUDw7wKHf3cAhIQ6AEISzAJ#v=onepage&q=%E6%95%B0%E5%AD%97%E5%88%86%E6%9E%90%E6%B3%95&f=false

    http://sjjp.tjuci.edu.cn/sjjg/DataStructure/DS/web/chazhao/chazhao9.4.3.3.htm

    http://www.cnblogs.com/qiaoshanzi/p/5295554.html

    (function () { ('pre.prettyprint code').each(function () { var lines =  (this).text().split(\n).length;var numbering = $(' ').addClass('pre-numbering').hide(); (this).addClass(hasnumbering).parent().append( numbering); for (i = 1; i
    展开全文
  • 基于量子游走的哈希函数
  • 1)设计几个不同的哈希函数,比较他们的地址冲突率(可以用更大的名字集合做实验)。 (2)研究这30个人名的特点,努力找一个哈希函数,使得对于不同的拼音名一定不发生地址冲突。 (3)在哈希函数确定的前提下尝试...
  • 量子哈希函数及其在量子密钥分发,伪随机数生成和图像加密中的隐私放大中的应用
  • 避免 这个问题的一个方法就是使用一个哈希函数来约束簇块的数量。哈希函数将会给定一个数值用来限定簇块数量的预计范围,但它得到的值是相对等分布的。哈希函数中存在的一个问题就是函数值会打乱记录原本的顺序。你...
  • 提供几个哈希函数(从字符串到int),这些函数将在C#和T-SQL中返回相同的值
  • 基于级联混沌的单向哈希函数
  • 如今越来越多的物联网设备带来了对哈希函数的需求,而传统的哈希函数又因为资源受限而不能直接应用,所以必须得针对该类设备重新设计,提出了一种新的轻量哈希函数HBL(Hash Function Based on LEA),它采用了主流...
  • 提出了一种适用于低成本无源RFID标签的低复杂性哈希函数M-hash。M-hash以并行线性反馈移位寄存器作为基本电路,采用并行压缩方式计算哈希值,利用压缩过程的信息损失而带来的单向性提供哈希函数的安全性。经过严格的...
  • 关于哈希函数的构造方法

    千次阅读 2022-04-08 15:44:16
    构造哈希函数的方法很多。在介绍各种方法之前,首先需要明确什么是“好”的哈希函数。 若对于关键字集合中的任一个关键字,经哈希函数映像到地址集合中任何一个地址的概率是相等的,则称此类哈希函数为均匀的(Uniform)...

            构造哈希函数的方法很多。在介绍各种方法之前,首先需要明确什么是“好”的哈希函数。

            若对于关键字集合中的任一个关键字,经哈希函数映像到地址集合中任何一个地址的概率是相等的,则称此类哈希函数为均匀的(Uniform)哈希函数。换句话说,就是使关键字经过哈希函数得到一个“随机的地址”,以便使一组关键字的哈希地址均匀分布在整个地址区间中,从而减少冲突。

            常用的构造哈希函数的方法有:

    1.直接定址法

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

            H(key)=key或H(key)=a\bulletkey+b

            其中a和b为常数(这种哈希函数叫做自身函数)。

            例如:有一个从1岁到100岁的人口数字统计表,其中,年龄作为关键字,哈希函数取关键字自身。如表1所示:

    标图1 直接定址哈希函数例之一题

            这样,若要询问25岁的人有多少,则只要查表的第25项即可。

            又如:有一个解放后出生的人口调查表,关键字是年份,哈希函数取关键字加一常数:H(key)-key+(-1948),如表2所示。

    图2 直接定址哈希函数列之二

            这样,若要查1970年出生的人数,则只要查第(1970—1948)=22项即可。

            由于直接定址所得地址集合和关键字集合的大小相同。因此,对于不同的关键字不会发生冲突。但实际中能使用这种哈希函数的情况很少。

    2.数字分析法

            假设关键字是以r为基的数(如:以10为基的十进制数),并且哈希表中可能出现的关键字都是事先知道的,则可取关键字的若干数位组成哈希地址。

            例如有80个记录,其关键字为8位十进制数。假设哈希表的表长为100%,则可取两位十进制数组成哈希地址。'取哪两位?原则是使得到的哈希地址尽量避免产生冲突,则需从分析这80个关键字着手。假设这80个关键字中的一部分如下所列:

            对关键字全体的分析中我们发现:第①②位都是“8 1”,第③位只可能取1、2、3或4,第⑧位只可能取2,5或7,因此这4位都不可取。由于中间的4位可看成是近乎随机的,因此可取其中任意两位,或取其中两位与另外两位的叠加求和后舍去进位作为哈希地址。

    3.平方取中法

            取关键字平方后的中间几位为哈希地址。这是一种较常用的构造哈希函数的方法。通常在选定哈希函数时不一定能知道关键字的全部情况,取其中哪几位也不一定合适,而一个数平方后的中间几位数和数的每一位都相关,由此使随机分布的关键字得到的哈希地址也是随机的。取的位数由表长决定。

            例如:为 BASIC源程序中的标识符建立一个哈希表。假设BASIC语言中允许的标识符为一个字母,或一个字母和一个数字。在计算机内可用两位八进制数表示字母和数字,如图3(a)所示。取标识符在计算机中的八进制数为它的关键字。假设表长为512=2^{9},则可取关键字平方后的中间9位二进制数为哈希地址。例如,图3(b)列出了一些标识符及它们的哈希地址。

    图3(a)字符的八进制表示对照表

    标题图3(b)标识符及其哈希地址

    4.折叠法

            将关键字分割成位数相同的几部分(最后一部分的位数可以不同),然后取这几部分的叠加和(舍去进位)作为哈希地址,这方法称为折叠法(folding)。关键字位数很多,而且关键字中每一-位上数字分布大致均匀时,可以采用折叠法得到哈希地址。

            例如:每一种西文图书都有一个国际标准图书编号(ISBN),它是一个10位的十进制数字,若要以它作关键字建立一个哈希表,当馆藏书种类不到10 000时,可采用折叠法构造一个四位数的哈希函数。在折叠法中数位叠加可以有移位叠加和间界叠加两种方法。移位叠加是将分割后的每一部分的最低位对齐,然后相加;间界叠加是从一端向另一端沿分割界来回折叠,然后对齐相加。如国际标准图书编号0-442-20586-4的哈希地址分别如图4(a)和(b)所示。

    图4 由折叠法求得哈希地址(a)移位叠加 (b)间界叠加

    5.除留余数发

            取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。即

            H(key) = key  MOD  p, p\leqm

            这是一种最简单,也最常用的构造哈希函数的方法。它不仅可以对关键字直接取模(MOD),也可在折叠,平方取中等运算之后取模。

            值得注意的是,在使用除留余数法时,对p的选择很重要。若p选的不好,容易产生同义词。请看下面3个例子。

            假设取标识符在计算机中的二进制表示为它的关键字(标识符中每个字母均用两位八进制数表示),然后对p=2^{6}取模。这个运算在计算机中只要移位便可实现,将关键字左移直至只留下最低的6位二进制数。这等于将关键字的所有高位值都忽略不计。因而使得所有最后一个字符相同的标识符,如a1,i1 , temp1,cp1等均成为同义词。

            若p含有质因子Pf,则所有含有pf因子的关键字的哈希地址均为pf的倍数。例如﹐当p=21( =3×7)时,下列含因子7的关键字对21取模的哈希地址均为7的倍数。

            假设有两个标识符xy 和yx,其中x,y均为字符,又假设它们的机器代码(6位二进制数)分别为c(z)和c(y),则上述两个标识符的关键字分别为

            key1 = 2^{6}c(x) + c(y) 和key2 = 2^{6}c(y) + c(x)

            假设用除留余数法求哈希地址,且力=tq,t是某个常数,q是某个质数。则当q=3时,这两个关键字将被散列在差为3的地址上。因为

            由众人的经验得知:一般情况下,可以选p为质数或不包含小于20的质因数的合数。

    6.随机数法

            选择一个随机函数,取关键字的随机函数值为它的哈希地址,即 H(key)=random(key),其中random为随机函数。通常﹐当关键字长度不等时采用此法构造哈希函数较恰当。

            实际工作中需视不同的情况采用不同的哈希函数。通常,考虑的因素有:

            (1)计算哈希函数所需时间(包括硬件指令的因素);

            (2)关键字的长度;

            (3)哈希表的大小;

            (4)关键字的分布情况;

            (5)记录的查找频率。

    然后今天就讲到这里啦,大家记得点赞收藏,分享转发,关注小哥哥哦! 最后,如果你想学或者正在学C/C++编程,可以加入小编的编程学习C/C++企鹅圈https://jq.qq.com/?_wv=1027&k=vLNylJeG

        

    展开全文
  • 哈希函数和数字签名概述.pdf
  • 哈希算法(哈希函数)基本

    千次阅读 2021-09-19 16:33:42
    一、什么是哈希(Hash) 哈希也称“散列”函数或“杂凑”函数。它是一个不可逆的单向映射,将任意长度的输入消息M...这是哈希函数安全性的基础。 灵敏性:对输入数据敏感,哪怕只改了一个Bit,得到的哈希值也大不相同

    目录

    一、什么是哈希(Hash)

    二、哈希的原理和特点

    三、哈希的实际用途

    四、典型的哈希函数

    (一)MD5

    (二)SHA

    五、Hash构造函数的方法


    一、什么是哈希(Hash)

    哈希也称“散列”函数或“杂凑”函数。它是一个不可逆的单向映射,将任意长度的输入消息M(或文件F)映射成为一个较短的定长哈希值H(M),也叫散列值(HashValue)、杂凑值或消息摘要。可见,这是一种单向密码体制,只有加密过程,没有解密过程(因此Hash求逆很困难)。

    二、哈希的原理和特点

    1. 单向性:从哈希值不能反向推导原始数据(计算不可行),即从哈希输出无法倒推输入的原始数值。这是哈希函数安全性的基础。
    2. 灵敏性:对输入数据敏感,哪怕只改了一个Bit,得到的哈希值也大不相同。换言之,消息M的任何改变都会导致哈希值H(M)发生改变。
    3. 易压易算:Hash本质上是把一个大范围集合映射到另一个小范围集合。故输入值的个数必须与小范围相当或者更小,不然冲突就会很多。所以,哈希算法执行效率要高,散列结果要尽量均衡。
    4. 抗碰撞性:理想Hash函数是无碰撞的,但实际上很难做到这一点。有两种抗碰撞性:一种是弱抗碰撞性,即对于给定的消息,要发现另一个消息,满足在计算上是不可行的;另一种是强抗碰撞性,即对于任意一对不同的消息,使得在计算上也是不可行的。

    也可以这么理解正向快速、逆向困难、输入敏感、冲突避免

    三、哈希的实际用途

    Hash能把一个大范围映射到一个小范围,能对输入数据或文件进行校验,还可用于查找等。具体的:

    1. 唯一标识或数据检验:能够对输入数据或文件进行校验,判断是否相同或是否被修改。如图片识别,可针对图像二进制流进行摘要后MD5,得到的哈希值作为图片唯一标识;如文件识别,服务器在接受文件上传时,对比两次传送文件的哈希值,若相同则无须再次上传(传统的奇偶校验和CRC校验一定程度上能检测并纠正数据传输中的信道误码,但没有抗数据篡改的能力)。
    2. 安全加密:对于敏感数据比如密码字段进行MD5或SHA加密传输。哈希算法还可以检验信息的拥有者是否真实。如,用保存密码的哈希值代替保存密码,基本可以杜绝泄密风险。
    3. 数字签名。由于非对称算法的运算速度较慢,所以在数字签名协议中,单向散列函数扮演了一个重要的角色。对Hash值,又称“数字摘要”进行数字签名,在统计上可以认为与对文件本身进行数字签名是等效的。
    4. 散列函数:是构造散列表的关键。它直接决定了散列冲突的概率和散列表的性质。不过相对哈希算法的其他方面应用,散列函数对散列冲突要求较低,出现冲突时可以通过开放寻址法或链表法解决冲突。对散列值是否能够反向解密要求也不高。反而更加关注的是散列的均匀性,即是否散列值均匀落入槽中以及散列函数执行的快慢也会影响散列表性能。所以散列函数一般比较简单,追求均匀和高效。
    5. *负载均衡:常用的负载均衡算法有很多,比如轮询、随机、加权轮询。如何实现一个会话粘滞的负载均衡算法呢?可以通过哈希算法,对客户端IP地址或会话SessionID计算哈希值,将取得的哈希值与服务器列表大小进行取模运算,最终得到应该被路由到的服务器编号。这样就可以把同一IP的客户端请求发到同一个后端服务器上。
    6. *数据分片:比如统计1T的日志文件中“搜索关键词”出现次数该如何解决?我们可以先对日志进行分片,然后采用多机处理,来提高处理速度。从搜索的日志中依次读取搜索关键词,并通过哈希函数计算哈希值,然后再跟n(机器数)取模,最终得到的值就是应该被分到的机器编号。这样相同哈希值的关键词就被分到同一台机器进行处理。每台机器分别计算关键词出现的次数,再进行合并就是最终结果。这也是MapReduce的基本思想。再比如图片识别应用中给每个图片的摘要信息取唯一标识然后构建散列表,如果图库中有大量图片,单机的hash表会过大,超过单机内存容量。这时也可以使用分片思想,准备n台机器,每台机器负责散列表的一部分数据。每次从图库取一个图片,计算唯一标识,然后与机器个数n求余取模,得到的值就是被分配到的机器编号,然后将这个唯一标识和图片路径发往对应机器构建散列表。当进行图片查找时,使用相同的哈希函数对图片摘要信息取唯一标识并对n求余取模操作后,得到的值k,就是当前图片所存储的机器编号,在该机器的散列表中查找该图片即可。实际上海量数据的处理问题,都可以借助这种数据分片思想,突破单机内存、CPU等资源限制。
    7. *分布式存储:一致性哈希算法解决缓存等分布式系统的扩容、缩容导致大量数据搬移难题。

    四、典型的哈希函数

    常见Hash算法有MD5和SHA系列,目前MD5和SHA1已经被破解,一般推荐至少使用SHA2-256算法。

    (一)MD5

    MD5属于Hash算法中的一种,它输入任意长度的信息,在处理过程中以512位输入数据块为单位,输出为128位的信息(数字指纹)。常用场景:

    1、防篡改,保障文件传输可靠性:如SVN中对文件的控制;文件下载过程中,网站提供MD5值供下载后判断文件是否被篡改;BT中对文件块进行校验的功能。

    2、增强密码保存的安全性:例如网站将用户密码的MD5值保存,而不是存储明文用户密码,当然,还会加SALT,进一步增强安全性。

    3、数字签名:在部分网上赌场中,使用MD5算法来保证过程的公平性,并使用随机串进行防碰撞,增加解码难度。

    算法实现过程:

    第一步:消息填充,补长到512的倍数。最后64位为消息长度(填充前的长度)的低64位,一定要补长(64+1~512),内容为100…0(如若消息长448,则填充512+64)。

    第二步:分割,把结果分割为512位的块:Y0,Y1,…(每一个有16个32比特长字)。

    第三步:计算,初始化MD buffer,128位常量(4个32bit字),进入循环迭代,共L次。每次一个输入128位,另一个输入512位,结果输出128位,用于下一轮输入。

    第四步:输出,最后一步的输出即为散列结果128位。

    (二)SHA-1  Secure Hash Algorithm

    安全哈希算法(Secure Hash Algorithm)主要适用于数字签名标准(Digital Signature Standard DSS)里面定义的数字签名算法(Digital Signature Algorithm DSA)。对于长度小于2^64b的消息,SHA-1将输入流按照每块512b(64B)进行分块,并产生20B或160b的信息摘要。

    https://images2015.cnblogs.com/blog/929265/201607/929265-20160701092331874-1851324775.png

    1.补位

    消息补位使其长度在对512取模以后的余数是448。也就是说,(补位后的消息长度)% 512 = 448。即使长度已经满足对512取模后余数是448,补位也必须要进行。

    补位是这样进行的:先补一个1,然后再补0,直到长度满足对512取模后余数是448。总而言之,补位是至少补一位,最多补512位。还是以前面的“abc”为例显示补位的过程。

    原始信息:  011000010110001001100011

    补位第一步:0110000101100010011000111,首先补一个“1”

    补位第二步:01100001011000100110001110…..0,然后补423个“0”

    我们可以把最后补位完成后的数据用16进制写成下面的样子,确保是448b:

    61626380000000000000000000000000

    00000000000000000000000000000000

    00000000000000000000000000000000

    0000000000000000

    2.补长度

    补长度是将原始数据的长度补到已经进行了补位操作的消息后面。通常用一个64位的数据来表示原始消息的长度。如果消息长度不大于2^64,那么第一个字就是0。

    在进行了补长度的操作以后,整个消息就变成下面这样了(16进制格式):

    61626380000000000000000000000000

    00000000000000000000000000000000

    00000000000000000000000000000000

    00000000000000000000000000000018

    如果原始的消息长度超过了512,我们需要将它补成512的倍数。然后我们把整个消息分成一个一个512位的数据块。分别处理每一个数据块,从而得到消息摘要。

    3.使用的常量

    一系列的常量字K(0),K(1),...,K(79),如果以16进制给出。它们如下:

    Kt=0x5A827999(0<=t<=19)

    Kt=0x6ED9EBA1(20<=t<=39)

    Kt=0x8F1BBCDC(40<=t<=59)

    Kt=0xCA62C1D6(60<=t<=79).

    4.需要使用的函数

    在SHA1中我们需要一系列的函数。每个函数ft(0<=t<=79)都操作32位字B,C,D并且产生32位字作为输出。

    ft(B,C,D)可以如下定义:

    ft(B,C,D)=(BANDC)or((NOTB)ANDD)(0<=t<=19)

    ft(B,C,D)=BXORCXORD(20<=t<=39)

    ft(B,C,D)=(BANDC)or(BANDD)or(CANDD)(40<=t<=59)

    ft(B,C,D)=BXORCXORD(60<=t<=79).

    5.计算消息摘要

    必须使用进行了补位和补长度后的消息来计算消息摘要。计算需要两个缓冲区,每个都由5个32位的字组成,还需要一个80个32位字的缓冲区。第一个5个字的缓冲区被标识为A,B,C,D,E。第一个5个字的缓冲区被标识为H0,H1,H2,H3,H4。80个字的缓冲区被标识为W0,W1,...,W79。

    另外还需要一个一个字的TEMP缓冲区。

    为了产生消息摘要,在第4部分中定义的16个字的数据块M1,M2,...,Mn会依次进行处理,处理每个数据块Mi包含80个步骤。


    在处理每个数据块之前,缓冲区{Hi}被初始化为下面的值(16进制)

    H0=0x67452301

    H1=0xEFCDAB89

    H2=0x98BADCFE

    H3=0x10325476

    H4=0xC3D2E1F0.


    现在开始处理M1,M2,...,Mn。为了处理Mi,需要进行下面的步骤

    (1)将Mi分成16个字W0,W1,...,W15,W0是最左边的字

    (2)对于t=16到79令Wt=S1(Wt-3XORWt-8XORWt-14XORWt-16).

    (3)令A=H0,B=H1,C=H2,D=H3,E=H4.

    (4)对于t=0到79,执行下面的循环

    TEMP=S5(A)+ft(B,C,D)+E+Wt+Kt;

    E=D;D=C;C=S30(B);B=A;A=TEMP;

    (5)令H0=H0+A,H1=H1+B,H2=H2+C,H3=H3+D,H4=H4+E.

    在处理完所有的Mn,后,消息摘要是一个160位的字符串,以下面的顺序标识H0H1H2H3H4。

    (三)SHA-2系列

    SHA-2是六个不同算法的合称,包括:SHA-224、SHA-256、SHA-384、SHA-512、SHA-512/224、SHA-512/256。除了生成摘要的长度、循环运行的次数等一些微小差异外,这些算法的基本结构是一致的。对于任意长度的消息,SHA256都会产生一个256bit长的消息摘要。

    详细参见:sha256算法原理 - Practical - 博客园

    至今尚未出现对SHA-2有效的攻击,SHA-2和SHA-1并没有接受公众密码社区的详细检验,所以它们的密码安全性还不被广泛信任。

    总体上,HAS-256与MD4、MD5以及HSA-1等哈希函数的操作流程类似,在哈希计算之前首先要进行以下两个步骤:

    • 对消息进行补位处理,最终的长度是512位的倍数;
    • 以512位为单位对消息进行分块为M1,M2,…,Mn
    • 处理消息块:从一个初始哈希H0开始,迭代计算:Hi = Hi-1 + CMi(Hi-1)

    其中C是SHA256的压缩函数,+是mod 2^32加法,Hn是消息区块的哈希值。

    五、Hash构造函数的方法

    1.直接定址法(极少用)

    以数据元素关键字k本身或它的线性函数作为它的哈希地址,即:H(k)=k或H(k)=a×k+b;(其中a,b为常数)。

    此法仅适合于:地址集合的大小==关键字集合的大小,其中a和b为常数。

    2.数字分析法

    假设关键字集合中的每个关键字都是由s位数字组成(u1,u2,…,us),分析关键字集中的全体,并从中提取分布均匀的若干位或它们的组合作为地址。数字分析法是取数据元素关键字中某些取值较均匀的数字位作为哈希地址的方法。即当关键字的位数很多时,可以通过对关键字的各位进行分析,丢掉分布不均匀的位,作为哈希值。它只适合于所有关键字值已知的情况。通过分析分布情况把关键字取值区间转化为一个较小的关键字取值区间。

    此法适于:能预先估计出全体关键字的每一位上各种数字出现的频度。

    3.折叠法

    将关键字分割成若干部分,然后取它们的叠加和为哈希地址。两种叠加处理的方法:移位叠加:将分割后的几部分低位对齐相加;边界叠加:从一端沿分割界来回折叠,然后对齐相加。

    所谓折叠法是将关键字分割成位数相同的几部分(最后一部分的位数可以不同),然后取这几部分的叠加和(舍去进位),这方法称为折叠法。这种方法适用于关键字位数较多,而且关键字中每一位上数字分布大致均匀的情况。

    折叠法中数位折叠又分为移位叠加和边界叠加两种方法,移位叠加是将分割后是每一部分的最低位对齐,然后相加;边界叠加是从一端向另一端沿分割界来回折叠,然后对齐相加。

    此法适于:关键字的数字位数特别多。

    4.平方取中法

    这是一种常用的哈希函数构造方法。这个方法是先取关键字的平方,然后根据可使用空间的大小,选取平方数是中间几位为哈希地址。哈希函数H(key)=“key2的中间几位”因为这种方法的原理是通过取平方扩大差别,平方值的中间几位和这个数的每一位都相关,则对不同的关键字得到的哈希函数值不易产生冲突,由此产生的哈希地址也较为均匀。

    此法适于:关键字中的每一位都有某些数字重复出现频度很高的现象。

    5.减去法



    减去法是数据的键值减去一个特定的数值以求得数据存储的位置。

    6.基数转换法

    将十进制数X看作其他进制,比如十三进制,再按照十三进制数转换成十进制数,提取其中若干为作为X的哈希值。一般取大于原来基数的数作为转换的基数,并且两个基数应该是互素的。

    7.除留余数法

    假设哈希表长为m,p为小于等于m的最大素数,则哈希函数为h(k)=k%p,其中%为模p取余运算。除留余数法的模p取不大于表长且最接近表长m素数时效果最好,且p最好取1.1n~1.7n之间的一个素数(n为存在的数据元素个数)。

    8.随机数法

    设定哈希函数为:H(key)=Random(key)其中,Random为伪随机函数

    此法适于:对长度不等的关键字构造哈希函数。

    9.随机乘数法

    亦称为“乘余取整法”。随机乘数法使用一个随机实数f,0≤f<1,乘积f*k的分数部分在0~1之间,用这个分数部分的值与n(哈希表的长度)相乘,乘积的整数部分就是对应的哈希值,显然这个哈希值落在0~n-1之间。其表达公式为:Hash(k)=「n*(f*k%1)」其中“f*k%1”表示f*k的小数部分,即f*k%1=f*k-「f*k」

    此方法的优点是对n的选择不很关键。通常若地址空间为p位就是选n=2p.Knuth对常数f的取法做了仔细的研究,他认为f取任何值都可以,但某些值效果更好。如f=(-1)/2=0.6180329...比较理想。

    10.字符串数值哈希法

    把字符串的前10个字符的ASCⅡ值之和对N取摸作为Hash地址,只要N较小,Hash地址将较均匀分布[0,N]区间内。对于N很大的情形,可使用ELFHash(ExecutableandLinkingFormat,ELF,可执行链接格式)函数,它把一个字符串的绝对长度作为输入,并通过一种方式把字符的十进制值结合起来,对长字符串和短字符串都有效,这种方式产生的位置可能不均匀分布。

    11.旋转法

    旋转法是将数据的键值中进行旋转。旋转法通常并不直接使用在哈希函数上,而是搭配其他哈希函数使用。

    展开全文
  • 基于可变参数广义混沌映射的快速高效哈希函数
  • 常用哈希函数介绍

    千次阅读 2021-03-31 16:21:32
    哈希函数介绍 什么是哈希?在记录的关键字与记录的存储地址之间建立的一种对应关系叫哈希函数哈希函数就是一种映射,是从关键字到存储地址的映射。 通常,包含哈希函数的算法的算法复杂度都假设为O(1),这就是为...
  • 1. 哈希表就是数组+哈希函数,其核心思想是利用数组可以按照下标索引随机访问数据的特性。 2. 哈希冲突的原因:数组的有界,哈希函数的计算,哈希值的映射。 3. 解决哈希冲突的方法:数组扩容,设计优秀的哈希函数,...
  • 本文详细分析了混沌并行键控哈希函数的安全性,指出它容易受到两种伪造攻击和弱密钥攻击(导致MAC冲突)。 为了纠正这种安全漏洞,进一步提出了一种改进的方案,并讨论了其安全性和性能。 理论分析表明,改进方案比...
  • 哈希函数的特征_哈希函数及其特征

    千次阅读 2020-07-06 22:57:28
    哈希函数的特征Prerequisite: Hashing data structure 先决条件: 哈希数据结构 The hash function is the component of hashing that maps the keys to some location in the hash table. As part of the hashing...
  • 用C语言实现常用的字符串哈希函数,比如RSHash、JSHash、PJWHash、FNVHash等
  • 创建最小的完美哈希函数为给定的键集生成最小的完美哈希函数。 给定的代码模板填充有参数,因此输出是实现哈希函数的代码。 可以轻松地为任何编程语言构造模板。安装最小的完美哈希函数生成器是用纯Python编写的,...
  • C++ STL 为std::unordered_set提供自定义哈希函数 所有哈希表都使用一个哈希函数,该函数将放入容器的元素的值映射到特定的存储桶。目标两个是相等的值始终生成相同的存储桶索引,而对于不同的值,理想情况下应处理...
  • 基于Johnson图上的量子游程构造量子哈希函数
  • 密码学哈希函数 什么是哈希函数? (What is a Hash Function?) A Hash Function is a mathematical function that converts a numerical value into another compressed numeric value. So, it compresses the text....
  • 基于网格密度和局部敏感哈希函数的并行化聚类算法.pdf

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 274,456
精华内容 109,782
关键字:

哈希函数