projects / reactos.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
history | raw | HEAD
- Create another branch for networking fixes
[reactos.git] / 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 /*****************************************************************************/
717 /*****************************************************************************/
718 /* big number stuff */
719 /******************* SHORT COPYRIGHT NOTICE*************************
720 This source code is part of the BigDigits multiple-precision
721 arithmetic library Version 1.0 originally written by David Ireland,
722 copyright (c) 2001 D.I. Management Services Pty Limited, all rights
723 reserved. It is provided "as is" with no warranties. You may use
724 this software under the terms of the full copyright notice
725 "bigdigitsCopyright.txt" that should have been included with
726 this library. To obtain a copy send an email to
727 <code@di-mgt.com.au> or visit <www.di-mgt.com.au/crypto.html>.
728 This notice must be retained in any copy.
729 ****************** END OF COPYRIGHT NOTICE*************************/
730 /************************* COPYRIGHT NOTICE*************************
731 This source code is part of the BigDigits multiple-precision
732 arithmetic library Version 1.0 originally written by David Ireland,
733 copyright (c) 2001 D.I. Management Services Pty Limited, all rights
734 reserved. You are permitted to use compiled versions of this code as
735 part of your own executable files and to distribute unlimited copies
736 of such executable files for any purposes including commercial ones
737 provided you keep the copyright notices intact in the source code
738 and that you ensure that the following characters remain in any
739 object or executable files you distribute:
740
741 "Contains multiple-precision arithmetic code originally written
742 by David Ireland, copyright (c) 2001 by D.I. Management Services
743 Pty Limited <www.di-mgt.com.au>, and is used with permission."
744
745 David Ireland and DI Management Services Pty Limited make no
746 representations concerning either the merchantability of this
747 software or the suitability of this software for any particular
748 purpose. It is provided "as is" without express or implied warranty
749 of any kind.
750
751 Please forward any comments and bug reports to <code@di-mgt.com.au>.
752 The latest version of the source code can be downloaded from
753 www.di-mgt.com.au/crypto.html.
754 ****************** END OF COPYRIGHT NOTICE*************************/
755
756 typedef unsigned int DIGIT_T;
757 #define HIBITMASK 0x80000000
758 #define MAX_DIG_LEN 51
759 #define MAX_DIGIT 0xffffffff
760 #define BITS_PER_DIGIT 32
761 #define MAX_HALF_DIGIT 0xffff
762 #define B_J (MAX_HALF_DIGIT + 1)
763 #define LOHALF(x) ((DIGIT_T)((x) & 0xffff))
764 #define HIHALF(x) ((DIGIT_T)((x) >> 16 & 0xffff))
765 #define TOHIGH(x) ((DIGIT_T)((x) << 16))
766
767 #define mpNEXTBITMASK(mask, n) \
768 { \
769 if (mask == 1) \
770 { \
771 mask = HIBITMASK; \
772 n--; \
773 } \
774 else \
775 { \
776 mask >>= 1; \
777 } \
778 }
779
780 /*****************************************************************************/
781 static DIGIT_T APP_CC
782 mpAdd(DIGIT_T* w, DIGIT_T* u, DIGIT_T* v, unsigned int ndigits)
783 {
784 /* Calculates w = u + v
785 where w, u, v are multiprecision integers of ndigits each
786 Returns carry if overflow. Carry = 0 or 1.
787
788 Ref: Knuth Vol 2 Ch 4.3.1 p 266 Algorithm A. */
789 DIGIT_T k;
790 unsigned int j;
791
792 /* Step A1. Initialise */
793 k = 0;
794 for (j = 0; j < ndigits; j++)
795 {
796 /* Step A2. Add digits w_j = (u_j + v_j + k)
797 Set k = 1 if carry (overflow) occurs */
798 w[j] = u[j] + k;
799 if (w[j] < k)
800 {
801 k = 1;
802 }
803 else
804 {
805 k = 0;
806 }
807 w[j] += v[j];
808 if (w[j] < v[j])
809 {
810 k++;
811 }
812 } /* Step A3. Loop on j */
813 return k; /* w_n = k */
814 }
815
816 /*****************************************************************************/
817 static void APP_CC
818 mpSetDigit(DIGIT_T* a, DIGIT_T d, unsigned int ndigits)
819 { /* Sets a = d where d is a single digit */
820 unsigned int i;
821
822 for (i = 1; i < ndigits; i++)
823 {
824 a[i] = 0;
825 }
826 a[0] = d;
827 }
828
829 /*****************************************************************************/
830 static int APP_CC
831 mpCompare(DIGIT_T* a, DIGIT_T* b, unsigned int ndigits)
832 {
833 /* Returns sign of (a - b) */
834 if (ndigits == 0)
835 {
836 return 0;
837 }
838 while (ndigits--)
839 {
840 if (a[ndigits] > b[ndigits])
841 {
842 return 1; /* GT */
843 }
844 if (a[ndigits] < b[ndigits])
845 {
846 return -1; /* LT */
847 }
848 }
849 return 0; /* EQ */
850 }
851
852 /*****************************************************************************/
853 static void APP_CC
854 mpSetZero(DIGIT_T* a, unsigned int ndigits)
855 { /* Sets a = 0 */
856 unsigned int i;
857
858 for (i = 0; i < ndigits; i++)
859 {
860 a[i] = 0;
861 }
862 }
863
864 /*****************************************************************************/
865 static void APP_CC
866 mpSetEqual(DIGIT_T* a, DIGIT_T* b, unsigned int ndigits)
867 { /* Sets a = b */
868 unsigned int i;
869
870 for (i = 0; i < ndigits; i++)
871 {
872 a[i] = b[i];
873 }
874 }
875
876 /*****************************************************************************/
877 static unsigned int APP_CC
878 mpSizeof(DIGIT_T* a, unsigned int ndigits)
879 { /* Returns size of significant digits in a */
880 while (ndigits--)
881 {
882 if (a[ndigits] != 0)
883 {
884 return (++ndigits);
885 }
886 }
887 return 0;
888 }
889
890 /*****************************************************************************/
891 static DIGIT_T APP_CC
892 mpShiftLeft(DIGIT_T* a, DIGIT_T* b, unsigned int x, unsigned int ndigits)
893 { /* Computes a = b << x */
894 unsigned int i;
895 unsigned int y;
896 DIGIT_T mask;
897 DIGIT_T carry;
898 DIGIT_T nextcarry;
899
900 /* Check input - NB unspecified result */
901 if (x >= BITS_PER_DIGIT)
902 {
903 return 0;
904 }
905 /* Construct mask */
906 mask = HIBITMASK;
907 for (i = 1; i < x; i++)
908 {
909 mask = (mask >> 1) | mask;
910 }
911 if (x == 0)
912 {
913 mask = 0x0;
914 }
915 y = BITS_PER_DIGIT - x;
916 carry = 0;
917 for (i = 0; i < ndigits; i++)
918 {
919 nextcarry = (b[i] & mask) >> y;
920 a[i] = b[i] << x | carry;
921 carry = nextcarry;
922 }
923 return carry;
924 }
925
926 /*****************************************************************************/
927 static DIGIT_T APP_CC
928 mpShiftRight(DIGIT_T* a, DIGIT_T* b, unsigned int x, unsigned int ndigits)
929 { /* Computes a = b >> x */
930 unsigned int i;
931 unsigned int y;
932 DIGIT_T mask;
933 DIGIT_T carry;
934 DIGIT_T nextcarry;
935
936 /* Check input - NB unspecified result */
937 if (x >= BITS_PER_DIGIT)
938 {
939 return 0;
940 }
941 /* Construct mask */
942 mask = 0x1;
943 for (i = 1; i < x; i++)
944 {
945 mask = (mask << 1) | mask;
946 }
947 if (x == 0)
948 {
949 mask = 0x0;
950 }
951 y = BITS_PER_DIGIT - x;
952 carry = 0;
953 i = ndigits;
954 while (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 void APP_CC
965 spMultSub(DIGIT_T* uu, DIGIT_T qhat, DIGIT_T v1, DIGIT_T v0)
966 {
967 /* Compute uu = uu - q(v1v0)
968 where uu = u3u2u1u0, u3 = 0
969 and u_n, v_n are all half-digits
970 even though v1, v2 are passed as full digits. */
971 DIGIT_T p0;
972 DIGIT_T p1;
973 DIGIT_T t;
974
975 p0 = qhat * v0;
976 p1 = qhat * v1;
977 t = p0 + TOHIGH(LOHALF(p1));
978 uu[0] -= t;
979 if (uu[0] > MAX_DIGIT - t)
980 {
981 uu[1]--; /* Borrow */
982 }
983 uu[1] -= HIHALF(p1);
984 }
985
986 /*****************************************************************************/
987 static int APP_CC
988 spMultiply(DIGIT_T* p, DIGIT_T x, DIGIT_T y)
989 { /* Computes p = x * y */
990 /* Ref: Arbitrary Precision Computation
991 http://numbers.computation.free.fr/Constants/constants.html
992
993 high p1 p0 low
994 +--------+--------+--------+--------+
995 | x1*y1 | x0*y0 |
996 +--------+--------+--------+--------+
997 +-+--------+--------+
998 |1| (x0*y1 + x1*y1) |
999 +-+--------+--------+
1000 ^carry from adding (x0*y1+x1*y1) together
1001 +-+
1002 |1|< carry from adding LOHALF t
1003 +-+ to high half of p0 */
1004 DIGIT_T x0;
1005 DIGIT_T y0;
1006 DIGIT_T x1;
1007 DIGIT_T y1;
1008 DIGIT_T t;
1009 DIGIT_T u;
1010 DIGIT_T carry;
1011
1012 /* Split each x,y into two halves
1013 x = x0 + B * x1
1014 y = y0 + B * y1
1015 where B = 2^16, half the digit size
1016 Product is
1017 xy = x0y0 + B(x0y1 + x1y0) + B^2(x1y1) */
1018
1019 x0 = LOHALF(x);
1020 x1 = HIHALF(x);
1021 y0 = LOHALF(y);
1022 y1 = HIHALF(y);
1023
1024 /* Calc low part - no carry */
1025 p[0] = x0 * y0;
1026
1027 /* Calc middle part */
1028 t = x0 * y1;
1029 u = x1 * y0;
1030 t += u;
1031 if (t < u)
1032 {
1033 carry = 1;
1034 }
1035 else
1036 {
1037 carry = 0;
1038 }
1039 /* This carry will go to high half of p[1]
1040 + high half of t into low half of p[1] */
1041 carry = TOHIGH(carry) + HIHALF(t);
1042
1043 /* Add low half of t to high half of p[0] */
1044 t = TOHIGH(t);
1045 p[0] += t;
1046 if (p[0] < t)
1047 {
1048 carry++;
1049 }
1050
1051 p[1] = x1 * y1;
1052 p[1] += carry;
1053
1054 return 0;
1055 }
1056
1057 /*****************************************************************************/
1058 static DIGIT_T APP_CC
1059 spDivide(DIGIT_T* q, DIGIT_T* r, DIGIT_T* u, DIGIT_T v)
1060 { /* Computes quotient q = u / v, remainder r = u mod v
1061 where u is a double digit
1062 and q, v, r are single precision digits.
1063 Returns high digit of quotient (max value is 1)
1064 Assumes normalised such that v1 >= b/2
1065 where b is size of HALF_DIGIT
1066 i.e. the most significant bit of v should be one
1067
1068 In terms of half-digits in Knuth notation:
1069 (q2q1q0) = (u4u3u2u1u0) / (v1v0)
1070 (r1r0) = (u4u3u2u1u0) mod (v1v0)
1071 for m = 2, n = 2 where u4 = 0
1072 q2 is either 0 or 1.
1073 We set q = (q1q0) and return q2 as "overflow' */
1074 DIGIT_T qhat;
1075 DIGIT_T rhat;
1076 DIGIT_T t;
1077 DIGIT_T v0;
1078 DIGIT_T v1;
1079 DIGIT_T u0;
1080 DIGIT_T u1;
1081 DIGIT_T u2;
1082 DIGIT_T u3;
1083 DIGIT_T uu[2];
1084 DIGIT_T q2;
1085
1086 /* Check for normalisation */
1087 if (!(v & HIBITMASK))
1088 {
1089 *q = *r = 0;
1090 return MAX_DIGIT;
1091 }
1092
1093 /* Split up into half-digits */
1094 v0 = LOHALF(v);
1095 v1 = HIHALF(v);
1096 u0 = LOHALF(u[0]);
1097 u1 = HIHALF(u[0]);
1098 u2 = LOHALF(u[1]);
1099 u3 = HIHALF(u[1]);
1100
1101 /* Do three rounds of Knuth Algorithm D Vol 2 p272 */
1102
1103 /* ROUND 1. Set j = 2 and calculate q2 */
1104 /* Estimate qhat = (u4u3)/v1 = 0 or 1
1105 then set (u4u3u2) -= qhat(v1v0)
1106 where u4 = 0. */
1107 qhat = u3 / v1;
1108 if (qhat > 0)
1109 {
1110 rhat = u3 - qhat * v1;
1111 t = TOHIGH(rhat) | u2;
1112 if (qhat * v0 > t)
1113 {
1114 qhat--;
1115 }
1116 }
1117 uu[1] = 0; /* (u4) */
1118 uu[0] = u[1]; /* (u3u2) */
1119 if (qhat > 0)
1120 {
1121 /* (u4u3u2) -= qhat(v1v0) where u4 = 0 */
1122 spMultSub(uu, qhat, v1, v0);
1123 if (HIHALF(uu[1]) != 0)
1124 { /* Add back */
1125 qhat--;
1126 uu[0] += v;
1127 uu[1] = 0;
1128 }
1129 }
1130 q2 = qhat;
1131 /* ROUND 2. Set j = 1 and calculate q1 */
1132 /* Estimate qhat = (u3u2) / v1
1133 then set (u3u2u1) -= qhat(v1v0) */
1134 t = uu[0];
1135 qhat = t / v1;
1136 rhat = t - qhat * v1;
1137 /* Test on v0 */
1138 t = TOHIGH(rhat) | u1;
1139 if ((qhat == B_J) || (qhat * v0 > t))
1140 {
1141 qhat--;
1142 rhat += v1;
1143 t = TOHIGH(rhat) | u1;
1144 if ((rhat < B_J) && (qhat * v0 > t))
1145 {
1146 qhat--;
1147 }
1148 }
1149 /* Multiply and subtract
1150 (u3u2u1)' = (u3u2u1) - qhat(v1v0) */
1151 uu[1] = HIHALF(uu[0]); /* (0u3) */
1152 uu[0] = TOHIGH(LOHALF(uu[0])) | u1; /* (u2u1) */
1153 spMultSub(uu, qhat, v1, v0);
1154 if (HIHALF(uu[1]) != 0)
1155 { /* Add back */
1156 qhat--;
1157 uu[0] += v;
1158 uu[1] = 0;
1159 }
1160 /* q1 = qhat */
1161 *q = TOHIGH(qhat);
1162 /* ROUND 3. Set j = 0 and calculate q0 */
1163 /* Estimate qhat = (u2u1) / v1
1164 then set (u2u1u0) -= qhat(v1v0) */
1165 t = uu[0];
1166 qhat = t / v1;
1167 rhat = t - qhat * v1;
1168 /* Test on v0 */
1169 t = TOHIGH(rhat) | u0;
1170 if ((qhat == B_J) || (qhat * v0 > t))
1171 {
1172 qhat--;
1173 rhat += v1;
1174 t = TOHIGH(rhat) | u0;
1175 if ((rhat < B_J) && (qhat * v0 > t))
1176 {
1177 qhat--;
1178 }
1179 }
1180 /* Multiply and subtract
1181 (u2u1u0)" = (u2u1u0)' - qhat(v1v0) */
1182 uu[1] = HIHALF(uu[0]); /* (0u2) */
1183 uu[0] = TOHIGH(LOHALF(uu[0])) | u0; /* (u1u0) */
1184 spMultSub(uu, qhat, v1, v0);
1185 if (HIHALF(uu[1]) != 0)
1186 { /* Add back */
1187 qhat--;
1188 uu[0] += v;
1189 uu[1] = 0;
1190 }
1191 /* q0 = qhat */
1192 *q |= LOHALF(qhat);
1193 /* Remainder is in (u1u0) i.e. uu[0] */
1194 *r = uu[0];
1195 return q2;
1196 }
1197
1198 /*****************************************************************************/
1199 static int APP_CC
1200 QhatTooBig(DIGIT_T qhat, DIGIT_T rhat, DIGIT_T vn2, DIGIT_T ujn2)
1201 { /* Returns true if Qhat is too big
1202 i.e. if (Qhat * Vn-2) > (b.Rhat + Uj+n-2) */
1203 DIGIT_T t[2];
1204
1205 spMultiply(t, qhat, vn2);
1206 if (t[1] < rhat)
1207 {
1208 return 0;
1209 }
1210 else if (t[1] > rhat)
1211 {
1212 return 1;
1213 }
1214 else if (t[0] > ujn2)
1215 {
1216 return 1;
1217 }
1218 return 0;
1219 }
1220
1221 /*****************************************************************************/
1222 static DIGIT_T APP_CC
1223 mpShortDiv(DIGIT_T* q, DIGIT_T* u, DIGIT_T v, unsigned int ndigits)
1224 {
1225 /* Calculates quotient q = u div v
1226 Returns remainder r = u mod v
1227 where q, u are multiprecision integers of ndigits each
1228 and d, v are single precision digits.
1229
1230 Makes no assumptions about normalisation.
1231
1232 Ref: Knuth Vol 2 Ch 4.3.1 Exercise 16 p625 */
1233 unsigned int j;
1234 unsigned int shift;
1235 DIGIT_T t[2];
1236 DIGIT_T r;
1237 DIGIT_T bitmask;
1238 DIGIT_T overflow;
1239 DIGIT_T* uu;
1240
1241 if (ndigits == 0)
1242 {
1243 return 0;
1244 }
1245 if (v == 0)
1246 {
1247 return 0; /* Divide by zero error */
1248 }
1249 /* Normalise first */
1250 /* Requires high bit of V
1251 to be set, so find most signif. bit then shift left,
1252 i.e. d = 2^shift, u' = u * d, v' = v * d. */
1253 bitmask = HIBITMASK;
1254 for (shift = 0; shift < BITS_PER_DIGIT; shift++)
1255 {
1256 if (v & bitmask)
1257 {
1258 break;
1259 }
1260 bitmask >>= 1;
1261 }
1262 v <<= shift;
1263 overflow = mpShiftLeft(q, u, shift, ndigits);
1264 uu = q;
1265 /* Step S1 - modified for extra digit. */
1266 r = overflow; /* New digit Un */
1267 j = ndigits;
1268 while (j--)
1269 {
1270 /* Step S2. */
1271 t[1] = r;
1272 t[0] = uu[j];
1273 overflow = spDivide(&q[j], &r, t, v);
1274 }
1275 /* Unnormalise */
1276 r >>= shift;
1277 return r;
1278 }
1279
1280 /*****************************************************************************/
1281 static DIGIT_T APP_CC
1282 mpMultSub(DIGIT_T wn, DIGIT_T* w, DIGIT_T* v, DIGIT_T q, unsigned int n)
1283 { /* Compute w = w - qv
1284 where w = (WnW[n-1]...W[0])
1285 return modified Wn. */
1286 DIGIT_T k;
1287 DIGIT_T t[2];
1288 unsigned int i;
1289
1290 if (q == 0) /* No change */
1291 {
1292 return wn;
1293 }
1294 k = 0;
1295 for (i = 0; i < n; i++)
1296 {
1297 spMultiply(t, q, v[i]);
1298 w[i] -= k;
1299 if (w[i] > MAX_DIGIT - k)
1300 {
1301 k = 1;
1302 }
1303 else
1304 {
1305 k = 0;
1306 }
1307 w[i] -= t[0];
1308 if (w[i] > MAX_DIGIT - t[0])
1309 {
1310 k++;
1311 }
1312 k += t[1];
1313 }
1314 /* Cope with Wn not stored in array w[0..n-1] */
1315 wn -= k;
1316 return wn;
1317 }
1318
1319 /*****************************************************************************/
1320 static int APP_CC
1321 mpDivide(DIGIT_T* q, DIGIT_T* r, DIGIT_T* u, unsigned int udigits,
1322 DIGIT_T* v, unsigned int vdigits)
1323 { /* Computes quotient q = u / v and remainder r = u mod v
1324 where q, r, u are multiple precision digits
1325 all of udigits and the divisor v is vdigits.
1326
1327 Ref: Knuth Vol 2 Ch 4.3.1 p 272 Algorithm D.
1328
1329 Do without extra storage space, i.e. use r[] for
1330 normalised u[], unnormalise v[] at end, and cope with
1331 extra digit Uj+n added to u after normalisation.
1332
1333 WARNING: this trashes q and r first, so cannot do
1334 u = u / v or v = u mod v. */
1335 unsigned int shift;
1336 int n;
1337 int m;
1338 int j;
1339 int qhatOK;
1340 int cmp;
1341 DIGIT_T bitmask;
1342 DIGIT_T overflow;
1343 DIGIT_T qhat;
1344 DIGIT_T rhat;
1345 DIGIT_T t[2];
1346 DIGIT_T* uu;
1347 DIGIT_T* ww;
1348
1349 /* Clear q and r */
1350 mpSetZero(q, udigits);
1351 mpSetZero(r, udigits);
1352 /* Work out exact sizes of u and v */
1353 n = (int)mpSizeof(v, vdigits);
1354 m = (int)mpSizeof(u, udigits);
1355 m -= n;
1356 /* Catch special cases */
1357 if (n == 0)
1358 {
1359 return -1; /* Error: divide by zero */
1360 }
1361 if (n == 1)
1362 { /* Use short division instead */
1363 r[0] = mpShortDiv(q, u, v[0], udigits);
1364 return 0;
1365 }
1366 if (m < 0)
1367 { /* v > u, so just set q = 0 and r = u */
1368 mpSetEqual(r, u, udigits);
1369 return 0;
1370 }
1371 if (m == 0)
1372 { /* u and v are the same length */
1373 cmp = mpCompare(u, v, (unsigned int)n);
1374 if (cmp < 0)
1375 { /* v > u, as above */
1376 mpSetEqual(r, u, udigits);
1377 return 0;
1378 }
1379 else if (cmp == 0)
1380 { /* v == u, so set q = 1 and r = 0 */
1381 mpSetDigit(q, 1, udigits);
1382 return 0;
1383 }
1384 }
1385 /* In Knuth notation, we have:
1386 Given
1387 u = (Um+n-1 ... U1U0)
1388 v = (Vn-1 ... V1V0)
1389 Compute
1390 q = u/v = (QmQm-1 ... Q0)
1391 r = u mod v = (Rn-1 ... R1R0) */
1392 /* Step D1. Normalise */
1393 /* Requires high bit of Vn-1
1394 to be set, so find most signif. bit then shift left,
1395 i.e. d = 2^shift, u' = u * d, v' = v * d. */
1396 bitmask = HIBITMASK;
1397 for (shift = 0; shift < BITS_PER_DIGIT; shift++)
1398 {
1399 if (v[n - 1] & bitmask)
1400 {
1401 break;
1402 }
1403 bitmask >>= 1;
1404 }
1405 /* Normalise v in situ - NB only shift non-zero digits */
1406 overflow = mpShiftLeft(v, v, shift, n);
1407 /* Copy normalised dividend u*d into r */
1408 overflow = mpShiftLeft(r, u, shift, n + m);
1409 uu = r; /* Use ptr to keep notation constant */
1410 t[0] = overflow; /* New digit Um+n */
1411 /* Step D2. Initialise j. Set j = m */
1412 for (j = m; j >= 0; j--)
1413 {
1414 /* Step D3. Calculate Qhat = (b.Uj+n + Uj+n-1)/Vn-1 */
1415 qhatOK = 0;
1416 t[1] = t[0]; /* This is Uj+n */
1417 t[0] = uu[j+n-1];
1418 overflow = spDivide(&qhat, &rhat, t, v[n - 1]);
1419 /* Test Qhat */
1420 if (overflow)
1421 { /* Qhat = b */
1422 qhat = MAX_DIGIT;
1423 rhat = uu[j + n - 1];
1424 rhat += v[n - 1];
1425 if (rhat < v[n - 1]) /* Overflow */
1426 {
1427 qhatOK = 1;
1428 }
1429 }
1430 if (!qhatOK && QhatTooBig(qhat, rhat, v[n - 2], uu[j + n - 2]))
1431 { /* Qhat.Vn-2 > b.Rhat + Uj+n-2 */
1432 qhat--;
1433 rhat += v[n - 1];
1434 if (!(rhat < v[n - 1]))
1435 {
1436 if (QhatTooBig(qhat, rhat, v[n - 2], uu[j + n - 2]))
1437 {
1438 qhat--;
1439 }
1440 }
1441 }
1442 /* Step D4. Multiply and subtract */
1443 ww = &uu[j];
1444 overflow = mpMultSub(t[1], ww, v, qhat, (unsigned int)n);
1445 /* Step D5. Test remainder. Set Qj = Qhat */
1446 q[j] = qhat;
1447 if (overflow)
1448 { /* Step D6. Add back if D4 was negative */
1449 q[j]--;
1450 overflow = mpAdd(ww, ww, v, (unsigned int)n);
1451 }
1452 t[0] = uu[j + n - 1]; /* Uj+n on next round */
1453 } /* Step D7. Loop on j */
1454 /* Clear high digits in uu */
1455 for (j = n; j < m+n; j++)
1456 {
1457 uu[j] = 0;
1458 }
1459 /* Step D8. Unnormalise. */
1460 mpShiftRight(r, r, shift, n);
1461 mpShiftRight(v, v, shift, n);
1462 return 0;
1463 }
1464
1465 /*****************************************************************************/
1466 static int APP_CC
1467 mpModulo(DIGIT_T* r, DIGIT_T* u, unsigned int udigits,
1468 DIGIT_T* v, unsigned int vdigits)
1469 {
1470 /* Calculates r = u mod v
1471 where r, v are multiprecision integers of length vdigits
1472 and u is a multiprecision integer of length udigits.
1473 r may overlap v.
1474
1475 Note that r here is only vdigits long,
1476 whereas in mpDivide it is udigits long.
1477
1478 Use remainder from mpDivide function. */
1479 /* Double-length temp variable for divide fn */
1480 DIGIT_T qq[MAX_DIG_LEN * 2];
1481 /* Use a double-length temp for r to allow overlap of r and v */
1482 DIGIT_T rr[MAX_DIG_LEN * 2];
1483
1484 /* rr[2n] = u[2n] mod v[n] */
1485 mpDivide(qq, rr, u, udigits, v, vdigits);
1486 mpSetEqual(r, rr, vdigits);
1487 mpSetZero(rr, udigits);
1488 mpSetZero(qq, udigits);
1489 return 0;
1490 }
1491
1492 /*****************************************************************************/
1493 static int APP_CC
1494 mpMultiply(DIGIT_T* w, DIGIT_T* u, DIGIT_T* v, unsigned int ndigits)
1495 {
1496 /* Computes product w = u * v
1497 where u, v are multiprecision integers of ndigits each
1498 and w is a multiprecision integer of 2*ndigits
1499 Ref: Knuth Vol 2 Ch 4.3.1 p 268 Algorithm M. */
1500 DIGIT_T k;
1501 DIGIT_T t[2];
1502 unsigned int i;
1503 unsigned int j;
1504 unsigned int m;
1505 unsigned int n;
1506
1507 n = ndigits;
1508 m = n;
1509 /* Step M1. Initialise */
1510 for (i = 0; i < 2 * m; i++)
1511 {
1512 w[i] = 0;
1513 }
1514 for (j = 0; j < n; j++)
1515 {
1516 /* Step M2. Zero multiplier? */
1517 if (v[j] == 0)
1518 {
1519 w[j + m] = 0;
1520 }
1521 else
1522 {
1523 /* Step M3. Initialise i */
1524 k = 0;
1525 for (i = 0; i < m; i++)
1526 {
1527 /* Step M4. Multiply and add */
1528 /* t = u_i * v_j + w_(i+j) + k */
1529 spMultiply(t, u[i], v[j]);
1530 t[0] += k;
1531 if (t[0] < k)
1532 {
1533 t[1]++;
1534 }
1535 t[0] += w[i + j];
1536 if (t[0] < w[i+j])
1537 {
1538 t[1]++;
1539 }
1540 w[i + j] = t[0];
1541 k = t[1];
1542 }
1543 /* Step M5. Loop on i, set w_(j+m) = k */
1544 w[j + m] = k;
1545 }
1546 } /* Step M6. Loop on j */
1547 return 0;
1548 }
1549
1550 /*****************************************************************************/
1551 static int APP_CC
1552 mpModMult(DIGIT_T* a, DIGIT_T* x, DIGIT_T* y,
1553 DIGIT_T* m, unsigned int ndigits)
1554 { /* Computes a = (x * y) mod m */
1555 /* Double-length temp variable */
1556 DIGIT_T p[MAX_DIG_LEN * 2];
1557
1558 /* Calc p[2n] = x * y */
1559 mpMultiply(p, x, y, ndigits);
1560 /* Then modulo */
1561 mpModulo(a, p, ndigits * 2, m, ndigits);
1562 mpSetZero(p, ndigits * 2);
1563 return 0;
1564 }
1565
1566 /*****************************************************************************/
1567 int APP_CC
1568 ssl_mod_exp(char* out, int out_len, char* in, int in_len,
1569 char* mod, int mod_len, char* exp, int exp_len)
1570 {
1571 /* Computes y = x ^ e mod m */
1572 /* Binary left-to-right method */
1573 DIGIT_T mask;
1574 DIGIT_T* e;
1575 DIGIT_T* x;
1576 DIGIT_T* y;
1577 DIGIT_T* m;
1578 unsigned int n;
1579 int max_size;
1580 char* l_out;
1581 char* l_in;
1582 char* l_mod;
1583 char* l_exp;
1584
1585 if (in_len > out_len || in_len == 0 ||
1586 out_len == 0 || mod_len == 0 || exp_len == 0)
1587 {
1588 return 0;
1589 }
1590 max_size = out_len;
1591 if (in_len > max_size)
1592 {
1593 max_size = in_len;
1594 }
1595 if (mod_len > max_size)
1596 {
1597 max_size = mod_len;
1598 }
1599 if (exp_len > max_size)
1600 {
1601 max_size = exp_len;
1602 }
1603 l_out = (char*)g_malloc(max_size, 1);
1604 l_in = (char*)g_malloc(max_size, 1);
1605 l_mod = (char*)g_malloc(max_size, 1);
1606 l_exp = (char*)g_malloc(max_size, 1);
1607 memcpy(l_in, in, in_len);
1608 memcpy(l_mod, mod, mod_len);
1609 memcpy(l_exp, exp, exp_len);
1610 e = (DIGIT_T*)l_exp;
1611 x = (DIGIT_T*)l_in;
1612 y = (DIGIT_T*)l_out;
1613 m = (DIGIT_T*)l_mod;
1614 /* Find second-most significant bit in e */
1615 n = mpSizeof(e, max_size / 4);
1616 for (mask = HIBITMASK; mask > 0; mask >>= 1)
1617 {
1618 if (e[n - 1] & mask)
1619 {
1620 break;
1621 }
1622 }
1623 mpNEXTBITMASK(mask, n);
1624 /* Set y = x */
1625 mpSetEqual(y, x, max_size / 4);
1626 /* For bit j = k - 2 downto 0 step -1 */
1627 while (n)
1628 {
1629 mpModMult(y, y, y, m, max_size / 4); /* Square */
1630 if (e[n - 1] & mask)
1631 {
1632 mpModMult(y, y, x, m, max_size / 4); /* Multiply */
1633 }
1634 /* Move to next bit */
1635 mpNEXTBITMASK(mask, n);
1636 }
1637 memcpy(out, l_out, out_len);
1638 g_free(l_out);
1639 g_free(l_in);
1640 g_free(l_mod);
1641 g_free(l_exp);
1642 return out_len;
1643 }
1644
A free Windows-compatible Operating System