sha256 hash算法的输出是否是均匀的？

5月16日更新

今天偶然想到可以将单线程执行的for循环，拆成多线程来并发执行(在多核处理器上)，用我的CPU(AMD A10 6700 3.7GHz 4核4线程)同样是生成一百万个sha256的散列值，所需的时间如下：

• 单线程：time:26.917543172836304
• 多线程：time:17.500558376312256

所以“将for循环拆为多线程执行提高效率的”这个思路是可行的，因为没有涉及对同一地址空间读写，所以也不用考虑加锁问题。

前言

最近偶然在v2ex看到这个问题，直觉告诉我其输出显然是均匀分布在值域上的，否则就不满足香农的混淆与扩散原则了。但是如何验证这个假设的正确性呢？

验证方法

找了很久，终于通过这篇文章学习到了验证这个假设的方法：算出散列算法结果的信息熵，生成大量散列输出，计算每一位的信息熵，与假设比较。

模拟实验

每一位的信息熵理论值：$$\sum_0^{15} - \frac{1}{16} \log_2 \frac{1}{16} = 4$$

#!/usr/bin/env python3
# -*- coding:utf-8 -*-
import threading
from hashlib import sha256
from math import log
import matplotlib.pyplot as plt


def entropy(wkList):  # 计算信息熵
    wkSet = set(wkList)
    rate = {}
    lenList = len(wkList)
    for k in wkSet:
        rate[k] = float(wkList.count(k)) / lenList
    return sum([-p * log(p, 2) for p in rate.values()])


# def gen_sha(n):
#     for i in range(n):
#         s = sha256(str(i).encode('utf-8')).hexdigest()
#         for j in range(64):
#             if j not in wkDict:
#                 wkDict[j] = [s[j]]
#             else:
#                 wkDict[j].append(s[j])

def gen_sha(_wkDict, start, stop):
    for _i in range(start, stop):
        s = sha256(str(_i).encode('utf-8')).hexdigest()
        for j in range(64):
            if j not in _wkDict:
                _wkDict[j] = [s[j]]
            else:
                _wkDict[j].append(s[j])


if __name__ == '__main__':

    # gen_sha(1000)
    wkDict = {}  # key: 某个十六进制位; value: 该位上的所有结果
    threads = []
    threadNum = 4
    interval = int(1000000 / threadNum)
    for i in range(threadNum):
        threads.append(threading.Thread(target=gen_sha, args=(wkDict, i * interval, (i + 1) * interval)))
    [t.start() for t in threads]
    [t.join() for t in threads]

    x = list(range(64))
    y = []
    for j in x:
        y.append(entropy(wkDict[j]))
    plt.plot(x, y)
    plt.xlim(0, 63)
    plt.ylim(3.9999, 4)
    plt.rcParams['font.sans-serif'] = ['SimHei']  # 设置中文字体
    plt.xlabel('十六进制位')
    plt.ylabel('信息熵')
    plt.show()

结论

根据图像可以看出输出结果的每一个十六进制位的信息熵都无限接近于4，因此假设可能正确。该假设还可以推广到所有密码学散列函数上：密码学Hash函数的输出结果是均匀分布的。