From f6bd922f1c28db136b3497da5a185eef1fb72209 Mon Sep 17 00:00:00 2001 From: hama Date: Sat, 31 Jan 2015 04:47:45 +0100 Subject: [PATCH] implementation of ReMD5 --- base/rebase.hpp | 1 + cunit/cuReMD5.cpp | 42 ++++++++ cunit/testall.cpp | 4 + math/ReMD5.cpp | 269 ++++++++++++++++++++++++++++++++++++++++++++++ math/ReMD5.hpp | 49 +++++++++ math/remath.hpp | 1 + 6 files changed, 366 insertions(+) create mode 100644 cunit/cuReMD5.cpp create mode 100644 math/ReMD5.cpp create mode 100644 math/ReMD5.hpp diff --git a/base/rebase.hpp b/base/rebase.hpp index a623bce..6c15189 100644 --- a/base/rebase.hpp +++ b/base/rebase.hpp @@ -31,6 +31,7 @@ # include # include typedef u_int64_t uint64_t; +typedef u_int8_t uint8_t; # define _strdup strdup # define _unlink unlink # define _strnicmp(s1, s2, n) strncasecmp(s1, s2, n) diff --git a/cunit/cuReMD5.cpp b/cunit/cuReMD5.cpp new file mode 100644 index 0000000..c3fd456 --- /dev/null +++ b/cunit/cuReMD5.cpp @@ -0,0 +1,42 @@ +/* + * cuReMatcher.cpp + * + * License: Public domain + * Do what you want. + * No warranties and disclaimer of any damages. + * The latest sources: https://github.com/republib + */ +/* + * cuReMatcher.hpp + * + * License: Public domain + * Do what you want. + * No warranties and disclaimer of any damages. + * The latest sources: https://github.com/republib + */ + + +#include "base/rebase.hpp" +#include "math/remath.hpp" + +class TestReMd5 : public ReTestUnit { +public: + TestReMd5() : ReTestUnit("ReMatcher", __FILE__){ + run(); + } +private: + void run(){ + testBase(); + } + void testBase(){ + ReMD5 md5; + md5.update((const uint8_t*)"", 0); + checkEqu("d41d8cd98f00b204e9800998ecf8427e", + md5.hexDigest().str()); + } +}; +extern void testReMD5(void); + +void testReMD5(void){ + TestReMd5 unit; +} diff --git a/cunit/testall.cpp b/cunit/testall.cpp index 277bd6e..844d604 100644 --- a/cunit/testall.cpp +++ b/cunit/testall.cpp @@ -62,12 +62,16 @@ void testOs(){ testReTraverser(); } void testMath(){ + extern void testReMD5(); + testReMD5(); extern void testReRandomizer(); testReRandomizer(); } void testAll(){ try { + testMath(); + testOs(); testBase(); testMath(); diff --git a/math/ReMD5.cpp b/math/ReMD5.cpp new file mode 100644 index 0000000..4621c31 --- /dev/null +++ b/math/ReMD5.cpp @@ -0,0 +1,269 @@ +/* + * ReMD5.cpp + * + * Created on: 30.01.2015 + * + */ + +#include "base/rebase.hpp" +#include "math/remath.hpp" +#define __LITTLE_ENDIAN__ + +const int ReMD5::m_s[64] = { + 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, + 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, + 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21 +}; +// for x in [1..64] : int(2**32 * sin(x)) +const int ReMD5::m_K[64] = { + 0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee, + 0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501, + 0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be, + 0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821, + 0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa, + 0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8, + 0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed, + 0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a, + 0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c, + 0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70, + 0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x04881d05, + 0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665, + 0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039, + 0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1, + 0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1, + 0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391 +}; + +/** + * Constructor. + */ +ReMD5::ReMD5() : + //m_digest + // m_hexDigest; + // m_waiting[64]; + m_lengthWaiting(0), + m_length(0), + m_a0(0x67452301), + m_b0(0xefcdab89), + m_c0(0x98badcfe), + m_d0(0x10325476), + m_finalized(false) +{ +} + +/** + * Destructor. + */ +ReMD5::~ReMD5() { +} + +/** + * Returns the binary digest value. + * + * @return the binary digest (16 byte array) + */ +const uint8_t* ReMD5::digest(){ + if (! m_finalized){ + finalize(); + } + return m_digest; +} + +/** + * Finalizes the digest. + * + * Handles the rest block (< 64 byte) and append a special tail: a "1" bit + * and the length of the total input length (in bits). + * + * @param block the rest input (incomplete chunk) + * @param blockLength the length of the block: 0..63 + */ +void ReMD5::finalize(){ + uint8_t* block = m_waiting; + int blockLength = m_lengthWaiting; + + // append "1" bit to message + // Notice: the input bytes are considered as bits strings, + // where the first bit is the most significant bit of the byte. + block[blockLength++] = 0x80; + //Pre-processing: padding with zeros + //append "0" bit until message length in bits ≡ 448 (mod 512) + // fill the rest of the chunk with '\0'. + // the last 8 bytes is set to the length in bits (length in bytes * 8) + int restLength = (m_length + 1) % 64; + // 0 -> 56, 1 -> 55, 2 -> 54, ... 55 -> 1, 56 -> 0, + // 57 -> 63, 58 -> 62, ... 63 -> 57 + int zeros = restLength <= 56 ? 56 - restLength : 120 - restLength; + memset(block + blockLength + 1, 0, zeros); + blockLength += zeros; + //append original length in bits mod (2 pow 64) to message + uint64_t lengthBits = 8LL * m_length; +#if defined __LITTLE_ENDIAN__ + memcpy(block + blockLength, &lengthBits, 8); + blockLength += 8; +#else + block[blockLength++] = lengthBits & 0xff; + lengthBits >>= 4; + block[blockLength++] = lengthBits & 0xff; + lengthBits >>= 4; + block[blockLength++] = lengthBits & 0xff; + lengthBits >>= 4; + block[blockLength++] = lengthBits & 0xff; + lengthBits >>= 4; + block[blockLength++] = lengthBits & 0xff; + lengthBits >>= 4; + block[blockLength++] = lengthBits & 0xff; + lengthBits >>= 4; + block[blockLength++] = lengthBits & 0xff; + lengthBits >>= 4; + block[blockLength++] = lengthBits & 0xff; +#endif + processChunk(block); + if (blockLength > 64) + processChunk(block + 64); +#if defined __LITTLE_ENDIAN__ + memcpy(m_digest, &m_a0, 4); + memcpy(m_digest + 4, &m_b0, 4); + memcpy(m_digest + 8, &m_c0, 4); + memcpy(m_digest + 12, &m_d0, 4); + blockLength += 8; +#else +#define oneWord(word, ix) m_digest[ix] = word; word >>= 4; \ + m_digest[ix + 1] = word; word >>= 4; m_digest[ix + 2] = word; word >>= 4; \ + m_digest[ix + 3] = word + oneWord(m_a0, 0); + oneWord(m_b0, 4); + oneWord(m_c0, 8); + oneWord(m_d0, 12); +#endif +} + +/** + * Returns the binary digest value. + * + * @return the binary digest (16 byte array) + */ +const ReByteBuffer& ReMD5::hexDigest(){ + if (m_hexDigest.length() == 0){ + digest(); + for (int ix = 0; ix < 16; ix++){ + m_hexDigest.appendInt(m_digest[ix], "%02x"); + } + } + return m_hexDigest; +} + +/** + * Processes a 512 bit block ("chunk"). + */ +void ReMD5::processChunk(const uint8_t block[64]){ + int M[16]; + // break chunk into sixteen 32-bit words M[j], 0 ≤ j ≤ 15 +#ifdef __LITTLE_ENDIAN__ + for (int ix = 0; ix < 16; ix++) + memcpy(&M[ix], block + ix * 4, 4); +#elif defined __BIG_ENDIAN__ + for (int ix = 0; ix < 16; ix++){ + M[ix] = block[3]; + for (jj = 2; jj >= 0; jj--){ + M[ix] = (M[ix] << 4) + block[jj]; + } + block += 4; + } +#else +# error "missing __LITTLE_ENDIAN__ or __BIG_ENDIAN__" +#endif + + //Initialize hash value for this chunk: + int A = m_a0; + int B = m_b0; + int C = m_c0; + int D = m_d0; + //Main loop: + int F, g; + for (int i = 0; i < 64; i++){ + if (i <= 15){ + // F := (B and C) or ((not B) and D) + F = (B & C) | (~ B & D); + g = i; + } else if (i > 15 && i <= 31){ + // F := (D and B) or ((not D) and C) + F = (D & B) | (~ D & C); + // g := (5×i + 1) mod 16 + g = (5*i + 1) % 16; + } else if (i > 31 && i <= 47){ + // F := B xor C xor D + F = (B ^ C) ^ D; + // g := (3×i + 5) mod 16 + g = (3*i + 5) % 16; + } else { + // F := C xor (B or (not D)) + F = C ^ (B | ~ D); + // g := (7×i) mod 16 + g = (7*i) % 16; + } + int dTemp = D; + D = C; + C = B; + // B := B + leftrotate((A + F + K[i] + M[g]), s[i]) + int x = (A + F + m_K[i] + M[g]) & 0xffffffff; + int shift = m_s[i]; + B += (x << shift) | (x >> (32 - shift)); + A = dTemp; + } + //Add this chunk's hash to result so far: + m_a0 += A; + m_b0 += B; + m_c0 += C; + m_d0 += D; +} + +/** + * Prepares the instance for a new checksum. + */ +void ReMD5::reset(){ + m_a0 = 0x67452301; + m_b0 = 0xefcdab89; + m_c0 = 0x98badcfe; + m_d0 = 0x10325476; + memset(m_digest, 0, sizeof m_digest); + memset(m_waiting, 0, sizeof m_waiting); + m_lengthWaiting = 0; + m_length = 0; +} +/** + * Processes a 64 byte block. + * + * @param block a block which should be added to the digest + * @param blockLength the length of block + */ +void ReMD5::update(const uint8_t* block, int blockLength){ + // process the "waiting" input (incomplete chunk): + m_length += blockLength; + if (m_lengthWaiting > 0){ + int rest = 64 - m_lengthWaiting; + if (rest > blockLength) + rest = blockLength; + memcpy(m_waiting + m_lengthWaiting, block, rest); + blockLength -= rest; + block += rest; + m_lengthWaiting += rest; + // Is the chunk complete? + if (m_lengthWaiting == 64){ + processChunk(m_waiting); + m_lengthWaiting = 0; + } + } + // process full 512 bit chunks (64 byte blocks): + for (int ix = blockLength / 64; ix >= 0; ix--){ + processChunk(block); + block += 64; + } + blockLength %= 64; + if (blockLength != 0){ + assert(m_lengthWaiting == 0); + memcpy(m_waiting, block, blockLength); + m_lengthWaiting = blockLength; + } +} + diff --git a/math/ReMD5.hpp b/math/ReMD5.hpp new file mode 100644 index 0000000..7c885ee --- /dev/null +++ b/math/ReMD5.hpp @@ -0,0 +1,49 @@ +/* + * ReMD5.hpp + * + * Created on: 30.01.2015 + * Author: hm + */ + +#ifndef MATH_REMD5_HPP_ +#define MATH_REMD5_HPP_ + +typedef uint8_t ReDigest[16]; +/** + * Building of the MD5 checksum. + * + * The algorithm is described in http://en.wikipedia.org/wiki/MD5. + */ +class ReMD5 { +public: + ReMD5(); + virtual ~ReMD5(); +public: + const uint8_t* digest(); + const ReByteBuffer& hexDigest(); + void update(const uint8_t* block, int blockLength); + void processChunk(const uint8_t block[64]); + void reset(); +private: + void finalize(); + +private: + ReDigest m_digest; + ReByteBuffer m_hexDigest; + // normally only the first chunk is used (64 byte), but while finalization + // a 2nd chunk may be needed. + uint8_t m_waiting[64+64]; + int m_lengthWaiting; + // total count of input bytes: + int m_length; + int m_a0; + int m_b0; + int m_c0; + int m_d0; + bool m_finalized; +private: + static const int m_s[64]; + static const int m_K[64]; +}; + +#endif /* MATH_REMD5_HPP_ */ diff --git a/math/remath.hpp b/math/remath.hpp index ac6ccd4..b2b5d00 100644 --- a/math/remath.hpp +++ b/math/remath.hpp @@ -13,5 +13,6 @@ #include "math/ReObfuscator.hpp" #include "math/ReRandomizer.hpp" +#include "math/ReMD5.hpp" #endif /* REMATH_HPP_ */ -- 2.39.5