密码学之一(Hash函数)

定义

Hash函数H将可变长度的数据M作为输入，产生固定长度的Hash值h。
Hash函数，哈希函数，散列函数，杂凑函数它们说的都是同一个含义，后续我们都称之为Hash函数。

$h = H (M)$ $h = H(M)$

单向性

给定输入M，通过函数H可以很容易计算出输出h；但如果给定h，则找到M在计算上不可行。

数据完整性

输入数据M中任何1个bit发生变化，都将导致输出M发生很大的变化。

Hash冲突

在Hash函数中，M称之为h原像,，因为H函数是一个多对一的映射,，对于任意给定的Hash数值h,，可能会有多个原像,，如果满足如下条件, 则称之为发生了哈希碰撞，也就是哈希冲突。

$x! = y a n d H (x) = = H (y)$ $x != y \quad and \quad H(x) == H(y)$

一个优良的Hash函数必须满足如下几个性质:

任意y，找x，使得H(x) = y，非常困难
给定x1, 找x2, 使得H(x1) == H(x2), 非常困难
找任意的x1, x2, 使得H(x1) == H(x2), 非常困难生日定理

常用的Hash算法

MD5
SHA1
SHA224
SHA256
SHA384
SHA512
SM3

程序

这里仅做原理性质的描述，因此直接调用库API。

#!/usr/bin/python
#coding:utf8

import hashlib

def b2s(bytes):
    rets = []
    for c in bytes:
        rets.append("%02X" % (ord(c)))
    r = ' '.join(rets)
    return r

def md5(data):
    hashobj = hashlib.md5()
    hashobj.update(data)
    return hashobj.digest()

def sha1(data):
    hashobj = hashlib.sha1()
    hashobj.update(data)
    return hashobj.digest()

def sha224(data):
    hashobj = hashlib.sha224()
    hashobj.update(data)
    return hashobj.digest()

def sha256(data):
    hashobj = hashlib.sha256()
    hashobj.update(data)
    return hashobj.digest()

def sha384(data):
    hashobj = hashlib.sha384()
    hashobj.update(data)
    return hashobj.digest()

def sha512(data):
    hashobj = hashlib.sha512()
    hashobj.update(data)
    return hashobj.digest()

def main():
    hash_fun_list = (md5, sha1, sha224, sha256, sha384, sha512)
    data = '\x12\x34'

    for fun in hash_fun_list:
        print fun
        r = fun(data)
        print b2s(r)

if __name__ == '__main__':
    main()

输出如下:

33563489094A0506C237A4965395D61B
FFA76D854A2969E7B9D83868D455512FCE0FD74D
C555719D8ABD5ECB99FB1D0B545448BE34F783632C09E314CA10AFF7
3A103A4E5729AD68C02A678AE39ACCFBC0AE208096437401B7CEAB63CCA0622F
9D27A0B45F3329EBEDDFAA3E99EC9F4C0FF164B86D816F051C2117C6B96F8432BD6B7CBECD13C796AE65FC9E445824F5
4C54886C9821195522D88FF4705C3E0C686B921054421E6EA598739C29C26E1EE75419AACEEC94DD2E3C0DBB82ECF895C9F61215F375DE6D800D9B99D3D4B816

Hash环问题

从一个给定的输入x0开始，依次计算找到一个环满足如下条件:

x 1 = H (x 0)

$x1=H(x0)$

x 2 = H (x 1)

$x2=H(x1)$

x 3 = H (x 2)

$x3=H(x2)$

x 4 = H (x 3)

$x4=H(x3)$

. . .

$...$

x 0 = H (x n)

$x0=H(xn)$

以SHA256为例子, 限定输入也为32字节，那么输入的集合包含2^32个元素，输出的集合包含2^32个元素，可以证明这样的Hash环存在。两种极端的情况分别是:

2^32个元素构成一个环
一个元素构成一个环，也就是 $x0=H(x0)$

寻找Hash环的程序，如此大的数学计算面前，计算机何时才能找到呢？

x0 = '\xAB' * 32
x = x0
num = 0
while True:
    x = sha256(x)
    num += 1
    if x == x0:
        print b2s(x)
        break

Hash应用场景

校验数据的完整性
和签名函数联合使用，用于计算输入数据的签名

更多精彩内容