精华内容
下载资源
问答
  • 哈希函数命令:Get-FileHash -Algorithm [算法] 文件路径 支持的哈希算法:SHA1,SHA256,SHA384,SHA512,MACTripleDES,MD5,RIPEMD160 以Win10为例,右击“开始”菜单,选择“Windows PowerShell(管理员)”; 例如: ...

    哈希函数命令:Get-FileHash -Algorithm [算法] 文件路径
    支持的哈希算法:SHA1,SHA256,SHA384,SHA512,MACTripleDES,MD5,RIPEMD160
    以Win10为例,右击“开始”菜单,选择“Windows PowerShell(管理员)”;
    在这里插入图片描述

    例如:

    Get-FileHash -Algorithm SHA256 D:\新建文件夹\test\readme.txt

    在这里插入图片描述

    在这里插入图片描述

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

    千次阅读 2020-01-09 18:11:06
    转换的方法称为哈希函数,原值经过哈希函数计算后得到的值称为哈希值。 1.哈希特点 (1)一致性:同一个值每次经过同一个哈希函数计算后得到的哈希值是一致的。 F(x)=rand() :每次返回一个随机值,是不好的哈希 (2)...

    一,什么是哈希

    哈希是将任意长度的数据转换为一个数字的过程。这个数字是在一个固定的范围之内的。
    转换的方法称为哈希函数,原值经过哈希函数计算后得到的值称为哈希值。

    哈希函数

    1.哈希特点

    (1)一致性:同一个值每次经过同一个哈希函数计算后得到的哈希值是一致的。

    F(x)=rand() :每次返回一个随机值,是不好的哈希
    

    (2)散列性:不同的值的哈希值尽量不同,理想情况下每个值对应于不同的数字。

    F(x)=1 : 不管输入什么都返回1,是不好的哈希
    
    2.冲突怎么解决

    把一个大的集合映射到一个固定大小的集合中,肯定是存在冲突的。这个是抽屉原理或者叫鸽巢理论。

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

    (1)拉链法:

    链表地址法是使用一个链表数组来存储相应数据,当hash遇到冲突的时候依次添加到链表的后面进行处理。Java里的HashMap是拉链法解决冲突的典型应用场景。

    Java8 HashMap

    Java8的HashMap中,使用一个链表数组来存储数据,根据元素的哈希值确定存储的数组索引位置,当冲突时,就链接到元素后面形成一个链表,Java8中当链表长度超过8的时候就变成红黑树以优化性能,红黑树也可以视为拉链法的一种变形。

    (2)开放地址法

    开放地址法是指大小为 M 的数组保存 N 个键值对,其中 M >N。我们需要依靠数组中的空位解决碰撞冲突。基于这种策略的所有方法被统称为“开放地址”哈希表。

    线性探测法,就是比较常用的一种“开放地址”哈希表的一种实现方式。线性探测法的核心思想是当冲突发生时,顺序查看表中下一单元,直到找出一个空单元或查遍全表。简单来说就是:一旦发生冲突,就去寻找下 一个空的散列表地址,只要散列表足够大,空的散列地址总能找到。

    Java8中的HashTable就是用线性探测法来解决冲突的。

        public synchronized V put(K key, V value) {
            // Make sure the value is not null
            if (value == null) {
                throw new NullPointerException();
            }
    
            // Makes sure the key is not already in the hashtable.
            Entry<?,?> tab[] = table;
            int hash = key.hashCode();
            int index = (hash & 0x7FFFFFFF) % tab.length;
            @SuppressWarnings("unchecked")
            Entry<K,V> entry = (Entry<K,V>)tab[index];
            for(; entry != null ; entry = entry.next) {
                if ((entry.hash == hash) && entry.key.equals(key)) {
                    V old = entry.value;
                    entry.value = value;
                    return old;
                }
            }
    
            addEntry(hash, key, value, index);
            return null;
        }
    
        private void addEntry(int hash, K key, V value, int index) {
            modCount++;
    
            Entry<?,?> tab[] = table;
            if (count >= threshold) {
                // Rehash the table if the threshold is exceeded
                rehash();
    
                tab = table;
                hash = key.hashCode();
                index = (hash & 0x7FFFFFFF) % tab.length;
            }
    
            // Creates the new entry.
            @SuppressWarnings("unchecked")
            Entry<K,V> e = (Entry<K,V>) tab[index];
            tab[index] = new Entry<>(hash, key, value, e);
            count++;
        }
    
    

    (2)冲突解决示例

    举个例子,假如散列长度为8,哈希函数是:y=x%7。两种解决冲突的方式如下:

    拉链法解决冲突
    拉链法

    线性探测法解决冲突
    线性探测法

    二,几个常见哈希算法

    1.MD5

    MD5哈希算法是将任意字符散列到一个长度为128位的Bit数组中,得出的结果表示为一个32位的十六进制数字。

    MD5哈希算法有以下几个特点:

    1. 正像快速:原始数据可以快速计算出哈希值
    2. 逆向困难:通过哈希值基本不可能推导出原始数据
    3. 输入敏感:原始数据只要有一点变动,得到的哈希值差别很大
    4. 冲突避免:很难找到不同的原始数据得到相同的哈希值

    算法过程:

    1. 数据填充:

    将原数据的二进制值进行补齐。

    (1)填充数据:使得长度模除512后得到448,留出64个bit来存储原信息的长度。填充规则是填充一个1,后面全部是0。

    (2)填充长度数据:计算原数据的长度数据,填充到最后的64个bit上,如果消息长度数据大于64bit就使用低64位的数据。

    第一步:填充数据

    1. 迭代计算:

    将填充好的数据按照每份512的长度进行切分,对每一份依次进行处理,每份的处理方式是使用四个函数进行依次进行计算,每个函数都有四个输入参数,输出也是四个数字,输出的数字作为下一份数据的输入,所有份数的数据处理完毕,得到的四个数字连接起来就是最终的MD5值。

    以下图片是整个迭代计算的过程示意图,其中四个初始参数和四个函数定义如下:

    //四个初始参数值
    A=0x67452301;
    B=0xefcdab89;
    C=0x98badcfe;
    D=0x10325476;
    
    //四个函数的定义
    // a、b、c、d是每次计算时候的四个参数
    F=(b&c)|((~b)&d);
    F=(d&b)|((~d)&c);
    F=b^c^d;
    F=c^(b|(~d));
    

    第二步:数据计算

    1. md5的java实现
    package com.chybin.algorithm.chapter2;
    
    /**
     * Create By 鸣宇淳 on 2019/12/26
     **/
    public class MD5{
        /*
         *四个链接变量
         */
        private final int A=0x67452301;
        private final int B=0xefcdab89;
        private final int C=0x98badcfe;
        private final int D=0x10325476;
        /*
         *ABCD的临时变量
         */
        private int Atemp,Btemp,Ctemp,Dtemp;
    
        /*
         *常量ti
         *公式:floor(abs(sin(i+1))×(2pow32)
         */
        private final int K[]={
                0xd76aa478,0xe8c7b756,0x242070db,0xc1bdceee,
                0xf57c0faf,0x4787c62a,0xa8304613,0xfd469501,0x698098d8,
                0x8b44f7af,0xffff5bb1,0x895cd7be,0x6b901122,0xfd987193,
                0xa679438e,0x49b40821,0xf61e2562,0xc040b340,0x265e5a51,
                0xe9b6c7aa,0xd62f105d,0x02441453,0xd8a1e681,0xe7d3fbc8,
                0x21e1cde6,0xc33707d6,0xf4d50d87,0x455a14ed,0xa9e3e905,
                0xfcefa3f8,0x676f02d9,0x8d2a4c8a,0xfffa3942,0x8771f681,
                0x6d9d6122,0xfde5380c,0xa4beea44,0x4bdecfa9,0xf6bb4b60,
                0xbebfbc70,0x289b7ec6,0xeaa127fa,0xd4ef3085,0x04881d05,
                0xd9d4d039,0xe6db99e5,0x1fa27cf8,0xc4ac5665,0xf4292244,
                0x432aff97,0xab9423a7,0xfc93a039,0x655b59c3,0x8f0ccc92,
                0xffeff47d,0x85845dd1,0x6fa87e4f,0xfe2ce6e0,0xa3014314,
                0x4e0811a1,0xf7537e82,0xbd3af235,0x2ad7d2bb,0xeb86d391};
        /*
         *向左位移数,计算方法未知
         */
        private final int s[]={7,12,17,22,7,12,17,22,7,12,17,22,7,
                12,17,22,5,9,14,20,5,9,14,20,5,9,14,20,5,9,14,20,
                4,11,16,23,4,11,16,23,4,11,16,23,4,11,16,23,6,10,
                15,21,6,10,15,21,6,10,15,21,6,10,15,21};
    
    
        /*
         *初始化函数
         */
        private void init(){
            Atemp=A;
            Btemp=B;
            Ctemp=C;
            Dtemp=D;
        }
        /*
         *移动一定位数
         */
        private    int    shift(int a,int s){
            return(a<<s)|(a>>>(32-s));//右移的时候,高位一定要补零,而不是补充符号位
        }
        /*
         *主循环
         */
        private void MainLoop(int M[]){
            int F,g;
            int a=Atemp;
            int b=Btemp;
            int c=Ctemp;
            int d=Dtemp;
            for(int i = 0; i < 64; i ++){
                if(i<16){
                    F=(b&c)|((~b)&d);
                    g=i;
                }else if(i<32){
                    F=(d&b)|((~d)&c);
                    g=(5*i+1)%16;
                }else if(i<48){
                    F=b^c^d;
                    g=(3*i+5)%16;
                }else{
                    F=c^(b|(~d));
                    g=(7*i)%16;
                }
                int tmp=d;
                d=c;
                c=b;
                b=b+shift(a+F+K[i]+M[g],s[i]);
                a=tmp;
            }
            Atemp=a+Atemp;
            Btemp=b+Btemp;
            Ctemp=c+Ctemp;
            Dtemp=d+Dtemp;
    
        }
        /*
         *填充函数
         *处理后应满足bits≡448(mod512),字节就是bytes≡56(mode64)
         *填充方式为先加一个0,其它位补零
         *最后加上64位的原来长度
         */
        private int[] add(String str){
            int num=((str.length()+8)/64)+1;//以512位,64个字节为一组
            int strByte[]=new int[num*16];//64/4=16,所以有16个整数
            for(int i=0;i<num*16;i++){//全部初始化0
                strByte[i]=0;
            }
            int    i;
            for(i=0;i<str.length();i++){
                strByte[i>>2]|=str.charAt(i)<<((i%4)*8);//一个整数存储四个字节,小端序
            }
            strByte[i>>2]|=0x80<<((i%4)*8);//尾部添加1
            /*
             *添加原长度,长度指位的长度,所以要乘8,然后是小端序,所以放在倒数第二个,这里长度只用了32位
             */
            strByte[num*16-2]=str.length()*8;
            return strByte;
        }
        /*
         *调用函数
         */
        public String getMD5(String source){
            init();
            int strByte[]=add(source);
            for(int i=0;i<strByte.length/16;i++){
                int num[]=new int[16];
                for(int j=0;j<16;j++){
                    num[j]=strByte[i*16+j];
                }
                MainLoop(num);
            }
            return changeHex(Atemp)+changeHex(Btemp)+changeHex(Ctemp)+changeHex(Dtemp);
    
        }
        /*
         *整数变成16进制字符串
         */
        private String changeHex(int a){
            String str="";
            for(int i=0;i<4;i++){
                str+=String.format("%2s", Integer.toHexString(((a>>i*8)%(1<<8))&0xff)).replace(' ', '0');
    
            }
            return str;
        }
        /*
         *单例
         */
        private static MD5 instance;
        public static MD5 getInstance(){
            if(instance==null){
                instance=new MD5();
            }
            return instance;
        }
    
        private MD5(){};
    
        public static void main(String[] args){
            String str=MD5.getInstance().getMD5("123");
            System.out.println(str);
        }
    }
    
    2.SHA

    SHA类似MD5,也是一种信息摘要算法,也是将任意长度的字符串转换为固定长度的数字的算法。SHA算法是一个家族,有五个算法:SHA-1、SHA-224、SHA-256、SHA-384,和SHA-512。这些变体除了生成摘要的长度、循环运行的次数等一些微小差异外,算法的基本结构是一致的。

    SHA-1算法的结果是一个160个bit的数字,比MD5的128个bit要长32位,碰撞几率要低了2^32倍。可是SHA-1和MD5一样已经被人破解,已经不安全了。

    SHA-256从名字上看就表明了它的值存储在长度为256的bit数组中的,SHA-512信息摘要长度是512个bit。

    SHA-224是SHA256的精简版本,SHA-384是SHA-512的精简版本,精简版本主要用在安全等级要求不太高的场景,比如只是验证下文件的完整性。使用什么版本的SHA取决于安全要求和算法速度,毕竟长度越长算法计算时间约长,但是安全等级高。

    在这里插入图片描述

    SHA算法过程:

    SHA算法的底层原理和MD5很相似,只是在摘要分段和处理细节上有少许差别,他们都是第一步将原数据进行填充,填充到512的整数倍,填充的信息包括10数据填充和长度填充,第二步切分为相同大小的块,第三步进行对每一块迭代,每块进行N轮运算,最终得到的值拼接起来就是最终的哈希值。

    以下是MD5、SHA-1、SHA-2系列的算法过程比较:

    MD5算法过程示意图:

    MD5是对每一块数据分为四个部分,用四个函数进行运算。最终生成128位的哈希值。

    MD5算法过程

    SHA-1算法过程示意图:

    SHA-1是将每一块数据分为五个部分。

    SHA-1算法过程

    SHA-2算法过程示意图:

    SHA-2是分为八个部分,算法也更加复杂。

    SHA-2算法过程

    3.SimHash

    SimHash是Google提出的一种判断文档是否重复的哈希算法,他是将文本转换为一个64位的哈希值,然后计算两个哈希值的距离,如果小于n(n一般是3)就认为这两个文本是相似的。

    之所以能够这样判断是否相似是因为SimHash算法不同于MD5之类的算法,SimHash算法是局部敏感的哈希算法,MD5算法是全局敏感的哈希算法。在MD5中原数据只要有一个字符的变化,哈希值就会变化很大,而在SimHash算法中,原数据变化一小部分,哈希值也只有很小一部分的变化,所以只要哈希值很类似,就意味着原数据就很类似。

    算法实现:

    参考这个博客【[Algorithm] 使用SimHash进行海量文本去重】

    (1)第一步:哈希

    1. 分词: 将文本进行分词,并给单词分配权重。
    2. hash: 对每个次进行hash计算,得到哈希值。
    3. 加权: 对每个单词的has进行加权。
    4. 合并: 把上一步加权hash值合并累计起来。
    5. 降维: 把上一步累加起来的值变为01。如果每一位大于0 记为 1,小于0 记为 0。

    (2)第二步:计算海明距离

    两个simhash对应二进制(01串)取值不同的数量称为这两个simhash的海明距离。

    举例如下: 10101 和 00110 从第一位开始依次有第一位、第四、第五位不同,则海明距离为3。

    异或就是如果a、b两个值不相同,则异或结果为1。如果a、b两个值相同,异或结果为0。两个simhash值进行异或,得出的结果中1的个数就是海明距离。

    simhash计算过程

    判断两个文本是否相似,就计算两个simhash哈希值的海明距离,根据经验,如果海明距离小于3就可以判定两个文本是相似的。

    4.GeoHash

    GeoHash 算法将经纬度哈希为一个数字,然后将数字base32编码为一个字符串。

    比如:北海公园的经纬度是:(39.928167,116.389550),对应的GeoHash值可以为wx4g、wx4g0、wx4g0s、wx4g0s8、wx4g0s8q。GeoHash值代表的是这个经纬度点所在的一个矩形区域,长度越长矩形面积约小,表示的越精确。

    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    两个位置的GeoHash值前部分一样的位数越多,说明两个位置离得越近,百度地图的查找附近、滴滴打车查找附近的车辆功能就可以使用这个算法。

    GeoHash算法过程

    下面对于北海公园的经纬度(39.928167,116.389550)进行编码,了解下算法过程。

    (1)第一步:纬度编码

    将整个地球从水平方向上进行逐步切分,确定纬度39.928167在哪个区域中。

    纬度范围是-90到90,每次平均分为两份,进行逐步细化地迭代。

    1. 第一次迭代:处于-90到0的标记为0,0到90的标记为1,39.928167处于1的区间,所以最终结果的第一位是1。
    2. 第二次迭代:对上一步标记为1的部分平分,0到45标记为0,45到90标记为1,39.928167标记为1处于0的区间,所以最终结果的第二位是0。
    3. 第三次迭代:对上一步标记为0的部分平分,0到22.5标记为0,22.5到45标记为1,39.928167标记为1处于0的区间,所以最终结果的第三位是0
    4. 第四次迭代:对上一步标记为0的部分平分,22.5到33.75标记为0,33.75到45标记为1,39.928167标记为1处于1的区间,所以最终结果的第三位是1。

    经过N次迭代后,得到一个长度为N的二进制值,比如得到的值为1011100011,这个就是对纬度进行的编码最终值。

    纬度编码示意图

    (2)第二步:经度编码

    对经度的编码过程跟对纬度编码过程十分类似,不同点是经度范围是-180到180,对经度116.389550经过N次迭代后得到编码值。比如得到1101001011。这个就是对经度编码的最终值。

    (3)第三步:合并经纬度

    对纬度编码值、经度编码值进行合并,合并规则是奇数位放纬度、偶数位放经度,合并为一个新的二进制串。

    (4)第四步:转换为字符串

    将上一步合并的二进制11100 11101 00100 01111每5位一段转换为十进制,结果是28、29、4、15,Base32编码后为wx4g。这个就是北海公园的经纬度(39.928167,116.389550)最终的GeoHash编码值。

    以下图表是二进制数字、base32字符对应表:

    Decimal 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
    Base 32 0 1 2 3 4 5 6 7 8 9 b c d e f
    Decimal 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
    Base 32 h j k m n p q r s t u v w x y
    展开全文
  • 数据结构之哈希函数

    千次阅读 2016-12-07 10:43:43
    概念:哈希(hash),也叫做散列、数据摘要等,是一种常见的数据结构。哈希的表的核心概念分为哈希表和哈希函数。哈希表(hashTable)哈希表之前讲过,...如果两个不同的对象经过哈希函数计算后得到相同的哈希值,则这

    概念:

    哈希(hash),也叫做散列、数据摘要等,是一种常见的数据结构。哈希的表的核心概念分为哈希表和哈希函数。

    哈希表(hashTable)

    哈希表之前讲过,有需要的可以参考:点击打开哈希表

    哈希函数

    哈希函数就是将某一不定长的对象映射为另一个定长的对象。能够做到这一点的函数有很多,那什么可以作为哈希函数?这里我们首先要明确下什么可以作为哈希函数。
    如果两个不同的对象经过哈希函数计算后得到相同的哈希值,则这就是所谓的冲突。冲突会导致很多的异常,说一种极端的情况:如果一个哈希函数的计算记过经常为0,那么它根本无法帮助我们来区分对象,也就不能帮助我们快速查找对象了,也就违反了哈希的作用。
    在设计哈希函数的时候我们主要关注两点:
    • 冲突少:很少出现不同的对象函数作用后得到相同的值。
    • 计算快:计算哈希能够快速找到对象。
     Hash函数还有另外的含义。实际中的Hash函数是指把一个大范围映射到一个小范围。把大范围映射到一个小范围的目的往往是为了节省空间,使得数据容易保存。除此以外,Hash函数往往应用于查找上。所以,在考虑使用Hash函数之前,需要明白它的几个限制:
    • Hash的主要原理就是把大范围映射到小范围;所以,你输入的实际值的个数必须和小范围相当或者比它更小。不然冲突就会很多。
    • 由于Hash逼近单向函数;所以,你可以用它来对数据进行加密。
    • 不同的应用对Hash函数有着不同的要求;比如,用于加密的Hash函数主要考虑它和单项函数的差距,而用于查找的Hash函数主要考虑它映射到小范围的冲突率。
    从简单原则出发,我们首先考虑下字符串的哈希函数。我们知道字符串特指ASCII的编码字符串,他们哈希函数后值是不一样的。看一个简单的算法
    djb2算法

    unsigned int DJB_hash(char *str)    
    {    
             unsigned int hash = 5381;    
        
             while (*str)    
             {    
                     hash += (hash << 5) + (*str++);    
             }    
        
             return (hash & 0x7FFFFFFF);    
    } 
    在看一个和djb算法相似的算法,sdbm算法
    unsigned int SDBM_hash(char *str)    
    {    
             unsigned int hash = 0;    
        
             while (*str)    
             {    
                     hash = (*str++) + (hash << 6) + (hash << 16) - hash;    
             }    
        
             return (hash & 0x7FFFFFFF);    
    }  

    虽然上面两种算法的很快,但是基于哈希冲突少的特点,djb算法和sdbm算法都没能提供理论的依据,而主要依赖于试验。
    在哈希的应用中,还有一类特殊的哈希函数,叫做密码哈希函数。

    密码学哈希函数

    定义:

      Hash函数H将可变长度的数据块M作为输入,产生固定长度的Hash值h = H(M)。
      称M是h的原像。因为H是多对一的映射,所以对于任意给定的Hash值h,对应有多个原像。如果满足x≠y且H(x)=H(y),则称为碰撞。

    密码学Hash函数的应用

    1、消息认证

      Hash码能够通过如下不同方法用于提供消息认证


     a) 使用对称密码E加密消息和Hash码,由于只有A和B共享密钥K,所以消息必然发自A处,且可通过验证Hash码证明数据在传输过程中未被更改。

        b) 使用对称密码只对Hash码加密。由于明文无需加密性的应用,这种方案大大减少了加密操作的负担。

        c) 不使用加密算法,仅使用Hash函数实现消息验证。该方案中,通信双方共享相同的秘密值S,发送方A将消息M和秘密值S串联后计算其Hash值,并将得到的Hash值附在消息M后发送。因为接收方B同时掌握S值,所以能够重新计算该Hash值进行验证。

        d) 在方案c的基础上将整个消息和Hash值加密,以提供保密性。

      处于成本和速度方面的考虑,人们越来越对那些不包含加密函数的方法感兴趣,因此b和c方案更受青睐,不过如果对整个消息有加密型要求,则a和d仍具有实际意义。

      实际应用中,消息认证通常使用消息认证码(MAC)实现。MAC函数将通信双方共享的密钥和数据块作为输入,产生Hash值作为MAC码,然后将MAC码和受保护的消息一起传递或存储。需要检查消息的完整性时,使用MAC函数对消息重新计算,并将计算结果与存储的MAC码对比。MAC提供安全保护,用于抵抗不知道密钥的攻击者的攻击。在实现中,往往使用比加密算法效率更高的特殊设计的MAC函数。

      2、数字签名

      数字签名的应用比消息认证更加广泛。主要有如下两种方案:


     a) 使用发送方的私钥利用公钥密码算法对Hash码进行加密。这种方法也可提供认证;由于只有发送方可以产生加密后的Hash码,所以这种方法也提供了数字签名。

        b) 若既希望保证保密性又希望有数字签名,则先用发送方的私钥对Hash码加密,再用对称密码中的密钥对象消息和公钥算法加密结果进行加密,这种技术比较常用。

      3、其他应用

      对于Hash函数,通常还被用于产生单向口令文件。在操作系统中,存储口令的Hash值而不是口令本身,当用户输入口令时,操作系统将比对输入口令的Hash值和存储在口令文件中的Hash值来进行用户验证。

      Hash函数还能用于入侵检测和病毒检测。将每个文件的Hash值H(F)存储在安全系统中(如CD-R),随后就能通过重新计算H(F)来判断文件是否被修改过。入侵者只能够改变F,而不能改变H(F)

      密码学Hash函数能够用于构建随机函数PRF或用作伪随机数发生器。基于Hash函数的PRF可用于对称密码中的密钥产生。

    密码学Hash函数的安全性需求


    弱Hash函数:只满足以上前五个要求的Hash函数。

      强Hash函数:满足以上前六个要求的Hash函数。

      强Hash函数能够保证免受以下攻击:假设Bob写一条借据消息并发送给Alice,Alice在借据上签名认可。Bob如果能找到两条消息具有同样的Hash值,其中一个借据消息要求Alice归还金额较小,另一个金额很大,那么让Alice签下第一个小额借据后,Bob就能声称第二个借据是真实的(将Alice在第一个借据的签名附到第二个借据中)。

      下图展示了抗原像攻击、抗弱碰撞攻击和抗强碰撞攻击三者之间的关系


     在传统观念中并没有把伪随机性作为密码学Hash函数的安全性需求,但在实际应用中或多或少有所要求。密码学Hash函数通常用于密钥产生、伪随机数发生器以及消息完整性应用,上述三个应用都要求Hash函数的输出是随机的。

    对Hash函数的攻击

      1、穷举攻击

      a) 原像攻击和第二原像攻击

      攻击者对给定的Hash值h,试图找到满足H(y) = h的y。穷举攻击的方法是随机选择y,尝试计算其Hash值知道碰撞出现。对于m位的Hash值,穷举的规模大约是2m,对于攻击者平均尝试次数为2m-1,才能找到一个满足H(y)=h的y值。

      b) 碰撞攻击

      对于碰撞攻击,攻击者试图找到两个消息或数据块x和y,满足H(x)=H(y),与原像攻击和第二原像攻击相比,其穷举的规模相对更小一些,这也通过数学上的生日悖论得到印证。本质上,如果我们在均匀分布的0到N-1的范围内选择随机整数变量,那么在N1/2次选择后发生重复的概率就会超过0.5。因此,对于m位的Hash值,如果我们随机选择数据块,预计在2m/2次尝试后就能找到两个具有相同Hash值的数据块。

      Yuval提出以下策略进行碰撞攻击:

        1、发送方A准备对文本消息x进行签名(尚未签名,但可预期要签名的文件内容),其使用的方法是:用A的私钥对m位的Hash码加密并将加密后的Hash码附于消息之后。

        2、攻击者产生该消息x的2m/2种变式x',每种变式都表达相同的意义,将这些消息以及对应的Hash值存储起来。

          产生多个具有相同意义的变式并不难,例如攻击者可以在文件的词与词之间插入若干“空格-空格-退格”字符对,然后在实例中用“空格-退格-空格”替代这些字符,从而产生各种变式。攻击者也可以简单地改变消息中的某些词但不改变消息的意义。

        3、攻击者准备伪造一条消息y,并想获取A的签名,只需要伪造y的变式y',然后计算H(y'),并与所有的H(x')进行比对,直到碰撞出现。

        4、攻击者将发生碰撞的消息x'提供给A签名,然后将该签名附于伪造消息y'后。这样攻击者就在不知道A密钥的情况下获得了有A数字签名的消息y',并可以此获利。


    参考:密码hash函数


    展开全文
  • 哈希函数需要易于计算并且能够均匀分布所有键。 在实际中,键并不一定都是数字,更有可能是字符串,还有可能是几个值的组合等。 1.整数 获取整数哈希值做常用的方法是使用除留余数法。即对于大小为素数M的数组,对于...

    哈希查找的第一步就是使用哈希函数将键映射成索引。这种映射函数就是哈希函数。如果有一个数组大小为M,那么就需要一个能够将任意键转换为该数组范围内的索引(0~M-1)的哈希函数。哈希函数需要易于计算并且能够均匀分布所有键。根据关键字的结构和分布的不同,可构造出许多不同的哈希函数。

    在实际中,键并不一定都是数字,更有可能是字符串,还有可能是几个值的组合等。

    1.整数

    获取整数哈希值做常用的方法是使用除留余数法。即对于大小为素数M的数组,对于任意整数k,计算k除以M的余数。M一般取素数。

    2.字符串

    将字符串作为键的时候,我们也可以将它作为一个大的整数,采用除留余数法。也可以将组成字符串的每一个字符取值然后进行哈希。

    参考

    1.浅谈算法和数据结构: 十一 哈希表

    展开全文
  • 哈希表 哈希函数 时间 安全从业人员的功能表中有一个工具可以帮助每个人理解,无论他们对计算机进行什么操作:加密哈希函数。 这听起来听起来像是神秘的,技术性的,甚至可能很无聊,但是我对什么是哈希以及它们为...
  • 了解了hash的思想之后,会发现哈希函数只是将关键字对下标的映射,没有什么特别的标准,冲突...如果关键字能够进过哈希函数计算得出的地址能够均匀地分布在地址区间中,就可以减少冲突。 直接定地址法 H(key...
  • 所有类型的数据, 包括浮点型, 字符型的都可以转化为整型, 然后用整型的哈希函数计算 哈希函数的设计要遵循一些原则: 一致性: 如果 a == b, 则 hash(a) == hash(b) 高效性: 计算高效简便 均匀性: 哈希值均.
  • 哈希是一种将哈希函数应用于数据的方法,其为几乎任何大小的输入(例如,文件,文本或图像)计算相对独特的输出(称为消息digest,或仅仅是digest)。它允许个人独立地获取输入数据、散列数据并得出相同的结果 - 证明...
  • 目录: ** 0x01 [哈希函数] vs [加密哈希函数] ** 0x02 [哈希碰撞] vs [生日问题] ** 0x03 [哈希表] vs [分布式哈希表] ...在哈希表计算索引的时候,我们需要一个哈希函数,通过hash(key)来计算key在哈...
  • 在某种程度上,散列是与排序相反的一种操作,排序是将集合中的元素按照某种方式比如字典顺序排列在一起,而散列通过计算哈希值,打破元素之间原有的关系,使集合中的元素按照散列函数的分类进行排列。 在介绍...
  • 常用的哈希函数

    千次阅读 2014-09-17 10:20:26
    常用的哈希函数包括:直接定址法、数字分析法、除留余数法、乘留余数法、平方取中法、折叠法等。应该根据实际工作中关 键码的特点选用适当的方法。 ...也就是如果两个不同的键用哈希函数计算得到了
  • 在某种程度上,散列是与排序相反的一种操作,排序是将集合中的元素按照某种方式比如字典顺序排列在一起,而散列通过计算哈希值,打破元素之间原有的关系,使集合中的元素按照散列函数的分类进行排列。 在介绍一些...
  • 哈希函数

    万次阅读 多人点赞 2018-03-01 08:12:14
    在某种程度上,散列是与排序相反的一种操作,排序是将集合中的元素按照某种方式比如字典顺序排列在一起,而散列通过计算哈希值,打破元素之间原有的关系,使集合中的元素按照散列函数的分类进行排列。在介绍一些集合...
  • 2 原理:每个url经过K个哈希函数在对应相应位置描黑,所有url描黑后,整个布隆过滤器相应类型的数组相当位置描黑,之后计算K个哈希函数对应位置,如果K个哈希函数对应位置上都是黑的那么这个url就在此黑名单里。...
  • 哈希法又称散列法、杂凑法以及关键字地址计算法等,相应的表称为...以后当查找关键字为k的元素时,再利用哈希函数计算出该元素的存储位置p=f(k),从而达到按关键字直接存取元素的目的。 当关键字集合很大时,关键字值
  • 单向函数特点:正向很容易 逆向很难定义:...计算f函数的逆f-1(x)是困难的,即对每一多项式时间概率算法M,每一多项式p(n)和充分大的n(n>n0)有Pr{M(f(Un)∈f-1(f(Un))}<1/p(n)Hash码把任意长变消息为固定长短的H...
  • 哈希函数的开散列

    2018-05-27 14:32:48
    一、哈希桶:1、通过哈希函数计算桶号 (1)哈希桶的最佳状态,就是每个桶下面挂一个元素(动态的可以增容:表格中的元素和总的个数相等):解决了一个哈希桶下面挂多个元素的情况(2)素数表泄露,则别人知道了增容...
  • 哈希法又称散列法、杂凑法以及关键字地址计算法等,相应...以后当查找关键字为k的元素时,再利用哈希函数计算出该元素的存储位置p=f(k),从而达到按关键字直接存取元素的目的。 当关键字集合很大时,关键字值不同的...
  • 其中h是定长的散列值,H是哈希函数,M是一个变长消息。 称M是h的原像。因为H是多对一的映射,所以对于任意给定的Hash值h,对应有多个原像。如果满足x≠y且H(x)=H(y),则称为碰撞。 Hash函数在数字签名和...
  • 什么是哈希冲突: 不同关键字通过相同哈希哈数计算出相同的哈希地址,该种现象称为哈希冲突或哈希碰撞。把具有不同关键码而具有相同哈希地址的数据元素称为“同义词” ...哈希函数计算出来的地址能均匀分布在
  • 哈希表查找的基本思想是:根据当前带查找数据的特征,以记录关键字为自变量,设计一个哈希函数,以该函数按关键码计算该元素的存储位置,并按此存放;查找时,有同一个函数对给定值key计算地址,将key与地址单元中...
  • 构造哈希函数

    2018-12-27 14:26:25
    设计哈希函数;分别采用线性探测再散列法和链地址法解决冲突 1.线性探测再散列:建立一个一维数组,需要计算数组的容量。如果是对12个数建立哈希表,则表长通过填满因子,计算为15。线性解决冲突的方法是通过哈希...
  • 密码学哈希函数

    千次阅读 2017-08-22 21:52:24
    什么是哈希函数哈希函数是一个数学函数,其具有以下三个特性: 输入可以为任意大小的字符串;其产生固定大小的输出;对于特定的输入字符串,能在合理时间计算出结果。对应n位的字符串,其哈希值计算的复杂度...
  • 哈希函数(两数求和)

    2019-08-30 15:10:36
    哈希 其实是随机存储的一种优化,先进行分类,然后查找时按照这个对象的分类去找。...如果存放时按照类别分开放,技术书、小说、文学等等分开(按照某种哈希函数计算),找书时只要从它对应的分...
  • 哈希函数,是用来计算存储数据的哈希值的,根据存储数据的类型,可以设计不同的哈希函数。一个好的哈希函数(让哈希表效率高的函数),一般都具备下面两个特点: 速度快(别计算一个哈希值计算了半天,导致效率很低...
  • 先用一个二维数组(char**)存储所有单词列表,然后用哈希函数计算每个单词的哈希值,存入哈希表中。然后遍历哈希表,同时进行桶排序,以链表的形式把二维数组中每个单词的地址存在桶里。最后输出桶中数据即可。 本...
  • 重温数据结构:哈希 哈希函数 哈希表

    万次阅读 多人点赞 2016-10-27 00:49:30
    在学习 HashMap 前,我们先来温习下 Hash(哈希) 的概念。...在某种程度上,散列是与排序相反的一种操作,排序是将集合中的元素按照某种方式比如字典顺序排列在一起,而散列通过计算哈希值,打破元素之间原

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,859
精华内容 1,143
关键字:

哈希函数计算