第18篇 哈希函数_哈希抗碰撞性两种方法

本文环境：

      操作系统：windows 64；

      node版本：v10.14.0

本文试图解释哈希函数的作用、标准、实现方式以及区块链技术在哪些地方用到了它。

本文中的哈希和hash是同一个词意，有可能会交叉出现。

本文中的哈希有可能是名词（哈希函数、哈希算法），也有可能是动词（把这段数据哈希一下）。

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

 

1.哈希函数的定义

1.1 基本概念

• 明文（plaintext）：原始可理解的信息或数据，作为加密算法的输入。
• 加密（encryption）算法：将明文转换成密文的过程。
• 密钥（key）：加密算法的输入，独立于明文，加密算法根据特定的密钥产生不同的输出。分为加密密钥和解密密钥。
• 密文（ciphertext）：加密算法的输出，看起来是完全随机而杂乱、隐藏了原文含义的数据，依赖于明文和密钥。
• 解密算法（decryption）：本质上是加密算法的逆，输入密文和密钥以恢复出明文。

1.2 哈希函数定义

Hash函数是密码学的一个重要分支，又称为哈希函数、散列函数；它是一种将任意长度的输入变换为固定长度的输出且不可逆的单向密码体制。

用一个简单的等式来表示哈希函数：

碰撞：

1. 理想的hash函数对于不同的输入可以获得不同的hash值。
2. 如果 x 和 y 是两个不同的消息，存在H（x）= H（y），则称 x 和 y 是hash函数H的一个碰撞。

hash函数的特点：

1.  易压缩：对于任意大小的输入x，hash值H（x）的长度很小，且长度固定；
2.  易计算：对于任意给定的消息x，计算其hash值都很容易；
3.  单向性：对于给定的hash值h，要找到x，使得H（x）= h在计算上是不可行的，即求hash的逆很困难；
4.  高灵敏性：这是从比特位角度出发，指的是1比特位的输入变化会造成50%的比特位发生变化。
5.  抗碰撞性：理想的hash函数是无碰撞的，但在实际算法的设计中很难做到这一点。有两种抗碰撞性：

• 弱抗碰撞性：对于给定的消息x，要发现另一个消息y，满足H（x）=H（y）在计算上是不可行的；
• 强抗碰撞性：对于任意不同的消息x和y，使得H（x）=H（y）在计算上也是不可行的。

典型的hash函数有两类：

• 消息摘要算法（MD5，Message-Digest Algorithm）
• 安全散列算法（SHA，Secure Hash Algorithm）

 

2.区块链哪些地方用到了哈希函数

在区块链中，有很多地方用到了哈希函数，本节说明其中三个地方。

2.1 私钥-公钥-地址

在区块链的地址生成过程中，最能体现哈希函数的特性。简述其步骤如下：

步骤1.随机数。随机数用于生成私钥，若随机数可以被预测或重现，则私钥就会立刻形同虚设。

所以保证随机数拥有下列三项特征，至关重要：

1. 随机性：不存在统计学偏差，完全杂乱的数列 ；
2. 不可预测性：不能从过去的数列推测下一个出现的数 ；
3. 不可重现性：除非将数列保存下来，否则不能重现相同的数列。

步骤2.私钥。选择生成私钥的随机数方法时，需要选择满足密码学强度的随机数方法，比如  crypto.randomBytes。当你调用 crypto.randomBytes(32) 方法时，它会等待熵池搜集足够的信息后，返回 64 位的随机数，即私钥。

const privateKey = crypto.randomBytes(32) 
// privateKey.toString('hex'):ea4692a11d962b249f8f0439d642a9013a1a08807649311d3672886d72d1fe51

步骤3.公钥。在非对称加密中，将密钥分为加密密钥和解密密钥，也就是我们常说的公钥和私钥。公钥和私钥一一对应，由公钥加密的密文，必须使用公钥配对的私钥才可以解密。

当我们调用 secp256k1.publicKeyCreate 获得公钥时，实际使用的是非对称加密中的椭圆曲线算法。通过该算法可以从私钥推导出公钥，这是一个不可逆的过程：K = k * G。给出常数点 G 时，使用已知私钥 k 求公钥 K 的问题并不困难，但反过来，已知公钥 K 求私钥 k，则非常困难。这就是椭圆曲线算法上的离散对数问题，也是为什么你可以分享地址（或公钥）给别人，但不能暴露自己的私钥。

const publicKey = secp256k1.publicKeyCreate(privateKey, false).slice(1) 
// publicKey.toString('hex'): 1e3f1532e3285b02...45d91a36a8d78cb6bef8

libsecp256k1，它是一个第三方C++库，在比特币代码(github_bitcoin)中就有应用，被视为一个经过优化的，针对椭圆曲线secp256k1的一个实现库。secp256k1对应于一组特定的椭圆曲线数字签名参数，包括曲线方程以及签名运算所需的一系列参数等，在比特币中，其所指定的曲线方程为y^2 = x^3 + 7。

步骤4.地址。当我们调用 createKeccakHash("keccak256") 方法时，Keccak 使用散列函数，对公钥与初始的内部状态做 XOR 运算得到 32 字节哈希值，取其后 20 字节，转成 40 位的 16 进制字符，即为地址。

const address = createKeccakHash("keccak256").update(publicKey).digest().slice(-20) 
// address.toString("hex"): 7a48ac1bf3943b2ca7a4ca4999cbcbb0e999950c

以上步骤，全部不可逆。也就是说，通过地址推导公钥，通过公钥推导私钥，在计算上都是不可能的。

2.2 实现示例

用户怎么实现2.1的过程，简单引用代码如下：

//run 'npm install eth-crypto --save'
const EthCrypto = require('eth-crypto');
 
const identity = EthCrypto.createIdentity();
 
//可以直接显示私钥、公钥和地址
console.log('privateKey:'+identity.privateKey);
console.log('publicKey: '+identity.publicKey);
console.log('address:   '+identity.address);
 
//从私钥得到公钥
const publicKey = EthCrypto.publicKeyByPrivateKey(identity.privateKey);
console.log(); 
console.log('publicKeyByPrivateKey: '+publicKey); 
 
//从公钥得到地址
const address = EthCrypto.publicKey.toAddress(identity.publicKey);
console.log(); 
console.log('addressByPublicKey: '+address); 

该步骤可以直接得到一套私钥、公钥、账号；也可以从私钥得到公钥；从公钥得到地址；运行后结果：

2.3 其他用到哈希函数的地方

1. 矿工在挖矿的过程中，需要不断计算特定数据的哈希值，这些数据包含了当前交易池中的合法交易，当计算出来的哈希值满足难度要求时，矿工便可以组建完成并广播一个新区块，获得奖励。
2. 在同步区块、接收新区块并验证区块的过程中，根据默克尔树根哈希的值前后是否一致，来判断区块中的交易是否被篡改。

 

3.怎么使用哈希函数

Crypto库是随Nodejs内核一起打包发布的，主要提供了加密、解密、签名、验证等功能。Crypto利用OpenSSL库来实现它的加密技术，它提供OpenSSL中的一系列哈希方法，包括hmac、cipher、decipher、签名和验证等方法的封装。

3.1 打印出支持的hash算法

创建文件hash.js；代码如下：

var crypto = require('crypto');  //加载crypto库
console.log(crypto.getHashes()); //打印支持的hash算法

运行结果如下：

3.2 使用md5算法进行hash计算

创建文件hashMD5.js；代码如下：

var crypto = require('crypto');        //加载crypto库
var content = 'password';              //加密的明文；
var md5 = crypto.createHash('md5');    //定义加密方式:md5，不可逆；
md5.update(content);
var d = md5.digest('hex');             //加密后的值d
console.log("加密的结果："+d);

运行结果如下：

很明显，第3行代码中的md5算法可以替换为3.1运行结果中的任意算法。

3.3 hash算法的比较

从3.1看到，目前支持的Hash算法很多，究竟怎么选择适合。下面用代码比较一下它们的区别：

创建文件hashAlgorithm.js；代码如下：

// Hash算法比较
var crypto = require('crypto');
var fs = require('fs');
 
function hashAlgorithm(algorithm){
    var s1 = new Date();
 
    var filename = "package.json";
    var txt = fs.ReadStream(filename);
 
    var shasum = crypto.createHash(algorithm);
    txt.on('data', function(d) {
        shasum.update(d);
    });
 
    txt.on('end', function() {
        var d = shasum.digest('hex');
        var s2 = new Date();
 
        console.log(algorithm+','+(s2-s1) +'ms,'+ d);
    });
}
 
function doHash(hashs){
    hashs.forEach(function(name){
        hashAlgorithm(name);
    })
}
 
var algs = ['md5','sha1','sha256','sha512','RSA-SHA1','RSA-SHA256','RSA-SHA512'];
 
doHash(algs);

运行结果如下：

输出以逗号分隔，分别是算法名、时间、密文。最常见的md5，密文长度最短，计算时间也最少；sha512密文最长，计算时间也最长。由于md5已经有了大量的字典库，对于安全级别一般的网站建议用sha1；如果安全级别要求很高，CPU配置也很牛，可以考虑用sha512。

也就是说，加密计算时间和编码长度，不同的算法都不尽相同，这个一般作为实际操作中选择算法的依据。

 

4.Hmac算法

HMAC是密钥相关的哈希运算消息认证码（Hash-based Message Authentication Code）。HMAC运算利用哈希算法，以一个密钥和一个消息为输入，生成一个消息摘要作为输出。HMAC可以有效防止一些类似md5的彩虹表等攻击，比如一些常见的密码直接MD5存入数据库的，可能被反向破解。

定义HMAC需要一个加密用散列函数（表示为H，可以是MD5或者SHA-1）和一个密钥K。我们用B来表示数据块的字节数。（以上所提到的散列函数的分割数据块字长B=64），用L来表示散列函数的输出数据字节数（MD5中L=16,SHA-1中L=20）。鉴别密钥的长度可以是小于等于数据块字长的任何正整数值。应用程序中使用的密钥长度若是比B大，则首先用使用散列函数H作用于它，然后用H输出的L长度字符串作为在HMAC中实际使用的密钥。一般情况下，推荐的最小密钥K长度是L个字节。

由于HMAC就是使用散列函数，所以这里选择上面的几种算法进行测试。

4.1 Hmac - sha1加密

新建文件hashHmac.js：

/*********hmac-sha1加密*********/
var crypto = require('crypto');  //加载crypto库
var content = 'password';        //加密的明文；
var token1='miyue';              //加密的密钥；
var buf = crypto.randomBytes(16);
token1 = buf.toString('hex');    //密钥加密；
    console.log("生成的token(用于加密的密钥):"+token1);
var SecrectKey=token1;           //秘钥；
var Signture = crypto.createHmac('sha1', SecrectKey);//定义加密方式
Signture.update(content);
var miwen=Signture.digest().toString('base64');//生成的密文后将再次作为明文再通过pbkdf2算法迭代加密；
console.log("加密的结果："+miwen);
/*********对应的结果(每次生成的结果都不一样)*********/

运行结果如下：

很明显，第9行代码中的sha1算法可以替换为3.1运行结果中的任意算法。

4.2 Hmac算法的比较

新建文件hashHmacAlgorithm.js：

var crypto = require('crypto');
var fs = require('fs');
 
function hmacAlgorithm(algorithm,key){
    var s1 = new Date();
 
    var filename = "package.json";
    var txt = fs.ReadStream(filename);
 
    var shasum = crypto.createHmac(algorithm,key);
    txt.on('data', function(d) {
        shasum.update(d);
    });
 
    txt.on('end', function() {
        var d = shasum.digest('hex');
        var s2 = new Date();
 
        console.log(algorithm+','+(s2-s1) +'ms,'+ d);
    });
}
 
function doHmac(hashs,key){
    console.log("\nKey : %s", key);
    console.log("============================");
    hashs.forEach(function(name){
        hmacAlgorithm(name,key);
    })
}
 
var algs = [ 'md5','sha1','sha256','sha512','RSA-SHA1','RSA-SHA256','RSA-SHA512'];
 
// 短KEY的测试
setTimeout(function(){
    doHmac(algs,"abc");
},1)
 
// 长KEY的测试
setTimeout(function(){
    var key = "jifdkd;adkfaj^&fjdifefdafda,ijjifdkd;adkfaj^&fjdifefdafdaljifdkd;adkfaj^&fjdifefdafda";
    doHmac(algs,key);
},2*1000)

运行结果如下：

输出以逗号分隔，分别是算法名、时间、密文。

通过比对短key和长key，在编码比较长的算法上面会有一些影响。由于Hmac有了第二参数key，所以会比单独的hash加密算法，有更好的安全性上的保证。

主要参考资料：

    1.https://github.com/bsspirit/nodejs-crypto

    2.https://nodejs.org/dist/latest-v4.x/docs/api/crypto.html

    3.http://blog.fens.me/nodejs-crypto/