SSL协议的哈希函数碰撞攻击与防范
什么是哈希函数
什么是哈希函数 哈希（Hash）函数在中文中有很多译名，有些人根据Hash的英文原意译为“散列函数”或“杂凑函数”，有些人干脆把它音译为“哈希函数”，还有些人根据Hash函数的功能译为“压缩函数”、“消息摘要函数”、“指纹函数”、“单向散列函数”等等。 1、Hash算法是把任意长度的输入数据经过算法压缩，输出一个尺寸小了很多的固定长度的数据，即哈希值。哈希值也称为输入数据的数字指纹（Digital Fingerprint）或消息摘要（Message Digest）等。Hash函数具备以下的性质： 2、给定输入数据，很容易计算出它的哈希值； 3、反过来，给定哈希值，倒推出输入数据则很难，计算上不可行。这就是哈希函数的单向性，在技术上称为抗原像攻击性； 4、给定哈希值，想要找出能够产生同样的哈希值的两个不同的输入数据，（这种情况称为碰撞，Collision），这很难，计算上不可行，在技术上称为抗碰撞攻击性； 5、哈希值不表达任何关于输入数据的信息。 哈希函数在实际中有多种应用，在信息安全领域中更受到重视。从哈希函数的特性，我们不难想象，我们可以在某些场合下，让哈希值来“代表”信息本身。例如，检验哈希值是否发生改变，借以判断信息本身是否发生了改变。` 怎样构建数字签名 好了，有了Hash函数，我们可以来构建真正实用的数字签名了。 发信者在发信前使用哈希算法求出待发信息的数字摘要，然后用私钥对这个数字摘要，而不是待发信息本身，进行加密而形成一段信息，这段信息称为数字签名。发信时将这个数字签名信息附在待发信息后面，一起发送过去。收信者收到信息后，一方面用发信者的公钥对数字签名解密，得到一个摘要H；另一方面把收到的信息本身用哈希算法求出另一个摘要H’，再把H和H’相比较，看看两者是否相同。根据哈希函数的特性，我们可以让简短的摘要来“代表”信息本身，如果两个摘要H和H’完全符合，证明信息是完整的；如果不符合，就说明信息被人篡改了。 数字签名也可以用在非通信，即离线的场合，同样具有以上功能和特性。 由于摘要一般只有128位或160位比特，比信息本身要短许多倍，USB Key或IC卡中的微处理器对摘要进行加密就变得很容易，数字签名的过程一般在一秒钟内即可完成。
最小完美哈希函数(深入搜索引擎)
最小完美哈希函数 哈希函数h是一个能够将n个键值x j的集合映射到一个整数集合的函数h(x i)，其值域范围是0≤h(x j)≤m-l，允许重复。哈希是一个具有查找表功能并且提供平均情况下快速访问的标准方法。例如，当数 据包含n个整数键值。某常用哈希函数采用h(x)=x mod m，其中m 是一个较小的值，且满足m>n/a。a是装载因子，表示记录数和可用地址数的比例关系。m一般选择一个素数，因此如果要求提供一个对1000个整数键值进行哈希的函数，一个程序员可能会建议写出如下函数形式：，h(x)=x mod 1399。并且提供一个装载因子为。a=0.7的表，该表声明能够存放1399个地址。 a越小，两个不同键值在相同哈希值相互冲突的可能性就越小，然而冲突总是不可避免。第1次考虑这个问题时，事实可能让人吃惊，最好的例子莫过于著名的生日悖论(birthday paradox)。假定一年有365天，那么要组合多少个人，才能使得出现生日相同的人这一概率超过0.5呢？换句话说，给定一个365个哈希槽(hashslot)。随机选择多少个键值才能够使得出现冲突的概率超过0.5?当首次面对这样一个问题时，一般的反应肯定是认为需要很多人才行。事实上，答案是只需区区23人。找到一个能够满足现实大小要求且无冲突的哈希函数的几率小到几乎可以忽略25。例如，一个1000个键值和1399个随机选择的槽，完全没有冲突的概率为 2.35×10-217（概率的计算诱导公式将在下一节中给出，以公式4.1代入m=1399和n=1000得到），如何才能最好地处理这些不可避免冲突？这一话题将在本节中以大段篇幅展开，这里我们正是要找到其中万里挑一的能够避免所有冲突的哈 希函数。 25可以试图在一群人中做这样一个有趣的实验，笔者曾在讲述哈希表的课上和同学们做 过多次这样的实验。有一项很重要的事情往往被我们忽略，即参加者必须事先在纸上写下他们的生日（或者其他任意日子）。然后才能开始核对的工作，这样才能消除神奇的负反馈。在我们的实验中，除非这样做了，否则也许必须找到366个同学才能遇到第1次碰撞，也许这乜存在心理学悖论吧。
HASH函数
密码学 （第十三讲） HASH函数 张焕国 武汉大学计算机学院
目录 密码学的基本概念 1、密码学 2、古典 、古典密码 3、数据加密标准（ ） DES） 、数据加密标准（DES 4、高级 ） AES） 数据加密标准（AES 高级数据加密标准（ 5、中国商用密码（ ） SMS4） 、中国商用密码（SMS4 6、分组密码的应用技术 7、序列密码 8、习题课：复习对称密码 、公开密钥密码（11） 9、公开密钥密码（
目录 公开密钥密码（22） 10 10、 11、数字签名（1） 12、数字签名（2） 13、 、HASH函数 13 14 14、 15、 15 PKI技术 16 16、 、PKI 17、习题课：复习公钥密码 18、总复习
一、HASH 函数函数的概念的概念 1、Hash Hash的作用的作用 ?Hash Hash码也称报文摘要码也称报文摘要。。 ?它具有极强的错误检测能力错误检测能力。。 ?用Hash Hash码作码作MAC ，可用于认证认证。。 ?用Hash Hash码辅助码辅助数字签名数字签名。。 ?Hash Hash函数可用于函数可用于保密保密。。
一、HASH 函数的概念 2、Hash Hash函数的定义函数的定义 ①Hash Hash函数将任意长的数据函数将任意长的数据M 变换为定长的码h ， 记为记为：：h=HASH(M)h=HASH(M)或或h=H(M)h=H(M)。。 ②实用性：对于给定的数据对于给定的数据M M ，计算，计算h=HASH(M)h=HASH(M)是是 高效的。 ③安全性安全性：： ? 单向性：对给定的对给定的Hash Hash值值h ，找到满足H(x)H(x)＝＝h 的x 在 计算上是不可行的计算上是不可行的。。 否则否则，，设传送数据为设传送数据为C=C=＜＜M ，H(M||K )＞,K 是密钥。攻击者可以截获攻击者可以截获C,C,求出求出Hash 函数的逆函数的逆，，从而得出 M||S ＝H -1(C)，然后从M 和M ||Ｋ即可即可得出得出Ｋ。
哈希函数编程实现
#include 常用的哈希函数 通用的哈希函数库有下面这些混合了加法和一位操作的字符串哈希算法。下面的这些算法在用法和功能方面各有不同，但是都可以作为学习哈希算法的实现的例子。(其他版本代码实现见下载） 1.RS 从Robert Sedgwicks的Algorithms in C一书中得到了。我(原文作者)已经添加了一些简单的优化的算法，以加快其散列过程。 [java]view plaincopy 1.public long RSHash(String str) 2. { 3.int b = 378551; 4.int a = 63689; 5.long hash = 0; 6.for(int i = 0; i < str.length(); i++) 7. { 8. hash = hash * a + str.charAt(i); 9. a = a * b; 10. } 11.return hash; 12. } 2.JS Justin Sobel写的一个位操作的哈希函数。 [c-sharp]view plaincopy 1.public long JSHash(String str) 2. { 3.long hash = 1315423911; 4.for(int i = 0; i < str.length(); i++) 5. { 6. hash ^= ((hash << 5) + str.charAt(i) + (hash >> 2)); 7. } 8.return hash; 9. } 3.PJW 该散列算法是基于贝尔实验室的彼得J温伯格的的研究。在Compilers一书中（原则，技术和工具），建议采用这个算法的散列函数的哈希方法。 上机三：HASH函数编程 【上机目的】 熟悉HASH函数的基本原理和性质，通过编程/开源代码分析了解一种标准HASH算法的运行原理。 【上机环境】 1、硬件PC机一台。 2、系统配置：操作系统windows XP以上。 3、编程语言：C/C++/C#/Java/Python 【上机内容及要求】 1、MD5算法分析和实现 2、使用实例分析 备注：可借鉴网上相关算法的开源代码进行编程实现，编程语言不限；除了MD5算法，也可以选取SHA系列HASH算法（或其它任一种标准的HASH算法）进行研究。 【上机报告】 实验过程： Python遇到Hash，内置的函数库就可以解决，但要是想理解算法与原理。还是要走一边流程。 Python hash库的应用 import hashlib psw="a" md5 = hashlib.md5() #初始化摘要对象 md5.update(psw.encode('utf-8')) #使用md5算法计算 print(md5.hexdigest())#输出16进制字符串 ‘a’的Hash值对应‘0cc175b9c0f1b6a831c399e269772661’ 让a=‘bujunjie’我的名字hash 看来老师让我们分析分析源码吗？ 要分析源码首先搞一下。什么是HASH？ 摘要算法是将信息压缩提取以作为数据指纹的算法,我们下载东西要确认下的 东西有没有下错下漏常用这种算法来做验证,在密码学中这是很多算法的基础 具体摘要算法是怎么样的？摘要算法又称哈希算法、散列算法。它通过一个函数，把任意长度的数据转换为一个长度固定的数据串（通常用16进制的字符 串表示） 还有一种应用场景是用来存储用户的密码,大明文密码存储在数据库里很不安全,之前爆出很多知名网站将用户密码以明文存储,导致信息泄露.可以通过摘 要算法给密码加个密存储进去.这样要破解密码除了要知道密码本身,还得知道 生成最终摘要文本的算法才可以.也就相对安全多了。 MD5是输入不定长度信息，输出固定长度128-bits的算法。经过程序流程，生成四个32位数据，最后联合起来成为一个128-bits散列。基本方式为，求余、取余、 调整长度、与链接变量进行循环运算。得出结果。 -----------------------------摘自wiki百科 //Note: All variables are unsigned 32 bits and wrap modulo 2^32 when calculating var int[64] r, k //r specifies the per-round shift amounts r[ 0..15]：={7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22} r[16..31]：={5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20} r[32..47]：={4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23} r[48..63]：={6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21} 封面 作者：PanHongliang 仅供个人学习 Hash函数在信息安全中的重要运用 学号：09008010124姓名：罗杨 摘要：随着计算机和Internet在各行各业的广泛应用，信息高速化的交互 传递过程中，信息安全问题备受关注。而基于hash函数的各种算法的产生和运用，为信息上一把牢固的安全之锁，md5、sha-1文件校验，加密存储，数字签名，PKI建设等对各种信息有充分的安全保障，能有效地防止攻击，保证真实信息不被修改或者泄露。 关键词：哈希 hash md5 数字签名 PKI 散列校验公钥私钥 一、定义 Hash，一般翻译做"散列"，也有直接音译为"哈希"的，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。HASH主要用于信息安全领域中加密算法，他把一些不同长度的信息转化成杂乱的128位的编码里，叫做Hash值。 二、算法举例 1、MD4 MD4(RFC 1320)是 MIT 的 Ronald L. Rivest 在 1990 年设计的，MD 是Message Digest 的缩写。它适用在32位字长的处理器上用高速软件实现--它是基于 32 位操作数的位操作来实现的。 MD4散列的例子： MD4 ("") = 31d6cfe0d16ae931b73c59d7e0c089c0 MD4 ("a") = bde52cb31de33e46245e05fbdbd6fb24 MD4 ("abc") = a448017aaf21d8525fc10ae87aa6729d MD4 ("message digest") = d9130a8164549fe818874806e1c7014b 2、MD5 任务一 MD5算法111111********* 一．哈希函数简介 信息安全的核心技术是应用密码技术。密码技术的应用远不止局限于提供机密性服务,密码技术也提供数据完整性服务。密码学上的散列函数(Hash Functions)就是能提供数据完整性保障的一个重要工具。Hash函数常用来构造数据的短“指纹”：消息的发送者使用所有的消息产生一个附件也就是短“指纹”，并将该短“指纹”与消息一起传输给接收者。即使数据存储在不安全的地方，接收者重新计算数据的指纹，并验证指纹是否改变，就能够检测数据的完整性。这是因为一旦数据在中途被破坏，或改变，短指纹就不再正确。 散列函数是一个函数，它以一个变长的报文作为输入，并产生一个定长的散列码，有时也称为报文摘要，作为函数的输出。散列函数最主要的作用于是用于鉴别，鉴别在网络安全中起到举足轻重的地位。鉴别的目的有以下两个：第一，验证信息的发送者是真正的，而不是冒充的，同时发信息者也不能抵赖，此为信源识别；第二，验证信息完整性，在传递或存储过程中未被篡改，重放或延迟等。 二．哈希函数特点 密码学哈希函数（cryptography hash function，简称为哈希函数）在现代密码学中起着重要的作用，主要用于对数据完整性和消息认证。哈希函数的基本思想是对数据进行运算得到一个摘要，运算过程满足： z压缩性：任意长度的数据，算出的摘要长度都固定。 z容易计算：从原数据容易算出摘要。 z抗修改性：对原数据进行任何改动，哪怕只修改1个字节，所得到的摘要都有很大区别。 z弱抗碰撞：已知原数据和其摘要，想找到一个具有相同摘要的数据（即伪造数据），在计算上是困难的。 数字签名与哈希函数 懂得一点公钥密码基础知识的人都知道，发信息的人用自己的私钥对所发信息进行加密( Encryption )，接收信息者用发信者的公钥来解密( Decryption )，就可以保证信息的真实性、完整性与不可否认性。（注：这里提到的加密、解密是指密码运算，其目的并非信息保密。）那么，我们也可以笼统地说，以上方法就已经达到了数字签名的目的。因为首先，私钥是发信者唯一持有的，别的任何人不可能制造出这份密文来，所以可以相信这份密文以及对应的明文不是伪造的（当然，发信者身份的确定还要通过数字证书来保证）；出于同样原因，发信者也不能抵赖、否认自己曾经发过这份信息；另外，信息在传输当中不可能被篡改，因为如果有人试图篡改，密文就解不出来。这样，用私钥加密，公钥解密的技术方法就可以代替传统签名、盖章，保证了信息的真实性、完整性与不可否认性。 但是，这样做在实际使用中却存在一个问题：要发的信息可能很长，非对称密码又比较复杂，运算量大，而为了保证安全，私钥通常保存在USB Key或IC卡中，加密运算也是在Key或卡中进行。一般来说，小小的USB Key或IC卡中的微处理器都做得比较简单而处理能力较弱，这样，加密所用的时间就会很长而导致无法实用。 另外，即使对于网站服务器而言，虽然它的处理能力很强，但服务器要同时处理许许多多签名加密的事情，也同样存在着加密耗时长系统效率低的问题。 有没有解决这个问题的办法呢？有的，常用的方法是使用哈希函数。 什么是哈希函数 哈希（Hash）函数在中文中有很多译名，有些人根据Hash的英文原意译为“散列函数”或“杂凑函数”，有些人干脆把它音译为“哈希函数”，还有些人根据Hash函数的功能 完美哈希函数 原理： 哈希查找是非常实用且快速的查找结构。其基本思想是将键值映射为[0,M)中的一个整数h,而键值存放的位置与h 有关。称映射h 为哈希函数，称h(key)为键值key 的哈希值，称M 为哈希表长。如果需要查找某个键值，首先计算哈希值，然后根据其哈希值来查找具体位置。 具体实现： 假设有一个字符串T = a 1a 2a 3^^^^^^^a n ，设计的哈希函数为hash(T)= (a 1*1+a 2*2+a 3*3+^^^^^^^a n *n)%253。先将关键字存在一个字符串数组 char *key[32]中，计算出每个关键字的哈希值，然后将关键字存在哈希表中char *HASH[253]（字符串数组要初始化，使每个字符串为空）中，哈希值作为数组下标。 源代码： #include "continue","default","do","double", "else","enum","extern", "float","for","goto","if","int","long", "register", "return", "short", "signed","sizeof","static", "struct","switch", "typedef","union","unsigned", "void","volatile","while"}; int hash(char *string) { int i=1; int ix = 0; for(;*string;string++) { ix =ix + i*(*string); i++; } ix = ix%253; return ix; }; int findkey(char * str) { int i; 散列函数 又称hash函数，Hash函数(也称杂凑函数或杂凑算法)就是把任意长的输入消息串变化成固定长的输出串的一种函数。这个输出串称为该消息的杂凑值。一般用于产生消息摘要，密钥加密等. 一个安全的杂凑函数应该至少满足以下几个条件: ①输入长度是任意的; ②输出长度是固定的,根据目前的计算技术应至少取128bits长,以便抵抗生日攻击; ③对每一个给定的输入,计算输出即杂凑值是很容易的 ④给定杂凑函数的描述,找到两个不同的输入消息杂凑到同一个值是计算上不可 行的,或给定杂凑函数的描述和一个随机选择的消息,找到另一个与该消息不同的消息使得它们杂凑到同一个值是计算上不可行的。 Hash函数主要用于完整性校验和提高数字签名的有效性,目前已有很多方案。这些算法都是伪随机函数,任何杂凑值都是等可能的。输出并不以可辨别的方式依赖于 输入;在任何输入串中单个比特的变化,将会导致输出比特串中大约一半的比特发生变化。 常见散列函数(Hash函数) ·MD5（Message Digest Algorithm 5）：是RSA数据安全公司开发的一种单向散列算法，MD5被广泛使用，可以用来把不同长度的数据块进行暗码运算成一个128位的数值； ·SHA（Secure Hash Algorithm）这是一种较新的散列算法，可以对任意长度的数据运算生成一个160位的数值； ·MAC（Message Authentication Code）：消息认证代码，是一种使用密钥的单向函数，可以用它们在系统上或用户之间认证文件或消息。HMAC（用于消息认证的密钥散列法）就是这种函数的一个例子。 ·CRC（Cyclic Redundancy Check）：循环冗余校验码，CRC校验由于实现简单，检错能力强，被广泛使用在各种数据校验应用中。占用系统资源少，用软硬件均能实现，是进行数据传输差错检测地一种很好的手段（CRC 并不是严格意义上的散列算法，但它的作用与散列算法大致相同，所以归于此类）。 讨论几种散列函数。在以下的讨论中，我们假设处理的是值为整型的关键码，否则我们总可以建立一种关键码与正整数之间的一一对应关系，从而把该关键码的检索转化为对与其对应的正整数的检索；同时，进一步假定散列函数的值落在0到M－1 之间。散列函数的选取原则是：运算尽可能简单；函数的值域必须在散列表的范围内；尽可能使得结点均匀分布，也就是尽量让不同的关键码具有不同的散列函数值。需要考虑各种因素：关键码长度、散列表大小、关键码分布情况、记录的检索频率等等。下面我们介绍几种常用的散列函数。 1、除余法 字符串Hash函数 今天根据自己的理解重新整理了一下几个字符串hash函数，使用了模板，使其支持宽字符串，代码如下： /// @brief BKDR Hash Function /// @detail 本算法由于在Brian Kernighan与Dennis Ritchie的《The C Programming Language》一书被展示而得名，是一种简单快捷的hash算法，也是Java目前采用的字符串的Hash算法（累乘因子为31）。 template 哈希函数 1 基本原理 我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数，也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标）相对应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照关键字为每一个元素"分类"，然后将这个元素存储在相应"类"所对应的地方。 但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了"冲突"，换句话说，就是把不同的元素分在了相同的"类"之中。后面我们将看到一种解决"冲突"的简便做法。 总的来说，"直接定址"与"解决冲突"是哈希表的两大特点。 2 函数构造 构造函数的常用方法（下面为了叙述简洁，设h(k) 表示关键字为k 的元素所对应的函数值）： a) 除余法： 选择一个适当的正整数p ，令h(k ) = k mod p 这里，p 如果选取的是比较大的素数，效果比较好。而且此法非常容易实现，因此是最常用的方法。 b) 数字选择法： 如果关键字的位数比较多，超过长整型范围而无法直接运算，可以选择其中数字分布比较均匀的若干位，所组成的新的值作为关键字或者直接作为函数值。 3 冲突处理 线性重新散列技术易于实现且可以较好的达到目的。令数组元素个数为S ，则当h(k) 已经存储了元素的时候，依次探查(h(k)+i) mod S , i=1,2,3…… ，直到找到空的存储单元为止（或者从头到尾扫描一圈仍未发现空单元，这就是哈希表已经满了，发生了错误。当然这是可以通过扩大数组范围避免的）。 4 支持运算 哈希表支持的运算主要有：初始化(makenull)、哈希函数值的运算(h(x))、插入元素(insert)、查找元素(member)。 设插入的元素的关键字为x ，A 为存储的数组。 初始化比较容易，例如 const empty=maxlongint; // 用非常大的整数代表这个位置没有存储元素 p=9997; // 表的大小 procedure makenull; var i:integer; begin for i:=0 to p-1 do A[i]:=empty; End; 哈希函数值的运算根据函数的不同而变化，例如除余法的一个例子： function h(x:longint):Integer; begin常用的哈希函数
HASH函数编程
Hash函数在信息安全中的重要运用
Hash算法实验原理及哈希函数简介
数字签名及哈希函数
完美哈希函数
散列函数
字符串Hash函数(源代码)
哈希函数