A fine-tuned implementation of the SHA256 hashing algorithm.
Dependents: EntropySource Wallet_v1
SHA256.cpp@6:c0ed1bf37651, 2011-06-20 (annotated)
- Committer:
- Remco
- Date:
- Mon Jun 20 13:21:38 2011 +0000
- Revision:
- 6:c0ed1bf37651
- Parent:
- 3:f19b10394f9c
Who changed what in which revision?
User | Revision | Line number | New contents of line |
---|---|---|---|
Remco | 6:c0ed1bf37651 | 1 | // Author: Remco Bloemen |
Remco | 6:c0ed1bf37651 | 2 | // Based on: |
Remco | 6:c0ed1bf37651 | 3 | // http://en.wikipedia.org/wiki/SHA-2 |
Remco | 6:c0ed1bf37651 | 4 | // http://www.iwar.org.uk/comsec/resources/cipher/sha256-384-512.pdf |
Remco | 6:c0ed1bf37651 | 5 | // some of the OpenSSL optimizations |
Remco | 6:c0ed1bf37651 | 6 | |
Remco | 6:c0ed1bf37651 | 7 | #include "SHA256.h" |
Remco | 6:c0ed1bf37651 | 8 | |
Remco | 6:c0ed1bf37651 | 9 | inline unsigned int reverse_bytes(unsigned int x) |
Remco | 6:c0ed1bf37651 | 10 | { |
Remco | 6:c0ed1bf37651 | 11 | return __rev(x); |
Remco | 6:c0ed1bf37651 | 12 | } |
Remco | 6:c0ed1bf37651 | 13 | |
Remco | 6:c0ed1bf37651 | 14 | inline unsigned int rotate_right(unsigned int x, int shift) |
Remco | 6:c0ed1bf37651 | 15 | { |
Remco | 6:c0ed1bf37651 | 16 | // return (x >> shift) | (x << (32 - shift)); |
Remco | 6:c0ed1bf37651 | 17 | return __ror(x, shift); |
Remco | 6:c0ed1bf37651 | 18 | } |
Remco | 6:c0ed1bf37651 | 19 | |
Remco | 6:c0ed1bf37651 | 20 | void SHA256::reset() |
Remco | 6:c0ed1bf37651 | 21 | { |
Remco | 6:c0ed1bf37651 | 22 | hash[0] = 0x6A09E667; |
Remco | 6:c0ed1bf37651 | 23 | hash[1] = 0xBB67AE85; |
Remco | 6:c0ed1bf37651 | 24 | hash[2] = 0x3C6EF372; |
Remco | 6:c0ed1bf37651 | 25 | hash[3] = 0xA54FF53A; |
Remco | 6:c0ed1bf37651 | 26 | hash[4] = 0x510E527F; |
Remco | 6:c0ed1bf37651 | 27 | hash[5] = 0x9B05688C; |
Remco | 6:c0ed1bf37651 | 28 | hash[6] = 0x1F83D9AB; |
Remco | 6:c0ed1bf37651 | 29 | hash[7] = 0x5BE0CD19; |
Remco | 6:c0ed1bf37651 | 30 | length = 0; |
Remco | 6:c0ed1bf37651 | 31 | } |
Remco | 6:c0ed1bf37651 | 32 | |
Remco | 6:c0ed1bf37651 | 33 | void SHA256::append(const char* data, int size) |
Remco | 6:c0ed1bf37651 | 34 | { |
Remco | 6:c0ed1bf37651 | 35 | int index = length % 64; |
Remco | 6:c0ed1bf37651 | 36 | length += size; |
Remco | 6:c0ed1bf37651 | 37 | const char* end = data + size; |
Remco | 6:c0ed1bf37651 | 38 | |
Remco | 6:c0ed1bf37651 | 39 | // Word align data |
Remco | 6:c0ed1bf37651 | 40 | char* bytes = reinterpret_cast<char*>(w + (index / 4)); |
Remco | 6:c0ed1bf37651 | 41 | switch(index % 4) |
Remco | 6:c0ed1bf37651 | 42 | { |
Remco | 6:c0ed1bf37651 | 43 | // Remember to reverse! (little endian!) |
Remco | 6:c0ed1bf37651 | 44 | case 1: bytes[2] = *data++; ++index; |
Remco | 6:c0ed1bf37651 | 45 | case 2: bytes[1] = *data++; ++index; |
Remco | 6:c0ed1bf37651 | 46 | case 3: bytes[0] = *data++; ++index; |
Remco | 6:c0ed1bf37651 | 47 | case 0: break; |
Remco | 6:c0ed1bf37651 | 48 | } |
Remco | 6:c0ed1bf37651 | 49 | if(data > end) { |
Remco | 6:c0ed1bf37651 | 50 | // We have overshot reading data |
Remco | 6:c0ed1bf37651 | 51 | // but w and length are correct |
Remco | 6:c0ed1bf37651 | 52 | return; |
Remco | 6:c0ed1bf37651 | 53 | } |
Remco | 6:c0ed1bf37651 | 54 | |
Remco | 6:c0ed1bf37651 | 55 | // Index is now word alligned |
Remco | 6:c0ed1bf37651 | 56 | index /= 4; |
Remco | 6:c0ed1bf37651 | 57 | if(index == 16) { |
Remco | 6:c0ed1bf37651 | 58 | process_chunk(); |
Remco | 6:c0ed1bf37651 | 59 | index = 0; |
Remco | 6:c0ed1bf37651 | 60 | } |
Remco | 6:c0ed1bf37651 | 61 | |
Remco | 6:c0ed1bf37651 | 62 | // Process whole words |
Remco | 6:c0ed1bf37651 | 63 | int num_words = (end - data) / 4; |
Remco | 6:c0ed1bf37651 | 64 | const unsigned int* data_words = reinterpret_cast<const unsigned int*>(data); |
Remco | 6:c0ed1bf37651 | 65 | const unsigned int* data_words_end = data_words + num_words; |
Remco | 6:c0ed1bf37651 | 66 | while(data_words != data_words_end) |
Remco | 6:c0ed1bf37651 | 67 | { |
Remco | 6:c0ed1bf37651 | 68 | w[index++] = reverse_bytes(*data_words++); |
Remco | 6:c0ed1bf37651 | 69 | if(index == 16) { |
Remco | 6:c0ed1bf37651 | 70 | process_chunk(); |
Remco | 6:c0ed1bf37651 | 71 | index = 0; |
Remco | 6:c0ed1bf37651 | 72 | } |
Remco | 6:c0ed1bf37651 | 73 | } |
Remco | 6:c0ed1bf37651 | 74 | |
Remco | 6:c0ed1bf37651 | 75 | // Process trailing data bytes |
Remco | 6:c0ed1bf37651 | 76 | // Again, we won't worry about overshooting data |
Remco | 6:c0ed1bf37651 | 77 | w[index] = reverse_bytes(*data_words); |
Remco | 6:c0ed1bf37651 | 78 | } |
Remco | 6:c0ed1bf37651 | 79 | |
Remco | 6:c0ed1bf37651 | 80 | void SHA256::finalize() |
Remco | 6:c0ed1bf37651 | 81 | { |
Remco | 6:c0ed1bf37651 | 82 | int trailing = length % 64; |
Remco | 6:c0ed1bf37651 | 83 | |
Remco | 6:c0ed1bf37651 | 84 | // Append the bit '1' to the message |
Remco | 6:c0ed1bf37651 | 85 | int last_block = trailing / 4; |
Remco | 6:c0ed1bf37651 | 86 | unsigned int bit_in_block = 0x80 << (24 - (trailing % 4) * 8); |
Remco | 6:c0ed1bf37651 | 87 | w[last_block] |= bit_in_block; |
Remco | 6:c0ed1bf37651 | 88 | |
Remco | 6:c0ed1bf37651 | 89 | // Set all other bits to zero |
Remco | 6:c0ed1bf37651 | 90 | w[last_block] &= ~(bit_in_block - 1); |
Remco | 6:c0ed1bf37651 | 91 | for(int i = last_block + 1; i < 16; ++i) |
Remco | 6:c0ed1bf37651 | 92 | w[i] = 0; |
Remco | 6:c0ed1bf37651 | 93 | |
Remco | 6:c0ed1bf37651 | 94 | // Make room for the length if necessary |
Remco | 6:c0ed1bf37651 | 95 | if(trailing >= 56) { |
Remco | 6:c0ed1bf37651 | 96 | process_chunk(); |
Remco | 6:c0ed1bf37651 | 97 | for(int i = 0; i <= last_block; ++i) |
Remco | 6:c0ed1bf37651 | 98 | w[i] = 0; |
Remco | 6:c0ed1bf37651 | 99 | } |
Remco | 6:c0ed1bf37651 | 100 | |
Remco | 6:c0ed1bf37651 | 101 | // Append the length in bits |
Remco | 6:c0ed1bf37651 | 102 | w[14] = length >> (32 - 3); |
Remco | 6:c0ed1bf37651 | 103 | w[15] = length << 3; |
Remco | 6:c0ed1bf37651 | 104 | process_chunk(); |
Remco | 6:c0ed1bf37651 | 105 | |
Remco | 6:c0ed1bf37651 | 106 | // Convert the result to big endian |
Remco | 6:c0ed1bf37651 | 107 | for(int i = 0; i < 8; ++i) |
Remco | 6:c0ed1bf37651 | 108 | hash[i] = reverse_bytes(hash[i]); |
Remco | 6:c0ed1bf37651 | 109 | } |
Remco | 6:c0ed1bf37651 | 110 | |
Remco | 6:c0ed1bf37651 | 111 | #define s0(x) (rotate_right(x, 7) ^ rotate_right(x, 18) ^ (x >> 3)) |
Remco | 6:c0ed1bf37651 | 112 | #define s1(x) (rotate_right(x, 17) ^ rotate_right(x, 19) ^ (x >> 10)) |
Remco | 6:c0ed1bf37651 | 113 | #define s2(x) (rotate_right(x, 2) ^ rotate_right(x, 13) ^ rotate_right(x, 22)) |
Remco | 6:c0ed1bf37651 | 114 | #define s3(x) (rotate_right(x, 6) ^ rotate_right(x, 11) ^ rotate_right(x, 25)) |
Remco | 6:c0ed1bf37651 | 115 | #define maj(a,b,c) ((a & b) ^ (a & c) ^ (b & c)) |
Remco | 6:c0ed1bf37651 | 116 | #define ch(a,b,c) ((a & b) ^ ((~a) & c)) |
Remco | 6:c0ed1bf37651 | 117 | |
Remco | 6:c0ed1bf37651 | 118 | const unsigned int k[64] = { |
Remco | 6:c0ed1bf37651 | 119 | 0x428A2F98, 0x71374491, 0xB5C0FBCF, 0xE9B5DBA5, 0x3956C25B, 0x59F111F1, 0x923F82A4, 0xAB1C5ED5, |
Remco | 6:c0ed1bf37651 | 120 | 0xD807AA98, 0x12835B01, 0x243185BE, 0x550C7DC3, 0x72BE5D74, 0x80DEB1FE, 0x9BDC06A7, 0xC19BF174, |
Remco | 6:c0ed1bf37651 | 121 | 0xE49B69C1, 0xEFBE4786, 0x0FC19DC6, 0x240CA1CC, 0x2DE92C6F, 0x4A7484AA, 0x5CB0A9DC, 0x76F988DA, |
Remco | 6:c0ed1bf37651 | 122 | 0x983E5152, 0xA831C66D, 0xB00327C8, 0xBF597FC7, 0xC6E00BF3, 0xD5A79147, 0x06CA6351, 0x14292967, |
Remco | 6:c0ed1bf37651 | 123 | 0x27B70A85, 0x2E1B2138, 0x4D2C6DFC, 0x53380D13, 0x650A7354, 0x766A0ABB, 0x81C2C92E, 0x92722C85, |
Remco | 6:c0ed1bf37651 | 124 | 0xA2BFE8A1, 0xA81A664B, 0xC24B8B70, 0xC76C51A3, 0xD192E819, 0xD6990624, 0xF40E3585, 0x106AA070, |
Remco | 6:c0ed1bf37651 | 125 | 0x19A4C116, 0x1E376C08, 0x2748774C, 0x34B0BCB5, 0x391C0CB3, 0x4ED8AA4A, 0x5B9CCA4F, 0x682E6FF3, |
Remco | 6:c0ed1bf37651 | 126 | 0x748F82EE, 0x78A5636F, 0x84C87814, 0x8CC70208, 0x90BEFFFA, 0xA4506CEB, 0xBEF9A3F7, 0xC67178F2 |
Remco | 6:c0ed1bf37651 | 127 | }; |
Remco | 6:c0ed1bf37651 | 128 | |
Remco | 6:c0ed1bf37651 | 129 | #define ROUND(a,b,c,d,e,f,g,h,i) \ |
Remco | 6:c0ed1bf37651 | 130 | h += w[i];\ |
Remco | 6:c0ed1bf37651 | 131 | h += *K++;\ |
Remco | 6:c0ed1bf37651 | 132 | h += s3(e); \ |
Remco | 6:c0ed1bf37651 | 133 | h += ch(e, f, g); \ |
Remco | 6:c0ed1bf37651 | 134 | d += h;\ |
Remco | 6:c0ed1bf37651 | 135 | h += s2(a);\ |
Remco | 6:c0ed1bf37651 | 136 | h += maj(a, b, c); |
Remco | 6:c0ed1bf37651 | 137 | |
Remco | 6:c0ed1bf37651 | 138 | #define W(n) w[(n) & 0xf] |
Remco | 6:c0ed1bf37651 | 139 | |
Remco | 6:c0ed1bf37651 | 140 | #define ROUND2(a,b,c,d,e,f,g,h,i) \ |
Remco | 6:c0ed1bf37651 | 141 | W(i) += s0(W(i+1)) + W(i+9) + s1(W(i+14));\ |
Remco | 6:c0ed1bf37651 | 142 | h += W(i); \ |
Remco | 6:c0ed1bf37651 | 143 | h += *K++;\ |
Remco | 6:c0ed1bf37651 | 144 | h += s3(e);\ |
Remco | 6:c0ed1bf37651 | 145 | h += ch(e, f, g); \ |
Remco | 6:c0ed1bf37651 | 146 | d += h;\ |
Remco | 6:c0ed1bf37651 | 147 | h += s2(a);\ |
Remco | 6:c0ed1bf37651 | 148 | h += maj(a, b, c); |
Remco | 6:c0ed1bf37651 | 149 | |
Remco | 6:c0ed1bf37651 | 150 | // Process a 512 bit chunk stored in w[1...15] |
Remco | 6:c0ed1bf37651 | 151 | void SHA256::process_chunk() |
Remco | 6:c0ed1bf37651 | 152 | { |
Remco | 6:c0ed1bf37651 | 153 | // Initialize using current hash |
Remco | 6:c0ed1bf37651 | 154 | unsigned int a = hash[0]; |
Remco | 6:c0ed1bf37651 | 155 | unsigned int b = hash[1]; |
Remco | 6:c0ed1bf37651 | 156 | unsigned int c = hash[2]; |
Remco | 6:c0ed1bf37651 | 157 | unsigned int d = hash[3]; |
Remco | 6:c0ed1bf37651 | 158 | unsigned int e = hash[4]; |
Remco | 6:c0ed1bf37651 | 159 | unsigned int f = hash[5]; |
Remco | 6:c0ed1bf37651 | 160 | unsigned int g = hash[6]; |
Remco | 6:c0ed1bf37651 | 161 | unsigned int h = hash[7]; |
Remco | 6:c0ed1bf37651 | 162 | |
Remco | 6:c0ed1bf37651 | 163 | // Main loop |
Remco | 6:c0ed1bf37651 | 164 | const unsigned int* K = k; |
Remco | 6:c0ed1bf37651 | 165 | const unsigned int* K_end = k + 64; |
Remco | 6:c0ed1bf37651 | 166 | ROUND(a,b,c,d,e,f,g,h,0); |
Remco | 6:c0ed1bf37651 | 167 | ROUND(h,a,b,c,d,e,f,g,1); |
Remco | 6:c0ed1bf37651 | 168 | ROUND(g,h,a,b,c,d,e,f,2); |
Remco | 6:c0ed1bf37651 | 169 | ROUND(f,g,h,a,b,c,d,e,3); |
Remco | 6:c0ed1bf37651 | 170 | ROUND(e,f,g,h,a,b,c,d,4); |
Remco | 6:c0ed1bf37651 | 171 | ROUND(d,e,f,g,h,a,b,c,5); |
Remco | 6:c0ed1bf37651 | 172 | ROUND(c,d,e,f,g,h,a,b,6); |
Remco | 6:c0ed1bf37651 | 173 | ROUND(b,c,d,e,f,g,h,a,7); |
Remco | 6:c0ed1bf37651 | 174 | ROUND(a,b,c,d,e,f,g,h,8); |
Remco | 6:c0ed1bf37651 | 175 | ROUND(h,a,b,c,d,e,f,g,9); |
Remco | 6:c0ed1bf37651 | 176 | ROUND(g,h,a,b,c,d,e,f,10); |
Remco | 6:c0ed1bf37651 | 177 | ROUND(f,g,h,a,b,c,d,e,11); |
Remco | 6:c0ed1bf37651 | 178 | ROUND(e,f,g,h,a,b,c,d,12); |
Remco | 6:c0ed1bf37651 | 179 | ROUND(d,e,f,g,h,a,b,c,13); |
Remco | 6:c0ed1bf37651 | 180 | ROUND(c,d,e,f,g,h,a,b,14); |
Remco | 6:c0ed1bf37651 | 181 | ROUND(b,c,d,e,f,g,h,a,15); |
Remco | 6:c0ed1bf37651 | 182 | do { |
Remco | 6:c0ed1bf37651 | 183 | ROUND2(a,b,c,d,e,f,g,h,0); |
Remco | 6:c0ed1bf37651 | 184 | ROUND2(h,a,b,c,d,e,f,g,1); |
Remco | 6:c0ed1bf37651 | 185 | ROUND2(g,h,a,b,c,d,e,f,2); |
Remco | 6:c0ed1bf37651 | 186 | ROUND2(f,g,h,a,b,c,d,e,3); |
Remco | 6:c0ed1bf37651 | 187 | ROUND2(e,f,g,h,a,b,c,d,4); |
Remco | 6:c0ed1bf37651 | 188 | ROUND2(d,e,f,g,h,a,b,c,5); |
Remco | 6:c0ed1bf37651 | 189 | ROUND2(c,d,e,f,g,h,a,b,6); |
Remco | 6:c0ed1bf37651 | 190 | ROUND2(b,c,d,e,f,g,h,a,7); |
Remco | 6:c0ed1bf37651 | 191 | ROUND2(a,b,c,d,e,f,g,h,8); |
Remco | 6:c0ed1bf37651 | 192 | ROUND2(h,a,b,c,d,e,f,g,9); |
Remco | 6:c0ed1bf37651 | 193 | ROUND2(g,h,a,b,c,d,e,f,10); |
Remco | 6:c0ed1bf37651 | 194 | ROUND2(f,g,h,a,b,c,d,e,11); |
Remco | 6:c0ed1bf37651 | 195 | ROUND2(e,f,g,h,a,b,c,d,12); |
Remco | 6:c0ed1bf37651 | 196 | ROUND2(d,e,f,g,h,a,b,c,13); |
Remco | 6:c0ed1bf37651 | 197 | ROUND2(c,d,e,f,g,h,a,b,14); |
Remco | 6:c0ed1bf37651 | 198 | ROUND2(b,c,d,e,f,g,h,a,15); |
Remco | 6:c0ed1bf37651 | 199 | } while(K != K_end); |
Remco | 6:c0ed1bf37651 | 200 | |
Remco | 6:c0ed1bf37651 | 201 | // Update hash |
Remco | 6:c0ed1bf37651 | 202 | hash[0] += a; |
Remco | 6:c0ed1bf37651 | 203 | hash[1] += b; |
Remco | 6:c0ed1bf37651 | 204 | hash[2] += c; |
Remco | 6:c0ed1bf37651 | 205 | hash[3] += d; |
Remco | 6:c0ed1bf37651 | 206 | hash[4] += e; |
Remco | 6:c0ed1bf37651 | 207 | hash[5] += f; |
Remco | 6:c0ed1bf37651 | 208 | hash[6] += g; |
Remco | 6:c0ed1bf37651 | 209 | hash[7] += h; |
Remco | 6:c0ed1bf37651 | 210 | } |
Remco | 6:c0ed1bf37651 | 211 | |
Remco | 6:c0ed1bf37651 | 212 | std::string SHA256::hexString() |
Remco | 6:c0ed1bf37651 | 213 | { |
Remco | 6:c0ed1bf37651 | 214 | const char* hex = "0123456789abcdef"; |
Remco | 6:c0ed1bf37651 | 215 | std::string hexstr(64, '0'); |
Remco | 6:c0ed1bf37651 | 216 | for(int i = 0; i < 32; ++i) { |
Remco | 6:c0ed1bf37651 | 217 | hexstr[2 * i + 0] = hex[digest()[i] >> 4]; |
Remco | 6:c0ed1bf37651 | 218 | hexstr[2 * i + 1] = hex[digest()[i] & 0xf]; |
Remco | 6:c0ed1bf37651 | 219 | } |
Remco | 6:c0ed1bf37651 | 220 | return hexstr; |
Remco | 6:c0ed1bf37651 | 221 | } |