精华内容
下载资源
问答
  • 常见的hash函数
    千次阅读
    2020-09-18 14:17:44

    概述

    Hash函数(散列函数):是一种将任意长度的数据映射到有限长度的域上。通俗来讲,就是将一串任意长度的数据进行打乱混合,转换为一段固定长度的数据输出,这段数据便成为输入数据的一个“指纹”(特征)。Hash函数的首要目标是保证数据的完整性。而不是安全性。

    Hash函数的安全性

    Hash函数的安全需求

    需求描述
    输入长度可变Hash函数可以应用于任意长度的数据块
    输出长度固定Hash的输出长度是固定的
    效率对任意的x,计算H(x)在计算上是较容易的
    抗原像攻击(单向性)对任意给定的H(n),计算n在计算上是不可行的。
    抗第二原像攻击(抗弱碰撞性)对任意给定的x,找到一个y(y≠x)使得H(x)=H(y)在计算上不可行
    抗碰撞攻击(抗强碰撞性)对任意的Hash函数,找到满足的H(x)=H(y)在计算上不可行。
    伪随机性输入相同,H的输出也一定相同

    Hash函数的安全属性

    1. Collsion-free 无冲突

    根据Hash的安全需求,Hash函数的输入长度InputLength是任意的,但是,其输出长度的OutputLength是固定的。从理论上而言,Input的组合是无穷多种,而OutPut的组合是有限的,那么应该是存在两个不同的数据会生成同样的哈希值。但是,对于SHA256而言,尝试2256+1次数据会有1次数据冲突。尝试2130次数据会有99%的可能性找到冲突。

    应用: 信息摘要(Message digest),因为冲突的几率很小,那么我们可以利用记住大信息的哈希值来进行信息比对,以减少数据比对的运算。也就是将哈希值作为信息的识别“指纹”。

    2.Hiding 隐藏性

    Hash函数的单项函数,是不可逆的,Hash值不能转换为原来的数据值,能够很好的隐藏原数据。对于一个大的数据库而言,如身份认证,一个公司存储的用户账号密码,一般存储其登录账号和密码的Hash值,避免数据泄露后,攻击者能够轻松的使用用户账户。但是,如果数据是由简单的数字组成,那么也很容易遭受到暴力破解,这也是为什么在密码设定中会要求用户加入字母,符号等。为了达到隐藏元数据的目的,元数据需要选自范围特别广的集(highmin-entropy)

    应用: Commitment,即只公布哈希值,而在之后再公布哈希前的原数据。后期所有用户都可以通过比对哈希值来验证“信封”中的内容是否更改。

    3.Puzzle-friendly 谜题友好性

    Hash函数中一个字节的变动就能导致生成完全不同的哈希值(雪崩效应),且哈希值的改变没有任何的规律可循。
    对于每一个用k来加密x得到的结果H(k | x) = y,在知道y、k和H(k|x)的条件下,不存在比随机遍历更好的方法。

    Hash函数的应用

    消息认证

    消息认证是用来验证消息完整性的一种机制或服务。消息认证确保收到的数据和发送时是一致的(消息没有被篡改)。

    消息认证的本质是:利用Hash函数对发送者即将发送的消息计算一组Hash值,然后将消息与Hash值一同发送。接收者在收到消息后利用相同的Hash函数对消息进行计算,并将结果与发送过来的Hash值进行比对,若不匹配,则推断出消息在传送的过程中受到了篡改。

    消息认证共有一下几种不同的方法:

    1.使用对称加密消息和Hash码。
    2.使用堆成密码算法支队Hash码进行加密。
    3.不使用加密算法,即假设通信双方之前已经共享了一个秘密值,将该秘密值和消息串联起来再进行Hash,再将Hash过后的值与消息进行拼接发送。
    4.在步骤3的基础之上,将消息和拼接Hash过后的Hash值一起对称加密发送。

    数字签名

    数字签名实质上也是利用Hash函数对消息进行杂糅,但不同于消息认证的是,他将这串数据或者数据的一部分进行密码变换。数字签名能够在保证数据的完整性的同时,还能够保证数据发送方的不可抵赖性。

    基于公钥密码体制和私钥密码体制都能够得到数字签名,但主要是基于公钥密码体制的数字签名(这句话源自百度)。个人理解是在对称秘钥的情境下,这种签名又叫消息认证码。常用的数字签名的算法有:RSA、ElGamal、Des/DSA,椭圆曲线数字签名算法。

    Hash码用于数字签名的方案:

    1. 使用用户的私钥,利用公钥密码算法对Hash值进行加密。
    2. 上一种方法没有提供保密性,所以可以在上述的过程之后,利用对称密码进行加密。

    SHA

    SHA其实只是Secure Hash Algorithm(安全Hash算法)的缩写。事实上,其余被广泛使用的Hash函数被先后显现存在安全性问题。如:2004年的国际密码讨论年会(CRYPTO)尾声,王小云及其研究同事展示了MD5、SHA-0及其他相关散列函数的散列冲撞。也就是说,他们找到了一种方法,能够让x≠y的情况下MD5(x)=MD5(y),并且这种方法代价远小于随机暴力破解。其实,SHA-1也已经被找到了方法能够散列冲撞。

    所以我们主要讨论SHA-2,而SHA-2中一共有多种版本,其Hash值得长度依次为224、256、384和512位,人们一般将其称为:SHA-224、SHA-256、SHA-384和SHA-512。SHA-2其实和SHA-1类似,都采用的是相同得迭代与二元逻辑操作,SHA-1和SHA-2之间的主要区别在于哈希的长度。SHA-1的散列是更基础的版本,提供了较短的代码,唯一组合的可能性较小,而SHA-2或SHA-256创建的散列则更长,因此更为复杂。

    SHA参数对比

    SHA-1SHA-224SHA-256SHA-384SHA-512
    消息摘要长度160224256384512
    消息长度<264<264<264<2128<2128
    分组长度51251251210241024
    字长度3232326464
    步骤数8064648080

    SHA-512

    Input: m(m<2128)
    Output: 512bit
    处理单元:1024bit

    1. 附件填充位: 填充m,使得填充后的 length(message)≡ 896 (mod 1024 )。

      填充要求:即便已经满足 length(message)≡ 896 (mod 1024 ),也要对消息进行填充一次。
      填充方式:填充由一个1,后全由0补充。

    2. 附加长度:在消息后附加一个128位的块。在message 后面加128位的数据块, 他表示了m的长度。

    由①②可知,填充后的信息M已经是1024整数倍了,将M分为一个个的函数处理单元,M1,M2,…,MN

    1. 初始化Hash。Hash的中间结果与最中结果都存在寄存器中。缓冲区由8个64位寄存器组成(a,b,c,d,e,f,g,h)。这8个寄存器的初始值为:前8个个素数取平方根,取小数部分前64位。(以高位存储)
    2. 以1024位为分组处理数据,SHA-512需要经过80轮运算模块(SHA-256经过64轮)
    3. 输出
    更多相关内容
  • Hash函数和数字签名 Hash函数和数字签名 Hash函数和数字签名
  • php自定义hash函数实例

    2020-10-24 07:12:57
    主要介绍了php自定义hash函数,实例分析了hash函数的实现技巧,可实现简单的加密功能,具有一定参考借鉴价值,需要的朋友可以参考下
  • HASH函数

    千次阅读 2022-04-09 22:31:42
    hash函数就是把任意长的输入位(或字节)变化成固定长的输出字符串的一种函数。输出字符串的长度称为hash函数的位数。 哈希不能用于发现原始消息的内容或其任何其他特征,但可用于确定消息是否已更改。几乎所有...

    散列函数代表除了对称和非对称加密之外的第三种加密类型,我们可以称之为无密钥加密。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) 的计算是一个快速运算

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

    哈希函数将任意长度的数据转换为固定长度。这个过程通常被称为散列数据。

    散列比输入数据小得多,因此散列函数有时被称为压缩函数。

    由于散列是较大数据的较小表示,因此也称为摘要。

    哈希函数功能包括:

    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的值都适用,但对某些值效果会更好。

    平方取中法

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

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


     

    除留余数法

    取关键字被数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 散列函数来保护信息。

    参考文章:

    Cryptography Hash functions

    小白入门——哈希算法 - 简书

    散列函数(哈希)_askunix_hjh的博客-CSDN博客_散列函数

    展开全文
  • 混沌加密算法与HASH函数构造研究_12767438.zip
  • 关于hash函数的ppt
  • myhash.go /** * Created with IntelliJ IDEA. * User: liaojie * Date: 12-9-8 * Time: 下午3:53 * To change this template use File | Settings | File Templates. */ package main ... hash io
  • 常用哈希函数介绍

    千次阅读 2021-03-31 16:21:32
    哈希函数介绍 什么是哈希?在记录的关键字与记录的存储地址之间建立的一种对应关系叫哈希函数。 哈希函数就是一种映射,是从关键字到存储地址的映射。 通常,包含哈希函数的算法的算法复杂度都假设为O(1),这就是为...

    转载自:
    常用哈希函数介绍


    哈希函数介绍

    什么是哈希?在记录的关键字与记录的存储地址之间建立的一种对应关系叫哈希函数。 哈希函数就是一种映射,是从关键字到存储地址的映射。 通常,包含哈希函数的算法的算法复杂度都假设为O(1),这就是为什么在哈希表中搜索数据的时间复杂度会被认为是"平均为O(1)的复杂度".

    在讲解具体内容前,首先我们要清楚以下几个概念:

    冲突(碰撞) 对于不同的关键字ki、kj,若ki != kj,但H(ki) = H(kj)的现象叫冲突(collision) ,即不同的输入却有相同的输出。我们应该尽量避免冲突,因为冲突不仅会使我们在查找的时候效率变慢,还甚至会被攻击者利用从而大量消耗系统资源。 至于冲突的解决方案有很多种,具体可以参考这篇添加哈希表针对冲突的两种方式优缺点是什么?

    哈希函数的应用

    哈希算法广泛应用于很多场景,例如安全加密和数据结构中哈希表的查找,布隆过滤器和负载均衡(一致性哈希)等等。 下面介绍几个常用的哈希算法。

    加密哈希算法

    在安全方面应用主要体现在以下三个方面: (1) 文件校验 (2) 数字签名 (3) 鉴权协议

    在nodejs中我们可以使用原生crypto模块对数据进行加密,crypto.getHashes()查看支持的哈希算法。

    const crypto = require('crypto');
    console.log(crypto.getHashes());
    /*
    [ 'DSA',
      'DSA-SHA',
      'DSA-SHA1',
      'DSA-SHA1-old',
      'RSA-MD4',
      'RSA-MD5',
      'RSA-MDC2',
      'RSA-RIPEMD160',
      'RSA-SHA',
      'RSA-SHA1',
      'RSA-SHA1-2',
      'RSA-SHA224',
      'RSA-SHA256',
      'RSA-SHA384',
      'RSA-SHA512',
      'dsaEncryption',
      'dsaWithSHA',
      'dsaWithSHA1',
      'dss1',
      'ecdsa-with-SHA1',
      'md4',
      'md4WithRSAEncryption',
      'md5',
      'md5WithRSAEncryption',
      'mdc2',
      'mdc2WithRSA',
      'ripemd',
      'ripemd160',
      'ripemd160WithRSA',
      'rmd160',
      'sha',
      'sha1',
      'sha1WithRSAEncryption',
      'sha224',
      'sha224WithRSAEncryption',
      'sha256',
      'sha256WithRSAEncryption',
      'sha384',
      'sha384WithRSAEncryption',
      'sha512',
      'sha512WithRSAEncryption',
      'shaWithRSAEncryption',
      'ssl2-md5',
      'ssl3-md5',
      'ssl3-sha1',
      'whirlpool' ]
    */
    

    除了我们常用的md5,sha-1,sha-2族外,还有像DSA-SHA1,RSA-SHA1,sha1WithRSAEncryption,其中sha1WithRSAEncryption和RSA-SHA1等价,DSA和RSA都是加密算法,DSA和RSA的区别在于,DSA用于签名,而RSA可用于签名和加密。

    下面简单介绍下几种比较常用的加密哈希算法:

    1、 MD5 MD5即Message-Digest Algorithm 5(信息-摘要算法5),用于确保信息传输完整一致。是计算机广泛使用的杂凑算法之一,主流编程语言普遍已有MD5实现。将数据(如汉字)运算为另一固定长度值,是杂凑算法的基础原理,MD5的前身有MD2、MD3和MD4。 MD5是输入不定长度信息,输出固定长度128-bits的算法。经过程序流程,生成四个32位数据,最后联合起来成为一个128-bits散列。基本方式为,求余、取余、调整长度、与链接变量进行循环运算。得出结果。 NodeJS中使用MD5:

    var hash = crypto.createHash('md5');
    hash.update('test');
    console.log(hash.digest('hex'));    // 098f6bcd4621d373cade4e832627b4f6
    var hash = crypto.createHash('md5');
    hash.update('test1');
    console.log(hash.digest('hex'));    // 5a105e8b9d40e1329780d62ea2265d8a
    

    MD5一度被广泛应用于安全领域。但是在2004年王小云教授公布了MD5、MD4、HAVAL-128、RIPEMD-128几个 Hash函数的碰撞。这是近年来密码学领域最具实质性的研究进展。使用他们的技术,在数个小时内就可以找到MD5碰撞。使本算法不再适合当前的安全环境。目前,MD5计算广泛应用于错误检查。例如在一些BitTorrent下载中,软件通过计算MD5和检验下载到的碎片的完整性。

    2、SHA-1 SHA-1曾经在许多安全协议中广为使用,包括TLS和SSL、PGP、SSH、S/MIME和IPsec,曾被视为是MD5的后继者。 SHA-1是如今很常见的一种加密哈希算法,HTTPS传输和软件签名认证都很喜欢它,但它毕竟是诞生于1995年的老技术了(出自美国国安局NSA),已经渐渐跟不上时代,被破解的速度也是越来越快。 微软在2013年的Windows 8系统里就改用了SHA-2,Google、Mozilla则宣布2017年1月1日起放弃SHA-1。 当然了,在普通民用场合,SHA-1还是可以继续用的,比如校验下载软件之类的,就像早已经被淘汰的MD5。

    var hash = crypto.createHash('sha1');
    hash.update('test');
    console.log(hash.digest('hex'));    // a94a8fe5ccb19ba61c4c0873d391e987982fbbd3
    

    3、SHA-2 SHA-224、SHA-256、SHA-384,和SHA-512并称为SHA-2。 新的哈希函数并没有接受像SHA-1一样的公众密码社区做详细的检验,所以它们的密码安全性还不被大家广泛的信任。 虽然至今尚未出现对SHA-2有效的攻击,它的算法跟SHA-1基本上仍然相似;因此有些人开始发展其他替代的哈希算法。

    var hash = crypto.createHash('sha256');
    hash.update('test');
    console.log(hash.digest('hex'));    // 9f86d081884c7d659a2feaa0c55ad015a3bf4f1b2b0b822cd15d6c15b0f00a08
    

    4、SHA-3 SHA-3,之前名为Keccak算法,是一个加密杂凑算法。 由于对MD5出现成功的破解,以及对SHA-0和SHA-1出现理论上破解的方法,NIST感觉需要一个与之前算法不同的,可替换的加密杂凑算法,也就是现在的SHA-3。

    5、RIPEMD-160 RIPEMD-160 是一个 160 位加密哈希函数。 它旨在用于替代 128 位哈希函数 MD4、MD5 和 RIPEMD。 RIPEMD-160没有输入大小限制,在处理速度方面比SHA2慢。 安全性也没SHA-256和SHA-512好。

    var hash = crypto.createHash('ripemd160');
    hash.update('test');
    console.log(hash.digest('hex'));    // 5e52fee47e6b070565f74372468cdc699de89107
    

    其它加密算法相关
    nodejs除了提供常用加密算法,还提供了HMAC(密钥相关的哈希运算消息认证,类似加盐处理),对称加密算法Cipher(加密)和Decipher(解密),非对称加密算法Signer(签名)和Verify(验证),这里篇幅太长,详细可以参考这几篇讲解得很详细的文章:
    Node.js加密算法库Crypto
    浅谈nodejs中的Crypto模块
    浅谈nodejs中的Crypto模块(补完)

    查找哈希算法

    下面列举几个目前在查找方面比较快的哈希算法(不区分先后),比较老的或者慢的就没举例了,毕竟篇幅有限。

    1、lookup3 Bob Jenkins在1997年发表了一篇关于哈希函数的文章《A hash function for hash Table lookup》,这篇文章自从发表以后现在网上有更多的扩展内容。这篇文章中,Bob广泛收录了很多已有的哈希函数,这其中也包括了他自己所谓的“lookup2”。随后在2006年,Bob发布了lookup3。 Bob很好的实现了散列的均匀分布,但是相对来说比较耗时,它有两个特性,1是具有抗篡改性,既更改输入参数的任何一位都将带来一半以上的位发生变化,2是具有可逆性,但是在逆运算时,它非常耗时。

    2、Murmur3 murmurhash是 Austin Appleby于2008年创立的一种非加密哈希算法,适用于基于哈希进行查找的场景。murmurhash最新版本是MurMurHash3,支持32位、64位及128位值的产生。 MurMur经常用在分布式环境中,比如Hadoop,其特点是高效快速,但是缺点是分布不是很均匀。

    3、FNV-1a FNV又称Fowler/Noll/Vo,来自3位算法设计者的名字(Glenn Fowler、Landon Curt Noll和Phong Vo)。FNV有3种:FNV-0(已过时)、FNV-1、FNV-1a,后两者的差别极小。FNV-1a生成的哈希值有几个特点:无符号整形;哈希值的bits数,是2的n次方(32, 64, 128, 256, 512, 1024),通常32 bits就能满足大多数应用。

    4、CityHash 2011年,google发布CityHash(由Geoff Pike 和Jyrki Alakuijala编写),其性能好于MurmurHash。 但后来CityHash的哈希算法被发现容易受到针对算法漏洞的攻击,该漏洞允许多个哈希冲突发生。

    5、SpookyHash 又是Bob Jenkins哈希牛人的一巨作,于2011年发布的新哈希函数性能优于MurmurHash,但是只给出了128位的输出,后面发布了SpookyHash V2,提供了64位输出。

    6、FarmHash FarmHash也是google发布的,FarmHash从CityHash继承了许多技巧和技术,是它的后继。FarmHash声称从多个方面改进了CityHash。

    7、xxhash xxhash由Yann Collet发表,http://cyan4973.github.io/xxHash/ ,这是它的官网,据说性能很好,似乎被很多开源项目使用,Bloom Filter的首选。

    查找哈希函数的性能比较

    一般性能好的哈希算法都会根据不同系统做优化。 这里有一篇文章详细介绍了各种非加密哈希的性能比较(More Hash Function Tests )。

    文章详细列出了各个平台(甚至包括手机和XBOXOne以及asm.js)之间的哈希算法性能比较,同时也对不同输入数据量做了对比。 似乎在跨平台使用方面CityHash64在64位系统性能最佳,而xxHash32在32位系统性能最好。 在数据量大方面,不同平台也有不同的选择 Intel CPU:总体来说xxhash64更好,随之FarmHash64(如果使用了SSE4.2),xxHash32更适合32位系统。 苹果手机CPU(A9):CityHash64在64位系统性能最佳,而xxHash32在32位系统性能最好。 SpookyV2更适合在XBOXOne中使用。 而短字符串输入使用FNV-1a性能最优(在pc,手机和XBOX中少于8字节,在asm.js中少于20字节),而且它的实现很简单。

    哈希函数的分类

    介绍了那么多哈希函数,实际上哈希函数主要分为以下几类:

    1、加法Hash; 所谓的加法Hash就是把输入元素一个一个的加起来构成最后的结果,prime是素数。

    function addictiveHash(key = '', prime){
        let hash = 0;
        for(let i = 0; i < key.length; ++i){
            hash += key.charCodeAt(i);
        }
    
        return hash % prime;
    }
    
    console.log(addictiveHash('test', 31)); // 14
    console.log(addictiveHash('abc', 31)); // 15
    console.log(addictiveHash('abb', 31)); // 14
    

    2、位运算Hash; 这类型Hash函数通过利用各种位运算(常见的是移位和异或)来充分的混合输入元素。

    function rotatingHash(key = '', prime) {
        let hash = 0;
        for (let i = 0; i < key.length; ++i) {
            hash = (hash << 4) ^ (hash >> 28) ^ key.charCodeAt(i);
        }
        return (hash % prime);
    }
    console.log(rotatingHash('test', 31)); // 13
    console.log(rotatingHash('abc', 31)); // 23
    console.log(rotatingHash('abb', 31)); // 22
    

    3、乘法Hash; 这样的类型的哈希函数利用了乘法的不相关性.乘法哈希里最有名的就是adler32,reactJS的checksum校验就是使用的adler32的改良版。 facebook/react

    function adler32(str) {
        var a = 1, b = 0, L = str.length, M = 0, c = 0, d = 0;
    
        for (var i = 0; i < L;) {
            M = Math.min(L - i, 3850);
            while (M > 0) {
                c = str.charCodeAt(i++);
                if (c < 0x80) { a += c; }
                else if (c < 0x800) {
                    a += 192 | ((c >> 6) & 31); b += a; --M;
                    a += 128 | (c & 63);
                } else if (c >= 0xD800 && c < 0xE000) {
                    c = (c & 1023) + 64; d = str.charCodeAt(i++) & 1023;
                    a += 240 | ((c >> 8) & 7); b += a; --M;
                    a += 128 | ((c >> 2) & 63); b += a; --M;
                    a += 128 | ((d >> 6) & 15) | ((c & 3) << 4); b += a; --M;
                    a += 128 | (d & 63);
                } else {
                    a += 224 | ((c >> 12) & 15); b += a; --M;
                    a += 128 | ((c >> 6) & 63); b += a; --M;
                    a += 128 | (c & 63);
                }
                b += a; --M;
            }
            a = (15 * (a >>> 16) + (a & 65535));
            b = (15 * (b >>> 16) + (b & 65535));
        }
        return ((b % 65521) << 16) | (a % 65521);
    }
    console.log(adler32('test', 31)); // 73204161
    console.log(adler32('abc', 31)); // 38600999
    console.log(adler32('abb', 31)); // 38535462
    

    4、除法Hash; 和乘法一样用了不相关性,但性能不好。

    5、查表Hash; 查表Hash最有名的样例莫过于CRC系列算法。尽管CRC系列算法本身并非查表,可是,查表是它的一种最快的实现方式。以下是CRC32的实现:

    function signed_crc_table() {
    	var c = 0, table = new Array(256);
    
    	for(var n =0; n != 256; ++n){
    		c = n;
    		c = ((c&1) ? (-306674912 ^ (c >>> 1)) : (c >>> 1));
    		c = ((c&1) ? (-306674912 ^ (c >>> 1)) : (c >>> 1));
    		c = ((c&1) ? (-306674912 ^ (c >>> 1)) : (c >>> 1));
    		c = ((c&1) ? (-306674912 ^ (c >>> 1)) : (c >>> 1));
    		c = ((c&1) ? (-306674912 ^ (c >>> 1)) : (c >>> 1));
    		c = ((c&1) ? (-306674912 ^ (c >>> 1)) : (c >>> 1));
    		c = ((c&1) ? (-306674912 ^ (c >>> 1)) : (c >>> 1));
    		c = ((c&1) ? (-306674912 ^ (c >>> 1)) : (c >>> 1));
    		table[n] = c;
    	}
    
    	return typeof Int32Array !== 'undefined' ? new Int32Array(table) : table;
    }
    
    var T = signed_crc_table();
    function crc32(str, seed) {
    	var C = seed ^ -1;
    	for(var i = 0, L=str.length, c, d; i < L;) {
    		c = str.charCodeAt(i++);
    		if(c < 0x80) {
    			C = (C>>>8) ^ T[(C ^ c)&0xFF];
    		} else if(c < 0x800) {
    			C = (C>>>8) ^ T[(C ^ (192|((c>>6)&31)))&0xFF];
    			C = (C>>>8) ^ T[(C ^ (128|(c&63)))&0xFF];
    		} else if(c >= 0xD800 && c < 0xE000) {
    			c = (c&1023)+64; d = str.charCodeAt(i++)&1023;
    			C = (C>>>8) ^ T[(C ^ (240|((c>>8)&7)))&0xFF];
    			C = (C>>>8) ^ T[(C ^ (128|((c>>2)&63)))&0xFF];
    			C = (C>>>8) ^ T[(C ^ (128|((d>>6)&15)|((c&3)<<4)))&0xFF];
    			C = (C>>>8) ^ T[(C ^ (128|(d&63)))&0xFF];
    		} else {
    			C = (C>>>8) ^ T[(C ^ (224|((c>>12)&15)))&0xFF];
    			C = (C>>>8) ^ T[(C ^ (128|((c>>6)&63)))&0xFF];
    			C = (C>>>8) ^ T[(C ^ (128|(c&63)))&0xFF];
    		}
    	}
    	return C ^ -1;
    }
    console.log(crc32('test', 31)); // -804963899
    console.log(crc32('abc', 31)); // 576628111
    console.log(crc32('abb', 31)); // 1431934233
    

    查表Hash中有名的样例有:Universal Hashing和Zobrist Hashing。他们的表格都是随机生成的。

    6、混合Hash; 混合Hash算法利用了以上各种方式。各种常见的Hash算法,比方MD5、Tiger都属于这个范围。它们一般非常少在面向查找的Hash函数里面使用。

    哈希函数的选择

    那么多种哈希函数,我们究竟该选择哪种呢? 不同的应用场景对哈希的算法设计要求也不一样,但一个好的哈希函数应该具备以下三点:

    1. 抗碰撞性,尽量避免冲突。
    2. 抗篡改性,只要改动一个字节,其哈希值也会很大不同。
    3. 查找效率。

    在加密方面,哈希函数应该对抗碰撞性和抗篡改性要求很高,而会牺牲查找效率。 而且随着时代的变化我们最好还是选择更现代化的哈希函数。 目前来说我们可以选择SHA-2族用于安全加密中,SHA-3更安全但对性能损耗更大。更保险的做法是加盐后混合加密。 在nodejs中我们可以很方便地用crypto.pbkdf2()函数加盐加密,默认会调用hmac算法,用sha-1进行加密,并且可以设置迭代次数和密文长度。常用于用户注册和登录校验流程中。下面的例子我们用伪随机函数randomBytes()生成16字节的盐(更安全的做法是多于16字节)

    const crypto = require('crypto');
    
    let txt = 'test';
    
    //通过伪随机码生成salt,进行加密
    crypto.randomBytes(128, function (err, salt) {
        if (err) throw err;
        salt = salt.toString('hex');
        console.log(salt); //生成salt
    
        crypto.pbkdf2(txt, salt, 4096, 256, function (err,hash) {
            if (err) throw err;
            hash = hash.toString('hex');
            console.log(hash);//生成密文
        })
    })
    
    /*
    6e5e20869916c5aea5f6188807abb0dcd83ca0d3c21ec880bab71c483e7cca624af8c5b6fe2ec820e296452e6e43476
    98411aa545d4c3a21056e02659446b694383b3eedd3a7cbcb9592ede2d5875206f6b764fee69e65271c99d73b818837
    9d0c92e345b046d760b84954babd6740b6928e76ef86e9bfd07c2867837678b575
    (node:1264) DeprecationWarning: crypto.pbkdf2 without specifying a digest is deprecated. Please
     specify a digest
    4572e319f6f5e05ee2507dacc43cd9c6f970e1ed37e76c2a86c99afde11c75f35f04322ee3fec4775a21f1181c0e357
    d00bdf1f1aef4cffe9f11f7859fea658df76553ae37deacc5e085d5e7e38a13ec0f7b0d8f29d738f0cd00cddbd74493
    53547eb651244a6c3e599d86878f80e1be2d269afd3d9ea678982150163fa9e61385f40fabedae2403085e8432a723e
    da8693466068523c9e26afdd0764a21d2372bde7f607af6bcbc8fd4a325ad942688ee770efdf038332a470b7ed7c49e
    7c9b0f8d6a1f9557dd51c3747ac4a7ecabda7089d5685403e6af525de5f84d0b4d7a53ea1fb879afa2cfee4a60775b5
    39614ef451de2dd1ca995a14a79c4236d6089
    */
    

    而在查找方面,哈希函数更追求查找的效率和良好的抗碰撞性。 短字符串输入使用FNV-1a,数量大的在32位系统使用xxhash,64位系统使用FarmHash。

    展开全文
  • 计算机安全保密:第七章 密码学 HASH函数.ppt
  • 几种常见hash算法

    千次阅读 2020-08-11 15:08:14
    常用字符串哈希函数 BKDRHash,APHash,DJBHash,JSHash,RSHash,SDBMHash,PJWHash,ELFHash等等 性能 经过比较BKDRHash无论是在实际效果还是编码实现中,效果都是最突出的。APHash也是较为优秀的算法。DJBHash,JS...

    原文链接:https://www.cnblogs.com/qijunhui/p/8445484.html

    常用字符串哈希函数

    BKDRHash,APHash,DJBHash,JSHash,RSHash,SDBMHash,PJWHash,ELFHash等等

    性能

    经过比较BKDRHash无论是在实际效果还是编码实现中,效果都是最突出的。APHash也是较为优秀的算法。DJBHash,JSHash,RSHash与SDBMHash各有千秋。PJWHash与ELFHash效果最差,但得分相似,其算法本质是相似的。

    代码实现

    1.BKDRHash

    /* 【算法】BKDRHash(Java字符串类的Hash算法,累成因子取31)
     * 【说明】累成因子可以为31/131/1313/13131/131313...
     * */
    public class BKDRHash {
        //BKDRHash算法
        static long BKDR_Hash(String str){
            long seed=131;
            long hash=0;
            for(int i=0;i<str.length();i++){
                hash=hash*seed+str.charAt(i);
                //System.out.println(hash);
            }
            return (hash & 0x7FFFFFFF);//32位
            //return (hash & 0x7FFFFFFFFFFFFFFFL);//64位
        }
        //主函数
        public static void main(String[] args) {
            System.out.println(Long.toBinaryString(BKDR_Hash("哈哈哈")));
        }
    }
    

    2.RSHash

    /* 【算法】RSHash(因Robert Sedgwicks在其《Algorithms in C》一书中展示而得名)
     * 【说明】63689和378551都是质数,之所以取这两个数,我想是因为抗碰撞小(散列分布均匀)
     * */
    public class RSHash {
        //RSHash算法
        static long RS_Hash(String str){
            int a=63689;
            int b=378551;
            long hash=0;
            for(int i=0;i<str.length();i++){
                hash=hash*a+str.charAt(i);
                //System.out.println(hash);
                a=a*b;
                //System.out.println(a);
            }
            return (hash & 0x7FFFFFFF);//32位
            //return (hash & 0x7FFFFFFFFFFFFFFFL);//64位
        }
        //主函数
        public static void main(String[] args) {
            System.out.println(Long.toBinaryString(RS_Hash("哈哈")));
        }
    }
    

    3 DJBHash

    /* 【算法】DJBHash(目前公布最有效的Hash算法)
     * 【说明】俗称"Times33"算法
     * */
    public class DJBHash {
        //DJBHash算法
        static long DJB_Hash(String str){
            long hash=5381;
            for(int i=0;i<str.length();i++){
                hash=((hash<<5)+hash)+str.charAt(i);
                //System.out.println(hash);
            }
            return (hash & 0x7FFFFFFF);//32位
            //return (hash & 0x7FFFFFFFFFFFFFFFL);//64位
        }
        //主函数
        public static void main(String[] args) {
            System.out.println(Long.toBinaryString(DJB_Hash("哈哈哈")));
        }
    }
    

    4 JSHash

    /* 【算法】JSHash(由Justin Sobel发明的一种hash算法)
     * 【说明】位操作
     * */
    public class JSHash {
        //JSHash算法
        static long JS_Hash(String str){
            long hash=1315423911;
            for(int i=0;i<str.length();i++){
                hash ^= ((hash << 5) + str.charAt(i) + (hash >> 2));
                //System.out.println(hash);
            }
            return (hash & 0x7FFFFFFF);//32位
            //return (hash & 0x7FFFFFFFFFFFFFFFL);//64位
        }
        //主函数
        public static void main(String[] args) {
            System.out.println(Long.toBinaryString(JS_Hash("哈哈哈")));
        }
    }
    

    5 SDBMHash

    /* 【算法】SDBMHash
     * 【说明】与BKDRHash思想一致,只是数乘因子不同
     * */
    public class SDBMHash {
        //SDBMHash算法
        static long SDBM_Hash(String str){
            long hash=0;
            for(int i=0;i<str.length();i++){
                hash=hash*65599+str.charAt(i);
                //hash=str.charAt(i)+(hash<<6)+(hash<<16)-hash;
                //System.out.println(hash);
            }
            return (hash & 0x7FFFFFFF);//32位
            //return (hash & 0x7FFFFFFFFFFFFFFFL);//64位
        }
        //主函数
        public static void main(String[] args) {
            System.out.println(Long.toBinaryString(SDBM_Hash("哈哈")));
        }
    }
    

    参考

    https://www.cnblogs.com/qijunhui/p/8445484.html
    https://www.cnblogs.com/wanghetao/p/4658471.html

    展开全文
  • 关于哈希函数的构造方法

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

    2015-04-21 15:11:02
    函数可以在输入Hash_QueryParameters.txt文件下,每行为一个数据(可以随便写)输入哈希表中,可以查找,删除,插入等操作
  • C++ hash函数

    千次阅读 2021-07-30 15:12:56
    hash函数介绍: 用途: Hash函数的特性: 参考: hash函数介绍: 哈希函数,又叫散列函数、散列算法,是一种从任何一种数据中创建小的数字“指纹”(也叫做摘要)的方法 用途: 1.快速验证: 生成各种数据...
  • 许多高校和研究机构在这方面都有长期的研究。...一个常见hash函数的例子是md5(),它流行于各种计算机语言和系统。 复制代码 代码如下: $data = “Hello World”; $hash = md5($data); echo $hash; // b1
  • hash函数 实例

    2013-07-19 21:45:31
    hash函数实例 c语言版 不喜勿喷!
  • 第八讲 HASH函数1

    2022-08-04 12:12:30
    二、中国商用密码 三、美国 一、HASH函数的概念 一、Hash函数的概念 一、Hash函数的概念 二、HASH函数的安全性 二、HASH函数的安全性 二、HA
  • hash主要操作函数

    千次阅读 2021-01-26 21:40:20
    hash主要操作函数 hash是一些列key value(field value)的映射表。常常用其存储一些对象实例。相对于把一个对象的各个字段存储为string,存储为hash会占用更少的内存。为什么会更省内存呢?需要搞清楚两个配置(hash-...
  • 什么是 hash 函数,区块链用 hash 函数来干什么 hash 函数 区块数据结构 hash 函数特性 hash 函数和 区块链的联系
  • 基于空间伸缩结构的参数可控的混沌Hash函数,廖东,王小敏,结合并行Hash函数和多混沌的设计思想,提出了一种基于空间伸缩结构的参数可控的混沌Hash函数构造方法。该方法结合空间结构的伸缩特�
  • 各种Hash函数(JAVA版)

    热门讨论 2010-05-20 18:07:10
    RS-Hash Function Value: " + ghl.RSHash(key)); System.out.println(" 2. JS-Hash Function Value: " + ghl.JSHash(key)); System.out.println(" 3. PJW-Hash Function Value: " + ghl.PJWHash(key)); System....
  • php常用hash加密函数

    2020-10-25 05:13:20
    主要介绍了php常用hash加密函数,以实例形式详细分析了PHP的hash加密函数用法,代码中备有详尽的注释,便于理解,需要的朋友可以参考下
  • hash函数 c语言

    2013-07-19 21:43:26
    hash函数 的 c语言版 大家可以试试 不喜勿喷!
  • Python hash函数详解

    千次阅读 2020-10-26 19:39:43
    Python hash函数 hash函数功能介绍 hash() 用于获取取一个对象(字符串或者数值等)的哈希值。 hash函数的参数必须为不可变类型参数 ​ 因为hash值是唯一且不可变的,如果参数值可变,hash也会跟着改变 ​ 所以hash...
  • 常见hash函数算法

    千次阅读 2014-02-21 16:06:57
    散列表,它是基于快速存取的角度设计的,也是一种典型的“空间换时间”的做法。顾名思义,该数据结构可以理解为一个线性表,但是其中的元素不是紧密排列的,...这个映射函数叫做散列函数,存放记录的数组叫做散列表。
  • HashMap源码分析hash函数(扰动函数)

    千次阅读 2021-05-25 21:42:43
    JDK1.7的hash()方法(扰动函数): final int hash(Object k) { int h = hashSeed; if (0 != h && k instanceof String) { return sun.misc.Hashing.stringHash32((String) k); } h ^= k.hashCode(); ...
  • python hash函数_Python hash()函数

    万次阅读 多人点赞 2020-07-13 16:34:52
    python hash函数Python hash() is one of the built-in function. Today we will look into the usage of hash() function and how we can override it for our custom object. Python hash()是内置函数之一。 ...
  • 详解 HashMap 中的 hash 函数

    万次阅读 多人点赞 2018-10-10 23:02:39
    hash 函数,即散列函数,或叫哈希函数。它可以将不定长的输入转变成定长的输出。在 Java 的 HashMap 中,是如何利用 hash 函数来计算 index 的,又是如何解决冲突的问题?本文将为你一一介绍。
  • 为克服现有Hash函数结构的缺陷,结合混沌系统与传统单向Hash函数的优点,提出了一种新的基于混沌消息扩展的Hash函数。该方案沿用传统Hash函数的Merkle-Damgard迭代结构和压缩函数,利用混沌映射网络实现消息扩展,从而...
  • hash函数查找

    2013-04-10 12:52:10
    建立hash函数,随机产生记录到txt文档中,并可从txt文档中读入数据进行查找
  • 单向hash函数

    千次阅读 2017-06-04 15:40:22
    1.1、单向Hash函数的多个名字:压缩函数、缩短函数、消息摘要、指纹、密码校验和、信息完整性检验(DIC)、操作检验码(MDC)。 1.2、功能地位:它是现代密码学的中心。单向Hash函数是许多协议的另一个结构模块。 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 411,661
精华内容 164,664
关键字:

常见的hash函数