哈希算法SHA-256实现示例
参考：
/wiki/SHA-2
/wiki/Endianness
/wiki/Binary_large_object
SHA-256哈希算法计算流程如下：
Note 1: All variables are 32 bit unsigned integers and addition is calculated modulo 232Note 2: For each round, there is one round constant k[i] and one entry in the message schedule array w[i], 0 ≤ i ≤ 63Note 3: The compression function uses 8 working variables, a through hNote 4: Big-endian convention is used when expressing the constants in this pseudocode,and when parsing message block data from bytes to words, for example,the first word of the input message "abc" after padding is 0x61626380Initialize hash values:(first 32 bits of the fractional parts of the square roots of the first 8 primes 2..19):h0 := 0x6a09e667h1 := 0xbb67ae85h2 := 0x3c6ef372h3 := 0xa54ff53ah4 := 0x510e527fh5 := 0x9b05688ch6 := 0x1f83d9abh7 := 0x5be0cd19Initialize array of round constants:(first 32 bits of the fractional parts of the cube roots of the first 64 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, 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, 0xc67178f2Pre-processing (Padding):begin with the original message of length L bitsappend a single '1' bitappend K '0' bits, where K is the minimum number >= 0 such that L + 1 + K + 64 is a multiple of 512append L as a 64-bit big-endian integer, making the total post-processed length a multiple of 512 bitsProcess the message in successive 512-bit chunks:break message into 512-bit chunksfor each chunkcreate a 64-entry message schedule array w[0..63] of 32-bit words(The initial values in w[0..63] don't matter, so many implementations zero them here)copy chunk into first 16 words w[0..15] of the message schedule arrayExtend the first 16 words into the remaining 48 words w[16..63] of the message schedule array:for i from 16 to 63s0 := (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] + s1Initialize working variables to current hash value:a := h0b := h1c := h2d := h3e := h4f := h5g := h6h := h7Compression function main loop:for i from 0 to 63S1 := (e rightrotate 6) xor (e rightrotate 11) xor (e rightrotate 25)ch := (e and f) xor ((not e) and g)temp1 := h + S1 + ch + k[i] + w[i]S0 := (a rightrotate 2) xor (a rightrotate 13) xor (a rightrotate 22)maj := (a and b) xor (a and c) xor (b and c)temp2 := S0 + majh := gg := ff := ee := d + temp1d := cc := bb := aa := temp1 + temp2Add the compressed chunk to the current hash value:h0 := h0 + ah1 := h1 + bh2 := h2 + ch3 := h3 + dh4 := h4 + eh5 := h5 + fh6 := h6 + gh7 := h7 + hProduce the final hash value (big-endian):digest := hash := h0 append h1 append h2 append h3 append h4 append h5 append h6 append h7
Bitcoin (0.16.0) 代码实现：
// Internal implementation code.namespace{/// Internal SHA-256 implementation.namespace sha256{uint32_t inline Ch(uint32_t x, uint32_t y, uint32_t z) { return z ^ (x & (y ^ z)); }uint32_t inline Maj(uint32_t x, uint32_t y, uint32_t z) { return (x & y) | (z & (x | y)); }uint32_t inline Sigma0(uint32_t x) { return (x >> 2 | x << 30) ^ (x >> 13 | x << 19) ^ (x >> 22 | x << 10); }uint32_t inline Sigma1(uint32_t x) { return (x >> 6 | x << 26) ^ (x >> 11 | x << 21) ^ (x >> 25 | x << 7); }uint32_t inline sigma0(uint32_t x) { return (x >> 7 | x << 25) ^ (x >> 18 | x << 14) ^ (x >> 3); }uint32_t inline sigma1(uint32_t x) { return (x >> 17 | x << 15) ^ (x >> 19 | x << 13) ^ (x >> 10); }/** One round of SHA-256. */void inline Round(uint32_t a, uint32_t b, uint32_t c, uint32_t& d, uint32_t e, uint32_t f, uint32_t g, uint32_t& h, uint32_t k, uint32_t w){uint32_t t1 = h + Sigma1(e) + Ch(e, f, g) + k + w;uint32_t t2 = Sigma0(a) + Maj(a, b, c);d += t1;h = t1 + t2;}/** Initialize SHA-256 state. */void inline Initialize(uint32_t* s){s[0] = 0x6a09e667ul;s[1] = 0xbb67ae85ul;s[2] = 0x3c6ef372ul;s[3] = 0xa54ff53aul;s[4] = 0x510e527ful;s[5] = 0x9b05688cul;s[6] = 0x1f83d9abul;s[7] = 0x5be0cd19ul;}/** Perform a number of SHA-256 transformations, processing 64-byte chunks. */void Transform(uint32_t* s, const unsigned char* chunk, size_t blocks){while (blocks--) {uint32_t a = s[0], b = s[1], c = s[2], d = s[3], e = s[4], f = s[5], g = s[6], h = s[7];uint32_t w0, w1, w2, w3, w4, w5, w6, w7, w8, w9, w10, w11, w12, w13, w14, w15;Round(a, b, c, d, e, f, g, h, 0x428a2f98, w0 = ReadBE32(chunk + 0));Round(h, a, b, c, d, e, f, g, 0x71374491, w1 = ReadBE32(chunk + 4));Round(g, h, a, b, c, d, e, f, 0xb5c0fbcf, w2 = ReadBE32(chunk + 8));Round(f, g, h, a, b, c, d, e, 0xe9b5dba5, w3 = ReadBE32(chunk + 12));Round(e, f, g, h, a, b, c, d, 0x3956c25b, w4 = ReadBE32(chunk + 16));Round(d, e, f, g, h, a, b, c, 0x59f111f1, w5 = ReadBE32(chunk + 20));Round(c, d, e, f, g, h, a, b, 0x923f82a4, w6 = ReadBE32(chunk + 24));Round(b, c, d, e, f, g, h, a, 0xab1c5ed5, w7 = ReadBE32(chunk + 28));Round(a, b, c, d, e, f, g, h, 0xd807aa98, w8 = ReadBE32(chunk + 32));Round(h, a, b, c, d, e, f, g, 0x12835b01, w9 = ReadBE32(chunk + 36));Round(g, h, a, b, c, d, e, f, 0x243185be, w10 = ReadBE32(chunk + 40));Round(f, g, h, a, b, c, d, e, 0x550c7dc3, w11 = ReadBE32(chunk + 44));Round(e, f, g, h, a, b, c, d, 0x72be5d74, w12 = ReadBE32(chunk + 48));Round(d, e, f, g, h, a, b, c, 0x80deb1fe, w13 = ReadBE32(chunk + 52));Round(c, d, e, f, g, h, a, b, 0x9bdc06a7, w14 = ReadBE32(chunk + 56));Round(b, c, d, e, f, g, h, a, 0xc19bf174, w15 = ReadBE32(chunk + 60));Round(a, b, c, d, e, f, g, h, 0xe49b69c1, w0 += sigma1(w14) + w9 + sigma0(w1));Round(h, a, b, c, d, e, f, g, 0xefbe4786, w1 += sigma1(w15) + w10 + sigma0(w2));Round(g, h, a, b, c, d, e, f, 0x0fc19dc6, w2 += sigma1(w0) + w11 + sigma0(w3));Round(f, g, h, a, b, c, d, e, 0x240ca1cc, w3 += sigma1(w1) + w12 + sigma0(w4));Round(e, f, g, h, a, b, c, d, 0x2de92c6f, w4 += sigma1(w2) + w13 + sigma0(w5));Round(d, e, f, g, h, a, b, c, 0x4a7484aa, w5 += sigma1(w3) + w14 + sigma0(w6));Round(c, d, e, f, g, h, a, b, 0x5cb0a9dc, w6 += sigma1(w4) + w15 + sigma0(w7));Round(b, c, d, e, f, g, h, a, 0x76f988da, w7 += sigma1(w5) + w0 + sigma0(w8));Round(a, b, c, d, e, f, g, h, 0x983e5152, w8 += sigma1(w6) + w1 + sigma0(w9));Round(h, a, b, c, d, e, f, g, 0xa831c66d, w9 += sigma1(w7) + w2 + sigma0(w10));Round(g, h, a, b, c, d, e, f, 0xb00327c8, w10 += sigma1(w8) + w3 + sigma0(w11));Round(f, g, h, a, b, c, d, e, 0xbf597fc7, w11 += sigma1(w9) + w4 + sigma0(w12));Round(e, f, g, h, a, b, c, d, 0xc6e00bf3, w12 += sigma1(w10) + w5 + sigma0(w13));Round(d, e, f, g, h, a, b, c, 0xd5a79147, w13 += sigma1(w11) + w6 + sigma0(w14));Round(c, d, e, f, g, h, a, b, 0x06ca6351, w14 += sigma1(w12) + w7 + sigma0(w15));Round(b, c, d, e, f, g, h, a, 0x14292967, w15 += sigma1(w13) + w8 + sigma0(w0));Round(a, b, c, d, e, f, g, h, 0x27b70a85, w0 += sigma1(w14) + w9 + sigma0(w1));Round(h, a, b, c, d, e, f, g, 0x2e1b2138, w1 += sigma1(w15) + w10 + sigma0(w2));Round(g, h, a, b, c, d, e, f, 0x4d2c6dfc, w2 += sigma1(w0) + w11 + sigma0(w3));Round(f, g, h, a, b, c, d, e, 0x53380d13, w3 += sigma1(w1) + w12 + sigma0(w4));Round(e, f, g, h, a, b, c, d, 0x650a7354, w4 += sigma1(w2) + w13 + sigma0(w5));Round(d, e, f, g, h, a, b, c, 0x766a0abb, w5 += sigma1(w3) + w14 + sigma0(w6));Round(c, d, e, f, g, h, a, b, 0x81c2c92e, w6 += sigma1(w4) + w15 + sigma0(w7));Round(b, c, d, e, f, g, h, a, 0x92722c85, w7 += sigma1(w5) + w0 + sigma0(w8));Round(a, b, c, d, e, f, g, h, 0xa2bfe8a1, w8 += sigma1(w6) + w1 + sigma0(w9));Round(h, a, b, c, d, e, f, g, 0xa81a664b, w9 += sigma1(w7) + w2 + sigma0(w10));Round(g, h, a, b, c, d, e, f, 0xc24b8b70, w10 += sigma1(w8) + w3 + sigma0(w11));Round(f, g, h, a, b, c, d, e, 0xc76c51a3, w11 += sigma1(w9) + w4 + sigma0(w12));Round(e, f, g, h, a, b, c, d, 0xd192e819, w12 += sigma1(w10) + w5 + sigma0(w13));Round(d, e, f, g, h, a, b, c, 0xd6990624, w13 += sigma1(w11) + w6 + sigma0(w14));Round(c, d, e, f, g, h, a, b, 0xf40e3585, w14 += sigma1(w12) + w7 + sigma0(w15));Round(b, c, d, e, f, g, h, a, 0x106aa070, w15 += sigma1(w13) + w8 + sigma0(w0));Round(a, b, c, d, e, f, g, h, 0x19a4c116, w0 += sigma1(w14) + w9 + sigma0(w1));Round(h, a, b, c, d, e, f, g, 0x1e376c08, w1 += sigma1(w15) + w10 + sigma0(w2));Round(g, h, a, b, c, d, e, f, 0x2748774c, w2 += sigma1(w0) + w11 + sigma0(w3));Round(f, g, h, a, b, c, d, e, 0x34b0bcb5, w3 += sigma1(w1) + w12 + sigma0(w4));Round(e, f, g, h, a, b, c, d, 0x391c0cb3, w4 += sigma1(w2) + w13 + sigma0(w5));Round(d, e, f, g, h, a, b, c, 0x4ed8aa4a, w5 += sigma1(w3) + w14 + sigma0(w6));Round(c, d, e, f, g, h, a, b, 0x5b9cca4f, w6 += sigma1(w4) + w15 + sigma0(w7));Round(b, c, d, e, f, g, h, a, 0x682e6ff3, w7 += sigma1(w5) + w0 + sigma0(w8));Round(a, b, c, d, e, f, g, h, 0x748f82ee, w8 += sigma1(w6) + w1 + sigma0(w9));Round(h, a, b, c, d, e, f, g, 0x78a5636f, w9 += sigma1(w7) + w2 + sigma0(w10));Round(g, h, a, b, c, d, e, f, 0x84c87814, w10 += sigma1(w8) + w3 + sigma0(w11));Round(f, g, h, a, b, c, d, e, 0x8cc70208, w11 += sigma1(w9) + w4 + sigma0(w12));Round(e, f, g, h, a, b, c, d, 0x90befffa, w12 += sigma1(w10) + w5 + sigma0(w13));Round(d, e, f, g, h, a, b, c, 0xa4506ceb, w13 += sigma1(w11) + w6 + sigma0(w14));Round(c, d, e, f, g, h, a, b, 0xbef9a3f7, w14 + sigma1(w12) + w7 + sigma0(w15));Round(b, c, d, e, f, g, h, a, 0xc67178f2, w15 + sigma1(w13) + w8 + sigma0(w0));s[0] += a;s[1] += b;s[2] += c;s[3] += d;s[4] += e;s[5] += f;s[6] += g;s[7] += h;chunk += 64;}}} // namespace sha256typedef void (*TransformType)(uint32_t*, const unsigned char*, size_t); TransformType Transform = sha256::Transform;} // namespace
上述代码实现哈希算法中常量的初始化，以及块处理。
/** A hasher class for SHA-256. */class CSHA256{private:uint32_t s[8];unsigned char buf[64];uint64_t bytes;public:static const size_t OUTPUT_SIZE = 32;CSHA256();CSHA256& Write(const unsigned char* data, size_t len);void Finalize(unsigned char hash[OUTPUT_SIZE]);CSHA256& Reset();};// SHA-256CSHA256::CSHA256() : bytes(0){sha256::Initialize(s);}CSHA256& CSHA256::Write(const unsigned char* data, size_t len){const unsigned char* end = data + len;size_t bufsize = bytes % 64;if (bufsize && bufsize + len >= 64) {// Fill the buffer, and process it.memcpy(buf + bufsize, data, 64 - bufsize);bytes += 64 - bufsize;data += 64 - bufsize;Transform(s, buf, 1);bufsize = 0;}if (end - data >= 64) {size_t blocks = (end - data) / 64;Transform(s, data, blocks);data += 64 * blocks;bytes += 64 * blocks;}if (end > data) {// Fill the buffer with what remains.memcpy(buf + bufsize, data, end - data);bytes += end - data;}return *this;}void CSHA256::Finalize(unsigned char hash[OUTPUT_SIZE]){static const unsigned char pad[64] = {0x80};unsigned char sizedesc[8];WriteBE64(sizedesc, bytes << 3);Write(pad, 1 + ((119 - (bytes % 64)) % 64));Write(sizedesc, 8);WriteBE32(hash, s[0]);WriteBE32(hash + 4, s[1]);WriteBE32(hash + 8, s[2]);WriteBE32(hash + 12, s[3]);WriteBE32(hash + 16, s[4]);WriteBE32(hash + 20, s[5]);WriteBE32(hash + 24, s[6]);WriteBE32(hash + 28, s[7]);}CSHA256& CSHA256::Reset(){bytes = 0;sha256::Initialize(s);return *this;}
SHA-256封装类，实现数据的长度处理，以及哈希结果值得输出。
其中，用到的一些通用函数，用来处理大端模式与小端模式的转换：
// 以字节为单位，交换64位数据的高低位inline uint64_t bswap_64(uint64_t x){return (((x & 0xff00000000000000ull) >> 56)| ((x & 0x00ff000000000000ull) >> 40)| ((x & 0x0000ff0000000000ull) >> 24)| ((x & 0x000000ff00000000ull) >> 8)| ((x & 0x00000000ff000000ull) << 8)| ((x & 0x0000000000ff0000ull) << 24)| ((x & 0x000000000000ff00ull) << 40)| ((x & 0x00000000000000ffull) << 56));}// 以字节为单位，交换32位数据的高低位inline uint32_t bswap_32(uint32_t x){return (((x & 0xff000000U) >> 24) | ((x & 0x00ff0000U) >> 8) |((x & 0x0000ff00U) << 8) | ((x & 0x000000ffU) << 24));}// 见bswap_32，大端模式转主机字节（小端模式）inline uint32_t be32toh(uint32_t big_endian_32bits){return bswap_32(big_endian_32bits);}// 见bswap_32，主机字节序转大端模式inline uint32_t htobe32(uint32_t host_32bits){return bswap_32(host_32bits);}// 见bswap_64，主机字节序转大端模式inline uint64_t htobe64(uint64_t host_64bits){return bswap_64(host_64bits);}// 小端模式转主机字节序（无变化）inline uint64_t le64toh(uint64_t little_endian_64bits){return little_endian_64bits;}// 从制定内存中读取32位数据，并将其转换为大端模式uint32_t static inline ReadBE32(const unsigned char* ptr){uint32_t x;memcpy((char*)&x, ptr, 4);return be32toh(x);}// 将32位数据转换为大端模式，并写入到制定内存void static inline WriteBE32(unsigned char* ptr, uint32_t x){uint32_t v = htobe32(x);memcpy(ptr, (char*)&v, 4);}// 将64位数据转换为大端模式，并写入到制定内存void static inline WriteBE64(unsigned char* ptr, uint64_t x){uint64_t v = htobe64(x);memcpy(ptr, (char*)&v, 8);}// 从制定那个内存中读取64位数据，并将其转换为主机字节序uint64_t static inline ReadLE64(const unsigned char* ptr){uint64_t x;memcpy((char*)&x, ptr, 8);return le64toh(x);}
代码中使用的数据类型uint256实现代码如下：
/** Template base class for fixed-sized opaque blobs. */template<unsigned int BITS>class base_blob{protected:static constexpr int WIDTH = BITS / 8;uint8_t data[WIDTH];public:base_blob(){memset(data, 0, sizeof(data));}explicit base_blob(const std::vector<unsigned char>& vch);bool IsNull() const{for (int i = 0; i < WIDTH; i++)if (data[i] != 0)return false;return true;}void SetNull(){memset(data, 0, sizeof(data));}inline int Compare(const base_blob& other) const { return memcmp(data, other.data, sizeof(data)); }friend inline bool operator==(const base_blob& a, const base_blob& b) { return pare(b) == 0; }friend inline bool operator!=(const base_blob& a, const base_blob& b) { return pare(b) != 0; }friend inline bool operator<(const base_blob& a, const base_blob& b) { return pare(b) < 0; }std::string GetHex() const;void SetHex(const char* psz);void SetHex(const std::string& str);std::string ToString() const;unsigned char* begin(){return &data[0];}unsigned char* end(){return &data[WIDTH];}const unsigned char* begin() const{return &data[0];}const unsigned char* end() const{return &data[WIDTH];}unsigned int size() const{return sizeof(data);}uint64_t GetUint64(int pos) const{const uint8_t* ptr = data + pos * 8;return ((uint64_t)ptr[0]) | \((uint64_t)ptr[1]) << 8 | \((uint64_t)ptr[2]) << 16 | \((uint64_t)ptr[3]) << 24 | \((uint64_t)ptr[4]) << 32 | \((uint64_t)ptr[5]) << 40 | \((uint64_t)ptr[6]) << 48 | \((uint64_t)ptr[7]) << 56;}template<typename Stream>void Serialize(Stream& s) const{s.write((char*)data, sizeof(data));}template<typename Stream>void Unserialize(Stream& s){s.read((char*)data, sizeof(data));}};/** 256-bit opaque blob.* @note This type is called uint256 for historical reasons only. It is an* opaque blob of 256 bits and has no integer operations. Use arith_uint256 if* those are required.*/class uint256 : public base_blob<256> {public:uint256() {}explicit uint256(const std::vector<unsigned char>& vch) : base_blob<256>(vch) {}/** A cheap hash function that just returns 64 bits from the result, it can be* used when the contents are considered uniformly random. It is not appropriate* when the value can easily be influenced from outside as e.g. a network adversary could* provide values to trigger worst-case behavior.*/uint64_t GetCheapHash() const{return ReadLE64(data);}};
计算对象的SHA-256哈希值模板实现：
/** Compute the 256-bit hash of an object. */template<typename T1>inline uint256 Hash(const T1 pbegin, const T1 pend){static const unsigned char pblank[1] = {};uint256 result;CSHA256().Write(pbegin == pend ? pblank : (const unsigned char*)&pbegin[0], (pend - pbegin) * sizeof(pbegin[0])).Finalize((unsigned char*)&result);return result;}
测试源码:
/babylco0/bitcoin_code_examples/blob/master/testsha256.cpp
