Remco Bloemen
A fine-tuned implementation of the SHA256 hashing algorithm.
Dependents: EntropySource Wallet_v1
SHA256.cpp@0:772b6de3a841, 2011-06-20 (annotated)
- Committer:
- Remco
- Date:
- Mon Jun 20 00:23:22 2011 +0000
- Revision:
- 0:772b6de3a841
- Child:
- 2:1991439ea6b8
Who changed what in which revision?
| User | Revision | Line number | New contents of line |
|---|---|---|---|
| Remco | 0:772b6de3a841 | 1 | // Author: Remco Bloemen |
| Remco | 0:772b6de3a841 | 2 | // Based on: |
| Remco | 0:772b6de3a841 | 3 | // http://en.wikipedia.org/wiki/SHA-2 |
| Remco | 0:772b6de3a841 | 4 | // http://www.iwar.org.uk/comsec/resources/cipher/sha256-384-512.pdf |
| Remco | 0:772b6de3a841 | 5 | |
| Remco | 0:772b6de3a841 | 6 | #include "SHA256.h" |
| Remco | 0:772b6de3a841 | 7 | |
| Remco | 0:772b6de3a841 | 8 | inline unsigned int byte_swap(unsigned int x) |
| Remco | 0:772b6de3a841 | 9 | { |
| Remco | 0:772b6de3a841 | 10 | // unsigned int result; |
| Remco | 0:772b6de3a841 | 11 | // asm("REV %0, %1" : "=r"(result) : "r"(x)); |
| Remco | 0:772b6de3a841 | 12 | // return result |
| Remco | 0:772b6de3a841 | 13 | return __rev(x); |
| Remco | 0:772b6de3a841 | 14 | } |
| Remco | 0:772b6de3a841 | 15 | |
| Remco | 0:772b6de3a841 | 16 | inline unsigned int rotate_right(unsigned int x, int shift) |
| Remco | 0:772b6de3a841 | 17 | { |
| Remco | 0:772b6de3a841 | 18 | return (x >> shift) | (x << (32 - shift)); |
| Remco | 0:772b6de3a841 | 19 | } |
| Remco | 0:772b6de3a841 | 20 | |
| Remco | 0:772b6de3a841 | 21 | const unsigned int k[64] = { |
| Remco | 0:772b6de3a841 | 22 | 0x428A2F98, 0x71374491, 0xB5C0FBCF, 0xE9B5DBA5, 0x3956C25B, 0x59F111F1, 0x923F82A4, 0xAB1C5ED5, |
| Remco | 0:772b6de3a841 | 23 | 0xD807AA98, 0x12835B01, 0x243185BE, 0x550C7DC3, 0x72BE5D74, 0x80DEB1FE, 0x9BDC06A7, 0xC19BF174, |
| Remco | 0:772b6de3a841 | 24 | 0xE49B69C1, 0xEFBE4786, 0x0FC19DC6, 0x240CA1CC, 0x2DE92C6F, 0x4A7484AA, 0x5CB0A9DC, 0x76F988DA, |
| Remco | 0:772b6de3a841 | 25 | 0x983E5152, 0xA831C66D, 0xB00327C8, 0xBF597FC7, 0xC6E00BF3, 0xD5A79147, 0x06CA6351, 0x14292967, |
| Remco | 0:772b6de3a841 | 26 | 0x27B70A85, 0x2E1B2138, 0x4D2C6DFC, 0x53380D13, 0x650A7354, 0x766A0ABB, 0x81C2C92E, 0x92722C85, |
| Remco | 0:772b6de3a841 | 27 | 0xA2BFE8A1, 0xA81A664B, 0xC24B8B70, 0xC76C51A3, 0xD192E819, 0xD6990624, 0xF40E3585, 0x106AA070, |
| Remco | 0:772b6de3a841 | 28 | 0x19A4C116, 0x1E376C08, 0x2748774C, 0x34B0BCB5, 0x391C0CB3, 0x4ED8AA4A, 0x5B9CCA4F, 0x682E6FF3, |
| Remco | 0:772b6de3a841 | 29 | 0x748F82EE, 0x78A5636F, 0x84C87814, 0x8CC70208, 0x90BEFFFA, 0xA4506CEB, 0xBEF9A3F7, 0xC67178F2 |
| Remco | 0:772b6de3a841 | 30 | }; |
| Remco | 0:772b6de3a841 | 31 | |
| Remco | 0:772b6de3a841 | 32 | inline unsigned int s0(unsigned int x) { |
| Remco | 0:772b6de3a841 | 33 | return rotate_right(x, 7) ^ rotate_right(x, 18) ^ (x >> 3); |
| Remco | 0:772b6de3a841 | 34 | } |
| Remco | 0:772b6de3a841 | 35 | |
| Remco | 0:772b6de3a841 | 36 | inline unsigned int s1(unsigned int x) { |
| Remco | 0:772b6de3a841 | 37 | return rotate_right(x, 17) ^ rotate_right(x, 19) ^ (x >> 10); |
| Remco | 0:772b6de3a841 | 38 | } |
| Remco | 0:772b6de3a841 | 39 | |
| Remco | 0:772b6de3a841 | 40 | inline unsigned int s2(unsigned int x) { |
| Remco | 0:772b6de3a841 | 41 | return rotate_right(x, 2) ^ rotate_right(x, 13) ^ rotate_right(x, 22); |
| Remco | 0:772b6de3a841 | 42 | } |
| Remco | 0:772b6de3a841 | 43 | |
| Remco | 0:772b6de3a841 | 44 | inline unsigned int s3(unsigned int x) { |
| Remco | 0:772b6de3a841 | 45 | return rotate_right(x, 6) ^ rotate_right(x, 11) ^ rotate_right(x, 25); |
| Remco | 0:772b6de3a841 | 46 | } |
| Remco | 0:772b6de3a841 | 47 | |
| Remco | 0:772b6de3a841 | 48 | void SHA256::reset() |
| Remco | 0:772b6de3a841 | 49 | { |
| Remco | 0:772b6de3a841 | 50 | hash[0] = 0x6A09E667; |
| Remco | 0:772b6de3a841 | 51 | hash[1] = 0xBB67AE85; |
| Remco | 0:772b6de3a841 | 52 | hash[2] = 0x3C6EF372; |
| Remco | 0:772b6de3a841 | 53 | hash[3] = 0xA54FF53A; |
| Remco | 0:772b6de3a841 | 54 | hash[4] = 0x510E527F; |
| Remco | 0:772b6de3a841 | 55 | hash[5] = 0x9B05688C; |
| Remco | 0:772b6de3a841 | 56 | hash[6] = 0x1F83D9AB; |
| Remco | 0:772b6de3a841 | 57 | hash[7] = 0x5BE0CD19; |
| Remco | 0:772b6de3a841 | 58 | length = 0; |
| Remco | 0:772b6de3a841 | 59 | } |
| Remco | 0:772b6de3a841 | 60 | |
| Remco | 0:772b6de3a841 | 61 | void SHA256::append(const char* data, int size) |
| Remco | 0:772b6de3a841 | 62 | { |
| Remco | 0:772b6de3a841 | 63 | const char* end = data + size; |
| Remco | 0:772b6de3a841 | 64 | char* buffer = reinterpret_cast<char*>(w); |
| Remco | 0:772b6de3a841 | 65 | |
| Remco | 0:772b6de3a841 | 66 | // TODO: operate in words |
| Remco | 0:772b6de3a841 | 67 | |
| Remco | 0:772b6de3a841 | 68 | int index = length % 64; |
| Remco | 0:772b6de3a841 | 69 | while(data != end) { |
| Remco | 0:772b6de3a841 | 70 | int word_index = index / 4; |
| Remco | 0:772b6de3a841 | 71 | int byte_index = index % 4; |
| Remco | 0:772b6de3a841 | 72 | buffer[4 * word_index + 3 - byte_index] = *data; |
| Remco | 0:772b6de3a841 | 73 | ++index; |
| Remco | 0:772b6de3a841 | 74 | ++data; |
| Remco | 0:772b6de3a841 | 75 | if(index == 64) { |
| Remco | 0:772b6de3a841 | 76 | process_chunk(); |
| Remco | 0:772b6de3a841 | 77 | index = 0; |
| Remco | 0:772b6de3a841 | 78 | } |
| Remco | 0:772b6de3a841 | 79 | } |
| Remco | 0:772b6de3a841 | 80 | length += size; |
| Remco | 0:772b6de3a841 | 81 | } |
| Remco | 0:772b6de3a841 | 82 | |
| Remco | 0:772b6de3a841 | 83 | void SHA256::finalize() |
| Remco | 0:772b6de3a841 | 84 | { |
| Remco | 0:772b6de3a841 | 85 | int trailing = length % 64; |
| Remco | 0:772b6de3a841 | 86 | |
| Remco | 0:772b6de3a841 | 87 | // Append the bit '1' to the message |
| Remco | 0:772b6de3a841 | 88 | int last_block = trailing / 4; |
| Remco | 0:772b6de3a841 | 89 | unsigned int bit_in_block = 0x80 << (24 - (trailing % 4) * 8); |
| Remco | 0:772b6de3a841 | 90 | w[last_block] |= bit_in_block; |
| Remco | 0:772b6de3a841 | 91 | w[last_block] &= ~(bit_in_block - 1); |
| Remco | 0:772b6de3a841 | 92 | |
| Remco | 0:772b6de3a841 | 93 | // Set all other bits to zero |
| Remco | 0:772b6de3a841 | 94 | for(int i = last_block + 1; i < 15; ++i) |
| Remco | 0:772b6de3a841 | 95 | w[i] = 0; |
| Remco | 0:772b6de3a841 | 96 | |
| Remco | 0:772b6de3a841 | 97 | // Make room for the length if necessary |
| Remco | 0:772b6de3a841 | 98 | if(trailing >= 56) { |
| Remco | 0:772b6de3a841 | 99 | process_chunk(); |
| Remco | 0:772b6de3a841 | 100 | for(int i = 0; i <= last_block; ++i) |
| Remco | 0:772b6de3a841 | 101 | w[i] = 0; |
| Remco | 0:772b6de3a841 | 102 | } |
| Remco | 0:772b6de3a841 | 103 | |
| Remco | 0:772b6de3a841 | 104 | // Append the length in bits |
| Remco | 0:772b6de3a841 | 105 | w[14] = length >> (32 - 3); |
| Remco | 0:772b6de3a841 | 106 | w[15] = length << 3; |
| Remco | 0:772b6de3a841 | 107 | process_chunk(); |
| Remco | 0:772b6de3a841 | 108 | |
| Remco | 0:772b6de3a841 | 109 | // Convert the result to big endian |
| Remco | 0:772b6de3a841 | 110 | for(int i = 0; i < 8; ++i) |
| Remco | 0:772b6de3a841 | 111 | hash[i] = byte_swap(hash[i]); |
| Remco | 0:772b6de3a841 | 112 | } |
| Remco | 0:772b6de3a841 | 113 | |
| Remco | 0:772b6de3a841 | 114 | // Process a 512 bit chunk stored in w[1...15] |
| Remco | 0:772b6de3a841 | 115 | void SHA256::process_chunk() |
| Remco | 0:772b6de3a841 | 116 | { |
| Remco | 0:772b6de3a841 | 117 | // Extend the chunk to 64 x 32 bit |
| Remco | 0:772b6de3a841 | 118 | for(int i = 16; i < 64; ++i) |
| Remco | 0:772b6de3a841 | 119 | w[i] = w[i - 16] + s0(w[i - 15]) + w[i - 7] + s1(w[i - 2]); |
| Remco | 0:772b6de3a841 | 120 | |
| Remco | 0:772b6de3a841 | 121 | // Initialize using current hash |
| Remco | 0:772b6de3a841 | 122 | unsigned int a = hash[0]; |
| Remco | 0:772b6de3a841 | 123 | unsigned int b = hash[1]; |
| Remco | 0:772b6de3a841 | 124 | unsigned int c = hash[2]; |
| Remco | 0:772b6de3a841 | 125 | unsigned int d = hash[3]; |
| Remco | 0:772b6de3a841 | 126 | unsigned int e = hash[4]; |
| Remco | 0:772b6de3a841 | 127 | unsigned int f = hash[5]; |
| Remco | 0:772b6de3a841 | 128 | unsigned int g = hash[6]; |
| Remco | 0:772b6de3a841 | 129 | unsigned int h = hash[7]; |
| Remco | 0:772b6de3a841 | 130 | |
| Remco | 0:772b6de3a841 | 131 | // Main loop |
| Remco | 0:772b6de3a841 | 132 | for(int i = 0; i < 64; ++i) { |
| Remco | 0:772b6de3a841 | 133 | unsigned int maj = (a & b) ^ (a & c) ^ (b & c); |
| Remco | 0:772b6de3a841 | 134 | unsigned int ch = (e & f) ^ ((~e) & g); |
| Remco | 0:772b6de3a841 | 135 | unsigned int t1 = h + s3(e) + ch + k[i] + w[i]; |
| Remco | 0:772b6de3a841 | 136 | unsigned int t2 = maj + s2(a); |
| Remco | 0:772b6de3a841 | 137 | h = g; |
| Remco | 0:772b6de3a841 | 138 | g = f; |
| Remco | 0:772b6de3a841 | 139 | f = e; |
| Remco | 0:772b6de3a841 | 140 | e = d + t1; |
| Remco | 0:772b6de3a841 | 141 | d = c; |
| Remco | 0:772b6de3a841 | 142 | c = b; |
| Remco | 0:772b6de3a841 | 143 | b = a; |
| Remco | 0:772b6de3a841 | 144 | a = t1 + t2; |
| Remco | 0:772b6de3a841 | 145 | } |
| Remco | 0:772b6de3a841 | 146 | |
| Remco | 0:772b6de3a841 | 147 | // Update hash |
| Remco | 0:772b6de3a841 | 148 | hash[0] += a; |
| Remco | 0:772b6de3a841 | 149 | hash[1] += b; |
| Remco | 0:772b6de3a841 | 150 | hash[2] += c; |
| Remco | 0:772b6de3a841 | 151 | hash[3] += d; |
| Remco | 0:772b6de3a841 | 152 | hash[4] += e; |
| Remco | 0:772b6de3a841 | 153 | hash[5] += f; |
| Remco | 0:772b6de3a841 | 154 | hash[6] += g; |
| Remco | 0:772b6de3a841 | 155 | hash[7] += h; |
| Remco | 0:772b6de3a841 | 156 | } |
| Remco | 0:772b6de3a841 | 157 | |
| Remco | 0:772b6de3a841 | 158 |