精华内容
下载资源
问答
  • 哈希函数生成方法

    千次阅读 2017-07-30 21:22:49
    本文阐述了哈希函数的构造方法有很多,但应注意两个原则:第一,函数值应在1至记录总数之间;第二,尽可能避免冲突。 设要存放的数据元素有n个,存放数据元素的内存单元有m个,设计哈希函数的目标就是要使通过哈希...

    本文阐述了哈希函数的构造方法有很多,但应注意两个原则:第一,函数值应在1至记录总数之间;第二,尽可能避免冲突。

    设要存放的数据元素有n个,存放数据元素的内存单元有m个,设计哈希函数的目标就是要使通过哈希函数得到的n个数据元素的哈希地址尽可能均匀地分布在m个连续内存单元上,同时使计算过程尽可能简单以达到尽可能高的时间效率。

                  

    引 言

    构造哈希函数的方法很多。如何构造一个“好”的哈希函数是很强的技术性和实践性问题,这里的“好”指的是哈希函数构造比较简单,并且用此哈希函数产生的映射所发生的冲突可能性最小,换句话说一个好的哈希函数能将给定数据集合均匀地映射到给定的地址区间中。

    Hash的原意是“弄乱,切碎”,这里的含义是“杂凑”。基本做法是,根据集合元素值的分布情况,设计一个哈希函数h(ki),存储之素ki时,计算ki的哈希函数值,元素ki存储在a(h)中。

    如果“幸运”,所设计的哈希函数很均匀,即任何ki≠kj,都有h(ki)≠h(kj),那么在查找ki时(再计算ki的哈希函数函数值h),就能在a[h]中找到元素ki。

    1.直接定址法

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

      例1,有一个人口统计表,记录了从1岁到100岁的人口数目,其中年龄作为关键字,哈希函数取关键字本身,如图(1):

    地址

    A1

    A2

    ……

    A99

    A100

    年龄

    1

    2

    ……

    99

    100

    人数

    980

    800

    ……

    495

    107

    可以看到,当需要查找某一年龄的人数时,直接查找相应的项即可。如查找99岁的老人数,则直接读出第99项即可。这种哈希函数简单,并且对于不同的关键字不会产生冲突,但可以看出这是一种较为特殊的哈希函数,实际生活中,关键字的元素很少是连续的。用该方法产生的哈希表会造成空间大量的浪费,因此这种方法适应性并不强。[2]↑

    2.数字分析法

     2.1数字分析法是取数据元素关键字中某些取值较均匀的数字位作为哈希地址的方法。即当关键字的位数很多时,可以通过对关键字的各位进行分析,丢掉分布不均匀的位,作为哈希值。它只适合于所有关键字值已知的情况。通过分析分布情况把关键字取值区间转化为一个较小的关键字取值区间。

       例2,要构造一个数据元素个数n=80,哈希长度m=100的哈希表。不失一般性,我们这里只给出其中8个关键字进行分析,8个关键字如下所示:

    K1=61317602      K2=61326875      K3=62739628      K4=61343634

    K5=62706815      K6=62774638      K7=61381262      K8=61394220

    分析上述8个关键字可知,关键字从左到右的第1、2、3、6位取值比较集中,不宜作为哈希地址,剩余的第4、5、7、8位取值较均匀,可选取其中的两位作为哈希地址。设选取最后两位作为哈希地址,则这8个关键字的哈希地址分别为:2,75,28,34,15,38,62,20。[1]↑

    2. 2设有n个d 位数,每一位可能有r种不同的符号,这r种不同的符号在各位上出现的频率不一定相同,可能在某位上分布均匀些,每种符号出现的机会均等;在某位上分布不均匀,只有某几种符号经常出现。可根据哈希表的大小,选取其中各种符号分布均匀的若干位作为哈希地址。计算各位数字中符号分布均匀度rk的公式为:rk=其中,aki表示第i个符号k位上出现的的期望值。计算出rk值越小,

    i=1

    表明在该位(第k位)各种符号分布越不均匀。 

    例3,有一组关键字,对其各位编码如下:

    9   2   1   4   8

    9   1   2   6   9

    9   0   5   2   7

    9   1   6   3   0

    9   1   8   0   5

    9   1   5   5   8

    9   2   0   4   7

    9   0   0   0   1   

    ①  ②  ③  ④  ⑤

    ①位仅“9”出现8次r1=(8-8/10)2*1+(0-8/10)2*9=57.60

    ②位“0,2”各出现2次,“1”出现4次r2=(2-8/10)2*2+(4-8/10)2*1+(0-8/10)2*7=17.60

    ③位“0,5”各出现2次,“1,2,6,8”各出现1次r3=(2-8/10)2*2+(1-8/10)2*4+(0-8/10)2*4=5.60

    ④位“0,4”各出现2次,“2,3,5,6”各出现1次

    ⑤位“7,8”各出现2次,“0,1,5,9”各出现1次

    r3 =r4 =r5 =5.60

    若哈希表地址范围有3位数字,取各关键字的③④⑤位作为记录的哈希地址。也可以把第①②和第⑤位想加,舍去进位,变成一位数,再与第③④位合起来哈希地址等。显然数字分析法仅适用于事先知道表中所有关键字每一位数值的分布情况,它完全依赖于关键字集合。如果换一个关键字集合,选择哪几位重新决定。

    3.折叠法

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

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

    例4,当哈希表长为1000时,关键字key=110108331119891,允许的地址空间为三位十进制数,则这两种叠加情况如图(2):

           移位叠加                                 边界叠加

           8 9 1                                     8 9 1

           1 1 9                                     9 1 1

           3 3 1                                     3 3 1

           1 0 8                                     8 0 1

        +  1 1 0                                   + 1 1 0              

       (1) 5 5 9                                  (3)0 4 4

                     图(2)由折叠法求哈希地址

         用移位叠加得到的哈希地址是559,而用边界叠加所得到的哈希地址是44。如果关键字不是数值而是字符串,则可先转化为数。转化的办法可以用ASCⅡ字符或字符的次序值。[3]↑

     

    4.平方取中法

      这是一种常用的哈希函数构造方法。这个方法是先取关键字的平方,然后根据可使用空间的大小,选取平方数是中间几位为哈希地址。

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

    例5,若设哈希表长为1000则可取关键字平方值的中间三位,如图(3)所示:

    关键字

    关键字的平方

    哈希函数值

    1234

    1522756

    227

    2143

    4592449

    924

    4132

    17073424

    734

    3214

    10329796

    297

    图(3)平方取中哈希函数示例    [4] ↑

    有人曾用“轮盘赌”的统计分析方法对它们进行了模拟分析,结论是平方取中法最接近“随机化”。

     

      例6,设有一组关键字值为ABC,BCD,CDE,DEF其相应的机内码分别为010203,020304,030405,040506。假设可利用地址空间大小为103,平方后取平方数的中间三位作为相当记录的存储地址。如图(4)所示:         

    关键字

    机内码

    机内码的平方

    哈希地址

    ABC

    010203

    0104101209

    101

    BCD

    020304

    0412252416

    252

    CDE

    030405

    0924464025

    464

    DEF

    040506

    1640736036

    736

    图(4)平方取中法关键字及其存储地址[6]↑

       下面给出平方取中法的哈希函数

         //平方取中法哈希函数,结设关键字值32位的整数

         //哈希函数将返回key * key的中间10位

           Int  Hash (int key)

             {

         //计算key的平方

          Key * = key ;

         //去掉低11位

         Key>>=11;

         // 返回低10位(即key * key的中间10位)

           Return key %1024;

              }

     

    5.减去法

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

    例7,公司有一百个员工,而员工的编号介于1001到1100,减去法就是员工编号减去1000后即为数据的位置。编号1001员工的数据在数据中的第一笔。编号1002员工的数据在数据中的第二笔…依次类推。从而获得有关员工的所有信息,因为编号1000以前并没有数据,所有员工编号都从1001开始编号。

     

    6.基数转换法

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

     

    例8,Hash(80127429)=(80127429)13=8*137+0*136+1*135+2*134+7*133+4*132+2*131+9=(502432641)10如果取中间三位作为哈希值,得Hash(80127429)=432

     为了获得良好的哈希函数,可以将几种方法联合起来使用,比如先变基,再折叠或平方取中等等,只要散列均匀,就可以随意拼凑。[5] ↑

     

    7.除留余数法

    取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址,即设定哈希函数为  Hash(key)=key mod p (p≤m),其中,除数p称作模。

    除留余数法不仅可以对关键字直接取模,也可以在折叠、平方取中等运算后取模。对于除留余数法求哈希地址,关键在于模p的选择。使得数据元素集合中每一个关键字通过该哈希函数映射到内存单元的任意地址上的概率相等,从而尽可能减少发生哈希冲突的可能性。

    理论研究表明,除留余数法的模p取不大于表长且最接近表长m素数时效果最好,且p最好取1.1n~1.7n之间的一个素数(n为存在的数据元素个数)。例如:当n=7时,p最好取11、13等素数。 又例图(5):

    表长m

    8

    16

    32

    64

    128

    256

    512

    1000

    模p

    7

    13

    31

    61

    127

    251

    503

    997

    由于除留余数法的地址计算方法简单,而且在许多情况下效果较好。[2]↑

    例9,公司有236个员工,而员工编号介于1000到9999,除留余数法就是员工编号除以数据个数236后,去余数即为数据的位置。编号5428员工的数据(编号5428除以236取余数得0)放数据中的第一笔,编号3512员工数据(编号3512除以236取余数得8)放数据中的第九笔…依次类推。

     

    8.随机乘数法

      亦称为“乘余取整法”。随机乘数法使用一个随机实数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」[5] ↑

      例10,对下列关键字值集合采用随机乘数法计算哈希值,随机数f=0.103149002 哈希表长度n=100得图(6):

     

    k

    f*k

    n*((f*k)的小数部分)

    Hash(k)

    319426

    32948.47311

    47.78411

    47

    718309

    74092.85648

    86.50448

    86

    629443

    64926.41727

    42.14427

    42

    919697

    84865.82769

    83.59669

    83

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

    9.字符串数值哈希法

    在很都情况下关键字是字符串,因此这样对字符串设计Hash函数是一个需要讨论的问题。下列函数是取字符串前10个字符来设计的哈希函数

    Int Hash _ char (char *X)

    {

      int I ,sum 

      i=0;

      while (i 10 && X[i]) 

      Sum +=X[i++];

      sum%=N;      //N是记录的条数

      }

    这种函数把字符串的前10个字符的ASCⅡ值之和对N取摸作为Hash地址,只要N较小,Hash地址将较均匀分布[0,N]区间内,因此这个函数还是可用的。对于N很大的情形,可使用下列函数

    int ELFhash (char *key )

    {

     Unsigned long h=0,g;

    whie (*key)

    h=(h<<4)+ *key;

    key++;

    g=h & 0 xF0000000L;

    if (g) h^=g>>24;

    h & =~g;

    }

    h=h % N

    return (h);

    }

      这个函数称为ELFHash(Exextable and Linking Format ,ELF,可执行链接格式)函数。它把一个字符串的绝对长度作为输入,并通过一种方式把字符的十进制值结合起来,对长字符串和短字符串都有效,这种方式产生的位置不可能不均匀分布。[7] ↑

    10.旋转法

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

      例11,某学校同一个系的新生(小于100人)的学号前5位数是相同的,只有最后2位数不同,我们将最后一位数,旋转放置到第一位,其余的往右移。

    新生学号

    旋转过程

    旋转后的新键值

    5062101

    5062101

    1506210

    5062102

    5062102

    2506210

    5062103

    5062103

    3506210

    5062104

    5062104

    4506210

    5062105

    5062105

    5506210

                          如图(7)

     运用这种方法可以只输入一个数值从而快速地查到有关学生的信息。[9] ↑

    11.伪随机数法

    伪随机数法是将利用数据的键值经过随机数法的运算后的结果作为数据存储的位置。其公式如下(a和c为质数):

    Y=(a * Key + c)mod 数组的大小

    例12,某公司的某女员工的编号是321547,现该公司共有107个女职工,我们取a=13,c=5则

    Y=(13*321547+5)%107

     =(4180111+5)%107

     =54

    则取54当作该员工数据存储的位置。[10] ↑

    小 结

    有许多种不同的哈希函数设计方法,这里主要讨论几种常用的不同类型关键字的希函数设计方法:直接定址法、数字分析法、折叠法、平方取中法、减去法、基数转换法、除留余数法、随机乘数法、字符串数值哈希法、伪随机数法、旋转法。

    尽管哈希函数的构造方法有很多,但不同的方法适用于不同的情况。如:当键字是字符串时可以用字符串数值哈希法构造哈希函数;当关键字是整数类型时就可以用除留余数法、直接定址法和数字分析法等设计哈希函数;而关键字是小数类型常用伪随机数法来构造哈希函数等。

     

    参 考 文 献

    [1]朱战立编著.数据结构(C++语言描述) 北京:高等教育出版社,2004

    [2]陈明编著.实用数据结构基础  北京:清华大学出版社,2002

    [3]严蔚敏等编著.数据结构及应用算法教程  北京:清华大学出版社,2000

    [4]殷人昆等编著.数据结构:面向对象方法与C++描述  北京:清华大学出版社,1999

    [5]熊岳山等编著.数据结构:C++语言描述,  长沙:国防科技大学出版社,2002.2

    [6]苏光奎等编著. 数据结构导学。  北京:清华大学出版社,2002

    [7]陈松乔等编著.算法与数据结构(C与C++描述)  北京:北方交通大学出版社  2002.8

    [8]卓滋德克著.陈曙晖译 数据结构与算法——C++  北京:清华大学出版社, 2003

    [9]王庆瑞编著.数据结构教程(C++语言描述) 北京:高等教育出版社,2002.8

    [10]黄国瑜等编著.数据结构(Java语言版) 北京:清华大学出版社,2002 

     

     

    转自http://wenku.baidu.com/view/61b121c06137ee06eff918c1.html

    展开全文
  • 最小的完美哈希函数生成器是用纯Python编写的,可以使用以下命令安装: $ pip install perfect-hash 该代码支持Python 2.7和Python 3.5或更高版本。 但是,有些示例不再支持Python 2。 介绍 某个键集S的理想散列...
  • 哈希函数的特征_哈希函数及其特征

    千次阅读 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...

    哈希函数的特征

    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 technique, we need a hash function to map the available keys to the set of indexes in the hash table. Say we have a set of keys ranging from [-1000, 1000] and have a hash table of size 10, index ranging from [0, 10].

    哈希函数是哈希的组件,它将密钥映射到哈希表中的某个位置。 作为哈希技术的一部分,我们需要一个哈希函数将可用键映射到哈希表中的索引集。 假设我们有一组范围从[-1000,1000]的键,并且有一个大小为10的哈希表,索引范围是[0,10]。

    That's why to map the keys we need hash functions. A hash function is termed as the perfect hash function is what is able to map the keys to unique locations. But unfortunately, there is no systematic way to generate hash function as the size of the key list is very large considered to hash table size.

    这就是为什么要映射我们需要哈希函数的键的原因。 哈希函数被称为完美哈希函数,它是能够将密钥映射到唯一位置的函数。 但是遗憾的是,由于键列表的大小对于哈希表的大小而言非常大,因此没有系统的方法来生成哈希函数。

    A popular hash function is a folding method where we fold the integers and sum the partitions and then take mod 10 finally.

    流行的哈希函数是一种折叠方法 ,其中我们折叠整数并将分区求和,然后最终取mod 10。

    For example,

    例如,

    The hash function for the folding method is = 
        sum of the fold of size two %10
    Say we have integer 60784567
    So sum will be 60 + 78 + 45 + 67 = 250
    So final location is 250 % 10 = 0
    
    

    The below program computes the above folding method which is an example of the hash function.

    下面的程序将计算上述折叠方法 ,该方法哈希函数的一个示例。

    #include <bits/stdc++.h>
    using namespace std;
    
    //folding method
    
    int main()
    {
        string s;
      
        cout << "enter number\n";
        cin >> s;
    
        //folding and summing
        int sum = 0;
        for (int i = 0; i < s.length(); i += 2) {
            if (i + 1 < s.length())
                sum += stoi(s.substr(i, 2));
            else
                //when only one digit is left for folding
                sum += stoi(s.substr(i, 1));
        }
    
        cout << s << "->" << sum % 10;
    
        return 0;
    }
    
    

    Output:

    输出:

    enter number
    60784567
    60784567->0
    
    

    Now if some other number also finds location 0, then it's called collision.

    现在,如果其他一些数字也找到位置0,则称为碰撞

    Characteristics of good hash function

    哈希函数良好的特征

    1. Minimum collision

      最小碰撞

    2. High gain factor (distributes keys evenly). Like say we have 10 locations in the hash table, then almost 9 locations should have keys. It should not be the case that 4-5 locations have keys only where the keys collided.

      高增益因子(均匀分布密钥)。 像说在哈希表中有10个位置,那么几乎9个位置应该有键。 并非4-5个位置仅在按键碰撞的地方具有按键。

    3. Have a high load factor. Load factor means the number of keys stored/hash table size

      负载系数高。 负载因子是指存储的密钥数/哈希表大小

    4. Easy to compute

      易于计算

    Exercises on hash function

    哈希函数练习

    Use the below hash function to compute the hashing and comment on the goodness of the hash function.

    使用下面的哈希函数来计算哈希并评论哈希函数的优缺点。

    1) F(key) = number of digits of key

    1)F(key)=密钥位数

    #include <bits/stdc++.h>
    using namespace std;
    
    //hash function 1
    int main()
    {
        string s;
        cout << "enter number\n";
        cin >> s;
    
        //f(s)=no of digit in s=length of s
        cout << s << "->" << s.length();
    
        return 0;
    }
    
    

    Output:

    输出:

    enter number
    123452
    123452->6
    
    

    The above hash function is not good at all. Say we have set of keys all having the same digits, then all the keys will collide and the rest of the locations will remain empty.

    上面的哈希函数根本不好。 假设我们有一组键都具有相同的数字,那么所有键将发生冲突,其余位置将保持为空。

    2) F(key) = (rand()*key) % 10

    2)F(键)=(rand()*键)%10

    #include <bits/stdc++.h>
    using namespace std;
    
    //hash function 2
    int main()
    {
        int n;
        cout << "enter number\n";
        cin >> n;
    
        //f(n)=rand()*n
        cout << n << "->" << (rand() * n) % 10;
    
        return 0;
    }
    
    

    Output:

    输出:

    enter number
    103456
    103456->2
    
    

    The above hash function is good as we are multiplying random integers and bringing randomness, the collision rate will be less.

    上面的哈希函数很好,因为我们要乘以随机整数并带来随机性,则冲突率会更低。

    Comparison of the above hash functions:

    上面的哈希函数比较:

    #include <bits/stdc++.h>
    using namespace std;
    
    //comparing goodness of hash function 1 &  2
    int main()
    {
    
        //set of input numbers
        vector<int> arr{ 12345, 234245, 1223123, 765845, 345234, 234534, 98675, 34523, 123, 3245 };
    
        //using hash function 1
        cout << "using hash function 1\n";
        for (int a : arr) {
            cout << a << "->" << to_string(a).length() % 10 << endl;
        }
    
        //using hash function 2
        cout << "\n\nusing hashh function 2\n";
        for (int a : arr) {
            cout << a << "->" << (rand() * a) % 10 << endl;
        }
    
        return 0;
    }
    
    

    Output:

    输出:

    using hash function 1
    12345->5
    234245->6
    1223123->7
    765845->6
    345234->6
    234534->6
    98675->5
    34523->5
    123->3
    3245->4
    
    
    using hashh function 2
    12345->9
    234245->4
    1223123->3
    765845->-1
    345234->-4
    234534->4
    98675->6
    34523->0
    123->5
    3245->-9
    
    
    

    翻译自: https://www.includehelp.com/data-structure-tutorial/hash-functions-and-its-characteristics.aspx

    哈希函数的特征

    展开全文
  • 哈希函数和消息认证

    千次阅读 2020-12-29 21:39:24
    文章目录一、哈希(Hash)函数1、...Hash函数也称散列函数、哈希函数、杂凑函数等。,是一个从消息空间到像空间的不可逆映射。hash函数能将“任意长度”的消息经过hash变换为固定长度的像。所以Hash函数是一种具有压缩性

    一、哈希(Hash)函数

    1、Hash函数的概念

    Hash函数也称散列函数、哈希函数、杂凑函数等。,是一个从消息空间到像空间的不可逆映射。hash函数能将“任意长度”的消息经过hash变换为固定长度的像。所以Hash函数是一种具有压缩性质的的单向函数。通常称其为数字指纹、消息摘要或散列值。
    散列值的生成过程为: h=H(M)
    其中M为变长的消息,H为hash函数,h为散列值。散列函数主要用于小组认证和数字签名,具有以下性质:

    • H可用于任意长度的消息。
    • H产生定长的输出
    • 对任意消息x,计算H(x)很容易,易于软硬件实现。
    • 单向性:又称抗原像性,即给定任意H(x),要找出x在计算上是不可行的。
    • 抗强碰撞性:找到任意满足H(x)=H(y)的偶对x=y,在计算上是不可行的
    • 抗弱碰撞性:又称抗第二原像性,给定任意消息x ,找到满足y!=x且H(y)=H(x)的消息在计算上是不可行的。

    2、Hash函数结构

    Hash函数的一般结构称为Hash函数迭代结构,也称MD结构。被广泛用于大多数的Hash函数。MD结构将输入的消息分为L个固定长度的分组,每一组长度为b位。最后一个分组包含消息的长度若长度不足b位,则填充到b位。
    迭代结构包含一个压缩函数f。函数f有两个输入,一个是前一次迭代的n为输出,一个是消息的b位分组,并产生一个n位的输出。因为一般情况来说消息分组长度b大于输出长度n,所以称为压缩函数。
    在这里插入图片描述

    3、Hash函数的应用

    1)数字签名
    由于消息散列值比消息短得多,用于签名笔直接对消息本身签名高效得多。由于Hash值有较好的抗碰撞性,所以使用Hash函数进行签名,能满足消息的完整性、防伪造性以及不可否认性等特点。
    2)生成程序或文档的“数字指纹”
    Hash函数可用来保证数据的完整性,实现消息认证,防止消息未经授权的修改。通过Hash函数变换得到程序或文档的散列值,即数字指纹,并存放在安全地方;然后在一定时间后定时岁文档或程序求其散列值,与原数据对比,进而检测程序或文档是否被修改或中毒。
    3)用于安全传输和存储口令
    通过Hash函数生成口令的散列值,然后在系统中保存账号的散列值,这样能有限的防止系统在被入侵后,用户信息不会被直接泄露。

    二、Hash算法

    1、MD5算法

    1)算法描述
    MD5算法的输入是长度小于262比特的消息,输出为128比特的消息摘要。输入的消息以512比特分组为单位处理。
    具体的算法流程如下:

    • 附加填充位。填充一个“1”和若干个“0”,使消息长度模512与448同余,再将原始消息长度以62比特表示填充到末尾。这样消息长度即变成了512比特的整数倍。
    • 初始化链接变量。MD5使用四个32位的寄存器A、B、C、D。最开始存放4个固定的32位参数,即初始链接变量。
    • 分组处理(迭代压缩)该操作与分组密码的分组处理类似。它由四轮组成,512比特的消息分组Mi被均分成16个子分组,参与每轮16步函数运算,即每轮包括16个步骤。每一步的输入是4个32比特的链接变量和一个32比特的消息分组,输出为32位值。经过四轮64步之后,得到四个寄存器值分别与输入链接变量进行模加,即得到此次分组处理的输出链接变量。
    • 步函数:每一轮的步函数是相同的,即使用同一个非线性函数,而不同轮的步函数不同,所以一共使用4个非线性函数。该函数有3个32位的输入变量,一个32位的输出变量。
    • 第四轮完成后,做如下运算:A=(A+AA)mod 232,B=(B+BB)mod 232,C=(C+CC)mod 232,D=(D+DD)mod 232.最后将四个寄存器的值做下一次迭代压缩时 的输入变量,知道最后一个消息分组输出128位的散列值。

    2、SHA1算法

    1)算法原理

    • 步骤一:添加填充位,使数据长度=448 mod 512
    • 步骤二:添加消息长度,一个62 位块,表示原始消息长度
    • 步骤三:初始化缓冲区。160位,表示5个32位寄存器(A,B,C,D,E)
    • 步骤四:以512位数据为单位处理消息,四轮,每轮20步,共有四个基本逻辑函数f1,f2,f3,f4
    • 步骤五:输出,全部L个512数据块处理完后,输出160位消息散列值。

    SHA1哈希值生成图示:
    在这里插入图片描述SHA1对单个512位分组的处理过程:

    在这里插入图片描述
    SHA1 压缩函数单轮逻辑:
    在这里插入图片描述

    三、Hash函数的攻击

    攻击者的主要目标不是恢复原始的明文。而是用非法的消息替代合法消息进行伪造和欺骗,会hash函数的攻击也是寻找碰撞的过程。

    1、生日悖论:

    生日悖论问题:两个人的生日是等概率的,在不考虑闰年的情况下,在kg个人中至少有两个人的生日相同的概率大于1/2.问k最小值是多少?
    在这里插入图片描述从而当k=100时,这100人中至少有两人生日相同近乎必然事件,然而这个结果似乎不合实际。这就是生日悖论。
    对于输出长度为128比特的散列函数求碰撞,类似于以上情况。
    要找到一个与特定非消息具有相同的散列值的另一个消息的改路很小。如果不指定散列值,只是在两组消息中找到具有相同散列值的两个消息,问题就容易很多。
    所以攻击者就会利用hash空间不够大易制造碰撞来进行攻击。

    四、消息论证

    1、消息认证基础理论

    网络系统安全一般要考虑两个问题:

    • 加密保护传送的消息,抵抗被动攻击
    • 防止伪造、篡改信息,抵抗主动攻击

    认证是抵抗主动攻击的主要手段,对于开放的网络中的各种信息系统的安全性有重要关系。
    消息认证的目的:

    • 验证消息的来源是真实的而不是冒充的
    • 验证消息的完整性,检测是否被篡改。

    安全认证模型:
    在这里插入图片描述安全认证系统的目标:

    • 接收方能检验消息的合法性、真实性和完整性

    • 除了合法的消息发送者,其他人不能伪造合法的消息

    • 消息的发送方和接受方不能抵赖
      消息认证函数分类:

    • 信息认证码:对信源消息的一个编码函数,需要秘钥

    • 散列函数认证:一个公开函数,将消息映射为固定长度的像

    • 基于DES的消息加密认证:消息与加密后的密文认证。

    2、消息认证码

    在这里插入图片描述

    3、基于DES的消息认证码

    在这里插入图片描述

    4、基于Hash的认证码

    在这里插入图片描述

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

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

    展开全文
  • 哈希原理与常见哈希函数

    千次阅读 2020-01-09 18:11:06
    转换的方法称为哈希函数,原值经过哈希函数计算后得到的值称为哈希值。 1.哈希特点 (1)一致性:同一个值每次经过同一个哈希函数计算后得到的哈希值是一致的。 F(x)=rand() :每次返回一个随机值,是不好的哈希 (2)...
  • 量子哈希函数及其在量子密钥分发,伪随机数生成和图像加密中的隐私放大中的应用
  • 常用哈希函数介绍

    千次阅读 2021-03-31 16:21:32
    哈希函数介绍 什么是哈希?在记录的关键字与记录的存储地址之间建立的一种对应关系叫哈希函数哈希函数就是一种映射,是从关键字到存储地址的映射。 通常,包含哈希函数的算法的算法复杂度都假设为O(1),这就是为...
  • 密码学哈希函数 什么是哈希函数? (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....
  • 无论是Yadong Mu的论文还是别人的,讲到多个哈希生成多个视觉词典之后,就戛然而止了,然后呢,针对每个词典获得一个检索结果,获得的多个检索结果通过什么方式确定最终的检索结果啊!...
  • 首先运行它,或者写 hassep7(number)。 数字的默认值是 1008。该图最多可以工作到 3 维。总和在最多 5 维时是正确的。该函数将返回其因子的总和。 您也可以探索整个 alicuot 循环。 代码中给出了示例。
  • 区块链中的哈希函数

    千次阅读 2021-08-22 16:06:20
    (1)哈希函数(Hash Function),又叫散列函数、散列算法。 哈希函数是一个公开函数,可以将任意长度的消息M映射成为一个长度较短且长度固定的值H(M),称H(M)为哈希值、散列值(Hash Value)、杂凑值或者消息...
  • 完美哈希函数生成器 。对于一个给定的字符串集,它会生成哈希函数和哈希表。以c或cpp代码的形式,通过输入的字符串来实现查询操作。产生的哈希函数是完美的,意味着哈希表没有冲突,并且查询操作仅仅需要一次比较...
  • 哈希(哈希表与哈希函数

    千次阅读 2018-07-04 14:32:43
    1、哈希函数2、哈希表3、哈希函数在大数据中应用1.1哈希函数哈希函数的性质哈希函数又名散列函数,对于经典哈希函数来说,它具有以下5点性质:1、输入域无穷大2、输出域有穷尽3、输入一样输出肯定一样4、当输入不...
  • 哈希函数

    千次阅读 2019-02-27 09:28:42
    `欢迎使用Markdown编辑器新的改变功能快捷键合理的创建标题,有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants创建...
  • 哈希函数和哈希表

    千次阅读 2019-05-08 16:31:12
    经典哈希函数的性质(散列函数) 1.输入域无穷大 2.输出域是有穷尽的 3.输入参数相同,返回哈希值不变(不是随机函数) 4.输入不同,哈希值亦可能相同,哈希碰撞 5.离散性:举例:input-0~98,out-0、1、2,...
  • 哈希函数理解

    千次阅读 2018-05-08 21:49:35
     Hash,一般翻译做“散列”,也有直接音译为“哈希”的,就是把任意长度的输入,通过散列算法,变换成固定长度的输出,该输出就是散列值。  散列表,它是基于快速存取的角度设计的,也是一种典型的“空间换时间”的...
  • Go-哈希函数与消息认证详解(含代码)哈希函数简介历史特性安全性MD族md4md5SHA系列SHA-1SHA-2消息认证消息认证的目的消息认证码认证码与检错码HMAC的Go实现crypto/hmac包hash包crypto/sha1包代码实现截图参考 哈希...
  • 最小完美哈希函数库。 主要用Java编写。 包括C版本(当前仅对MPHF进行评估)。 可以在线性时间内生成每个密钥需要少于1.58的MPHF。 可以以小于100 ns / key的速度生成MPHF,以小于100 ns / key的速度评估,每...
  • 哈希函数是什么,在区块链中有什么用 哈希函数是什么? 哈希函数,又叫散列函数、散列算法,是一种从任何一种数据中创建小的数字“指纹”(也叫做摘要)的方法。什么意思呢?就是说,你输入任何长度、任何内容的...
  • 1.1 密码学哈希函数

    千次阅读 2018-09-12 15:13:01
    我们需要理解的第一个密码学的基础知识是密码学哈希函数哈希...● 它能进行有效计算,简单来说就是对于特定的输入字符串,在合理时间内,我们可以算出哈希函数的输出。更准确地说,对应n的字符串,其哈希值计算...
  • 哈希函数(Hash Function)

    千次阅读 2019-07-23 12:23:36
    哈希函数(散列函数)说明应用解释Q:冲突是不是可以避免的?hash函数的构造准则:简单、均匀hash函数的构造方法:处理冲突的方法:参考 说明 散列的概念属于查找,它不以关键字的比较为基本操作,采用直接寻址技术...
  • 哈希函数sha-256流程 这将是哈希函数的基本介绍。 我将假设我的大多数读者都在这里,以了解为什么使用哈希函数以及它们为什么起作用的基本概念。 我的目标是从一般意义上解释它,我将省略证明和实现细节,而将重点...
  • 哈希函数&哈希表

    2018-08-08 23:47:31
    1、哈希函数:传入一个字符串返回一个哈希码 数字0~9,字母a~f,长度为16或者32; 这就是哈希函数,mD5哈希。16^16范围。 哈希函数又叫散列函数, 性质:1.输入域是无限的;2.输出域是有限的;3.当你输入参数是...
  • 在当前状态下,代码可以基于 BLAKE 哈希函数生成彩虹表。 它是为快速、内存中的彩虹表而开发的,因为可找到每个密码的搜索时间有限。 有一些函数可以将彩虹表保存到文件中并从那里加载它,但这只是为了在攻击密码...
  • wyhash:传递了SMHasher,BigCrush和practrand的梦想快速哈希函数和随机数生成
  • 一番码客 : 挖掘你关心的亮点。 ... 本文目录: 文章目录初识hash函数hash函数的作用hash算法的安全性常见的Hash算法MD5SHA1...哈希函数,也称散列函数。 更像是一种思想,没有一个固定公式。 只要符合散列思想的的算...
  • 哈希函数的构造 常用的哈希函数的构造方法有 6 种:直接定址法、数字分析法、平方取中法、折叠法、除留余数法和随机数法。 直接定址法:其哈希函数为一次函数,即以下两种形式: H(key)= key 或者 H(key)=a * ...
  • 行业资料-电子功用-基于变色龙哈希函数的电子支票生成和验证方法

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 107,171
精华内容 42,868
关键字:

哈希函数的生成位