Ruby 1.9.3p327(2012-11-10revision37606)
|
00001 /* 00002 Copyright (C) 1999, 2000 Aladdin Enterprises. All rights reserved. 00003 00004 This software is provided 'as-is', without any express or implied 00005 warranty. In no event will the authors be held liable for any damages 00006 arising from the use of this software. 00007 00008 Permission is granted to anyone to use this software for any purpose, 00009 including commercial applications, and to alter it and redistribute it 00010 freely, subject to the following restrictions: 00011 00012 1. The origin of this software must not be misrepresented; you must not 00013 claim that you wrote the original software. If you use this software 00014 in a product, an acknowledgment in the product documentation would be 00015 appreciated but is not required. 00016 2. Altered source versions must be plainly marked as such, and must not be 00017 misrepresented as being the original software. 00018 3. This notice may not be removed or altered from any source distribution. 00019 00020 L. Peter Deutsch 00021 ghost@aladdin.com 00022 00023 */ 00024 00025 /* 00026 Independent implementation of MD5 (RFC 1321). 00027 00028 This code implements the MD5 Algorithm defined in RFC 1321. 00029 It is derived directly from the text of the RFC and not from the 00030 reference implementation. 00031 00032 The original and principal author of md5.c is L. Peter Deutsch 00033 <ghost@aladdin.com>. Other authors are noted in the change history 00034 that follows (in reverse chronological order): 00035 00036 2000-07-03 lpd Patched to eliminate warnings about "constant is 00037 unsigned in ANSI C, signed in traditional"; 00038 made test program self-checking. 00039 1999-11-04 lpd Edited comments slightly for automatic TOC extraction. 00040 1999-10-18 lpd Fixed typo in header comment (ansi2knr rather than md5). 00041 1999-05-03 lpd Original version. 00042 */ 00043 00044 /* 00045 This code was modified for use in Ruby. 00046 00047 - Akinori MUSHA <knu@idaemons.org> 00048 */ 00049 00050 /*$OrigId: md5c.c,v 1.2 2001/03/26 08:57:14 matz Exp $ */ 00051 /*$RoughId: md5.c,v 1.2 2001/07/13 19:48:41 knu Exp $ */ 00052 /*$Id: md5.c 25189 2009-10-02 12:04:37Z akr $ */ 00053 00054 #include "md5.h" 00055 00056 #ifdef TEST 00057 /* 00058 * Compile with -DTEST to create a self-contained executable test program. 00059 * The test program should print out the same values as given in section 00060 * A.5 of RFC 1321, reproduced below. 00061 */ 00062 #include <string.h> 00063 int 00064 main() 00065 { 00066 static const char *const test[7*2] = { 00067 "", "d41d8cd98f00b204e9800998ecf8427e", 00068 "a", "0cc175b9c0f1b6a831c399e269772661", 00069 "abc", "900150983cd24fb0d6963f7d28e17f72", 00070 "message digest", "f96b697d7cb7938d525a2f31aaf161d0", 00071 "abcdefghijklmnopqrstuvwxyz", "c3fcd3d76192e4007dfb496cca67e13b", 00072 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789", 00073 "d174ab98d277d9f5a5611c2c9f419d9f", 00074 "12345678901234567890123456789012345678901234567890123456789012345678901234567890", "57edf4a22be3c955ac49da2e2107b67a" 00075 }; 00076 int i; 00077 00078 for (i = 0; i < 7*2; i += 2) { 00079 MD5_CTX state; 00080 uint8_t digest[16]; 00081 char hex_output[16*2 + 1]; 00082 int di; 00083 00084 MD5_Init(&state); 00085 MD5_Update(&state, (const uint8_t *)test[i], strlen(test[i])); 00086 MD5_Final(digest, &state); 00087 printf("MD5 (\"%s\") = ", test[i]); 00088 for (di = 0; di < 16; ++di) 00089 sprintf(hex_output + di * 2, "%02x", digest[di]); 00090 puts(hex_output); 00091 if (strcmp(hex_output, test[i + 1])) 00092 printf("**** ERROR, should be: %s\n", test[i + 1]); 00093 } 00094 return 0; 00095 } 00096 #endif /* TEST */ 00097 00098 00099 /* 00100 * For reference, here is the program that computed the T values. 00101 */ 00102 #ifdef COMPUTE_T_VALUES 00103 #include <math.h> 00104 int 00105 main() 00106 { 00107 int i; 00108 for (i = 1; i <= 64; ++i) { 00109 unsigned long v = (unsigned long)(4294967296.0 * fabs(sin((double)i))); 00110 00111 /* 00112 * The following nonsense is only to avoid compiler warnings about 00113 * "integer constant is unsigned in ANSI C, signed with -traditional". 00114 */ 00115 if (v >> 31) { 00116 printf("#define T%d /* 0x%08lx */ (T_MASK ^ 0x%08lx)\n", i, 00117 v, (unsigned long)(unsigned int)(~v)); 00118 } else { 00119 printf("#define T%d 0x%08lx\n", i, v); 00120 } 00121 } 00122 return 0; 00123 } 00124 #endif /* COMPUTE_T_VALUES */ 00125 /* 00126 * End of T computation program. 00127 */ 00128 #ifdef T_MASK 00129 #undef T_MASK 00130 #endif 00131 #define T_MASK ((uint32_t)~0) 00132 #define T1 /* 0xd76aa478 */ (T_MASK ^ 0x28955b87) 00133 #define T2 /* 0xe8c7b756 */ (T_MASK ^ 0x173848a9) 00134 #define T3 0x242070db 00135 #define T4 /* 0xc1bdceee */ (T_MASK ^ 0x3e423111) 00136 #define T5 /* 0xf57c0faf */ (T_MASK ^ 0x0a83f050) 00137 #define T6 0x4787c62a 00138 #define T7 /* 0xa8304613 */ (T_MASK ^ 0x57cfb9ec) 00139 #define T8 /* 0xfd469501 */ (T_MASK ^ 0x02b96afe) 00140 #define T9 0x698098d8 00141 #define T10 /* 0x8b44f7af */ (T_MASK ^ 0x74bb0850) 00142 #define T11 /* 0xffff5bb1 */ (T_MASK ^ 0x0000a44e) 00143 #define T12 /* 0x895cd7be */ (T_MASK ^ 0x76a32841) 00144 #define T13 0x6b901122 00145 #define T14 /* 0xfd987193 */ (T_MASK ^ 0x02678e6c) 00146 #define T15 /* 0xa679438e */ (T_MASK ^ 0x5986bc71) 00147 #define T16 0x49b40821 00148 #define T17 /* 0xf61e2562 */ (T_MASK ^ 0x09e1da9d) 00149 #define T18 /* 0xc040b340 */ (T_MASK ^ 0x3fbf4cbf) 00150 #define T19 0x265e5a51 00151 #define T20 /* 0xe9b6c7aa */ (T_MASK ^ 0x16493855) 00152 #define T21 /* 0xd62f105d */ (T_MASK ^ 0x29d0efa2) 00153 #define T22 0x02441453 00154 #define T23 /* 0xd8a1e681 */ (T_MASK ^ 0x275e197e) 00155 #define T24 /* 0xe7d3fbc8 */ (T_MASK ^ 0x182c0437) 00156 #define T25 0x21e1cde6 00157 #define T26 /* 0xc33707d6 */ (T_MASK ^ 0x3cc8f829) 00158 #define T27 /* 0xf4d50d87 */ (T_MASK ^ 0x0b2af278) 00159 #define T28 0x455a14ed 00160 #define T29 /* 0xa9e3e905 */ (T_MASK ^ 0x561c16fa) 00161 #define T30 /* 0xfcefa3f8 */ (T_MASK ^ 0x03105c07) 00162 #define T31 0x676f02d9 00163 #define T32 /* 0x8d2a4c8a */ (T_MASK ^ 0x72d5b375) 00164 #define T33 /* 0xfffa3942 */ (T_MASK ^ 0x0005c6bd) 00165 #define T34 /* 0x8771f681 */ (T_MASK ^ 0x788e097e) 00166 #define T35 0x6d9d6122 00167 #define T36 /* 0xfde5380c */ (T_MASK ^ 0x021ac7f3) 00168 #define T37 /* 0xa4beea44 */ (T_MASK ^ 0x5b4115bb) 00169 #define T38 0x4bdecfa9 00170 #define T39 /* 0xf6bb4b60 */ (T_MASK ^ 0x0944b49f) 00171 #define T40 /* 0xbebfbc70 */ (T_MASK ^ 0x4140438f) 00172 #define T41 0x289b7ec6 00173 #define T42 /* 0xeaa127fa */ (T_MASK ^ 0x155ed805) 00174 #define T43 /* 0xd4ef3085 */ (T_MASK ^ 0x2b10cf7a) 00175 #define T44 0x04881d05 00176 #define T45 /* 0xd9d4d039 */ (T_MASK ^ 0x262b2fc6) 00177 #define T46 /* 0xe6db99e5 */ (T_MASK ^ 0x1924661a) 00178 #define T47 0x1fa27cf8 00179 #define T48 /* 0xc4ac5665 */ (T_MASK ^ 0x3b53a99a) 00180 #define T49 /* 0xf4292244 */ (T_MASK ^ 0x0bd6ddbb) 00181 #define T50 0x432aff97 00182 #define T51 /* 0xab9423a7 */ (T_MASK ^ 0x546bdc58) 00183 #define T52 /* 0xfc93a039 */ (T_MASK ^ 0x036c5fc6) 00184 #define T53 0x655b59c3 00185 #define T54 /* 0x8f0ccc92 */ (T_MASK ^ 0x70f3336d) 00186 #define T55 /* 0xffeff47d */ (T_MASK ^ 0x00100b82) 00187 #define T56 /* 0x85845dd1 */ (T_MASK ^ 0x7a7ba22e) 00188 #define T57 0x6fa87e4f 00189 #define T58 /* 0xfe2ce6e0 */ (T_MASK ^ 0x01d3191f) 00190 #define T59 /* 0xa3014314 */ (T_MASK ^ 0x5cfebceb) 00191 #define T60 0x4e0811a1 00192 #define T61 /* 0xf7537e82 */ (T_MASK ^ 0x08ac817d) 00193 #define T62 /* 0xbd3af235 */ (T_MASK ^ 0x42c50dca) 00194 #define T63 0x2ad7d2bb 00195 #define T64 /* 0xeb86d391 */ (T_MASK ^ 0x14792c6e) 00196 00197 00198 static void 00199 md5_process(MD5_CTX *pms, const uint8_t *data /*[64]*/) 00200 { 00201 uint32_t 00202 a = pms->state[0], b = pms->state[1], 00203 c = pms->state[2], d = pms->state[3]; 00204 uint32_t t; 00205 00206 #ifdef WORDS_BIGENDIAN 00207 00208 /* 00209 * On big-endian machines, we must arrange the bytes in the right 00210 * order. (This also works on machines of unknown byte order.) 00211 */ 00212 uint32_t X[16]; 00213 const uint8_t *xp = data; 00214 int i; 00215 00216 for (i = 0; i < 16; ++i, xp += 4) 00217 X[i] = xp[0] + (xp[1] << 8) + (xp[2] << 16) + (xp[3] << 24); 00218 00219 #else 00220 00221 /* 00222 * On little-endian machines, we can process properly aligned data 00223 * without copying it. 00224 */ 00225 uint32_t xbuf[16]; 00226 const uint32_t *X; 00227 00228 if (!((data - (const uint8_t *)0) & 3)) { 00229 /* data are properly aligned */ 00230 X = (const uint32_t *)data; 00231 } else { 00232 /* not aligned */ 00233 memcpy(xbuf, data, 64); 00234 X = xbuf; 00235 } 00236 #endif 00237 00238 #define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32 - (n)))) 00239 00240 /* Round 1. */ 00241 /* Let [abcd k s i] denote the operation 00242 a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s). */ 00243 #define F(x, y, z) (((x) & (y)) | (~(x) & (z))) 00244 #define SET(a, b, c, d, k, s, Ti)\ 00245 t = a + F(b,c,d) + X[k] + Ti;\ 00246 a = ROTATE_LEFT(t, s) + b 00247 /* Do the following 16 operations. */ 00248 SET(a, b, c, d, 0, 7, T1); 00249 SET(d, a, b, c, 1, 12, T2); 00250 SET(c, d, a, b, 2, 17, T3); 00251 SET(b, c, d, a, 3, 22, T4); 00252 SET(a, b, c, d, 4, 7, T5); 00253 SET(d, a, b, c, 5, 12, T6); 00254 SET(c, d, a, b, 6, 17, T7); 00255 SET(b, c, d, a, 7, 22, T8); 00256 SET(a, b, c, d, 8, 7, T9); 00257 SET(d, a, b, c, 9, 12, T10); 00258 SET(c, d, a, b, 10, 17, T11); 00259 SET(b, c, d, a, 11, 22, T12); 00260 SET(a, b, c, d, 12, 7, T13); 00261 SET(d, a, b, c, 13, 12, T14); 00262 SET(c, d, a, b, 14, 17, T15); 00263 SET(b, c, d, a, 15, 22, T16); 00264 #undef SET 00265 00266 /* Round 2. */ 00267 /* Let [abcd k s i] denote the operation 00268 a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s). */ 00269 #define G(x, y, z) (((x) & (z)) | ((y) & ~(z))) 00270 #define SET(a, b, c, d, k, s, Ti)\ 00271 t = a + G(b,c,d) + X[k] + Ti;\ 00272 a = ROTATE_LEFT(t, s) + b 00273 /* Do the following 16 operations. */ 00274 SET(a, b, c, d, 1, 5, T17); 00275 SET(d, a, b, c, 6, 9, T18); 00276 SET(c, d, a, b, 11, 14, T19); 00277 SET(b, c, d, a, 0, 20, T20); 00278 SET(a, b, c, d, 5, 5, T21); 00279 SET(d, a, b, c, 10, 9, T22); 00280 SET(c, d, a, b, 15, 14, T23); 00281 SET(b, c, d, a, 4, 20, T24); 00282 SET(a, b, c, d, 9, 5, T25); 00283 SET(d, a, b, c, 14, 9, T26); 00284 SET(c, d, a, b, 3, 14, T27); 00285 SET(b, c, d, a, 8, 20, T28); 00286 SET(a, b, c, d, 13, 5, T29); 00287 SET(d, a, b, c, 2, 9, T30); 00288 SET(c, d, a, b, 7, 14, T31); 00289 SET(b, c, d, a, 12, 20, T32); 00290 #undef SET 00291 00292 /* Round 3. */ 00293 /* Let [abcd k s t] denote the operation 00294 a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s). */ 00295 #define H(x, y, z) ((x) ^ (y) ^ (z)) 00296 #define SET(a, b, c, d, k, s, Ti)\ 00297 t = a + H(b,c,d) + X[k] + Ti;\ 00298 a = ROTATE_LEFT(t, s) + b 00299 /* Do the following 16 operations. */ 00300 SET(a, b, c, d, 5, 4, T33); 00301 SET(d, a, b, c, 8, 11, T34); 00302 SET(c, d, a, b, 11, 16, T35); 00303 SET(b, c, d, a, 14, 23, T36); 00304 SET(a, b, c, d, 1, 4, T37); 00305 SET(d, a, b, c, 4, 11, T38); 00306 SET(c, d, a, b, 7, 16, T39); 00307 SET(b, c, d, a, 10, 23, T40); 00308 SET(a, b, c, d, 13, 4, T41); 00309 SET(d, a, b, c, 0, 11, T42); 00310 SET(c, d, a, b, 3, 16, T43); 00311 SET(b, c, d, a, 6, 23, T44); 00312 SET(a, b, c, d, 9, 4, T45); 00313 SET(d, a, b, c, 12, 11, T46); 00314 SET(c, d, a, b, 15, 16, T47); 00315 SET(b, c, d, a, 2, 23, T48); 00316 #undef SET 00317 00318 /* Round 4. */ 00319 /* Let [abcd k s t] denote the operation 00320 a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s). */ 00321 #define I(x, y, z) ((y) ^ ((x) | ~(z))) 00322 #define SET(a, b, c, d, k, s, Ti)\ 00323 t = a + I(b,c,d) + X[k] + Ti;\ 00324 a = ROTATE_LEFT(t, s) + b 00325 /* Do the following 16 operations. */ 00326 SET(a, b, c, d, 0, 6, T49); 00327 SET(d, a, b, c, 7, 10, T50); 00328 SET(c, d, a, b, 14, 15, T51); 00329 SET(b, c, d, a, 5, 21, T52); 00330 SET(a, b, c, d, 12, 6, T53); 00331 SET(d, a, b, c, 3, 10, T54); 00332 SET(c, d, a, b, 10, 15, T55); 00333 SET(b, c, d, a, 1, 21, T56); 00334 SET(a, b, c, d, 8, 6, T57); 00335 SET(d, a, b, c, 15, 10, T58); 00336 SET(c, d, a, b, 6, 15, T59); 00337 SET(b, c, d, a, 13, 21, T60); 00338 SET(a, b, c, d, 4, 6, T61); 00339 SET(d, a, b, c, 11, 10, T62); 00340 SET(c, d, a, b, 2, 15, T63); 00341 SET(b, c, d, a, 9, 21, T64); 00342 #undef SET 00343 00344 /* Then perform the following additions. (That is increment each 00345 of the four registers by the value it had before this block 00346 was started.) */ 00347 pms->state[0] += a; 00348 pms->state[1] += b; 00349 pms->state[2] += c; 00350 pms->state[3] += d; 00351 } 00352 00353 void 00354 MD5_Init(MD5_CTX *pms) 00355 { 00356 pms->count[0] = pms->count[1] = 0; 00357 pms->state[0] = 0x67452301; 00358 pms->state[1] = /*0xefcdab89*/ T_MASK ^ 0x10325476; 00359 pms->state[2] = /*0x98badcfe*/ T_MASK ^ 0x67452301; 00360 pms->state[3] = 0x10325476; 00361 } 00362 00363 void 00364 MD5_Update(MD5_CTX *pms, const uint8_t *data, size_t nbytes) 00365 { 00366 const uint8_t *p = data; 00367 size_t left = nbytes; 00368 size_t offset = (pms->count[0] >> 3) & 63; 00369 uint32_t nbits = (uint32_t)(nbytes << 3); 00370 00371 if (nbytes <= 0) 00372 return; 00373 00374 /* Update the message length. */ 00375 pms->count[1] += nbytes >> 29; 00376 pms->count[0] += nbits; 00377 if (pms->count[0] < nbits) 00378 pms->count[1]++; 00379 00380 /* Process an initial partial block. */ 00381 if (offset) { 00382 size_t copy = (offset + nbytes > 64 ? 64 - offset : nbytes); 00383 00384 memcpy(pms->buffer + offset, p, copy); 00385 if (offset + copy < 64) 00386 return; 00387 p += copy; 00388 left -= copy; 00389 md5_process(pms, pms->buffer); 00390 } 00391 00392 /* Process full blocks. */ 00393 for (; left >= 64; p += 64, left -= 64) 00394 md5_process(pms, p); 00395 00396 /* Process a final partial block. */ 00397 if (left) 00398 memcpy(pms->buffer, p, left); 00399 } 00400 00401 void 00402 MD5_Finish(MD5_CTX *pms, uint8_t *digest) 00403 { 00404 static const uint8_t pad[64] = { 00405 0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 00406 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 00407 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 00408 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 00409 }; 00410 uint8_t data[8]; 00411 size_t i; 00412 00413 /* Save the length before padding. */ 00414 for (i = 0; i < 8; ++i) 00415 data[i] = (uint8_t)(pms->count[i >> 2] >> ((i & 3) << 3)); 00416 /* Pad to 56 bytes mod 64. */ 00417 MD5_Update(pms, pad, ((55 - (pms->count[0] >> 3)) & 63) + 1); 00418 /* Append the length. */ 00419 MD5_Update(pms, data, 8); 00420 for (i = 0; i < 16; ++i) 00421 digest[i] = (uint8_t)(pms->state[i >> 2] >> ((i & 3) << 3)); 00422 } 00423