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.
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.
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.
16 xrdp: A Remote Desktop Protocol server.
17 Copyright (C) Jay Sorg 2004-2005
27 /*****************************************************************************/
28 static void * g_malloc(int size
, int zero
)
40 /*****************************************************************************/
41 static void g_free(void * in
)
46 /*****************************************************************************/
47 /*****************************************************************************/
49 /* An implementation of the ARC4 algorithm
51 * Copyright (C) 2001-2003 Christophe Devine
60 /*****************************************************************************/
62 ssl_rc4_info_create(void)
64 return g_malloc(sizeof(struct rc4_state
), 1);
67 /*****************************************************************************/
69 ssl_rc4_info_delete(void* rc4_info
)
74 /*****************************************************************************/
76 ssl_rc4_set_key(void* rc4_info
, char* key
, int len
)
85 s
= (struct rc4_state
*)rc4_info
;
89 for (i
= 0; i
< 256; i
++)
95 for (i
= 0; i
< 256; i
++)
98 j
= (unsigned char)(j
+ a
+ key
[k
]);
109 /*****************************************************************************/
111 ssl_rc4_crypt(void* rc4_info
, char* in_data
, char* out_data
, int len
)
121 s
= (struct rc4_state
*)rc4_info
;
125 for (i
= 0; i
< len
; i
++)
127 x
= (unsigned char)(x
+ 1);
129 y
= (unsigned char)(y
+ a
);
133 out_data
[i
] = in_data
[i
] ^ (m
[(unsigned char)(a
+ b
)]);
139 /*****************************************************************************/
140 /*****************************************************************************/
142 /* FIPS-180-1 compliant SHA-1 implementation
144 * Copyright (C) 2001-2003 Christophe Devine
153 /*****************************************************************************/
155 ssl_sha1_info_create(void)
157 return g_malloc(sizeof(struct sha1_context
), 1);
160 /*****************************************************************************/
162 ssl_sha1_info_delete(void* sha1_info
)
167 /*****************************************************************************/
169 ssl_sha1_clear(void* sha1_info
)
171 struct sha1_context
* ctx
;
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;
183 #define GET_UINT32(n, b, i) \
185 (n) = ((b)[(i) + 0] << 24) | \
186 ((b)[(i) + 1] << 16) | \
187 ((b)[(i) + 2] << 8) | \
188 ((b)[(i) + 3] << 0); \
192 #define PUT_UINT32(n, b, i) \
194 (b)[(i) + 0] = ((n) >> 24); \
195 (b)[(i) + 1] = ((n) >> 16); \
196 (b)[(i) + 2] = ((n) >> 8); \
197 (b)[(i) + 3] = ((n) >> 0); \
200 /*****************************************************************************/
202 sha1_process(struct sha1_context
* ctx
, char* in_data
)
213 data
= (unsigned char*)in_data
;
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);
232 #define S(x, n) ((x << n) | ((x & 0xFFFFFFFF) >> (32 - n)))
236 temp = W[(t - 3) & 0x0F] ^ \
237 W[(t - 8) & 0x0F] ^ \
238 W[(t - 14) & 0x0F] ^ \
240 (W[t & 0x0F] = S(temp, 1)) \
244 #define P(a, b, c, d, e, x) \
246 e += S(a, 5) + F(b, c, d) + K + x; \
256 #define F(x, y, z) (z ^ (x & (y ^ z)))
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));
283 #define F(x, y, z) (x ^ y ^ z)
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));
310 #define F(x, y, z) ((x & y) | (z & (x | y)))
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));
337 #define F(x, y, z) (x ^ y ^ z)
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));
371 /*****************************************************************************/
373 ssl_sha1_transform(void* sha1_info
, char* data
, int len
)
377 struct sha1_context
* ctx
;
379 ctx
= (struct sha1_context
*)sha1_info
;
384 left
= ctx
->total
[0] & 0x3F;
386 ctx
->total
[0] += len
;
387 ctx
->total
[0] &= 0xFFFFFFFF;
388 if (ctx
->total
[0] < len
)
392 if (left
&& (len
>= fill
))
394 memcpy(ctx
->buffer
+ left
, data
, fill
);
395 sha1_process(ctx
, ctx
->buffer
);
402 sha1_process(ctx
, data
);
408 memcpy(ctx
->buffer
+ left
, data
, len
);
412 static unsigned char sha1_padding
[64] =
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
420 /*****************************************************************************/
422 ssl_sha1_complete(void* sha1_info
, char* data
)
429 struct sha1_context
* ctx
;
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);
447 /*****************************************************************************/
448 /*****************************************************************************/
450 /* RFC 1321 compliant MD5 implementation
452 * Copyright (C) 2001-2003 Christophe Devine
462 /*****************************************************************************/
464 ssl_md5_info_create(void)
466 return g_malloc(sizeof(struct md5_context
), 1);
469 /*****************************************************************************/
471 ssl_md5_info_delete(void* md5_info
)
476 /*****************************************************************************/
478 ssl_md5_clear(void* md5_info
)
480 struct md5_context
* ctx
;
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;
491 #define GET_UINT32(n, b, i) \
493 (n) = ((b)[(i) + 0] << 0) | \
494 ((b)[(i) + 1] << 8) | \
495 ((b)[(i) + 2] << 16) | \
496 ((b)[(i) + 3] << 24); \
500 #define PUT_UINT32(n, b, i) \
502 (b)[(i) + 0] = ((n) >> 0); \
503 (b)[(i) + 1] = ((n) >> 8); \
504 (b)[(i) + 2] = ((n) >> 16); \
505 (b)[(i) + 3] = ((n) >> 24); \
508 /*****************************************************************************/
510 md5_process(struct md5_context
* ctx
, char* in_data
)
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);
537 #define S(x, n) ((x << n) | ((x & 0xFFFFFFFF) >> (32 - n)))
540 #define P(a, b, c, d, k, s, t) \
542 a += F(b, c, d) + X[k] + t; \
551 #define F(x, y, z) (z ^ (x & (y ^ z)))
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);
572 #define F(x, y, z) (y ^ (z & (x ^ y)))
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);
593 #define F(x, y, z) (x ^ y ^ z)
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);
614 #define F(x, y, z) (y ^ (x | ~z))
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);
641 /*****************************************************************************/
643 ssl_md5_transform(void* md5_info
, char* data
, int len
)
647 struct md5_context
* ctx
;
649 ctx
= (struct md5_context
*)md5_info
;
654 left
= ctx
->total
[0] & 0x3F;
656 ctx
->total
[0] += len
;
657 ctx
->total
[0] &= 0xFFFFFFFF;
658 if (ctx
->total
[0] < len
)
662 if (left
&& (len
>= fill
))
664 memcpy(ctx
->buffer
+ left
, data
, fill
);
665 md5_process(ctx
, ctx
->buffer
);
672 md5_process(ctx
, data
);
678 memcpy(ctx
->buffer
+ left
, data
, len
);
682 static unsigned char md5_padding
[64] =
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
690 /*****************************************************************************/
692 ssl_md5_complete(void* md5_info
, char* data
)
699 struct md5_context
* ctx
;
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);
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:
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."
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
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*************************/
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))
767 #define mpNEXTBITMASK(mask, n) \
780 /*****************************************************************************/
781 static DIGIT_T APP_CC
782 mpAdd(DIGIT_T
* w
, DIGIT_T
* u
, DIGIT_T
* v
, unsigned int ndigits
)
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.
788 Ref: Knuth Vol 2 Ch 4.3.1 p 266 Algorithm A. */
792 /* Step A1. Initialise */
794 for (j
= 0; j
< ndigits
; j
++)
796 /* Step A2. Add digits w_j = (u_j + v_j + k)
797 Set k = 1 if carry (overflow) occurs */
812 } /* Step A3. Loop on j */
813 return k
; /* w_n = k */
816 /*****************************************************************************/
818 mpSetDigit(DIGIT_T
* a
, DIGIT_T d
, unsigned int ndigits
)
819 { /* Sets a = d where d is a single digit */
822 for (i
= 1; i
< ndigits
; i
++)
829 /*****************************************************************************/
831 mpCompare(DIGIT_T
* a
, DIGIT_T
* b
, unsigned int ndigits
)
833 /* Returns sign of (a - b) */
840 if (a
[ndigits
] > b
[ndigits
])
844 if (a
[ndigits
] < b
[ndigits
])
852 /*****************************************************************************/
854 mpSetZero(DIGIT_T
* a
, unsigned int ndigits
)
858 for (i
= 0; i
< ndigits
; i
++)
864 /*****************************************************************************/
866 mpSetEqual(DIGIT_T
* a
, DIGIT_T
* b
, unsigned int ndigits
)
870 for (i
= 0; i
< ndigits
; i
++)
876 /*****************************************************************************/
877 static unsigned int APP_CC
878 mpSizeof(DIGIT_T
* a
, unsigned int ndigits
)
879 { /* Returns size of significant digits in a */
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 */
900 /* Check input - NB unspecified result */
901 if (x
>= BITS_PER_DIGIT
)
907 for (i
= 1; i
< x
; i
++)
909 mask
= (mask
>> 1) | mask
;
915 y
= BITS_PER_DIGIT
- x
;
917 for (i
= 0; i
< ndigits
; i
++)
919 nextcarry
= (b
[i
] & mask
) >> y
;
920 a
[i
] = b
[i
] << x
| carry
;
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 */
936 /* Check input - NB unspecified result */
937 if (x
>= BITS_PER_DIGIT
)
943 for (i
= 1; i
< x
; i
++)
945 mask
= (mask
<< 1) | mask
;
951 y
= BITS_PER_DIGIT
- x
;
956 nextcarry
= (b
[i
] & mask
) << y
;
957 a
[i
] = b
[i
] >> x
| carry
;
963 /*****************************************************************************/
965 spMultSub(DIGIT_T
* uu
, DIGIT_T qhat
, DIGIT_T v1
, DIGIT_T v0
)
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. */
977 t
= p0
+ TOHIGH(LOHALF(p1
));
979 if (uu
[0] > MAX_DIGIT
- t
)
981 uu
[1]--; /* Borrow */
986 /*****************************************************************************/
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
994 +--------+--------+--------+--------+
996 +--------+--------+--------+--------+
997 +-+--------+--------+
998 |1| (x0*y1 + x1*y1) |
999 +-+--------+--------+
1000 ^carry from adding (x0*y1+x1*y1) together
1002 |1|< carry from adding LOHALF t
1003 +-+ to high half of p0 */
1012 /* Split each x,y into two halves
1015 where B = 2^16, half the digit size
1017 xy = x0y0 + B(x0y1 + x1y0) + B^2(x1y1) */
1024 /* Calc low part - no carry */
1027 /* Calc middle part */
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
);
1043 /* Add low half of t to high half of p[0] */
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
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' */
1086 /* Check for normalisation */
1087 if (!(v
& HIBITMASK
))
1093 /* Split up into half-digits */
1101 /* Do three rounds of Knuth Algorithm D Vol 2 p272 */
1103 /* ROUND 1. Set j = 2 and calculate q2 */
1104 /* Estimate qhat = (u4u3)/v1 = 0 or 1
1105 then set (u4u3u2) -= qhat(v1v0)
1110 rhat
= u3
- qhat
* v1
;
1111 t
= TOHIGH(rhat
) | u2
;
1117 uu
[1] = 0; /* (u4) */
1118 uu
[0] = u
[1]; /* (u3u2) */
1121 /* (u4u3u2) -= qhat(v1v0) where u4 = 0 */
1122 spMultSub(uu
, qhat
, v1
, v0
);
1123 if (HIHALF(uu
[1]) != 0)
1131 /* ROUND 2. Set j = 1 and calculate q1 */
1132 /* Estimate qhat = (u3u2) / v1
1133 then set (u3u2u1) -= qhat(v1v0) */
1136 rhat
= t
- qhat
* v1
;
1138 t
= TOHIGH(rhat
) | u1
;
1139 if ((qhat
== B_J
) || (qhat
* v0
> t
))
1143 t
= TOHIGH(rhat
) | u1
;
1144 if ((rhat
< B_J
) && (qhat
* v0
> t
))
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)
1162 /* ROUND 3. Set j = 0 and calculate q0 */
1163 /* Estimate qhat = (u2u1) / v1
1164 then set (u2u1u0) -= qhat(v1v0) */
1167 rhat
= t
- qhat
* v1
;
1169 t
= TOHIGH(rhat
) | u0
;
1170 if ((qhat
== B_J
) || (qhat
* v0
> t
))
1174 t
= TOHIGH(rhat
) | u0
;
1175 if ((rhat
< B_J
) && (qhat
* v0
> t
))
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)
1193 /* Remainder is in (u1u0) i.e. uu[0] */
1198 /*****************************************************************************/
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) */
1205 spMultiply(t
, qhat
, vn2
);
1210 else if (t
[1] > rhat
)
1214 else if (t
[0] > ujn2
)
1221 /*****************************************************************************/
1222 static DIGIT_T APP_CC
1223 mpShortDiv(DIGIT_T
* q
, DIGIT_T
* u
, DIGIT_T v
, unsigned int ndigits
)
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.
1230 Makes no assumptions about normalisation.
1232 Ref: Knuth Vol 2 Ch 4.3.1 Exercise 16 p625 */
1247 return 0; /* Divide by zero error */
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
++)
1263 overflow
= mpShiftLeft(q
, u
, shift
, ndigits
);
1265 /* Step S1 - modified for extra digit. */
1266 r
= overflow
; /* New digit Un */
1273 overflow
= spDivide(&q
[j
], &r
, t
, v
);
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. */
1290 if (q
== 0) /* No change */
1295 for (i
= 0; i
< n
; i
++)
1297 spMultiply(t
, q
, v
[i
]);
1299 if (w
[i
] > MAX_DIGIT
- k
)
1308 if (w
[i
] > MAX_DIGIT
- t
[0])
1314 /* Cope with Wn not stored in array w[0..n-1] */
1319 /*****************************************************************************/
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.
1327 Ref: Knuth Vol 2 Ch 4.3.1 p 272 Algorithm D.
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.
1333 WARNING: this trashes q and r first, so cannot do
1334 u = u / v or v = u mod v. */
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
);
1356 /* Catch special cases */
1359 return -1; /* Error: divide by zero */
1362 { /* Use short division instead */
1363 r
[0] = mpShortDiv(q
, u
, v
[0], udigits
);
1367 { /* v > u, so just set q = 0 and r = u */
1368 mpSetEqual(r
, u
, udigits
);
1372 { /* u and v are the same length */
1373 cmp
= mpCompare(u
, v
, (unsigned int)n
);
1375 { /* v > u, as above */
1376 mpSetEqual(r
, u
, udigits
);
1380 { /* v == u, so set q = 1 and r = 0 */
1381 mpSetDigit(q
, 1, udigits
);
1385 /* In Knuth notation, we have:
1387 u = (Um+n-1 ... U1U0)
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
++)
1399 if (v
[n
- 1] & bitmask
)
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
--)
1414 /* Step D3. Calculate Qhat = (b.Uj+n + Uj+n-1)/Vn-1 */
1416 t
[1] = t
[0]; /* This is Uj+n */
1418 overflow
= spDivide(&qhat
, &rhat
, t
, v
[n
- 1]);
1423 rhat
= uu
[j
+ n
- 1];
1425 if (rhat
< v
[n
- 1]) /* Overflow */
1430 if (!qhatOK
&& QhatTooBig(qhat
, rhat
, v
[n
- 2], uu
[j
+ n
- 2]))
1431 { /* Qhat.Vn-2 > b.Rhat + Uj+n-2 */
1434 if (!(rhat
< v
[n
- 1]))
1436 if (QhatTooBig(qhat
, rhat
, v
[n
- 2], uu
[j
+ n
- 2]))
1442 /* Step D4. Multiply and subtract */
1444 overflow
= mpMultSub(t
[1], ww
, v
, qhat
, (unsigned int)n
);
1445 /* Step D5. Test remainder. Set Qj = Qhat */
1448 { /* Step D6. Add back if D4 was negative */
1450 overflow
= mpAdd(ww
, ww
, v
, (unsigned int)n
);
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
++)
1459 /* Step D8. Unnormalise. */
1460 mpShiftRight(r
, r
, shift
, n
);
1461 mpShiftRight(v
, v
, shift
, n
);
1465 /*****************************************************************************/
1467 mpModulo(DIGIT_T
* r
, DIGIT_T
* u
, unsigned int udigits
,
1468 DIGIT_T
* v
, unsigned int vdigits
)
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.
1475 Note that r here is only vdigits long,
1476 whereas in mpDivide it is udigits long.
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];
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
);
1492 /*****************************************************************************/
1494 mpMultiply(DIGIT_T
* w
, DIGIT_T
* u
, DIGIT_T
* v
, unsigned int ndigits
)
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. */
1509 /* Step M1. Initialise */
1510 for (i
= 0; i
< 2 * m
; i
++)
1514 for (j
= 0; j
< n
; j
++)
1516 /* Step M2. Zero multiplier? */
1523 /* Step M3. Initialise i */
1525 for (i
= 0; i
< m
; i
++)
1527 /* Step M4. Multiply and add */
1528 /* t = u_i * v_j + w_(i+j) + k */
1529 spMultiply(t
, u
[i
], v
[j
]);
1543 /* Step M5. Loop on i, set w_(j+m) = k */
1546 } /* Step M6. Loop on j */
1550 /*****************************************************************************/
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];
1558 /* Calc p[2n] = x * y */
1559 mpMultiply(p
, x
, y
, ndigits
);
1561 mpModulo(a
, p
, ndigits
* 2, m
, ndigits
);
1562 mpSetZero(p
, ndigits
* 2);
1566 /*****************************************************************************/
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
)
1571 /* Computes y = x ^ e mod m */
1572 /* Binary left-to-right method */
1585 if (in_len
> out_len
|| in_len
== 0 ||
1586 out_len
== 0 || mod_len
== 0 || exp_len
== 0)
1591 if (in_len
> max_size
)
1595 if (mod_len
> max_size
)
1599 if (exp_len
> max_size
)
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
;
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)
1618 if (e
[n
- 1] & mask
)
1623 mpNEXTBITMASK(mask
, n
);
1625 mpSetEqual(y
, x
, max_size
/ 4);
1626 /* For bit j = k - 2 downto 0 step -1 */
1629 mpModMult(y
, y
, y
, m
, max_size
/ 4); /* Square */
1630 if (e
[n
- 1] & mask
)
1632 mpModMult(y
, y
, x
, m
, max_size
/ 4); /* Multiply */
1634 /* Move to next bit */
1635 mpNEXTBITMASK(mask
, n
);
1637 memcpy(out
, l_out
, out_len
);