什么是单向散列函数
- 任意长度数据生成固定长度是散列
- 快速计算
- 消息变化散列变化
- 单向不可逆,抗碰撞
应用场景
- 文件完整性
- 口令加密
- 消息认证
- 伪随机数
- 配合非对称加密做数字签名
- 比特币工作量证明
单向hash抗碰撞
弱抗碰撞
给定X
和hash
值的情况下,找到另外个数,hash
值相同。
强抗碰撞
- 找到散列值相同的两个字符串
-
MD5
,SHA-1
已经被攻破可以找到相同散列值的不同消息
常用的Hash
算法
MD5
SHA1
-
SHA2
(SHA-256
SHA-384
SHA-512
) -
SHA3
Keccak256
选举产生 - 国密
SM3
MD5
算法
- 消息摘要(Message Digest)
- 产生128比特(16字节) 散列值(
RFC1321
) - 强抗碰撞已经被破, 2004年王小云攻破
- 已经不安全, 如果应用加salt
- 历史系统最广泛,效率高
原理
- 补结尾处的字节, 取余448,补
1
后再补0
,补足到448位 - 剩余64位做存储原始数据的长度
- 初始化
MD
缓冲, A: 01 23 45 67,B:89 1b cd ef … - 4个函数处理消息块
Open SSL
实现MD5
#include <iostream>
#include <openssl/md5.h>
using namespace std;
//将二进制转换成16进制的文本字符
string char2Hex(unsigned char *out, int len)
{
const unsigned char hex_chars[] = "0123456789ABCDEF";
string result;
for (int i = 0; i < len; i++)
{
unsigned char ch = out[i];
unsigned int hc = (ch >> 4) & 0xf;
unsigned int lc = ch & 0x0f;
//采用大端存储的方式拼接
result += hex_chars[hc];
result += hex_chars[lc];
}
return result;
}
string MD5Hash(unsigned char *data, size_t len)
{
//初始化MD5环境
MD5_CTX ctx;
MD5_Init(&ctx);
// 计算MD5hash数据
MD5_Update(&ctx, data, len);
//读取数据
unsigned char out[16] = { 0 }; // 只有16个字节
//把数据读取到out中
MD5_Final(out, &ctx);
return char2Hex(out, 16);
}
//采用简化模式实现MD5
string MD5HashSimple(unsigned char* data, size_t len)
{
//读取数据
unsigned char out[16] = { 0 }; // 只有16个字节
//把数据读取到out中
MD5(data, len, out);
return char2Hex(out, 16);
}
int main(int argc, char* argv[])
{
unsigned char data[] = "测试md5数据";
int len = sizeof(data);
string result = MD5Hash(data, len);
cout <<"MD5:"<<result<< endl;
data[0] = '9';
result = MD5HashSimple(data, len);
cout << "MD5:" << result << endl;
}
计算文件的MD5值
string GetFileListHash(string filepath)
{
string hash;
/ 以二进制方式
ifstream ifs(filepath, ios::binary);
if (!ifs)
return hash;
int block_size = 128;
// 文件读取buf
unsigned char buf[1024] = { 0 };
//hash输出
unsigned char out[1024] = { 0 };
while (!ifs.eof())
{
ifs.read((char*)buf, block_size);
int read_size = ifs.gcount();
if (read_size < 0)
{
break;
}
MD5(buf, read_size, out);
hash.insert(hash.end(), out, out + 16);
}
ifs.close();
MD5((unsigned char*)hash.data(), hash.size(), out);
return char2Hex(out, 16);
}
SHA-1
算法
- 安全散列算法(Secure Hash Algorithm)
- 消息摘要(Message Digest)
- 产生160比特(20字节) 散列值
H0
H1
H2
H3
H4
。 - 强抗碰撞已经攻破, 在2005年王小云攻破。
- 和
MD5
一样都是由MD4
导出。
代码演示
代码实现与MD5
类似, 分为三步.
- 初始化
SHA
上下文 - 对数据进行
hash
计算 - 读取
hash
计算结果
代码如下:
string SHA1Hash(unsigned char* data, size_t len)
{
// 首先也是初始化SHA1的上下文
SHA_CTX ctx;
SHA1_Init(&ctx);
// 编码数据
SHA1_Update(&ctx, data, len);
//读取数据
unsigned char out[20];
SHA1_Final(out, &ctx);
//将字节内容转换为字符
return char2Hex(out, 20);
}
同样,为了方便调用,open ssl
对上述过程进行了封装。仅用一个SHA1
函数即可实现以上3步。测试代码如下
//简化函数实现SHA1
string SHA1HashSimple(unsigned char* data, size_t len)
{
unsigned char out[20];
SHA1(data, len, out);
return char2Hex(out, 20);
}
测试:
int main(int argc, char* argv[])
{
// --- 测试MD5
unsigned char data[] = "测试md5数据";
int len = sizeof(data);
// 测试SHA1
string hash = SHA1Hash(data, len);
cout << "SHA1:\t" << hash << endl;
//简介函数测试
hash = SHA1HashSimple(data, len);
cout << "SHA1:\t" << hash << endl;
return 0;
}
运行结果:
使用sha1
测试Merkle Tree
算法文章来源:https://www.uudwc.com/A/k9XxY/
//文件可信树
string GetFileMerkleHash(string filepath)
{
string hash;
// 存放hash列表, 后面所有结果都存在其中
vector<string> hashs;
ifstream ifs(filepath, ios::binary);
if (!ifs)
{
cout << "文件" << filepath << "不存在" << endl;
return hash;
}
unsigned char buf[1024] = { 0 };
unsigned char out[1024] = { 0 };
int block_size = 128;
while (!ifs.eof())
{
ifs.read((char*)buf, block_size);
int read_size = ifs.gcount();
if (read_size <= 0)
{
break;
}
SHA1(buf, read_size, out);
hashs.push_back(string(out, out + 20));
}
while (hashs.size() > 1) // ==1表示已经计算到root节点
{
// 不是二的倍数补节点(二叉树)
if (hashs.size() & 1)
{
hashs.push_back(hashs.back());
}
// 把hash结果的hash结果还吸入到hashs中
for (int i = 0; i < hashs.size() / 2; i++)
{
// 两个节点拼起来, i表示的父节点
string tmp_hash = hashs[i * 2]; // 左节点
tmp_hash += hashs[i * 2 + 1]; // 右节点
SHA1((const unsigned char*)tmp_hash.data(), tmp_hash.size(), out);
// 写入结果
hashs[i] = string(out, out + 20);
}
// hash列表删除上一次多余的hash值
hashs.resize(hashs.size() / 2);
}
if (hashs.size() == 0) return hash;
return char2Hex((unsigned char*)hashs[0].data(), 20);
}
SHA-2
算法
类别 | SHA-1 | SHA-224 | SHA-256 | SHA-384 | SHA-512 |
---|---|---|---|---|---|
消息摘要长度 | 160 | 224 | 256 | 384 | 512 |
消息长度 | 小于 2 64 2^{64} 264位 | 小于 2 64 2^{64} 264位 | 小于 2 64 2^{64} 264位 | 小于 2 128 2^{128} 2128位 | 小于 2 128 2^{128} 2128位 |
分组长度 | 512 | 512 | 512 | 1024 | 1024 |
计算字长度 | 32 | 32 | 32 | 64 | 64 |
计算步骤数 | 80 | 64 | 64 | 80 | 80 |
- 消息填充摸512与448同余补充消息长度。
- 初始化链接变量 缓冲区用8个32位寄存器(
SHA256
) - 取自前8个素数(2、3、5、7、11、13、17、19)的平方根的小数部分其二进制表示的前32位 8 ∗ 32 = 256 8*32=256 8∗32=256.
-
SHA512
是用64位寄存器 - 以512位(64)分组位单位处理, 进行64步循环,
SHA512
以1024(128)位为以个分组 -
SHA-384
和SHA-512
也都有6个迭代函数
string SHA256Hash(const unsigned char* data, size_t len)
{
// 初始化SHA256的上下文
SHA256_CTX ctx;
SHA256_Init(&ctx);
// 开始写入数据
SHA256_Update(&ctx, data, len);
// 读取数据
unsigned char out[32] = {0};
SHA256_Final(out, &ctx);
return char2Hex(out, 32);
}
string SHA256HashSimple(const unsigned char* data, size_t len)
{
unsigned char out[32];
SHA256(data, len, out);
return char2Hex(out, 32);
}
SHA-3
算法
海绵结构, 把数据压到海绵里面。文章来源地址https://www.uudwc.com/A/k9XxY/
- 填充,
- 分组4组
- 与初始值异或