精华内容
下载资源
问答
  • 哈希中压缩函数是什么
    千次阅读
    2020-09-25 11:45:24

    Hash函数译为哈希函数,又称散列函数。是把任意长度的输入,通过散列算法,变换成固定长度的输出,该输出的值称为散列值或消息摘要。简单来说就是一种将任意长度的输入消息压缩成某一固定长度的消息摘要的函数

     

    它具备以下的性质(哈希函数所必须的性质):

    1. H可应用于任意大小的数据块。
    2. H产生定长的输出。
    3. 对任意给定的x,计算H(x)比较容易,用硬件和软件均可以实现。

    出于安全性考虑,对哈希函数的三个安全性假设:

    1. 对任意给定的散列值h,找到满足H(x)=h的x在计算上是不可行的,称之为单向性。
    2. 对任意给定的分组x,找到满足y≠x,且H(x)=H(y)的y在计算上是不可行的,称之为抗弱碰撞性。
    3. 找到任何满足H(x)=H(y)的偶对x=y在计算上是不可行的,称之为抗强碰撞性。

    满足这三个安全性假设的安全Hash函数称作碰撞稳固的Hash函数。

    更多相关内容
  • 密码学哈希函数 什么是哈希函数? (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....

    密码学哈希函数

    什么是哈希函数? (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. Also, it should be noted that the input value for the hash functions can be of arbitrary length, but the output text that it will produce will always be of fixed length.

    哈希函数是一种数学函数,可将数字值转换为另一个压缩数字值。 因此,它压缩文本。 另外,应注意,哈希函数的输入值可以是任意长度,但是它将产生的输出文本始终是固定长度。

    Representation of the hash function:

    哈希函数的表示形式:

    The hash functions are usually represented through capital H symbol,

    哈希函数通常用大写的H符号表示,

        H (M) = C
    
    

    Here,

    这里,

    • H() denotes the hash function.

      H()表示哈希函数。

    • M denotes the input value (in numeric form)

      M表示输入值(数字形式)

    • And, C denotes the compressed output value, also in numeric form.

      并且, C也以数字形式表示压缩输出值。

    哈希函数的属性 (Properties of Hash Functions)

    1. Compressed output

      压缩输出

      The hash function always produces a compressed value of the input provided to it.

      哈希函数始终会产生提供给它的输入的压缩值。

    2. Fixed Length Output

      定长输出

      No matter what may be the length of the input value to the hash function, the output that it produces is always of fixed length.

      无论哈希函数的输入值的长度是多少,它生成的输出始终是固定长度的。

    3. Pre-Image Resistance

      像前电阻

      It is computationally hard to reverse a Hash function. This is due to its compressive nature.

      在计算上很难逆转哈希函数。 这是由于其压缩性质。

      H (X) = Z

      H(X)= Z

      Suppose we are provided the

      假设我们提供了

      Z value, then it is almost impossible to predict the input value X. This protects the system and data from hackers and attackers who have a hash value and are trying to find the input.

      Z值,那么几乎不可能预测输入值X。 这样可以保护系统和数据免受具有哈希值并试图查找输入的黑客和攻击者的侵害。

    4. Second pre-Image Resistance

      二次成像前电阻

      As the hash functions are compression function with a fixed-length output, it is very hard (almost practically impossible) to have the same hash values for two values. This means that our function also provides us the security from the brute force attacks, because:

      由于哈希函数是具有固定长度输出的压缩函数,因此很难为两个值具有相同的哈希值(几乎几乎是不可能的)。 这意味着我们的职能还为我们提供了免受暴力攻击的安全性,因为:

      H (x) ≠ H (y).

      H(x)≠H(y)

    5. Collision Resistance

      耐碰撞

      As it is extremely hard to find the second pre-Image of the hash function, this implies that it is rare (almost impossible) for the Hash function to have a collision. Therefore, the hash function is almost collision-free.

      由于很难找到哈希函数的第二个pre-Image,这意味着哈希函数很少(几乎不可能)发生冲突。 因此,哈希函数几乎没有冲突。

    哈希函数的应用和使用 (Applications and uses of the hash functions)

    1. Encryption techniques: Due to the irreversible nature and collision-free properties, the hash function finds its wide use in the advanced encryption techniques used nowadays for ensuring data security and privacy.

      加密技术 :由于不可逆的性质和无冲突的特性,哈希函数在当今用于确保数据安全性和隐私性的高级加密技术中得到了广泛的应用。

    2. Used for authentications and integrity checks.

      用于身份验证和完整性检查

    3. To minimize the storage space: As the Hash function is compressive, it takes less amount of space to store the hash value than the original space. This provides us with an efficient way to store our data.

      最小化存储空间 :由于哈希函数具有压缩性,因此存储哈希值所需的空间要少于原始空间。 这为我们提供了一种存储数据的有效方法。

    哈希函数的缺点 (Drawbacks of the Hash Functions)

    1. Data retrieval almost impossible:

      数据检索几乎是不可能的

      If you want to store the data in compressed form to minimize space allocation, you can do it with Hash functions but you cannot retrieve back the data in its original form. Therefore, it is better to compress those values using hash functions which will later not be required in its original form and will be required only to check the integrity and correctness.

      如果要以压缩形式存储数据以最大程度地减少空间分配,则可以使用哈希函数进行处理,但是无法以原始形式检索回数据。 因此,最好使用散列函数压缩这些值,这些散列函数以后将不再需要其原始形式,而仅在检查完整性和正确性时才需要。

    2. Complexity:

      复杂度

      The Hash functions are very complex to understand and implement.

      哈希函数很难理解和实现。

    翻译自: https://www.includehelp.com/cryptography/hash-function.aspx

    密码学哈希函数

    展开全文
  • 什么是哈希Hash(散列函数)

    千次阅读 2019-07-04 16:02:00
    Hash(散列函数) Hash,一般翻译做散列、杂凑,或音译为哈希,是把任意长度的输入(又叫做预映射pre-image)通过散列算法变换成...简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数 基本...

    Hash(散列函数)

    Hash,一般翻译做散列、杂凑,或音译为哈希,是把任意长度的输入(又叫做预映射pre-image)通过散列算法变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,所以不可能从散列值来确定唯一的输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数

    基本概念

    编辑
    若结构中存在和关键字K相等的记录,则必定在f(K)的 存储位置上。由此,不需比较便可直接取得所查记录。称这个对应关系f为 散列函数(Hash function),按这个事先建立的表为 散列表
    对不同的关键字可能得到同一散列地址,即key1≠key2,而f(key1)=f(key2),这种现象称碰撞。具有相同函数值的关键字对该散列函数来说称做 同义词。综上所述,根据散列函数H(key)和处理冲突的方法将一组关键字映射到一个有限的连续的地址集(区间)上,并以关键字在地址集中的“象” 作为记录在表中的存储位置,这种表便称为 散列表,这一映象过程称为散列造表或 散列,所得的存储位置称散列地址。
    若对于 关键字集合中的任一个关键字,经 散列函数映象到地址集合中任何一个地址的概率是相等的,则称此类散列函数为均匀散列函数(Uniform Hash function),这就是使关键字经过散列函数得到一个“随机的地址”,从而减少冲突。
    性质
    所有 散列函数都有如下一个基本特性:如果两个散列值是不相同的(根据同一函数),那么这两个散列值的原始输入也是不相同的。这个特性是散列函数具有确定性的结果。但另一方面,散列函数的输入和输出不是一一对应的,如果两个散列值相同,两个输入值很可能是相同的,但不绝对肯定二者一定相等(可能出现哈希碰撞)。输入一些数据计算出散列值,然后部分改变输入值,一个具有强混淆特性的散列函数会产生一个完全不同的散列值。  [1] 
    典型的散列函数都有无限定义域,比如任意长度的字节字符串,和有限的值域,比如固定长度的比特串。在某些情况下,散列函数可以设计成具有相同大小的定义域和值域间的一一对应。一一对应的散列函数也称为排列。可逆性可以通过使用一系列的对于输入值的可逆“混合”运算而得到。
    常用HASH函数
    散列函数能使对一个数据序列的访问过程更加迅速有效,通过散列函数, 数据元素将被更快地定位。常用Hash函数有:
    1. 直接寻址法。取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a·key + b,其中a和b为常数(这种散列函数叫做自身函数)
    2. 数字分析法。分析一组数据,比如一组员工的出生年月日,这时我们发现出生年月日的前几位数字大体相同,这样的话,出现冲突的几率就会很大,但是我们发现年月日的后几位表示月份和具体日期的数字差别很大,如果用后面的数字来构成散列地址,则冲突的几率会明显降低。因此数字分析法就是找出数字的规律,尽可能利用这些数据来构造冲突几率较低的散列地址。
    3. 平方取中法。取关键字平方后的中间几位作为散列地址。
    4. 折叠法。将关键字分割成位数相同的几部分,最后一部分位数可以不同,然后取这几部分的叠加和(去除进位)作为散列地址。
    5. 随机数法。选择一随机函数,取关键字作为随机函数的种子生成随机值作为散列地址,通常用于关键字长度不同的场合。
    6. 除留余数法。取关键字被某个不大于 散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p,p<=m。不仅可以对关键字直接取模,也可在折叠、平方取中等运算之后取模。对p的选择很重要,一般取素数或m,若p选的不好,容易产生碰撞。
    处理冲突方法
    1. 开放寻址法;Hi=(H(key) + di) MOD m,i=1,2,…,k(k<=m-1),其中H(key)为 散列函数,m为 散列表长,di为增量序列,可有下列三种取法:
    1). di=1,2,3,…,m-1,称线性探测再散列;
    2). di=1^2,-1^2,2^2,-2^2,3^2,…,±k^2,(k<=m/2)称二次探测再散列;
    3). di= 伪随机数序列,称伪随机探测再散列。
    2. 再 散列法:Hi=RHi(key),i=1,2,…,k RHi均是不同的散列函数,即在同义词产生地址冲突时计算另一个散列函数地址,直到冲突不再发生,这种方法不易产生“聚集”,但增加了计算时间。
    3. 链地址法(拉链法)
    4. 建立一个公共溢出区
    查找性能分析
    散列表的查找过程基本上和造表过程相同。一些关键码可通过 散列函数转换的地址直接找到,另一些关键码在散列函数得到的地址上产生了冲突,需要按处理冲突的方法进行查找。在介绍的三种处理冲突的方法中,产生冲突后的查找仍然是给定值与关键码进行比较的过程。所以,对散列表查找效率的量度,依然用 平均查找长度来衡量。
    查找过程中,关键码的比较次数,取决于产生冲突的多少,产生的冲突少,查找效率就高,产生的冲突多,查找效率就低。因此,影响产生冲突多少的因素,也就是影响查找效率的因素。影响产生冲突多少有以下三个因素:
    1.散列函数是否均匀;
    2. 处理冲突的方法;
    3. 散列表的装填因子。
    散列表的装填因子定义为:α= 填入表中的元素个数/散列表的长度
    α是散列表装满程度的标志因子。由于表长是定值,α与“填入表中的元素个数”成正比,所以,α越大,填入表中的元素较多,产生冲突的可能性就越大;α越小,填入表中的元素较少,产生冲突的可能性就越小。
    实际上,散列表的 平均查找长度是装填因子α的函数,只是不同处理冲突的方法有不同的函数。
    了解了hash基本定义,就不能不提到一些著名的hash算法, MD5SHA-1可以说是应用最广泛的 Hash算法,而它们都是以 MD4为基础设计的。
    常用hash算法的介绍:
    (1)MD4
    MD4(RFC 1320)是 MIT 的 Ronald L. Rivest在 1990 年设计的,MD 是 Message Digest( 消息摘要) 的缩写。它适用在32位 字长的处理器上用高速软件实现——它是基于 32 位操作数的位操作来实现的。
    (2) MD5
    MD5(RFC 1321)是 Rivest 于1991年对MD4的改进版本。它对输入仍以512位分组,其输出是4个32位字的级联,与 MD4 相同。MD5比MD4来得复杂,并且速度较之要慢一点,但更安全,在抗分析和抗差分方面表现更好。
    (3) SHA-1及其他
    SHA1是由NIST NSA设计为同DSA一起使用的,它对长度小于2^64的输入,产生长度为160bit的散列值,因此抗穷举(brute-force)性更好。SHA-1 设计时基于和MD4相同原理,并且模仿了该算法。  [2] 
    散列函数应用
    由于 散列函数的应用的多样性,它们经常是专为某一应用而设计的。例如, 加密散列函数假设存在一个要找到具有相同散列值的原始输入的敌人。一个设计优秀的加密散列函数是一个“单向”操作:对于给定的散列值,没有实用的方法可以计算出一个原始输入,也就是说很难伪造。为加密散列为目的设计的函数,如MD5,被广泛的用作检验散列函数。这样软件下载的时候,就会对照验证代码之后才下载正确的文件部分。此代码有可能因为环境因素的变化,如机器配置或者IP地址的改变而有变动。以保证源文件的安全性。
    错误监测和修复函数主要用于辨别数据被随机的过程所扰乱的事例。当散列函数被用于 校验和的时候,可以用相对较短的散列值来验证任意长度的数据是否被更改过。
    错误校正
    使用一个 散列函数可以很直观的检测出数据在传输时发生的错误。在数据的发送方,对将要发送的数据应用散列函数,并将计算的结果同原始数据一同发送。在数据的接收方,同样的散列函数被再一次应用到接收到的数据上,如果两次散列函数计算出来的结果不一致,那么就说明数据在传输的过程中某些地方有错误了。这就叫做 冗余校验
    对于错误校正,假设相似扰动的分布接近最小(a distribution of likely perturbations is assumed at least approximately)。对于一个信息串的微扰可以被分为两类,大的(不可能的)错误和小的(可能的)错误。我们对于第二类错误重新定义如下,假如给定 H(x) 和 x+s,那么只要s足够小,我们就能有效的计算出x。那样的 散列函数被称作错误校正编码。这些错误校正编码有两个重要的分类:循环冗余校验和 里德所罗门码。
    语音识别
    对于像从一个已知列表中匹配一个MP3文件这样的应用,一种可能的方案是使用传统的散列函数——例如MD5,但是这种方案会对时间平移、CD读取错误、不同的音频压缩算法或者音量调整的实现机制等情况非常敏感。使用一些类似于MD5的方法有利于迅速找到那些严格相同(从音频文件的二进制数据来看)的音频文件,但是要找到全部相同(从音频文件的内容来看)的音频文件就需要使用其他更高级的算法了。
    那些并不紧随IT工业潮流的人往往能反其道而行之,对于那些微小差异足够 鲁棒散列函数确实存在。现存的绝大多数散列算法都是不够鲁棒的,但是有少数散列算法能够达到辨别从嘈杂房间里的扬声器里播放出来的音乐的鲁棒性。有一个实际的例子是Shazam[1]服务。用户可以用电话机拨打一个特定的号码,并将电话机的话筒靠近用于播放音乐的扬声器。该项服务会分析正在播放的音乐,并将它于存储在数据库中的已知的散列值进行比较。用户就能够收到被识别的音乐的曲名(需要收取一定的费用)
    信息安全
    Hash算法在信息安全方面的应用主要体以下的3个方面:
    (1) 文件校验
    我们比较熟悉的校验算法有 奇偶校验和CRC校验,这2种校验并没有抗 数据篡改的能力,它们一定程度上能检测并纠正数据传输中的信道误码,但却不能防止对数据的恶意破坏。
    MD5 Hash算法的"数字指纹"特性,使它成为应用最广泛的一种文件完整性 校验和(Checksum)算法,不少Unix系统有提供计算md5 checksum的命令。
    (2) 数字签名
    Hash 算法也是现代密码体系中的一个重要组成部分。由于 非对称算法的运算速度较慢,所以在数字签名协议中, 单向散列函数扮演了一个重要的角色。对 Hash 值,又称" 数字摘要"进行数字签名,在统计上可以认为与对文件本身进行数字签名是等效的。而且这样的协议还有其他的优点。
    (3) 鉴权协议
    如下的鉴权协议又被称作挑战--认证模式:在传输信道是可被侦听,但不可被篡改的情况下,这是一种简单而安全的方法。以上就是一些关于hash以及其相关的一些基本预备知识。
    哈希函数
    (1)余数法:先估计整个哈希表中的表项目数目大小。然后用这个估计值作为除数去除每个原始值,得到商和余数。用余数作为哈希值。因为这种方法产生冲突的可能性相当大,因此任何搜索算法都应该能够判断冲突是否发生并提出取代算法。  [3] 
    (2)折叠法:这种方法是针对原始值为数字时使用,将原始值分为若干部分,然后将各部分叠加,得到的最后四个数字(或者取其他位数的数字都可以)来作为哈希值。
    (3)基数转换法:当原始值是数字时,可以将原始值的数制基数转为一个不同的数字。例如,可以将十进制的原始值转为十六进制的哈希值。为了使哈希值的长度相同,可以省略高位数字。
    (4)数据重排法:这种方法只是简单的将原始值中的数据打乱排序。比如可以将第三位到第六位的数字逆序排列,然后利用重排后的数字作为哈希值。
    哈希函数并不通用,比如在数据库中用能够获得很好效果的哈希函数,用在密码学或错误校验方面就未必可行。在密码学领域有几个著名的哈希函数。这些函数包括MD2、MD4以及MD5,利用散列法将数字签名转换成的哈希值称为信息摘要(message-digest),另外还有 安全散列算法(SHA),这是一种标准算法,能够生成更大的(60bit)的信息摘要,有点儿类似于MD4算法。
    文件的hash值
    大家都知道emule是基于P2P (Peer-to-peer的缩写,指的是对等体网络下客户到客户文件传输的软件), 它采用了"多源文件传输协议”( MFTP,the Multisource FileTransfer Protocol)。在协议中,定义了一系列传输、压缩和打包还有积分的标准,emule 对于每个文件都有md5-hash的算法设置,这使得该文件,并且在整个网络上都可以追踪得到。
    MD5-Hash-文件的数字文摘通过Hash函数计算得到。不管文件长度如何,它的Hash函数计算结果是一个固定长度的数字。与 加密算法不同,这一个Hash算法是一个不可逆的 单向函数。采用安全性高的Hash算法,如MD5、SHA时,两个不同的文件几乎不可能得到相同的Hash结果。因此,一旦文件被修改,就可检测出来。
    当我们的文件放到emule里面进行共享发布的时候, emule会根据 hash算法自动生成这个文件的hash值,他就是这个文件的身份标志,它包含了这个文件的基本信息,然后把它提交到所连接的服务器。当有他人想对这个文件提出下载请求的时候, 这个hash值可以让他人知道他正在下载的文件是不是就是他所想要的。尤其是在文件的其他属性被更改之后(如名称等)这个值就更显得重要。而且服务器还提供了,这个文件当前所在的用户的地址,端口等信息,这样emule就知道到哪里去下载了。
    一般来讲我们要搜索一个文件,emule在得到了这个信息后,会向被添加的服务器发出请求,要求得到有相同hash值的文件。而服务器则返回持有这个文件的用户信息。这样我们的客户端就可以直接的和拥有那个文件的用户沟通,看看是不是可以从他那里下载所需的文件。
    对于emule中文件的hash值是固定的,也是的,它就相当于这个文件的信息摘要,无论这个文件在谁的机器上,他的hash值都是不变的,无论过了多长时间,这个值始终如一,当我们在进行文件的下载上传过程中,emule都是通过这个值来确定文件。
    hash文件
    我们经常在emule日志里面看到,emule正在hash文件,这里就是利用了hash算法的 文件校验性这个功能了,文章前面已经说了一些这些功能,其实这部分是一个非常复杂的过程,在ftp,bt等软件里面都是用的这个基本原理,emule里面是采用文件分块传输,这样传输的每一块都要进行对比校验,如果错误则要进行重新下载,这期间这些相关信息写入met文件,直到整个任务完成,这个时候part文件进行重新命名,然后使用move命令,把它传送到incoming文件里面,然后met文件自动删除,所以我们有的时候会遇到hash文件失败,就是指的是met里面的信息出了错误不能够和part文件匹配,另外有的时候开机也要疯狂hash,有两种情况一种是你在第一次使用,这个时候要hash提取所有文件信息,还有一种情况就是上一次你 非法关机,那么这个时候就是要进行排错校验了。
    关于hash的算法研究,一直是信息科学里面的一个前沿,尤其在 网络技术普及的,他的重要性越来越突出,其实我们每天在网上进行的信息交流安全验证,我们在使用的操作系统 密钥原理,里面都有它的身影,特别对于那些研究信息安全有兴趣的朋友,这更是一个打开信息世界的钥匙,他在hack世界里面也是一个研究的焦点。
    userhash
    道理同上,当我们在第一次使用emule的时候,emule会自动生成一个值,这个值也是的,它是我们在emule世界里面的标志,只要你不卸载,不删除config,你的userhash值也就永远不变,积分制度就是通过这个值在起作用,emule里面的积分保存,身份识别,都是使用这个值,而和你的id和你的用户名无关,你随便怎么改这些东西,你的userhash值都是不变的,这也充分保证了公平性。其实他也是一个信息摘要,只不过保存的不是文件信息,而是我们每个人的信息。
    散列表
    散列表散列函数的一个主要应用,使用散列表能够快速的按照关键字查找数据记录。(注意:关键字不是像在加密中所使用的那样是秘密的,但它们都是用来“解锁”或者访问数据的。)例如,在英语字典中的关键字是英文单词,和它们相关的记录包含这些单词的定义。在这种情况下,散列函数必须把按照字母顺序排列的字符串映射到为散列表的内部 数组所创建的索引上。
    散列表散列函数的几乎不可能/不切实际的理想是把每个关键字映射到的索引上(参考散列),因为这样能够保证直接 访问表中的每一个数据。
    一个好的散列函数(包括大多数 加密散列函数)具有均匀的真正随机输出,因而平均只需要一两次探测(依赖于装填因子)就能找到目标。同样重要的是,随机 散列函数几乎不可能出现非常高的冲突率。但是,少量的可以估计的冲突在实际状况下是不可避免的(参考生日悖论)。
    在很多情况下,heuristic散列函数所产生的冲突比随机散列函数少的多。Heuristic函数利用了相似关键字的相似性。例如,可以设计一个heuristic函数使得像FILE0000.CHK,FILE0001.CHK,FILE0002.CHK,等等这样的文件名映射到表的连续指针上,也就是说这样的序列不会发生冲突。相比之下,对于一组好的关键字性能出色的随机散列函数,对于一组坏的关键字经常性能很差,这种坏的关键字会自然产生而不仅仅在攻击中才出现。性能不佳的 散列函数表意味着查找操作会退化为费时的线性搜索。扩展
    MD5、SHA1的破解
    2004年8月17日,在美国 加州圣芭芭拉召开的国际密码大会上,山东大学 王小云教授在国际会议上首次宣布了她及她的研究小组的研究成果——对 MD5、HAVAL-128、MD4和 RIPEMD四个著名 密码算法的破译结果。次年二月宣布破解 SHA-1密码。命令描述
    Linux命令——hash
    hash命令用来显示、添加和清除 哈希表。该命令的语法格式如下所示。
    语法
    hash [-l] [-r] [-p <path> <name>] [-t <command>]
    选项说明
    选项
    说明
    -l
    显示哈希表,包括路径
    -r
    清除哈希表
    -p <path> <name>
    向哈希表中增加内容
    -t <command>
    显示指定命令的完整路径
    HASH命令
    hash 每次传输完 数据缓冲区中的数据后就显示一个#号

    转载于:https://www.cnblogs.com/h-c-g/p/11133000.html

    展开全文
  • 哈希算法(哈希函数)基本

    千次阅读 2021-09-19 16:33:42
    一、什么是哈希(Hash) 哈希也称“散列”函数或“杂凑”函数。它是一个不可逆的单向映射,将任意长度的输入消息M(或文件F)映射成为一个较短的定长哈希值H(M),也叫散列值(HashValue)、杂凑值或消息摘要。...

    目录

    一、什么是哈希(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.旋转法

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

    展开全文
  • 本文出自 AC.HASH 团队,AC<=>Adaptive Creator,适应性创作者,旨在于能够在未来新领域下创造出新的哈希算法以应对未来局面。...什么是压缩函数?什么是冲突(pseudo-collisions)?什么是MD2、M.
  • 哈希函数的构造方法: 直接定址法 数字分析法 平方取中法 除留余数法 解决哈希冲突的方法 开放地址法-线性探查法 容易产生堆积,即存储太多时,没地方放。 链地址法 链表定义的方法。 链地址法 ...
  • python字典中哈希函数Hashing is a key part of most programming languages. Large amounts of data can be represented in a fixed buffer. Key-value structures use hashes to store references. 散列是大多数...
  • 密码学哈希函数A Hash Function is a mathematical function that converts a numerical value into another compressed numeric value. The input value for the hash functions can be of arbitrary length, but ...
  • 一,什么是哈希函数? 二,哈希碰撞(hash collision)的解决方式 三,什么是好的哈希函数? 四,哈希函数的构造方法 五,哈希表(hash table)原理
  • Merkle-Damgrd(MD)迭代结构存在着不能保持压缩函数的第2原像稳固性、伪随机函数性等不安全性问题。为增强迭代哈希函数的安全性,从抵抗现有攻击的角度提出1个强化MD迭代结构,称为CMD结构。经证明,该结构可以保持...
  • M-hash以并行线性反馈移位寄存器作为基本电路,采用并行压缩方式计算哈希值,利用压缩过程的信息损失而带来的单向性提供哈希函数的安全性。经过严格的理论证明,M-hash平衡度为1,为规则哈希函数。与基于LFSR的...
  • 区块链与哈希函数

    2022-07-19 22:03:48
    (另外一个工作是RSA算法) 这种结构在几乎所有的哈希函数中使用,具体做法为: 把所有消息M分成一些固定长度的 块Yi; 最后一块padding并使其包含消息 M的长度; 设定初始值CV0; 循环执行压缩函数f,CVi=f(CVi - 1||...
  • Hash+哈希+哈希函数

    2021-05-29 08:11:53
    Hash+哈希+哈希函数 hash == 散列 == 哈希 是一种有损压缩技术 是一种数字指纹技术 哈希是一种加密算法 哈希函数(Hash Function),也称为散列函数或杂凑函数哈希函数是一个公开函数,可以将任意...
  • 提出了一种新的感知哈希算法,用于基于MDCT(频谱离散熵)频谱熵的压缩域语音内容识别。 它的主要目的是解决将传统识别方法应用于压缩语音时出现的计算量大和实时性能差的问题。 该过程开始于提取MDCT系数,该系数是...
  • 哈希函数和消息认证

    千次阅读 2020-12-29 21:39:24
    文章目录一、哈希(Hash)函数1、Hash函数的概念2、Hash函数结构3、Hash函数的应用二、Hash算法1、MD5算法2、SHA1算法三、Hash函数的攻击1、生日悖论:四、消息论证1、消息认证基础理论2、消息认证码3、基于DES的消息...
  • 哈希函数密码学

    2019-02-22 15:30:07
    哈希函数是密码学的一个重要分支,该函数是一类数学函数,它可以在有限的合理时间内,将任意长度的消息变换成固定长度的二进制串,且不可逆,这个输出值就是哈希值,也叫散列值或消息摘要。以hash函数为基础的hash...
  • 哈希函数是一个公开函数,可以将任意长度的消息M映射成为一个长度较短且长度固定的值H(M),称H(M)为哈希值、散列值(Hash Value)、杂凑值或者消息摘要(Message Digest)。它是一种单向密码体制,即一个从明文...
  • 常见的六种哈希构造函数

    千次阅读 2021-02-23 09:46:53
    文章目录相关概念介绍一、直接寻址法二、数字分析法三、折叠法四、平方取中法五、除留余数法...简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。 散列表: 散列表(Hash table,也叫哈希表),是.
  • 网络安全原理与应用:哈希函数.pptx
  • 1哈希函数是密码学的一个重要分支,该函数是一类数学函数,它可以在有限的合理时间内,将任意长度的消息变换成固定长度的二进制串,且不可逆,这个输出值就是哈希值,也叫散列值或消息摘要。以hash函数为基础的...
  • 哈希函数理解

    千次阅读 2018-05-08 21:49:35
     Hash,一般翻译做“散列”,也有直接音译为“哈希”的,就是把任意长度的输入,通过散列算法,变换成固定长度的输出,该输出就是散列值。  散列表,它是基于快速存取的角度设计的,也是一种典型的“空间换时间”的...
  • 安全哈希函数哈希函数定义 Hash一般翻译做散列也有直接音译为哈希的就是把任意长度的输入又叫 做预映射pre-image通过散列算法变换成固定长度的输出该输出就是散列值这 种转换是一种压缩映射也就是散列值的空间...
  • 【JS数据结构与算法】实现哈希函数

    千次阅读 2019-08-14 12:36:21
    那这个哈希函数怎么实现呢,根据前面一篇博客【JS数据结构】认识哈希表,我们已经认识了什么是哈希表以及为什么需要设计一个哈希函数。 其实就是要达到两个目的: 能够快速地计算,快速地获取hashC...
  • 哈希函数(散列函数)详解

    千次阅读 2017-12-19 00:40:59
    哈希函数(散列函数)Hash,一般翻译做”散列”,也有直接音译为”哈希”的,就是把任意长度的输入(又叫做预映射, pre-image),通过散列算法,变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,...
  • 哈希函数相关的比较分析

    千次阅读 2022-03-03 08:30:28
    哈希函数的几个临近的概念,和应用实例的一些简单调查。主要比较了密码学哈希,非密码学哈希,以及应用实例的哈希密码、密钥派生函数
  • 哈希函数和数字签名

    千次阅读 2021-09-13 18:54:27
    目录1 哈希函数 Hash1.1 构造方法1.2 哈希函数在密码学的应用2 数字签名2.1 签名--认证流程2.2 一个生动形象的例子 在讲数字前面以前,我们先要了解一下哈希函数 1 哈希函数 Hash Hash,一般翻译做散列、杂凑,或...
  • DNA 的哈希函数,可为正向偏置或反向互补生成相同的输出。 作者:凯瑟尔·加维; 实现是AGPL,概念是公共领域。 请让我知道这是否有用,我很感激署名。 包含 作为脚本运行时具有简单测试的 python 模块 带有测试的 ...
  • 1)哈希表的存储,查询,都是要经过哈希函数转换地址的,f%N 2)哈希表往往是固定长度,当容量不够,自动扩容,但是整体上哈希表的操作仍然是o(1)时间复杂度! 3)笔试求AC,可以不考虑空间复杂度,但是面试既要考虑...
  • 第18篇 哈希函数

    千次阅读 2020-07-06 08:18:57
    本文哈希有可能是名词(哈希函数哈希算法),也有可能是动词(把这段数据哈希一下)。 Hash函数在数字签名和消息完整性检测等方面有着广泛的应用。 1.哈希函数的定义 1.1 基本概念 明文(plaintext):...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 49,472
精华内容 19,788
关键字:

哈希中压缩函数是什么