Create a gist now

Instantly share code, notes, and snippets.

@anthay /sha1.h
Created Oct 25, 2010

#ifndef SHA1_H_INCLUDED
#define SHA1_H_INCLUDED
/* calculate SHA-1 digest
Copyright (c) 2010 Anthony C. Hay
Distributed under the BSD license, see:
http://creativecommons.org/licenses/BSD/ */
#include <cstddef>
#include <stdexcept>
namespace nettle_soup {
class sha1 {
public:
sha1()
{
reset();
}
// digest 'len' bytes in given 'buf'; may be called zero or more times
void update(const void * buf, std::size_t len)
{
if (finalized_) {
/* the correct usage for this class is: c'tor or reset() followed
by zero or more calls to update() followed by zero or more
calls to final_value() followed, if required, by zero or more
calls to reset(), and so on; you may not digest more data after
the first call to final_value() without an interveining call
to reset() */
throw std::logic_error("sha1::update() called after call to sha1::final_value()");
}
// first fill block_, if we can, then process it
const unsigned char * src = reinterpret_cast<const unsigned char *>(buf);
unsigned char * blk = block_ + (total_ & 63);
unsigned char * end = block_ + 64;
total_ += len;
while (len && blk < end) {
*blk++ = *src++;
--len;
}
if (blk < end)
return; // block_ not yet full
process_block(block_, h_);
// process all remaining full 64-byte blocks in given data
while (len >= 64) {
process_block(src, h_);
src += 64;
len -= 64;
}
// copy any unprocessed data to block_ so it can be processed next time
blk = block_;
end = block_ + len;
while (blk < end)
*blk++ = *src++;
}
// the digest result is in the form of 5 32-bit unsigned ints
typedef unsigned digest_type[5];
// return a const ref to the digest result; may be called 0 or more times
const digest_type & final_value()
{
if (!finalized_) {
unsigned char total_bits[8];
big_endian(total_ << 3, total_bits);
// write a 1-bit and suficient 0-bits to reach 8 bytes from block end
static const unsigned char pad[64] = { 0x80 };
update(pad, 1 + (63 & (55 - (int)(total_ & 63))));
// final 8 bytes contain total number of user data bits digested
update(total_bits, 8);
finalized_ = true;
}
return h_;
}
// call reset() if you want to reuse the object (you may not call update()
// after the first call to final_value() without an interveining call to
// reset() - if you do, update() will throw)
void reset()
{
h_[0] = 0x67452301;
h_[1] = 0xEFCDAB89;
h_[2] = 0x98BADCFE;
h_[3] = 0x10325476;
h_[4] = 0xC3D2E1F0;
total_ = 0;
finalized_ = false;
}
private:
digest_type h_; // digest accumulated here
unsigned char block_[64]; // copy of data waiting to be processed
unsigned long long total_; // total number of bytes processsed so far
bool finalized_; // to ensure we only finalize once
// return given 'x' rotated left by 'count' bits
unsigned rol(unsigned x, unsigned count) const
{
return (x << count) | (x >> (32 - count));
}
// write given 'n' to given 8-byte 'buf' in big-endian byte order
void big_endian(unsigned long long n, unsigned char * buf) const
{
for (int i = 7; i >= 0; --i) {
buf[i] = static_cast<unsigned char>(n);
n >>= 8;
}
}
// apply SHA-1 algorithm to one full 64-byte 'block'; update given 5-word 'h'
// (lookup "FIPS 180-1" for details of the SHA-1 algorithm)
void process_block(const unsigned char * block, unsigned * h) const
{
unsigned w[80];
unsigned * p = w;
for (; p < w+16; ++p, block += 4)
*p = (block[0] << 24) | (block[1] << 16) | (block[2] << 8) | block[3];
int i = 16;
for (; i < 80; ++i)
*p++ = rol(w[i-3] ^ w[i-8] ^ w[i-14] ^ w[i-16], 1);
unsigned a = h[0];
unsigned b = h[1];
unsigned c = h[2];
unsigned d = h[3];
unsigned e = h[4];
for (i = 0; i < 20; ++i) {
const unsigned newa = rol(a, 5) + e + w[i] + 0x5A827999 + (((c ^ d) & b) ^ d);
e = d; d = c; c = rol(b, 30); b = a; a = newa;
}
for (; i < 40; ++i) {
const unsigned newa = rol(a, 5) + e + w[i] + 0x6ED9EBA1 + (b ^ c ^ d);
e = d; d = c; c = rol(b, 30); b = a; a = newa;
}
for (; i < 60; ++i) {
const unsigned newa = rol(a, 5) + e + w[i] + 0x8F1BBCDC + ((b & c) + (d & (b ^ c)));
e = d; d = c; c = rol(b, 30); b = a; a = newa;
}
for (; i < 80; ++i) {
const unsigned newa = rol(a, 5) + e + w[i] + 0xCA62C1D6 + (b ^ c ^ d);
e = d; d = c; c = rol(b, 30); b = a; a = newa;
}
h[0] += a;
h[1] += b;
h[2] += c;
h[3] += d;
h[4] += e;
}
};
}
#endif
// unit test for nettle_soup::sha1
#include "sha1.h"
using nettle_soup::sha1;
#include <iostream>
#include <sstream>
#include <iomanip>
unsigned g_test_count; // count of number of unit tests executed
unsigned g_fault_count; // count of number of unit tests that fail
template <typename T1, typename T2>
void test_equal_(const T1 & value, const T2 & expected_value, const char * file, int line)
{
++g_test_count;
if (value != expected_value) {
std::cout
<< file << '(' << line << ") : "
<< " expected " << expected_value
<< ", got " << value
<< '\n';
++g_fault_count;
}
}
// write a message to std::cout if value != expected_value
#define TEST_EQUAL(expected_value, value) test_equal_(value, expected_value, __FILE__, __LINE__)
// return the hex ASCII string representation of the given array of 5 unsigned ints
std::string to_string(const unsigned int (&d)[5])
{
std::ostringstream s;
s << std::hex << std::setfill('0');
for (int i = 0; i < 5; ++i)
s << std::setw(8) << d[i];
return s.str();
}
// return the SHA-1 digest of the given string as a hex ASCII string
std::string sha1_str(const std::string & s)
{
sha1 digest;
digest.update(s.c_str(), s.size());
return to_string(digest.final_value());
}
void test_assumptions()
{
// the implementation requires these types be these sizes
TEST_EQUAL(32, sizeof(unsigned) * CHAR_BIT);
TEST_EQUAL(64, sizeof(unsigned long long) * CHAR_BIT);
}
void test_known_values()
{
TEST_EQUAL("da39a3ee5e6b4b0d3255bfef95601890afd80709", sha1_str(""));
TEST_EQUAL("356a192b7913b04c54574d18c28d46e6395428ab", sha1_str("1"));
TEST_EQUAL("a9993e364706816aba3e25717850c26c9cd0d89d", sha1_str("abc"));
TEST_EQUAL("9b56d519ccd9e1e5b2a725e186184cdc68de0731", sha1_str("Hello."));
TEST_EQUAL("32d10c7b8cf96570ca04ce37f2a19d84240d3a89", sha1_str("abcdefghijklmnopqrstuvwxyz"));
TEST_EQUAL("2fd4e1c67a2d28fced849ee1bb76e7391b93eb12", sha1_str("The quick brown fox jumps over the lazy dog"));
TEST_EQUAL("de9f2c7fd25e1b3afad3e85a0bd17d9b100db4b3", sha1_str("The quick brown fox jumps over the lazy cog"));
TEST_EQUAL("f042dc98a62cbad68dbe21f11bbc1e9d416d2bf6", sha1_str("9b56d519ccd9e1e5b2a725e186184cdc68de0731"));
TEST_EQUAL("84983e441c3bd26ebaae4aa1f95129e5e54670f1",
sha1_str("abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq"));
TEST_EQUAL("761c457bf73b14d27e9e9265c46f4b4dda11f940",
sha1_str("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"));
TEST_EQUAL("50abf5706a150990a08b2c5ea40fa0e585554732",
sha1_str("12345678901234567890123456789012345678901234567890123456789012345678901234567890"));
}
void test_big()
{
# define BIG_LEN 1000000
char big[BIG_LEN];
for (int i = 0; i < BIG_LEN; ++i)
big[i] = 'a';
const char expected_result[] = "34aa973cd4c4daa4f61eeb2bdbad27316534016f";
// one call to update() with 1,000,000 bytes
sha1 digest;
digest.update(big, BIG_LEN);
TEST_EQUAL(expected_result, to_string(digest.final_value()));
// 100 calls to update() with 10,000 bytes each
digest.reset();
for (int j = 0; j < 100; ++j)
digest.update(big + BIG_LEN/100 * j, BIG_LEN/100);
TEST_EQUAL(expected_result, to_string(digest.final_value()));
// 1,000 calls to update() with 1,000 bytes each
digest.reset();
for (int j = 0; j < 1000; ++j)
digest.update(big + BIG_LEN/1000 * j, BIG_LEN/1000);
TEST_EQUAL(expected_result, to_string(digest.final_value()));
// 1,000,000 calls to update() with 1 byte each
digest.reset();
for (int j = 0; j < BIG_LEN; ++j)
digest.update(big + j, 1);
TEST_EQUAL(expected_result, to_string(digest.final_value()));
// digest 8 GiB in 64 KiB bites
digest.reset();
for (int j = 0; j < 128 * 1024; ++j)
digest.update(big, 64 * 1024);
TEST_EQUAL("971a7246e08be6e4d11ccdf362e19b19ca358792", to_string(digest.final_value()));
}
void demonstrate_usage()
{
sha1 digest;
// call update() as many times as you need to digest the data
digest.update("abc", 3);
digest.update("def", 3);
digest.update("ghijklmnopqrstuvwxyz", 20);
// call final_value() as many times as you need to access the result
TEST_EQUAL("32d10c7b8cf96570ca04ce37f2a19d84240d3a89", to_string(digest.final_value()));
TEST_EQUAL(0x240d3a89, digest.final_value()[4]);
unsigned d[5];
const unsigned * p = &digest.final_value()[0];
std::copy(p, p + 5, d);
TEST_EQUAL("32d10c7b8cf96570ca04ce37f2a19d84240d3a89", to_string(d));
// call reset() to reuse the object
digest.reset();
digest.update("abc", 3);
TEST_EQUAL("a9993e364706816aba3e25717850c26c9cd0d89d", to_string(digest.final_value()));
}
int main ()
{
test_assumptions();
demonstrate_usage();
test_known_values();
test_big();
std::cout
<< "total tests " << g_test_count
<< ", total failures " << g_fault_count
<< "\n";
return g_fault_count ? EXIT_FAILURE : EXIT_SUCCESS;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment