fork download 
  1. #define TEST
  2.  
  3. // sha.h
  4. #ifndef SHA_256_H_INCLUDED
  5. #define SHA_256_H_INCLUDED
  6.  
  7. // This is a relatively straightforward implementation of SHA-256. It makes no particular
  8. // attempt at optimization, instead aiming toward easy verification against the standard.
  9. // To that end, many of the variable names are identical to those used in FIPS 180-2 and
  10. // FIPS 180-3. 
  11. //
  12. // The code should be fairly portable, within a few limitations:
  13. // 1. It requires that 'char' have 8 bits. In theory this is avoidable, but I don't think
  14. // it's worth the bother.
  15. // 2. It only deals with inputs in (8-bit) bytes. In theory, SHA-256 can deal with a number of 
  16. // bits that's not a multiple of 8, but I've never needed it. Since the padding always results
  17. // in a byte-sized stream, the only parts that would need changing would be reading and padding
  18. // the input. The main hashing portion would be unaffected.
  19. //
  20. // Originally written in February 2008 for SHA-1.
  21. // Converted to SHA-256 sometime later (sorry, I don't remember exactly when).
  22. // 
  23. // You can use this software any way you want to, with following limitations
  24. // (shamelessly stolen from the Boost software license):
  25. //
  26. // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  27. // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  28. // FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
  29. // SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
  30. // FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
  31. // ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
  32. // DEALINGS IN THE SOFTWARE.
  33. // 
  34. // If you put this to real use, I'd be happy to hear about it. If you find a bug, 
  35. // I'd be interested in hearing about that too. There's even a pretty good chance 
  36. // that I'll try to fix it, though I certainly can't guarantee that.
  37. // 
  38. #include <algorithm>
  39. #include <vector>
  40. #include <string>
  41. #include <assert.h>
  42. #include <iostream>
  43. #include <sstream>
  44. #include <iomanip>
  45.  
  46. #if defined(_MSC_VER) && _MSC_VER < 1600
  47. typedef unsigned int uint32_t;
  48. typedef unsigned __int64 uint64_t;
  49. #else
  50. #include <stdint.h>
  51. #endif
  52.  
  53. namespace crypto { 
  54. namespace {
  55.     struct ternary_operator { 
  56.         virtual uint32_t operator()(uint32_t x, uint32_t y, uint32_t z) = 0;
  57.     };
  58. }
  59.  
  60. class sha256 { 
  61.     static const size_t hash_size = 8;
  62.     static const size_t min_pad = 64;
  63.     static const size_t block_bits = 512;
  64.     static const size_t block_bytes = block_bits / 8;
  65.     static const size_t block_words = block_bytes / 4;
  66.  
  67.     std::vector<uint32_t> K;
  68.     std::vector<uint32_t> H;
  69.     std::vector<uint32_t> W;
  70.     std::vector<ternary_operator *> fs;
  71. //    uint32_t a, b, c, d, e, T;
  72. 	std::vector<uint32_t> temp;
  73.  
  74.     static const size_t block_size = 16;
  75.     static const size_t bytes_per_word = 4;
  76.     size_t total_size;
  77.  
  78.     // hash a 512-bit block of input.
  79.     //
  80.     void hash_block(std::vector<uint32_t> const &block);
  81.  
  82.     // Pad the input to a multiple of 512 bits, and add the length
  83.     // in binary to the end.
  84.     static std::string pad(std::string const &input);
  85.  
  86.     // Turn 64 bytes into a block of 16 uint32_t's.
  87.     std::vector<uint32_t> make_block(std::string const &in);
  88.  
  89. public:
  90.     // Construct a SHA-256 object. More expensive that typical 
  91.     // ctor, but not expected to be copied a lot or anything
  92.     // like that, so it should be fairly harmless.
  93.     sha256();
  94.  
  95.     // Hash a string. You get the result as a vector<uint32_t>. It's 
  96.     // a fairly small vector, so even if your compiler doesn't do
  97.     // return-value optimization, the time for copying isn't like to 
  98.     // be significant.
  99.     // 
  100.     std::vector<uint32_t> operator()(std::string const &input);
  101.  
  102.     friend std::ostream &operator<<(std::ostream &os, sha256 const &s);
  103. };
  104. }
  105.  
  106. #endif
  107.  
  108. // sha256.cpp
  109.  
  110. //#include "sha.h"
  111.  
  112. namespace crypto {
  113. namespace {
  114. 	uint32_t word(int a, int b, int c, int d) {
  115. 		a &= 0xff;
  116. 		b &= 0xff;
  117. 		c &= 0xff;
  118. 		d &= 0xff;
  119. 		int val =  a << 24 | b << 16 | c << 8 | d;
  120. 		return val;
  121. 	}
  122.  
  123. 	uint32_t ROTR(uint32_t number, unsigned bits) { 
  124. 		return (number >> bits) | (number << (32-bits));
  125. 	}
  126.  
  127. 	uint32_t f1(uint32_t x, uint32_t y, uint32_t z) { 
  128. 		return (x & y) ^ (~x & z); //return (x & y) ^ (~x & z);
  129. 	}
  130. 	uint32_t f2(uint32_t x, uint32_t y, uint32_t z) { 
  131. 		return (x & y) ^ (x&z) ^ (y&z);
  132. 	}
  133. 	uint32_t f3(uint32_t x) { 
  134. 		return ROTR(x, 2) ^ ROTR(x, 13) ^ ROTR(x, 22);	
  135. 	}
  136. 	uint32_t f4(uint32_t x) { 
  137. 		return ROTR(x, 6) ^ ROTR(x, 11) ^ ROTR(x, 25);
  138. 	}
  139. 	uint32_t f5(uint32_t x) { 
  140. 		return ROTR(x, 7) ^ ROTR(x, 18) ^ (x >> 3);
  141. 	}
  142. 	uint32_t f6(uint32_t x) { 
  143. 		return ROTR(x, 17) ^ ROTR(x, 19) ^ (x >> 10);
  144. 	}
  145.  
  146. 	uint32_t add(uint32_t a, uint32_t b) {
  147. 		return a+b;
  148. 	}
  149. }
  150.  
  151. // Pad the input to a multiple of 512 bits, and add the length
  152. // in binary to the end.
  153. std::string sha256::pad(std::string const &input) {
  154. 	uint64_t length = input.size() * 8 + 1;
  155. 	size_t remainder = length % block_bits;
  156. 	size_t k = (remainder <= 448) ? 448 - remainder : 960 - remainder;
  157.  
  158. 	std::string padding("\x80");
  159. 	padding.append(std::string(k/8, '\0'));
  160. 	--length;
  161.  
  162. 	for (int i=sizeof(length)-1; i>-1; i--) {
  163. 		unsigned char byte = length >> (i*8) & 0xff;
  164. 		padding.push_back(byte);
  165. 	}
  166.  
  167. 	std::string ret(input+padding);
  168. 	return ret;
  169. }
  170.  
  171. // Turn 64 bytes into a vector of 16 uint32_t's.
  172. std::vector<uint32_t> sha256::make_block(std::string const &in) { 
  173. 	assert(in.size() >= block_bytes);
  174.  
  175. 	std::vector<uint32_t> ret(block_words);
  176.  
  177. 	for (size_t i=0; i<block_words; i++) {
  178. 		size_t s = i*4;
  179. 		ret[i] = word(in[s], in[s+1], in[s+2], in[s+3]);
  180. 	}
  181. 	return ret;
  182. }
  183.  
  184. sha256::sha256() : H(hash_size), W(64), temp(10) { 
  185. 	static const uint32_t H0[hash_size] = {
  186. 		0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a, 
  187. 		0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19
  188. 	};
  189.  
  190. 	std::copy(H0, H0+hash_size, H.begin());
  191. }
  192.  
  193. void sha256::hash_block(std::vector<uint32_t> const &block) {
  194. 	static const uint32_t K[] = {
  195. 		0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5,
  196. 		0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5, 
  197. 		0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3,
  198. 		0x72be5d74, 0x80deb1fe,	0x9bdc06a7, 0xc19bf174,
  199. 		0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc,
  200. 		0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
  201. 		0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7,
  202. 		0xc6e00bf3, 0xd5a79147,	0x06ca6351, 0x14292967,
  203. 		0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13,
  204. 		0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
  205. 		0xa2bfe8a1, 0xa81a664b,	0xc24b8b70, 0xc76c51a3,
  206. 		0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,	
  207. 		0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5,
  208. 		0x391c0cb3, 0x4ed8aa4a,	0x5b9cca4f, 0x682e6ff3,
  209. 		0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208,
  210. 		0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2
  211. 	};
  212.  
  213. 	assert(block.size() == 16);
  214.  
  215. 	std::copy(block.begin(), block.end(), W.begin());
  216. 	for (int t=16; t<64; ++t) 
  217. 		W[t] = f6(W[t-2]) + W[t-7] + f5(W[t-15]) + W[t-16];
  218. 	std::copy(H.begin(), H.end(), temp.begin());
  219.  
  220. 	for (int t=0; t<64; ++t) {
  221. 		temp[8] = temp[7]+f4(temp[4]) + f1(temp[4],temp[5],temp[6])+K[t]+W[t];
  222. 		temp[9] = f3(temp[0]) + f2(temp[0], temp[1], temp[2]);
  223. 		temp[7] = temp[6];
  224. 		temp[6] = temp[5];
  225. 		temp[5] = temp[4];
  226. 		temp[4] = temp[3] + temp[8];
  227. 		temp[3] = temp[2];
  228. 		temp[2] = temp[1];
  229. 		temp[1] = temp[0];
  230. 		temp[0] = temp[8] + temp[9];
  231. 	}
  232. 	std::transform(H.begin(), H.end(), temp.begin(), H.begin(), add);
  233. }
  234.  
  235. // Take a `std::string` as input, produce a SHA-256 hash as a vector of 16 uint32_ts'.
  236. //
  237. std::vector<uint32_t> sha256::operator()(std::string const &input) { 
  238. 	std::string temp(pad(input));
  239. 	std::vector<uint32_t> block(block_size);
  240.  
  241. 	size_t num = temp.size()/block_bytes;
  242.  
  243. 	for (unsigned block_num=0; block_num<num; block_num++) {
  244. 		size_t s;
  245. 		for (size_t i=0; i<block_size; i++) {
  246. 			s = block_num*block_bytes+i*4;
  247. 			block[i] = word(temp[s], temp[s+1], temp[s+2], temp[s+3]);
  248. 		}
  249. 		hash_block(block);	
  250. 	}
  251. 	return H;
  252. }
  253.  
  254. std::ostream &operator<<(std::ostream &os, sha256 const &s) { 
  255. 	// Display hash result in hex.
  256. 	for (size_t i=0; i<(s.H).size(); i++)
  257. 		os << std::fixed << std::setprecision(8) << std::hex << std::setfill('0') << (s.H)[i] << " ";
  258. 	return os << std::dec << std::setfill(' ') << "\n";
  259. }
  260. }
  261.  
  262. #ifdef TEST
  263. #include <iostream>
  264. #include <iomanip>
  265. #include <string>
  266. #include <sstream>
  267.  
  268. // A minimal test harness to check that it's working correctly. Strictly black-box
  269. // testing, with no attempt at things like coverage analysis. Nonetheless, I believe
  270. // it should cover most of the code -- the core hashing code all gets used for every
  271. // possible value. The padding code should be tested fairly thoroughly as well -- the
  272. // first test is a fairly simple case, and the second the more complex one (where the 
  273. // padding requires adding another block).
  274. class tester {
  275. 	bool verify(uint32_t *test_val, std::vector<uint32_t> const &hash, std::ostream &os) {
  276. 		// Verify that a result matches a test value and report result.
  277. 		for (size_t i=0; i<hash.size(); i++)
  278. 			if (hash[i] != test_val[i]) {
  279. 				os << "Mismatch. Expected: " << test_val[i] << ", but found: " << hash[i] << "\n";
  280. 				return false;
  281. 			}
  282. 			os << "Message digest Verified.\n\n";
  283. 			return true;
  284. 	}
  285.  
  286. public:
  287.  
  288. 	bool operator()(uint32_t *test_val, std::string const &input) {
  289. 		std::cout << "Testing hashing from string:\n\"" << input << "\"\n";
  290. 		crypto::sha256 hasher1;
  291. 		std::vector<uint32_t> hash = hasher1(input);
  292. 		std::cout << "Message digest is:\n\t" << hasher1;
  293. 		return verify(test_val, hash, std::cerr);
  294. 	}
  295. };
  296.  
  297. int main() {
  298.  
  299. 	char const *input1 = "abc";
  300. 	uint32_t result1[] = {0xba7816bf, 0x8f01cfea, 0x414140de, 0x5dae2223, 0xb00361a3, 0x96177a9c, 0xb410ff61, 0xf20015ad};
  301.  
  302. 	char const *input2 = "abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq";
  303. 	uint32_t result2[] = {0x248d6a61, 0xd20638b8, 0xe5c02693, 0x0c3e6039, 0xa33ce459, 0x64ff2167, 0xf6ecedd4, 0x19db06c1};
  304.  
  305. 	bool correct = tester()(result1, input1);
  306. 	correct &= tester()(result2, input2);
  307. 	if (correct)
  308. 		std::cerr << "All Tests passed!\n";
  309. 	else
  310. 		std::cerr << "Test Failed!\n";
  311. }
  312. #endif
  313.  
Success #stdin #stdout 0.01s 2820KB
comments (?)
stdin 
Standard input is empty
stdout 
Testing hashing from string:
"abc"
Message digest is:
	ba7816bf 8f01cfea 414140de 5dae2223 b00361a3 96177a9c b410ff61 f20015ad 
Testing hashing from string:
"abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq"
Message digest is:
	248d6a61 d20638b8 e5c02693 c3e6039 a33ce459 64ff2167 f6ecedd4 19db06c1
https://ideone.com/E2g9Y
language:
C++ (gcc 8.3)
created:
13 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!