-
2021-12-12 16:13:52
哈希算法
-
哈希函数:
在密码学中,哈希函数H是一个公开函数,用于将任意长的消息M映射为较短的、固定长度一个值H(M),作为认证符,称函数值H(M)为哈希值或哈希码或消息摘要。哈希函数的安全性要求给定数据容易计算出哈希值,但给定哈希值不能计算出数据。哈希码提供了一种错误检测能力。
-
使用哈希函数提供消息认证有6种基本使用方式:
(1)消息与哈希码链接后用单钥加密算法加密(2)用单钥加密算法仅对哈希码加密(3)用公钥加密算法和发方的秘密钥仅加密哈希码,这种方法提供了数字签名(4)消息的哈希码值用公钥加密算法和发送方的秘密钥加密后与消息链接,再对链接后的结果用单钥加密算法加密,这种方法提供了保密性和数字签名。(5)通信双方共享一个秘密值S,A计算消息M和秘密值S链接在一起的哈希值,并将此哈希值附加到M后发往B。(6)在(5)中消息与哈希值链接后再增加单钥加密计算,提供保密性。
-
哈希函数需要的条件:
-
函数的输入可以是任意长的。
-
函数的输出是固定长的。
-
已知x,求H(x)较为容易
-
已知h,求使得H(x)=h的x在计算上是不可行的,,满足这一性质称为的哈希函数为单向哈希函数。
-
已知h,求使得h(x)=h的x在计算上是不可行的,满足这一性质称为若单向哈希函数。
-
找出任意两个不同输入的x,y,使得h(x)=h(y)在计算上是不可行的,满足这一性质称为强单向哈希函数。
- 与哈希函数有关的攻击:
第I类生日攻击
第II类生日攻击
- 哈希算法:
哈希函数也称为哈希算法,目前常见的哈希算法有
MD5
哈希算法、SHA
哈希算法等。现在常见的哈希算法都是迭代结构。伪代码如下:CV0 = IV = n比特长的初始值 CVi = f(CVi-1, Yi-1); 1 <= i <= L H(M) = CVL
MD5哈希算法
算法输入为任意长的消息,分为长为512比特的分组,输出为128比特的消息摘要。
- 对消息填充。使得其比特长在模512下为448。
- 附加消息长度。用留下的64比特以
little-endian
方式表示消息被填充前的长度。 - 对MD缓冲区初始化。算法使用128比特长的缓冲区已存储中间结果和最终哈希值,缓冲区表示为4个32比特长的寄存器ABCD,其初始值A=01234567,B=89ABCDEF, C=FEDCBA98,D=76543210。
- 以分组为单位对消息进行处理。每一分租都要经过压缩函数H(哈希函数)MD5的处理,H是算法的核心。其中又有4轮处理过程,如下
- MD5的压缩函数
安全哈希算法SHA
算法输入是小于2^64比特长的任意消息,分为512比特长的分组,输出为160比特长的消息摘要。算法框图与MD5一样,但哈希值的长度和链接变量为160比特。
算法步骤如下:
- 对消息填充。与MD5一样。
- 附加消息长度。与MD5类似,不同之处在于以
big-endian
方式填充。 - 对MD缓冲区初始化。算法使用160比特的缓冲区存储中间结果和最终的哈希值,缓冲区可表示为5个32比特长的寄存器ABCDE,其初始值为A=67452301,B=EFCDAB89,C=98BADCFB,D=10325476,E=C3D2E2F0。
- 以分组为单位对消息进行处理。框图和MD5相似。
ps://blog.csdn.net/lwanttowin/article/details/53726450)
更多相关内容 -
-
基于差异哈希算法的改进非局部均值去噪算法
2021-02-21 23:18:17针对非局部均值(NLM)算法度量邻域块相似度不够准确的缺点,提出了一种基于差异哈希算法与汉明距离的改进NLM算法。传统算法通过欧氏距离度量邻域块之间的相似度,保持边缘和细节的能力较弱,易导致滤波后的图像模糊失真... -
Matlab实现感知哈希算法
2017-11-12 21:21:41参考网上博客的感知哈希算法的理论知识,实现基本的感知哈希算法,内有几张图片用来测试,程序可参考。 -
感知哈希算法(Python版)
2017-04-20 18:50:10Python3实现基于PHA实现图像配准 -
数据依赖的多索引哈希算法
2021-03-16 06:24:17多索引哈希是目前使用最广泛的针对二进制码的索引算法. 由于多索引哈希基于数据集中的二进制码呈均匀... 在大规模数据集上的实验表明,与多索引哈希算法相比数据依赖的多索引哈希算法可以使查询速度提升36.9%–87.4%. -
相似图像搜索的哈希算法思想及实现(差值哈希算法和均值哈希算法)
2021-06-02 13:52:05图像相似度比较哈希算法: 什么是哈希(Hash)? • 散列函数(或散列算法,又称哈希函数,英语:Hash Function)是一种从任何一种数据中创建小 的数字“指纹”的方法。散列函数把消息或数据压缩成摘要,使得数据量变...图像相似度比较哈希算法:
什么是哈希(Hash)?
• 散列函数(或散列算法,又称哈希函数,英语:Hash Function)是一种从任何一种数据中创建小 的数字“指纹”的方法。散列函数把消息或数据压缩成摘要,使得数据量变小,将数据的格式固定 下来。该函数将数据打乱混合,重新创建一个叫做散列值(hash values,hash codes,hash sums, 或hashes)的指纹。散列值通常用一个短的随机字母和数字组成的字符串来代表。
• 通过哈希算法得到的任意长度的二进制值映射为较短的固定长度的二进制值,即哈希值。此外, 哈希值是一段数据唯一且极其紧凑的数值表示形式,如果通过哈希一段明文得到哈希值,哪怕只 更改该段明文中的任意一个字母,随后得到的哈希值都将不同。
• 哈希算法是一个函数,能够把几乎所有的数字文件都转换成一串由数字和字母构成的看似乱码的 字符串。
哈希函数的特点
哈希函数作为一种加密函数,其拥有两个最重要特点:
- 不可逆性。输入信息得出输出的那个看似乱码的字符串(哈希值)非常容易,但是从输出的字符 串反推出输入的结果却是却非常非常难。
- 输出值唯一性和不可预测性。只要输入的信息有一点点区别,那么根据哈希算法得出来的输出值 也相差甚远。
哈希算法的种类
哈希算法是一类算法的总称,共有三种:
- 均值哈希算法aHash
- 差值哈希算法dHash
- 感知哈希算法pHash
汉明距离
两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。
均值哈希算法
步骤:
- 缩放:图片缩放为8*8,保留结构,除去细节。
- 灰度化:转换为灰度图。
- 求平均值:计算灰度图所有像素的平均值。
- 比较:像素值大于平均值记作1,相反记作0,总共64位。
- 生成hash:将上述步骤生成的1和0按顺序组合起来既是图片的指纹(hash)。
- 对比指纹:将两幅图的指纹对比,计算汉明距离,即两个64位的hash值有多少位是不一样的,不 相同位数越少,图片越相似。
差值哈希算法
差值哈希算法相较于均值哈希算法,前期和后期基本相同,只有中间比较hash有变化。
步骤:
- 缩放:图片缩放为8*9,保留结构,除去细节。
- 灰度化:转换为灰度图。
- 求平均值:计算灰度图所有像素的平均值。
- 比较:像素值大于后一个像素值记作1,相反记作0。本行不与下一行对比,每行9个像素, 八个差值,有8行,总共64位
- 生成hash:将上述步骤生成的1和0按顺序组合起来既是图片的指纹(hash)。
- 对比指纹:将两幅图的指纹对比,计算汉明距离,即两个64位的hash值有多少位是不一样 的,不相同位数越少,图片越相似。
感知哈希算法
均值哈希算法过于严格,不够精确,更适合搜索缩略图,为了获得更精确的结果可以选择感知哈希 算法,它采用的是DCT(离散余弦变换)来降低频率的方法。
步骤:
- 缩小图片:32 * 32是一个较好的大小,这样方便DCT计算
- 转化为灰度图:把缩放后的图片转化为灰度图。
- 计算DCT:DCT把图片分离成分率的集合
- 缩小DCT:DCT计算后的矩阵是32 * 32,保留左上角的8 * 8,这些代表图片的最低频率。
- 计算平均值:计算缩小DCT后的所有像素点的平均值。
- 进一步减小DCT:大于平均值记录为1,反之记录为0.
- 得到信息指纹:组合64个信息位,顺序随意保持一致性。
- 最后比对两张图片的指纹,获得汉明距离即可。
代码实现:均值哈希算法和差值哈希算法
import cv2 import numpy as np #均值哈希算法 def aHash(img): #缩放为8*8 img=cv2.resize(img,(8,8),interpolation=cv2.INTER_CUBIC) #转换为灰度图 gray=cv2.cvtColor(img,cv2.COLOR_BGR2GRAY) #s为像素和初值为0,hash_str为hash值初值为'' s=0 hash_str='' #遍历累加求像素和 for i in range(8): for j in range(8): s=s+gray[i,j] #求平均灰度 avg=s/64 #灰度大于平均值为1相反为0生成图片的hash值 for i in range(8): for j in range(8): if gray[i,j]>avg: hash_str=hash_str+'1' else: hash_str=hash_str+'0' return hash_str #差值感知算法 def dHash(img): #缩放8*9 img=cv2.resize(img,(9,8),interpolation=cv2.INTER_CUBIC) #转换灰度图 gray=cv2.cvtColor(img,cv2.COLOR_BGR2GRAY) hash_str='' #每行前一个像素大于后一个像素为1,相反为0,生成哈希 for i in range(8): for j in range(8): if gray[i,j]>gray[i,j+1]: hash_str=hash_str+'1' else: hash_str=hash_str+'0' return hash_str #Hash值对比 def cmpHash(hash1,hash2): n=0 #hash长度不同则返回-1代表传参出错 if len(hash1)!=len(hash2): return -1 #遍历判断 for i in range(len(hash1)): #不相等则n计数+1,n最终为相似度 if hash1[i]!=hash2[i]: n=n+1 return n img1=cv2.imread('lenna.png') img2=cv2.imread('lenna_noise.png') hash1= aHash(img1) hash2= aHash(img2) print(hash1) print(hash2) n=cmpHash(hash1,hash2) print('均值哈希算法相似度:',n) hash1= dHash(img1) hash2= dHash(img2) print(hash1) print(hash2) n=cmpHash(hash1,hash2) print('差值哈希算法相似度:',n)
运行结果:
输入:
输出:
图像相似度比较哈希算法
三种算法的比较:
• aHash:均值哈希。速度比较快,但是常常不太精确。
• pHash:感知哈希。精确度较高,但是速度方面较差一些。
• dHash:差值哈希。精确度较高,且速度也非常快。
• 均值哈希本质上是对颜色的比较;
• 感知哈希由于做了 DCT 操作,本质上是对频率的比较;
• 差值哈希本质上是基于渐变的感知哈希算法。 -
哈希算法(Matlab和C语言版)
2021-11-14 09:41:28此压缩包有关于哈希算法的资料介绍以及其在Matlab和Visual studio中的代码实现。 -
c#哈希算法的实现方法及思路
2020-09-04 20:30:07主要介绍了c#哈希算法的实现方法及思路,有需要的朋友可以参考一下 -
哈希算法C语言实现
2016-02-17 12:56:54哈希算法C语言实现 -
makeCRC_哈希算法_简单的CRC16算法_数据校验_
2021-10-01 15:48:27CRC16算法,哈希算法,用于数据传输校验 -
SHA-1密码哈希算法(c语言实现)
2020-04-05 14:40:51本人为在校大学生,所写源码可能不够尽善尽美,希望各位包涵指正。写这个代码只是为了练手,可能有错误,只为大家提供思路和方法。 -
基于一致性哈希算法的分布式数据库高效扩展方法.pdf
2021-08-08 22:06:09#资源达人分享计划# -
一种稳健的紧凑图像哈希算法
2021-02-04 08:07:34为克服此类问题, 设计了基于改进的局部二值模式(LBP)算子与动态更新变换的紧凑图像哈希算法。引入线性插值技术, 对输入图像实现预处理, 改善哈希序列对尺度缩放的稳健性。利用Ring分割, 将插值图像转化成二次图像。... -
基于点对相似度的深度非松弛哈希算法
2021-04-17 03:20:24本文提出了一种基于点对相似度的深度非松弛哈希算法, 在卷积神经网络的输出端使用可导的软阈值函数代替传统方法中所用的符号函数使准哈希码非线性接近−1或1, 将网络输出的结果直接用于计算训练误差, 在损失函数中... -
sm3哈希算法.rar
2020-12-26 01:37:11sm3哈希算法.rar -
MD5_哈希算法_md5_
2021-10-04 04:16:30MD5哈希算法, 任意长度数据提取出固定长度的数组,MD5 hash algorithm -
哈希算法_蒟蒻学习笔记
2021-02-23 18:38:38哈希 -
用Python实现通过哈希算法检测图片重复的教程
2020-09-22 07:23:49主要介绍了用Python实现通过哈希算法检测图片重复的教程,这个方法被Iconfinder用作防盗版技术,需要的朋友可以参考下 -
基于一致性哈希算法的区块链优化模型.pdf
2021-08-15 23:09:36#资源达人分享计划# -
一致性哈希算法演示.rar
2019-12-04 17:22:29运行平台:VS 2019 一致性哈希算法演示项目,演示新增节点key分布情况;移除节点key分布情况! C#,C#,C#....... -
数据结构之哈希算法
2022-03-04 18:18:091:什么是哈希算法? 将一个任意长度的二进制串映射为固定长度的二进制串的算法,我们叫做是哈希算法,其中固定长度的二进制串结果叫做哈希值。 比如md5算法就是一种哈希算法,md5算法将任意长度的二进制串映射为...1:什么是哈希算法?
将一个任意长度的二进制串映射为固定长度的二进制串的算法,我们叫做是哈希算法,其中固定长度的二进制串结果叫做哈希值。
比如md5算法就是一种哈希算法,md5算法将任意长度的二进制串映射为长度128bit的二进制串。
2:一个合格的哈希算法需要满足哪些条件?
1:哈希冲突概率极低 2:差别很小的原始串哈希的结果差别也要很大 3:哈希计算速度快(如md5算法加密4000个字左右的汉字只需要1ms左右) 4:无法反向从哈希值推到出原始值
3:哈希算法都有哪些应用?
A:加密(密码存储) B:唯一标示(数据库主键,文件存储) C:数据校验(接口请求数据有效性) D:散列函数(散列表生成散列值) E:负载均衡 F:数据分片 G:分布式存储
4:为什么哈希算法无法做到无冲突?
借鉴
鸽巢原理(抽屉原理)
,假设有10个鸽巢,11只鸽子,每个鸽子下一个鸽子蛋,则至少有一个鸽巢鸽子蛋的数量不少于2
,在1:什么是哈希算法?
部分我们分析了哈希算法的定义,从中可以看出哈希值是一个定长的结果,因此哈希值结果个数必定存在上限,比如md5算法,哈希值长度为128bit,也就是哈希值一共有2^128次方个可能的值,则根据鸽巢原理
,当有2^128+1
个原始串时,必定会出现冲突,但是出现冲突的概率极低。5:哈希算法在分布式的应用实例
为了提高系统的查询性能,我们现在需要构建一个分布式的缓存系统,前端系统通过分布式缓存系统来获取数据,可以达到减少数据库查询的目的,架构如下图:
这样子,一个简单的分布式缓存系统就构建完毕了,注意图中的
步骤2
,假设我们使用的是md5算法执行哈希,则可能的代码如下:class FakeCls { int hash(String userId) { // 分布式缓存系统中一共有10个节点 int cacheSystemNodeNum = 10; return Md5(userId) % cacheSystemNodeNum; } }
需要注意,哈希值的计算严重依赖于了分布式缓存系统中节点的个数,当节点个数发生变更时,该函数的结果必定发生比较大的变化,从而造成将请求分配到了无对应缓存数据的节点,此时大量的请求都会打到DB,从而造成缓存雪崩的发生。
延伸知识:缓存雪崩,缓存击穿,缓存穿透。
缓存雪崩:当突然大规模的出现无法从缓存中获取数据的情况时,请求全部打到了DB,从而造成DB的宕机,这是缓存雪崩。
缓存击穿:当某个热点key失效,导致获取该热点key的请求打到DB,这是缓存击穿。
缓存穿透:当查询的key在缓存中不可能存在,此时一定会将请求打到DB,这是缓存穿透。
想要解决这个问题就不能使用普通的哈希函数,而需要考虑使用一致性哈希了,关于一致性哈希具体参考
6:一致性哈希
,使用一致性hash后,步骤2的伪代码如下:class FakeCls { int hash(String userId) { return someConsistencyHash(userId); } }
这样,当节点发生变更,影响的也只是部分键哈希的结果,不会造成特别严重的后果,经过一段时间的自动预热
(即将缓存中不存在key查询之后放到缓存中)
之后,就能恢复正常了。6:一致性哈希
一致性哈希依赖于哈希环,哈希环是一个具有一定范围的环,机器节点和数据都会被映射到环上的某个位置,如下是一个范围是[1,10000]的环:
比如我们现在有三个节点,哈希值分别如下:
节点1:508 节点2:6010 节点3:2056
则我们将这三个节点映射到哈希环上之后,如下图:
接下来数据查找过程是这样子的,首先经过哈希函数获取[1,10000]内的一个数字,按照如下两种情况处理:
1:如果是当前哈希值对应的位置恰好有映射的节点,则使用该节点查询数据 2:如果是当前哈希值没有映射的节点,则顺时针旋转,使用第一个遇到的节点,作为目标节点来查询数据
比如我们现在要查询
用户ID=20201303-1
对应的用户信息,假设hash(20201303-1)=5632,则会使用节点2,来作为目标节点查找数据,这个过程如下图:但是此时还是有一个问题,那就是,
节点映射是失衡的
,如下的映射关系:[509,2056]映射到node3,可映射的哈希值个数为1548。 [2057,6010]映射到node2,可映射哈希值个数为3954。 [6011,10000],[1,508]映射到node1,可映射的哈希值个数是4498。
则映射到各个节点的比例为
node1:node2:node3=4498:3954:1548
,可以看到这个比例并不是接近1:1:1
的,为了解决这个问题,我们可以将这3个节点都克隆若干份,然后再映射到哈希环上,这个克隆的副本我们叫做是虚拟机节点
,增加虚拟节点后哈希环可能如下:这样子就能解决映射不均匀的问题了。回过头看,在
5:哈希算法在分布式的应用实例
我们提到可以使用一致性哈希来解决机器节点个数发生改变导致的雪崩问题,这是为什么呢?接上图,假设我们现在增加了节点4,哈希环变为下图:此时受影响的哈希范围是[2057,2789],原来是映射到node1,现在映射到node4,[6529,7923]原来映射到node3,现在映射到node4,可以看到影响的范围还是比较小的,基于此来解决缓存雪崩问题。
以上使用虚拟节点的算法其实是
ketama
一致性哈希算法。 -
最快的排序算法 java实现哈希算法-Java–哈希算法–最快的实现,排序算法数据结构
2022-04-07 15:14:46最快的排序算法 java实现哈希算法-Java–哈希算法–最快的实现,排序算法数据结构 -
一致性哈希算法以及其PHP实现详细解析
2020-12-19 08:37:58在做服务器负载均衡时候可供选择的负载均衡的算法有很多,包括: 轮循算法(Round Robin)、哈希算法(HASH)、最少连接算法(Least Connection)、响应速度算法(Response Time)、加权法(Weighted )等。... -
php-perl哈希算法实现(times33哈希算法)
2020-10-26 11:20:34php-perl哈希实现算法–DJBX33A(Daniel J. Bernstein, Times 33 with Addition)APR哈希默认算法 -
密码学系列 – 哈希算法
2021-01-08 04:31:40哈希算法 哈希算法将任意长度的二进制值映射为较短的固定长度的二进制值,这个小的二进制值称为哈希值。哈希值是一段数据唯一且极其紧凑的数值表示形式。如果散列一段明文而且哪怕只更改该段落的一个字母,随后的... -
wossl:OpenSSL对称算法、哈希校验、非对称算法、证书管理、SSL安全
2021-05-14 10:46:13OpenSSL管理平台为OpenSSL操作提供可视化的界面,方便快捷地完成对称算法、哈希校验、非对称算法、证书管理、SSL安全等操作。 功能模块: 对称算法:AES、DES、Triple DES。 哈希校验:MD2、MD4、MD5、SHA1、SHA224... -
银联卡哈希算法
2018-08-07 09:33:02哈希算法即通过将单向数学函数应用到任意数量的数据所得到的固定大小的结果。它是一种单向密 码体制,即它是一个从明文到密文的不可逆的映射,只有加密过程,没有解密过程。典型哈希算法如MD5、 SHA-1、SHA-2、SM3等。... -
基于局部敏感哈希算法的图像高维数据索引技术的研究 (2013年)
2021-06-12 21:43:26局部敏感哈希(LSH)算法是有效的高维数据索引方法之一,该算法成功地解决了“维数灾难”问题。分析了LSH算法中主要参数对索引性能的影响,在规模不同的图像数据集上应用了LSH算法,实验结果表明选择合适的参数时,其性能... -
感知哈希算法
2016-11-30 19:40:12MATLAB实现的感知哈希算法,用于判断两幅图片的相似度,返回为两幅图片的汉明距离 -
OpenCvSharp 图像拼接 OpenCV感知哈希算法进行图片相似度对比
2018-08-07 16:49:57利用OpenCvSharp实现感知哈希算法进行图片相似度对比及Stitcher类图像拼接生成全景图像 vs2015环境