projects / reactos.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
history | raw | HEAD
[NtUser]
[reactos.git] / reactos / base / applications / mstsc / ssl_calls.c
1 /*
2 This program is free software; you can redistribute it and/or modify
3 it under the terms of the GNU General Public License as published by
4 the Free Software Foundation; either version 2 of the License, or
5 (at your option) any later version.
6
7 This program is distributed in the hope that it will be useful,
8 but WITHOUT ANY WARRANTY; without even the implied warranty of
9 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10 GNU General Public License for more details.
11
12 You should have received a copy of the GNU General Public License along
13 with this program; if not, write to the Free Software Foundation, Inc.,
14 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
15
16 xrdp: A Remote Desktop Protocol server.
17 Copyright (C) Jay Sorg 2004-2005
18
19 ssl calls
20
21 */
22
23 #include "precomp.h"
24
25 #define APP_CC
26
27 /*****************************************************************************/
28 static void * g_malloc(int size, int zero)
29 {
30 void * p;
31
32 p = xmalloc(size);
33 if (zero)
34 {
35 memset(p, 0, size);
36 }
37 return p;
38 }
39
40 /*****************************************************************************/
41 static void g_free(void * in)
42 {
43 xfree(in);
44 }
45
46 /*****************************************************************************/
47 /*****************************************************************************/
48 /* rc4 stuff */
49 /* An implementation of the ARC4 algorithm
50 *
51 * Copyright (C) 2001-2003 Christophe Devine
52 */
53 struct rc4_state
54 {
55 int x;
56 int y;
57 int m[256];
58 };
59
60 /*****************************************************************************/
61 void* APP_CC
62 ssl_rc4_info_create(void)
63 {
64 return g_malloc(sizeof(struct rc4_state), 1);
65 }
66
67 /*****************************************************************************/
68 void APP_CC
69 ssl_rc4_info_delete(void* rc4_info)
70 {
71 g_free(rc4_info);
72 }
73
74 /*****************************************************************************/
75 void APP_CC
76 ssl_rc4_set_key(void* rc4_info, char* key, int len)
77 {
78 int i;
79 int j;
80 int k;
81 int a;
82 int* m;
83 struct rc4_state* s;
84
85 s = (struct rc4_state*)rc4_info;
86 s->x = 0;
87 s->y = 0;
88 m = s->m;
89 for (i = 0; i < 256; i++)
90 {
91 m[i] = i;
92 }
93 j = 0;
94 k = 0;
95 for (i = 0; i < 256; i++)
96 {
97 a = m[i];
98 j = (unsigned char)(j + a + key[k]);
99 m[i] = m[j];
100 m[j] = a;
101 k++;
102 if (k >= len)
103 {
104 k = 0;
105 }
106 }
107 }
108
109 /*****************************************************************************/
110 void APP_CC
111 ssl_rc4_crypt(void* rc4_info, char* in_data, char* out_data, int len)
112 {
113 int i;
114 int x;
115 int y;
116 int a;
117 int b;
118 int* m;
119 struct rc4_state* s;
120
121 s = (struct rc4_state*)rc4_info;
122 x = s->x;
123 y = s->y;
124 m = s->m;
125 for (i = 0; i < len; i++)
126 {
127 x = (unsigned char)(x + 1);
128 a = m[x];
129 y = (unsigned char)(y + a);
130 b = m[y];
131 m[x] = b;
132 m[y] = a;
133 out_data[i] = in_data[i] ^ (m[(unsigned char)(a + b)]);
134 }
135 s->x = x;
136 s->y = y;
137 }
138
139 /*****************************************************************************/
140 /*****************************************************************************/
141 /* sha1 stuff */
142 /* FIPS-180-1 compliant SHA-1 implementation
143 *
144 * Copyright (C) 2001-2003 Christophe Devine
145 */
146 struct sha1_context
147 {
148 int total[2];
149 int state[5];
150 char buffer[64];
151 };
152
153 /*****************************************************************************/
154 void* APP_CC
155 ssl_sha1_info_create(void)
156 {
157 return g_malloc(sizeof(struct sha1_context), 1);
158 }
159
160 /*****************************************************************************/
161 void APP_CC
162 ssl_sha1_info_delete(void* sha1_info)
163 {
164 g_free(sha1_info);
165 }
166
167 /*****************************************************************************/
168 void APP_CC
169 ssl_sha1_clear(void* sha1_info)
170 {
171 struct sha1_context* ctx;
172
173 ctx = (struct sha1_context*)sha1_info;
174 memset(ctx, 0, sizeof(struct sha1_context));
175 ctx->state[0] = 0x67452301;
176 ctx->state[1] = 0xEFCDAB89;
177 ctx->state[2] = 0x98BADCFE;
178 ctx->state[3] = 0x10325476;
179 ctx->state[4] = 0xC3D2E1F0;
180 }
181
182 #undef GET_UINT32
183 #define GET_UINT32(n, b, i) \
184 { \
185 (n) = ((b)[(i) + 0] << 24) | \
186 ((b)[(i) + 1] << 16) | \
187 ((b)[(i) + 2] << 8) | \
188 ((b)[(i) + 3] << 0); \
189 }
190
191 #undef PUT_UINT32
192 #define PUT_UINT32(n, b, i) \
193 { \
194 (b)[(i) + 0] = ((n) >> 24); \
195 (b)[(i) + 1] = ((n) >> 16); \
196 (b)[(i) + 2] = ((n) >> 8); \
197 (b)[(i) + 3] = ((n) >> 0); \
198 }
199
200 /*****************************************************************************/
201 static void APP_CC
202 sha1_process(struct sha1_context* ctx, char* in_data)
203 {
204 int temp;
205 int W[16];
206 int A;
207 int B;
208 int C;
209 int D;
210 int E;
211 unsigned char* data;
212
213 data = (unsigned char*)in_data;
214
215 GET_UINT32(W[0], data, 0);
216 GET_UINT32(W[1], data, 4);
217 GET_UINT32(W[2], data, 8);
218 GET_UINT32(W[3], data, 12);
219 GET_UINT32(W[4], data, 16);
220 GET_UINT32(W[5], data, 20);
221 GET_UINT32(W[6], data, 24);
222 GET_UINT32(W[7], data, 28);
223 GET_UINT32(W[8], data, 32);
224 GET_UINT32(W[9], data, 36);
225 GET_UINT32(W[10], data, 40);
226 GET_UINT32(W[11], data, 44);
227 GET_UINT32(W[12], data, 48);
228 GET_UINT32(W[13], data, 52);
229 GET_UINT32(W[14], data, 56);
230 GET_UINT32(W[15], data, 60);
231
232 #define S(x, n) ((x << n) | ((x & 0xFFFFFFFF) >> (32 - n)))
233
234 #define R(t) \
235 ( \
236 temp = W[(t - 3) & 0x0F] ^ \
237 W[(t - 8) & 0x0F] ^ \
238 W[(t - 14) & 0x0F] ^ \
239 W[(t - 0) & 0x0F], \
240 (W[t & 0x0F] = S(temp, 1)) \
241 )
242
243 #undef P
244 #define P(a, b, c, d, e, x) \
245 { \
246 e += S(a, 5) + F(b, c, d) + K + x; \
247 b = S(b, 30); \
248 }
249
250 A = ctx->state[0];
251 B = ctx->state[1];
252 C = ctx->state[2];
253 D = ctx->state[3];
254 E = ctx->state[4];
255
256 #define F(x, y, z) (z ^ (x & (y ^ z)))
257 #define K 0x5A827999
258
259 P(A, B, C, D, E, W[0]);
260 P(E, A, B, C, D, W[1]);
261 P(D, E, A, B, C, W[2]);
262 P(C, D, E, A, B, W[3]);
263 P(B, C, D, E, A, W[4]);
264 P(A, B, C, D, E, W[5]);
265 P(E, A, B, C, D, W[6]);
266 P(D, E, A, B, C, W[7]);
267 P(C, D, E, A, B, W[8]);
268 P(B, C, D, E, A, W[9]);
269 P(A, B, C, D, E, W[10]);
270 P(E, A, B, C, D, W[11]);
271 P(D, E, A, B, C, W[12]);
272 P(C, D, E, A, B, W[13]);
273 P(B, C, D, E, A, W[14]);
274 P(A, B, C, D, E, W[15]);
275 P(E, A, B, C, D, R(16));
276 P(D, E, A, B, C, R(17));
277 P(C, D, E, A, B, R(18));
278 P(B, C, D, E, A, R(19));
279
280 #undef K
281 #undef F
282
283 #define F(x, y, z) (x ^ y ^ z)
284 #define K 0x6ED9EBA1
285
286 P(A, B, C, D, E, R(20));
287 P(E, A, B, C, D, R(21));
288 P(D, E, A, B, C, R(22));
289 P(C, D, E, A, B, R(23));
290 P(B, C, D, E, A, R(24));
291 P(A, B, C, D, E, R(25));
292 P(E, A, B, C, D, R(26));
293 P(D, E, A, B, C, R(27));
294 P(C, D, E, A, B, R(28));
295 P(B, C, D, E, A, R(29));
296 P(A, B, C, D, E, R(30));
297 P(E, A, B, C, D, R(31));
298 P(D, E, A, B, C, R(32));
299 P(C, D, E, A, B, R(33));
300 P(B, C, D, E, A, R(34));
301 P(A, B, C, D, E, R(35));
302 P(E, A, B, C, D, R(36));
303 P(D, E, A, B, C, R(37));
304 P(C, D, E, A, B, R(38));
305 P(B, C, D, E, A, R(39));
306
307 #undef K
308 #undef F
309
310 #define F(x, y, z) ((x & y) | (z & (x | y)))
311 #define K 0x8F1BBCDC
312
313 P(A, B, C, D, E, R(40));
314 P(E, A, B, C, D, R(41));
315 P(D, E, A, B, C, R(42));
316 P(C, D, E, A, B, R(43));
317 P(B, C, D, E, A, R(44));
318 P(A, B, C, D, E, R(45));
319 P(E, A, B, C, D, R(46));
320 P(D, E, A, B, C, R(47));
321 P(C, D, E, A, B, R(48));
322 P(B, C, D, E, A, R(49));
323 P(A, B, C, D, E, R(50));
324 P(E, A, B, C, D, R(51));
325 P(D, E, A, B, C, R(52));
326 P(C, D, E, A, B, R(53));
327 P(B, C, D, E, A, R(54));
328 P(A, B, C, D, E, R(55));
329 P(E, A, B, C, D, R(56));
330 P(D, E, A, B, C, R(57));
331 P(C, D, E, A, B, R(58));
332 P(B, C, D, E, A, R(59));
333
334 #undef K
335 #undef F
336
337 #define F(x, y, z) (x ^ y ^ z)
338 #define K 0xCA62C1D6
339
340 P(A, B, C, D, E, R(60));
341 P(E, A, B, C, D, R(61));
342 P(D, E, A, B, C, R(62));
343 P(C, D, E, A, B, R(63));
344 P(B, C, D, E, A, R(64));
345 P(A, B, C, D, E, R(65));
346 P(E, A, B, C, D, R(66));
347 P(D, E, A, B, C, R(67));
348 P(C, D, E, A, B, R(68));
349 P(B, C, D, E, A, R(69));
350 P(A, B, C, D, E, R(70));
351 P(E, A, B, C, D, R(71));
352 P(D, E, A, B, C, R(72));
353 P(C, D, E, A, B, R(73));
354 P(B, C, D, E, A, R(74));
355 P(A, B, C, D, E, R(75));
356 P(E, A, B, C, D, R(76));
357 P(D, E, A, B, C, R(77));
358 P(C, D, E, A, B, R(78));
359 P(B, C, D, E, A, R(79));
360
361 #undef K
362 #undef F
363
364 ctx->state[0] += A;
365 ctx->state[1] += B;
366 ctx->state[2] += C;
367 ctx->state[3] += D;
368 ctx->state[4] += E;
369 }
370
371 /*****************************************************************************/
372 void APP_CC
373 ssl_sha1_transform(void* sha1_info, char* data, int len)
374 {
375 int left;
376 int fill;
377 struct sha1_context* ctx;
378
379 ctx = (struct sha1_context*)sha1_info;
380 if (len == 0)
381 {
382 return;
383 }
384 left = ctx->total[0] & 0x3F;
385 fill = 64 - left;
386 ctx->total[0] += len;
387 ctx->total[0] &= 0xFFFFFFFF;
388 if (ctx->total[0] < len)
389 {
390 ctx->total[1]++;
391 }
392 if (left && (len >= fill))
393 {
394 memcpy(ctx->buffer + left, data, fill);
395 sha1_process(ctx, ctx->buffer);
396 len -= fill;
397 data += fill;
398 left = 0;
399 }
400 while (len >= 64)
401 {
402 sha1_process(ctx, data);
403 len -= 64;
404 data += 64;
405 }
406 if (len != 0)
407 {
408 memcpy(ctx->buffer + left, data, len);
409 }
410 }
411
412 static unsigned char sha1_padding[64] =
413 {
414 0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
415 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
416 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
417 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
418 };
419
420 /*****************************************************************************/
421 void APP_CC
422 ssl_sha1_complete(void* sha1_info, char* data)
423 {
424 int last;
425 int padn;
426 int high;
427 int low;
428 char msglen[8];
429 struct sha1_context* ctx;
430
431 ctx = (struct sha1_context*)sha1_info;
432 high = (ctx->total[0] >> 29) | (ctx->total[1] << 3);
433 low = (ctx->total[0] << 3);
434 PUT_UINT32(high, msglen, 0);
435 PUT_UINT32(low, msglen, 4);
436 last = ctx->total[0] & 0x3F;
437 padn = (last < 56) ? (56 - last) : (120 - last);
438 ssl_sha1_transform(ctx, (char *)sha1_padding, padn);
439 ssl_sha1_transform(ctx, msglen, 8);
440 PUT_UINT32(ctx->state[0], data, 0);
441 PUT_UINT32(ctx->state[1], data, 4);
442 PUT_UINT32(ctx->state[2], data, 8);
443 PUT_UINT32(ctx->state[3], data, 12);
444 PUT_UINT32(ctx->state[4], data, 16);
445 }
446
447 /*****************************************************************************/
448 /*****************************************************************************/
449 /* md5 stuff */
450 /* RFC 1321 compliant MD5 implementation
451 *
452 * Copyright (C) 2001-2003 Christophe Devine
453 */
454
455 struct md5_context
456 {
457 int total[2];
458 int state[4];
459 char buffer[64];
460 };
461
462 /*****************************************************************************/
463 void* APP_CC
464 ssl_md5_info_create(void)
465 {
466 return g_malloc(sizeof(struct md5_context), 1);
467 }
468
469 /*****************************************************************************/
470 void APP_CC
471 ssl_md5_info_delete(void* md5_info)
472 {
473 g_free(md5_info);
474 }
475
476 /*****************************************************************************/
477 void APP_CC
478 ssl_md5_clear(void* md5_info)
479 {
480 struct md5_context* ctx;
481
482 ctx = (struct md5_context*)md5_info;
483 memset(ctx, 0, sizeof(struct md5_context));
484 ctx->state[0] = 0x67452301;
485 ctx->state[1] = 0xEFCDAB89;
486 ctx->state[2] = 0x98BADCFE;
487 ctx->state[3] = 0x10325476;
488 }
489
490 #undef GET_UINT32
491 #define GET_UINT32(n, b, i) \
492 { \
493 (n) = ((b)[(i) + 0] << 0) | \
494 ((b)[(i) + 1] << 8) | \
495 ((b)[(i) + 2] << 16) | \
496 ((b)[(i) + 3] << 24); \
497 }
498
499 #undef PUT_UINT32
500 #define PUT_UINT32(n, b, i) \
501 { \
502 (b)[(i) + 0] = ((n) >> 0); \
503 (b)[(i) + 1] = ((n) >> 8); \
504 (b)[(i) + 2] = ((n) >> 16); \
505 (b)[(i) + 3] = ((n) >> 24); \
506 }
507
508 /*****************************************************************************/
509 static void
510 md5_process(struct md5_context* ctx, char* in_data)
511 {
512 int X[16];
513 int A;
514 int B;
515 int C;
516 int D;
517 unsigned char* data;
518
519 data = (unsigned char*)in_data;
520 GET_UINT32(X[0], data, 0);
521 GET_UINT32(X[1], data, 4);
522 GET_UINT32(X[2], data, 8);
523 GET_UINT32(X[3], data, 12);
524 GET_UINT32(X[4], data, 16);
525 GET_UINT32(X[5], data, 20);
526 GET_UINT32(X[6], data, 24);
527 GET_UINT32(X[7], data, 28);
528 GET_UINT32(X[8], data, 32);
529 GET_UINT32(X[9], data, 36);
530 GET_UINT32(X[10], data, 40);
531 GET_UINT32(X[11], data, 44);
532 GET_UINT32(X[12], data, 48);
533 GET_UINT32(X[13], data, 52);
534 GET_UINT32(X[14], data, 56);
535 GET_UINT32(X[15], data, 60);
536
537 #define S(x, n) ((x << n) | ((x & 0xFFFFFFFF) >> (32 - n)))
538
539 #undef P
540 #define P(a, b, c, d, k, s, t) \
541 { \
542 a += F(b, c, d) + X[k] + t; \
543 a = S(a, s) + b; \
544 }
545
546 A = ctx->state[0];
547 B = ctx->state[1];
548 C = ctx->state[2];
549 D = ctx->state[3];
550
551 #define F(x, y, z) (z ^ (x & (y ^ z)))
552
553 P(A, B, C, D, 0, 7, 0xD76AA478);
554 P(D, A, B, C, 1, 12, 0xE8C7B756);
555 P(C, D, A, B, 2, 17, 0x242070DB);
556 P(B, C, D, A, 3, 22, 0xC1BDCEEE);
557 P(A, B, C, D, 4, 7, 0xF57C0FAF);
558 P(D, A, B, C, 5, 12, 0x4787C62A);
559 P(C, D, A, B, 6, 17, 0xA8304613);
560 P(B, C, D, A, 7, 22, 0xFD469501);
561 P(A, B, C, D, 8, 7, 0x698098D8);
562 P(D, A, B, C, 9, 12, 0x8B44F7AF);
563 P(C, D, A, B, 10, 17, 0xFFFF5BB1);
564 P(B, C, D, A, 11, 22, 0x895CD7BE);
565 P(A, B, C, D, 12, 7, 0x6B901122);
566 P(D, A, B, C, 13, 12, 0xFD987193);
567 P(C, D, A, B, 14, 17, 0xA679438E);
568 P(B, C, D, A, 15, 22, 0x49B40821);
569
570 #undef F
571
572 #define F(x, y, z) (y ^ (z & (x ^ y)))
573
574 P(A, B, C, D, 1, 5, 0xF61E2562);
575 P(D, A, B, C, 6, 9, 0xC040B340);
576 P(C, D, A, B, 11, 14, 0x265E5A51);
577 P(B, C, D, A, 0, 20, 0xE9B6C7AA);
578 P(A, B, C, D, 5, 5, 0xD62F105D);
579 P(D, A, B, C, 10, 9, 0x02441453);
580 P(C, D, A, B, 15, 14, 0xD8A1E681);
581 P(B, C, D, A, 4, 20, 0xE7D3FBC8);
582 P(A, B, C, D, 9, 5, 0x21E1CDE6);
583 P(D, A, B, C, 14, 9, 0xC33707D6);
584 P(C, D, A, B, 3, 14, 0xF4D50D87);
585 P(B, C, D, A, 8, 20, 0x455A14ED);
586 P(A, B, C, D, 13, 5, 0xA9E3E905);
587 P(D, A, B, C, 2, 9, 0xFCEFA3F8);
588 P(C, D, A, B, 7, 14, 0x676F02D9);
589 P(B, C, D, A, 12, 20, 0x8D2A4C8A);
590
591 #undef F
592
593 #define F(x, y, z) (x ^ y ^ z)
594
595 P(A, B, C, D, 5, 4, 0xFFFA3942);
596 P(D, A, B, C, 8, 11, 0x8771F681);
597 P(C, D, A, B, 11, 16, 0x6D9D6122);
598 P(B, C, D, A, 14, 23, 0xFDE5380C);
599 P(A, B, C, D, 1, 4, 0xA4BEEA44);
600 P(D, A, B, C, 4, 11, 0x4BDECFA9);
601 P(C, D, A, B, 7, 16, 0xF6BB4B60);
602 P(B, C, D, A, 10, 23, 0xBEBFBC70);
603 P(A, B, C, D, 13, 4, 0x289B7EC6);
604 P(D, A, B, C, 0, 11, 0xEAA127FA);
605 P(C, D, A, B, 3, 16, 0xD4EF3085);
606 P(B, C, D, A, 6, 23, 0x04881D05);
607 P(A, B, C, D, 9, 4, 0xD9D4D039);
608 P(D, A, B, C, 12, 11, 0xE6DB99E5);
609 P(C, D, A, B, 15, 16, 0x1FA27CF8);
610 P(B, C, D, A, 2, 23, 0xC4AC5665);
611
612 #undef F
613
614 #define F(x, y, z) (y ^ (x | ~z))
615
616 P(A, B, C, D, 0, 6, 0xF4292244);
617 P(D, A, B, C, 7, 10, 0x432AFF97);
618 P(C, D, A, B, 14, 15, 0xAB9423A7);
619 P(B, C, D, A, 5, 21, 0xFC93A039);
620 P(A, B, C, D, 12, 6, 0x655B59C3);
621 P(D, A, B, C, 3, 10, 0x8F0CCC92);
622 P(C, D, A, B, 10, 15, 0xFFEFF47D);
623 P(B, C, D, A, 1, 21, 0x85845DD1);
624 P(A, B, C, D, 8, 6, 0x6FA87E4F);
625 P(D, A, B, C, 15, 10, 0xFE2CE6E0);
626 P(C, D, A, B, 6, 15, 0xA3014314);
627 P(B, C, D, A, 13, 21, 0x4E0811A1);
628 P(A, B, C, D, 4, 6, 0xF7537E82);
629 P(D, A, B, C, 11, 10, 0xBD3AF235);
630 P(C, D, A, B, 2, 15, 0x2AD7D2BB);
631 P(B, C, D, A, 9, 21, 0xEB86D391);
632
633 #undef F
634
635 ctx->state[0] += A;
636 ctx->state[1] += B;
637 ctx->state[2] += C;
638 ctx->state[3] += D;
639 }
640
641 /*****************************************************************************/
642 void APP_CC
643 ssl_md5_transform(void* md5_info, char* data, int len)
644 {
645 int left;
646 int fill;
647 struct md5_context* ctx;
648
649 ctx = (struct md5_context*)md5_info;
650 if (len == 0)
651 {
652 return;
653 }
654 left = ctx->total[0] & 0x3F;
655 fill = 64 - left;
656 ctx->total[0] += len;
657 ctx->total[0] &= 0xFFFFFFFF;
658 if (ctx->total[0] < len)
659 {
660 ctx->total[1]++;
661 }
662 if (left && (len >= fill))
663 {
664 memcpy(ctx->buffer + left, data, fill);
665 md5_process(ctx, ctx->buffer);
666 len -= fill;
667 data += fill;
668 left = 0;
669 }
670 while (len >= 64)
671 {
672 md5_process(ctx, data);
673 len -= 64;
674 data += 64;
675 }
676 if (len != 0)
677 {
678 memcpy(ctx->buffer + left, data, len);
679 }
680 }
681
682 static unsigned char md5_padding[64] =
683 {
684 0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
685 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
686 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
687 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
688 };
689
690 /*****************************************************************************/
691 void APP_CC
692 ssl_md5_complete(void* md5_info, char* data)
693 {
694 int last;
695 int padn;
696 int high;
697 int low;
698 char msglen[8];
699 struct md5_context* ctx;
700
701 ctx = (struct md5_context*)md5_info;
702 high = (ctx->total[0] >> 29) | (ctx->total[1] << 3);
703 low = (ctx->total[0] << 3);
704 PUT_UINT32(low, msglen, 0);
705 PUT_UINT32(high, msglen, 4);
706 last = ctx->total[0] & 0x3F;
707 padn = (last < 56) ? (56 - last) : (120 - last);
708 ssl_md5_transform(ctx, (char *)md5_padding, padn);
709 ssl_md5_transform(ctx, msglen, 8);
710 PUT_UINT32(ctx->state[0], data, 0);
711 PUT_UINT32(ctx->state[1], data, 4);
712 PUT_UINT32(ctx->state[2], data, 8);
713 PUT_UINT32(ctx->state[3], data, 12);
714 }
715
716 void APP_CC ssl_hmac_md5(char* key, int keylen, char* data, int len, char* output)
717 {
718 int i;
719 char ipad[64];
720 char opad[64];
721 char sum[16];
722 void* ctx;
723
724 if( keylen > 64 )
725 {
726 ctx = ssl_md5_info_create();
727 ssl_md5_transform(ctx, key, keylen);
728 ssl_md5_complete(ctx, sum);
729 ssl_md5_info_delete(ctx);
730 keylen = 16;
731 key = sum;
732 }
733
734 memset( ipad, 0x36, sizeof(ipad) );
735 memset( opad, 0x5C, sizeof(opad) );
736
737 for( i = 0; i < keylen; i++ )
738 {
739 ipad[i] = ipad[i] ^ key[i];
740 opad[i] = opad[i] ^ key[i];
741 }
742 ctx = ssl_md5_info_create();
743 ssl_md5_transform(ctx, ipad, sizeof(ipad));
744 ssl_md5_transform(ctx, data, len);
745 ssl_md5_complete(ctx, sum);
746 ssl_md5_info_delete(ctx);
747 ctx = ssl_md5_info_create();
748 ssl_md5_transform(ctx, opad, sizeof(opad));
749 ssl_md5_complete(ctx, output);
750 ssl_md5_info_delete(ctx);
751 }
752
753 /*****************************************************************************/
754 /*****************************************************************************/
755 /* big number stuff */
756 /******************* SHORT COPYRIGHT NOTICE*************************
757 This source code is part of the BigDigits multiple-precision
758 arithmetic library Version 1.0 originally written by David Ireland,
759 copyright (c) 2001 D.I. Management Services Pty Limited, all rights
760 reserved. It is provided "as is" with no warranties. You may use
761 this software under the terms of the full copyright notice
762 "bigdigitsCopyright.txt" that should have been included with
763 this library. To obtain a copy send an email to
764 <code@di-mgt.com.au> or visit <www.di-mgt.com.au/crypto.html>.
765 This notice must be retained in any copy.
766 ****************** END OF COPYRIGHT NOTICE*************************/
767 /************************* COPYRIGHT NOTICE*************************
768 This source code is part of the BigDigits multiple-precision
769 arithmetic library Version 1.0 originally written by David Ireland,
770 copyright (c) 2001 D.I. Management Services Pty Limited, all rights
771 reserved. You are permitted to use compiled versions of this code as
772 part of your own executable files and to distribute unlimited copies
773 of such executable files for any purposes including commercial ones
774 provided you keep the copyright notices intact in the source code
775 and that you ensure that the following characters remain in any
776 object or executable files you distribute:
777
778 "Contains multiple-precision arithmetic code originally written
779 by David Ireland, copyright (c) 2001 by D.I. Management Services
780 Pty Limited <www.di-mgt.com.au>, and is used with permission."
781
782 David Ireland and DI Management Services Pty Limited make no
783 representations concerning either the merchantability of this
784 software or the suitability of this software for any particular
785 purpose. It is provided "as is" without express or implied warranty
786 of any kind.
787
788 Please forward any comments and bug reports to <code@di-mgt.com.au>.
789 The latest version of the source code can be downloaded from
790 www.di-mgt.com.au/crypto.html.
791 ****************** END OF COPYRIGHT NOTICE*************************/
792
793 typedef unsigned int DIGIT_T;
794 #define HIBITMASK 0x80000000
795 #define MAX_DIG_LEN 51
796 #define MAX_DIGIT 0xffffffff
797 #define BITS_PER_DIGIT 32
798 #define MAX_HALF_DIGIT 0xffff
799 #define B_J (MAX_HALF_DIGIT + 1)
800 #define LOHALF(x) ((DIGIT_T)((x) & 0xffff))
801 #define HIHALF(x) ((DIGIT_T)((x) >> 16 & 0xffff))
802 #define TOHIGH(x) ((DIGIT_T)((x) << 16))
803
804 #define mpNEXTBITMASK(mask, n) \
805 { \
806 if (mask == 1) \
807 { \
808 mask = HIBITMASK; \
809 n--; \
810 } \
811 else \
812 { \
813 mask >>= 1; \
814 } \
815 }
816
817 /*****************************************************************************/
818 static DIGIT_T APP_CC
819 mpAdd(DIGIT_T* w, DIGIT_T* u, DIGIT_T* v, unsigned int ndigits)
820 {
821 /* Calculates w = u + v
822 where w, u, v are multiprecision integers of ndigits each
823 Returns carry if overflow. Carry = 0 or 1.
824
825 Ref: Knuth Vol 2 Ch 4.3.1 p 266 Algorithm A. */
826 DIGIT_T k;
827 unsigned int j;
828
829 /* Step A1. Initialise */
830 k = 0;
831 for (j = 0; j < ndigits; j++)
832 {
833 /* Step A2. Add digits w_j = (u_j + v_j + k)
834 Set k = 1 if carry (overflow) occurs */
835 w[j] = u[j] + k;
836 if (w[j] < k)
837 {
838 k = 1;
839 }
840 else
841 {
842 k = 0;
843 }
844 w[j] += v[j];
845 if (w[j] < v[j])
846 {
847 k++;
848 }
849 } /* Step A3. Loop on j */
850 return k; /* w_n = k */
851 }
852
853 /*****************************************************************************/
854 static void APP_CC
855 mpSetDigit(DIGIT_T* a, DIGIT_T d, unsigned int ndigits)
856 { /* Sets a = d where d is a single digit */
857 unsigned int i;
858
859 for (i = 1; i < ndigits; i++)
860 {
861 a[i] = 0;
862 }
863 a[0] = d;
864 }
865
866 /*****************************************************************************/
867 static int APP_CC
868 mpCompare(DIGIT_T* a, DIGIT_T* b, unsigned int ndigits)
869 {
870 /* Returns sign of (a - b) */
871 if (ndigits == 0)
872 {
873 return 0;
874 }
875 while (ndigits--)
876 {
877 if (a[ndigits] > b[ndigits])
878 {
879 return 1; /* GT */
880 }
881 if (a[ndigits] < b[ndigits])
882 {
883 return -1; /* LT */
884 }
885 }
886 return 0; /* EQ */
887 }
888
889 /*****************************************************************************/
890 static void APP_CC
891 mpSetZero(DIGIT_T* a, unsigned int ndigits)
892 { /* Sets a = 0 */
893 unsigned int i;
894
895 for (i = 0; i < ndigits; i++)
896 {
897 a[i] = 0;
898 }
899 }
900
901 /*****************************************************************************/
902 static void APP_CC
903 mpSetEqual(DIGIT_T* a, DIGIT_T* b, unsigned int ndigits)
904 { /* Sets a = b */
905 unsigned int i;
906
907 for (i = 0; i < ndigits; i++)
908 {
909 a[i] = b[i];
910 }
911 }
912
913 /*****************************************************************************/
914 static unsigned int APP_CC
915 mpSizeof(DIGIT_T* a, unsigned int ndigits)
916 { /* Returns size of significant digits in a */
917 while (ndigits--)
918 {
919 if (a[ndigits] != 0)
920 {
921 return (++ndigits);
922 }
923 }
924 return 0;
925 }
926
927 /*****************************************************************************/
928 static DIGIT_T APP_CC
929 mpShiftLeft(DIGIT_T* a, DIGIT_T* b, unsigned int x, unsigned int ndigits)
930 { /* Computes a = b << x */
931 unsigned int i;
932 unsigned int y;
933 DIGIT_T mask;
934 DIGIT_T carry;
935 DIGIT_T nextcarry;
936
937 /* Check input - NB unspecified result */
938 if (x >= BITS_PER_DIGIT)
939 {
940 return 0;
941 }
942 /* Construct mask */
943 mask = HIBITMASK;
944 for (i = 1; i < x; i++)
945 {
946 mask = (mask >> 1) | mask;
947 }
948 if (x == 0)
949 {
950 mask = 0x0;
951 }
952 y = BITS_PER_DIGIT - x;
953 carry = 0;
954 for (i = 0; i < ndigits; i++)
955 {
956 nextcarry = (b[i] & mask) >> y;
957 a[i] = b[i] << x | carry;
958 carry = nextcarry;
959 }
960 return carry;
961 }
962
963 /*****************************************************************************/
964 static DIGIT_T APP_CC
965 mpShiftRight(DIGIT_T* a, DIGIT_T* b, unsigned int x, unsigned int ndigits)
966 { /* Computes a = b >> x */
967 unsigned int i;
968 unsigned int y;
969 DIGIT_T mask;
970 DIGIT_T carry;
971 DIGIT_T nextcarry;
972
973 /* Check input - NB unspecified result */
974 if (x >= BITS_PER_DIGIT)
975 {
976 return 0;
977 }
978 /* Construct mask */
979 mask = 0x1;
980 for (i = 1; i < x; i++)
981 {
982 mask = (mask << 1) | mask;
983 }
984 if (x == 0)
985 {
986 mask = 0x0;
987 }
988 y = BITS_PER_DIGIT - x;
989 carry = 0;
990 i = ndigits;
991 while (i--)
992 {
993 nextcarry = (b[i] & mask) << y;
994 a[i] = b[i] >> x | carry;
995 carry = nextcarry;
996 }
997 return carry;
998 }
999
1000 /*****************************************************************************/
1001 static void APP_CC
1002 spMultSub(DIGIT_T* uu, DIGIT_T qhat, DIGIT_T v1, DIGIT_T v0)
1003 {
1004 /* Compute uu = uu - q(v1v0)
1005 where uu = u3u2u1u0, u3 = 0
1006 and u_n, v_n are all half-digits
1007 even though v1, v2 are passed as full digits. */
1008 DIGIT_T p0;
1009 DIGIT_T p1;
1010 DIGIT_T t;
1011
1012 p0 = qhat * v0;
1013 p1 = qhat * v1;
1014 t = p0 + TOHIGH(LOHALF(p1));
1015 uu[0] -= t;
1016 if (uu[0] > MAX_DIGIT - t)
1017 {
1018 uu[1]--; /* Borrow */
1019 }
1020 uu[1] -= HIHALF(p1);
1021 }
1022
1023 /*****************************************************************************/
1024 static int APP_CC
1025 spMultiply(DIGIT_T* p, DIGIT_T x, DIGIT_T y)
1026 { /* Computes p = x * y */
1027 /* Ref: Arbitrary Precision Computation
1028 http://numbers.computation.free.fr/Constants/constants.html
1029
1030 high p1 p0 low
1031 +--------+--------+--------+--------+
1032 | x1*y1 | x0*y0 |
1033 +--------+--------+--------+--------+
1034 +-+--------+--------+
1035 |1| (x0*y1 + x1*y1) |
1036 +-+--------+--------+
1037 ^carry from adding (x0*y1+x1*y1) together
1038 +-+
1039 |1|< carry from adding LOHALF t
1040 +-+ to high half of p0 */
1041 DIGIT_T x0;
1042 DIGIT_T y0;
1043 DIGIT_T x1;
1044 DIGIT_T y1;
1045 DIGIT_T t;
1046 DIGIT_T u;
1047 DIGIT_T carry;
1048
1049 /* Split each x,y into two halves
1050 x = x0 + B * x1
1051 y = y0 + B * y1
1052 where B = 2^16, half the digit size
1053 Product is
1054 xy = x0y0 + B(x0y1 + x1y0) + B^2(x1y1) */
1055
1056 x0 = LOHALF(x);
1057 x1 = HIHALF(x);
1058 y0 = LOHALF(y);
1059 y1 = HIHALF(y);
1060
1061 /* Calc low part - no carry */
1062 p[0] = x0 * y0;
1063
1064 /* Calc middle part */
1065 t = x0 * y1;
1066 u = x1 * y0;
1067 t += u;
1068 if (t < u)
1069 {
1070 carry = 1;
1071 }
1072 else
1073 {
1074 carry = 0;
1075 }
1076 /* This carry will go to high half of p[1]
1077 + high half of t into low half of p[1] */
1078 carry = TOHIGH(carry) + HIHALF(t);
1079
1080 /* Add low half of t to high half of p[0] */
1081 t = TOHIGH(t);
1082 p[0] += t;
1083 if (p[0] < t)
1084 {
1085 carry++;
1086 }
1087
1088 p[1] = x1 * y1;
1089 p[1] += carry;
1090
1091 return 0;
1092 }
1093
1094 /*****************************************************************************/
1095 static DIGIT_T APP_CC
1096 spDivide(DIGIT_T* q, DIGIT_T* r, DIGIT_T* u, DIGIT_T v)
1097 { /* Computes quotient q = u / v, remainder r = u mod v
1098 where u is a double digit
1099 and q, v, r are single precision digits.
1100 Returns high digit of quotient (max value is 1)
1101 Assumes normalised such that v1 >= b/2
1102 where b is size of HALF_DIGIT
1103 i.e. the most significant bit of v should be one
1104
1105 In terms of half-digits in Knuth notation:
1106 (q2q1q0) = (u4u3u2u1u0) / (v1v0)
1107 (r1r0) = (u4u3u2u1u0) mod (v1v0)
1108 for m = 2, n = 2 where u4 = 0
1109 q2 is either 0 or 1.
1110 We set q = (q1q0) and return q2 as "overflow' */
1111 DIGIT_T qhat;
1112 DIGIT_T rhat;
1113 DIGIT_T t;
1114 DIGIT_T v0;
1115 DIGIT_T v1;
1116 DIGIT_T u0;
1117 DIGIT_T u1;
1118 DIGIT_T u2;
1119 DIGIT_T u3;
1120 DIGIT_T uu[2];
1121 DIGIT_T q2;
1122
1123 /* Check for normalisation */
1124 if (!(v & HIBITMASK))
1125 {
1126 *q = *r = 0;
1127 return MAX_DIGIT;
1128 }
1129
1130 /* Split up into half-digits */
1131 v0 = LOHALF(v);
1132 v1 = HIHALF(v);
1133 u0 = LOHALF(u[0]);
1134 u1 = HIHALF(u[0]);
1135 u2 = LOHALF(u[1]);
1136 u3 = HIHALF(u[1]);
1137
1138 /* Do three rounds of Knuth Algorithm D Vol 2 p272 */
1139
1140 /* ROUND 1. Set j = 2 and calculate q2 */
1141 /* Estimate qhat = (u4u3)/v1 = 0 or 1
1142 then set (u4u3u2) -= qhat(v1v0)
1143 where u4 = 0. */
1144 qhat = u3 / v1;
1145 if (qhat > 0)
1146 {
1147 rhat = u3 - qhat * v1;
1148 t = TOHIGH(rhat) | u2;
1149 if (qhat * v0 > t)
1150 {
1151 qhat--;
1152 }
1153 }
1154 uu[1] = 0; /* (u4) */
1155 uu[0] = u[1]; /* (u3u2) */
1156 if (qhat > 0)
1157 {
1158 /* (u4u3u2) -= qhat(v1v0) where u4 = 0 */
1159 spMultSub(uu, qhat, v1, v0);
1160 if (HIHALF(uu[1]) != 0)
1161 { /* Add back */
1162 qhat--;
1163 uu[0] += v;
1164 uu[1] = 0;
1165 }
1166 }
1167 q2 = qhat;
1168 /* ROUND 2. Set j = 1 and calculate q1 */
1169 /* Estimate qhat = (u3u2) / v1
1170 then set (u3u2u1) -= qhat(v1v0) */
1171 t = uu[0];
1172 qhat = t / v1;
1173 rhat = t - qhat * v1;
1174 /* Test on v0 */
1175 t = TOHIGH(rhat) | u1;
1176 if ((qhat == B_J) || (qhat * v0 > t))
1177 {
1178 qhat--;
1179 rhat += v1;
1180 t = TOHIGH(rhat) | u1;
1181 if ((rhat < B_J) && (qhat * v0 > t))
1182 {
1183 qhat--;
1184 }
1185 }
1186 /* Multiply and subtract
1187 (u3u2u1)' = (u3u2u1) - qhat(v1v0) */
1188 uu[1] = HIHALF(uu[0]); /* (0u3) */
1189 uu[0] = TOHIGH(LOHALF(uu[0])) | u1; /* (u2u1) */
1190 spMultSub(uu, qhat, v1, v0);
1191 if (HIHALF(uu[1]) != 0)
1192 { /* Add back */
1193 qhat--;
1194 uu[0] += v;
1195 uu[1] = 0;
1196 }
1197 /* q1 = qhat */
1198 *q = TOHIGH(qhat);
1199 /* ROUND 3. Set j = 0 and calculate q0 */
1200 /* Estimate qhat = (u2u1) / v1
1201 then set (u2u1u0) -= qhat(v1v0) */
1202 t = uu[0];
1203 qhat = t / v1;
1204 rhat = t - qhat * v1;
1205 /* Test on v0 */
1206 t = TOHIGH(rhat) | u0;
1207 if ((qhat == B_J) || (qhat * v0 > t))
1208 {
1209 qhat--;
1210 rhat += v1;
1211 t = TOHIGH(rhat) | u0;
1212 if ((rhat < B_J) && (qhat * v0 > t))
1213 {
1214 qhat--;
1215 }
1216 }
1217 /* Multiply and subtract
1218 (u2u1u0)" = (u2u1u0)' - qhat(v1v0) */
1219 uu[1] = HIHALF(uu[0]); /* (0u2) */
1220 uu[0] = TOHIGH(LOHALF(uu[0])) | u0; /* (u1u0) */
1221 spMultSub(uu, qhat, v1, v0);
1222 if (HIHALF(uu[1]) != 0)
1223 { /* Add back */
1224 qhat--;
1225 uu[0] += v;
1226 uu[1] = 0;
1227 }
1228 /* q0 = qhat */
1229 *q |= LOHALF(qhat);
1230 /* Remainder is in (u1u0) i.e. uu[0] */
1231 *r = uu[0];
1232 return q2;
1233 }
1234
1235 /*****************************************************************************/
1236 static int APP_CC
1237 QhatTooBig(DIGIT_T qhat, DIGIT_T rhat, DIGIT_T vn2, DIGIT_T ujn2)
1238 { /* Returns true if Qhat is too big
1239 i.e. if (Qhat * Vn-2) > (b.Rhat + Uj+n-2) */
1240 DIGIT_T t[2];
1241
1242 spMultiply(t, qhat, vn2);
1243 if (t[1] < rhat)
1244 {
1245 return 0;
1246 }
1247 else if (t[1] > rhat)
1248 {
1249 return 1;
1250 }
1251 else if (t[0] > ujn2)
1252 {
1253 return 1;
1254 }
1255 return 0;
1256 }
1257
1258 /*****************************************************************************/
1259 static DIGIT_T APP_CC
1260 mpShortDiv(DIGIT_T* q, DIGIT_T* u, DIGIT_T v, unsigned int ndigits)
1261 {
1262 /* Calculates quotient q = u div v
1263 Returns remainder r = u mod v
1264 where q, u are multiprecision integers of ndigits each
1265 and d, v are single precision digits.
1266
1267 Makes no assumptions about normalisation.
1268
1269 Ref: Knuth Vol 2 Ch 4.3.1 Exercise 16 p625 */
1270 unsigned int j;
1271 unsigned int shift;
1272 DIGIT_T t[2];
1273 DIGIT_T r;
1274 DIGIT_T bitmask;
1275 DIGIT_T overflow;
1276 DIGIT_T* uu;
1277
1278 if (ndigits == 0)
1279 {
1280 return 0;
1281 }
1282 if (v == 0)
1283 {
1284 return 0; /* Divide by zero error */
1285 }
1286 /* Normalise first */
1287 /* Requires high bit of V
1288 to be set, so find most signif. bit then shift left,
1289 i.e. d = 2^shift, u' = u * d, v' = v * d. */
1290 bitmask = HIBITMASK;
1291 for (shift = 0; shift < BITS_PER_DIGIT; shift++)
1292 {
1293 if (v & bitmask)
1294 {
1295 break;
1296 }
1297 bitmask >>= 1;
1298 }
1299 v <<= shift;
1300 overflow = mpShiftLeft(q, u, shift, ndigits);
1301 uu = q;
1302 /* Step S1 - modified for extra digit. */
1303 r = overflow; /* New digit Un */
1304 j = ndigits;
1305 while (j--)
1306 {
1307 /* Step S2. */
1308 t[1] = r;
1309 t[0] = uu[j];
1310 overflow = spDivide(&q[j], &r, t, v);
1311 }
1312 /* Unnormalise */
1313 r >>= shift;
1314 return r;
1315 }
1316
1317 /*****************************************************************************/
1318 static DIGIT_T APP_CC
1319 mpMultSub(DIGIT_T wn, DIGIT_T* w, DIGIT_T* v, DIGIT_T q, unsigned int n)
1320 { /* Compute w = w - qv
1321 where w = (WnW[n-1]...W[0])
1322 return modified Wn. */
1323 DIGIT_T k;
1324 DIGIT_T t[2];
1325 unsigned int i;
1326
1327 if (q == 0) /* No change */
1328 {
1329 return wn;
1330 }
1331 k = 0;
1332 for (i = 0; i < n; i++)
1333 {
1334 spMultiply(t, q, v[i]);
1335 w[i] -= k;
1336 if (w[i] > MAX_DIGIT - k)
1337 {
1338 k = 1;
1339 }
1340 else
1341 {
1342 k = 0;
1343 }
1344 w[i] -= t[0];
1345 if (w[i] > MAX_DIGIT - t[0])
1346 {
1347 k++;
1348 }
1349 k += t[1];
1350 }
1351 /* Cope with Wn not stored in array w[0..n-1] */
1352 wn -= k;
1353 return wn;
1354 }
1355
1356 /*****************************************************************************/
1357 static int APP_CC
1358 mpDivide(DIGIT_T* q, DIGIT_T* r, DIGIT_T* u, unsigned int udigits,
1359 DIGIT_T* v, unsigned int vdigits)
1360 { /* Computes quotient q = u / v and remainder r = u mod v
1361 where q, r, u are multiple precision digits
1362 all of udigits and the divisor v is vdigits.
1363
1364 Ref: Knuth Vol 2 Ch 4.3.1 p 272 Algorithm D.
1365
1366 Do without extra storage space, i.e. use r[] for
1367 normalised u[], unnormalise v[] at end, and cope with
1368 extra digit Uj+n added to u after normalisation.
1369
1370 WARNING: this trashes q and r first, so cannot do
1371 u = u / v or v = u mod v. */
1372 unsigned int shift;
1373 int n;
1374 int m;
1375 int j;
1376 int qhatOK;
1377 int cmp;
1378 DIGIT_T bitmask;
1379 DIGIT_T overflow;
1380 DIGIT_T qhat;
1381 DIGIT_T rhat;
1382 DIGIT_T t[2];
1383 DIGIT_T* uu;
1384 DIGIT_T* ww;
1385
1386 /* Clear q and r */
1387 mpSetZero(q, udigits);
1388 mpSetZero(r, udigits);
1389 /* Work out exact sizes of u and v */
1390 n = (int)mpSizeof(v, vdigits);
1391 m = (int)mpSizeof(u, udigits);
1392 m -= n;
1393 /* Catch special cases */
1394 if (n == 0)
1395 {
1396 return -1; /* Error: divide by zero */
1397 }
1398 if (n == 1)
1399 { /* Use short division instead */
1400 r[0] = mpShortDiv(q, u, v[0], udigits);
1401 return 0;
1402 }
1403 if (m < 0)
1404 { /* v > u, so just set q = 0 and r = u */
1405 mpSetEqual(r, u, udigits);
1406 return 0;
1407 }
1408 if (m == 0)
1409 { /* u and v are the same length */
1410 cmp = mpCompare(u, v, (unsigned int)n);
1411 if (cmp < 0)
1412 { /* v > u, as above */
1413 mpSetEqual(r, u, udigits);
1414 return 0;
1415 }
1416 else if (cmp == 0)
1417 { /* v == u, so set q = 1 and r = 0 */
1418 mpSetDigit(q, 1, udigits);
1419 return 0;
1420 }
1421 }
1422 /* In Knuth notation, we have:
1423 Given
1424 u = (Um+n-1 ... U1U0)
1425 v = (Vn-1 ... V1V0)
1426 Compute
1427 q = u/v = (QmQm-1 ... Q0)
1428 r = u mod v = (Rn-1 ... R1R0) */
1429 /* Step D1. Normalise */
1430 /* Requires high bit of Vn-1
1431 to be set, so find most signif. bit then shift left,
1432 i.e. d = 2^shift, u' = u * d, v' = v * d. */
1433 bitmask = HIBITMASK;
1434 for (shift = 0; shift < BITS_PER_DIGIT; shift++)
1435 {
1436 if (v[n - 1] & bitmask)
1437 {
1438 break;
1439 }
1440 bitmask >>= 1;
1441 }
1442 /* Normalise v in situ - NB only shift non-zero digits */
1443 overflow = mpShiftLeft(v, v, shift, n);
1444 /* Copy normalised dividend u*d into r */
1445 overflow = mpShiftLeft(r, u, shift, n + m);
1446 uu = r; /* Use ptr to keep notation constant */
1447 t[0] = overflow; /* New digit Um+n */
1448 /* Step D2. Initialise j. Set j = m */
1449 for (j = m; j >= 0; j--)
1450 {
1451 /* Step D3. Calculate Qhat = (b.Uj+n + Uj+n-1)/Vn-1 */
1452 qhatOK = 0;
1453 t[1] = t[0]; /* This is Uj+n */
1454 t[0] = uu[j+n-1];
1455 overflow = spDivide(&qhat, &rhat, t, v[n - 1]);
1456 /* Test Qhat */
1457 if (overflow)
1458 { /* Qhat = b */
1459 qhat = MAX_DIGIT;
1460 rhat = uu[j + n - 1];
1461 rhat += v[n - 1];
1462 if (rhat < v[n - 1]) /* Overflow */
1463 {
1464 qhatOK = 1;
1465 }
1466 }
1467 if (!qhatOK && QhatTooBig(qhat, rhat, v[n - 2], uu[j + n - 2]))
1468 { /* Qhat.Vn-2 > b.Rhat + Uj+n-2 */
1469 qhat--;
1470 rhat += v[n - 1];
1471 if (!(rhat < v[n - 1]))
1472 {
1473 if (QhatTooBig(qhat, rhat, v[n - 2], uu[j + n - 2]))
1474 {
1475 qhat--;
1476 }
1477 }
1478 }
1479 /* Step D4. Multiply and subtract */
1480 ww = &uu[j];
1481 overflow = mpMultSub(t[1], ww, v, qhat, (unsigned int)n);
1482 /* Step D5. Test remainder. Set Qj = Qhat */
1483 q[j] = qhat;
1484 if (overflow)
1485 { /* Step D6. Add back if D4 was negative */
1486 q[j]--;
1487 overflow = mpAdd(ww, ww, v, (unsigned int)n);
1488 }
1489 t[0] = uu[j + n - 1]; /* Uj+n on next round */
1490 } /* Step D7. Loop on j */
1491 /* Clear high digits in uu */
1492 for (j = n; j < m+n; j++)
1493 {
1494 uu[j] = 0;
1495 }
1496 /* Step D8. Unnormalise. */
1497 mpShiftRight(r, r, shift, n);
1498 mpShiftRight(v, v, shift, n);
1499 return 0;
1500 }
1501
1502 /*****************************************************************************/
1503 static int APP_CC
1504 mpModulo(DIGIT_T* r, DIGIT_T* u, unsigned int udigits,
1505 DIGIT_T* v, unsigned int vdigits)
1506 {
1507 /* Calculates r = u mod v
1508 where r, v are multiprecision integers of length vdigits
1509 and u is a multiprecision integer of length udigits.
1510 r may overlap v.
1511
1512 Note that r here is only vdigits long,
1513 whereas in mpDivide it is udigits long.
1514
1515 Use remainder from mpDivide function. */
1516 /* Double-length temp variable for divide fn */
1517 DIGIT_T qq[MAX_DIG_LEN * 2];
1518 /* Use a double-length temp for r to allow overlap of r and v */
1519 DIGIT_T rr[MAX_DIG_LEN * 2];
1520
1521 /* rr[2n] = u[2n] mod v[n] */
1522 mpDivide(qq, rr, u, udigits, v, vdigits);
1523 mpSetEqual(r, rr, vdigits);
1524 mpSetZero(rr, udigits);
1525 mpSetZero(qq, udigits);
1526 return 0;
1527 }
1528
1529 /*****************************************************************************/
1530 static int APP_CC
1531 mpMultiply(DIGIT_T* w, DIGIT_T* u, DIGIT_T* v, unsigned int ndigits)
1532 {
1533 /* Computes product w = u * v
1534 where u, v are multiprecision integers of ndigits each
1535 and w is a multiprecision integer of 2*ndigits
1536 Ref: Knuth Vol 2 Ch 4.3.1 p 268 Algorithm M. */
1537 DIGIT_T k;
1538 DIGIT_T t[2];
1539 unsigned int i;
1540 unsigned int j;
1541 unsigned int m;
1542 unsigned int n;
1543
1544 n = ndigits;
1545 m = n;
1546 /* Step M1. Initialise */
1547 for (i = 0; i < 2 * m; i++)
1548 {
1549 w[i] = 0;
1550 }
1551 for (j = 0; j < n; j++)
1552 {
1553 /* Step M2. Zero multiplier? */
1554 if (v[j] == 0)
1555 {
1556 w[j + m] = 0;
1557 }
1558 else
1559 {
1560 /* Step M3. Initialise i */
1561 k = 0;
1562 for (i = 0; i < m; i++)
1563 {
1564 /* Step M4. Multiply and add */
1565 /* t = u_i * v_j + w_(i+j) + k */
1566 spMultiply(t, u[i], v[j]);
1567 t[0] += k;
1568 if (t[0] < k)
1569 {
1570 t[1]++;
1571 }
1572 t[0] += w[i + j];
1573 if (t[0] < w[i+j])
1574 {
1575 t[1]++;
1576 }
1577 w[i + j] = t[0];
1578 k = t[1];
1579 }
1580 /* Step M5. Loop on i, set w_(j+m) = k */
1581 w[j + m] = k;
1582 }
1583 } /* Step M6. Loop on j */
1584 return 0;
1585 }
1586
1587 /*****************************************************************************/
1588 static int APP_CC
1589 mpModMult(DIGIT_T* a, DIGIT_T* x, DIGIT_T* y,
1590 DIGIT_T* m, unsigned int ndigits)
1591 { /* Computes a = (x * y) mod m */
1592 /* Double-length temp variable */
1593 DIGIT_T p[MAX_DIG_LEN * 2];
1594
1595 /* Calc p[2n] = x * y */
1596 mpMultiply(p, x, y, ndigits);
1597 /* Then modulo */
1598 mpModulo(a, p, ndigits * 2, m, ndigits);
1599 mpSetZero(p, ndigits * 2);
1600 return 0;
1601 }
1602
1603 /*****************************************************************************/
1604 int APP_CC
1605 ssl_mod_exp(char* out, int out_len, char* in, int in_len,
1606 char* mod, int mod_len, char* exp, int exp_len)
1607 {
1608 /* Computes y = x ^ e mod m */
1609 /* Binary left-to-right method */
1610 DIGIT_T mask;
1611 DIGIT_T* e;
1612 DIGIT_T* x;
1613 DIGIT_T* y;
1614 DIGIT_T* m;
1615 unsigned int n;
1616 int max_size;
1617 char* l_out;
1618 char* l_in;
1619 char* l_mod;
1620 char* l_exp;
1621
1622 if (in_len > out_len || in_len == 0 ||
1623 out_len == 0 || mod_len == 0 || exp_len == 0)
1624 {
1625 return 0;
1626 }
1627 max_size = out_len;
1628 if (in_len > max_size)
1629 {
1630 max_size = in_len;
1631 }
1632 if (mod_len > max_size)
1633 {
1634 max_size = mod_len;
1635 }
1636 if (exp_len > max_size)
1637 {
1638 max_size = exp_len;
1639 }
1640 l_out = (char*)g_malloc(max_size, 1);
1641 l_in = (char*)g_malloc(max_size, 1);
1642 l_mod = (char*)g_malloc(max_size, 1);
1643 l_exp = (char*)g_malloc(max_size, 1);
1644 memcpy(l_in, in, in_len);
1645 memcpy(l_mod, mod, mod_len);
1646 memcpy(l_exp, exp, exp_len);
1647 e = (DIGIT_T*)l_exp;
1648 x = (DIGIT_T*)l_in;
1649 y = (DIGIT_T*)l_out;
1650 m = (DIGIT_T*)l_mod;
1651 /* Find second-most significant bit in e */
1652 n = mpSizeof(e, max_size / 4);
1653 for (mask = HIBITMASK; mask > 0; mask >>= 1)
1654 {
1655 if (e[n - 1] & mask)
1656 {
1657 break;
1658 }
1659 }
1660 mpNEXTBITMASK(mask, n);
1661 /* Set y = x */
1662 mpSetEqual(y, x, max_size / 4);
1663 /* For bit j = k - 2 downto 0 step -1 */
1664 while (n)
1665 {
1666 mpModMult(y, y, y, m, max_size / 4); /* Square */
1667 if (e[n - 1] & mask)
1668 {
1669 mpModMult(y, y, x, m, max_size / 4); /* Multiply */
1670 }
1671 /* Move to next bit */
1672 mpNEXTBITMASK(mask, n);
1673 }
1674 memcpy(out, l_out, out_len);
1675 g_free(l_out);
1676 g_free(l_in);
1677 g_free(l_mod);
1678 g_free(l_exp);
1679 return out_len;
1680 }
1681
A free Windows-compatible Operating System