Initial version, with MD5
authorMikko Rasa <tdb@tdb.fi>
Sun, 14 Dec 2014 08:57:28 +0000 (10:57 +0200)
committerMikko Rasa <tdb@tdb.fi>
Sun, 14 Dec 2014 09:15:23 +0000 (11:15 +0200)
.gitignore [new file with mode: 0644]
Build [new file with mode: 0644]
source/hash.cpp [new file with mode: 0644]
source/hash.h [new file with mode: 0644]
source/md5.cpp [new file with mode: 0644]
source/md5.h [new file with mode: 0644]
tests/Build [new file with mode: 0644]
tests/md5.cpp [new file with mode: 0644]

diff --git a/.gitignore b/.gitignore
new file mode 100644 (file)
index 0000000..536c16b
--- /dev/null
@@ -0,0 +1,6 @@
+.config
+temp
+/libmspcrypto.a
+/libmspcrypto.so
+/mspcrypto.pc
+/tests/test
diff --git a/Build b/Build
new file mode 100644 (file)
index 0000000..003e9e3
--- /dev/null
+++ b/Build
@@ -0,0 +1,17 @@
+package "mspcrypto"
+{
+       description "A cryptographic library written in C++";
+       version "0.1";
+
+       require "mspcore";
+
+       library "mspcrypto"
+       {
+               source "source";
+               install true;
+               install_map
+               {
+                       map "source" "include/msp/crypto";
+               };
+       };
+};
diff --git a/source/hash.cpp b/source/hash.cpp
new file mode 100644 (file)
index 0000000..66da965
--- /dev/null
@@ -0,0 +1,30 @@
+#include <vector>
+#include "hash.h"
+
+using namespace std;
+
+namespace Msp {
+namespace Crypto {
+
+void Hash::update(const string &str)
+{
+       update(str.data(), str.size());
+}
+
+string Hash::get_hexdigest() const
+{
+       static const char hexdigits[] = "0123456789abcdef";
+
+       vector<char> digest(get_digest_size());
+       unsigned len = get_digest(&digest[0], digest.size());
+       string hex(len*2, '0');
+       for(unsigned i=0; i<len; ++i)
+       {
+               hex[i*2] = hexdigits[(digest[i]>>4)&15];
+               hex[i*2+1] = hexdigits[digest[i]&15];
+       }
+       return hex;
+}
+
+} // namespace Crypto
+} // namespace Msp
diff --git a/source/hash.h b/source/hash.h
new file mode 100644 (file)
index 0000000..ca7a857
--- /dev/null
@@ -0,0 +1,27 @@
+#ifndef MSP_CRYPTO_HASH_H_
+#define MSP_CRYPTO_HASH_H_
+
+#include <string>
+
+namespace Msp {
+namespace Crypto {
+
+class Hash
+{
+protected:
+       Hash() { }
+public:
+       virtual ~Hash() { }
+
+       virtual unsigned get_digest_size() const = 0;
+
+       virtual void update(const char *, unsigned) = 0;
+       virtual void update(const std::string &);
+       virtual unsigned get_digest(char *, unsigned) const = 0;
+       virtual std::string get_hexdigest() const;
+};
+
+} // namespace Crypto
+} // namespace Msp
+
+#endif
diff --git a/source/md5.cpp b/source/md5.cpp
new file mode 100644 (file)
index 0000000..c989526
--- /dev/null
@@ -0,0 +1,185 @@
+#include <cmath>
+#include <stdexcept>
+#include "md5.h"
+
+using namespace std;
+
+namespace Msp {
+namespace Crypto {
+
+namespace {
+
+template<unsigned N>
+inline UInt32 func(UInt32, UInt32, UInt32);
+
+template<>
+UInt32 func<1>(UInt32 x, UInt32 y, UInt32 z)
+{
+       return (y&x) | (z&~x);
+}
+
+template<>
+UInt32 func<2>(UInt32 x, UInt32 y, UInt32 z)
+{
+       return (x&z) | (y&~z);
+}
+
+template<>
+UInt32 func<3>(UInt32 x, UInt32 y, UInt32 z)
+{
+       return x^y^z;
+}
+
+template<>
+UInt32 func<4>(UInt32 x, UInt32 y, UInt32 z)
+{
+       return y^(x|~z);
+}
+
+inline UInt32 rotate_left(UInt32 x, UInt32 b)
+{
+       return (x<<b) | (x>>(32-b));
+}
+
+}
+
+
+UInt32 MD5::sin_table[64] = { 0 };
+unsigned MD5::rotate_table[16] =
+{
+       7, 12, 17, 22,
+       5, 9, 14, 20,
+       4, 11, 16, 23,
+       6, 10, 15, 21
+};
+
+MD5::MD5()
+{
+       init();
+}
+
+MD5::MD5(const char *data, unsigned len)
+{
+       init();
+       update(data, len);
+}
+
+MD5::MD5(const string &str)
+{
+       init();
+       update(str);
+}
+
+void MD5::init()
+{
+       buffer[0] = 0x67452301;
+       buffer[1] = 0xefcdab89;
+       buffer[2] = 0x98badcfe;
+       buffer[3] = 0x10325476;
+       processed_bytes = 0;
+       unprocessed_bytes = 0;
+
+       if(!sin_table[0])
+               for(unsigned i=0; i<64; ++i)
+                       sin_table[i] = 4294967296.0*abs(sin((i+1)*1.0));
+
+       if(!rotate_table[0])
+       {
+               for(unsigned i=0; i<4; ++i)
+                       rotate_table[i] = 7+i*5;
+               for(unsigned i=0; i<4; ++i)
+                       rotate_table[4+i] = 5+i*4+i*i/3;
+               for(unsigned i=0; i<4; ++i)
+                       rotate_table[8+i] = 4+i*7;
+               for(unsigned i=0; i<4; ++i)
+                       rotate_table[12+i] = 6+i*4+i*i/3;
+       }
+}
+
+void MD5::update(const char *data, unsigned len)
+{
+       if(unprocessed_bytes && unprocessed_bytes+len>=64)
+       {
+               unsigned needed = 64-unprocessed_bytes;
+               copy(data, data+needed, unprocessed+unprocessed_bytes);
+               process_block(unprocessed);
+               data += needed;
+               len -= needed;
+               unprocessed_bytes = 0;
+       }
+
+       while(len>=64)
+       {
+               process_block(data);
+               data += 64;
+               len -= 64;
+       }
+
+       if(len>0)
+       {
+               copy(data, data+len, unprocessed+unprocessed_bytes);
+               unprocessed_bytes += len;
+       }
+}
+
+unsigned MD5::get_digest(char *digest, unsigned len) const
+{
+       if(len<16)
+               throw invalid_argument("MD5::get_digest");
+
+       MD5 padded = *this;
+
+       char padding[64] = { static_cast<char>(0x80) };
+       padded.update(padding, 64-(unprocessed_bytes+8)%64);
+
+       UInt64 message_length = (processed_bytes+unprocessed_bytes)*8;
+       for(unsigned i=0; i<8; ++i)
+               padding[i] = message_length>>(i*8);
+       padded.update(padding, 8);
+
+       for(unsigned i=0; i<16; ++i)
+               digest[i] = padded.buffer[i/4]>>((i%4)*8);
+
+       return 16;
+}
+
+void MD5::process_block(const char *data)
+{
+       UInt32 input_words[16];
+
+       const UInt8 *u8data = reinterpret_cast<const UInt8 *>(data);
+       for(unsigned i=0; i<16; ++i)
+               input_words[i] = (u8data[i*4+3]<<24) | (u8data[i*4+2]<<16) | (u8data[i*4+1]<<8) | u8data[i*4];
+
+       UInt32 work_buffer[4];
+       copy(buffer, buffer+4, work_buffer);
+
+       perform_round<1, 0, 1>(work_buffer, input_words);
+       perform_round<2, 1, 5>(work_buffer, input_words);
+       perform_round<3, 5, 3>(work_buffer, input_words);
+       perform_round<4, 0, 7>(work_buffer, input_words);
+
+       for(unsigned i=0; i<4; ++i)
+               buffer[i] += work_buffer[i];
+
+       processed_bytes += 64;
+}
+
+template<unsigned N, unsigned START, unsigned DELTA>
+inline void MD5::perform_round(UInt32 *work_buffer, const UInt32 *input_words)
+{
+       for(unsigned i=0; i<4; ++i)
+               for(unsigned j=0; j<4; ++j)
+               {
+                       unsigned k = i*4+j;
+                       UInt32 &a = work_buffer[(4-j)&3];
+                       UInt32 &b = work_buffer[(5-j)&3];
+                       UInt32 &c = work_buffer[(6-j)&3];
+                       UInt32 &d = work_buffer[(7-j)&3];
+                       UInt32 sum = a + func<N>(b, c, d) + input_words[(START+k*DELTA)&15] + sin_table[(N-1)*16+k];
+                       a = b + rotate_left(sum, rotate_table[(N-1)*4+j]);
+               }
+}
+
+} // namespace Crypto
+} // namespace Msp
diff --git a/source/md5.h b/source/md5.h
new file mode 100644 (file)
index 0000000..f47723c
--- /dev/null
@@ -0,0 +1,45 @@
+#ifndef MSP_CRYPTO_MD5_H_
+#define MSP_CRYPTO_MD5_H_
+
+#include <msp/core/inttypes.h>
+#include "hash.h"
+
+namespace Msp {
+namespace Crypto {
+
+class MD5: public Hash
+{
+private:
+       UInt32 buffer[4];
+       UInt64 processed_bytes;
+       char unprocessed[64];
+       unsigned unprocessed_bytes;
+
+       static UInt32 sin_table[64];
+       static unsigned rotate_table[16];
+
+public:
+       MD5();
+       MD5(const char *, unsigned);
+       MD5(const std::string &);
+private:
+       void init();
+
+public:
+       virtual unsigned get_digest_size() const { return 16; }
+
+       using Hash::update;
+       virtual void update(const char *, unsigned);
+       virtual unsigned get_digest(char *, unsigned) const;
+
+private:
+       void process_block(const char *);
+
+       template<unsigned, unsigned, unsigned>
+       static void perform_round(UInt32 *, const UInt32 *);
+};
+
+} // namespace Crypto
+} // namespace Msp
+
+#endif
diff --git a/tests/Build b/tests/Build
new file mode 100644 (file)
index 0000000..cdf397f
--- /dev/null
@@ -0,0 +1,11 @@
+package "mspcrypto-tests"
+{
+       require "mspcore";
+       require "mspcrypto";
+       require "msptest";
+
+       program "test"
+       {
+               source ".";
+       };
+};
diff --git a/tests/md5.cpp b/tests/md5.cpp
new file mode 100644 (file)
index 0000000..e89078c
--- /dev/null
@@ -0,0 +1,87 @@
+#include <msp/crypto/md5.h>
+#include <msp/test/test.h>
+
+using namespace std;
+using namespace Msp;
+
+class MD5Tests: public Test::RegisteredTest<MD5Tests>
+{
+public:
+       MD5Tests();
+
+       static const char *get_name() { return "MD5"; }
+
+private:
+       void empty_input();
+       void known_strings();
+       void size_corner_cases();
+       void large_input();
+};
+
+MD5Tests::MD5Tests()
+{
+       add(&MD5Tests::empty_input,       "empty input");
+       add(&MD5Tests::known_strings,     "known strings");
+       add(&MD5Tests::size_corner_cases, "input size corner cases");
+       add(&MD5Tests::large_input,       "large input");
+}
+
+void MD5Tests::empty_input()
+{
+       string digest = Crypto::MD5().get_hexdigest();
+       EXPECT_EQUAL(digest, "d41d8cd98f00b204e9800998ecf8427e");
+}
+
+void MD5Tests::known_strings()
+{
+       // Test suite from RFC 1321
+       const char *test_suite[] =
+       {
+               "a", "0cc175b9c0f1b6a831c399e269772661",
+               "abc", "900150983cd24fb0d6963f7d28e17f72",
+               "message digest", "f96b697d7cb7938d525a2f31aaf161d0",
+               "abcdefghijklmnopqrstuvwxyz", "c3fcd3d76192e4007dfb496cca67e13b",
+               "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789", "d174ab98d277d9f5a5611c2c9f419d9f",
+               "12345678901234567890123456789012345678901234567890123456789012345678901234567890", "57edf4a22be3c955ac49da2e2107b67a",
+               0
+       };
+
+       for(unsigned i=0; test_suite[i]; i+=2)
+       {
+               string digest = Crypto::MD5(test_suite[i]).get_hexdigest();
+               expect_equal(digest, digest==test_suite[i+1], string("digest == \"")+test_suite[i+1]+"\"");
+       }
+
+       // This appears in Wikipedia
+       string digest = Crypto::MD5("The quick brown fox jumps over the lazy dog").get_hexdigest();
+       EXPECT_EQUAL(digest, "9e107d9d372bb6826bd81d3542a419d6");
+}
+
+void MD5Tests::size_corner_cases()
+{
+       // 55 bytes; shortest possible padding
+       string digest = Crypto::MD5("0123456789abcdef0123456789abcdef0123456789abcdef0123456").get_hexdigest();
+       EXPECT_EQUAL(digest, "d8ea71eb4d2af27f59a5316c971065e6");
+
+       // 56 bytes; longest possible padding
+       digest = Crypto::MD5("0123456789abcdef0123456789abcdef0123456789abcdef01234567").get_hexdigest();
+       EXPECT_EQUAL(digest, "a68f061e81239660f6305195739ba7f0");
+
+       // 64 bytes; exactly one block
+       digest = Crypto::MD5("0123456789abcdef0123456789abcdef0123456789abcdef0123456789abcdef").get_hexdigest();
+       EXPECT_EQUAL(digest, "fe3a1ff59f3b89b2ad3d33f08984874b");
+}
+
+void MD5Tests::large_input()
+{
+       static const char lorem_ipsum[] = "Lorem ipsum dolor sit amet, consectetur "
+               "adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore "
+               "magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation "
+               "ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute "
+               "irure dolor in reprehenderit in voluptate velit esse cillum dolore eu "
+               "fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, "
+               "sunt in culpa qui officia deserunt mollit anim id est laborum.";
+
+       string digest = Crypto::MD5(lorem_ipsum).get_hexdigest();
+       EXPECT_EQUAL(digest, "db89bb5ceab87f9c0fcc2ab36c189c2c");
+}