blob: f9bea0f57a758f44dc903df220adcca448d689af [file] [log] [blame]
Guido van Rossum13ecc7a1993-11-01 16:19:05 +00001/* MD5C.C - RSA Data Security, Inc., MD5 message-digest algorithm
2 */
3
4/* Copyright (C) 1991-2, RSA Data Security, Inc. Created 1991. All
5rights reserved.
6
7License to copy and use this software is granted provided that it
8is identified as the "RSA Data Security, Inc. MD5 Message-Digest
9Algorithm" in all material mentioning or referencing this software
10or this function.
11
12License is also granted to make and use derivative works provided
13that such works are identified as "derived from the RSA Data
14Security, Inc. MD5 Message-Digest Algorithm" in all material
15mentioning or referencing the derived work.
16
17RSA Data Security, Inc. makes no representations concerning either
18the merchantability of this software or the suitability of this
19software for any particular purpose. It is provided "as is"
20without express or implied warranty of any kind.
21
22These notices must be retained in any copies of any part of this
23documentation and/or software.
24 */
25
Fred Drakea6debec2000-09-28 02:54:51 +000026#include "Python.h"
Guido van Rossum13ecc7a1993-11-01 16:19:05 +000027#include "md5.h"
28
Fred Drake859bad02000-07-10 04:20:57 +000029/* Constants for MD5Transform routine. */
Guido van Rossum13ecc7a1993-11-01 16:19:05 +000030
31#define S11 7
32#define S12 12
33#define S13 17
34#define S14 22
35#define S21 5
36#define S22 9
37#define S23 14
38#define S24 20
39#define S31 4
40#define S32 11
41#define S33 16
42#define S34 23
43#define S41 6
44#define S42 10
45#define S43 15
46#define S44 21
47
Fred Drake859bad02000-07-10 04:20:57 +000048static void MD5Transform(UINT4[4], unsigned char[64]);
49static void Encode(unsigned char *, UINT4 *, unsigned int);
50static void Decode(UINT4 *, unsigned char *, unsigned int);
Guido van Rossum13ecc7a1993-11-01 16:19:05 +000051
52static unsigned char PADDING[64] = {
Fred Drake859bad02000-07-10 04:20:57 +000053 0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
54 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
55 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
Guido van Rossum13ecc7a1993-11-01 16:19:05 +000056};
57
Fred Drake859bad02000-07-10 04:20:57 +000058/* F, G, H and I are basic MD5 functions. */
Guido van Rossum13ecc7a1993-11-01 16:19:05 +000059#define F(x, y, z) (((x) & (y)) | ((~x) & (z)))
60#define G(x, y, z) (((x) & (z)) | ((y) & (~z)))
61#define H(x, y, z) ((x) ^ (y) ^ (z))
62#define I(x, y, z) ((y) ^ ((x) | (~z)))
63
Fred Drake859bad02000-07-10 04:20:57 +000064/* ROTATE_LEFT rotates x left n bits. */
Guido van Rossum13ecc7a1993-11-01 16:19:05 +000065#define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n))))
66
67/* FF, GG, HH, and II transformations for rounds 1, 2, 3, and 4.
Fred Drake859bad02000-07-10 04:20:57 +000068 Rotation is separate from addition to prevent recomputation.
Guido van Rossum13ecc7a1993-11-01 16:19:05 +000069 */
70#define FF(a, b, c, d, x, s, ac) { \
Fred Drake859bad02000-07-10 04:20:57 +000071 (a) += F ((b), (c), (d)) + (x) + (UINT4)(ac); \
72 (a) = ROTATE_LEFT ((a), (s)); \
73 (a) += (b); \
74 }
Guido van Rossum13ecc7a1993-11-01 16:19:05 +000075#define GG(a, b, c, d, x, s, ac) { \
Fred Drake859bad02000-07-10 04:20:57 +000076 (a) += G ((b), (c), (d)) + (x) + (UINT4)(ac); \
77 (a) = ROTATE_LEFT ((a), (s)); \
78 (a) += (b); \
79 }
Guido van Rossum13ecc7a1993-11-01 16:19:05 +000080#define HH(a, b, c, d, x, s, ac) { \
Fred Drake859bad02000-07-10 04:20:57 +000081 (a) += H ((b), (c), (d)) + (x) + (UINT4)(ac); \
82 (a) = ROTATE_LEFT ((a), (s)); \
83 (a) += (b); \
84 }
Guido van Rossum13ecc7a1993-11-01 16:19:05 +000085#define II(a, b, c, d, x, s, ac) { \
Fred Drake859bad02000-07-10 04:20:57 +000086 (a) += I ((b), (c), (d)) + (x) + (UINT4)(ac); \
87 (a) = ROTATE_LEFT ((a), (s)); \
88 (a) += (b); \
89 }
Guido van Rossum13ecc7a1993-11-01 16:19:05 +000090
Fred Drake859bad02000-07-10 04:20:57 +000091
92/* MD5 initialization. Begins an MD5 operation, writing a new context. */
93void
94MD5Init(MD5_CTX *context)
Guido van Rossum13ecc7a1993-11-01 16:19:05 +000095{
Fred Drake859bad02000-07-10 04:20:57 +000096 context->count[0] = context->count[1] = 0;
97 /* Load magic initialization constants. */
98 context->state[0] = 0x67452301;
99 context->state[1] = 0xefcdab89;
100 context->state[2] = 0x98badcfe;
101 context->state[3] = 0x10325476;
Guido van Rossum13ecc7a1993-11-01 16:19:05 +0000102}
103
Fred Drake859bad02000-07-10 04:20:57 +0000104
Guido van Rossum13ecc7a1993-11-01 16:19:05 +0000105/* MD5 block update operation. Continues an MD5 message-digest
Fred Drake859bad02000-07-10 04:20:57 +0000106 operation, processing another message block, and updating the
107 context.
Guido van Rossum13ecc7a1993-11-01 16:19:05 +0000108 */
Fred Drake859bad02000-07-10 04:20:57 +0000109void
110MD5Update(MD5_CTX *context, unsigned char *input, unsigned int inputLen)
Guido van Rossum13ecc7a1993-11-01 16:19:05 +0000111{
Fred Drake859bad02000-07-10 04:20:57 +0000112 unsigned int i, index, partLen;
Guido van Rossum13ecc7a1993-11-01 16:19:05 +0000113
Fred Drake859bad02000-07-10 04:20:57 +0000114 /* Compute number of bytes mod 64 */
115 index = (unsigned int)((context->count[0] >> 3) & 0x3F);
Guido van Rossum13ecc7a1993-11-01 16:19:05 +0000116
Fred Drake859bad02000-07-10 04:20:57 +0000117 /* Update number of bits */
118 if ((context->count[0] += ((UINT4)inputLen << 3))
119 < ((UINT4)inputLen << 3))
120 context->count[1]++;
121 context->count[1] += ((UINT4)inputLen >> 29);
Guido van Rossum13ecc7a1993-11-01 16:19:05 +0000122
Fred Drake859bad02000-07-10 04:20:57 +0000123 partLen = 64 - index;
Guido van Rossum13ecc7a1993-11-01 16:19:05 +0000124
Fred Drake859bad02000-07-10 04:20:57 +0000125 /* Transform as many times as possible. */
126 if (inputLen >= partLen) {
Martin v. Löwis287620f2001-09-24 17:14:40 +0000127 memcpy((POINTER)&context->buffer[index], (POINTER)input, partLen);
Fred Drake859bad02000-07-10 04:20:57 +0000128 MD5Transform(context->state, context->buffer);
Guido van Rossum13ecc7a1993-11-01 16:19:05 +0000129
Fred Drake859bad02000-07-10 04:20:57 +0000130 for (i = partLen; i + 63 < inputLen; i += 64)
131 MD5Transform(context->state, &input[i]);
Guido van Rossum13ecc7a1993-11-01 16:19:05 +0000132
Fred Drake859bad02000-07-10 04:20:57 +0000133 index = 0;
134 }
135 else
136 i = 0;
Guido van Rossum13ecc7a1993-11-01 16:19:05 +0000137
Fred Drake859bad02000-07-10 04:20:57 +0000138 /* Buffer remaining input */
Martin v. Löwis287620f2001-09-24 17:14:40 +0000139 memcpy((POINTER)&context->buffer[index],
Fred Drake859bad02000-07-10 04:20:57 +0000140 (POINTER)&input[i], inputLen-i);
Guido van Rossum13ecc7a1993-11-01 16:19:05 +0000141}
142
143/* MD5 finalization. Ends an MD5 message-digest operation, writing the
Walter Dörwaldf0dfc7a2003-10-20 14:01:56 +0000144 message digest and zeroing the context.
Guido van Rossum13ecc7a1993-11-01 16:19:05 +0000145 */
Fred Drake859bad02000-07-10 04:20:57 +0000146void
147MD5Final(unsigned char digest[16], MD5_CTX *context)
Guido van Rossum13ecc7a1993-11-01 16:19:05 +0000148{
Fred Drake859bad02000-07-10 04:20:57 +0000149 unsigned char bits[8];
150 unsigned int index, padLen;
Guido van Rossum13ecc7a1993-11-01 16:19:05 +0000151
Fred Drake859bad02000-07-10 04:20:57 +0000152 /* Save number of bits */
153 Encode (bits, context->count, 8);
Guido van Rossum13ecc7a1993-11-01 16:19:05 +0000154
Fred Drake859bad02000-07-10 04:20:57 +0000155 /* Pad out to 56 mod 64. */
156 index = (unsigned int)((context->count[0] >> 3) & 0x3f);
157 padLen = (index < 56) ? (56 - index) : (120 - index);
158 MD5Update(context, PADDING, padLen);
Guido van Rossum13ecc7a1993-11-01 16:19:05 +0000159
Fred Drake859bad02000-07-10 04:20:57 +0000160 /* Append length (before padding) */
161 MD5Update(context, bits, 8);
Guido van Rossum13ecc7a1993-11-01 16:19:05 +0000162
Fred Drake859bad02000-07-10 04:20:57 +0000163 /* Store state in digest */
164 Encode(digest, context->state, 16);
Guido van Rossum13ecc7a1993-11-01 16:19:05 +0000165
Fred Drake859bad02000-07-10 04:20:57 +0000166 /* Zeroize sensitive information. */
Martin v. Löwis287620f2001-09-24 17:14:40 +0000167 memset((POINTER)context, 0, sizeof (*context));
Guido van Rossum13ecc7a1993-11-01 16:19:05 +0000168}
169
Fred Drake859bad02000-07-10 04:20:57 +0000170
171/* MD5 basic transformation. Transforms state based on block. */
172static void
173MD5Transform(UINT4 state[4], unsigned char block[64])
Guido van Rossum13ecc7a1993-11-01 16:19:05 +0000174{
Fred Drake859bad02000-07-10 04:20:57 +0000175 UINT4 a = state[0], b = state[1], c = state[2], d = state[3], x[16];
Guido van Rossum13ecc7a1993-11-01 16:19:05 +0000176
Fred Drake859bad02000-07-10 04:20:57 +0000177 Decode (x, block, 64);
Guido van Rossum13ecc7a1993-11-01 16:19:05 +0000178
Fred Drake859bad02000-07-10 04:20:57 +0000179 /* Round 1 */
180 FF(a, b, c, d, x[ 0], S11, 0xd76aa478); /* 1 */
181 FF(d, a, b, c, x[ 1], S12, 0xe8c7b756); /* 2 */
182 FF(c, d, a, b, x[ 2], S13, 0x242070db); /* 3 */
183 FF(b, c, d, a, x[ 3], S14, 0xc1bdceee); /* 4 */
184 FF(a, b, c, d, x[ 4], S11, 0xf57c0faf); /* 5 */
185 FF(d, a, b, c, x[ 5], S12, 0x4787c62a); /* 6 */
186 FF(c, d, a, b, x[ 6], S13, 0xa8304613); /* 7 */
187 FF(b, c, d, a, x[ 7], S14, 0xfd469501); /* 8 */
188 FF(a, b, c, d, x[ 8], S11, 0x698098d8); /* 9 */
189 FF(d, a, b, c, x[ 9], S12, 0x8b44f7af); /* 10 */
190 FF(c, d, a, b, x[10], S13, 0xffff5bb1); /* 11 */
191 FF(b, c, d, a, x[11], S14, 0x895cd7be); /* 12 */
192 FF(a, b, c, d, x[12], S11, 0x6b901122); /* 13 */
193 FF(d, a, b, c, x[13], S12, 0xfd987193); /* 14 */
194 FF(c, d, a, b, x[14], S13, 0xa679438e); /* 15 */
195 FF(b, c, d, a, x[15], S14, 0x49b40821); /* 16 */
Guido van Rossum13ecc7a1993-11-01 16:19:05 +0000196
Fred Drake859bad02000-07-10 04:20:57 +0000197 /* Round 2 */
198 GG(a, b, c, d, x[ 1], S21, 0xf61e2562); /* 17 */
199 GG(d, a, b, c, x[ 6], S22, 0xc040b340); /* 18 */
200 GG(c, d, a, b, x[11], S23, 0x265e5a51); /* 19 */
201 GG(b, c, d, a, x[ 0], S24, 0xe9b6c7aa); /* 20 */
202 GG(a, b, c, d, x[ 5], S21, 0xd62f105d); /* 21 */
203 GG(d, a, b, c, x[10], S22, 0x2441453); /* 22 */
204 GG(c, d, a, b, x[15], S23, 0xd8a1e681); /* 23 */
205 GG(b, c, d, a, x[ 4], S24, 0xe7d3fbc8); /* 24 */
206 GG(a, b, c, d, x[ 9], S21, 0x21e1cde6); /* 25 */
207 GG(d, a, b, c, x[14], S22, 0xc33707d6); /* 26 */
208 GG(c, d, a, b, x[ 3], S23, 0xf4d50d87); /* 27 */
209 GG(b, c, d, a, x[ 8], S24, 0x455a14ed); /* 28 */
210 GG(a, b, c, d, x[13], S21, 0xa9e3e905); /* 29 */
211 GG(d, a, b, c, x[ 2], S22, 0xfcefa3f8); /* 30 */
212 GG(c, d, a, b, x[ 7], S23, 0x676f02d9); /* 31 */
213 GG(b, c, d, a, x[12], S24, 0x8d2a4c8a); /* 32 */
Guido van Rossum13ecc7a1993-11-01 16:19:05 +0000214
Fred Drake859bad02000-07-10 04:20:57 +0000215 /* Round 3 */
216 HH(a, b, c, d, x[ 5], S31, 0xfffa3942); /* 33 */
217 HH(d, a, b, c, x[ 8], S32, 0x8771f681); /* 34 */
218 HH(c, d, a, b, x[11], S33, 0x6d9d6122); /* 35 */
219 HH(b, c, d, a, x[14], S34, 0xfde5380c); /* 36 */
220 HH(a, b, c, d, x[ 1], S31, 0xa4beea44); /* 37 */
221 HH(d, a, b, c, x[ 4], S32, 0x4bdecfa9); /* 38 */
222 HH(c, d, a, b, x[ 7], S33, 0xf6bb4b60); /* 39 */
223 HH(b, c, d, a, x[10], S34, 0xbebfbc70); /* 40 */
224 HH(a, b, c, d, x[13], S31, 0x289b7ec6); /* 41 */
225 HH(d, a, b, c, x[ 0], S32, 0xeaa127fa); /* 42 */
226 HH(c, d, a, b, x[ 3], S33, 0xd4ef3085); /* 43 */
227 HH(b, c, d, a, x[ 6], S34, 0x4881d05); /* 44 */
228 HH(a, b, c, d, x[ 9], S31, 0xd9d4d039); /* 45 */
229 HH(d, a, b, c, x[12], S32, 0xe6db99e5); /* 46 */
230 HH(c, d, a, b, x[15], S33, 0x1fa27cf8); /* 47 */
231 HH(b, c, d, a, x[ 2], S34, 0xc4ac5665); /* 48 */
Guido van Rossum13ecc7a1993-11-01 16:19:05 +0000232
Fred Drake859bad02000-07-10 04:20:57 +0000233 /* Round 4 */
234 II(a, b, c, d, x[ 0], S41, 0xf4292244); /* 49 */
235 II(d, a, b, c, x[ 7], S42, 0x432aff97); /* 50 */
236 II(c, d, a, b, x[14], S43, 0xab9423a7); /* 51 */
237 II(b, c, d, a, x[ 5], S44, 0xfc93a039); /* 52 */
238 II(a, b, c, d, x[12], S41, 0x655b59c3); /* 53 */
239 II(d, a, b, c, x[ 3], S42, 0x8f0ccc92); /* 54 */
240 II(c, d, a, b, x[10], S43, 0xffeff47d); /* 55 */
241 II(b, c, d, a, x[ 1], S44, 0x85845dd1); /* 56 */
242 II(a, b, c, d, x[ 8], S41, 0x6fa87e4f); /* 57 */
243 II(d, a, b, c, x[15], S42, 0xfe2ce6e0); /* 58 */
244 II(c, d, a, b, x[ 6], S43, 0xa3014314); /* 59 */
245 II(b, c, d, a, x[13], S44, 0x4e0811a1); /* 60 */
246 II(a, b, c, d, x[ 4], S41, 0xf7537e82); /* 61 */
247 II(d, a, b, c, x[11], S42, 0xbd3af235); /* 62 */
248 II(c, d, a, b, x[ 2], S43, 0x2ad7d2bb); /* 63 */
249 II(b, c, d, a, x[ 9], S44, 0xeb86d391); /* 64 */
Guido van Rossum13ecc7a1993-11-01 16:19:05 +0000250
Fred Drake859bad02000-07-10 04:20:57 +0000251 state[0] += a;
252 state[1] += b;
253 state[2] += c;
254 state[3] += d;
Guido van Rossum13ecc7a1993-11-01 16:19:05 +0000255
Fred Drake859bad02000-07-10 04:20:57 +0000256 /* Zeroize sensitive information. */
Martin v. Löwis287620f2001-09-24 17:14:40 +0000257 memset((POINTER)x, 0, sizeof (x));
Guido van Rossum13ecc7a1993-11-01 16:19:05 +0000258}
259
Fred Drake859bad02000-07-10 04:20:57 +0000260
Guido van Rossum13ecc7a1993-11-01 16:19:05 +0000261/* Encodes input (UINT4) into output (unsigned char). Assumes len is
Fred Drake859bad02000-07-10 04:20:57 +0000262 a multiple of 4.
Guido van Rossum13ecc7a1993-11-01 16:19:05 +0000263 */
Fred Drake859bad02000-07-10 04:20:57 +0000264static void
265Encode(unsigned char *output, UINT4 *input, unsigned int len)
Guido van Rossum13ecc7a1993-11-01 16:19:05 +0000266{
Fred Drake859bad02000-07-10 04:20:57 +0000267 unsigned int i, j;
Guido van Rossum13ecc7a1993-11-01 16:19:05 +0000268
Fred Drake859bad02000-07-10 04:20:57 +0000269 for (i = 0, j = 0; j < len; i++, j += 4) {
270 output[j] = (unsigned char)(input[i] & 0xff);
271 output[j+1] = (unsigned char)((input[i] >> 8) & 0xff);
272 output[j+2] = (unsigned char)((input[i] >> 16) & 0xff);
273 output[j+3] = (unsigned char)((input[i] >> 24) & 0xff);
274 }
Guido van Rossum13ecc7a1993-11-01 16:19:05 +0000275}
276
Fred Drake859bad02000-07-10 04:20:57 +0000277
Guido van Rossum13ecc7a1993-11-01 16:19:05 +0000278/* Decodes input (unsigned char) into output (UINT4). Assumes len is
Fred Drake859bad02000-07-10 04:20:57 +0000279 a multiple of 4.
Guido van Rossum13ecc7a1993-11-01 16:19:05 +0000280 */
Fred Drake859bad02000-07-10 04:20:57 +0000281static void
282Decode(UINT4 *output, unsigned char *input, unsigned int len)
Guido van Rossum13ecc7a1993-11-01 16:19:05 +0000283{
Fred Drake859bad02000-07-10 04:20:57 +0000284 unsigned int i, j;
Guido van Rossum13ecc7a1993-11-01 16:19:05 +0000285
Fred Drake859bad02000-07-10 04:20:57 +0000286 for (i = 0, j = 0; j < len; i++, j += 4) {
287 output[i] = ((UINT4)input[j]) | (((UINT4)input[j+1]) << 8) |
288 (((UINT4)input[j+2]) << 16) | (((UINT4)input[j+3]) << 24);
289 }
Guido van Rossum13ecc7a1993-11-01 16:19:05 +0000290}