精华内容
下载资源
问答
  • 为了有效的应用hash查找技术
    千次阅读
    2019-04-07 17:08:27

    一、散列查找的基本思想:

    散列技术:

    在记录的存储位置和它的关键码key之间建立一个确定的对应关系H,使得每个关键字key和唯一的存储位置H(key)相对应。存储记录时,根据这个对应关系找到关键码的映射地址,并按此地址存储该记录;查找记录时,根据这个对应关系找到待查关键码的映射地址,并按此地址访问该记录,这种查找技术就称为散列技术。采用散列技术将记录存储在一块连续的存储空间中,这块连续的存储空间称为散列表;将关键码映射为散列表中适当位置的函数称为散列函数,所得的存储位置称为散列地址

    散列技术需要考虑的两个问题:

    1.散列函数的设计。力求简单、均匀、存储利用率高的散列函数。

    2.冲突的处理。

    二、散列函数的设计。

    散列函数遵循的基本原则:

    1.计算简单。散列函数应该不是很大的计算量,否则会降低查找效率。

    2.函数值(即散列地址)分布均匀,希望散列函数能够把记录以相同的概率散列到散列表的所有地址空间中,这样才能保证存储空间的有效利用,并减少冲突。

    三种常见的散列函数:

    直接定址法:

    直接定址法的散列函数是关键码的线性函数,即H(key) = a x key + b , 其中a, b为常数。

    例如:关键码集合为{10,30,50,70,80},选取的散列函数为H(key) = key / 10,则散列表如下图所示:

    评价:

    直接定址法的特点是不会产生冲突,但实际应用中能使用这种散列函数的情况很少,它适用于事先知道关键码的分布,关键码结合不是很大且连续性较好的情况。

    除留余数法:

    除留余数法的基本思想是选择某个适当的正整数p,以关键码除以p的余数作为散列地址。

    H(key) = key mod p.

    一般情况下,如果散列表的长度为m, 通常选p为小于或等于表长(最好接近m)的最小素数或不包含小于20质因子的合数。

    评价:

    除留余数法是一种最简单、也是最常用的构造散列函数的方法,并且这种方法不要求事先知道关键码的分布。

     

    平方取中法:

    平方取中法是对关键码平方后,按散列表大小,取中间的若干位作为散列地址(简称平方后截取)。

    之所以这样,是因为一个数平方后,中间的几位分布较均匀,从而冲突发生的概率较小。

    例如:关键码1234,假设散列地址是2位,1234^2 = 1522756,选取中间的2位作为散列地址,可以选22,也可以选27.

    三、处理冲突的方法

    1.开放定址法:

    用开发定址法处理冲突得到的散列表叫做闭散列表。

    开放地址法处理冲突的方法是,如果关键码得到的散列地址产生了冲突,就去寻找下一个空的散列地址,只要散列表足够大,他的散列地址总能找到,并将记录存入。找下一个空散列地址的方法通常有线性探测法和二次探测法。

    1.1线性探测法:

    当冲突发生时,线性探测法从冲突位置的下一个位置起,依次寻找空的散列地址,对于键值key,闭散列表的长度为m, 发生冲突时,寻找下一个散列地址的公式为:

    (H(key) + di) % m               (di = 1,2,3 ,4,...m-1)

    1.2二次探测法

    2.拉链法(链地址法)

    用拉链法处理冲突构造的散列表叫做开散列表。

    四、散列查找的性能分析

    影响冲突概率的主要三个因素:

    1.散列函数是否均匀。

    2.处理冲突的方法。

    3.散列表的装填因子。

    开散列表和闭散列表的比较:

     

    未完待续...

    更多相关内容
  • Hash学习技术目前被广泛应用于大规模数据的相似性查找中,其通过将数据转化成二进制编码的形式,同时提高查找速度和降低存储代价。目前,大多数Hash排序算法通过比较数据在欧氏空间和海明空间的排序一致性来构造损失...
  • Hash查找算法

    千次阅读 2018-09-05 14:53:03
    提起哈希,我的第一印象就是C#中的Hashtable类,它是由一组key/value的键值对组成的集合,它就是应用了散列技术。 那么,什么是哈希查找呢?在弄清楚什么是哈希查找之前,我们要弄清楚哈希技术,哈希技...

    哈希查找,也称为散列查找(本文以哈希称呼)。提起哈希,我的第一印象就是C#中的Hashtable类,它是由一组key/value的键值对组成的集合,它就是应用了散列技术。

    那么,什么是哈希查找呢?在弄清楚什么是哈希查找之前,我们要弄清楚哈希技术,哈希技术是在记录的存储位置和记录的关键字之间建立一个确定的对应关系f,使得每个关键字key对应一个存储位置f(key)。查找时,根据这个确定的对应关系找到给定值的映射f(key),若查找集合中存在这个记录,则必定在f(key)的位置上。哈希技术既是一种存储方法,也是一种查找方法。

    六种哈希函数的构造方法:

    1,直接定址法:

    函数公式:f(key)=a*key+b (a,b为常数)

    这种方法的优点是:简单,均匀,不会产生冲突。但是需要事先知道关键字的分布情况,适合查找表较小并且连续的情况。

    2,数字分析法:

    比如我们的11位手机号码“136XXXX7887”,其中前三位是接入号,一般对应不同运营公司的子品牌,如130是联通如意通,136是移动神州行,153是电信等。中间四们是HLR识别号,表示用户归属地。最后四们才是真正的用户号。

    若我们现在要存储某家公司员工登记表,如果用手机号码作为关键字,那么极有可能前7位都是相同的,所以我们选择后面的四们作为哈希地址就是不错的选择。

    3,平方取中法:

    故名思义,比如关键字是1234,那么它的平方就是1522756,再抽取中间的3位就是227作为哈希地址。

    4,折叠法:

    折叠法是将关键字从左到右分割成位数相等的几个部分(最后一部分位数不够可以短些),然后将这几部分叠加求和,并按哈希表表长,取后几位作为哈希地址。

    比如我们的关键字是9876543210,哈希表表长三位,我们将它分为四组,987|654|321|0 ,然后将它们叠加求和987+654+321+0=1962,再求后3位即得到哈希地址为962,哈哈,是不是很有意思。

    5,除留余数法:

    函数公式:f(key)=key mod p (p<=m)m为哈希表表长。

    这种方法是最常用的哈希函数构造方法。

    6,随机数法:

    函数公式:f(key)= random(key)。

    这里random是随机函数,当关键字的长度不等是,采用这种方法比较合适。

    两种哈希函数冲突解决方法:

    我们设计得最好的哈希函数也不可能完全避免冲突,当我们在使用哈希函数后发现两个关键字key1!=key2,但是却有f(key1)=f(key2),即发生冲突。

    方法一:开放定址法:

    开放定址法就是一旦发生了冲突,就去寻找下一个空的哈希地址,只要哈希表足够大,空的哈希地址总是能找到,然后将记录插入。这种方法是最常用的解决冲突的方法。

    方法二:链地址法:

    下面是实现代码:

    C#版本:

    复制代码
    namespace HashSearch.CSharp
    {
        class Program
        {
            //初始化哈希表
            static int hashLength = 7;
            static int[] hashTable= new int[hashLength];
    
            //原始数据
            static List<int> list = new List<int>() { 13,29,27,28,26,30,38 };
    
            static void Main(string[] args)
            {
                Console.WriteLine("********************哈希查找(C#版)********************\n");
    
                //创建哈希表
                for (int i = 0; i < list.Count; i++)
                {
                    Insert(hashTable,list[i]);
                }
                Console.WriteLine("展示哈希表中的数据:{0}",String.Join(",",hashTable));
    
                while (true)
                {
                    //哈希表查找
                    Console.Write("请输入要查找的数据:");
                    int data = int.Parse(Console.ReadLine());
                    var result = Search(hashTable, data);
                    if (result == -1) Console.WriteLine("对不起,没有找到!");
                    else Console.WriteLine("数据的位置是:{0}", result);
                }
            }
    
            /// <summary>
            /// 哈希表插入
            /// </summary>
            /// <param name="hashTable">哈希表</param>
            /// <param name="data">待插入值</param>
            public static void Insert(int[] hashTable, int data)
            { 
                //哈希函数,除留余数法
                int hashAddress = Hash(hashTable,data);
    
                //如果不为0,则说明发生冲突
                while (hashTable[hashAddress] != 0)
                {
                    //利用开放定址的线性探测法解决冲突
                    hashAddress = (++hashAddress) % hashTable.Length;
                }
    
                //将待插入值存入字典中
                hashTable[hashAddress] = data;
            }
    
            /// <summary>
            /// 哈希表查找
            /// </summary>
            /// <param name="hashTable">哈希表</param>
            /// <param name="data">待查找的值</param>
            /// <returns></returns>
            public static int Search(int[] hashTable, int data)
            {
                //哈希函数,除留余数法
                int hashAddress = Hash(hashTable,data);
    
                //冲突发生
                while (hashTable[hashAddress] != data)
                {
                    //利用开放定址的线性探测法解决冲突
                    hashAddress = (++hashAddress) % hashTable.Length;
    
                    //查找到了开放单元或者循环回到原点,表示查找失败
                    if (hashTable[hashAddress] == 0 || hashAddress==Hash(hashTable,data)) return -1;
                }
                //查找成功,返回值的下标
                return hashAddress;
            }
    
            /// <summary>
            /// 哈希函数(除留余数法)
            /// </summary>
            /// <param name="hashTable">待操作哈希表</param>
            /// <param name="data"></param>
            /// <returns>返回数据的位置</returns>
            public static int Hash(int[] hashTable, int data)
            {
                return data % hashTable.Length;
            }
        }
    }
    复制代码

    程序输出结果如图:

    ds41

     

    C语言版:

    复制代码
    #include "stdio.h"    
    
    
    
    
    
    #include " stdlib.h " #include " io.h " #include " math.h " #include " time.h " #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define SUCCESS 1 #define UNSUCCESS 0 #define HASHSIZE 7 /* 定义散列表长为数组的长度 */ #define NULLKEY -32768 typedef int Status; typedef struct { int *elem; /* 数据元素存储地址,动态分配数组 */ int count; /* 当前数据元素个数 */ }HashTable; int m= 0; /* 散列表表长,全局变量 */ /* 初始化 */ Status Init(HashTable * hashTable) { int i; m= HASHSIZE; hashTable->elem= ( int *)malloc(m* sizeof( int)); // 申请内存 hashTable->count= m; for (i= 0;i<m;i++ ) { hashTable->elem[i]= NULLKEY; } return OK; } /* 哈希函数(除留余数法) */ int Hash( int data) { return data% m; } /* 插入 */ void Insert(HashTable *hashTable, int data) { int hashAddress=Hash(data); // 求哈希地址 // 发生冲突 while(hashTable->elem[hashAddress]!= NULLKEY) { // 利用开放定址的线性探测法解决冲突 hashAddress=(++hashAddress)% m; } // 插入值 hashTable->elem[hashAddress]= data; } /* 查找 */ int Search(HashTable *hashTable, int data) { int hashAddress=Hash(data); // 求哈希地址 // 发生冲突 while(hashTable->elem[hashAddress]!= data) { // 利用开放定址的线性探测法解决冲突 hashAddress=(++hashAddress)% m; if (hashTable->elem[hashAddress]==NULLKEY||hashAddress==Hash(data)) return - 1 ; } // 查找成功 return hashAddress; } /* 打印结果 */ void Display(HashTable * hashTable) { int i; printf( " \n**********展示结果**********\n " ); for (i= 0;i<hashTable->count;i++ ) { printf( " %d ",hashTable-> elem[i]); } printf( " \n**********展示完毕**********\n " ); } void main() { int i,j,result; HashTable hashTable; int arr[HASHSIZE]={ 13, 29, 27, 28, 26, 30, 38 }; printf( " ***************哈希查找(C语言版)***************\n " ); // 初始化哈希表 Init(& hashTable); // 插入数据 for (i= 0;i<HASHSIZE;i++ ) { Insert(& hashTable,arr[i]); } Display(& hashTable); // 查找数据 result= Search(&hashTable, 29 ); if (result==- 1) printf( " 对不起,没有找到! " ); else printf( " 29在哈希表中的位置是:%d " ,result); getchar(); }
    复制代码

    程序输出结果如图:

    ds42

    ————————————————-

    Hash算法

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

      HASH主要用于信息安全领域中加密算法,它把一些不同长度的信息转化成杂乱的128位的编码,这些编码值叫做HASH值. 也可以说,hash就是找到一种数据内容和数据存放地址之间的映射关系

    基本概念

       * 若结构中存在和关键字K相等的记录,则必定在f(K)的存储位置上。由此,不需比较便可直接取得所查记录。称这个对应关系f为散列函数(Hash function),按这个思想建立的表为散列表

      * 对不同的关键字可能得到同一散列地址,即key1≠key2,而f(key1)=f(key2),这种现象称冲突。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述,根据散列函数H(key)和处理冲突的方法将一组关键字映象到一个有限的连续的地址集(区间)上,并以关键字在地址集中的“象” 作为记录在表中的存储位置,这种表便称为散列表,这一映象过程称为散列造表或散列,所得的存储位置称散列地址。

      * 若对于关键字集合中的任一个关键字,经散列函数映象到地址集合中任何一个地址的概率是相等的,则称此类散列函数为均匀散列函数(Uniform Hash function),这就是使关键字经过散列函数得到一个“随机的地址”,从而减少冲突。

    常用的构造散列函数的方法

      散列函数能使对一个数据序列的访问过程更加迅速有效,通过散列函数,数据元素将被更快地定位ǐ

      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算法,MD5 和 SHA-1 可以说是目前应用最广泛的Hash算法,而它们都是以 MD4 为基础设计的。那么他们都是什么意思呢?

      这里简单说一下:

      (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一起使用的,它对长度小于264的输入,产生长度为160bit的散列值,因此抗穷举(brute-force)性更好。SHA-1 设计时基于和MD4相同原理,并且模仿了该算法。

      那么这些Hash算法到底有什么用呢?

      Hash算法在信息安全方面的应用主要体现在以下的3个方面:

      (1) 文件校验

      我们比较熟悉的校验算法有奇偶校验和CRC校验,这2种校验并没有抗数据篡改的能力,它们一定程度上能检测并纠正数据传输中的信道误码,但却不能防止对数据的恶意破坏。

      MD5 Hash算法的”数字指纹”特性,使它成为目前应用最广泛的一种文件完整性校验和(Checksum)算法,不少Unix系统有提供计算md5 checksum的命令。

      (2) 数字签名

      Hash 算法也是现代密码体系中的一个重要组成部分。由于非对称算法的运算速度较慢,所以在数字签名协议中,单向散列函数扮演了一个重要的角色。 对 Hash 值,又称”数字摘要“进行数字签名,在统计上可以认为与对文件本身进行数字签名是等效的。而且这样的协议还有其他的优点。

      (3) 鉴权协议

      如下的鉴权协议又被称作挑战–认证模式:在传输信道是可被侦听,但不可被篡改的情况下,这是一种简单而安全的方法。以上就是一些关于hash以及其相关的一些基本预备知识。那么在emule里面他具体起到什么作用呢?

      MD5、SHA1的破解

      2004年8月17日,在美国加州圣芭芭拉召开的国际密码大会上,山东大学王小云教授在国际会议上首次宣布了她及她的研究小组近年来的研究成果——对MD5、HAVAL-128、MD4和RIPEMD等四个著名密码算法的破译结果。 次年二月宣布破解SHA-1密码。

    编辑本段散列函数的性质

      所有散列函数都有如下一个基本特性:如果两个散列值是不相同的(根据同一函数),那么这两个散列值的原始输入也是不相同的。这个特性是散列函数具有确定性的结果。但另一方面,散列函数的输入和输出不是一一对应的,如果两个散列值相同,两个输入值很可能是相同的,但并不能绝对肯定二者一定相等。输入一些数据计算出散列值,然后部分改变输入值,一个具有强混淆特性的散列函数会产生一个完全不同的散列值。

      典型的散列函数都有无限定义域,比如任意长度的字节字符串,和有限的值域,比如固定长度的比特串。在某些情况下,散列函数可以设计成具有相同大小的定义域和值域间的一一对应。一一对应的散列函数也称为排列。可逆性可以通过使用一系列的对于输入值的可逆“混合”运算而得到。求。到2007年为止,第三版还未完备。

    编辑本段散列函数的应用

      由于散列函数的应用的多样性,它们经常是专为某一应用而设计的。例如,加密散列函数假设存在一个要找到具有相同散列值的原始输入的敌人。一个设计优秀的加密散列函数是一个“单向”操作:对于给定的散列值,没有实用的方法可以计算出一个原始输入,也就是说很难伪造。为加密散列为目的设计的函数,如MD5,被广泛的用作检验散列函数。这样软件下载的时候,就会对照验证代码之后才下载正确的文件部分。此代码有可能因为环境因素的变化,如机器配置或者IP地址的改变而有变动。以保证源文件的安全性。

      错误监测和修复函数主要用于辨别数据被随机的过程所扰乱的事例。当散列函数被用于校验和的时候,可以用相对较短的散列值来验证任意长度的数据是否被更改过。

    编辑本段散列表

      散列表是散列函数的一个主要应用,使用散列表能够快速的按照关键字查找数据记录。(注意:关键字不是像在加密中所使用的那样是秘密的,但它们都是用来“解锁”或者访问数据的。)例如,在英语字典中的关键字是英文单词,和它们相关的记录包含这些单词的定义。在这种情况下,散列函数必须把按照字母顺序排列的字符串映射到为散列表的内部数组所创建的索引上。

      散列表散列函数的几乎不可能/不切实际的理想是把每个关键字映射到唯一的索引上(参考完美散列),因为这样能够保证直接访问表中的每一个数据。

      一个好的散列函数(包括大多数加密散列函数)具有均匀的真正随机输出,因而平均只需要一两次探测(依赖于装填因子)就能找到目标。同样重要的是,随机散列函数几乎不可能出现非常高的冲突率。但是,少量的可以估计的冲突在实际状况下是不可避免的(参考生日悖论)。

      在很多情况下,heuristic散列函数所产生的冲突比随机散列函数少的多。Heuristic函数利用了相似关键字的相似性。例如,可以设计一个heuristic函数使得像FILE0000.CHK, FILE0001.CHK, FILE0002.CHK, 等等这样的文件名映射到表的连续指针上,也就是说这样的序列不会发生冲突。相比之下,对于一组好的关键字性能出色的随机散列函数,对于一组坏的关键字经常性能很差,这种坏的关键字会自然产生而不仅仅在攻击中才出现。性能不佳的散列函数表意味着查找操作会退化为费时的线性搜索。

    编辑本段错误校正

      使用一个散列函数可以很直观的检测出数据在传输时发生的错误。在数据的发送方,对将要发送的数据应用散列函数,并将计算的结果同原始数据一同发送。在数据的接收方,同样的散列函数被再一次应用到接收到的数据上,如果两次散列函数计算出来的结果不一致,那么就说明数据在传输的过程中某些地方有错误了。这就叫做冗余校验。

      对于错误校正,假设相似扰动的分布接近最小(a distribution of likely perturbations is assumed at least approximately)。对于一个信息串的微扰可以被分为两类,大的(不可能的)错误和小的(可能的)错误。我们对于第二类错误重新定义如下,假如给定 H(x) 和 x+s,那么只要s足够小,我们就能有效的计算出x。那样的散列函数被称作错误校正编码。这些错误校正编码有两个重要的分类:循环冗余校验和里德所罗门码。

    编辑本段语音识别

      对于像从一个已知列表中匹配一个MP3文件这样的应用,一种可能的方案是使用传统的散列函数——例如MD5,但是这种方案会对时间平移、CD读取错误、不同的音频压缩算法或者音量调整的实现机制等情况非常敏感。使用一些类似于MD5的方法有利于迅速找到那些严格相同(从音频文件的二进制数据来看)的音频文件,但是要找到全部相同(从音频文件的内容来看)的音频文件就需要使用其他更高级的算法了。

      那些并不紧随IT工业潮流的人往往能反其道而行之,对于那些微小差异足够鲁棒的散列函数确实存在。现存的绝大多数散列算法都是不够鲁棒的,但是有少数散列算法能够达到辨别从嘈杂房间里的扬声器里播放出来的音乐的鲁棒性。有一个实际的例子是Shazam[1]服务。用户可以用电话机拨打一个特定的号码,并将电话机的话筒靠近用于播放音乐的扬声器。该项服务会分析正在播放的音乐,并将它于存储在数据库中的已知的散列值进行比较。用户就能够收到被识别的音乐的曲名(需要收取一定的费用)

      什么是文件的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都是通过这个值来确定文件。

      那么什么是userhash呢?

      道理同上,当我们在第一次使用emule的时候,emule会自动生成一个值,这个值也是唯一的,它是我们在emule世界里面的标志,只要你不卸载,不删除config,你的userhash值也就永远不变,积分制度就是通过这个值在起作用,emule里面的积分保存,身份识别,都是使用这个值,而和你的id和你的用户名无关,你随便怎么改这些东西,你的userhash值都是不变的,这也充分保证了公平性。其实他也是一个信息摘要,只不过保存的不是文件信息,而是我们每个人的信息。

      那么什么是hash文件呢?

      我们经常在emule日至里面看到,emule正在hash文件,这里就是利用了hash算法的文件校验性这个功能了,文章前面已经说了一些这些功能,其实这部分是一个非常复杂的过程,目前在ftp,bt等软件里面都是用的这个基本原理,emule里面是采用文件分块传输,这样传输的每一块都要进行对比校验,如果错误则要进行重新下载,这期间这些相关信息写入met文件,直到整个任务完成,这个时候part文件进行重新命名,然后使用move命令,把它传送到incoming文件里面,然后met文件自动删除,所以我们有的时候会遇到hash文件失败,就是指的是met里面的信息出了错误不能够和part文件匹配,另外有的时候开机也要疯狂hash,有两种情况一种是你在第一次使用,这个时候要hash提取所有文件信息,还有一种情况就是上一次你非法关机,那么这个时候就是要进行排错校验了。

      关于hash的算法研究,一直是信息科学里面的一个前沿,尤其在网络技术普及的今天,他的重要性越来越突出,其实我们每天在网上进行的信息交流安全验证,我们在使用的操作系统密钥原理,里面都有它的身影,特别对于那些研究信息安全有兴趣的朋友,这更是一个打开信息世界的钥匙,他在hack世界里面也是一个研究的焦点。

      常用HASH函数

      ·直接取余法: f(x):= x mod maxM ; maxM一般是不太接近 2^t 的一个质数。

      ·乘法取整法: f(x):=trunc((x/maxX)*maxlongit) mod maxM,主要用于实数。

      ·平方取中法: f(x):=(x*x div 1000 ) mod 1000000); 平方后取中间的,每位包含信息比较多。




    展开全文
  • hash算法原理详解

    千次阅读 2021-07-07 15:49:01
    hash算法原理详解1、什么是Hash2、Hash的特点3、Hash碰撞的解决方案3.1 链地址法3.2 开放地址法3.3 两种方案的demo示例4、hash算法在日常活动中的应用4.1 信息加密4.2 数据校验4.3 负载均衡5、几种hash算法的扩展...

    C/C++Linux服务器开发/后台架构师知识体系资料整理

    1、什么是Hash

    Hash也称散列、哈希,对应的英文都是Hash。基本原理就是把任意长度的输入,通过Hash算法变成固定长度的输出。这个映射的规则就是对应的Hash算法,而原始数据映射后的二进制串就是哈希值。活动开发中经常使用的MD5和SHA都是历史悠久的Hash算法。

    echo md5("这是一个测试文案");
    // 输出结果:2124968af757ed51e71e6abeac04f98d
    

    在这个例子里,这是一个测试文案是原始值,2124968af757ed51e71e6abeac04f98d 就是经过hash算法得到的Hash值。整个Hash算法的过程就是把原始任意长度的值空间,映射成固定长度的值空间的过程。

    2、Hash的特点

    一个优秀的hash算法,需要什么样的要求呢?

    • a)、从hash值不可以反向推导出原始的数据
      这个从上面MD5的例子里可以明确看到,经过映射后的数据和原始数据没有对应关系
    • b)、输入数据的微小变化会得到完全不同的hash值,相同的数据会得到相同的值echo md5(“这是一个测试文案”);// 输出结果:2124968af757ed51e71e6abeac04f98decho md5(“这是二个测试文案”);// 输出结果:bcc2a4bb4373076d494b2223aef9f702
      可以看到我们只改了一个文字,但是整个得到的hash值产生了非常大的变化。
    • c)、哈希算法的执行效率要高效,长的文本也能快速地计算出哈希值
    • d)、hash算法的冲突概率要小
      由于hash的原理是将输入空间的值映射成hash空间内,而hash值的空间远小于输入的空间。根据抽屉原理,一定会存在不同的输入被映射成相同输出的情况。那么作为一个好的hash算法,就需要这种冲突的概率尽可能小。

    桌上有十个苹果,要把这十个苹果放到九个抽屉里,无论怎样放,我们会发现至少会有一个抽屉里面放不少于两个苹果。这一现象就是我们所说的“抽屉原理”。抽屉原理的一般含义为:“如果每个抽屉代表一个集合,每一个苹果就可以代表一个元素,假如有n+1个元素放到n个集合中去,其中必定有一个集合里至少有两个元素。” 抽屉原理有时也被称为鸽巢原理。它是组合数学中一个重要的原理

    3、Hash碰撞的解决方案

    前面提到了hash算法是一定会有冲突的,那么如果我们如果遇到了hash冲突需要解决的时候应该怎么处理呢?比较常用的算法是链地址法和开放地址法。

    3.1 链地址法

    链表地址法是使用一个链表数组,来存储相应数据,当hash遇到冲突的时候依次添加到链表的后面进行处理。
    在这里插入图片描述
    链地址在处理的流程如下:添加一个元素的时候,首先计算元素key的hash值,确定插入数组中的位置。如果当前位置下没有重复数据,则直接添加到当前位置。当遇到冲突的时候,添加到同一个hash值的元素后面,行成一个链表。这个链表的特点是同一个链表上的Hash值相同。java的数据结构HashMap使用的就是这种方法来处理冲突,JDK1.8中,针对链表上的数据超过8条的时候,使用了红黑树进行优化。

    3.2 开放地址法

    开放地址法是指大小为 M 的数组保存 N 个键值对,其中 M > N。我们需要依靠数组中的空位解决碰撞冲突。基于这种策略的所有方法被统称为“开放地址”哈希表。线性探测法,就是比较常用的一种“开放地址”哈希表的一种实现方式。线性探测法的核心思想是当冲突发生时,顺序查看表中下一单元,直到找出一个空单元或查遍全表。简单来说就是:一旦发生冲突,就去寻找下 一个空的散列表地址,只要散列表足够大,空的散列地址总能找到

    线性探测法的数学描述是:h(k, i) = (h(k, 0) + i) mod m,i表示当前进行的是第几轮探查。i=1时,即是探查h(k, 0)的下一个;i=2,即是再下一个。这个方法是简单地向下探查。mod m表示:到达了表的底下之后,回到顶端从头开始。

    对于开放寻址冲突解决方法,除了线性探测方法之外,还有另外两种比较经典的探测方法,二次探测(Quadratic probing)和双重散列(Double hashing)。但是不管采用哪种探测方法,当散列表中空闲位置不多的时候,散列冲突的概率就会大大提高。为了尽可能保证散列表的操作效率,一般情况下,我们会尽可能保证散列表中有一定比例的空闲槽位。我们用装载因子(load factor)来表示空位的多少。

    散列表的装载因子=填入表中的元素个数/散列表的长度。装载因子越大,说明冲突越多,性能越差。

    3.3 两种方案的demo示例

    假设散列长为8,散列函数H(K)=K mod 7,给定的关键字序列为{32,14,23,2, 20}
    当使用链表法时,相应的数据结构如下图所示:
    在这里插入图片描述
    当使用线性探测法时,相应的数据结果如下图所示:
    在这里插入图片描述这里的两种算法的区别是2这个元素,在链表法中还是在节点2的位置上,但是在线性探测法遇到冲突时会将冲突数据放到下一个空的位置下面。

    4、hash算法在日常活动中的应用

    在日常运营活动中,我们活动开发经常遇到的应用场景是信息加密、数据校验、负载均衡。下面分别对这三种应用场景进行讲解。

    4.1 信息加密

    首先我们看一下信息加密的应用。2011年CSDN脱库事件,导致超过600W的用户的密码泄露,让人失望的是,CSDN是明文存储用户的注册邮箱和密码的。作为用户的非常隐私的信息,最简单的保护措施就是对密码进行hash加密。在客户端对用户输入的密码进行hash运算,然后在服务端的数据库中保存用户密码的hash值。由于服务器端也没有存储密码的明文,所以目前很多网站也就不再有找回密码的功能了。

    • 这里也友情提示一下大家:如果在使用中发现某网站还有提供找回密码的功能,就要好好担心下这个网站的安全性了。

    看到这里有些同学会觉得那么我们是不是对用户输入的密码进行一次MD5加密就可以了呢,这样就算恶意用户知道了hash值,也没有办法拿到用户的真实密码。假设用户的密码是123456789,经过一次md5以后得到的值是:

    25f9e794323b453885f5181f1b624d0b
    

    那么是不是使用了这个加密后的字符串来存密码就万无一失了呢,理想总是很丰满,而现实总是很骨感的。

    大家可以看一下这个网站:

    https://www.cmd5.com/

    这里是该网站的相关介绍:

    本站针对md5、sha1等全球通用公开的加密算法进行反向查询,通过穷举字符组合的方式,创建了明文密文对应查询数据库,创建的记录约90万亿条,占用硬盘超过500TB,查询成功率95%以上,很多复杂密文只有本站才可查询。已稳定运行十余年,国内外享有盛誉

    在这里插入图片描述

    那么一般针对这种问题,我们的解决之道就是引入salt(加盐),即利用特殊字符(盐)和用户的输入合在一起组成新的字符串进行加密。通过这样的方式,增加了反向查询的复杂度。但是这样的方式也不是万无一失,如果发生了盐被泄露的问题,就需要所有用到的地方来重置密码。

    针对salt泄露的问题,其实还有一种解决办法,即使用HMAC进行加密(Hash-based Message Authentication Code)。这种算法的核心思路是加密使用的key是从服务器端获取的,每一个用户的是不一样的。如果发生了泄露,那么也就是这一个用户的会被泄露,不会影响到全局。

    这里也留给大家一个思考点,如果恶意用户直接抓取了你的活动参与链接,也就是拿到了你计算后的hash值,那从技术的角度上说,我们还有没有其他可以提升恶意用户的违法成本呢?

    4.2 数据校验

    - git commit id
    使用过git的同学都应该清楚,每次git提交后都有一个commit id,比如:

    19d02d2cc358e59b3d04f82677dbf3808ae4fc40
    

    就是一次git commit的结果,那么这个id是如何生成出来的呢?查阅了相关资料,使用如下代码可以进行查看:

    printf "commit %s\0" $(git cat-file commit HEAD | wc -c); git cat-file commit HEAD
    

    git的commit id主要包括了以下几部分内容:Tree 哈希,parent哈希、作者信息和本次提交的备注。
    在这里插入图片描述
    针对这些信息进行SHA-1 算法后得到值就是本次提交的commit id。简单来讲,就是对于单次提交的头信息的一个校验和。

    Linux kernel开创者和Git的开发者——Linus说,Git使用了sha1并非是为了安全性,而是为了数据的完整性;它可以保证,在很多年后,你重新checkout某个commit时,一定是它多年前的当时的状态,完全一摸一样,完全值得信任。

    但最新研究表明,理论上对其进行哈希碰撞(hash collision,不同的两块数据有相同的hash值)的攻击可以在2^51(2的51次方)左右的次数内实现。不过由于commit id 是针对单个仓库里的,所以实际应用中我们可以认为如果两个文件的SHA-1值是相同的,那么它们确是完全相同的内容。

    注:对于git里tree、parent等结构感兴趣的同学,可以参考下这篇文章《Git 内部原理 - Git 对象》,这里由于篇幅原因就不进行深入分析了。

    • 版权校验
      在数据校验方面的另一个应用场景就是版权的保护或者违禁信息的打击,比如某个小视频,第一个用户上传的时候,我们认为是版权所有者,计算一个hash值存下来。当第二个用户上传的时候,同样计算hash值,如果hash值一样的话,就算同一个文件。这种方案其实也给用户传播违禁文件提高了一些门槛,不是简单的换一个名字或者改一下后缀名就可以躲避掉打击了。(当然这种方式也是可以绕过的,图片的你随便改一下颜色,视频去掉一帧就又是完全不同的hash值了。注意:我没有教你变坏,我只是和你在讨论这个技术。。。)另外我们在社区里,也会遇到玩家重复上传同一张图片或者视频的情况,使用这种校验的方式,可以有效减少cos服务的存储空间。
    • 大文件分块校验
      使用过bt的同学都有经验,在p2p网络中会把一个大文件拆分成很多小的数据各自传输。这样的好处是如果某个小的数据块在传输过程中损坏了,只要重新下载这个块就好。为了确保每一个小的数据块都是发布者自己传输的,我们可以对每一个小的数据块都进行一个hash的计算,维护一个hash List,在收到所有数据以后,我们对于这个hash List里的每一块进行遍历比对。这里有一个优化点是如果文件分块特别多的时候,如果遍历对比就会效率比较低。可以把所有分块的hash值组合成一个大的字符串,对于这个字符串再做一次Hash运算,得到最终的hash(Root hash)。在实际的校验中,我们只需要拿到了正确的Root hash,即可校验Hash List,也就可以校验每一个数据块了。

    在这里插入图片描述

    4.3 负载均衡

    活动开发同学在应对高星级业务大用户量参与时,都会使用分库分表,针对用户的openid进行hashtime33取模,就可以得到对应的用户分库分表的节点了。
    在这里插入图片描述
    如上图所示,这里其实是分了10张表,openid计算后的hash值取模10,得到对应的分表,在进行后续处理就好。对于一般的活动或者系统,我们一般设置10张表或者100张表就好。

    下面我们来看一点复杂的问题,假设我们活动初始分表了10张,运营一段时间以后发现需要10张不够,需要改到100张。这个时候我们如果直接扩容的话,那么所有的数据都需要重新计算Hash值,大量的数据都需要进行迁移。如果更新的是缓存的逻辑,则会导致大量缓存失效,发生雪崩效应,导致数据库异常。造成这种问题的原因是hash算法本身的缘故,只要是取模算法进行处理,则无法避免这种情况。针对这种问题,我们就需要利用一致性hash进行相应的处理了。

    一致性hash的基本原理是将输入的值hash后,对结果的hash值进行2^32取模,这里和普通的hash取模算法不一样的点是在一致性hash算法里将取模的结果映射到一个环上。将缓存服务器与被缓存对象都映射到hash环上以后,从被缓存对象的位置出发,沿顺时针方向遇到的第一个服务器,就是当前对象将要缓存于的服务器,由于被缓存对象与服务器hash后的值是固定的,所以,在服务器不变的情况下,一个openid必定会被缓存到固定的服务器上,那么,当下次想要访问这个用户的数据时,只要再次使用相同的算法进行计算,即可算出这个用户的数据被缓存在哪个服务器上,直接去对应的服务器查找对应的数据即可。这里的逻辑其实和直接取模的是一样的。如下图所示:

    在这里插入图片描述初始情况如下:用户1的数据在服务器A里,用户2、3的数据存在服务器C里,用户4的数据存储在服务器B里

    下面我们来看一下当服务器数量发生变化的时候,相应影响的数据情况:

    • 服务器缩容
      在这里插入图片描述
      服务器B发生了故障,进行剔除后,只有用户4的数据发生了异常。这个时候我们需要继续按照顺时针的方案,把缓存的数据放在用户A上面。

    • 服务器扩容
      同样的,我们进行了服务器扩容以后,新增了一台服务器D,位置落在用户2和3之间。按照顺时针原则,用户2依然访问的是服务器C的数据,而用户3顺时针查询后,发现最近的服务器是D,后续数据就会存储到d上面。
      在这里插入图片描述

    • 虚拟节点
      当然这只是一种理想情况,实际使用中,由于服务器节点数量有限,有可能出现分布不均匀的情况。这个时候会出现大量数据都被映射到某一台服务器的情况,如下图左侧所示。为了解决这个问题,我们采用了虚拟节点的方案。虚拟节点是实际节点(实际的物理服务器)在hash环上的复制品,一个实际节点可以对应多个虚拟节点。虚拟节点越多,hash环上的节点就越多,数据被均匀分布的概率就越大。


    如右图所示,B、C、D 是原始节点复制出来的虚拟节点,原本都要访问机器D的用户1、4,分别被映射到了B,D。通过这样的方式,起到了一个服务器均匀分布的作用。

    5、几种hash算法的扩展应用

    下面介绍几种大家可能不经常遇到的应用,由于篇幅原因,不做深入介绍,只抛砖引玉。

    5.1 SimHash

    simHash是google用于海量文本去重的一种方法,它是一种局部敏感hash。那什么叫局部敏感呢,假定两个字符串具有一定的相似性,在hash之后,仍然能保持这种相似性,就称之为局部敏感hash。普通的hash是不具有这种属性的。simhash被Google用来在海量文本中去重。

    simHash算法的思路大致如下:

    • 将Doc进行关键词抽取(其中包括分词和计算权重),抽取出n个(关键词,权重)对, 即图中的多个(feature, weight)。记为 feature_weight_pairs = [fw1, fw2 … fwn],其中 fwn = (feature_n,weight_n)。
    • 对每个feature_weight_pairs中的feature进行hash。然后对hash_weight_pairs进行位的纵向累加,如果该位是1,则+weight,如果是0,则-weight,最后生成bits_count个数字,大于0标记1,小于0标记0
    • 最后转换成一个64位的字节,判断重复只需要判断他们的特征字的距离是不是<n (n根据经验一般取3),就可以判断两个文档是否相似。

    在这里插入图片描述
    如下图所示,当两个文本只有一个字变化时,如果使用普通Hash则会导致两次的结果发生较大改变,而SimHash的局部敏感特性,会导致只有部分数据发生变化。
    在这里插入图片描述

    5.2 GeoHash

    GeoHash将地球作为为一个二维平面进行递归分解。每个分解后的子块在一定经纬度范围内拥有相同的编码。以下图为例,这个矩形区域内所有的点(经纬度坐标)都共享相同的GeoHash字符串,这样既可以保护隐私(只表示大概区域位置而不是具体的点),又比较容易做缓存。


    下面以一个例子来理解下这个算法,我们对纬度39.3817进行逼近编码 :

    • 地球纬度区间是[-90,90],对于这个区间进行二分划分左区间[-90,0), 右区间[0,90]。39.3817属于右区间,标记为1
    • 将右区间[0,90]继续进行划分,左区间[0,45) ,右区间[45,90]。39.3817属于左区间,标记为0
    • 递归上面的过程,随着每次迭代,区间[a,b]会不断接近39.3817。递归的次数决定了生成的序列长度。
    • 对于经度做同样的处理。得到的字符串,偶数位放经度,奇数位放纬度,把2串编码组合生成新串。对于新串转成对应10进制查出实际的base32编码就是类似WX4ER的hash值。

    整体递归过程如下表所示:
    在这里插入图片描述

    5.3 布隆过滤器

    布隆过滤器被广泛用于黑名单过滤、垃圾邮件过滤、爬虫判重系统以及缓存穿透问题。对于数量小,内存足够大的情况,我们可以直接用hashMap或者hashSet就可以满足这个活动需求了。但是如果数据量非常大,比如5TB的硬盘上放满了用户的参与数据,需要一个算法对这些数据进行去重,取得活动的去重参与用户数。这种时候,布隆过滤器就是一种比较好的解决方案了。

    布隆过滤器其实是基于bitmap的一种应用,在1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数,用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难,主要用于大数据去重、垃圾邮件过滤和爬虫url记录中。核心思路是使用一个bit来存储多个元素,通过这样的方式来减少内存的消耗。通过多个hash函数,将每个数据都算出多个值,存放在bitmap中对应的位置上。

    布隆过滤器的原理见下图所示:
    在这里插入图片描述
    上图所示的例子中,数据a、b、c经过三次hash映射后,对应的bit位都是1,表示这三个数据已经存在了。而d这份数据经过映射后有一个结果是0,则表明d这个数据一定没有出现过。布隆过滤器存在假阳率(判定存在的元素可能不存在)的问题,但是没有假阴率(判断不存在的原因可能存在)的问题。即对于数据e,三次映射的结果都是1,但是这份数据也可能没有出现过。

    误判率的数据公式如下所示:
    在这里插入图片描述
    其中,p是误判率,n是容纳的元素,m是需要的存储空间。由公示可以看出,布隆过滤器的长度会直接影响误报率,布隆过滤器越长其误报率越小。哈希函数的个数也需要权衡,个数越多则布隆过滤器 bit 位置位 1 的速度越快,且布隆过滤器的效率越低;但是如果太少的话,则会导致误报率升高。

    6、总结

    Hash算法作为一种活动开发经常遇到的算法,我们在使用中不仅仅要知道这种算法背后真正的原理,才可以在使用上做到有的放矢。Hash的相关知识还有很多,有兴趣的同学可以继续深入研究。

    作者:腾讯技术工程
    链接:https://www.zhihu.com/question/26762707/answer/890181997

    C/C++Linux服务器开发/后台架构师面试题、学习资料、教学视频和学习路线图如有需要的可以自行添加学习交流群960994558

    展开全文
  • // 写在前面的话和背景因为做项目涉及到用户在浏览器或者用户windows的桌面系统中输入完用户名和密码,发http的rest请求到nodejs server端,server端验证用户名和密码是有效后(可以请求db或者ldap),继续后续的业务...


    // 写在前面的话和背景

    因为做项目涉及到用户在浏览器或者用户windows的桌面系统中输入完用户名和密码,发http的rest请求到nodejs server端,server端验证用户名和密码是有效后(可以请求db或者ldap),继续后续的业务逻辑操作(比如操作db或者读取server上的文件),将操作结果返回给请求端。

    上面的一系列操作,比如 

      1. 当用户输入密码(是否要加密,比如salt等), 

      2. 密码传输(https?如果是在windows上桌面请求怎么保证传输的安全性?), 

      3. nodejs server是否要解密(比如加 salt的密码?),在做 ladp验证?还是 ladp支持加 salt的验证?

    11. 下面的文章不能回答上面的问题,文章中c#举例,但至少是对 密码加密有个基础或者概念性的了解

    http://www.cnblogs.com/leoo2sk/archive/2010/10/01/hash-and-encrypt.html


    2010-10-01 00:09 by T2噬菌体, 44948 阅读, 46 评论, 收藏编辑

    0、摘要

          今天看到吉日嘎拉一篇关于管理软件中信息加密和安全的文章,感觉非常有实际意义。文中作者从实践经验出发,讨论了信息管理软件中如何通过哈希和加密进行数据保护。但是从文章评论中也可以看出很多朋友对这个方面一些基本概念比较模糊,这样就容易“照葫芦画瓢”,不能根据自身具体情况灵活选择和使用各种哈希和加密方式。本文不对哈希和加密做过于深入的讨论,而是对哈希和加密的基本概念和原理进行阐述、比较,并结合具体实践说明如何选择哈希和加密算法、如何提高安全性等问题,使朋友们做到“知其然,知其所以然”,这样就能通过分析具体情况,灵活运用哈希和加密保护数据。

    1、哈希(Hash)与加密(Encrypt)的区别

          在本文开始,我需要首先从直观层面阐述哈希(Hash)加密(Encrypt)的区别,因为我见过很多朋友对这两个概念不是很清晰,容易混淆两者。而正确区别两者是正确选择和使用哈希与加密的基础。

          概括来说,哈希(Hash)是将目标文本转换成具有相同长度的、不可逆的杂凑字符串(或叫做消息摘要),而加密(Encrypt)是将目标文本转换成具有不同长度的、可逆的密文。

          具体来说,两者有如下重要区别:

          1、哈希算法往往被设计成生成具有相同长度的文本,而加密算法生成的文本长度与明文本身的长度有关。

          例如,设我们有两段文本:“Microsoft”和“Google”。两者使用某种哈希算法得到的结果分别为:“140864078AECA1C7C35B4BEB33C53C34”和“8B36E9207C24C76E6719268E49201D94”,而使用某种加密算法的到的结果分别为“Njdsptpgu”和“Hpphmf”。可以看到,哈希的结果具有相同的长度,而加密的结果则长度不同。实际上,如果使用相同的哈希算法,不论你的输入有多么长,得到的结果长度是一个常数,而加密算法往往与明文的长度成正比。

          2、哈希算法是不可逆的,而加密算法是可逆的。

          这里的不可逆有两层含义,一是“给定一个哈希结果R,没有方法将E转换成原目标文本S”,二是“给定哈希结果R,即使知道一段文本S的哈希结果为R,也不能断言当初的目标文本就是S”。其实稍微想想就知道,哈希是不可能可逆的,因为如果可逆,那么哈希就是世界上最强悍的压缩方式了——能将任意大小的文件压缩成固定大小。

          加密则不同,给定加密后的密文R,存在一种方法可以将R确定的转换为加密前的明文S。

          这里先从直观层面简单介绍两者的区别,等下文从数学角度对两者做严谨描述后,读者朋友就知道为什么会有这两个区别了。

    2、哈希(Hash)与加密(Encrypt)的数学基础

          从数学角度讲,哈希和加密都是一个映射。下面正式定义两者:

          一个哈希算法是一个多对一映射,给定目标文本S,H可以将其唯一映射为R,并且对于所有S,R具有相同的长度。由于是多对一映射,所以H不存在逆映射

    使得R转换为唯一的S。

          一个加密算法是一个一一映射,其中第二个参数叫做加密密钥,E可以将给定的明文S结合加密密钥Ke唯一映射为密文R,并且存在另一个一一映射,可以结合Kd将密文R唯一映射为对应明文S,其中Kd叫做解密密钥。

          下图是哈希和加密过程的图示:

          有了以上定义,就很清楚为什么会存在上文提到的两个区别了。由于哈希算法的定义域是一个无限集合,而值域是一个有限集合,将无限集合映射到有限集合,根据“鸽笼原理(Pigeonhole principle)”,每个哈希结果都存在无数个可能的目标文本,因此哈希不是一一映射,是不可逆的。

          而加密算法是一一映射,因此理论上来说是可逆的。

          但是,符合上面两个定义的映射仅仅可以被叫做哈希算法和加密算法,但未必是好的哈希和加密,好的哈希和加密往往需要一些附加条件,下面介绍这些内容。

          一个设计良好的哈希算法应该很难从哈希结果找到哈希目标文本的碰撞(Collision)。那么什么是碰撞呢?对于一个哈希算法H,如果,则S1和S2互为碰撞。关于为什么好的哈希需要难以寻找碰撞,在下面讲应用的时候会详解。另外,好的哈希算法应该对于输入的改变极其敏感,即使输入有很小的改动,如一亿个字符变了一个字符,那么结果应该截然不同。这就是为什么哈希可以用来检测软件的完整性。

          一个设计良好的加密算法应该是一个“单向陷门函数(Trapdoor one-way function)”,单向陷门函数的特点是一般情况下即使知道函数本身也很难将函数的值转换回函数的自变量,具体到加密也就是说很难从密文得到明文,虽然从理论上这是可行的,而“陷门”是一个特殊的元素,一旦知道了陷门,则这种逆转换则非常容易进行,具体到加密算法,陷门就是密钥。

          顺便提一句,在加密中,应该保密的仅仅是明文和密钥。也就是说我们通常假设攻击者对加密算法和密文了如指掌,因此加密的安全性应该仅仅依赖于密钥而不是依赖于假设攻击者不知道加密算法。

    3、哈希(Hash)与加密(Encrypt)在软件开发中的应用

          哈希与加密在现代工程领域应用非常广泛,在计算机领域也发挥了很大作用,这里我们仅仅讨论在平常的软件开发中最常见的应用——数据保护。

          所谓数据保护,是指在数据库被非法访问的情况下,保护敏感数据不被非法访问者直接获取。这是非常有现实意义的,试想一个公司的安保系统数据库服务器被入侵,入侵者获得了所有数据库数据的查看权限,如果管理员的口令(Password)被明文保存在数据库中,则入侵者可以进入安保系统,将整个公司的安保设施关闭,或者删除安保系统中所有的信息,这是非常严重的后果。但是,如果口令经过良好的哈希或加密,使得入侵者无法获得口令明文,那么最多的损失只是被入侵者看到了数据库中的数据,而入侵者无法使用管理员身份进入安保系统作恶。

    3.1、哈希(Hash)与加密(Encrypt)的选择

          要实现上述的数据保护,可以选择使用哈希或加密两种方式。那么在什么时候该选择哈希、什么时候该选择加密呢?

          基本原则是:如果被保护数据仅仅用作比较验证,在以后不需要还原成明文形式,则使用哈希;如果被保护数据在以后需要被还原成明文,则需要使用加密。

          例如,你正在做一个系统,你打算当用户忘记自己的登录口令时,重置此用户口令为一个随机口令,而后将此随机口令发给用户,让用户下次使用此口令登录,则适合使用哈希。实际上很多网站都是这么做的,想想你以前登录过的很多网站,是不是当你忘记口令的时候,网站并不是将你忘记的口令发送给你,而是发送给你一个新的、随机的口令,然后让你用这个新口令登录。这是因为你在注册时输入的口令被哈希后存储在数据库里,而哈希算法不可逆,所以即使是网站管理员也不可能通过哈希结果复原你的口令,而只能重置口令。

          相反,如果你做的系统要求在用户忘记口令的时候必须将原口令发送给用户,而不是重置其口令,则必须选择加密而不是哈希。

    3.2、使用简单的一次哈希(Hash)方法进行数据保护

          首先我们讨论使用一次哈希进行数据保护的方法,其原理如下图所示:

          对上图我想已无需多言,很多朋友应该使用过类似的哈希方法进行数据保护。当前最常用的哈希算法是MD5SHA1,下面给出在.NET平台上用C#语言实现MD5和SHA1哈希的代码,由于.NET对于这两个哈希算法已经进行很很好的封装,因此我们不必自己实现其算法细节,直接调用相应的库函数即可(实际上MD5和SHA1算法都十分复杂,有兴趣的可以参考维基百科)。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    using  System;
    using  System.Web.Security;
     
    namespace  HashAndEncrypt
    {
         /// <summary>
         /// 哈希(Hash)工具类
         /// </summary>
         public  sealed  class  HashHelper
         {
             /// <summary>
             /// 使用MD5算法进行哈希
             /// </summary>
             /// <param name="source">源字串</param>
             /// <returns>杂凑字串</returns>
             public  static  string  MD5Hash( string  source)
             {
                 return  FormsAuthentication.HashPasswordForStoringInConfigFile(source, "MD5" );
             }
     
             /// <summary>
             /// 使用SHA1算法进行哈希
             /// </summary>
             /// <param name="source">源字串</param>
             /// <returns>杂凑字串</returns>
             public  static  string  SHA1Hash( string  source)
             {
                 return  FormsAuthentication.HashPasswordForStoringInConfigFile(source, "SHA1" );
             }
         }
    }

    3.3、对简单哈希(Hash)的攻击

          下面我们讨论上述的数据保护方法是否安全。

          对于哈希的攻击,主要有寻找碰撞法穷举法

          先来说说寻找碰撞法。从哈希本身的定义和上面的数据保护原理图可以看出,如果想非法登录系统,不一定非要得到注册时的输入口令,只要能得到一个注册口令的碰撞即可。因此,如果能从杂凑串中分析出一个口令的碰撞,则大功告成。

          不过我的意见是,对这种攻击大可不必担心,因为目前对于MD5和SHA1并不存在有效地寻找碰撞方法。虽然我国杰出的数学家王小云教授曾经在国际密码学会议上发布了对于MD5和SHA1的碰撞寻找改进算法,但这种方法和很多人口中所说的“破解”相去甚远,其理论目前仅具有数学上的意义,她将破解MD5的预期步骤数从2^80降到了2^69,虽然从数学上降低了好几个数量级,但2^69对于实际应用来说仍然是一个天文数字,就好比以前需要一亿年,现在需要一万年一样。

          不过这并不意味着使用MD5或SHA1后就万事大吉了,因为还有一种对于哈希的攻击方法——穷举法。通俗来说,就是在一个范围内,如从000000到999999,将其中所有值一个一个用相同的哈希算法哈希,然后将结果和杂凑串比较,如果相同,则这个值就一定是源字串或源字串的一个碰撞,于是就可以用这个值非法登录了。

          例如,下文是对MD5的穷举攻击的代码(设攻击范围为000000到999999):

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    using  System;
    using  System.Web.Security;
     
    namespace  HashAndEncrypt
    {
         /// <summary>
         /// MD5攻击工具类
         /// </summary>
         public  sealed  class  MD5AttackHelper
         {
             /// <summary>
             /// 对MD5进行穷举攻击
             /// </summary>
             /// <param name="hashString">杂凑串</param>
             /// <returns>杂凑串的源串或源串碰撞(攻击失败则返回null)</returns>
             public  static  string  AttackMD5( string  hashString)
             {
                 for  ( int  i = 0; i <= 999999; i++)
                 {
                     string  testString = i.ToString();
                     while  (testString.Length < 6)
                         testString = "0"  + testString;
     
                     if  (FormsAuthentication.HashPasswordForStoringInConfigFile(testString, "MD5" ) == hashString)
                         return  testString;
                 }
     
                 return  null ;
             }
         }
    }

          这种看似笨拙的方法,在现实中爆发的能量却是惊人的,目前几乎所有的MD5破解机或MD5在线破解都是用这种穷举法,但就是这种“笨”方法,却成功破解出很多哈希串。纠其缘由,就是相当一部分口令是非常简单的,如“123456”或“000000”这种口令还有很多人在用,可以看出,穷举法是否能成功很大程度上取决于口令的复杂性。因为穷举法扫描的区间往往是单字符集、规则的区间,或者由字典数据进行组合,因此,如果使用复杂的口令,例如“ASDF#$%uiop.8930”这种变态级口令,穷举法就很难奏效了。

    3.4、对一次哈希(Hash)的改进——多重混合哈希(Hash)

          上面说过,如果口令过于简单,则使用穷举法可以很有效地破解出一次哈希后的杂凑串。如果不想这样,只有让用户使用复杂口令,但是,很多时候我们并不能强迫用户,因此,我们需要想一种办法,即使用户使用诸如“000000”这种简单密码,也令穷举法难奏效。其中一种办法就是使用多重哈希,所谓多重哈希就是使用不同的哈希函数配合自定义的Key对口令进行多次哈希,如果Key很复杂,那么穷举法将变得异常艰难。

          例如,如果使用下面的混合公式进行哈希:

          如果将Key设为一个极为复杂的字符串,那么在攻击者不知道Key的情况下,几乎无法通过穷举法破解。因为即使S很简单,但是Key的MD5值几乎是无法在合理时间内穷举完的。下面是这种多重混合哈希的代码实现:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    using  System;
    using  System.Web.Security;
     
    namespace  HashAndEncrypt
    {
         /// <summary>
         /// 多重混合哈希工具类
         /// </summary>
         public  sealed  class  HashHelper
         {
             private  static  readonly  String hashKey = "qwer#&^Buaa06" ;
             /// <summary>
             /// 对敏感数据进行多重混合哈希
             /// </summary>
             /// <param name="source">待处理明文</param>
             /// <returns>Hasn后的数据</returns>
             public  static  String Hash(String source)
             {
                 String hashCode = FormsAuthentication.HashPasswordForStoringInConfigFile(source, "MD5" ) +
                                   FormsAuthentication.HashPasswordForStoringInConfigFile(hashKey, "MD5" );
                 return  FormsAuthentication.HashPasswordForStoringInConfigFile(hashCode, "SHA1" );
             }
         }
    }

    3.5、使用加密(Encrypt)方法进行数据保护

          加密方法如果用于口令保护的话,与上述哈希方法的流程基本一致,只是在需要时,可以使用解密方法得到明文。关于加密本身是一个非常庞大的系统,而对于加密算法的攻击更是可以写好几本书了,所以这里从略。下面只给出使用C#进行DES加密和解密的代码。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    using  System;
    using  System.Security.Cryptography;
    using  System.Text;
    using  System.Web.Security;
     
    namespace  HashAndEncrypt
    {
         /// <summary>
         /// 工具类,封装了加解密相关操作
         /// </summary>
         public  sealed  class  EncryptHelper
         {
             private  static  readonly  Byte[] DesKey = {5, 7, 8, 9, 0, 2, 1, 6};
             private  static  readonly  Byte[] DesVi = { 6, 9, 8, 5, 1, 6, 2, 8 };
             /// <summary>
             /// 使用DES算法加密数据
             /// </summary>
             /// <param name="data">待加密数据</param>
             /// <returns>密文</returns>
             public  static  String Encrypt(String data)
             {
                 DESCryptoServiceProvider des = new  DESCryptoServiceProvider();
                 Encoding utf = new  UTF8Encoding();
                 ICryptoTransform encryptor = des.CreateEncryptor(DesKey, DesVi);
     
                 byte [] bData = utf.GetBytes(data);
                 byte [] bEnc = encryptor.TransformFinalBlock(bData, 0, bData.Length);
                 return  Convert.ToBase64String(bEnc);
             }
     
             /// <summary>
             /// 使用DES算法解密数据
             /// </summary>
             /// <param name="data">待解密数据</param>
             /// <returns>明文</returns>
             public  static  String Decrypt(String data)
             {
                 DESCryptoServiceProvider des = new  DESCryptoServiceProvider();
                 Encoding utf = new  UTF8Encoding();
                 ICryptoTransform decryptor = des.CreateDecryptor(DesKey, DesVi);
     
                 byte [] bEnc = Convert.FromBase64String(data);
                 byte [] bDec = decryptor.TransformFinalBlock(bEnc, 0, bEnc.Length);
                 return  utf.GetString(bDec);
             }
         }
    }

    4、总结

          密码学本身是一个非常深奥的数学分支,对于普通开发者,不需要了解过于深入的密码学知识。本文仅仅讲述哈希与加密的基础内容,并对两者做了比较,帮助读者明晰概念,另外,对一些实际应用情况进行了简单的讨论。希望本文对大家有所帮助。看了下时间,零点刚过,祝大家十一快乐!玩得开心!

    __________________________________________________________________________________________________________

    __________________________________________________________________________________________________________

    12: 【转载】 加盐密码哈希:如何正确使用

    http://blog.jobbole.com/61872/

    如果你是Web开发者,你很可能需要开发一个用户账户系统。这个系统最重要的方面,就是怎样保护用户的密码。存放帐号的数据库经常成为入侵的目标,所以你必须做点什么来保护密码,以防网站被攻破时发生危险。最好的办法就是对密码进行加盐哈希,这篇文章将介绍它是如何做到这点。

    在对密码进行哈希加密的问题上,人们有许多争论和误解,这大概是由于网络上广泛的误传吧。密码哈希是一件非常简单的事情,但是依然有很多人理解错误了。本文阐述的并不是进行密码哈希唯一正确的方法,但是会告诉你为什么这样是正确的。

    郑重警告:如果你在试图编写自己的密码哈希代码,赶紧停下来!那太容易搞砸了。即使你受过密码学的高等教育,也应该听从这个警告。这是对所有人说的:不要自己写加密函数!安全存储密码的难题现在已经被解决了,请使用phpass或者本文给出的一些源代码。

    如果因为某些原因你忽视了上面那个红色警告,请翻回去好好读一遍,我是认真的。这篇文章的目的不是教你研究出自己的安全算法,而是讲解为什么密码应该被这样储存。

    下面一些链接可以用来快速跳转到本文的各章节。

    1. 为什么密码需要进行哈希?
    2. 如何破解哈希加密
    3. 加盐
    4. 无效的哈希方法
    5. 恰当使用哈希加密
    6. 常见问题

    这里也给出了一些基于BSD许可的哈希函数源代码:

    为什么密码需要进行哈希?


    hash("hello") = 2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824
    hash("hbllo") = 58756879c05c68dfac9866712fad6a93f8146f337a69afe7dd238f3364946366
    hash("waltz") = c0e81794384491161f1777c232bc6bd9ec38f616560b120fda8e90f383853542

    哈希算法是一个单向函数。它可以将任何大小的数据转化为定长的“指纹”,并且无法被反向计算。另外,即使数据源只改动了一丁点,哈希的结果也会完全不同(参考上面的例子)。这样的特性使得它非常适合用于保存密码,因为我们需要加密后的密码无法被解密,同时也能保证正确校验每个用户的密码。

    在基于哈希加密的账户系统中,通常用户注册和认证的流程是这样的:

    1. 用户注册一个帐号
    2. 密码经过哈希加密储存在数据库中。只要密码被写入磁盘,任何时候都不允许是明文
    3. 当用户登录的时候,从数据库取出已经加密的密码,和经过哈希的用户输入进行对比
    4. 如果哈希值相同,用户获得登入授权,否则,会被告知输入了无效的登录信息
    5. 每当有用户尝试登录,以上两步都会重复

    在第4步中,永远不要告诉用户到底是用户名错了,还是密码错了。只需要给出一个大概的提示,比如“无效的用户名或密码”。这可以防止攻击者在不知道密码的情况下,枚举出有效的用户名。

    需要提到的是,用于保护密码的哈希函数和你在数据结构中学到的哈希函数是不同的。比如用于实现哈希表这之类数据结构的哈希函数,它们的目标是快速查找,而不是高安全性。只有加密哈希函数才能用于保护密码,例如SHA256,SHA512,RipeMD和WHIRLPOOL。

    也许你很容易就认为只需要简单地执行一遍加密哈希函数,密码就能安全,那么你大错特错了。有太多的办法可以快速地把密码从简单哈希值中恢复出来,但也有很多比较容易实现的技术能使攻击者的效率大大降低。黑客的进步也在激励着这些技术的进步,比如这样一个网站:你可以提交一系列待破解的哈希值,并且在不到1秒的时间内得到了结果。显然,简单哈希加密并不能满足我们对安全性的需求。

    那么下一节会讲到几种常用的破解简单哈希加密的办法。

    如何破解哈希加密


    字典攻击和暴力攻击

    Dictionary Attack
    Trying apple : failed
    Trying blueberry : failed
    Trying justinbeiber : failed
    ...
    Trying letmein : failed

    Trying s3cr3t : success!
    Brute Force Attack
    Trying aaaa : failed
    Trying aaab : failed
    Trying aaac : failed
    ...
    Trying acdb : failed

    Trying acdc : success!

    • 破解哈希加密最简单的办法,就是去猜,将每个猜测值哈希之后的结果和目标值比对,如果相同则破解成功。两种最常见的猜密码的办法是字典攻击暴力攻击

    • 字典攻击需要使用一个字典文件,它包含单词、短语、常用密码以及其他可能用作密码的字符串。其中每个词都是进过哈希后储存的,用它们和密码哈希比对,如果相同,这个词就是密码。字典文件的构成是从大段文本中分解出的单词,甚至还包括一些数据库中真实的密码。然后还可以对字典文件进行更进一步的处理使它更有效,比如把单词中的字母替换为它们的“形近字”(hello变为h3110)。

    • 暴力攻击会尝试每一个在给定长度下各种字符的组合。这种攻击会消耗大量的计算,也通常是破解哈希加密中效率最低的办法,但是它最终会找到正确的密码。因此密码需要足够长,以至于遍历所有可能的字符串组合将耗费太长时间,从而不值得去破解它。

    • 我们没有办法阻止字典攻击和暴击攻击,尽管可以降低它们的效率,但那也不是完全阻止。如果你的密码哈希系统足够安全,唯一的破解办法就是进行字典攻击或者暴力遍历每一个哈希值。

    查表法

    Searching: 5f4dcc3b5aa765d61d8327deb882cf99: FOUND: password5
    Searching: 6cbe615c106f422d23669b610b564800: not in database
    Searching: 630bf032efe4507f2c57b280995925a9: FOUND: letMEin12
    Searching: 386f43fab5d096a7a66d67c8f213e5ec: FOUND: mcd0nalds
    Searching: d5ec75d5fe70d428685510fae36492d9: FOUND: p@ssw0rd!

    查表法对于破解一系列算法相同的哈希值有着无与伦比的效率。主要的思想就是预计算密码字典中的每个密码,然后把哈希值和对应的密码储存到一个用于快速查询的数据结构中。一个良好的查表实现可以每秒进行数百次哈希查询,即使表中储存了几十亿个哈希值。

    如果你想更好地体验查表法的速度,尝试使用CrackStation的free hash cracker来破解下图中四个SHA256加密的哈希值吧。

    c11083b4b0a7743af748c85d343dfee9fbb8b2576c05f3a7f0d632b0926aadfc
    08eac03b80adc33dc7d8fbe44b7c7b05d3a2c511166bdb43fcb710b03ba919e7
    e4ba5cbd251c98e6cd1c23f126a3b81d8d8328abc95387229850952b3ef9f904
    5206b8b8a996cf5320cb12ca91c7b790fba9f030408efe83ebb83548dc3007bd

    反向查表法

    Searching for hash(apple) in users' hash list... : Matches [alice3, 0bob0, charles8]
    Searching for hash(blueberry) in users' hash list... : Matches [usr10101, timmy, john91]
    Searching for hash(letmein) in users' hash list... : Matches [wilson10, dragonslayerX, joe1984]
    Searching for hash(s3cr3t) in users' hash list... : Matches [bruce19, knuth1337, john87]
    Searching for hash(z@29hjja) in users' hash list... : No users used this password

    这种方法可以使攻击者同时对多个哈希值发起字典攻击或暴力攻击,而不需要预先计算出一个查询表。

    首先攻击者构造一个基于密码-用户名的一对多的表,当然数据需要从某个已经被入侵的数据库获得,然后猜测一系列哈希值并且从表中查找拥有此密码的用户。通常许多用户可能有着相同的密码,因此这种攻击方式也显得尤为有效。

    彩虹表

    彩虹表是一种在时间和空间的消耗上找寻平衡的破解技术。它和查表法很类似,但是为了使查询表占用的空间更小而牺牲了破解速度。因为它更小,于是我们可以在一定的空间内存储更多的哈希值,从而使攻击更加有效。能够破解任何8位及以下长度MD5值的彩虹表已经出现了。

    下面我们会讲到一种让查表法和彩虹表都失去作用的技术,叫做加盐

    加盐


    hash("hello") = 2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824
    hash("hello" + "QxLUF1bgIAdeQX") = 9e209040c863f84a31e719795b2577523954739fe5ed3b58a75cff2127075ed1
    hash("hello" + "bv5PehSMfV11Cd") = d1d3ec2e6f20fd420d50e2642992841d8338a314b8ea157c9e18477aaef226ab
    hash("hello" + "YYLmfY6IehjZMQ") = a49670c3c18b9e079b9cfaf51634f563dc8ae3070db2c4a8544305df1b60f007

    查表法和彩虹表只有在所有密码都以相同方式进行哈希加密时才有效。如果两个用户密码相同,那么他们密码的哈希值也是相同的。我们可以通过“随机化”哈希来阻止这类攻击,于是当相同的密码被哈希两次之后,得到的值就不相同了。

    比如可以在密码中混入一段“随机”的字符串再进行哈希加密,这个被字符串被称作盐值。如同上面例子所展示的,这使得同一个密码每次都被加密为完全不同的字符串。为了校验密码是否正确,我们需要储存盐值。通常和密码哈希值一起存放在账户数据库中,或者直接存为哈希字符串的一部分。

    盐值并不需要保密??,由于随机化了哈希值,查表法、反向查表法和彩虹表都不再有效。攻击者无法确知盐值,于是就不能预先计算出一个查询表或者彩虹表。这样每个用户的密码都混入不同的盐值后再进行哈希,因此反向查表法也变得难以实施。

    我理解这里不需要保密的意思是,并不是可以把 盐值 让攻击者知道,

    下面讲讲我们在实现加盐哈希的过程中通常会犯哪些错误

    错误一:短盐值和盐值重复


    最常见的错误就是在多次哈希加密中使用相同的盐值或者太短的盐值。

    盐值重复

    每次哈希加密都使用相同的盐值是很容易犯的一个错误,这个盐值要么被硬编码到程序里,要么只在第一次使用时随机获得。这样加盐的方式是做无用功,因为两个相同的密码依然会得到相同的哈希值。攻击者仍然可以使用反向查表法对每个值进行字典攻击,只需要把盐值应用到每个猜测的密码上再进行哈希即可。如果盐值被硬编码到某个流行的软件里,可以专门为这个软件制作查询表和彩虹表,那么破解它生成的哈希值就变得很简单了。

    用户创建账户或每次修改密码时,都应该重新生成新的盐值进行加密

    短盐值

    如果盐值太短,攻击者可以构造一个查询表包含所有可能的盐值。以只有3个ASCII字符的盐值为例,一共有95x95x95=857,375种可能。这看起来很多,但是如果对于每个盐值查询表只包含1MB最常见的密码,那么总共只需要837GB的储存空间。一个不到100美元的1000GB硬盘就能解决问题。
    同样地,用户名也不应该被用作盐值。尽管在一个网站中用户名是唯一的,但是它们是可预测的,并且经常重复用于其他服务中。攻击者可以针对常见用户名构建查询表,然后对用户名盐值哈希发起进攻。

    为了使攻击者无法构造包含所有可能盐值的查询表,盐值必须足够长。一个好的做法是使用和哈希函数输出的字符串等长的盐值,比如SHA256算法的输出是256bits(32 bytes),那么盐值也至少应该是32个随机字节。

    错误二:两次哈希和组合哈希函数


    (译注:此节标题原文中的Wacky Hash Functions直译是古怪的哈希函数,大概是由于作者不认可这种组合多种哈希函数的做法,为了便于理解,本文还是翻译为组合哈希函数)

    这节讲述了另一种对密码哈希的误解:使用组合哈希函数。人们经常不由自主地认为将不同的哈希函数组合起来,结果会更加安全。实际上这样做几乎没有好处,仅仅造成了函数之间互相影响的问题,甚至有时候会变得更加不安全。永远不要尝试发明自己的加密方法,只需只用已经被设计好的标准算法。有的人会说使用多种哈希函数会使计算更慢,从而破解也更慢,但是还有其他的办法能更好地减缓破解速度,后面会提到的。

    这里有些低端的组合哈希函数,我在网上某些论坛看到它们被推荐使用:

    • md5(sha1(password))
    • md5(md5(salt) + md5(password))
    • sha1(sha1(password))
    • sha1(str_rot13(password + salt))
    • md5(sha1(md5(md5(password) + sha1(password)) + md5(password)))

    不要使用其中任何一种。

    注意:这节内容是有争议的。我已经收到的大量的邮件,为组合哈希函数而辩护。他们的理由是如果攻击者不知道系统使用的哪种哈希函数,那么也就很难预先为这种组合构造出彩虹表,于是破解起来会花费更多的时间。

    诚然,攻击者在不知道加密算法的时候是无法发动攻击的,但是不要忘了Kerckhoffs’s principle,攻击者通常很容易就能拿到源码(尤其是那些免费或开源的软件)。通过系统中取出的一些密码-哈希值对应关系,很容易反向推导出加密算法。破解组合哈希函数确实需要更多时间,但也只是受了一点可以确知的因素影响。更好的办法是使用一个很难被并行计算出结果的迭代算法,然后增加适当的盐值防止彩虹表攻击。

    当然你实在想用“标准的”组合哈希函数,比如HMAC,也是可以的。但如果只是为了使破解起来更慢,那么先读读下面讲到的密钥扩展。

    创造新的哈希函数可能带来安全问题,构造哈希函数的组合又可能带来函数间互相影响的问题,它们带来的一丁点好处和这些比起来真是微不足道。显然最好的做法是使用标准的、经过完整测试的算法。

    哈希碰撞


    哈希函数将任意大小的数据转化为定长的字符串,因此其中一定有些输入经过哈希计算之后得到了相同的结果。加密哈希函数的设计就是为了使这样的碰撞尽可能难以被发现。随着时间流逝,密码学家发现攻击者越来越容易找到碰撞了,最近的例子就是MD5算法的碰撞已经确定被发现了。

    碰撞攻击的出现表明很可能有一个和用户密码不同的字符串却和它有着相同的哈希值。然而,即使在MD5这样脆弱的哈希函数中找到碰撞也需要耗费大量的计算,因此这样的碰撞“意外地”在实际中出现的可能性是很低的。于是站在实用性的角度上可以这么说,加盐MD5和加盐SHA256的安全性是一样的。不过可能的话,使用本身更安全的哈希函数总是好的,比如SHA256、SHA512、RipeMD或者WHIRLPOOL

    正确的做法:恰当使用哈希加密


    本节会准确讲述应该如何对密码进行哈希加密。其中第一部分介绍最基本的要素,也是在哈希加密中一定要做到的;后面讲解怎样在这个基础上进行扩展,使得加密更难被破解。

    基本要素:加盐哈希

    忠告:你不仅仅要用眼睛看文章,更要自己动手去实现后面讲到的“让密码更难破解:慢哈希函数”。

    在前文中我们已经看到,利用查表法和彩虹表,普通哈希加密是多么容易被恶意攻击者破解,也知道了可以通过随机加盐的办法也解决这个问题。那么到底应该使用怎样的盐值呢,又如何把它混入密码?

    盐值应该使用基于加密的伪随机数生成器(Cryptographically Secure Pseudo-Random Number Generator – CSPRNG)来生成。CSPRNG和普通的随机数生成器有很大不同,如C语言中的rand()函数。物如其名,CSPRNG专门被设计成用于加密,它能提供高度随机和无法预测的随机数。我们显然不希望自己的盐值被猜测到,所以一定要使用CSPRNG。下面的表格列出了当前主流编程语言中的CSPRNG方法:

    PlatformCSPRNG
    PHPmcrypt_create_ivopenssl_random_pseudo_bytes
    Javajava.security.SecureRandom
    Dot NET (C#, VB)System.Security.Cryptography.RNGCryptoServiceProvider
    RubySecureRandom
    Pythonos.urandom
    PerlMath::Random::Secure
    C/C++ (Windows API)CryptGenRandom
    Any language on GNU/Linux or UnixRead from /dev/random or /dev/urandom

    对于每个用户的每个密码,盐值都应该是独一无二的。每当有新用户注册或者修改密码,都应该使用新的盐值进行加密。并且这个盐值也应该足够长,使得有足够多的盐值以供加密。一个好的标准的是:盐值至少和哈希函数的输出一样长;盐值应该被储存和密码哈希一起储存在账户数据表中。

    存储密码的步骤

    1. 使用CSPRNG生成一个长度足够的盐值
    2. 将盐值混入密码,并使用标准的加密哈希函数进行加密,如SHA256
    3. 把哈希值和盐值一起存入数据库中对应此用户的那条记录

    校验密码的步骤

    1. 从数据库取出用户的密码哈希值和对应盐值
    2. 将盐值混入用户输入的密码,并且使用同样的哈希函数进行加密
    3. 比较上一步的结果和数据库储存的哈希值是否相同,如果相同那么密码正确,反之密码错误

    文章最后有几个加盐密码哈希的代码实现,分别使用了PHP、C#、Java和Ruby。

    在Web程序中,永远在服务器端进行哈希加密

    如果你正在开发一个Web程序,你可能会疑惑到底在哪进行加密。是使用JavaScript在用户的浏览器上操作呢,还是将密码“裸体”传送到服务器再进行加密?

    即使浏览器端用JavaScript加密了,你仍然需要在服务端再次进行加密。试想有个网站在浏览器将密码经过哈希后传送到服务器,那么在认证用户的时候,网站收到哈希值和数据库中的值进行比对就可以了。这看起来比只在服务器端加密安全得多,因为至始至终没有将用户的密码明文传输,但实际上不是这样。

    问题在于,从客户端来看,经过哈希的密码逻辑上成为用户真正的密码。为了通过服务器认证,用户只需要发送密码的哈希值即可。如果有坏小子获取了这个哈希值,他甚至可以在不知道用户密码的情况通过认证。更进一步,如果他用某种手段入侵了网站的数据库,那么不需要去猜解任何人的密码,就可以随意使用每个人的帐号登录。

    这并不是说你不应该在浏览器端进行加密,但是如果你这么做了,一定要在服务端再次加密。在浏览器中进行哈希加密是个好想法,不过实现的时候注意下面几点:

    • 客户端密码哈希并不能代替HTTPS(SSL/TLS)。如果浏览器和服务器之间的连接是不安全的,那么中间人攻击可以修改JavaScript代码,删除加密函数,从而获取用户密码。

    • 有些浏览器不支持JavaScript,也有的用户禁用了浏览器的JavaScript功能。为了最好的兼容性,你的程序应该检测JavaScript是否可用,如果答案为否,需要在服务端模拟客户端的加密。

    • 客户端哈希同样需要加盐,很显然的办法就是向服务器请求用户的盐值,但是不要这么做。因为这给了坏蛋一个机会,能够在不知道密码的情况下检测用户名是否有效。既然你已经在服务端对密码进行了加盐哈希,那么在客户端把用户名(或邮箱)加上网站特有的字符串(如域名)作为盐值是可行的。

    让密码更难破解:慢哈希函数

    加盐使攻击者无法采用特定的查询表和彩虹表快速破解大量哈希值,但是却不能阻止他们使用字典攻击或暴力攻击。高端的显卡(GPU)和定制的硬件可以每秒进行数十亿次哈希计算,因此这类攻击依然可以很高效。为了降低攻击者的效率,我们可以使用一种叫做密钥扩展的技术。

    这种技术的思想就是把哈希函数变得很慢,于是即使有着超高性能的GPU或定制硬件,字典攻击和暴力攻击也会慢得让攻击者无法接受。最终的目标是把哈希函数的速度降到足以让攻击者望而却步,但造成的延迟又不至于引起用户的注意。

    密钥扩展的实现是依靠一种CPU密集型哈希函数。不要尝试自己发明简单的迭代哈希加密,如果迭代不够多,是可以被高效的硬件快速并行计算出来的,就和普通哈希一样。应该使用标准的算法,比如PBKDF2或者bcrypt这里可以找到PBKDF2在PHP上的一种实现。

    这类算法使用一个安全因子或迭代次数作为参数,这个值决定了哈希函数会有多慢。对于桌面软件或者手机软件,获取参数最好的办法就是执行一个简短的性能基准测试,找到使哈希函数大约耗费0.5秒的值。这样,你的程序就可以尽可能保证安全,而又不影响到用户体验。

    如果你在一个Web程序中使用密钥扩展,记得你需要额外的资源处理大量认证请求,并且密钥扩展也使得网站更容易遭受拒绝服务攻击(DoS)。但我依然推荐使用密钥扩展,不过把迭代次数设定得低一点,你应该基于认证请求最高峰时的剩余硬件资源来计算迭代次数。要求用户每次登录时输入验证码可以消除拒绝服务的威胁。另外,一定要把你的系统设计为迭代次数可随时调整的。

    如果你担心计算量带来的负载,但又想在Web程序中使用密钥扩展,可以考虑在浏览器中用JavaScript完成。Stanford JavaScript Crypto Library里包含了PBKDF2的实现。迭代次数应该被设置到足够低,以适应速度较慢的客户端,比如移动设备。同时当客户端不支持JavaScript的时候,服务端应该接手计算。客户端的密钥扩展并不能免除服务端进行哈希加密的职责,你必须对客户端传来的哈希值再次进行哈希加密,就像对付一个普通密码一样。

    无法破解的哈希加密:密钥哈希和密码哈希设备

    只要攻击者可以检测对一个密码的猜测是否正确,那么他们就可以进行字典攻击或暴力攻击。因此下一步就是向哈希计算中增加一个密钥,只有知道这个密钥的人才能校验密码。有两种办法可以实现:将哈希值加密,比如使用AES算法;将密钥包含到哈希字符串中,比如使用密钥哈希算法HMAC

    听起来很简单,做起来就不一样了。这个密钥需要在任何情况下都不被攻击者获取,即使系统因为漏洞被攻破了。如果攻击者获取了进入系统的最高权限,那么不论密钥被储存在哪,他们都可以窃取到。因此密钥需要储存在外部系统中,比如另一个用于密码校验的物理服务器,或者一个关联到服务器的特制硬件,如YubiHSM

    我强烈推荐大型服务(10万用户以上)使用这类办法,因为我认为面对如此多的用户是有必要的。

    如果你难以负担多个服务器或专用的硬件,仍然有办法在一个普通Web服务器上利用密钥哈希技术。大部分针对数据库的入侵都是由于SQL注入攻击,因此不要给攻击者进入本地文件系统的权限(禁止数据库服务访问本地文件系统,如果它有这个功能的话)。这样一来,当你随机生成一个密钥存到通过Web程序无法访问的文件中,然后混入加盐哈希,得到的哈希值就不再那么脆弱了,即便这时数据库遭受了注入攻击。不要把将密钥硬编码到代码里,应该在安装时随机生成。这当然不如独立的硬件系统安全,因为如果Web程序存在SQL注入点,那么可能还存在其他一些问题,比如本地文件包含漏洞(Local File Inclusion),攻击者可以利用它读取本地密钥文件。无论如何,这个措施比没有好。

    请注意密钥哈希不代表无需进行加盐。高明的攻击者迟早会找到办法窃取密钥,因此依然对密码哈希进行加盐和密钥扩展很重要。

    其他安全措施


    哈希加密可以在系统发生入侵时保护密码,但这并不能使整个程序更加安全。首先还有很多事情需要做,来保证密码哈希(和其他用户数据)不被窃取。

    即使经验丰富的开发者也需要额外学习安全知识,才能写出安全的程序。这里有个关于Web程序漏洞的资源:The Open Web Application Security Project (OWASP),还有一个很好的介绍:OWASP Top Ten Vulnerability List。除非你了解列表中所有的漏洞,才能尝试编写一个处理敏感数据的Web程序。雇主也有责任保证他所有的开发人员都有资质编写安全的程序。

    对你的程序进行第三方“渗透测试”是一个不错的选择。最好的程序员也可能犯错,因此有一个安全专家审查你的代码寻找潜在的漏洞是有意义的。找寻值得信赖的机构(或招聘人员)来对你的代码进行审查。安全审查应该从编码的初期就着手进行,一直贯穿整个开发过程。

    监控你的网站来发现入侵行为也是很重要的,我推荐至少雇佣一个人全职负责监测和处理安全隐患。如果有个漏洞没被发现,攻击者可能通过网站利用恶意软件感染访问者,因此检测漏洞并且及时应对是十分重要的

    常见问题


    我应该使用什么哈希算法?

    应该使用:

    • 本文末尾的PHP source code, Java source code, C# source code or the Ruby source code
    • OpenWall的Portable PHP password hashing framework
    • 任何先进的、被良好测试过的哈希加密算法,比如SHA256,SHA512,RipeMD,WHIRLPOOL,SHA3等等
    • 设计良好的密钥扩展算法,如PBKDF2bcryptscrypt
    • 安全的crypt()版本($2y$,$5$,$6$)

    不要使用:

    • 过时的函数,比如MD5或SHA1
    • 不安全的crypt()版本($1$,$2$,$2x$,$3$)
    • 任何你自己设计的加密算法。只应该使用那些在公开领域中的,并且被密码学家完整测试过的技术

    尽管还没有一种针对MD5或SHA1非常效率的攻击手段,但是它们太古老也被广泛地认为不足以胜任存储密码的工作(某种程度上甚至是错误的),因此我也不推荐使用它们。但是有个例外,PBKDF2中频繁地使用了SHA1作为它底层的哈希函数。

    当用户忘记密码的时候,怎样进行重置?

    我个人的观点是,当前所有广泛使用的密码重置机制都是不安全的。如果你对安全性有极高的要求,比如一个加密服务,那么不要允许用户重置密码。
    大多数网站向那些忘记密码的用户发送电子邮件来进行身份认证。首先,需要随机生成一个一次性的令牌,它直接关联到用户的账户。然后将这个令牌混入一个重置密码的链接中,发送到用户的电子邮箱。最后当用户点击这个包含有效令牌的链接时,提示他们可以设置新的密码。要确保这个令牌只对一个账户有效,以防攻击者从邮箱获取到令牌后,用来重置其他用户的密码。

    令牌必须在15分钟内使用,并且一旦被使用就立即失效。当用户重新请求令牌时,或用户登录成功时(说明他还记得密码),使原令牌失效也是一个好做法。如果一个令牌始终不过期,那么它一直可以用于入侵用户的帐号。电子邮件(SMTP)是一个纯文本协议,并且网络上有很多恶意路由在截取邮件信息。在用户修改密码后,那些包含重置密码链接的邮件在很长一段时间内依然缺乏保护。因此应该尽早使令牌过期,降低把用户信息暴露给攻击者的可能。

    攻击者是可以篡改令牌的,所以不要把账户信息和失效时间存储在里面。这些信息应该以不可猜解的二进制形式存在,并且只用来识别数据库中某条用户的记录。

    永远不要通过电子邮件向用户发送新密码,同时也记得在用户重置密码的时候随机生成一个新的盐值用于加密,不要重复使用之前密码的那个盐值。

    当账户数据库被泄漏或入侵时,应该怎么做?

    你首先需要做的,是查看系统被暴露到什么程度了,然后修复这个攻击者利用的漏洞。如果你没有应对入侵的经验,我强烈推荐雇一个第三方安全机构来做这件事。

    将一个漏洞精心掩盖期待没有人能注意到,是否听起来很省事而又诱人呢?但是这样只会让你显得更糟糕,因为你在用户不知情的情况下,将他们的密码和个人信息暴露在危险之中。即使用户还无法理解到底发生了什么,你也应该尽快履行告知的义务。比如在首页放置一个链接,指向对此问题更详细的说明,可能的话还可以通过电子邮件告知用户目前的情况。

    向你的用户说明你是如何保护他们的密码的——最好是使用了加盐哈希——即便如此恶意黑客也能使用字典攻击和暴力攻击。设想用户可能在很多服务中使用相同的密码,攻击者会用找到的密码去尝试登录其他网站。提示你的用户应该修改所有相似的密码,不论它们被使用在哪个服务上,并且强制用户下次登录你的网站时修改密码。大部分用户会尝试将密码“修改”为和之前相同的以便记忆,你应该使用老密码的哈希值来确保用户无法这么做。

    即使有加盐哈希的保护,攻击者也很可能快速破解其中一些脆弱的密码。为了减少攻击者使用的它们机会,你应该对这些密码的帐号发送认证电子邮件,直到用户修改了密码。可以参考上一个问题,其中有一些实现电子邮件认证的要点。

    另外也要告诉你的用户,网站到底储存了哪些个人信息。如果你的数据库中有用户的信用卡号,你应该指导用户检查自己近期的账单,并且注销掉这张信用卡。

    我应该使用什么样的密码规则?是否应该强制用户使用复杂的密码?

    如果你的服务对安全性没有严格的要求,那么不要对用户进行限制。我推荐在用户输入密码的时候,页面上显示出密码强度,由用户自己决定需要多安全的密码。如果你的服务对安全有特殊的需求,那就应该强制用户输入长度至少为12个字符的密码,并且其中至少包括两个字母、两个数字和两个符号。

    不要过于频繁地强制你的用户修改密码,最多6个月1次,因为那样做会使用户疲于选择一个强度足够好的密码。更好的做法是指导用户在他们感觉密码可能泄漏的时候去主动修改,并且提示用户不要把密码告诉任何人。如果这是在商业环境中,鼓励你的员工利用工作时间熟记并使用他们的密码。

    如果攻击者入侵了我的数据库,他们难道不能把其中的密码哈希替换为自己的值,然后登录系统么?

    当然可以,但是如果他已经入侵了你的数据库,那么很可能已经有权限访问你服务器上任何东西了,因此完全没必要登录账户去获取他想要的。对密码进行哈希加密的手段,(对网站而言)不是保护网站免受入侵,而是在入侵已经发生时保护数据库中的密码。

    通过为数据库连接设置两种权限,可以防止密码哈希在遭遇注入攻击时被篡改。一种权限用于创建用户:它对用户表可读可写;另一种用于用户登录,它只能读用户表而不能写。

    为什么我非得用像HMAC那种特殊的算法?为什么不能简单地把密钥混入密码?

    像MD5、SHA1和SHA2这类哈希函数是基于Merkle–Damgård构造的,因此在长度扩展攻击面前非常脆弱。就是说如果已经知道一个哈希值H(X),对于任意的字符串Y,攻击者可以计算出H(pad(X) + Y)的值,而不需要知道X是多少,其中pad(X)是哈希函数的填充函数(padding function,比如MD5将数据每512bit分为一组,最后不足的将填充字节)。

    在攻击者不知道密钥(key)的情况下,他仍然可以根据哈希值H(key + message)计算出H(pad(key + message) + extension)。如果这个哈希值用于身份认证,并且依靠其中的密钥来防止攻击者篡改消息,这个办法已经行不通了。因为攻击者无需知道密钥,也能构造出包含message + extension的一个有效的哈希值。

    目前还不清楚攻击者能否用这个办法更快破解密码,但是由于这种攻击的出现,在密钥哈希中使用上述哈希函数已经被认为是差劲的实践了。也许某天高明的密码学家会发现一个利用长度扩展攻击的新思路,从而更快地破解密码,所以还是使用HMAC吧。

    盐值应该加到密码前面还是后面?

    都行,但是在一个程序中应该保持一致,以免出现互操作方面的问题。目前看来加到密码之前是比较常用的做法。

    为什么本文中的代码在比较哈希值的时候,都是经过固定的时间才返回结果?

    让比较过程耗费固定的时间可以保证攻击者无法对一个在线系统使用计时攻击,以此获取密码的哈希值,然后进行本地破解工作。

    比较两个字节序列(字符串)的标准做法是,从第一字节开始,每个字节逐一顺序比较。只要发现某字节不相同了,就可以立即返回“假”的结果。如果遍历整个字符串也没有找到不同的字节,那么两个字符串就是相同的,并且返回“真”。这意味着比较字符串的耗时决定于两个字符串到底有多大的不同。

    举个例子,使用标准的方法比较“xyzabc”和“abcxyz”,由于第一个字符就不同,不需要检查后面的内容就可以马上返回结果。相反,如果比较“aaaaaaaaaaB”和“aaaaaaaaaaZ”,比较算法就需要遍历最后一位前所有的“a”,然后才能知道它们是不相同的。

    假设攻击者妄图入侵一个在线系统,并且此系统限制了每秒只能尝试一次用户认证。还假设他已经知道了密码哈希所有的参数(盐值、哈希函数的类型等等),除了密码的哈希值和密码本身(显然啊,否则还破解个什么)。如果攻击者能精确测量在线系统耗时多久去比较他猜测的密码和真实密码,那么他就能使用计时攻击获取密码的哈希值,然后进行离线破解,从而绕过系统对认证频率的限制。

    首先攻击者准备256个字符串,它们的哈希值的第一字节包含了所有可能的情况。然后用它们去系统中尝试登录,并记录系统返回结果所消耗的时间,耗时最长的那个就是第一字节猜对的那个。接下来用同样的方式猜测第二字节、第三字节等等。直到攻击者获取了最够长的哈希值片段,最后只需在自己的机器上破解即可,完全不受在线系统的限制。

    乍看之下在网络上进行计时攻击是不可能做到的,然而有人已经实现了,并运用到实际中了。因此本文提供的代码才使用固定的时间去比较字符串,不论它们有多相似。

    “慢比较”的代码是如何工作的?

    上一个问题解释了为什么“慢比较”是有必要的,现在来讲解一下代码具体是怎么实现的。

    代码中使用了异或运算符“^”(XOR)来比较两个整数是否相等,而不是“==”。当且仅当两位相等时,异或的结果才是0。因为0 XOR 0 = 0, 1 XOR 1 = 0, 0 XOR 1 = 1, 1 XOR 0 = 1。应用到整数中每一位就是说,当且仅当字节两个整数各位都相等,结果才是0。

    代码中的第一行,比较a.length和b.length,相同的话diff是0,否则diff非0。然后使用异或比较数组中各字节,并且将结果和diff求或。如果有任何一个字节不相同,diff就会变成非0的值。因为或运算没有“置0”的功能,所以循环结束后diff是0的话只有一种可能,那就是循环前两个数组长度相等(a.length == b.length),并且数组中每一个字节都相同(每次异或的结果都非0)。
    我们使用XOR而不是“==”来比较整数的原因是:“==”通常被翻译/编译/解释为带有分支的语句。例如C语言中的“diff &= a == b”可能在x86机器成被编译为如下汇编语言:

    MOV EAX, [A]
    CMP [B], EAX
    JZ equal
    JMP done
    equal:
    AND [VALID], 1
    done:
    AND [VALID], 0

    其中的分支导致代码运行的时间不固定,决定于两个整数相等的程度和CPU内部的跳转预测机制(branch prediction)。

    而C语言代码“diff |=a ^ b”会被编译为下面的样子,它执行的时间和两个整数是什么样的情况无关。

    MOV EAX, [A]
    XOR EAX, [B]
    OR [DIFF], EAX

    弄这么麻烦干嘛?

    用户在你的网站上输入密码,说明他们相信你会保障密码的安全。如果你的数据库被黑了,又没有对用户密码加以保护,恶意黑客就可以使用这些密码去入侵用户在其他网站或服务的账户(大部分人会在各处使用相同的密码)。这不仅仅关乎你网站的安全,更关系到用户的。你需要对用户的安全负责。

    PHP PBKDF2 密码哈希代码


    下面是PBKDF2在PHP中一种安全的实现,你也可以在这个页面找到测试用例和基准测试的代码。

    下载PasswordHash.php

    如果你需要兼容的PHP和C#代码,点击这里

    Java PBKDF2 密码哈希代码


    下面是PBKDF2在Java中一种安全的实现。

    下载PasswordHash.java

    ASP.NET(C#) PBKDF2 密码哈希代码


    下面是PBKDF2在ASP.NET(C#)中一种安全的实现。

    下载PasswordHash.cs

    如果你需要兼容的PHP和C#代码,点击这里