精华内容
下载资源
问答
  • 1.信息摘要函数(Hash函数)的设计与性质验证实验 2.实验目的:信息摘要函数(Hash函数)的设计与性质验证。 2.1实验设备:PC机 一台/人 2.2实验原理: 2.2.1.信息摘要函数具有固定的输出数位。 2.2.1信息摘要函数满足不...

    1.信息摘要函数(Hash函数)的设计与性质验证实验

    2.实验目的:信息摘要函数(Hash函数)的设计与性质验证。

    2.1实验设备:PC机 一台/人

    2.2实验原理:

    2.2.1.信息摘要函数具有固定的输出数位。

    2.2.1信息摘要函数满足不可求逆,不可伪造和在可行时间之内找不到碰撞等特性。

    3.实验内容及注意事项:

    信息摘要函数的设计与Hash值的性质验证

    实验步骤:

    3.1设计符合原理要求的信息摘要函数H(m)。

    3.2对于如下明文信息m:

    There was a grocery shop in a town. Plenty of mice lived in that grocery shop. Food was in plenty for them. They ate everything and spoiled all the bags. They also wasted the bread, biscuits and fruits of the shop. The grocer got really worried. So, he thought "I should buy a cat and let it stay at the grocery. Only then I can save my things." He bought a nice, big fat cat and let him stay there. The cat had a nice time hunting the mice and killing them. The mice could not move freely now. They were afraid that anytime the cat would eat them up. The mice wanted to do something. They held a meeting and all of them tweeted "We must get rid of the cat. Can someone give a suggestion"?  All the mice sat and brooded. A smart looking mouse stood up and said, "The cat moves softly. That is the problem. If we can tie a bell around her neck, then things will be fine. We can know the movements of the cat". “Yes, that is answer," stated all the mice. An old mouse slowly stood up and asked, "Who would tie the bell?" After some moments there was no one there to answer this question. 
    

    调用H(m)算法,产生Hash值。

    3.3随机改变m的任意一位字符,产生新的Hash值,

    如此实验10次,记新的Hash值为 H1,H2,…H10

    3.4设计函数计算H0和Hi 的相似度 i=1,2,…10

    3.5分析结果,得出结论

    4.实验过程

    4.1设计 哈希函数Hash(m)的思路

    MD5摘要算法是Hash摘要算法中的一种摘要算法,具有不可求逆性,不可伪造性。MD5 算法自诞生之日起,就有很多人试图证明和发现它的不安全之处,即存在碰撞(在对两个不同的内容使用 MD5算法运算的时候,有可能得到一对相同的结果值)。2009年,中国科学院的谢涛和冯登国仅用了 的碰撞算法复杂度,破解了MD5的碰撞抵抗,该攻击在普通计算机上运行只需要数秒钟 。因此MD5算法不具备实验中要求的“在可行时间之内找不到碰撞”这个特性。
    ​ 根据MD5的存在的缺点,为了加强MD5加密算法的安全性(本身是不可逆的),从而加入了新的算法部分即加盐值,加盐值是随机生成的一组字符串,可以包括随机的大小写字母、数字、字符,位数可以根据要求而不一样,使用不同的加盐值产生的最终密文是不一样的。由于使用加盐值以后的密码相当的安全,即便是你获得了其中的salt和最终密文,破解也是一个耗费相当多时间的过程,可以说是破解单纯MD5的好几倍。并且同一个明文在经过加盐(这个盐是随机的,不同的)后进行MD5算法产生的密文也是不同的。这就使得MD5算法的抗碰撞性得到大幅度增强,因此可以满足本次实验要求。

    4.2MD5+盐的实现步骤

    1).首先获取需要进行md5普摘要算法的明文text。
    2).随机生成加盐值(可以由字母,数字,字符组成,位数可以自己决定,这里使用16位的字符串)salt字符串.
    3)将生成的salt字符串追加到明文text中,得到组合的字符串 mergeText = text +salt
    4)使用md5普通摘要算法获取mergeText 的hash值得到一个32位的字符串decodeText。
    5).将盐salt字符串的每个字符逐个插入到字符串decodeText是 i *3+1(i = 0,1,2,…16)的位置上,得到一个新的48位的字符串 decode。
    6)最终的decode字符串就是所要的密文,位长为48个字符。

    该代码已经用c++实现,具体请看:C++实现MD5摘要算法加盐salt值

    4.3具体代码实现

    4.3.1MD5的普通加密算法

    4.3.1.1.将二进制字节数组转换为16进制的字符串
    /* Convert byte array to hex string. */
    string MD5::bytesToHexString(const byte *input, size_t length) {
    	string str;
    	str.reserve(length << 1);
    	for (size_t i = 0; i < length; i++) {
    		int t = input[i];
    		int a = t / 16;
    		int b = t % 16;
    		str.append(1, HEX[a]);
    		str.append(1, HEX[b]);
    	}
    	return str;
    }
    
    string EncryptUtil::md5Hex(const string& text) {
    	//首先更新md5中需要进行摘要的字符串
    	this->md5->update(text);
    	//使用md5的方法生成对应的摘要后的字符串
    	return this->md5->toString();
    
    }
    

    4.3.2产生盐值字符串的算法

    /**
    产生盐值字符串salt
    */
    string EncryptUtil::createSalt()
    {
    	//随机生成两个随机数
    	int num1 = rand() % 99999999;
    	int num2 = rand() % 99999999;
    	string salt = "";
    	//将这两个随机数转换为字符串后追加到salt中
    	salt.append(to_string(num1));
    	salt.append(to_string(num2));
    	//salt不够十六位就在后面加0
    	int len = salt.size();
    	if (len < 16) {
    		for (int i = 0; i < 16 - len; i++) {
    			salt.append("0");
    		}
    	}
    	return salt;
    }
    
    

    4.3.3获取md5普通摘要函数+盐值salt操作后的最终密文

    /**
    * 加盐MD5
    * @param text : 需要进行加盐后摘要的text明文
    * @return string:返回进行摘要算法后的字符串
    */
    string EncryptUtil::encryptBySalt(const string& text) {
    	//产生盐值字符串salt
    	string salt = createSalt();
    	//将产生的salt追加到需要进行摘要的明文text中,得到由明文text和salt组成的字符串
    	string merge_str =  text + salt;
    	//使用md5算法进行摘要计算得到相应的32位的密文
    	string encodeText = md5Hex(merge_str);
    	char cs [48];
    	//将32位的密文和产生的16位的salt进行重组形成新的48位的字符串。
    	//这里表示,在新的字符数组cs中,salt中的字符添加到cs字符数组中位置是i*3+1的位置,其它位置由摘要密文encodeText中的字符填充
    	for (int i = 0; i < 48; i += 3) {
    		cs[i] = encodeText[i / 3 * 2];
    		char c = salt[i / 3];
    		cs[i + 1] = c;
    		cs[i + 2] = encodeText[i / 3 * 2 + 1];
    	}
    	//将组合成的cs字符数组转化为字符串得到48位的加盐后形成的md5摘要密文
    	string code = "";
    	for (int i = 0; i < 48; i++)
    	{
    	  code.append(1,cs[i]);
    	}
    	return code;
    }
    

    4.3.4校验加盐后是否和原文一致

    /**
     * 校验加盐后是否和原文一致
     * @param text : 进行摘要算法的明文
     * @param encryptText  : 进行加盐摘要算法后的密文
     * @return 如果加盐后和原明文text一致则返回true,否则返回false
     */
     bool EncryptUtil::verify( string text,  string encryptText) {
    	char md5Text[32];
    	char salt[16];
    	//首先将加盐后md5算法摘要得到的encryptText密文进行拆分成一个32位的普通md5摘要算法密文md5Text和一个16位的字符串salt。
    	//这里就是进行salt和md5摘要密文形成48位新的字符串encryptText时的逆向操作。encryptText中salt[i] =  encryptText[ 3* i + 1], i = 0,1,2,...16
    	for (int i = 0; i < 48; i += 3) {
    		md5Text[i / 3 * 2] = encryptText[i];
    		md5Text[i / 3 * 2 + 1] = encryptText[i + 2];
    		salt[i / 3] = encryptText[i + 1];
    	}
    	//将拆分的16个随机字符串追salt加到明文text中
    	for (int  i = 0; i < 16; i++)
    	{
    		text.append(1,salt[i]);
    	}
    	//使用md5摘要算法进行生成密文得到enCs2
    	string enCs2 = md5Hex(text);
    	//比较两个字符串相等,如果相等则返回true,只要有一个字符不相等就返回false
    	for (int i = 0; i < enCs2.size(); i++)
    	{
    		if (enCs2[i] != md5Text[i])
    		{
    			return false;
    		}
    	}
    	return true;
    }
    

    4.3.5 逐个比较两个密文相同位置上字符是否相同来计算两个明文进行md5加密后的相似度。

    /**
      逐个比较两个密文相同位置上字符是否相同来计算两个明文进行md5加密后的相似度。
     @param str1: md5摘要算法后的字符串
     @param str2:md5摘要算法后的字符串
     @return double: 返回相似度
     */
    double EncryptUtil::similarityDegree(const string& str1, const string& str2)
    {
    	if (str1.size() <= 0 && (str1.size() != str2.size()))
    	{
    		return 0;
    	}
    	int count = 0;
    	//统计对应位置上字符相同的个数
    	for (int i = 0; i < str1.size(); i++)
    	{
    		if (str1[i] == str2[i])
    		{
    			count++;
    		}
    	}
    	//计算相似度
    	double result = count * 1.0 / str1.size();
    	return result;
    }
    

    4.3.6为了方便,将明文保存到文件中,然后读取文件内容作为字符串

    string loadTextToString(const string textFilePath) {
    	ifstream* ism = new ifstream(textFilePath,ios::app|ios::binary);
    	if (ism->is_open())
    	{
    		string text = "";
    		char ch;
    		while (!ism->eof())
    		{
    			ism->get(ch);
    			text.append(1,ch);
    		}
    		return text;
    	}
    	else {
    		cout << "打开文件失败!" << endl;
    		return "";
    	}
    }
    
    

    5.验证实验内容

    设计函数验证获取H0到H10的密文,并计算相似度。

    string randomReplace(string text,int index,string replaceChar) {
    	return text.replace(index,1,replaceChar);
    }
    void test() {
    	string text = loadTextToString("hashtext.txt");
    	cout << "需要加密的明文为:\n" << text << endl;
    	EncryptUtil util;
    	string md0 = util.encryptBySalt(text);
    	cout << "md5加盐后加密的md5值H0:" + md0 << endl;
    	vector<string> vec;
    	for (int i = 0; i < 10; i++)
    	{
    		//替换十个字符,每个原来的字符+1
    		string  newStr =	randomReplace(text, i * 5,string(1, text[i * 5] + 1));
    		//计算每个替换后字符的hash值
    		 string encodeText =util.encryptBySalt(newStr);
    		vec.push_back(encodeText);
    	}
    	for (size_t i = 0; i < 10; i++)
    	{
    		cout << "md5加盐后加密的md5值H"+ to_string(i + 1) + ":" + vec[i]<< endl;
    	}
    	for (size_t i = 0; i < 10; i++)
    	{
    		//计算H0和H的相似度
    		cout << "H0和H" + to_string(i + 1) + "的相似度:" + to_string(util.similarityDegree(md0, vec[i])) << endl;
    	}
    }
    

    [外链图片转存中...(img-GMQD1fac-1607789521383)]

    md5加盐后加密的md5值H0:051293435697829a9bc1de2ff8ed0cb0a908706504302100
    md5加盐后加密的md5值H1:061233445697859a2bc8de3ff0ed0cb0a908706504302100
    md5加盐后加密的md5值H2:021203415697819a2bc1de9ff1ed6cb0a908706504302100
    md5加盐后加密的md5值H3:091243475677819a6bc4de1ff3ed0cb0a908706504302100
    md5加盐后加密的md5值H4:031203425687869a4bc8de6ff3ed0cb0a908706504302100
    md5加盐后加密的md5值H5:011253485697809a1bc5de5ff0ed7cb0a908706504302100
    md5加盐后加密的md5值H6:031203485607829a1bc5de3ff6ed6cb0a908706504302100
    md5加盐后加密的md5值H7:031203425617829a1bc5de0ff8ed0cb0a908706504302100
    md5加盐后加密的md5值H8:011293475627869a2bc0de0ff9ed0cb0a908706504302100
    md5加盐后加密的md5值H9:021223425667899a1bc2de7ff0ed0cb0a908706504302100
    md5加盐后加密的md5值H10:091293415627829a3bc6de5ff5ed0cb0a908706504302100
    H0和H1的相似度:0.833333
    H0和H2的相似度:0.833333
    H0和H3的相似度:0.812500
    H0和H4的相似度:0.812500
    H0和H5的相似度:0.812500
    H0和H6的相似度:0.812500
    H0和H7的相似度:0.854167
    H0和H8的相似度:0.833333
    H0和H9的相似度:0.812500
    H0和H10的相似度:0.854167

    6.拓展

    6.1验证md5经过摘要算法后和原来明文一致

    void test9() {
    	string text = loadTextToString("hashtext.txt");
    	EncryptUtil util;
    	string encodeText = util.encryptBySalt(text);
    	string encodeText1 = util.encryptBySalt(text);
    	cout << "md5加盐后加密的md5值:" + encodeText << endl;
    	cout << "md5加盐后加密的md5值:" + encodeText1 << endl;
    	if (encodeText.compare(encodeText1) == 0)
    	{
    		cout << "两次生成的加盐密文相等!" << endl;
    	}
    	else {
    		cout << "两次生成的加盐密文不相等!" << endl;
    	}
    	bool fla = util.verify(text, encodeText);
    	if (fla == true)
    	{
    		cout << "原来的明文和加盐后的明文一致得到验证!" << endl;
    	}
    	else {
    		cout << "原来的明文和加盐后的明文不一致!" << endl;
    	}
    
    }
    

    [外链图片转存中...(img-eCm0qnl5-1607789521389)]

    md5加盐后加密的md5值:071263445647839a7bc0de0ff0ed0cb0a908706504302100
    md5加盐后加密的md5值:021253435637849a1bc6de1ff8ed9cb0a908706504302100
    两次生成的加盐密文不相等!
    原来的明文和加盐后的明文一致得到验证!
    

    由结果知道,虽然加盐后得到的密文不一样,但是相同的明文产生的密文是可以通过验证知道原来的明文是否一致的。

    7.完整的代码

    #pragma once
    #include<iostream>
    #include<string>
    #include"Md5.h"
    #include<time.h>
    using namespace std;
    
    class EncryptUtil
    {
    public:
    	EncryptUtil();
    /**
    *@param text:需要进行普通md5摘要算法计算的明文
    *@return string:返回普通md5摘要算计算后的字符串
    */
    	string md5Decode(const string& text);
    /**
    产生盐值字符串salt
    */
    	string createSalt();
    
    /**
    * 加盐MD5
    * @param text : 需要进行加盐后摘要的text明文
    * @return string:返回进行摘要算法后的字符串
    */
    	string encryptBySalt(const string& text);
    /**
     * 获取十六进制字符串形式的MD5摘要
     * @param text: 需要进行摘要算法的明文
     * @return string: 返回进行普通md5摘要后的字符串
     */
    	string md5Hex(const string& src);
    /**
     * 校验加盐后是否和原文一致
     * @param text : 进行摘要算法的明文
     * @param encryptText  : 进行加盐摘要算法后的密文
     * @return 如果加盐后和原明文text一致则返回true,否则返回false
     */
    	bool verify( string text,  string md5Text);
    /**
      逐个比较两个密文相同位置上字符是否相同来计算两个进行md5加密后的相似度。
     @param str1: md5摘要算法后的字符串
     @param str2:md5摘要算法后的字符串
     @return double: 返回相似度
     */
    	double similarityDegree(const string& str1, const string& str2);
    	~EncryptUtil();
    private:
    	MD5* md5 = nullptr;
    	
    };
    
    
    
    #include "EncryptUtil.h"
    
    
    
    EncryptUtil::EncryptUtil()
    {
    	//初始化MD5这个类
    	this->md5 = new MD5();
    	//设置随机数种子,在产生盐时可以产生随机数。
    	srand(time(NULL));
    }
    
    /**
    *@param text:需要进行普通md5摘要算法计算的明文
    *@return string:返回普通md5摘要算计算后的字符串
    */
    string EncryptUtil::md5Decode(const string & text)
    {
    	//调用md5Hex(text)函数即可
    	 return this->md5Hex(text);
    }
    /**
    产生盐值字符串salt
    */
    string EncryptUtil::createSalt()
    {
    	//随机生成两个随机数
    	int num1 = rand() % 99999999;
    	int num2 = rand() % 99999999;
    	string salt = "";
    	//将这两个随机数转换为字符串后追加到salt中
    	salt.append(to_string(num1));
    	salt.append(to_string(num2));
    	//salt不够十六位就在后面加0
    	int len = salt.size();
    	if (len < 16) {
    		for (int i = 0; i < 16 - len; i++) {
    			salt.append("0");
    		}
    	}
    	//cout << "产生的盐值字符串为:" <<salt<< endl;
    	return salt;
    }
    
    /**
    * 加盐MD5
    * @param text : 需要进行加盐后摘要的text明文
    * @return string:返回进行摘要算法后的字符串
    */
    string EncryptUtil::encryptBySalt(const string& text) {
    	//产生盐值字符串salt
    	string salt = createSalt();
    	//将产生的salt追加到需要进行摘要的明文text中,得到由明文text和salt组成的字符串
    	string merge_str =  text + salt;
    	//使用md5算法进行摘要计算得到相应的32位的密文
    	string encodeText = md5Hex(merge_str);
    	char cs [48];
    	//将32位的密文和产生的16位的salt进行重组形成新的48位的字符串。
    	//这里表示,在新的字符数组cs中,salt中的字符添加到cs字符数组中位置是i*3+1的位置,其它位置由摘要密文encodeText中的字符填充
    	for (int i = 0; i < 48; i += 3) {
    		cs[i] = encodeText[i / 3 * 2];
    		char c = salt[i / 3];
    		cs[i + 1] = c;
    		cs[i + 2] = encodeText[i / 3 * 2 + 1];
    	}
    	//将组合成的cs字符数组转化为字符串得到48位的加盐后形成的md5摘要密文
    	string code = "";
    	for (int i = 0; i < 48; i++)
    	{
    	  code.append(1,cs[i]);
    	}
    	return code;
    }
    /**
     * 获取十六进制字符串形式的MD5摘要
     * @param text: 需要进行摘要算法的明文
     * @return string: 返回进行普通md5摘要后的字符串
     */
    string EncryptUtil::md5Hex(const string& text) {
    	//首先更新md5中需要进行摘要的字符串
    	this->md5->update(text);
    	//使用md5的方法生成对应的摘要后的字符串
    	return this->md5->toString();
    
    }
    /**
     * 校验加盐后是否和原文一致
     * @param text : 进行摘要算法的明文
     * @param encryptText  : 进行加盐摘要算法后的密文
     * @return 如果加盐后和原明文text一致则返回true,否则返回false
     */
     bool EncryptUtil::verify( string text,  string encryptText) {
    	char md5Text[32];
    	char salt[16];
    	//首先将加盐后md5算法摘要得到的encryptText密文进行拆分成一个32位的普通md5摘要算法密文md5Text和一个16位的字符串salt。
    	//这里就是进行salt和md5摘要密文形成48位新的字符串encryptText时的逆向操作。encryptText中salt[i] =  encryptText[ 3* i + 1], i = 0,1,2,...16
    	for (int i = 0; i < 48; i += 3) {
    		md5Text[i / 3 * 2] = encryptText[i];
    		md5Text[i / 3 * 2 + 1] = encryptText[i + 2];
    		salt[i / 3] = encryptText[i + 1];
    	}
    	//将拆分的16个随机字符串追salt加到明文text中
    	for (int  i = 0; i < 16; i++)
    	{
    		text.append(1,salt[i]);
    	}
    	//使用md5摘要算法进行生成密文得到enCs2
    	string enCs2 = md5Hex(text);
    	//比较两个字符串相等,如果相等则返回true,只要有一个字符不相等就返回false
    	for (int i = 0; i < enCs2.size(); i++)
    	{
    		if (enCs2[i] != md5Text[i])
    		{
    			return false;
    		}
    	}
    	return true;
    }
     /**
      逐个比较两个密文相同位置上字符是否相同来计算两个明文进行md5加密后的相似度。
     @param str1: md5摘要算法后的字符串
     @param str2:md5摘要算法后的字符串
     @return double: 返回相似度
     */
    double EncryptUtil::similarityDegree(const string& str1, const string& str2)
    {
    	if (str1.size() <= 0 && (str1.size() != str2.size()))
    	{
    		return 0;
    	}
    	int count = 0;
    	//统计对应位置上字符相同的个数
    	for (int i = 0; i < str1.size(); i++)
    	{
    		if (str1[i] == str2[i])
    		{
    			count++;
    		}
    	}
    	//计算相似度
    	double result = count * 1.0 / str1.size();
    	return result;
    }
    
     
    
    EncryptUtil::~EncryptUtil()
    {
    }
    
    
    #pragma once
    #ifndef MD5_H
    #define MD5_H
    #include <string>
    #include <fstream>
    using namespace std;
    /* Type define */
    typedef unsigned char byte;
    typedef unsigned int uint32;
    
    
    
    /* MD5 declaration. */
    class MD5 {
    public:
    	MD5();
    	MD5(const void *input, size_t length);
    	MD5(const string &str);
    	MD5(ifstream &in);
    	void update(const void *input, size_t length);
    	void update(const string &str);
    	void update(ifstream &in);
    	const byte* digest();
    	string toString();
    	
    private:
    	void reset();
    	void update(const byte *input, size_t length);
    	void final();
    	void transform(const byte block[64]);
    	void encode(const uint32 *input, byte *output, size_t length);
    	void decode(const byte *input, uint32 *output, size_t length);
    	string bytesToHexString(const byte *input, size_t length);
    	/* class uncopyable */
    	MD5(const MD5&);
    	MD5& operator=(const MD5&);
    private:
    	uint32 _state[4];	/* state (ABCD) */
    	uint32 _count[2];	/* number of bits, modulo 2^64 (low-order word first) */
    	byte _buffer[64];	/* input buffer */
    	byte _digest[16];	/* message digest */
    	bool _finished;		/* calculate finished ? */
    	static const byte PADDING[64];	/* padding for calculate */
    	static const char HEX[16];
    	static const size_t BUFFER_SIZE = 1024;
    };
    
    #endif/*MD5_H*/
    
    #include "md5.h"
    
    
    
    /* Constants for MD5Transform routine. */
    #define S11 7
    #define S12 12
    #define S13 17
    #define S14 22
    #define S21 5
    #define S22 9
    #define S23 14
    #define S24 20
    #define S31 4
    #define S32 11
    #define S33 16
    #define S34 23
    #define S41 6
    #define S42 10
    #define S43 15
    #define S44 21
    
    
    /* F, G, H and I are basic MD5 functions.
    */
    #define F(x, y, z) (((x) & (y)) | ((~x) & (z)))
    #define G(x, y, z) (((x) & (z)) | ((y) & (~z)))
    #define H(x, y, z) ((x) ^ (y) ^ (z))
    #define I(x, y, z) ((y) ^ ((x) | (~z)))
    
    /* ROTATE_LEFT rotates x left n bits.
    */
    #define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n))))
    
    /* FF, GG, HH, and II transformations for rounds 1, 2, 3, and 4.
    Rotation is separate from addition to prevent recomputation.
    */
    #define FF(a, b, c, d, x, s, ac) { \
    	(a) += F ((b), (c), (d)) + (x) + ac; \
    	(a) = ROTATE_LEFT ((a), (s)); \
    	(a) += (b); \
    }
    #define GG(a, b, c, d, x, s, ac) { \
    	(a) += G ((b), (c), (d)) + (x) + ac; \
    	(a) = ROTATE_LEFT ((a), (s)); \
    	(a) += (b); \
    }
    #define HH(a, b, c, d, x, s, ac) { \
    	(a) += H ((b), (c), (d)) + (x) + ac; \
    	(a) = ROTATE_LEFT ((a), (s)); \
    	(a) += (b); \
    }
    #define II(a, b, c, d, x, s, ac) { \
    	(a) += I ((b), (c), (d)) + (x) + ac; \
    	(a) = ROTATE_LEFT ((a), (s)); \
    	(a) += (b); \
    }
    const byte MD5::PADDING[64] = { 0x80 };
    const char MD5::HEX[16] = {
    	'0', '1', '2', '3',
    	'4', '5', '6', '7',
    	'8', '9', 'a', 'b',
    	'c', 'd', 'e', 'f'
    };
    
    /* Default construct. */
    MD5::MD5() {
    	reset();
    }
    
    /* Construct a MD5 object with a input buffer. */
    MD5::MD5(const void *input, size_t length) {
    	reset();
    	update(input, length);
    }
    
    /* Construct a MD5 object with a string. */
    MD5::MD5(const string &str) {
    	reset();
    	update(str);
    }
    
    /* Construct a MD5 object with a file. */
    MD5::MD5(ifstream &in) {
    	reset();
    	update(in);
    }
    
    /* Return the message-digest */
    const byte* MD5::digest() {
    	if (!_finished) {
    		_finished = true;
    		final();
    	}
    	return _digest;
    }
    
    /* Reset the calculate state */
    void MD5::reset() {
    
    	_finished = false;
    	/* reset number of bits. */
    	_count[0] = _count[1] = 0;
    	/* Load magic initialization constants. */
    	_state[0] = 0x67452301;
    	_state[1] = 0xefcdab89;
    	_state[2] = 0x98badcfe;
    	_state[3] = 0x10325476;
    	
    }
    
    /* Updating the context with a input buffer. */
    void MD5::update(const void *input, size_t length) {
    	update((const byte*)input, length);
    }
    
    /* Updating the context with a string. */
    void MD5::update(const string &str) {
    	update((const byte*)str.c_str(), str.length());
    }
    
    /* Updating the context with a file. */
    void MD5::update(ifstream &in) {
    
    	if (!in)
    		return;
    
    	std::streamsize length;
    	char buffer[BUFFER_SIZE];
    	while (!in.eof()) {
    		in.read(buffer, BUFFER_SIZE);
    		length = in.gcount();
    		if (length > 0)
    			update(buffer, length);
    	}
    	in.close();
    }
    
    /* MD5 block update operation. Continues an MD5 message-digest
    operation, processing another message block, and updating the
    context.
    */
    void MD5::update(const byte *input, size_t length) {
    
    	uint32 i, index, partLen;
    
    	//_finished = false;
    	this->reset();
    	/* Compute number of bytes mod 64 */
    	index = (uint32)((_count[0] >> 3) & 0x3f);
    
    	/* update number of bits */
    	if ((_count[0] += ((uint32)length << 3)) < ((uint32)length << 3))
    		_count[1]++;
    	_count[1] += ((uint32)length >> 29);
    
    	partLen = 64 - index;
    
    	/* transform as many times as possible. */
    	if (length >= partLen) {
    
    		memcpy(&_buffer[index], input, partLen);
    		transform(_buffer);
    
    		for (i = partLen; i + 63 < length; i += 64)
    			transform(&input[i]);
    		index = 0;
    
    	}
    	else {
    		i = 0;
    	}
    
    	/* Buffer remaining input */
    	memcpy(&_buffer[index], &input[i], length - i);
    }
    
    /* MD5 finalization. Ends an MD5 message-_digest operation, writing the
    the message _digest and zeroizing the context.
    */
    void MD5::final() {
    
    	byte bits[8];
    	uint32 oldState[4];
    	uint32 oldCount[2];
    	uint32 index, padLen;
    
    	/* Save current state and count. */
    	memcpy(oldState, _state, 16);
    	memcpy(oldCount, _count, 8);
    
    	/* Save number of bits */
    	encode(_count, bits, 8);
    
    	/* Pad out to 56 mod 64. */
    	index = (uint32)((_count[0] >> 3) & 0x3f);
    	padLen = (index < 56) ? (56 - index) : (120 - index);
    	update(PADDING, padLen);
    
    	/* Append length (before padding) */
    	update(bits, 8);
    
    	/* Store state in digest */
    	encode(_state, _digest, 16);
    
    	/* Restore current state and count. */
    	memcpy(_state, oldState, 16);
    	memcpy(_count, oldCount, 8);
    }
    
    /* MD5 basic transformation. Transforms _state based on block. */
    void MD5::transform(const byte block[64]) {
    
    	uint32 a = _state[0], b = _state[1], c = _state[2], d = _state[3], x[16];
    
    	decode(block, x, 64);
    
    	/* Round 1 */
    	FF(a, b, c, d, x[0], S11, 0xd76aa478); /* 1 */
    	FF(d, a, b, c, x[1], S12, 0xe8c7b756); /* 2 */
    	FF(c, d, a, b, x[2], S13, 0x242070db); /* 3 */
    	FF(b, c, d, a, x[3], S14, 0xc1bdceee); /* 4 */
    	FF(a, b, c, d, x[4], S11, 0xf57c0faf); /* 5 */
    	FF(d, a, b, c, x[5], S12, 0x4787c62a); /* 6 */
    	FF(c, d, a, b, x[6], S13, 0xa8304613); /* 7 */
    	FF(b, c, d, a, x[7], S14, 0xfd469501); /* 8 */
    	FF(a, b, c, d, x[8], S11, 0x698098d8); /* 9 */
    	FF(d, a, b, c, x[9], S12, 0x8b44f7af); /* 10 */
    	FF(c, d, a, b, x[10], S13, 0xffff5bb1); /* 11 */
    	FF(b, c, d, a, x[11], S14, 0x895cd7be); /* 12 */
    	FF(a, b, c, d, x[12], S11, 0x6b901122); /* 13 */
    	FF(d, a, b, c, x[13], S12, 0xfd987193); /* 14 */
    	FF(c, d, a, b, x[14], S13, 0xa679438e); /* 15 */
    	FF(b, c, d, a, x[15], S14, 0x49b40821); /* 16 */
    
    	/* Round 2 */
    	GG(a, b, c, d, x[1], S21, 0xf61e2562); /* 17 */
    	GG(d, a, b, c, x[6], S22, 0xc040b340); /* 18 */
    	GG(c, d, a, b, x[11], S23, 0x265e5a51); /* 19 */
    	GG(b, c, d, a, x[0], S24, 0xe9b6c7aa); /* 20 */
    	GG(a, b, c, d, x[5], S21, 0xd62f105d); /* 21 */
    	GG(d, a, b, c, x[10], S22, 0x2441453); /* 22 */
    	GG(c, d, a, b, x[15], S23, 0xd8a1e681); /* 23 */
    	GG(b, c, d, a, x[4], S24, 0xe7d3fbc8); /* 24 */
    	GG(a, b, c, d, x[9], S21, 0x21e1cde6); /* 25 */
    	GG(d, a, b, c, x[14], S22, 0xc33707d6); /* 26 */
    	GG(c, d, a, b, x[3], S23, 0xf4d50d87); /* 27 */
    	GG(b, c, d, a, x[8], S24, 0x455a14ed); /* 28 */
    	GG(a, b, c, d, x[13], S21, 0xa9e3e905); /* 29 */
    	GG(d, a, b, c, x[2], S22, 0xfcefa3f8); /* 30 */
    	GG(c, d, a, b, x[7], S23, 0x676f02d9); /* 31 */
    	GG(b, c, d, a, x[12], S24, 0x8d2a4c8a); /* 32 */
    
    	/* Round 3 */
    	HH(a, b, c, d, x[5], S31, 0xfffa3942); /* 33 */
    	HH(d, a, b, c, x[8], S32, 0x8771f681); /* 34 */
    	HH(c, d, a, b, x[11], S33, 0x6d9d6122); /* 35 */
    	HH(b, c, d, a, x[14], S34, 0xfde5380c); /* 36 */
    	HH(a, b, c, d, x[1], S31, 0xa4beea44); /* 37 */
    	HH(d, a, b, c, x[4], S32, 0x4bdecfa9); /* 38 */
    	HH(c, d, a, b, x[7], S33, 0xf6bb4b60); /* 39 */
    	HH(b, c, d, a, x[10], S34, 0xbebfbc70); /* 40 */
    	HH(a, b, c, d, x[13], S31, 0x289b7ec6); /* 41 */
    	HH(d, a, b, c, x[0], S32, 0xeaa127fa); /* 42 */
    	HH(c, d, a, b, x[3], S33, 0xd4ef3085); /* 43 */
    	HH(b, c, d, a, x[6], S34, 0x4881d05); /* 44 */
    	HH(a, b, c, d, x[9], S31, 0xd9d4d039); /* 45 */
    	HH(d, a, b, c, x[12], S32, 0xe6db99e5); /* 46 */
    	HH(c, d, a, b, x[15], S33, 0x1fa27cf8); /* 47 */
    	HH(b, c, d, a, x[2], S34, 0xc4ac5665); /* 48 */
    
    	/* Round 4 */
    	II(a, b, c, d, x[0], S41, 0xf4292244); /* 49 */
    	II(d, a, b, c, x[7], S42, 0x432aff97); /* 50 */
    	II(c, d, a, b, x[14], S43, 0xab9423a7); /* 51 */
    	II(b, c, d, a, x[5], S44, 0xfc93a039); /* 52 */
    	II(a, b, c, d, x[12], S41, 0x655b59c3); /* 53 */
    	II(d, a, b, c, x[3], S42, 0x8f0ccc92); /* 54 */
    	II(c, d, a, b, x[10], S43, 0xffeff47d); /* 55 */
    	II(b, c, d, a, x[1], S44, 0x85845dd1); /* 56 */
    	II(a, b, c, d, x[8], S41, 0x6fa87e4f); /* 57 */
    	II(d, a, b, c, x[15], S42, 0xfe2ce6e0); /* 58 */
    	II(c, d, a, b, x[6], S43, 0xa3014314); /* 59 */
    	II(b, c, d, a, x[13], S44, 0x4e0811a1); /* 60 */
    	II(a, b, c, d, x[4], S41, 0xf7537e82); /* 61 */
    	II(d, a, b, c, x[11], S42, 0xbd3af235); /* 62 */
    	II(c, d, a, b, x[2], S43, 0x2ad7d2bb); /* 63 */
    	II(b, c, d, a, x[9], S44, 0xeb86d391); /* 64 */
    
    	_state[0] += a;
    	_state[1] += b;
    	_state[2] += c;
    	_state[3] += d;
    }
    
    /* Encodes input (ulong) into output (byte). Assumes length is
    a multiple of 4.
    */
    void MD5::encode(const uint32 *input, byte *output, size_t length) {
    
    	for (size_t i = 0, j = 0; j < length; i++, j += 4) {
    		output[j] = (byte)(input[i] & 0xff);
    		output[j + 1] = (byte)((input[i] >> 8) & 0xff);
    		output[j + 2] = (byte)((input[i] >> 16) & 0xff);
    		output[j + 3] = (byte)((input[i] >> 24) & 0xff);
    	}
    }
    
    /* Decodes input (byte) into output (ulong). Assumes length is
    a multiple of 4.
    */
    void MD5::decode(const byte *input, uint32 *output, size_t length) {
    
    	for (size_t i = 0, j = 0; j < length; i++, j += 4) {
    		output[i] = ((uint32)input[j]) | (((uint32)input[j + 1]) << 8) |
    			(((uint32)input[j + 2]) << 16) | (((uint32)input[j + 3]) << 24);
    	}
    }
    
    /* Convert byte array to hex string. */
    string MD5::bytesToHexString(const byte *input, size_t length) {
    	string str;
    	str.reserve(length << 1);
    	for (size_t i = 0; i < length; i++) {
    		int t = input[i];
    		int a = t / 16;
    		int b = t % 16;
    		str.append(1, HEX[a]);
    		str.append(1, HEX[b]);
    	}
    	return str;
    }
    
    MD5 & MD5::operator=(const MD5 &)
    {
    	return *this;
    }
    
    /* Convert digest to string value */
    string MD5::toString() {
    	return bytesToHexString(digest(), 16);
    }
    

    测试文件

    #include<iostream>
    #include"Md5.h"
    #include<string>
    #include<fstream>
    #include"EncryptUtil.h"
    #include<time.h>
    #include<vector>
    using namespace std;
     
    string loadTextToString(const string textFilePath) {
    	ifstream* ism = new ifstream(textFilePath,ios::app|ios::binary);
    	if (ism->is_open())
    	{
    		
    		string text = "";
    		char ch;
    		while (!ism->eof())
    		{
    			ism->get(ch);
    			text.append(1,ch);
    		}
    		return text;
    	}
    	else {
    		cout << "打开文件失败!" << endl;
    		return "";
    	}
    }
    
    void test2() {
    	
    	
    }
    void test1() {
    	string text = loadTextToString("hashtext.txt");
    	MD5 md5(text);
    	cout << md5.toString();
    }
    void test3() {
    	string s = "11";
    	s.append(to_string(121));
    	cout << s;
    }
    void test4() {
    	string text = loadTextToString("hashtext.txt");
    	EncryptUtil util;
    	string str = util.md5Decode(text);
    	cout << "\n普通加密后的md5值:" + str << endl;
    	cout << "普通加密后的md5值:" + util.md5Decode(text) << endl;
    	string encodeText =util.encryptBySalt(text);
    	string encodeText1 = util.encryptBySalt(text);
    	cout << "md5加盐后加密的md5值:" + encodeText << endl;
    	cout << "md5加盐后加密的md5值:" + encodeText1 << endl;
    	if (encodeText.compare(encodeText1) == 0)
    	{
    		cout << "两次生成的加盐秘钥相等!" << endl;
    	}
    	else {
    		cout << "两次生成的加盐秘钥不相等!" << endl;
    	}
    	bool fla = util.verify(text,encodeText);
    	if (fla == true)
    	{
    		cout << "相等!"<<endl;
    	}
    	else {
    		cout << "不相等" << endl;
    	}
    
    }
    void test5() {
    	string text = loadTextToString("hashtext.txt");
    	cout << endl;
    
    }
    void test6() {
    	srand(time(NULL));
    	cout << rand() % 99999999 <<"  "<<  rand()% 99999999 <<endl;
    	cout << rand() % 99999999 << "  " << rand() % 99999999 << endl;
    }
    void test7() {
    	string text = loadTextToString("hashtext.txt");
    	cout << "需要加密的明文为:\n" << text<<endl;
    	EncryptUtil util;
    	string encodeText = util.encryptBySalt(text);
    	cout << "md5加盐后加密的md5值:" + encodeText << endl;
    	
    
    }
    string randomReplace(string text,int index,string replaceChar) {
    
    	
    	
    	return text.replace(index,1,replaceChar);
    }
    void test() {
    	string text = loadTextToString("hashtext.txt");
    	cout << "需要加密的明文为:\n" << text << endl;
    	EncryptUtil util;
    	string md0 = util.encryptBySalt(text);
    	cout << "md5加盐后加密的md5值H0:" + md0 << endl;
    	vector<string> vec;
    	for (int i = 0; i < 10; i++)
    	{
    		//替换十个字符,每个原来的字符+1
    		string  newStr =	randomReplace(text, i * 5,string(1, text[i * 5] + 1));
    		//计算每个替换后字符的hash值
    		 string encodeText =util.encryptBySalt(newStr);
    		vec.push_back(encodeText);
    	}
    	for (size_t i = 0; i < 10; i++)
    	{
    		cout << "md5加盐后加密的md5值H"+ to_string(i + 1) + ":" + vec[i]<< endl;
    	}
    	for (size_t i = 0; i < 10; i++)
    	{
    		//计算H0和H的相似度
    		cout << "H0和H" + to_string(i + 1) + "的相似度:" + to_string(util.similarityDegree(md0, vec[i])) << endl;
    	}
    }
    void test8() {
    	string text = loadTextToString("hashtext.txt");
    	cout << "需要加密的明文为:\n" << text << endl;
    	EncryptUtil util;
    	string md0 = util.encryptBySalt(text);
    	cout << "md5加盐后加密的md5值H0:" + md0 << endl;
    	string text1 = 	text.replace(10,1,"a");
    	string md1 = util.encryptBySalt(text1);
    	cout << "md5加盐后加密的md5值H1:" + md1 << endl;
    	cout << "md0和md1相似度:" << util.similarityDegree(md0,md1)<<endl;
    
    }
    void test9() {
    	string text = loadTextToString("hashtext.txt");
    	EncryptUtil util;
    	string encodeText = util.encryptBySalt(text);
    	string encodeText1 = util.encryptBySalt(text);
    	cout << "md5加盐后加密的md5值:" + encodeText << endl;
    	cout << "md5加盐后加密的md5值:" + encodeText1 << endl;
    	if (encodeText.compare(encodeText1) == 0)
    	{
    		cout << "两次生成的加盐密文相等!" << endl;
    	}
    	else {
    		cout << "两次生成的加盐密文不相等!" << endl;
    	}
    	bool fla = util.verify(text, encodeText);
    	if (fla == true)
    	{
    		cout << "原来的明文和加盐后的明文一致得到验证!" << endl;
    	}
    	else {
    		cout << "原来的明文和加盐后的明文不一致!" << endl;
    	}
    
    }
    int main() {
    	// test8();
    	
    		
    	test9();
    	system("pause");
    	return 0;
    }
    

    8.看完记得点赞哦,笔记整理不易。

    9.本博客已经同步到个人博客,如有需要请移步:http://moyisuiying.com/index.php/cppstudy/information-secure/433.html

    展开全文
  • 赵润晓,男,1995年生,本科,E-mail:578562554@ 第1作者手机号码:180,E-mail:578562554@ 散列算法和Hash 函数 赵润晓1 1(华中科技大学物理学院 应用物理学1401班,武汉市中国430074 摘要中本文介绍了散列算法和Hash 函数...
  • Hash函数

    2019-10-09 10:08:17
    Hash函数 概念 将任意长度的输入变换为固定长度的输出的不可逆的单向密码体制 Hash函数在数字签名和消息完整性检测等方面有着广泛的应用 Hash函数同时是一种具有压缩特性的单向函数,其像通常称为数字指纹,消息...

    Hash函数

    概念

    将任意长度的输入变换为固定长度的输出的不可逆的单向密码体制

    Hash函数在数字签名和消息完整性检测等方面有着广泛的应用

    Hash函数同时是一种具有压缩特性的单向函数,其像通常称为数字指纹,消息摘要或散列值。

    散列值的生成过程可以表示为

    h = H(M)

    其中h是定长的散列值,H是哈希函数,M是一个变长消息

    散列函数主要用于消息认证和数字签名,因此需要具备以下特性

    1. H可应用于任意长度的消息
    2. H产生定长的输出
    3. 对任意给定的消息x,计算H(x)比较容易,用硬件软件均可实现
    4. 单向性:对任意给定的散列值h,找到满足H(x) = h 的x在计算上是不可行的
    5. 抗弱碰撞性:对任意给定的消息x,找到x != y并且H(x) = H(y)的消息y在计算上是不可行的
    6. 抗强碰撞性:找到任何满足H(x) = H(y) 的偶对(x,y)在计算上是不可行的

    性质2是哈希函数的基本特性,性质3是哈希函数的可用性,性质4,5,6是哈希函数为满足不同应用而需具备的基本安全性质

    应用

    数字签名

    由于消息散列值通常比消息本身短的多,因此对消息散列值进行数字签名在处理上比对消息本身进行签名要高效的多。

    生成程序或文档的数字指纹

    hash函数可以用来保证消息的完整性。首先,通过哈希函数变换得到程序或文档的散列值,然后将散列值存储,对程序或文档进行定时的检测,与已存储的散列值进行比较,以此来实现完整性验证。

    用于安全传输和用户口令

    用于保存用户登陆口令(密码),通过用户id及口令生成相应的散列值,然后保存,用户在进入系统输入口令时,生成散列值与存储的散列值进行比较,这样可以确保用户口令不被管理员或攻击者获取到


    哈希算法


    消息认证

    消息认证的作用主要有两个:一个是验证信息来源的真实性,一般称之为信息源认证;另一个是验证消息的完整性

    消息认证码(MAC)

    利用消息和双放共享的密钥通过认证函数来生成一个固定长度的短数据块,并将该数据块附加在消息后

    比如发送方A和接收方B共享密钥K,若A向B发送消息M,则MAC = C(K,M) ,其中C是认证函数,MAC是消息认证码

    (a)为明文传输,(b)为先计算MAC后,将MAC数据块附加在M信息后进行加密传输,(c)为先将M进行加密,再生成MAC,并附在消息块后进行传输

    基于哈希的消息认证码

    HMAC是实际应用中使用最多的方案,如SSL就使用HMAC来实现消息认证功能

    展开全文
  • HASH函数 应用Hash函数

    2015-08-14 14:05:06
    HASH函数 应用Hash函数  作者:冲处宇宙 时间:2007.1.25 计算理论中,没有Hash函数的说法,只有单向函数的说法。所谓的单向函数,是一个复杂的定义,大家可以去看计算理论或者...
    HASH函数
     
    
    应用Hash函数 

    作者:冲处宇宙

    时间:2007.1.25

    计算理论中,没有Hash函数的说法,只有单向函数的说法。所谓的单向函数,是一个复杂的定义,大家可以去看计算理论或者密码学方面的数据。用“人类”的语言描述单向函数就是:如果某个函数在给定输入的时候,很容易计算出其结果来;而当给定结果的时候,很难计算出输入来,这就是单项函数。各种加密函数都可以被认为是单向函数的逼近。Hash函数(或者成为散列函数)也可以看成是单向函数的一个逼近。即它接近于满足单向函数的定义。

    Hash函数还有另外的含义。实际中的Hash函数是指把一个大范围映射到一个小范围。把大范围映射到一个小范围的目的往往是为了节省空间,使得数据容易保存。除此以外,Hash函数往往应用于查找上。所以,在考虑使用Hash函数之前,需要明白它的几个限制:

    1. Hash的主要原理就是把大范围映射到小范围;所以,你输入的实际值的个数必须和小范围相当或者比它更小。不然冲突就会很多。
    2. 由于Hash逼近单向函数;所以,你可以用它来对数据进行加密。
    3. 不同的应用对Hash函数有着不同的要求;比如,用于加密的Hash函数主要考虑它和单项函数的差距,而用于查找的Hash函数主要考虑它映射到小范围的冲突率。

    应用于加密的Hash函数已经探讨过太多了,在作者的博客里面有更详细的介绍。所以,本文只探讨用于查找的Hash函数。

    Hash函数应用的主要对象是数组(比如,字符串),而其目标一般是一个int类型。以下我们都按照这种方式来说明。

    一般的说,Hash函数可以简单的划分为如下几类:
    1. 加法Hash;
    2. 位运算Hash;
    3. 乘法Hash;
    4. 除法Hash;
    5. 查表Hash;
    6. 混合Hash;
    下面详细的介绍以上各种方式在实际中的运用。
    一 加法Hash

    所谓的加法Hash就是把输入元素一个一个的加起来构成最后的结果。标准的加法Hash的构造如下:

    static int additiveHash(String key, int prime)
    {
    int hash, i;
    for (hash = key.length(), i = 0; i < key.length(); i++)
    hash += key.charAt(i);
    return (hash % prime);
    }
    这里的prime是任意的质数,看得出,结果的值域为[0,prime-1]。
    二 位运算Hash

    这类型Hash函数通过利用各种位运算(常见的是移位和异或)来充分的混合输入元素。比如,标准的旋转Hash的构造如下:

    static int rotatingHash(String key, int prime)
    {
    int hash, i;
    for (hash=key.length(), i=0; i<key.length(); ++i)
    hash = (hash<<4)^(hash>>28)^key.charAt(i);
    return (hash % prime);
    }

    先移位,然后再进行各种位运算是这种类型Hash函数的主要特点。比如,以上的那段计算hash的代码还可以有如下几种变形:
    1. hash = (hash<<5)^(hash>>27)^key.charAt(i);
    2. hash += key.charAt(i);
    hash += (hash << 10);
    hash ^= (hash >> 6);
    3. if((i&1) == 0)
    {
    hash ^= (hash<<7) ^ key.charAt(i) ^ (hash>>3);
    }
    else
    {
    hash ^= ~((hash<<11) ^ key.charAt(i) ^ (hash >>5));
    }
    4. hash += (hash<<5) + key.charAt(i);
    5. hash = key.charAt(i) + (hash<<6) + (hash>>16) – hash;
    6. hash ^= ((hash<<5) + key.charAt(i) + (hash>>2));
    三 乘法Hash

    这种类型的Hash函数利用了乘法的不相关性(乘法的这种性质,最有名的莫过于平方取头尾的随机数生成算法,虽然这种算法效果并不好)。比如,

    static int bernstein(String key)
    {
    int hash = 0;
    int i;
    for (i=0; i<key.length(); ++i) hash = 33*hash + key.charAt(i);
    return hash;
    }

    jdk5.0里面的String类的hashCode()方法也使用乘法Hash。不过,它使用的乘数是31。推荐的乘数还有:131, 1313, 13131, 131313等等。

    使用这种方式的著名Hash函数还有:
    // 32位FNV算法
    int M_SHIFT = 0;
    public int FNVHash(byte[] data)
    {
    int hash = (int)2166136261L;
    for(byte b : data)
    hash = (hash * 16777619) ^ b;
    if (M_SHIFT == 0)
    return hash;
    return (hash ^ (hash >> M_SHIFT)) & M_MASK;
    }

    以及改进的FNV算法:
    public static int FNVHash1(String data)
    {
    final int p = 16777619;
    int hash = (int)2166136261L;
    for(int i=0;i<data.length();i++)
    hash = (hash ^ data.charAt(i)) * p;
    hash += hash << 13;
    hash ^= hash >> 7;
    hash += hash << 3;
    hash ^= hash >> 17;
    hash += hash << 5;
    return hash;
    }

    除了乘以一个固定的数,常见的还有乘以一个不断改变的数,比如:
    static int RSHash(String str)
    {
    int b = 378551;
    int a = 63689;
    int hash = 0;

    for(int i = 0; i < str.length(); i++)
    {
    hash = hash * a + str.charAt(i);
    a = a * b;
    }
    return (hash & 0x7FFFFFFF);
    }

    虽然Adler32算法的应用没有CRC32广泛,不过,它可能是乘法Hash里面最有名的一个了。关于它的介绍,大家可以去看RFC 1950规范。
    四 除法Hash

    除法和乘法一样,同样具有表面上看起来的不相关性。不过,因为除法太慢,这种方式几乎找不到真正的应用。需要注意的是,我们在前面看到的hash的结果除以一个prime的目的只是为了保证结果的范围。如果你不需要它限制一个范围的话,可以使用如下的代码替代”hash%prime”: hash = hash ^ (hash>>10) ^ (hash>>20)。
    五 查表Hash

    查表Hash最有名的例子莫过于CRC系列算法。虽然CRC系列算法本身并不是查表,但是,查表是它的一种最快的实现方式。下面是CRC32的实现:

    static int crctab[256] = {
    0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f, 0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988, 0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, 0x1db71064, 0x6ab020f2, 0xf3b97148, 0x84be41de, 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7, 0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9, 0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172, 0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, 0x35b5a8fa, 0x42b2986c, 0xdbbbc9d6, 0xacbcf940, 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59, 0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423, 0xcfba9599, 0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924, 0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190, 0x01db7106, 0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433, 0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d, 0x91646c97, 0xe6635c01, 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e, 0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950, 0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65, 0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7, 0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0, 0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa, 0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f, 0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81, 0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a, 0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, 0xe3630b12, 0x94643b84, 0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1, 0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb,
    0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc, 0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, 0xd6d6a3e8, 0xa1d1937e, 0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b, 0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55, 0x316e8eef, 0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236, 0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe, 0xb2bd0b28, 0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d, 0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, 0x9c0906a9, 0xeb0e363f, 0x72076785, 0x05005713, 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38, 0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242, 0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777, 0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69, 0x616bffd3, 0x166ccf45, 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2, 0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc, 0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9, 0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693, 0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94, 0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d
    };
    int crc32(String key, int hash)
    {
    int i;
    for (hash=key.length(), i=0; i<key.length(); ++i)
    hash = (hash >> 8) ^ crctab[(hash & 0xff) ^ k.charAt(i)];
    return hash;
    }

    查表Hash中有名的例子有:Universal Hashing和Zobrist Hashing。他们的表格都是随机生成的。
    六 混合Hash

    混合Hash算法利用了以上各种方式。各种常见的Hash算法,比如MD5、Tiger都属于这个范围。它们一般很少在面向查找的Hash函数里面使用。
    七 对Hash算法的评价

    http://www.burtleburtle.net/bob/hash/doobs.html 这个页面提供了对几种流行Hash算法的评价。我们对Hash函数的建议如下:

    1. 字符串的Hash。最简单可以使用基本的乘法Hash,当乘数为33时,对于英文单词有很好的散列效果(小于6个的小写形式可以保证没有冲突)。复杂一点可以使用FNV算法(及其改进形式),它对于比较长的字符串,在速度和效果上都不错。

    2. 长数组的Hash。可以使用http://burtleburtle.net/bob/c/lookup3.c这种算法,它一次运算多个字节,速度还算不错。
    展开全文
  • 信息安全概论:Hash函数概念与性质

    千次阅读 2020-04-02 18:20:39
    Hash函数可以将“任意长度“的输入经过变换以后得到固定长度的输出,也称为消息摘要。 消息摘要能有用于完成消息的认证功能,消息认证是保证信息完整性的重要措施。 Hash函数也成散列函数、哈希函数、杂凑函数等,是...

    信息安全除了要保障信息的机密性外,还要保障信息在存储、使用、传输过程中不被非法篡改,即信息的完整性。
    Hash函数可以将“任意长度“的输入经过变换以后得到固定长度的输出,也称为消息摘要。
    消息摘要能有用于完成消息的认证功能,消息认证是保证信息完整性的重要措施。
    Hash函数也成散列函数、哈希函数、杂凑函数等,是密码学的一个重要分支,Hash函数可以看做是一种单向密码体制,即它是从一个明文到密文的不可逆映射,即只有加密过程,不能解密。

    Hash函数的基本概念
    Hash函数的单向特征和输出数据长度固定的特征使得它可以生成消息或其他数据块的“数据指纹”(消息摘要或hash值),用于消息认证和数字签名等区域。
    hash值的生成过程可以表示为h=H(M),其中M是“任意”长度的消息,H是hash函数,h是固定长度的hash值。

    • H可以用于“任意”长度的消息,“任意”是指实际存在的
    • H产生的hash值是固定长度的,这是hash函数的基本性质
    • 对于任意给定的消息M,容易计算H(M)值,这是要求hash函数的可用性。

    Hash函数的性质

    • 抗第一原像(单向性):对于给定的hash值h,要找到M使得H(M)=h在计算上是不可行的
    • 抗第二原像(抗弱碰撞性):对于给定的消息M1,要发现另一个消息M2,满足H(M1)=H(M2)在计算上是不可行的
    • 抗强碰撞性:找任意一对不同消息M1、M2,使H(M1)=H(M2)在计算上是不可行的

    消息对应hash值的每一比特应与消息的每一个比特有关联
    当消息原文发生改变时,求得的消息摘要必须相应的变化

    hash函数结构
    hash函数的设计主要分为两类:

    • 基于加密体制实现,例如使用对称分组密码算法的CBC模式来产生hash值
    • 直接构造复杂的非线性关系实现单向性,是目前使用较多的设计方法

    典型的hash算法中著名的是MD系列和SHA系列

    消息认证技术

    • 消息认证的目的主要包括:验证信息来源的真实性和验证消息的完整性
      消息认证码是一种重要的消息认证技术,利用消息和双方共享密钥通过认证函数来生成一个固定长度的短数据块,并将该数据块附在消息后
    • 消息认证码是与密钥相关的hash函数,也称消息鉴别码
      消息认证码与hash函数类似,都具有单向性,此外消息认证码还包括一个密钥
      不同的密钥会产生不同的hash函数,这样就能在验证消息没有经过篡改的同时,验证是由哪个发送者发送的

    消息认证码的实现过程
    在这里插入图片描述

    由于消息在发送过程中是明文形式,所以只提供认证性而未提供保密性
    提供保密性可在生成MAC之后或之前进行一次加密,而且加密密钥也需被收发双方共享
    通常希望直接对明文进行认证,因此先计算MAC再加密的使用方式更为常用
    MAC算法与加密算法类似,不同之处是MAC不必是可逆的,因此与加密算法相比更不易被攻破

    生成消息认证码的方法主要包括:基于加密函数的认证码和基于hash的认证码

    展开全文
  • Hash表、Hash函数和HashCode ** Hash函数和Hash表: Hash函数就是根据key计算出应该存储的位置,而Hash表则是基于Hash函数建立的一种查找表。给定表M,存在函数f(key),对任意给定的关键字值key,代入函数后若能...
  • HASH函数

    2013-12-17 10:10:47
    HASH函数 计算理论中,没有Hash函数的说法,只有单向函数的说法。所谓的单向函数,是一个复杂的定义,大家可以去看计算理论或者密码学方面的数据。用“人类”的语言描述单向函数就是:如果某个函数在给定输入...
  • hash函数

    千次阅读 2007-12-15 11:44:00
    HASH函数
  • Hash函数相关

    2020-03-30 16:55:00
    1.1 hash函数性质 (1)输入域是无穷的,但是输出域是有限的 (2)不是随机产生的输出,相同的输入一定对应相同的输出 (3)不同的输入可能会导致相同的输出(hash碰撞) (4)输出的值在整个输出域几乎是均匀分布...
  • hash函数性质(假设输入空间很大,而且平均分布) 1.抵制碰撞:难以找到不同的输入,映射到同一个输出(但是不代表不会出现)。可防篡改,因为篡改输入,输出改变。 2.隐藏:可用于防泄漏。 3.hash(任意长度的消息)-...
  • Hash 函数

    2015-05-04 14:58:45
    散列表,它时给予快速存取的角度设计的,也是一种典型的“空间换时间”的做法。顾名思义,该数据可以理解为一个线性表,但是其中的元素...这个影色好函数叫做散列函数,存放纪录的数组叫做散列表。 比如我们存储7
  • 应用Hash函数

    2014-03-19 10:43:26
    应用Hash函数  作者:冲处宇宙 时间:2007.1.25 计算理论中,没有Hash函数的说法,只有单向函数的说法。所谓的单向函数,是一个复杂的定义,大家可以去看计算理论或者密码学方面的数据。用“人类”的语言描述...
  • Hash函数及其应用

    2020-06-22 16:38:23
    性质 ... 基本性质 摘要性 输出很短的信息,定长输出 计算容易 适用于任意长度输入(可以将输入分组) ...安全性质 ...MD5 一个hash函数,但被证明不抗碰撞 ...Sha3/sha256现在blockchain中通用的hash函数
  • Hash函数理解

    千次阅读 2017-05-12 20:58:57
    哈希函数Hash)  又称为 散列函数、散列算法、杂凑函数等  是一种单向密码体制:从明文到密文的不可逆映射  可将任意长度的输入变换为固定长度的输出  生成消息的“数据指纹”(也称消息摘要或散列值...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 22,850
精华内容 9,140
关键字:

hash函数性质