MD5 algorithm learning notes
This post is reprinted from: http://blog.9cbs.net/aloking/archive/2004/07/30/56719.aspx
One-way hash function, MD indicates a message summary, which generates a 128-column value value for the input message.
Algorithm principle
First, the fill message makes the data length of only 512, only the number of small 64 bits, and the method is to attach one 1 behind the message, the rear required multiple 0, and then attached thereafter 64-bit message length The role of these two parts is to make the message length exactly equal to the integer multiple of 512 bits, and ensure that different messages are different in the fill.
C language example:
--------------------------------------------
* /
#ifndef prototypes
#define prototypes 0
#ENDIF
Typedef unsigned char * pointer;
Typedef unsigned short int uint2;
Typedef unsigned long int uint4;
#if protoypes
#define proto_list (list) List
#ELSE
#define proto_list (list) ()
#ENDIF
---------- Md5.h ----------------------------
Typedef struct {
Uint4 state [4];
Uint4 count [2];
UNSIGNED Char Buffer [64];
} MD5_CTX;
Void MD5init Proto_List ((MD5_CTX *));
Void MD5UPDATE PROTO_LIST
((MD5_CTX *, Unsigned CHAR *, UNSIGNED INT);
Void MD5Final Proto_List ((unsigned char [16), md5_ctx *));
※※※※※※※※※ ※ ※※※※※※※※※※※※※※※※※※※※※※
#include "global.h"
#include "md5.h"
#define S11 7
#define s12 12
#define s13 17
#define s14 22
#define s21 5
#define s22 9
#define s23 14
#define s24 20
#define s31 4
#define s32 11
#define s33 16
#define s34 23
#define s41 6
#define s42 10
#define s43 15
#define s44 21
Static void MD5Transform Proto_List ((uint4 [4), unsigned char [64]));
Static void Encode Proto_List
((UNSIGNED CHAR *, UINT4 *, UNSIGNED INT);
Static Void Decode Proto_List
((Uint4 *, unsigned char *, unsigned int));
Static void MD5_Memcpy Proto_List ((Pointer, Pointer, Unsigned Int);
Static void MD5_MEMSET Proto_List ((Pointer, INT, Unsigned Int);
Static unsigned charphar padding [64] = {
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
}
/ * Define F g H i to four courses
#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) (UINT4) (AC); /
(a) = rotate_left ((a), (s)); /
(a) = (b); /
}
#define GG (A, B, C, D, X, S, AC) {/
(a) = g ((b), (c), (d)) (x) (UINT4) (AC); /
(a) = rotate_left ((a), (s)); /
(a) = (b); /
}
#define HH (A, B, C, D, X, S, AC) {/
(a) = h ((b), (c), (d)) (x) (UINT4) (AC); /
(a) = rotate_left ((a), (s)); /
(a) = (b); /
}
#define II (A, B, C, D, X, S, AC) {/
(a) = I ((b), (c), (d)) (x) (UINT4) (AC); /
(a) = rotate_left ((a), (s)); /
(a) = (b); /
}
/ * Start MD5 calculation
Void MD5Init (Context)
MD5_CTX * Context;
{
CONTEXT-> count [0] = context-> count [1] = 0;
/ * The four constants are defined here, that is, the four characteristics we have just said.
Context-> State [0] = 0x67452301;
Context-> State [1] = 0xEfcdAb89;
CONTEXT-> State [2] = 0x98badcfe;
Context-> State [3] = 0x10325476;
}
Void Md5Update (Context, Input, Inputlen)
MD5_CTX * Context;
Unsigned char * input;
Unsigned int inputlen;
{
Unsigned Int I, Index, Partle;
Index = (unsigned int) ((CONTEXT-> COUNT [0] >> 3) & 0x3F);
IF ((context-> count [0] = (uint4) Inputlen << 3)) <((uint4) inputlen << 3))
Context-> count [1] ; context-> count [1] = ((uint4) Inputlen >> 29);
Partlen = 64 - INDEX;
IF (Inputlen> = Partle) {
MD5_MEMCPY
((Pointer) & context-> buffer [index], (Pointer) Input, Partle;
MD5Transform (context-> state, context-> buffer);
For (i = partlen; i 63 MD5Transform (Context-> State, & Input [i]); INDEX = 0; } Else i = 0; MD5_MEMCPY (Pointer & Context-> Buffer [Index], (Pointer) & INPUT [i], Inputlen-i); } Void Md5Final (Digest, Context) Unsigned char digest [16]; MD5_CTX * Context; { UNSIGNED Char Bits [8]; Unsigned int index, padlen ENCODE (Bits, Context-> Count, 8); Index = (unsigned int) ((CONTEXT-> COUNT [0] >> 3) & 0x3F); Padlen = (INDEX <56)? (56 - INDEX): (120 - index); MD5UPDATE (Context, Padding, Padlen); MD5UPDATE (Context, Bits, 8); ENCODE (Digest, Context-> State, 16); MD5_MEMSET ((Pointer) Context, 0, SizeOf (* Context)); } Static Void Md5Transform (State, Block) Uint4 state [4]; UNSIGNED Char Block [64]; { Uint4 a = state [0], b = state [1], c = state [2], d = state [3], x [16]; Decode (X, Block, 64); / * First round cycle * / FF (A, B, C, D, X [0], S11, 0xD76AA478); / * 1 * / FF (D, A, B, C, X [1], S12, 0xE8C7B756); / * 2 * / FF (C, D, A, B, X [2], S13, 0x242070dB); / * 3 * / FF (B, C, D, A, X [3], S14, 0XC1BDCEEE); / * 4 * / FF (A, B, C, D, X [4], S11, 0xF57c0FAF); / * 5 * / FF (D, A, B, C, X [5], S12, 0X4787C62A); / * 6 * / FF (C, D, A, B, X [6], S13, 0xA8304613); / * 7 * / FF (B, C, D, A, X [7], S14, 0xFD469501); / * 8 * / FF (A, B, C, D, X [8], S11, 0x698098D8); / * 9 * / FF (D, A, B, C, X [9], S12, 0x8B44F7AF); / * 10 * / FF (C, D, A, B, X [10], S13, 0xFFFFFFF5BB1); / * 11 * / ff (B, C, D, A, X [11], S14, 0x895CD7BE); / * 12 * / FF (A, B, C, D, X [12], S11, 0x6B901122); / * 13 * / FF (D, A, B, C, X [13], S12, 0xFD987193); / * 14 * / FF (C, D, A, B, X [14], S13, 0XA679438E); / * 15 * / FF (B, C, D, A, X [15], S14, 0X49B40821); / * 16 * / / * Second round cycle * / GG (A, B, C, D, X [1], S21, 0XF61E2562); / * 17 * / GG (D, A, B, C, X [6], S22, 0XC040B340); / * 18 * / GG (C, D, A, B, X [11], S23, 0X265E5A51); / * 19 * / GG (B, C, D, A, X [0], S24, 0XE9B6C7AA); / * 20 * / GG (A, B, C, D, X [5], S21, 0XD62F105D); / * 21 * / GG (D, A, B, C, X [10], S22, 0x2441453); / * 22 * / GG (C, D, A, B, X [15], S23, 0XD8A1E681); / * 23 * / GG (B, C, D, A, X [4], S24, 0XE7D3FBC8); / * 24 * / GG (A, B, C, D, X [9], S21, 0X21E1CDE6); / * 25 * / GG (D, A, B, C, X [14], S22, 0XC33707D6); / * 26 * / GG (C, D, A, B, X [3], S23, 0xF4D50D87); / * 27 * / GG (B, C, D, A, X [8], S24, 0x455A14ED); / * 28 * / GG (A, B, C, D, X [13], S21, 0XA9E3E905); / * 29 * / GG (D, A, B, C, X [2], S22, 0XFCEFA3F8); / * 30 * / GG (C, D, A, B, X [7], S23, 0X676F02D9); / * 31 * / GG (B, C, D, A, X [12], S24, 0x8D2A4C8A); / * 32 * / / * Third round loop * / HH (A, B, C, D, X [5], S31, 0xFFFA3942); / * 33 * / HH (D, A, B, C, X [8], S32, 0x8771F681); / * 34 * / HH (C, D, A, B, X [11], S33, 0x6D9D6122); / * 35 * / HH (B, C, D, A, X [14], S34, 0xFDE5380C); / * 36 * / HH (A, B, C, D, X [1], S31, 0XA4BEEA44); / * 37 * / HH (D, A, B, C, X [4], S32, 0x4BDECFA9); / * 38 * / HH (C, D, A, B, X [7], S33, 0XF6BB4B60); / * 39 * / HH (B, C, D, A, X [10], S34, 0XBEBFBC70); / * 40 * / HH (A, B, C, D, X [13], S31, 0x289B7EC6); / * 41 * / HH (D, A, B, C, X [0], S32, 0XEAA127FA); / * 42 * / HH (C, D, A, B, X [3], S33, 0xD4EF3085); / * 43 * / HH (B, C, D, A, X [6], S34, 0X4881D05); / * 44 * / HH (A, B, C, D, X [9], S31, 0XD9D4D039); / * 45 * / HH (D, A, B, C, X [12], S32, 0xE6DB99E5); / * 46 * / HH (C, D, A, B, X [15], S33, 0x1FA27CF8); / * 47 * / HH (B, C, D, A, X [2], S34, 0XC4AC5665); / * 48 * / / * Fourth round cycle * / II (A, B, C, D, X [0], S41, 0XF4292244); / * 49 * / II (D, A, B, C, X [7], S42, 0x432AFF97); / * 50 * / II (C, D, A, B, X [14], S43, 0XAB9423A7); / * 51 * / II (B, C, D, A, X [5], S44, 0XFC93A039); / * 52 * / II (A, B, C, D, X [12], S41, 0X655B59C3); / * 53 * / II (D, A, B, C, X [3], S42, 0x8F0CCC92); / * 54 * / II (C, D, A, B, X [10], S43, 0xffeff47d); / * 55 * / II (B, C, D, A, X [1], S44, 0X85845DD1); / * 56 * / II (A, B, C, D, X [8], S41, 0X6FA87E4F); / * 57 * / II (D, A, B, C, X [15], S42, 0XFE2CE6E0); / * 58 * / Ii (C, D, A, B, X [6], S43, 0XA3014314); / * 59 * / II (B, C, D, A, X [13], S44, 0X4E0811A1); / * 60 * / II (A, B, C, D, X [4], S41, 0XF7537E82); / * 61 * / II (D, A, B, C, X [11], S42, 0XBD3AF235); / * 62 * / II (C, D, A, B, X [2], S43, 0x2AD7D2BB); / * 63 * / II (B, C, D, A, X [9], S44, 0XEB86D391); / * 64 * / State [0] = a; State [1] = B; State [2] = C; State [3] = D; MD5_MEMSET ((Pointer) X, 0, SizeOf (x)); } Static void Encode (Output, Input, Len) Unsigned char * OUTPUT; Uint4 * input; Unsigned int Len; { UNSIGNED INT I, J; For (i = 0, j = 0; j Output [j] = (unsigned char) (INPUT [I] & 0xFF); Output [J 1] = (Unsigned Char) ((INPUT [I] >> 8) & 0xFF); OUTPUT [J 2] = (unsigned char) ((INPUT [I] >> 16) & 0xFF); OUTPUT [J 3] = (Unsigned Char) ((INPUT [I] >> 24) & 0xFF); } } Static void Decode (Output, Input, Len) UINT4 * OUTPUT; UNSIGNED CHAR * INPUT Unsigned int Len; { UNSIGNED INT I, J; For (i = 0, j = 0; j OUTPUT [I] = ((uint4) INPUT [J]) | ((uint4) INPUT [J 1]) << 8) | ((UINT4) INPUT [J 2]) << 16) | ((uint4) INPUT [J 3]) << 24); } Static void MD5_Memcpy (Output, Input, LEN) Pointer Output; Pointer INPUT; Unsigned int Len; { Unsigned Int i; For (i = 0; i } Static void MD5_MEMSET (Output, Value, Len) Pointer Output; Int value; Unsigned int Len; { Unsigned Int i; For (i = 0; i (CHAR *) OUTPUT [I] = (char) value; } ---------------- C code end ----------
