1.SHA简介5 O2 J. t9 R( v, w
关于SHA的定义直接参考wiki介绍：
( H  I5 ]% T0 h/ ?- Q9 W% n" M安全散列算法（英语：Secure Hash Algorithm，缩写为SHA）是一个密码散列函数家族，是FIPS所认证的安全散列算法。能计算出一个数字消息所对应到的，长度固定的字符串（又称消息摘要）的算法。且若输入的消息不同，它们对应到不同字符串的机率很高。) d& D' F! |' n% F# I
SHA可看作是是一种单向函数，几乎不可逆，给一段信息，它会给你生成固定长度的摘要，当然，不同的信息是的确有可能生成相同的摘要的，这被称作碰撞，简单来说，摘要的长度越长，碰撞几率越低。' {. j6 x% U. N+ g3 y0 Y3 i/ Q5 b
既然有碰撞这种可能性，那碰撞肯定会被拿来用作攻击手段的，SHA-1已经在17年被Google和荷兰的小组攻破了，目前使用的标准是SHA-2，其实在算法上SHA-2和SHA-1区别不大，但是至今SHA-2还没被攻破，所以暂且当它没什么弱点。! ?& m  ^8 E# p
从SHA的特点来看，用来作文件验证和数字签名是非常合适的。比特币使用的就是SHA-2中的SHA256算法。7 O' v" S$ j/ n+ }7 j
2.SHA256的算法实现
) Z  C8 s/ R5 V. n首先，SHA算法在数学原理上是相当复杂的（那些移位与或非对于算法的作用看着就头大），对于不以密码学研究为目的，同时也是初学者的我来说，去分析它的数学细节对我没有什么意义，因此我暂且忽略那一部分直接看它的算法实现。
6 }. q: {- Y6 T7 w4 {. H3 e5 b实现可以分为三个部分：常量初始化，信息预处理，生成摘要。
6 c3 u2 n4 A) y1 t4 r. i2.1常量初始化
8 e. Q1 U' n9 x3 Y7 Q首先是初始化8个值，分别是最开始的连续8个素数（从2到19）的平方根的二进制表示的小数部分的前32位，有点绕，不过就是这样啦，这些后面会作为迭代的初值使用。
+ \& `( {9 q% P; o. r1 }( UInitialize variables' p+ }9 z; }' A0 q4 a$ p: Q
(first 32 bits of the fractional parts of the square roots of the first 8 primes 2..19):
7 }' R0 O* {# E' A0 C6 s2 lh0 := 0x6a09e667
4 `/ R4 \6 ^( t" Kh1 := 0xbb67ae85; f4 E9 C( L0 O# Z$ S
h2 := 0x3c6ef372; J, z6 V1 v! P
h3 := 0xa54ff53a
' W+ R* J0 T, V2 ]4 B  Ih4 := 0x510e527f! Y" S, r9 ^6 Y) A  p
h5 := 0x9b05688c$ R: [7 V) n1 N& B
h6 := 0x1f83d9ab8 R6 T: i1 ^( C6 P/ W: [" f0 K
h7 := 0x5be0cd195 ^1 A7 y7 f* v$ ]4 T
然后还要初始化64个值，分别是最开始的连续64个素数（从2到311）的立方根的二进制表示的小数部分的前32位，可以看到这64个数也成了数组的形式，因为是要在后面每次迭代中拿来进行循环运算的。
' q; K( d. o2 m" IInitialize table of round constants- m- j, j, ]5 j4 w  a5 Y
(first 32 bits of the fractional parts of the cube roots of the first 64 primes 2..311):
  f7 @; G3 m) i, M4 i8 \k[0..63] :=
' |1 O: `& p6 m& f0 D  K' c   0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,# i3 {3 h" d  ^( i
   0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,+ [" S/ m! U4 C2 I* \$ `7 @3 V  C7 Y
   0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,& }1 C5 ^9 w6 [( h. o/ Z& ]
   0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
3 e2 W/ V2 M% v   0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
4 k9 ~/ M1 x  T# {7 j# s, @  r   0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
* v- a# H# J% b   0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
6 q- r/ n9 ~; b- A8 x/ l" C   0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2- t: b0 u2 b. b! v' K* U
2.2信息预处理, O! K$ H5 o% W: s* a3 P- i* O
预处理分为三步，首先是在原信息后加一个‘1’；然后再添加k个0，直到信息长度 mod 512 = 448，如果原信息是447这种长度，那其实就不用加0了；最后就是再添加原信息的长度到末尾，是64位的大端模式的格式。, ]6 r/ s1 F. E
Pre-processing:. ^7 ~9 C1 o6 [
append the bit '1' to the message+ z" s& Y5 r; ~2 p
append k bits '0', where k is the minimum number >= 0 such that the resulting message
5 }  `" V* E( \0 ]    length (in bits) is congruent to 448(mod 512)
& J* w1 d" \/ Y) J, bappend length of message (before pre-processing), in bits, as 64-bit big-endian integer  M* O- Q, m' W: k( }
2.3生成摘要
/ f+ e, U; H) c+ `( C. o# L到了最麻烦的一步了，生成摘要。
1 Z$ X  [8 Z8 C7 v: Q首先，经过第二步，现在信息已经是512bit的倍数这种格式了，所以这里首先是把信息分成块，每一块是512bit，然后每一块都是一次迭代，每一次迭代都会更新摘要，最后一次迭代结果就是最终生成的摘要。
7 @7 h$ M, F; r, K) @0 a. ]9 r  B9 }+ F所以，关键就是每一步迭代过程中发生了什么。
( u$ a1 p, S) u6 ~对于SHA256算法，最终的摘要是256bit的，结合前面的8个32bit的初值，这里就不难理解了，总的摘要是分成8个值进行更新的。块大小是512bit的，将其也以32bit为单位分成16个，然后通过对16个数进行运算，生成另外48个数，总之，得到了64个值，这和前面的64个常量相对应，剩下的就直接看下图吧：' V+ A2 F2 ~) l+ `& ?: }- p

% C2 T( ~5 {1 [$ ]. N5 g每次迭代摘要的更新流程: X9 A- O0 U. l
中间各种运算符什么的，就是一些运算而已，没什么好说的， W是从块中得到的64个数的集合，K是之前初始化的64个数的集合，可以看到一次迭代内部有64次循环，每次循环都会更新一次摘要。" f8 o6 g# q- I1 O, _5 h2 J( |7 w
最后，来看看伪代码把：* B% Q8 V0 ?7 q7 P
Process the message in successive 512-bit chunks:
9 f( W$ j# W6 p+ C/ J# Ybreak message into 512-bit chunks
) h% U; I8 C* W) y) q  Hfor each chunk
; B; j4 {) u2 _  q    break chunk into sixteen 32-bit big-endian words w[0..15]
  S) y3 S* G0 s: k+ e    Extend the sixteen 32-bit words into sixty-four 32-bit words:6 R! H8 F* U' p4 ^
    for i from 16 to 63
+ _/ P$ K& [. m& O! L7 R        s0 := (w[i-15] rightrotate 7) xor (w[i-15] rightrotate 18) xor(w[i-15] rightshift 3)5 s; V7 ^  B1 |7 g1 k- K! b
        s1 := (w[i-2] rightrotate 17) xor (w[i-2] rightrotate 19) xor(w[i-2] rightshift 10)6 C. P% `1 q) w: p: ?8 {2 h
        w := w[i-16] + s0 + w[i-7] + s1
+ Z) Z- K: O. `; j& F    Initialize hash value for this chunk:
# r" i$ Y- ^9 i8 P8 [+ a" n    a := h09 i! K+ M+ U' _1 Y; D4 ]4 C
    b := h16 ~3 A) C8 T0 {  W$ W; |: ?
    c := h2$ j6 \7 t) }- p& r! s; z
    d := h3
+ V- T8 Q! b! n8 c4 @    e := h45 {9 f$ F+ I4 h" J+ }, G, z
    f := h5. h( O0 b1 N0 Y7 b% D
    g := h6
* X* k: c6 _9 q. X- @" g8 c2 i    h := h76 J" Q- m2 W8 v: k8 s" ?9 L) m
    Main loop:
* `( {8 Q% G7 l  V: {( j0 D2 o: H    for i from 0 to 63
5 W( m- C2 A: l0 W- M- }$ M; F4 m        s0 := (a rightrotate 2) xor (a rightrotate 13) xor(a rightrotate 22)
& ^) H5 k% `. U; n: T/ n7 q3 _" s( G        maj := (a and b) xor (a and c) xor(b and c)* e- B( p9 O+ S" ~0 D
        t2 := s0 + maj' x' C5 G& j1 U( @# S  L% V
        s1 := (e rightrotate 6) xor (e rightrotate 11) xor(e rightrotate 25)* D/ l# O7 ~6 o% G$ A% z9 ^
        ch := (e and f) xor ((not e) and g). A2 U; h1 c. N& F
        t1 := h + s1 + ch + k + w# r) \" m& @3 \9 P! A; g
        h := g- A+ Z$ q, i4 H# X+ d; k
        g := f
+ v- U7 J# [7 f        f := e" l' ]/ G( Z, F' ]$ W
        e := d + t15 E' E2 s: ?' P( o# c
        d := c
. u4 y! W5 L' N, f& B% l  d1 m        c := b; U2 l" f2 `/ h5 b8 I1 S- u
        b := a
; n1 |* c$ l: T: S, O' Q        a := t1 + t2
" ~1 @" x1 _0 s& ?    Add this chunk's hash to result so far:
8 G# F) {! T( N! I$ }    h0 := h0 + a* O6 E8 l) K" G
    h1 := h1 + b
, t7 k6 j7 o! L& f8 c    h2 := h2 + c! i" g& F$ ?1 J+ l4 C# d
    h3 := h3 + d
  `( Y7 \/ E* \7 E9 e9 ?* C    h4 := h4 + e$ j" I. |6 Z4 ~* o0 Q* _
    h5 := h5 + f
/ i% B) P+ R  Z. V* y: y    h6 := h6 + g
% `- Z' R% s+ k8 ]: y) [4 Y( Q    h7 := h7 + h
" W6 v# g" p' g" \/ ?" a5 b, S) \' FProduce the final hash value (big-endian):& ^2 s# I4 s2 @# u, o
digest = hash = h0 append h1 append h2 append h3 append h4 append h5 append h6 append h71 b+ k' Z. _, `6 h3 K
一目了然，对吧。* D4 }! Z4 s0 f6 v7 F# y