C and C++ MD5 algorithm implementation code
- 2020-05-26 09:52:16
- OfStack
In the reverse program, we often encounter the problem of encryption algorithm. In the previous analysis of question 2 of the reverse engineer of UC, we found that the encryption algorithm of MD5 was used (the algorithm of MD5 is realized by ourselves, not the algorithm library function). Especially in the reverse analysis of network protocol, 1 - like programs used encryption algorithm is the library function provided by the algorithm, some programs use the algorithm is their own implementation; Relatively speaking, the encryption function algorithm provided by the function library is relatively easy to identify, because there are common functions in the algorithm; However, if you do not use the function library to provide encryption function but to implement some algorithms, it is difficult to identify, which requires you to be familiar with the function encryption principle and process algorithm features to quickly identify. The following will be online about MD5 algorithm 1 some knowledge 1, aspects of their own reference.
md5 profile
Message digest algorithm version 5 (English: Message-Digest Algorithm 5, abbreviated as MD5), is currently used in the computer field to ensure the integrity of information transmission 1 and widely used hash algorithm 1 (also translated hash algorithm, digest algorithm, etc.), the mainstream programming language generally has the implementation of MD5. The basic principle of hash algorithm is to change the operation of data (such as a paragraph of text) into another fixed-length value. The predecessor of MD5 is MD2, MD3 and MD4. MD5 is improved from MD4, MD3 and MD2, which mainly increases the algorithm complexity and irreversibility. At present, MD5 algorithm is still widely used in the field of error checking of common data due to its universal, stable and fast characteristics. For example, in some BitTorrent downloads, the software will verify the integrity of the downloaded file fragment by calculating MD5. MD5 has been widely used to provide one-point reliability for file transfers. For example, the server provides an MD5 checksum in advance. After the user downloads the file, the MD5 algorithm is used to calculate the MD5 checksum of the downloaded file. MD5 is an algorithm that inputs the variable length information and outputs the fixed length 128-bits. Through the program flow, four 32-bit data are generated and finally combined into a 128-bits hash. The basic method is to find the remainder, take the remainder, adjust the length, and link variables for loop operation. You get the result.
md5 algorithm description
Assuming that the length of the input message (input message) is b(bit), we want to generate its message digest, where b is an arbitrary non-negative integer: b may also be 0, nor is 1 an integer multiple of 8, and may be of an arbitrarily large length. Let the bitstream of this information be represented as follows: M[0] M[1] M[2]... To calculate the message digest for this information, M[b-1] requires the following five steps:
1. Cover you
Before the information calculation, bit complement should be performed. If the length of the information after the complement is set as LEN(bit), then LEN%512 = 448(bit), that is, the data is extended to K * 512 + 448(bit). So K * 64+56(byte), K is an integer. A complement operation is always performed, even if the length of the message before the complement is left at 448 for 512. Specific fill operation: fill 1 1, and then fill 0 to meet the above requirements. In total, at least 1bit should be supplemented, and at most 512bit should be supplemented.
2. Add the information length to the tail
Represent the original length of the input information as a number of 64-bit, and add it to the result of the previous step (on a 32-bit machine, the 64-bit will be represented in two words and low in front). In rare cases where b is greater than 2^64, the high bits of b are truncated and only the low 64 bits of b are used. After the above two steps, the data is filled with multiples of 512(bit). That is, the length of the data is an integer multiple of 16 words (32byte). At this time, the data is expressed as: M[0... N-1] where N is a multiple of 16.
3. Initialize the cache
With a four word buffer (A B, C, D) to calculate the message digest, A, B, C, D 32-bit registers, initialization using the said 106 hexadecimal number, pay attention to the low byte in front: word A: 01 23 45 67 word B: 89 ab cd ef word C: fe dc word 98 word D: 76 54 32 10
4. The conversion
First of all, four auxiliary functions are defined. The input of each function is 3 32-bit words, and the output is 1 32-bit word: F(X,Y,Z) = XY v (X) Z G(X,Y,Z) = XZ v (Z) H(X,Y,Z) = X xor Y xor Z I(X,Y,Z) = Y xor (X v not(Z))
FF(a,b,c,d,Mj,s,ti ) said a = b + ((a + F(b,c,d) + Mj + ti) << s)
GG(a,b,c,d,Mj,s,ti ) said a = b + ((a + G(b,c,d) + Mj + ti) << s)
HH(a,b,c,d,Mj,s,ti ) said a = b + ((a + H(b,c,d) + Mj + ti) << s)
Ⅱ ( a,b,c,d,Mj,s,ti ) said a = b + ((a + I(b,c,d) + Mj + ti) << s)The four rounds (64 steps) are:
1 round
FF (a b, c d, M0, 7, 0) xd76aa478 FF (d a, b, c, M1, 12, 0 xe8c7b756) FF (c d, a b, M2, 17, 0 x242070db) FF (b c, d, a, M3, 22, 0 xc1bdceee) FF (a b, c d, M4, 7, 0) xf57c0faf FF (d a, b, c, M5, 12, 0 x4787c62a) FF (c d, a b, M6, 17, 0 xa8304613) FF (b c, d, a, M7, 22, 0 xfd469501) FF (a b, c d, M8, 7, 0) x698098d8 FF (d a, b, c, M9, 12, 0 x8b44f7af) FF (c d, a b, M10, 17, 0 xffff5bb1) FF (b c, d, a, M11, 22, 0 x895cd7be) FF (a b, c d, M12, 7, 0) x6b901122 FF (d a, b, c, M13, 12, 0 xfd987193) FF (c d, a b, M14, 17, 0 xa679438e) FF (b c, d, a, M15, 22, 0 x49b40821)
Second round
GG (a b, c d, M1, 5, 0 xf61e2562) GG (d a, b, c, M6, 9, 0 xc040b340) GG (c d, a b, M11, 14, 0 x265e5a51) GG (b c, d, a, M0, 20, 0 xe9b6c7aa) GG (a b, c d, M5, 5, 0 xd62f105d) GG (d a, b, c, M10, 9, 0 x02441453) GG (c d, a b, M15, 14, 0 xd8a1e681) GG (b c, d, a, M4, 20, 0 xe7d3fbc8) GG (a b, c d, M9, 5, 0 x21e1cde6) GG (d a, b, c, M14, 9, 0 xc33707d6) GG (c d, a b, M3, 14, 0 xf4d50d87) GG (b c, d, a, M8, 20, 0 x455a14ed) GG (a b, c d, M13, 5, 0 xa9e3e905) GG (d a, b, c, M2, 9, 0 xfcefa3f8) GG (c d, a b, M7, 14, 0 x676f02d9) GG (b c, d, a, M12, 20, 0 x8d2a4c8a)
The third wheel
HH (a b, c d, M5, 4, 0 xfffa3942 HH (d a, b, c, M8, 11, 0 x8771f681) HH (c d, a b, M11, 16, 0 x6d9d6122) HH (b c, d, a, M14, 23, 0 xfde5380c) HH (a b, c d, M1, 4, 0 xa4beea44 HH (d a, b, c, M4, 11, 0 x4bdecfa9) HH (c d, a b, M7, 16, 0 xf6bb4b60) HH (b c, d, a, M10, 23, 0 xbebfbc70) HH (a b, c d, M13, 4, 0 x289b7ec6 HH (d a, b, c, M0, 11, 0 xeaa127fa) HH (c d, a b, M3, 16, 0 xd4ef3085) HH (b c, d, a, M6, 23, 0 x04881d05) HH (a b, c d, M9, 4, 0 xd9d4d039 HH (d a, b, c, M12, 11, 0 xe6db99e5) HH (c d, a b, M15, 16, 0 x1fa27cf8) HH (b c, d, a, M2, 23, 0 xc4ac5665)
The fourth round of
Ⅱ (a b, c d, M0, 6, 0 xf4292244) Ⅱ (d a, b, c, M7, 10, 0 x432aff97) Ⅱ (c d, a, b, M14, 15, 0 xab9423a7) Ⅱ (b c, d a, M5, 21, 0 xfc93a039) Ⅱ (a b, c, d, M12, 6, 0 x655b59c3) Ⅱ (d a, b c, M3, 10, 0 x8f0ccc92) Ⅱ (c d, a, b, M10, 15, 0 xffeff47d) Ⅱ (b c, d a, M1, 21, 0 x85845dd1) Ⅱ (a b, c, d, M8, 6, 0 x6fa87e4f) Ⅱ (d a, b c, M15, 10, 0 xfe2ce6e0) Ⅱ (c d, a, b, M6, 15, 0 xa3014314) Ⅱ (b c, d a, M13, 21, 0 x4e0811a1) Ⅱ (a b, c, d, M4, 6, 0 xf7537e82) Ⅱ (d a, b c, M11, 10, 0 xbd3af235) Ⅱ (c d, a, b, M2, 15, 0 x2ad7d2bb) Ⅱ (b c, d a, M9, 21, 0 xeb86d391)
The following is the concrete implementation of MD5 algorithm
MD5 algorithm header file Md5.h:
#ifndef MD5_H
#define MD5_H
typedef struct
{
unsigned int count[2];
unsigned int state[4];
unsigned char buffer[64];
}MD5_CTX;
#define F(x,y,z) ((x & y) | (~x & z))
#define G(x,y,z) ((x & z) | (y & ~z))
#define H(x,y,z) (x^y^z)
#define I(x,y,z) (y ^ (x | ~z))
#define ROTATE_LEFT(x,n) ((x << n) | (x >> (32-n)))
#define FF(a,b,c,d,x,s,ac) { \
a += F(b, c, d) + x + ac; \
a = ROTATE_LEFT(a, s); \
a += b; \
}
#define GG(a,b,c,d,x,s,ac) { \
a += G(b, c, d) + x + ac; \
a = ROTATE_LEFT(a, s); \
a += b; \
}
#define HH(a,b,c,d,x,s,ac) { \
a += H(b, c, d) + x + ac; \
a = ROTATE_LEFT(a, s); \
a += b; \
}
#define II(a,b,c,d,x,s,ac) { \
a += I(b, c, d) + x + ac; \
a = ROTATE_LEFT(a, s); \
a += b; \
}
void MD5Init(MD5_CTX *context);
void MD5Update(MD5_CTX *context, unsigned char *input, unsigned int inputlen);
void MD5Final(MD5_CTX *context, unsigned char digest[16]);
void MD5Transform(unsigned int state[4], unsigned char block[64]);
void MD5Encode(unsigned char *output, unsigned int *input, unsigned int len);
void MD5Decode(unsigned int *output, unsigned char *input, unsigned int len);
#endifMD5 algorithm implementation file Md5.cpp:
unsigned char PADDING[] = {
0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
// When reverting code, you need to focus on the following eigenvalues
void MD5Init(MD5_CTX *context)
{
context->count[0] = 0;
context->count[1] = 0;
context->state[0] = 0x67452301;
context->state[1] = 0xEFCDAB89;
context->state[2] = 0x98BADCFE;
context->state[3] = 0x10325476;
}
void MD5Update(MD5_CTX *context, unsigned char *input, unsigned int inputlen)
{
unsigned int i = 0, index = 0, partlen = 0;
index = (context->count[0] >> 3) & 0x3F;
partlen = 64 - index;
context->count[0] += inputlen << 3;
if (context->count[0] < (inputlen << 3))
context->count[1]++;
context->count[1] += inputlen >> 29;
if (inputlen >= partlen)
{
memcpy(&context->buffer[index], input, partlen);
MD5Transform(context->state, context->buffer);
for (i = partlen; i + 64 <= inputlen; i += 64)
MD5Transform(context->state, &input[i]);
index = 0;
}
else
{
i = 0;
}
memcpy(&context->buffer[index], &input[i], inputlen - i);
}
void MD5Final(MD5_CTX *context, unsigned char digest[16])
{
unsigned int index = 0, padlen = 0;
unsigned char bits[8];
index = (context->count[0] >> 3) & 0x3F;
padlen = (index < 56) ? (56 - index) : (120 - index);
MD5Encode(bits, context->count, 8);
MD5Update(context, PADDING, padlen);
MD5Update(context, bits, 8);
MD5Encode(digest, context->state, 16);
}
void MD5Encode(unsigned char *output, unsigned int *input, unsigned int len)
{
unsigned int i = 0, j = 0;
while (j < len)
{
output[j] = input[i] & 0xFF;
output[j + 1] = (input[i] >> 8) & 0xFF;
output[j + 2] = (input[i] >> 16) & 0xFF;
output[j + 3] = (input[i] >> 24) & 0xFF;
i++;
j += 4;
}
}
void MD5Decode(unsigned int *output, unsigned char *input, unsigned int len)
{
unsigned int i = 0, j = 0;
while (j < len)
{
output[i] = (input[j]) |
(input[j + 1] << 8) |
(input[j + 2] << 16) |
(input[j + 3] << 24);
i++;
j += 4;
}
}
void MD5Transform(unsigned int state[4], unsigned char block[64])
{
unsigned int a = state[0];
unsigned int b = state[1];
unsigned int c = state[2];
unsigned int d = state[3];
unsigned int x[64];
MD5Decode(x, block, 64);
FF(a, b, c, d, x[0], 7, 0xd76aa478);
FF(d, a, b, c, x[1], 12, 0xe8c7b756);
FF(c, d, a, b, x[2], 17, 0x242070db);
FF(b, c, d, a, x[3], 22, 0xc1bdceee);
FF(a, b, c, d, x[4], 7, 0xf57c0faf);
FF(d, a, b, c, x[5], 12, 0x4787c62a);
FF(c, d, a, b, x[6], 17, 0xa8304613);
FF(b, c, d, a, x[7], 22, 0xfd469501);
FF(a, b, c, d, x[8], 7, 0x698098d8);
FF(d, a, b, c, x[9], 12, 0x8b44f7af);
FF(c, d, a, b, x[10], 17, 0xffff5bb1);
FF(b, c, d, a, x[11], 22, 0x895cd7be);
FF(a, b, c, d, x[12], 7, 0x6b901122);
FF(d, a, b, c, x[13], 12, 0xfd987193);
FF(c, d, a, b, x[14], 17, 0xa679438e);
FF(b, c, d, a, x[15], 22, 0x49b40821);
GG(a, b, c, d, x[1], 5, 0xf61e2562);
GG(d, a, b, c, x[6], 9, 0xc040b340);
GG(c, d, a, b, x[11], 14, 0x265e5a51);
GG(b, c, d, a, x[0], 20, 0xe9b6c7aa);
GG(a, b, c, d, x[5], 5, 0xd62f105d);
GG(d, a, b, c, x[10], 9, 0x2441453);
GG(c, d, a, b, x[15], 14, 0xd8a1e681);
GG(b, c, d, a, x[4], 20, 0xe7d3fbc8);
GG(a, b, c, d, x[9], 5, 0x21e1cde6);
GG(d, a, b, c, x[14], 9, 0xc33707d6);
GG(c, d, a, b, x[3], 14, 0xf4d50d87);
GG(b, c, d, a, x[8], 20, 0x455a14ed);
GG(a, b, c, d, x[13], 5, 0xa9e3e905);
GG(d, a, b, c, x[2], 9, 0xfcefa3f8);
GG(c, d, a, b, x[7], 14, 0x676f02d9);
GG(b, c, d, a, x[12], 20, 0x8d2a4c8a);
HH(a, b, c, d, x[5], 4, 0xfffa3942);
HH(d, a, b, c, x[8], 11, 0x8771f681);
HH(c, d, a, b, x[11], 16, 0x6d9d6122);
HH(b, c, d, a, x[14], 23, 0xfde5380c);
HH(a, b, c, d, x[1], 4, 0xa4beea44);
HH(d, a, b, c, x[4], 11, 0x4bdecfa9);
HH(c, d, a, b, x[7], 16, 0xf6bb4b60);
HH(b, c, d, a, x[10], 23, 0xbebfbc70);
HH(a, b, c, d, x[13], 4, 0x289b7ec6);
HH(d, a, b, c, x[0], 11, 0xeaa127fa);
HH(c, d, a, b, x[3], 16, 0xd4ef3085);
HH(b, c, d, a, x[6], 23, 0x4881d05);
HH(a, b, c, d, x[9], 4, 0xd9d4d039);
HH(d, a, b, c, x[12], 11, 0xe6db99e5);
HH(c, d, a, b, x[15], 16, 0x1fa27cf8);
HH(b, c, d, a, x[2], 23, 0xc4ac5665);
II(a, b, c, d, x[0], 6, 0xf4292244);
II(d, a, b, c, x[7], 10, 0x432aff97);
II(c, d, a, b, x[14], 15, 0xab9423a7);
II(b, c, d, a, x[5], 21, 0xfc93a039);
II(a, b, c, d, x[12], 6, 0x655b59c3);
II(d, a, b, c, x[3], 10, 0x8f0ccc92);
II(c, d, a, b, x[10], 15, 0xffeff47d);
II(b, c, d, a, x[1], 21, 0x85845dd1);
II(a, b, c, d, x[8], 6, 0x6fa87e4f);
II(d, a, b, c, x[15], 10, 0xfe2ce6e0);
II(c, d, a, b, x[6], 15, 0xa3014314);
II(b, c, d, a, x[13], 21, 0x4e0811a1);
II(a, b, c, d, x[4], 6, 0xf7537e82);
II(d, a, b, c, x[11], 10, 0xbd3af235);
II(c, d, a, b, x[2], 15, 0x2ad7d2bb);
II(b, c, d, a, x[9], 21, 0xeb86d391);
state[0] += a;
state[1] += b;
state[2] += c;
state[3] += d;
} Call test of MD5 algorithm:
int _tmain(int argc, _TCHAR* argv[])
{
int i;
unsigned char encrypt[] = "admin";//21232f297a57a5a743894a0e4a801fc3
unsigned char decrypt[16];
MD5_CTX md5;
MD5Init(&md5);
MD5Update(&md5, encrypt, strlen((char *)encrypt));
MD5Final(&md5, decrypt);
//Md5 The encrypted 32 A result
printf(" Before the encryption :%s\n encrypted 16 position :", encrypt);
for (i = 4; i<12; i++)
{
printf("%02x", decrypt[i]);
}
//Md5 The encrypted 32 A result
printf("\n Before the encryption :%s\n encrypted 32 position :", encrypt);
for (i = 0; i<16; i++)
{
printf("%02x", decrypt[i]);
}
getchar();
return 0;
}The code above engineering download address: Md5Demo201707 zip
Crack MD5 encrypted url: http: / / www cmd5. com /
Thanks for your links:
http://blog.sina.com.cn/s/blog_693de6100101kcu6.html
https://github.com/JieweiWei/md5