SHA256简介

SHA256简介1. SHA256简介

SHA256是SHA-2下细分出的⼀种算法

SHA-2，名称来⾃于安全散列算法2（英语：Secure Hash Algorithm 2）的缩写，⼀种密码散列函数算法标准，由美国国家研发，属于SHA算法之⼀，是SHA-1的后继者。

SHA-2下⼜可再分为六个不同的算法标准

包括了：SHA-224、SHA-256、SHA-384、SHA-512、SHA-512/224、SHA-512/256。这些变体除了⽣成摘要的长度 、循环运⾏的次数等⼀些微⼩差异外，算法的基本结构是⼀致的。回到SHA256上，说⽩了，它就是⼀个哈希函数。

哈希函数，⼜称散列算法，是⼀种从任何⼀种数据中创建⼩的数字“指纹”的⽅法。散列函数把消息或数据压缩成摘要，使得数据量变⼩，将数据的格式固定下来。该函数将数据打乱混合，重新创建⼀个叫做散列值（或哈希值）的指纹。散列值通常⽤⼀个短的随机字母和数字组成的字符串来代表。对于任意长度的消息，SHA256都会产⽣⼀个256bit长的哈希值，称作消息摘要。

这个摘要相当于是个长度为32个字节的数组，通常⽤⼀个长度为的⼗六进制字符串来表⽰来看⼀个例⼦：

⼲他100天成为区块链程序员，红军⼤叔带领着我们，fighting!

这句话，经过哈希函数SHA256后得到的哈希值为：

A7FCFC6B5269BDCCE571798D618EA219A68B96CB87A0E21080C2E758D23E4CE9

这⾥找到了⼀个，可以⽤来进⾏SHA256哈希结果的验证，后⾯也可以⽤来检验⾃⼰的SHA256代码是否正确。⽤起来很⽅便，不妨感受下。

2. SHA256原理详解

为了更好的理解SHA256的原理，这⾥⾸先将算法中可以单独抽出的模块，包括常量的初始化、信息预处理、使⽤到的逻辑运算分别进⾏介绍，甩开这些理解上的障碍后，⼀起来探索SHA256算法的主体部分，即消息摘要是如何计算的。

2.1 常量初始化

SHA256算法中⽤到了8个哈希初值以及个哈希常量其中，SHA256算法的8个哈希初值如下：

h0 := 0x6a09e667h1 := 0xbb67ae85h2 := 0x3c6ef372h3 := 0xaff53ah4 := 0x510e527fh5 := 0x9b05688ch6 := 0x1f83d9abh7 := 0x5be0cd1912345678

这些初值是对⾃然数中前8个质数（2,3,5,7,11,13,17,19）的平⽅根的⼩数部分取前32bit⽽来

举个例⼦来说，$ \\sqrt{2} $⼩数部分约为0.414213562373095048，⽽

0.414213562373095048 ≈ 6 ∗ 1 6 − 1 + a ∗ 1 6 − 2 + 0 ∗ 1 6 − 3 + . . . 0.414213562373095048 \\approx 616^{-1} + a16^{-2} + 016^{-3} +...0.414213562373095048≈6∗16−1+a*∗16−2+0∗16−3+...于是，质数2的平⽅根的⼩数部分取前32bit就对应出了0x6a09e667在SHA256算法中，⽤到的个常量如下：

428a2f98 71374491 b5c0fbcf e9b5dba53956c25b 59f111f1 923f82a4 ab1c5ed5d807aa98 12835b01 243185be 550c7dc372be5d74 80deb1fe 9bdc06a7 c19bf174e49b69c1 efbe4786 0fc19dc6 240ca1cc2de92c6f 4a7484aa 5cb0a9dc 76f988da983e5152 a831c66d b00327c8 bf597fc7c6e00bf3 d5a79147 06ca6351 1429296727b70a85 2e1b2138 4d2c6dfc 53380d13650a73 766a0abb 81c2c92e 92722c85a2bfe8a1 a81a6b c24b8b70 c76c51a3d192e819 d6990624 f40e3585 106aa07019a4c116 1e376c08 2748774c 34b0bcb5391c0cb3 4ed8aa4a 5b9cca4f 682e6ff3748f82ee 78a5636f 84c87814 8cc70200befffa a4506ceb bef9a3f7 c67178f2123456710111213141516

和8个哈希初值类似，这些常量是对⾃然数中前个质数(2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,,97…)的⽴⽅根的⼩数部分取前

32bit⽽来。

2.2 信息预处理(pre-processing)

SHA256算法中的预处理就是在想要Hash的消息后⾯补充需要的信息，使整个消息满⾜指定的结构。信息的预处理分为两个步骤：附加填充⽐特和附加长度STEP1：附加填充⽐特

在报⽂末尾进⾏填充，使报⽂长度在对512取模以后的余数是448

填充是这样进⾏的：先补第⼀个⽐特为1，然后都补0，直到长度满⾜对512取模后余数是448。

需要注意的是，信息必须进⾏填充，也就是说，即使长度已经满⾜对512取模后余数是448，补位也必须要进⾏，这时要填充512个⽐特。因此，填充是⾄少补⼀位，最多补512位。例：以信息“abc”为例显⽰补位的过程。a,b,c对应的分别是97,98,99

于是原始信息的⼆进制编码为：01100001 01100010 01100011补位第⼀步，⾸先补⼀个“1” ： 0110000101100010 01100011 1

补位第⼆步,补423个“0”：01100001 01100010 01100011 10000000 00000000 … 00000000补位完成后的数据如下（为了简介⽤16进制表⽰）：

61626380 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 000000001234

为什么是448?

因为在第⼀步的预处理后，第⼆步会再附加上⼀个bit的数据，⽤来表⽰原始报⽂的长度信息。⽽448+=512，正好拼成了⼀个完整的结构。STEP2：附加长度值

附加长度值就是将原始数据（第⼀步填充前的消息）的长度信息补到已经进⾏了填充操作的消息后⾯。

wiki百科中给出的原⽂是：append length of message (before pre-processing), in bits, as -bit big-endian integerSHA256⽤⼀个位的数据来表⽰原始消息的长度。

因此，通过SHA256计算的消息长度必须要⼩于$ 2^ $，当然绝⼤多数情况这⾜够⼤了。长度信息的编码⽅式为-bit big-endian integer关于的含义，⽂末给出了补充

回到刚刚的例⼦，消息“abc”，3个字符，占⽤24个bit

因此，在进⾏了补长度的操作以后，整个消息就变成下⾯这样了（16进制格式）

61626380 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 0000000000000000 00000000 00000000 000000181234

2.3 逻辑运算

SHA256散列函数中涉及的操作全部是逻辑的位运算包括如下的逻辑函数：

C h ( x , y , z ) = ( x ∧ y ) ⊕ ( ¬ x ∧ z ) Ch(x,y,z) = (x \\land y) \\oplus (\\neg x \\land z)C**h(x,y,z)=(x∧y)⊕(¬x∧z)

M a ( x , y , z ) = ( x ∧ y ) ⊕ ( x ∧ z ) ⊕ ( y ∧ z ) Ma(x,y,z) = (x \\land y) \\oplus (x \\land z) \\oplus (y \\land z)M**a(x,y,z)=(x∧y)⊕(x∧z)⊕(y∧z)Σ 0 ( x ) = S 2 ( x ) ⊕ S 13 ( x ) ⊕ S 22 ( x ) \\Sigma_{0}(x) = S^{2}(x) \\oplus S^{13}(x) \\oplus S^{22}(x)Σ0(x)=S2(x)⊕S13(x)⊕S22(x)Σ 1 ( x ) = S 6 ( x ) ⊕ S 11 ( x ) ⊕ S 25 ( x ) \\Sigma_{1}(x) = S^{6}(x) \\oplus S^{11}(x) \\oplus S^{25}(x)Σ1(x)=S6(x)⊕S11(x)⊕S25(x)σ 0 ( x ) = S 7 ( x ) ⊕ S 18 ( x ) ⊕ R 3 ( x ) \\sigma_{0}(x) = S^{7}(x) \\oplus S^{18}(x) \\oplus R^{3}(x)σ0(x)=S7(x)⊕S18(x)⊕R3(x)

σ 1 ( x ) = S 17 ( x ) ⊕ S 19 ( x ) ⊕ R 10 ( x ) \\sigma_{1}(x) = S^{17}(x) \\oplus S^{19}(x) \\oplus R^{10}(x)σ1(x)=S17(x)⊕S19(x)⊕R10(x)其中：逻辑运算∧ \\land∧¬ \\neg¬⊕ \\oplus⊕

含义按位“与”按位“补”按位“异或”

S n S^{n}S**n循环右移n个bitR n R^{n}R**n右移n个bit

2.4 计算消息摘要

现在来介绍SHA256算法的主体部分，即消息摘要是如何计算的。⾸先：将消息分解成512-bit⼤⼩的块(break message into 512-bit chunks)

假设消息M可以被分解为n个块，于是整个算法需要做的就是完成n次迭代，n次迭代的结果就是最终的哈希值，即256bit的数字摘要。⼀个256-bit的摘要的初始值H0，经过第⼀个数据块进⾏运算，得到H1，即完成了第⼀次迭代H1经过第⼆个数据块得到H2，……，依次处理，最后得到Hn，Hn即为最终的256-bit消息摘要将每次迭代进⾏的映射⽤$ Map(H_{i-1}) = H_{i} $表⽰，于是迭代可以更形象的展⽰为：

图中256-bit的Hi被描述8个⼩块，这是因为SHA256算法中的最⼩运算单元称为“字”（Word），⼀个字是32位。此外，第⼀次迭代中，映射的初值设置为前⾯介绍的8个哈希初值，如下图所⽰：

下⾯开始介绍每⼀次迭代的内容，即映射$ Map(H_{i-1}) = H_{i} $的具体算法STEP1：构造个字（word）

break chunk into sixteen 32-bit big-endian words w[0], …, w[15]

对于每⼀块，将块分解为16个32-bit的big-endian的字，记为w[0], …, w[15]也就是说，前16个字直接由消息的第i个块分解得到其余的字由如下迭代公式得到：

W t = σ 1 ( W t − 2 ) + W t − 7 + σ 0 ( W t − 15 ) + W t − 16 W_{t} = \\sigma_{1}(W_{t-2}) + W_{t-7} + \\sigma_{0}(W_{t-15}) + W_{t-16}W**t=σ1(W**t−2)+W**t−7+σ0(W**t−15)+W**t−16STEP2：进⾏次循环

映射 $ Map(H_{i-1}) = H_{i} $ 包含了次加密循环即进⾏次加密循环即可完成⼀次迭代每次加密循环可以由下图描述：

图中，ABCDEFGH这8个字（word）在按照⼀定的规则进⾏更新，其中深蓝⾊⽅块是事先定义好的⾮线性逻辑函数，上⽂已经做过铺垫

红⾊⽥字⽅块代表 mod $ 2^{32} $ addition，即将两个数字加在⼀起，如果结果⼤于$ 2^{32} ， 你 必 须 除 以 ，你必须除以，你必须除以 2^{32} $并找到余数。ABCDEFGH⼀开始的初始值分别为$ H_{i-1}(0),H_{i-1}(1),…,H_{i-1}(7) $Kt是第t个密钥，对应我们上⽂提到的个常量

Wt是本区块产⽣第t个word。原消息被切成固定长度512-bit的区块，对每⼀个区块，产⽣个word，通过重复运⾏循环n次对ABCDEFGH这⼋个字循环加密。最后⼀次循环所产⽣的⼋个字合起来即是第i个块对应到的散列字符串$ H_{i} $由此变完成了SHA256算法的所有介绍

3. SHA256算法伪代码

现在我们可以结合SHA256算法的伪代码,将上述的所有步骤进⾏梳理整合：

Note: All variables are unsigned 32 bits and wrap modulo 232 when calculating

Initialize variables

(first 32 bits of the fractional parts of the square roots of the first 8 primes 2..19):h0 := 0x6a09e667h1 := 0xbb67ae85h2 := 0x3c6ef372h3 := 0xaff53ah4 := 0x510e527fh5 := 0x9b05688ch6 := 0x1f83d9abh7 := 0x5be0cd19

Initialize table of round constants

(first 32 bits of the fractional parts of the cube roots of the first primes 2..311):k[0..63] :=

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, 0x650a73, 0x766a0abb, 0x81c2c92e, 0x92722c85, 0xa2bfe8a1, 0xa81a6b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070, 0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3, 0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2

Pre-processing:

append the bit '1' to the message

append k bits '0', where k is the minimum number >= 0 such that the resulting message length (in bits) is congruent to 448(mod 512)

append length of message (before pre-processing), in bits, as -bit big-endian integer

Process the message in successive 512-bit chunks:break message into 512-bit chunksfor each chunk

break chunk into sixteen 32-bit big-endian words w[0..15]

Extend the sixteen 32-bit words into sixty-four 32-bit words: for i from 16 to 63

s0 := (w[i-15] rightrotate 7) xor (w[i-15] rightrotate 18) xor(w[i-15] rightshift 3) s1 := (w[i-2] rightrotate 17) xor (w[i-2] rightrotate 19) xor(w[i-2] rightshift 10) w[i] := w[i-16] + s0 + w[i-7] + s1 Initialize hash value for this chunk: a := h0 b := h1 c := h2 d := h3 e := h4 f := h5 g := h6 h := h7

Main loop:

for i from 0 to 63

s0 := (a rightrotate 2) xor (a rightrotate 13) xor(a rightrotate 22) maj := (a and b) xor (a and c) xor(b and c) t2 := s0 + maj

s1 := (e rightrotate 6) xor (e rightrotate 11) xor(e rightrotate 25) ch := (e and f) xor ((not e) and g) t1 := h + s1 + ch + k[i] + w[i] h := g g := f f := e

e := d + t1 d := c c := b b := a

a := t1 + t2

Add this chunk's hash to result so far: h0 := h0 + a h1 := h1 + b h2 := h2 + c h3 := h3 + d h4 := h4 + e h5 := h5 + f h6 := h6 + g h7 := h7 + h

Produce the final hash value (big-endian):

digest = hash = h0 append h1 append h2 append h3 append h4 append h5 append h6 append h7

1234567101112131415161718192021222324252627282930313233343536373839404142434447484950515253555657585960616263656667686970717273747576777879808182838485

4. 参考⽂献

本篇笔记主要参考整合的资料如下：

知识填补

⼤端和⼩端（Big endian and Little endian）

对于整型、长整型等数据类型，都存在字节排列的⾼低位顺序问题。

Big endian 认为第⼀个字节是最⾼位字节（按照从低地址到⾼地址的顺序存放数据的⾼位字节到低位字节）

⽽ Little endian 则相反，它认为第⼀个字节是最低位字节（按照从低地址到⾼地址的顺序存放据的低位字节到⾼位字节）。例如，假设从内存地址 0x0000 开始有以下数据：地址数据

…地址…数据0x00000x120x00010x340x00020xab0x00030xcd…

…

假设我们去读取⼀个地址为 0x0000 的四个字节变量若字节序为big-endian，则读出结果为0x1234abcd；若字节序为little-endian，则读出结果为0xcdab3412。

如果我们将0x1234abcd 写⼊到以 0x0000 开始的内存中，则Little endian 和 Big endian 模式的存放结果如下：

地址little-endian

0x00000x00010x00020x0003

0x340xab

0xab0x34

0xcd0x12

0xcd

big-Big_endian0x12