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