Hash算法簡(jiǎn)介

一、Hash算法的身影

可以看到，在生成比特幣地址(《精通比特幣》第4章提到)，以及生成區(qū)塊唯一標(biāo)識(shí)(《精通比特幣》第7章提到)：區(qū)塊Hash值時(shí)(即挖礦的過(guò)程)，都使用了Hash算法，特別是SHA256算法。比特幣系統(tǒng)本身也就是加密算法的衍生物。

二、SHA256算法過(guò)程

本文主要簡(jiǎn)述一下SHA256算法的過(guò)程，下一篇會(huì)大概說(shuō)一下它的理論基礎(chǔ)。

1. 輸入信息x

SHA256要求報(bào)文長(zhǎng)度不超過(guò)2^64bit。

2. 補(bǔ)位

因?yàn)椴捎玫氖欠纸M加密的方法，每組長(zhǎng)度是512bit，而原始的信息x，不一定是512的倍數(shù)，也就是說(shuō)不一定能剛好分成每組都是512bit的情況。這時(shí)候需要補(bǔ)位。

在x后面先補(bǔ)一個(gè)1，然后再補(bǔ)多個(gè)0，一直到總長(zhǎng)度(x以及補(bǔ)的位數(shù))模512是448

3. 補(bǔ)長(zhǎng)度

為什么第二步不直接把總長(zhǎng)度補(bǔ)到512的倍數(shù)呢，因?yàn)楹竺孢€要補(bǔ)64位，記錄原始信息x的位數(shù)。(64 + 448) % 512 = 0。可以看到，只有64位表示原始信息x的位數(shù)，所以x的最大長(zhǎng)度是2^64。

4. 計(jì)算Hash值

前面已經(jīng)將消息補(bǔ)成了512的倍數(shù)，總長(zhǎng)度變?yōu)?12 * N。計(jì)算hash值的基本思想是：先將處理完的消息分成N個(gè)512bit的數(shù)據(jù)塊：M[1]，M[2]，……，M[N]，然后一塊一塊的處理：哈希初值H[0]經(jīng)過(guò)第一個(gè)數(shù)據(jù)塊M[1]得到H[1]，H[1]經(jīng)過(guò)第二個(gè)數(shù)據(jù)塊M[2]得到H[2]，……，依次處理，最后得到H[N]。每個(gè)哈希值，比如H[0]，由8個(gè)32bit組成，32bit又稱為字，也就是說(shuō)每個(gè)hash值都由8個(gè)字組成。最后將H[N]的8個(gè)字連接成256bit(8 * 32 bit)的最終值。至于為什么可以這么做，我們下一篇再介紹，先看流程。

1) 哈希初值H[0]

SHA256算法中用到的哈希初值H[0](共有8個(gè)32bit)為：

H[0][0] = 0x6A09E667

H[0][1] = 0xBB67AE85

H[0][2] = 0x3C6EF372

H[0][3] = 0xA54FF53A

H[0][4] = 0x510E527F

H[0][5] = 0x9B05688C

H[0][6] = 0x1F83D9AB

H[0][7] = 0x5BE0CD19

0x表示的是十六進(jìn)制，十六進(jìn)制中一位表示4bit。

注：這些初值是對(duì)自然數(shù)中前8個(gè)質(zhì)數(shù)2、3、5、7、11等的平方根的小數(shù)部分取前32bit而來(lái)。

2) 循環(huán)計(jì)算

# M的下標(biāo)從1開始，M即為M[1], ..., M[N]

for i in range(1, N + 1):

# 第一步，先根據(jù)16個(gè)32bit的原始消息，生成64個(gè)32bit

W = [0] * 64

for t in range(0, 64):

if t < 16:

W[t] = M[i][t]

else:

W[t] = SSIG1(W[t - 2]) + W[t-7] + SSIG0(W[t-15]) + W[t-16]

# 第二步，將上次的hash值，也就是8個(gè)32bit，賦值到8個(gè)臨時(shí)變量，用這8個(gè)臨時(shí)變量計(jì)算

# 原本的hash值在本輪結(jié)束的時(shí)候仍然需要使用

a = H[i - 1][0]

b = H[i - 1][1]

c = H[i - 1][2]

d = H[i - 1][3]

e = H[i - 1][4]

f = H[i - 1][5]

g = H[i - 1][6]

h = H[i - 1][7]

# 第三步，執(zhí)行散列計(jì)算，內(nèi)循環(huán)是64輪，使用了上面的64個(gè)W，以及提前定義好的64個(gè)K

for t in range(0, 64):

t1 = h + BSIG1(e) + CH(e, f, g) + K[t] + W[t]

t2 = BSIG0(a) + MAJ(a,b,c)

h = g

g = f

f = e

e = d + t1

d = c

c = b

b = a

a = t1 + t2

# 第四步，將本輪經(jīng)過(guò)64個(gè)內(nèi)循環(huán)新計(jì)算的臨時(shí)值和上次的hash值求和，作為本輪最終的hash值

H[i][0] = a + H[i - 1][0]

H[i][1] = b + H[i - 1][1]

H[i][2] = c + H[i - 1][2]

H[i][3] = d + H[i - 1][3]

H[i][4] = e + H[i - 1][4]

H[i][5] = f + H[i - 1][5]

H[i][6] = g + H[i - 1][6]

H[i][7] = h + H[i - 1][7]

# 最終H[N]的8個(gè)32bit返回，即為該消息的SHA256結(jié)果

3) 函數(shù)和常量說(shuō)明

(1) 64個(gè)常量K為:

K = [

0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,

0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,

0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,

0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,

0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,

0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,

0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,

0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2]

注：這些常數(shù)的取值是從自然數(shù)中前64個(gè)質(zhì)數(shù)的立方根的小數(shù)部分取前32bit而來(lái)的。

(2) 利用到的函數(shù)為：

# 本段代碼沒有使用python語(yǔ)法

CH(x, y, z) = (x AND y) XOR ((NOT x) AND z)

MAJ(x, y, z) = (x AND y) XOR (x AND z) XOR (y AND z)

BSIG0(x) = ROTR^2(x) XOR ROTR^13(x) XOR ROTR^22(x)

BSIG1(x) = ROTR^6(x) XOR ROTR^11(x) XOR ROTR^25(x)

SSIG0(x) = ROTR^7(x) XOR ROTR^18(x) XOR SHR^3(x)

SSIG1(x) = ROTR^17(x) XOR ROTR^19(x) XOR SHR^10(x)

其中，除了與或非外，XOR是異或， ROTR^n是循環(huán)右移n位，SHR^n是右移n位。

三、總結(jié)

上面就是SHA256的計(jì)算過(guò)程。