1 | /* integer.c
|
---|
2 | *
|
---|
3 | * Copyright (C) 2006-2020 wolfSSL Inc.
|
---|
4 | *
|
---|
5 | * This file is part of wolfSSL.
|
---|
6 | *
|
---|
7 | * wolfSSL is free software; you can redistribute it and/or modify
|
---|
8 | * it under the terms of the GNU General Public License as published by
|
---|
9 | * the Free Software Foundation; either version 2 of the License, or
|
---|
10 | * (at your option) any later version.
|
---|
11 | *
|
---|
12 | * wolfSSL is distributed in the hope that it will be useful,
|
---|
13 | * but WITHOUT ANY WARRANTY; without even the implied warranty of
|
---|
14 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
---|
15 | * GNU General Public License for more details.
|
---|
16 | *
|
---|
17 | * You should have received a copy of the GNU General Public License
|
---|
18 | * along with this program; if not, write to the Free Software
|
---|
19 | * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1335, USA
|
---|
20 | */
|
---|
21 |
|
---|
22 |
|
---|
23 |
|
---|
24 | /*
|
---|
25 | * Based on public domain LibTomMath 0.38 by Tom St Denis, tomstdenis@iahu.ca,
|
---|
26 | * http://math.libtomcrypt.com
|
---|
27 | */
|
---|
28 |
|
---|
29 |
|
---|
30 | #ifdef HAVE_CONFIG_H
|
---|
31 | #include <config.h>
|
---|
32 | #endif
|
---|
33 |
|
---|
34 | /* in case user set USE_FAST_MATH there */
|
---|
35 | #include <wolfssl/wolfcrypt/settings.h>
|
---|
36 |
|
---|
37 | #ifdef NO_INLINE
|
---|
38 | #include <wolfssl/wolfcrypt/misc.h>
|
---|
39 | #else
|
---|
40 | #define WOLFSSL_MISC_INCLUDED
|
---|
41 | #include <wolfcrypt/src/misc.c>
|
---|
42 | #endif
|
---|
43 |
|
---|
44 | #ifndef NO_BIG_INT
|
---|
45 |
|
---|
46 | #ifndef USE_FAST_MATH
|
---|
47 |
|
---|
48 | #ifndef WOLFSSL_SP_MATH
|
---|
49 |
|
---|
50 | #include <wolfssl/wolfcrypt/integer.h>
|
---|
51 |
|
---|
52 | #if defined(FREESCALE_LTC_TFM)
|
---|
53 | #include <wolfssl/wolfcrypt/port/nxp/ksdk_port.h>
|
---|
54 | #endif
|
---|
55 | #ifdef WOLFSSL_DEBUG_MATH
|
---|
56 | #include <stdio.h>
|
---|
57 | #endif
|
---|
58 |
|
---|
59 | #ifdef SHOW_GEN
|
---|
60 | #ifndef NO_STDIO_FILESYSTEM
|
---|
61 | #include <stdio.h>
|
---|
62 | #endif
|
---|
63 | #endif
|
---|
64 |
|
---|
65 | #if defined(WOLFSSL_HAVE_SP_RSA) || defined(WOLFSSL_HAVE_SP_DH)
|
---|
66 | #ifdef __cplusplus
|
---|
67 | extern "C" {
|
---|
68 | #endif
|
---|
69 | WOLFSSL_LOCAL int sp_ModExp_1024(mp_int* base, mp_int* exp, mp_int* mod,
|
---|
70 | mp_int* res);
|
---|
71 | WOLFSSL_LOCAL int sp_ModExp_1536(mp_int* base, mp_int* exp, mp_int* mod,
|
---|
72 | mp_int* res);
|
---|
73 | WOLFSSL_LOCAL int sp_ModExp_2048(mp_int* base, mp_int* exp, mp_int* mod,
|
---|
74 | mp_int* res);
|
---|
75 | WOLFSSL_LOCAL int sp_ModExp_3072(mp_int* base, mp_int* exp, mp_int* mod,
|
---|
76 | mp_int* res);
|
---|
77 | WOLFSSL_LOCAL int sp_ModExp_4096(mp_int* base, mp_int* exp, mp_int* mod,
|
---|
78 | mp_int* res);
|
---|
79 | #ifdef __cplusplus
|
---|
80 | } /* extern "C" */
|
---|
81 | #endif
|
---|
82 | #endif
|
---|
83 |
|
---|
84 | /* reverse an array, used for radix code */
|
---|
85 | static void
|
---|
86 | bn_reverse (unsigned char *s, int len)
|
---|
87 | {
|
---|
88 | int ix, iy;
|
---|
89 | unsigned char t;
|
---|
90 |
|
---|
91 | ix = 0;
|
---|
92 | iy = len - 1;
|
---|
93 | while (ix < iy) {
|
---|
94 | t = s[ix];
|
---|
95 | s[ix] = s[iy];
|
---|
96 | s[iy] = t;
|
---|
97 | ++ix;
|
---|
98 | --iy;
|
---|
99 | }
|
---|
100 | }
|
---|
101 |
|
---|
102 | /* math settings check */
|
---|
103 | word32 CheckRunTimeSettings(void)
|
---|
104 | {
|
---|
105 | return CTC_SETTINGS;
|
---|
106 | }
|
---|
107 |
|
---|
108 |
|
---|
109 | /* handle up to 6 inits */
|
---|
110 | int mp_init_multi(mp_int* a, mp_int* b, mp_int* c, mp_int* d, mp_int* e,
|
---|
111 | mp_int* f)
|
---|
112 | {
|
---|
113 | int res = MP_OKAY;
|
---|
114 |
|
---|
115 | if (a) XMEMSET(a, 0, sizeof(mp_int));
|
---|
116 | if (b) XMEMSET(b, 0, sizeof(mp_int));
|
---|
117 | if (c) XMEMSET(c, 0, sizeof(mp_int));
|
---|
118 | if (d) XMEMSET(d, 0, sizeof(mp_int));
|
---|
119 | if (e) XMEMSET(e, 0, sizeof(mp_int));
|
---|
120 | if (f) XMEMSET(f, 0, sizeof(mp_int));
|
---|
121 |
|
---|
122 | if (a && ((res = mp_init(a)) != MP_OKAY))
|
---|
123 | return res;
|
---|
124 |
|
---|
125 | if (b && ((res = mp_init(b)) != MP_OKAY)) {
|
---|
126 | mp_clear(a);
|
---|
127 | return res;
|
---|
128 | }
|
---|
129 |
|
---|
130 | if (c && ((res = mp_init(c)) != MP_OKAY)) {
|
---|
131 | mp_clear(a); mp_clear(b);
|
---|
132 | return res;
|
---|
133 | }
|
---|
134 |
|
---|
135 | if (d && ((res = mp_init(d)) != MP_OKAY)) {
|
---|
136 | mp_clear(a); mp_clear(b); mp_clear(c);
|
---|
137 | return res;
|
---|
138 | }
|
---|
139 |
|
---|
140 | if (e && ((res = mp_init(e)) != MP_OKAY)) {
|
---|
141 | mp_clear(a); mp_clear(b); mp_clear(c); mp_clear(d);
|
---|
142 | return res;
|
---|
143 | }
|
---|
144 |
|
---|
145 | if (f && ((res = mp_init(f)) != MP_OKAY)) {
|
---|
146 | mp_clear(a); mp_clear(b); mp_clear(c); mp_clear(d); mp_clear(e);
|
---|
147 | return res;
|
---|
148 | }
|
---|
149 |
|
---|
150 | return res;
|
---|
151 | }
|
---|
152 |
|
---|
153 |
|
---|
154 | /* init a new mp_int */
|
---|
155 | int mp_init (mp_int * a)
|
---|
156 | {
|
---|
157 | /* Safeguard against passing in a null pointer */
|
---|
158 | if (a == NULL)
|
---|
159 | return MP_VAL;
|
---|
160 |
|
---|
161 | /* defer allocation until mp_grow */
|
---|
162 | a->dp = NULL;
|
---|
163 |
|
---|
164 | /* set the used to zero, allocated digits to the default precision
|
---|
165 | * and sign to positive */
|
---|
166 | a->used = 0;
|
---|
167 | a->alloc = 0;
|
---|
168 | a->sign = MP_ZPOS;
|
---|
169 | #ifdef HAVE_WOLF_BIGINT
|
---|
170 | wc_bigint_init(&a->raw);
|
---|
171 | #endif
|
---|
172 |
|
---|
173 | return MP_OKAY;
|
---|
174 | }
|
---|
175 |
|
---|
176 |
|
---|
177 | /* clear one (frees) */
|
---|
178 | void mp_clear (mp_int * a)
|
---|
179 | {
|
---|
180 | int i;
|
---|
181 |
|
---|
182 | if (a == NULL)
|
---|
183 | return;
|
---|
184 |
|
---|
185 | /* only do anything if a hasn't been freed previously */
|
---|
186 | if (a->dp != NULL) {
|
---|
187 | /* first zero the digits */
|
---|
188 | for (i = 0; i < a->used; i++) {
|
---|
189 | a->dp[i] = 0;
|
---|
190 | }
|
---|
191 |
|
---|
192 | /* free ram */
|
---|
193 | mp_free(a);
|
---|
194 |
|
---|
195 | /* reset members to make debugging easier */
|
---|
196 | a->alloc = a->used = 0;
|
---|
197 | a->sign = MP_ZPOS;
|
---|
198 | }
|
---|
199 | }
|
---|
200 |
|
---|
201 | void mp_free (mp_int * a)
|
---|
202 | {
|
---|
203 | /* only do anything if a hasn't been freed previously */
|
---|
204 | if (a->dp != NULL) {
|
---|
205 | /* free ram */
|
---|
206 | XFREE(a->dp, 0, DYNAMIC_TYPE_BIGINT);
|
---|
207 | a->dp = NULL;
|
---|
208 | }
|
---|
209 |
|
---|
210 | #ifdef HAVE_WOLF_BIGINT
|
---|
211 | wc_bigint_free(&a->raw);
|
---|
212 | #endif
|
---|
213 | }
|
---|
214 |
|
---|
215 | void mp_forcezero(mp_int * a)
|
---|
216 | {
|
---|
217 | if (a == NULL)
|
---|
218 | return;
|
---|
219 |
|
---|
220 | /* only do anything if a hasn't been freed previously */
|
---|
221 | if (a->dp != NULL) {
|
---|
222 | /* force zero the used digits */
|
---|
223 | ForceZero(a->dp, a->used * sizeof(mp_digit));
|
---|
224 | #ifdef HAVE_WOLF_BIGINT
|
---|
225 | wc_bigint_zero(&a->raw);
|
---|
226 | #endif
|
---|
227 | /* free ram */
|
---|
228 | mp_free(a);
|
---|
229 |
|
---|
230 | /* reset members to make debugging easier */
|
---|
231 | a->alloc = a->used = 0;
|
---|
232 | a->sign = MP_ZPOS;
|
---|
233 | }
|
---|
234 |
|
---|
235 | a->sign = MP_ZPOS;
|
---|
236 | a->used = 0;
|
---|
237 | }
|
---|
238 |
|
---|
239 |
|
---|
240 | /* get the size for an unsigned equivalent */
|
---|
241 | int mp_unsigned_bin_size (mp_int * a)
|
---|
242 | {
|
---|
243 | int size = mp_count_bits (a);
|
---|
244 | return (size / 8 + ((size & 7) != 0 ? 1 : 0));
|
---|
245 | }
|
---|
246 |
|
---|
247 |
|
---|
248 | /* returns the number of bits in an int */
|
---|
249 | int mp_count_bits (mp_int * a)
|
---|
250 | {
|
---|
251 | int r;
|
---|
252 | mp_digit q;
|
---|
253 |
|
---|
254 | /* shortcut */
|
---|
255 | if (a->used == 0) {
|
---|
256 | return 0;
|
---|
257 | }
|
---|
258 |
|
---|
259 | /* get number of digits and add that */
|
---|
260 | r = (a->used - 1) * DIGIT_BIT;
|
---|
261 |
|
---|
262 | /* take the last digit and count the bits in it */
|
---|
263 | q = a->dp[a->used - 1];
|
---|
264 | while (q > ((mp_digit) 0)) {
|
---|
265 | ++r;
|
---|
266 | q >>= ((mp_digit) 1);
|
---|
267 | }
|
---|
268 | return r;
|
---|
269 | }
|
---|
270 |
|
---|
271 |
|
---|
272 | int mp_leading_bit (mp_int * a)
|
---|
273 | {
|
---|
274 | int bit = 0;
|
---|
275 | mp_int t;
|
---|
276 |
|
---|
277 | if (mp_init_copy(&t, a) != MP_OKAY)
|
---|
278 | return 0;
|
---|
279 |
|
---|
280 | while (mp_iszero(&t) == MP_NO) {
|
---|
281 | #ifndef MP_8BIT
|
---|
282 | bit = (t.dp[0] & 0x80) != 0;
|
---|
283 | #else
|
---|
284 | bit = ((t.dp[0] | ((t.dp[1] & 0x01) << 7)) & 0x80) != 0;
|
---|
285 | #endif
|
---|
286 | if (mp_div_2d (&t, 8, &t, NULL) != MP_OKAY)
|
---|
287 | break;
|
---|
288 | }
|
---|
289 | mp_clear(&t);
|
---|
290 | return bit;
|
---|
291 | }
|
---|
292 |
|
---|
293 | int mp_to_unsigned_bin_at_pos(int x, mp_int *t, unsigned char *b)
|
---|
294 | {
|
---|
295 | int res = 0;
|
---|
296 | while (mp_iszero(t) == MP_NO) {
|
---|
297 | #ifndef MP_8BIT
|
---|
298 | b[x++] = (unsigned char) (t->dp[0] & 255);
|
---|
299 | #else
|
---|
300 | b[x++] = (unsigned char) (t->dp[0] | ((t->dp[1] & 0x01) << 7));
|
---|
301 | #endif
|
---|
302 | if ((res = mp_div_2d (t, 8, t, NULL)) != MP_OKAY) {
|
---|
303 | return res;
|
---|
304 | }
|
---|
305 | res = x;
|
---|
306 | }
|
---|
307 | return res;
|
---|
308 | }
|
---|
309 |
|
---|
310 | /* store in unsigned [big endian] format */
|
---|
311 | int mp_to_unsigned_bin (mp_int * a, unsigned char *b)
|
---|
312 | {
|
---|
313 | int x, res;
|
---|
314 | mp_int t;
|
---|
315 |
|
---|
316 | if ((res = mp_init_copy (&t, a)) != MP_OKAY) {
|
---|
317 | return res;
|
---|
318 | }
|
---|
319 |
|
---|
320 | x = mp_to_unsigned_bin_at_pos(0, &t, b);
|
---|
321 | if (x < 0) {
|
---|
322 | mp_clear(&t);
|
---|
323 | return x;
|
---|
324 | }
|
---|
325 |
|
---|
326 | bn_reverse (b, x);
|
---|
327 | mp_clear (&t);
|
---|
328 | return res;
|
---|
329 | }
|
---|
330 |
|
---|
331 | int mp_to_unsigned_bin_len(mp_int * a, unsigned char *b, int c)
|
---|
332 | {
|
---|
333 | int i, len;
|
---|
334 |
|
---|
335 | len = mp_unsigned_bin_size(a);
|
---|
336 |
|
---|
337 | /* pad front w/ zeros to match length */
|
---|
338 | for (i = 0; i < c - len; i++)
|
---|
339 | b[i] = 0x00;
|
---|
340 | return mp_to_unsigned_bin(a, b + i);
|
---|
341 | }
|
---|
342 |
|
---|
343 | /* creates "a" then copies b into it */
|
---|
344 | int mp_init_copy (mp_int * a, mp_int * b)
|
---|
345 | {
|
---|
346 | int res;
|
---|
347 |
|
---|
348 | if ((res = mp_init_size (a, b->used)) != MP_OKAY) {
|
---|
349 | return res;
|
---|
350 | }
|
---|
351 |
|
---|
352 | if((res = mp_copy (b, a)) != MP_OKAY) {
|
---|
353 | mp_clear(a);
|
---|
354 | }
|
---|
355 |
|
---|
356 | return res;
|
---|
357 | }
|
---|
358 |
|
---|
359 |
|
---|
360 | /* copy, b = a */
|
---|
361 | int mp_copy (mp_int * a, mp_int * b)
|
---|
362 | {
|
---|
363 | int res, n;
|
---|
364 |
|
---|
365 | /* Safeguard against passing in a null pointer */
|
---|
366 | if (a == NULL || b == NULL)
|
---|
367 | return MP_VAL;
|
---|
368 |
|
---|
369 | /* if dst == src do nothing */
|
---|
370 | if (a == b) {
|
---|
371 | return MP_OKAY;
|
---|
372 | }
|
---|
373 |
|
---|
374 | /* grow dest */
|
---|
375 | if (b->alloc < a->used || b->alloc == 0) {
|
---|
376 | if ((res = mp_grow (b, a->used)) != MP_OKAY) {
|
---|
377 | return res;
|
---|
378 | }
|
---|
379 | }
|
---|
380 |
|
---|
381 | /* zero b and copy the parameters over */
|
---|
382 | {
|
---|
383 | mp_digit *tmpa, *tmpb;
|
---|
384 |
|
---|
385 | /* pointer aliases */
|
---|
386 |
|
---|
387 | /* source */
|
---|
388 | tmpa = a->dp;
|
---|
389 |
|
---|
390 | /* destination */
|
---|
391 | tmpb = b->dp;
|
---|
392 |
|
---|
393 | /* copy all the digits */
|
---|
394 | for (n = 0; n < a->used; n++) {
|
---|
395 | *tmpb++ = *tmpa++;
|
---|
396 | }
|
---|
397 |
|
---|
398 | /* clear high digits */
|
---|
399 | for (; n < b->used && b->dp; n++) {
|
---|
400 | *tmpb++ = 0;
|
---|
401 | }
|
---|
402 | }
|
---|
403 |
|
---|
404 | /* copy used count and sign */
|
---|
405 | b->used = a->used;
|
---|
406 | b->sign = a->sign;
|
---|
407 | return MP_OKAY;
|
---|
408 | }
|
---|
409 |
|
---|
410 |
|
---|
411 | /* grow as required */
|
---|
412 | int mp_grow (mp_int * a, int size)
|
---|
413 | {
|
---|
414 | int i;
|
---|
415 | mp_digit *tmp;
|
---|
416 |
|
---|
417 | /* if the alloc size is smaller alloc more ram */
|
---|
418 | if (a->alloc < size || size == 0) {
|
---|
419 | /* ensure there are always at least MP_PREC digits extra on top */
|
---|
420 | size += (MP_PREC * 2) - (size % MP_PREC);
|
---|
421 |
|
---|
422 | /* reallocate the array a->dp
|
---|
423 | *
|
---|
424 | * We store the return in a temporary variable
|
---|
425 | * in case the operation failed we don't want
|
---|
426 | * to overwrite the dp member of a.
|
---|
427 | */
|
---|
428 | tmp = OPT_CAST(mp_digit) XREALLOC (a->dp, sizeof (mp_digit) * size, NULL,
|
---|
429 | DYNAMIC_TYPE_BIGINT);
|
---|
430 | if (tmp == NULL) {
|
---|
431 | /* reallocation failed but "a" is still valid [can be freed] */
|
---|
432 | return MP_MEM;
|
---|
433 | }
|
---|
434 |
|
---|
435 | /* reallocation succeeded so set a->dp */
|
---|
436 | a->dp = tmp;
|
---|
437 |
|
---|
438 | /* zero excess digits */
|
---|
439 | i = a->alloc;
|
---|
440 | a->alloc = size;
|
---|
441 | for (; i < a->alloc; i++) {
|
---|
442 | a->dp[i] = 0;
|
---|
443 | }
|
---|
444 | }
|
---|
445 | return MP_OKAY;
|
---|
446 | }
|
---|
447 |
|
---|
448 |
|
---|
449 | /* shift right by a certain bit count (store quotient in c, optional
|
---|
450 | remainder in d) */
|
---|
451 | int mp_div_2d (mp_int * a, int b, mp_int * c, mp_int * d)
|
---|
452 | {
|
---|
453 | int D, res;
|
---|
454 | mp_int t;
|
---|
455 |
|
---|
456 |
|
---|
457 | /* if the shift count is <= 0 then we do no work */
|
---|
458 | if (b <= 0) {
|
---|
459 | res = mp_copy (a, c);
|
---|
460 | if (d != NULL) {
|
---|
461 | mp_zero (d);
|
---|
462 | }
|
---|
463 | return res;
|
---|
464 | }
|
---|
465 |
|
---|
466 | if ((res = mp_init (&t)) != MP_OKAY) {
|
---|
467 | return res;
|
---|
468 | }
|
---|
469 |
|
---|
470 | /* get the remainder */
|
---|
471 | if (d != NULL) {
|
---|
472 | if ((res = mp_mod_2d (a, b, &t)) != MP_OKAY) {
|
---|
473 | mp_clear (&t);
|
---|
474 | return res;
|
---|
475 | }
|
---|
476 | }
|
---|
477 |
|
---|
478 | /* copy */
|
---|
479 | if ((res = mp_copy (a, c)) != MP_OKAY) {
|
---|
480 | mp_clear (&t);
|
---|
481 | return res;
|
---|
482 | }
|
---|
483 |
|
---|
484 | /* shift by as many digits in the bit count */
|
---|
485 | if (b >= (int)DIGIT_BIT) {
|
---|
486 | mp_rshd (c, b / DIGIT_BIT);
|
---|
487 | }
|
---|
488 |
|
---|
489 | /* shift any bit count < DIGIT_BIT */
|
---|
490 | D = (b % DIGIT_BIT);
|
---|
491 | if (D != 0) {
|
---|
492 | mp_rshb(c, D);
|
---|
493 | }
|
---|
494 | mp_clamp (c);
|
---|
495 | if (d != NULL) {
|
---|
496 | mp_exch (&t, d);
|
---|
497 | }
|
---|
498 | mp_clear (&t);
|
---|
499 | return MP_OKAY;
|
---|
500 | }
|
---|
501 |
|
---|
502 |
|
---|
503 | /* set to zero */
|
---|
504 | void mp_zero (mp_int * a)
|
---|
505 | {
|
---|
506 | int n;
|
---|
507 | mp_digit *tmp;
|
---|
508 |
|
---|
509 | if (a == NULL)
|
---|
510 | return;
|
---|
511 |
|
---|
512 | a->sign = MP_ZPOS;
|
---|
513 | a->used = 0;
|
---|
514 |
|
---|
515 | tmp = a->dp;
|
---|
516 | for (n = 0; n < a->alloc; n++) {
|
---|
517 | *tmp++ = 0;
|
---|
518 | }
|
---|
519 | }
|
---|
520 |
|
---|
521 |
|
---|
522 | /* trim unused digits
|
---|
523 | *
|
---|
524 | * This is used to ensure that leading zero digits are
|
---|
525 | * trimmed and the leading "used" digit will be non-zero
|
---|
526 | * Typically very fast. Also fixes the sign if there
|
---|
527 | * are no more leading digits
|
---|
528 | */
|
---|
529 | void mp_clamp (mp_int * a)
|
---|
530 | {
|
---|
531 | /* decrease used while the most significant digit is
|
---|
532 | * zero.
|
---|
533 | */
|
---|
534 | while (a->used > 0 && a->dp[a->used - 1] == 0) {
|
---|
535 | --(a->used);
|
---|
536 | }
|
---|
537 |
|
---|
538 | /* reset the sign flag if used == 0 */
|
---|
539 | if (a->used == 0) {
|
---|
540 | a->sign = MP_ZPOS;
|
---|
541 | }
|
---|
542 | }
|
---|
543 |
|
---|
544 |
|
---|
545 | /* swap the elements of two integers, for cases where you can't simply swap the
|
---|
546 | * mp_int pointers around
|
---|
547 | */
|
---|
548 | void mp_exch (mp_int * a, mp_int * b)
|
---|
549 | {
|
---|
550 | mp_int t;
|
---|
551 |
|
---|
552 | t = *a;
|
---|
553 | *a = *b;
|
---|
554 | *b = t;
|
---|
555 | }
|
---|
556 |
|
---|
557 |
|
---|
558 | /* shift right a certain number of bits */
|
---|
559 | void mp_rshb (mp_int *c, int x)
|
---|
560 | {
|
---|
561 | mp_digit *tmpc, mask, shift;
|
---|
562 | mp_digit r, rr;
|
---|
563 | mp_digit D = x;
|
---|
564 |
|
---|
565 | if (mp_iszero(c)) return;
|
---|
566 |
|
---|
567 | /* mask */
|
---|
568 | mask = (((mp_digit)1) << D) - 1;
|
---|
569 |
|
---|
570 | /* shift for lsb */
|
---|
571 | shift = DIGIT_BIT - D;
|
---|
572 |
|
---|
573 | /* alias */
|
---|
574 | tmpc = c->dp + (c->used - 1);
|
---|
575 |
|
---|
576 | /* carry */
|
---|
577 | r = 0;
|
---|
578 | for (x = c->used - 1; x >= 0; x--) {
|
---|
579 | /* get the lower bits of this word in a temp */
|
---|
580 | rr = *tmpc & mask;
|
---|
581 |
|
---|
582 | /* shift the current word and mix in the carry bits from previous word */
|
---|
583 | *tmpc = (*tmpc >> D) | (r << shift);
|
---|
584 | --tmpc;
|
---|
585 |
|
---|
586 | /* set the carry to the carry bits of the current word found above */
|
---|
587 | r = rr;
|
---|
588 | }
|
---|
589 | mp_clamp(c);
|
---|
590 | }
|
---|
591 |
|
---|
592 |
|
---|
593 | /* shift right a certain amount of digits */
|
---|
594 | void mp_rshd (mp_int * a, int b)
|
---|
595 | {
|
---|
596 | int x;
|
---|
597 |
|
---|
598 | /* if b <= 0 then ignore it */
|
---|
599 | if (b <= 0) {
|
---|
600 | return;
|
---|
601 | }
|
---|
602 |
|
---|
603 | /* if b > used then simply zero it and return */
|
---|
604 | if (a->used <= b) {
|
---|
605 | mp_zero (a);
|
---|
606 | return;
|
---|
607 | }
|
---|
608 |
|
---|
609 | {
|
---|
610 | mp_digit *bottom, *top;
|
---|
611 |
|
---|
612 | /* shift the digits down */
|
---|
613 |
|
---|
614 | /* bottom */
|
---|
615 | bottom = a->dp;
|
---|
616 |
|
---|
617 | /* top [offset into digits] */
|
---|
618 | top = a->dp + b;
|
---|
619 |
|
---|
620 | /* this is implemented as a sliding window where
|
---|
621 | * the window is b-digits long and digits from
|
---|
622 | * the top of the window are copied to the bottom
|
---|
623 | *
|
---|
624 | * e.g.
|
---|
625 |
|
---|
626 | b-2 | b-1 | b0 | b1 | b2 | ... | bb | ---->
|
---|
627 | /\ | ---->
|
---|
628 | \-------------------/ ---->
|
---|
629 | */
|
---|
630 | for (x = 0; x < (a->used - b); x++) {
|
---|
631 | *bottom++ = *top++;
|
---|
632 | }
|
---|
633 |
|
---|
634 | /* zero the top digits */
|
---|
635 | for (; x < a->used; x++) {
|
---|
636 | *bottom++ = 0;
|
---|
637 | }
|
---|
638 | }
|
---|
639 |
|
---|
640 | /* remove excess digits */
|
---|
641 | a->used -= b;
|
---|
642 | }
|
---|
643 |
|
---|
644 |
|
---|
645 | /* calc a value mod 2**b */
|
---|
646 | int mp_mod_2d (mp_int * a, int b, mp_int * c)
|
---|
647 | {
|
---|
648 | int x, res;
|
---|
649 |
|
---|
650 | /* if b is <= 0 then zero the int */
|
---|
651 | if (b <= 0) {
|
---|
652 | mp_zero (c);
|
---|
653 | return MP_OKAY;
|
---|
654 | }
|
---|
655 |
|
---|
656 | /* if the modulus is larger than the value than return */
|
---|
657 | if (b >= (int) (a->used * DIGIT_BIT)) {
|
---|
658 | res = mp_copy (a, c);
|
---|
659 | return res;
|
---|
660 | }
|
---|
661 |
|
---|
662 | /* copy */
|
---|
663 | if ((res = mp_copy (a, c)) != MP_OKAY) {
|
---|
664 | return res;
|
---|
665 | }
|
---|
666 |
|
---|
667 | /* zero digits above the last digit of the modulus */
|
---|
668 | for (x = (b / DIGIT_BIT) + ((b % DIGIT_BIT) == 0 ? 0 : 1); x < c->used; x++) {
|
---|
669 | c->dp[x] = 0;
|
---|
670 | }
|
---|
671 | /* clear the digit that is not completely outside/inside the modulus */
|
---|
672 | c->dp[b / DIGIT_BIT] &= (mp_digit) ((((mp_digit) 1) <<
|
---|
673 | (((mp_digit) b) % DIGIT_BIT)) - ((mp_digit) 1));
|
---|
674 | mp_clamp (c);
|
---|
675 | return MP_OKAY;
|
---|
676 | }
|
---|
677 |
|
---|
678 |
|
---|
679 | /* reads a unsigned char array, assumes the msb is stored first [big endian] */
|
---|
680 | int mp_read_unsigned_bin (mp_int * a, const unsigned char *b, int c)
|
---|
681 | {
|
---|
682 | int res;
|
---|
683 |
|
---|
684 | /* make sure there are at least two digits */
|
---|
685 | if (a->alloc < 2) {
|
---|
686 | if ((res = mp_grow(a, 2)) != MP_OKAY) {
|
---|
687 | return res;
|
---|
688 | }
|
---|
689 | }
|
---|
690 |
|
---|
691 | /* zero the int */
|
---|
692 | mp_zero (a);
|
---|
693 |
|
---|
694 | /* read the bytes in */
|
---|
695 | while (c-- > 0) {
|
---|
696 | if ((res = mp_mul_2d (a, 8, a)) != MP_OKAY) {
|
---|
697 | return res;
|
---|
698 | }
|
---|
699 |
|
---|
700 | #ifndef MP_8BIT
|
---|
701 | a->dp[0] |= *b++;
|
---|
702 | a->used += 1;
|
---|
703 | #else
|
---|
704 | a->dp[0] = (*b & MP_MASK);
|
---|
705 | a->dp[1] |= ((*b++ >> 7U) & 1);
|
---|
706 | a->used += 2;
|
---|
707 | #endif
|
---|
708 | }
|
---|
709 | mp_clamp (a);
|
---|
710 | return MP_OKAY;
|
---|
711 | }
|
---|
712 |
|
---|
713 |
|
---|
714 | /* shift left by a certain bit count */
|
---|
715 | int mp_mul_2d (mp_int * a, int b, mp_int * c)
|
---|
716 | {
|
---|
717 | mp_digit d;
|
---|
718 | int res;
|
---|
719 |
|
---|
720 | /* copy */
|
---|
721 | if (a != c) {
|
---|
722 | if ((res = mp_copy (a, c)) != MP_OKAY) {
|
---|
723 | return res;
|
---|
724 | }
|
---|
725 | }
|
---|
726 |
|
---|
727 | if (c->alloc < (int)(c->used + b/DIGIT_BIT + 1)) {
|
---|
728 | if ((res = mp_grow (c, c->used + b / DIGIT_BIT + 1)) != MP_OKAY) {
|
---|
729 | return res;
|
---|
730 | }
|
---|
731 | }
|
---|
732 |
|
---|
733 | /* shift by as many digits in the bit count */
|
---|
734 | if (b >= (int)DIGIT_BIT) {
|
---|
735 | if ((res = mp_lshd (c, b / DIGIT_BIT)) != MP_OKAY) {
|
---|
736 | return res;
|
---|
737 | }
|
---|
738 | }
|
---|
739 |
|
---|
740 | /* shift any bit count < DIGIT_BIT */
|
---|
741 | d = (mp_digit) (b % DIGIT_BIT);
|
---|
742 | if (d != 0) {
|
---|
743 | mp_digit *tmpc, shift, mask, r, rr;
|
---|
744 | int x;
|
---|
745 |
|
---|
746 | /* bitmask for carries */
|
---|
747 | mask = (((mp_digit)1) << d) - 1;
|
---|
748 |
|
---|
749 | /* shift for msbs */
|
---|
750 | shift = DIGIT_BIT - d;
|
---|
751 |
|
---|
752 | /* alias */
|
---|
753 | tmpc = c->dp;
|
---|
754 |
|
---|
755 | /* carry */
|
---|
756 | r = 0;
|
---|
757 | for (x = 0; x < c->used; x++) {
|
---|
758 | /* get the higher bits of the current word */
|
---|
759 | rr = (*tmpc >> shift) & mask;
|
---|
760 |
|
---|
761 | /* shift the current word and OR in the carry */
|
---|
762 | *tmpc = (mp_digit)(((*tmpc << d) | r) & MP_MASK);
|
---|
763 | ++tmpc;
|
---|
764 |
|
---|
765 | /* set the carry to the carry bits of the current word */
|
---|
766 | r = rr;
|
---|
767 | }
|
---|
768 |
|
---|
769 | /* set final carry */
|
---|
770 | if (r != 0) {
|
---|
771 | c->dp[(c->used)++] = r;
|
---|
772 | }
|
---|
773 | }
|
---|
774 | mp_clamp (c);
|
---|
775 | return MP_OKAY;
|
---|
776 | }
|
---|
777 |
|
---|
778 |
|
---|
779 | /* shift left a certain amount of digits */
|
---|
780 | int mp_lshd (mp_int * a, int b)
|
---|
781 | {
|
---|
782 | int x, res;
|
---|
783 |
|
---|
784 | /* if its less than zero return */
|
---|
785 | if (b <= 0) {
|
---|
786 | return MP_OKAY;
|
---|
787 | }
|
---|
788 |
|
---|
789 | /* grow to fit the new digits */
|
---|
790 | if (a->alloc < a->used + b) {
|
---|
791 | if ((res = mp_grow (a, a->used + b)) != MP_OKAY) {
|
---|
792 | return res;
|
---|
793 | }
|
---|
794 | }
|
---|
795 |
|
---|
796 | {
|
---|
797 | mp_digit *top, *bottom;
|
---|
798 |
|
---|
799 | /* increment the used by the shift amount then copy upwards */
|
---|
800 | a->used += b;
|
---|
801 |
|
---|
802 | /* top */
|
---|
803 | top = a->dp + a->used - 1;
|
---|
804 |
|
---|
805 | /* base */
|
---|
806 | bottom = a->dp + a->used - 1 - b;
|
---|
807 |
|
---|
808 | /* much like mp_rshd this is implemented using a sliding window
|
---|
809 | * except the window goes the other way around. Copying from
|
---|
810 | * the bottom to the top. see bn_mp_rshd.c for more info.
|
---|
811 | */
|
---|
812 | for (x = a->used - 1; x >= b; x--) {
|
---|
813 | *top-- = *bottom--;
|
---|
814 | }
|
---|
815 |
|
---|
816 | /* zero the lower digits */
|
---|
817 | top = a->dp;
|
---|
818 | for (x = 0; x < b; x++) {
|
---|
819 | *top++ = 0;
|
---|
820 | }
|
---|
821 | }
|
---|
822 | return MP_OKAY;
|
---|
823 | }
|
---|
824 |
|
---|
825 |
|
---|
826 | /* this is a shell function that calls either the normal or Montgomery
|
---|
827 | * exptmod functions. Originally the call to the montgomery code was
|
---|
828 | * embedded in the normal function but that wasted a lot of stack space
|
---|
829 | * for nothing (since 99% of the time the Montgomery code would be called)
|
---|
830 | */
|
---|
831 | #if defined(FREESCALE_LTC_TFM)
|
---|
832 | int wolfcrypt_mp_exptmod (mp_int * G, mp_int * X, mp_int * P, mp_int * Y)
|
---|
833 | #else
|
---|
834 | int mp_exptmod (mp_int * G, mp_int * X, mp_int * P, mp_int * Y)
|
---|
835 | #endif
|
---|
836 | {
|
---|
837 | int dr;
|
---|
838 |
|
---|
839 | /* modulus P must be positive */
|
---|
840 | if (mp_iszero(P) || P->sign == MP_NEG) {
|
---|
841 | return MP_VAL;
|
---|
842 | }
|
---|
843 | if (mp_isone(P)) {
|
---|
844 | mp_set(Y, 0);
|
---|
845 | return MP_OKAY;
|
---|
846 | }
|
---|
847 | if (mp_iszero(X)) {
|
---|
848 | mp_set(Y, 1);
|
---|
849 | return MP_OKAY;
|
---|
850 | }
|
---|
851 | if (mp_iszero(G)) {
|
---|
852 | mp_set(Y, 0);
|
---|
853 | return MP_OKAY;
|
---|
854 | }
|
---|
855 |
|
---|
856 | /* if exponent X is negative we have to recurse */
|
---|
857 | if (X->sign == MP_NEG) {
|
---|
858 | #ifdef BN_MP_INVMOD_C
|
---|
859 | mp_int tmpG, tmpX;
|
---|
860 | int err;
|
---|
861 |
|
---|
862 | /* first compute 1/G mod P */
|
---|
863 | if ((err = mp_init(&tmpG)) != MP_OKAY) {
|
---|
864 | return err;
|
---|
865 | }
|
---|
866 | if ((err = mp_invmod(G, P, &tmpG)) != MP_OKAY) {
|
---|
867 | mp_clear(&tmpG);
|
---|
868 | return err;
|
---|
869 | }
|
---|
870 |
|
---|
871 | /* now get |X| */
|
---|
872 | if ((err = mp_init(&tmpX)) != MP_OKAY) {
|
---|
873 | mp_clear(&tmpG);
|
---|
874 | return err;
|
---|
875 | }
|
---|
876 | if ((err = mp_abs(X, &tmpX)) != MP_OKAY) {
|
---|
877 | mp_clear(&tmpG);
|
---|
878 | mp_clear(&tmpX);
|
---|
879 | return err;
|
---|
880 | }
|
---|
881 |
|
---|
882 | /* and now compute (1/G)**|X| instead of G**X [X < 0] */
|
---|
883 | err = mp_exptmod(&tmpG, &tmpX, P, Y);
|
---|
884 | mp_clear(&tmpG);
|
---|
885 | mp_clear(&tmpX);
|
---|
886 | return err;
|
---|
887 | #else
|
---|
888 | /* no invmod */
|
---|
889 | return MP_VAL;
|
---|
890 | #endif
|
---|
891 | }
|
---|
892 |
|
---|
893 | #ifdef BN_MP_EXPTMOD_BASE_2
|
---|
894 | if (G->used == 1 && G->dp[0] == 2) {
|
---|
895 | return mp_exptmod_base_2(X, P, Y);
|
---|
896 | }
|
---|
897 | #endif
|
---|
898 |
|
---|
899 | /* modified diminished radix reduction */
|
---|
900 | #if defined(BN_MP_REDUCE_IS_2K_L_C) && defined(BN_MP_REDUCE_2K_L_C) && \
|
---|
901 | defined(BN_S_MP_EXPTMOD_C)
|
---|
902 | if (mp_reduce_is_2k_l(P) == MP_YES) {
|
---|
903 | return s_mp_exptmod(G, X, P, Y, 1);
|
---|
904 | }
|
---|
905 | #endif
|
---|
906 |
|
---|
907 | #ifdef BN_MP_DR_IS_MODULUS_C
|
---|
908 | /* is it a DR modulus? */
|
---|
909 | dr = mp_dr_is_modulus(P);
|
---|
910 | #else
|
---|
911 | /* default to no */
|
---|
912 | dr = 0;
|
---|
913 | #endif
|
---|
914 |
|
---|
915 | (void)dr;
|
---|
916 |
|
---|
917 | #ifdef BN_MP_REDUCE_IS_2K_C
|
---|
918 | /* if not, is it a unrestricted DR modulus? */
|
---|
919 | if (dr == 0) {
|
---|
920 | dr = mp_reduce_is_2k(P) << 1;
|
---|
921 | }
|
---|
922 | #endif
|
---|
923 |
|
---|
924 | /* if the modulus is odd or dr != 0 use the montgomery method */
|
---|
925 | #ifdef BN_MP_EXPTMOD_FAST_C
|
---|
926 | if (mp_isodd (P) == MP_YES || dr != 0) {
|
---|
927 | return mp_exptmod_fast (G, X, P, Y, dr);
|
---|
928 | } else {
|
---|
929 | #endif
|
---|
930 | #ifdef BN_S_MP_EXPTMOD_C
|
---|
931 | /* otherwise use the generic Barrett reduction technique */
|
---|
932 | return s_mp_exptmod (G, X, P, Y, 0);
|
---|
933 | #else
|
---|
934 | /* no exptmod for evens */
|
---|
935 | return MP_VAL;
|
---|
936 | #endif
|
---|
937 | #ifdef BN_MP_EXPTMOD_FAST_C
|
---|
938 | }
|
---|
939 | #endif
|
---|
940 | }
|
---|
941 |
|
---|
942 | int mp_exptmod_ex (mp_int * G, mp_int * X, int digits, mp_int * P, mp_int * Y)
|
---|
943 | {
|
---|
944 | (void)digits;
|
---|
945 | return mp_exptmod(G, X, P, Y);
|
---|
946 | }
|
---|
947 |
|
---|
948 | /* b = |a|
|
---|
949 | *
|
---|
950 | * Simple function copies the input and fixes the sign to positive
|
---|
951 | */
|
---|
952 | int mp_abs (mp_int * a, mp_int * b)
|
---|
953 | {
|
---|
954 | int res;
|
---|
955 |
|
---|
956 | /* copy a to b */
|
---|
957 | if (a != b) {
|
---|
958 | if ((res = mp_copy (a, b)) != MP_OKAY) {
|
---|
959 | return res;
|
---|
960 | }
|
---|
961 | }
|
---|
962 |
|
---|
963 | /* force the sign of b to positive */
|
---|
964 | b->sign = MP_ZPOS;
|
---|
965 |
|
---|
966 | return MP_OKAY;
|
---|
967 | }
|
---|
968 |
|
---|
969 |
|
---|
970 | /* hac 14.61, pp608 */
|
---|
971 | #if defined(FREESCALE_LTC_TFM)
|
---|
972 | int wolfcrypt_mp_invmod(mp_int * a, mp_int * b, mp_int * c)
|
---|
973 | #else
|
---|
974 | int mp_invmod (mp_int * a, mp_int * b, mp_int * c)
|
---|
975 | #endif
|
---|
976 | {
|
---|
977 | /* b cannot be negative or zero, and can not divide by 0 (1/a mod b) */
|
---|
978 | if (b->sign == MP_NEG || mp_iszero(b) == MP_YES || mp_iszero(a) == MP_YES) {
|
---|
979 | return MP_VAL;
|
---|
980 | }
|
---|
981 |
|
---|
982 | #ifdef BN_FAST_MP_INVMOD_C
|
---|
983 | /* if the modulus is odd we can use a faster routine instead */
|
---|
984 | if ((mp_isodd(b) == MP_YES) && (mp_cmp_d(b, 1) != MP_EQ)) {
|
---|
985 | return fast_mp_invmod (a, b, c);
|
---|
986 | }
|
---|
987 | #endif
|
---|
988 |
|
---|
989 | #ifdef BN_MP_INVMOD_SLOW_C
|
---|
990 | return mp_invmod_slow(a, b, c);
|
---|
991 | #else
|
---|
992 | return MP_VAL;
|
---|
993 | #endif
|
---|
994 | }
|
---|
995 |
|
---|
996 |
|
---|
997 | /* computes the modular inverse via binary extended euclidean algorithm,
|
---|
998 | * that is c = 1/a mod b
|
---|
999 | *
|
---|
1000 | * Based on slow invmod except this is optimized for the case where b is
|
---|
1001 | * odd as per HAC Note 14.64 on pp. 610
|
---|
1002 | */
|
---|
1003 | int fast_mp_invmod (mp_int * a, mp_int * b, mp_int * c)
|
---|
1004 | {
|
---|
1005 | mp_int x, y, u, v, B, D;
|
---|
1006 | int res, neg, loop_check = 0;
|
---|
1007 |
|
---|
1008 | /* 2. [modified] b must be odd */
|
---|
1009 | if (mp_iseven (b) == MP_YES) {
|
---|
1010 | return MP_VAL;
|
---|
1011 | }
|
---|
1012 |
|
---|
1013 | /* init all our temps */
|
---|
1014 | if ((res = mp_init_multi(&x, &y, &u, &v, &B, &D)) != MP_OKAY) {
|
---|
1015 | return res;
|
---|
1016 | }
|
---|
1017 |
|
---|
1018 | /* x == modulus, y == value to invert */
|
---|
1019 | if ((res = mp_copy (b, &x)) != MP_OKAY) {
|
---|
1020 | goto LBL_ERR;
|
---|
1021 | }
|
---|
1022 |
|
---|
1023 | /* we need y = |a| */
|
---|
1024 | if ((res = mp_mod (a, b, &y)) != MP_OKAY) {
|
---|
1025 | goto LBL_ERR;
|
---|
1026 | }
|
---|
1027 |
|
---|
1028 | /* 3. u=x, v=y, A=1, B=0, C=0,D=1 */
|
---|
1029 | if ((res = mp_copy (&x, &u)) != MP_OKAY) {
|
---|
1030 | goto LBL_ERR;
|
---|
1031 | }
|
---|
1032 | if ((res = mp_copy (&y, &v)) != MP_OKAY) {
|
---|
1033 | goto LBL_ERR;
|
---|
1034 | }
|
---|
1035 | if ((res = mp_set (&D, 1)) != MP_OKAY) {
|
---|
1036 | goto LBL_ERR;
|
---|
1037 | }
|
---|
1038 |
|
---|
1039 | top:
|
---|
1040 | /* 4. while u is even do */
|
---|
1041 | while (mp_iseven (&u) == MP_YES) {
|
---|
1042 | /* 4.1 u = u/2 */
|
---|
1043 | if ((res = mp_div_2 (&u, &u)) != MP_OKAY) {
|
---|
1044 | goto LBL_ERR;
|
---|
1045 | }
|
---|
1046 | /* 4.2 if B is odd then */
|
---|
1047 | if (mp_isodd (&B) == MP_YES) {
|
---|
1048 | if ((res = mp_sub (&B, &x, &B)) != MP_OKAY) {
|
---|
1049 | goto LBL_ERR;
|
---|
1050 | }
|
---|
1051 | }
|
---|
1052 | /* B = B/2 */
|
---|
1053 | if ((res = mp_div_2 (&B, &B)) != MP_OKAY) {
|
---|
1054 | goto LBL_ERR;
|
---|
1055 | }
|
---|
1056 | }
|
---|
1057 |
|
---|
1058 | /* 5. while v is even do */
|
---|
1059 | while (mp_iseven (&v) == MP_YES) {
|
---|
1060 | /* 5.1 v = v/2 */
|
---|
1061 | if ((res = mp_div_2 (&v, &v)) != MP_OKAY) {
|
---|
1062 | goto LBL_ERR;
|
---|
1063 | }
|
---|
1064 | /* 5.2 if D is odd then */
|
---|
1065 | if (mp_isodd (&D) == MP_YES) {
|
---|
1066 | /* D = (D-x)/2 */
|
---|
1067 | if ((res = mp_sub (&D, &x, &D)) != MP_OKAY) {
|
---|
1068 | goto LBL_ERR;
|
---|
1069 | }
|
---|
1070 | }
|
---|
1071 | /* D = D/2 */
|
---|
1072 | if ((res = mp_div_2 (&D, &D)) != MP_OKAY) {
|
---|
1073 | goto LBL_ERR;
|
---|
1074 | }
|
---|
1075 | }
|
---|
1076 |
|
---|
1077 | /* 6. if u >= v then */
|
---|
1078 | if (mp_cmp (&u, &v) != MP_LT) {
|
---|
1079 | /* u = u - v, B = B - D */
|
---|
1080 | if ((res = mp_sub (&u, &v, &u)) != MP_OKAY) {
|
---|
1081 | goto LBL_ERR;
|
---|
1082 | }
|
---|
1083 |
|
---|
1084 | if ((res = mp_sub (&B, &D, &B)) != MP_OKAY) {
|
---|
1085 | goto LBL_ERR;
|
---|
1086 | }
|
---|
1087 | } else {
|
---|
1088 | /* v - v - u, D = D - B */
|
---|
1089 | if ((res = mp_sub (&v, &u, &v)) != MP_OKAY) {
|
---|
1090 | goto LBL_ERR;
|
---|
1091 | }
|
---|
1092 |
|
---|
1093 | if ((res = mp_sub (&D, &B, &D)) != MP_OKAY) {
|
---|
1094 | goto LBL_ERR;
|
---|
1095 | }
|
---|
1096 | }
|
---|
1097 |
|
---|
1098 | /* if not zero goto step 4 */
|
---|
1099 | if (mp_iszero (&u) == MP_NO) {
|
---|
1100 | if (++loop_check > MAX_INVMOD_SZ) {
|
---|
1101 | res = MP_VAL;
|
---|
1102 | goto LBL_ERR;
|
---|
1103 | }
|
---|
1104 | goto top;
|
---|
1105 | }
|
---|
1106 |
|
---|
1107 | /* now a = C, b = D, gcd == g*v */
|
---|
1108 |
|
---|
1109 | /* if v != 1 then there is no inverse */
|
---|
1110 | if (mp_cmp_d (&v, 1) != MP_EQ) {
|
---|
1111 | res = MP_VAL;
|
---|
1112 | goto LBL_ERR;
|
---|
1113 | }
|
---|
1114 |
|
---|
1115 | /* b is now the inverse */
|
---|
1116 | neg = a->sign;
|
---|
1117 | while (D.sign == MP_NEG) {
|
---|
1118 | if ((res = mp_add (&D, b, &D)) != MP_OKAY) {
|
---|
1119 | goto LBL_ERR;
|
---|
1120 | }
|
---|
1121 | }
|
---|
1122 | /* too big */
|
---|
1123 | while (mp_cmp_mag(&D, b) != MP_LT) {
|
---|
1124 | if ((res = mp_sub(&D, b, &D)) != MP_OKAY) {
|
---|
1125 | goto LBL_ERR;
|
---|
1126 | }
|
---|
1127 | }
|
---|
1128 | mp_exch (&D, c);
|
---|
1129 | c->sign = neg;
|
---|
1130 | res = MP_OKAY;
|
---|
1131 |
|
---|
1132 | LBL_ERR:mp_clear(&x);
|
---|
1133 | mp_clear(&y);
|
---|
1134 | mp_clear(&u);
|
---|
1135 | mp_clear(&v);
|
---|
1136 | mp_clear(&B);
|
---|
1137 | mp_clear(&D);
|
---|
1138 | return res;
|
---|
1139 | }
|
---|
1140 |
|
---|
1141 |
|
---|
1142 | /* hac 14.61, pp608 */
|
---|
1143 | int mp_invmod_slow (mp_int * a, mp_int * b, mp_int * c)
|
---|
1144 | {
|
---|
1145 | mp_int x, y, u, v, A, B, C, D;
|
---|
1146 | int res;
|
---|
1147 |
|
---|
1148 | /* b cannot be negative */
|
---|
1149 | if (b->sign == MP_NEG || mp_iszero(b) == MP_YES) {
|
---|
1150 | return MP_VAL;
|
---|
1151 | }
|
---|
1152 |
|
---|
1153 | /* init temps */
|
---|
1154 | if ((res = mp_init_multi(&x, &y, &u, &v,
|
---|
1155 | &A, &B)) != MP_OKAY) {
|
---|
1156 | return res;
|
---|
1157 | }
|
---|
1158 |
|
---|
1159 | /* init rest of tmps temps */
|
---|
1160 | if ((res = mp_init_multi(&C, &D, 0, 0, 0, 0)) != MP_OKAY) {
|
---|
1161 | mp_clear(&x);
|
---|
1162 | mp_clear(&y);
|
---|
1163 | mp_clear(&u);
|
---|
1164 | mp_clear(&v);
|
---|
1165 | mp_clear(&A);
|
---|
1166 | mp_clear(&B);
|
---|
1167 | return res;
|
---|
1168 | }
|
---|
1169 |
|
---|
1170 | /* x = a, y = b */
|
---|
1171 | if ((res = mp_mod(a, b, &x)) != MP_OKAY) {
|
---|
1172 | goto LBL_ERR;
|
---|
1173 | }
|
---|
1174 | if (mp_isone(&x)) {
|
---|
1175 | mp_set(c, 1);
|
---|
1176 | res = MP_OKAY;
|
---|
1177 | goto LBL_ERR;
|
---|
1178 | }
|
---|
1179 | if ((res = mp_copy (b, &y)) != MP_OKAY) {
|
---|
1180 | goto LBL_ERR;
|
---|
1181 | }
|
---|
1182 |
|
---|
1183 | /* 2. [modified] if x,y are both even then return an error! */
|
---|
1184 | if (mp_iseven (&x) == MP_YES && mp_iseven (&y) == MP_YES) {
|
---|
1185 | res = MP_VAL;
|
---|
1186 | goto LBL_ERR;
|
---|
1187 | }
|
---|
1188 |
|
---|
1189 | /* 3. u=x, v=y, A=1, B=0, C=0,D=1 */
|
---|
1190 | if ((res = mp_copy (&x, &u)) != MP_OKAY) {
|
---|
1191 | goto LBL_ERR;
|
---|
1192 | }
|
---|
1193 | if ((res = mp_copy (&y, &v)) != MP_OKAY) {
|
---|
1194 | goto LBL_ERR;
|
---|
1195 | }
|
---|
1196 | if ((res = mp_set (&A, 1)) != MP_OKAY) {
|
---|
1197 | goto LBL_ERR;
|
---|
1198 | }
|
---|
1199 | if ((res = mp_set (&D, 1)) != MP_OKAY) {
|
---|
1200 | goto LBL_ERR;
|
---|
1201 | }
|
---|
1202 |
|
---|
1203 | top:
|
---|
1204 | /* 4. while u is even do */
|
---|
1205 | while (mp_iseven (&u) == MP_YES) {
|
---|
1206 | /* 4.1 u = u/2 */
|
---|
1207 | if ((res = mp_div_2 (&u, &u)) != MP_OKAY) {
|
---|
1208 | goto LBL_ERR;
|
---|
1209 | }
|
---|
1210 | /* 4.2 if A or B is odd then */
|
---|
1211 | if (mp_isodd (&A) == MP_YES || mp_isodd (&B) == MP_YES) {
|
---|
1212 | /* A = (A+y)/2, B = (B-x)/2 */
|
---|
1213 | if ((res = mp_add (&A, &y, &A)) != MP_OKAY) {
|
---|
1214 | goto LBL_ERR;
|
---|
1215 | }
|
---|
1216 | if ((res = mp_sub (&B, &x, &B)) != MP_OKAY) {
|
---|
1217 | goto LBL_ERR;
|
---|
1218 | }
|
---|
1219 | }
|
---|
1220 | /* A = A/2, B = B/2 */
|
---|
1221 | if ((res = mp_div_2 (&A, &A)) != MP_OKAY) {
|
---|
1222 | goto LBL_ERR;
|
---|
1223 | }
|
---|
1224 | if ((res = mp_div_2 (&B, &B)) != MP_OKAY) {
|
---|
1225 | goto LBL_ERR;
|
---|
1226 | }
|
---|
1227 | }
|
---|
1228 |
|
---|
1229 | /* 5. while v is even do */
|
---|
1230 | while (mp_iseven (&v) == MP_YES) {
|
---|
1231 | /* 5.1 v = v/2 */
|
---|
1232 | if ((res = mp_div_2 (&v, &v)) != MP_OKAY) {
|
---|
1233 | goto LBL_ERR;
|
---|
1234 | }
|
---|
1235 | /* 5.2 if C or D is odd then */
|
---|
1236 | if (mp_isodd (&C) == MP_YES || mp_isodd (&D) == MP_YES) {
|
---|
1237 | /* C = (C+y)/2, D = (D-x)/2 */
|
---|
1238 | if ((res = mp_add (&C, &y, &C)) != MP_OKAY) {
|
---|
1239 | goto LBL_ERR;
|
---|
1240 | }
|
---|
1241 | if ((res = mp_sub (&D, &x, &D)) != MP_OKAY) {
|
---|
1242 | goto LBL_ERR;
|
---|
1243 | }
|
---|
1244 | }
|
---|
1245 | /* C = C/2, D = D/2 */
|
---|
1246 | if ((res = mp_div_2 (&C, &C)) != MP_OKAY) {
|
---|
1247 | goto LBL_ERR;
|
---|
1248 | }
|
---|
1249 | if ((res = mp_div_2 (&D, &D)) != MP_OKAY) {
|
---|
1250 | goto LBL_ERR;
|
---|
1251 | }
|
---|
1252 | }
|
---|
1253 |
|
---|
1254 | /* 6. if u >= v then */
|
---|
1255 | if (mp_cmp (&u, &v) != MP_LT) {
|
---|
1256 | /* u = u - v, A = A - C, B = B - D */
|
---|
1257 | if ((res = mp_sub (&u, &v, &u)) != MP_OKAY) {
|
---|
1258 | goto LBL_ERR;
|
---|
1259 | }
|
---|
1260 |
|
---|
1261 | if ((res = mp_sub (&A, &C, &A)) != MP_OKAY) {
|
---|
1262 | goto LBL_ERR;
|
---|
1263 | }
|
---|
1264 |
|
---|
1265 | if ((res = mp_sub (&B, &D, &B)) != MP_OKAY) {
|
---|
1266 | goto LBL_ERR;
|
---|
1267 | }
|
---|
1268 | } else {
|
---|
1269 | /* v - v - u, C = C - A, D = D - B */
|
---|
1270 | if ((res = mp_sub (&v, &u, &v)) != MP_OKAY) {
|
---|
1271 | goto LBL_ERR;
|
---|
1272 | }
|
---|
1273 |
|
---|
1274 | if ((res = mp_sub (&C, &A, &C)) != MP_OKAY) {
|
---|
1275 | goto LBL_ERR;
|
---|
1276 | }
|
---|
1277 |
|
---|
1278 | if ((res = mp_sub (&D, &B, &D)) != MP_OKAY) {
|
---|
1279 | goto LBL_ERR;
|
---|
1280 | }
|
---|
1281 | }
|
---|
1282 |
|
---|
1283 | /* if not zero goto step 4 */
|
---|
1284 | if (mp_iszero (&u) == MP_NO)
|
---|
1285 | goto top;
|
---|
1286 |
|
---|
1287 | /* now a = C, b = D, gcd == g*v */
|
---|
1288 |
|
---|
1289 | /* if v != 1 then there is no inverse */
|
---|
1290 | if (mp_cmp_d (&v, 1) != MP_EQ) {
|
---|
1291 | res = MP_VAL;
|
---|
1292 | goto LBL_ERR;
|
---|
1293 | }
|
---|
1294 |
|
---|
1295 | /* if its too low */
|
---|
1296 | while (mp_cmp_d(&C, 0) == MP_LT) {
|
---|
1297 | if ((res = mp_add(&C, b, &C)) != MP_OKAY) {
|
---|
1298 | goto LBL_ERR;
|
---|
1299 | }
|
---|
1300 | }
|
---|
1301 |
|
---|
1302 | /* too big */
|
---|
1303 | while (mp_cmp_mag(&C, b) != MP_LT) {
|
---|
1304 | if ((res = mp_sub(&C, b, &C)) != MP_OKAY) {
|
---|
1305 | goto LBL_ERR;
|
---|
1306 | }
|
---|
1307 | }
|
---|
1308 |
|
---|
1309 | /* C is now the inverse */
|
---|
1310 | mp_exch (&C, c);
|
---|
1311 | res = MP_OKAY;
|
---|
1312 | LBL_ERR:mp_clear(&x);
|
---|
1313 | mp_clear(&y);
|
---|
1314 | mp_clear(&u);
|
---|
1315 | mp_clear(&v);
|
---|
1316 | mp_clear(&A);
|
---|
1317 | mp_clear(&B);
|
---|
1318 | mp_clear(&C);
|
---|
1319 | mp_clear(&D);
|
---|
1320 | return res;
|
---|
1321 | }
|
---|
1322 |
|
---|
1323 |
|
---|
1324 | /* compare magnitude of two ints (unsigned) */
|
---|
1325 | int mp_cmp_mag (mp_int * a, mp_int * b)
|
---|
1326 | {
|
---|
1327 | int n;
|
---|
1328 | mp_digit *tmpa, *tmpb;
|
---|
1329 |
|
---|
1330 | /* compare based on # of non-zero digits */
|
---|
1331 | if (a->used > b->used) {
|
---|
1332 | return MP_GT;
|
---|
1333 | }
|
---|
1334 |
|
---|
1335 | if (a->used < b->used) {
|
---|
1336 | return MP_LT;
|
---|
1337 | }
|
---|
1338 |
|
---|
1339 | /* alias for a */
|
---|
1340 | tmpa = a->dp + (a->used - 1);
|
---|
1341 |
|
---|
1342 | /* alias for b */
|
---|
1343 | tmpb = b->dp + (a->used - 1);
|
---|
1344 |
|
---|
1345 | /* compare based on digits */
|
---|
1346 | for (n = 0; n < a->used; ++n, --tmpa, --tmpb) {
|
---|
1347 | if (*tmpa > *tmpb) {
|
---|
1348 | return MP_GT;
|
---|
1349 | }
|
---|
1350 |
|
---|
1351 | if (*tmpa < *tmpb) {
|
---|
1352 | return MP_LT;
|
---|
1353 | }
|
---|
1354 | }
|
---|
1355 | return MP_EQ;
|
---|
1356 | }
|
---|
1357 |
|
---|
1358 |
|
---|
1359 | /* compare two ints (signed)*/
|
---|
1360 | int mp_cmp (mp_int * a, mp_int * b)
|
---|
1361 | {
|
---|
1362 | /* compare based on sign */
|
---|
1363 | if (a->sign != b->sign) {
|
---|
1364 | if (a->sign == MP_NEG) {
|
---|
1365 | return MP_LT;
|
---|
1366 | } else {
|
---|
1367 | return MP_GT;
|
---|
1368 | }
|
---|
1369 | }
|
---|
1370 |
|
---|
1371 | /* compare digits */
|
---|
1372 | if (a->sign == MP_NEG) {
|
---|
1373 | /* if negative compare opposite direction */
|
---|
1374 | return mp_cmp_mag(b, a);
|
---|
1375 | } else {
|
---|
1376 | return mp_cmp_mag(a, b);
|
---|
1377 | }
|
---|
1378 | }
|
---|
1379 |
|
---|
1380 |
|
---|
1381 | /* compare a digit */
|
---|
1382 | int mp_cmp_d(mp_int * a, mp_digit b)
|
---|
1383 | {
|
---|
1384 | /* special case for zero*/
|
---|
1385 | if (a->used == 0 && b == 0)
|
---|
1386 | return MP_EQ;
|
---|
1387 |
|
---|
1388 | /* compare based on sign */
|
---|
1389 | if ((b && a->used == 0) || a->sign == MP_NEG) {
|
---|
1390 | return MP_LT;
|
---|
1391 | }
|
---|
1392 |
|
---|
1393 | /* compare based on magnitude */
|
---|
1394 | if (a->used > 1) {
|
---|
1395 | return MP_GT;
|
---|
1396 | }
|
---|
1397 |
|
---|
1398 | /* compare the only digit of a to b */
|
---|
1399 | if (a->dp[0] > b) {
|
---|
1400 | return MP_GT;
|
---|
1401 | } else if (a->dp[0] < b) {
|
---|
1402 | return MP_LT;
|
---|
1403 | } else {
|
---|
1404 | return MP_EQ;
|
---|
1405 | }
|
---|
1406 | }
|
---|
1407 |
|
---|
1408 |
|
---|
1409 | /* set to a digit */
|
---|
1410 | int mp_set (mp_int * a, mp_digit b)
|
---|
1411 | {
|
---|
1412 | int res;
|
---|
1413 | mp_zero (a);
|
---|
1414 | res = mp_grow (a, 1);
|
---|
1415 | if (res == MP_OKAY) {
|
---|
1416 | a->dp[0] = (mp_digit)(b & MP_MASK);
|
---|
1417 | a->used = (a->dp[0] != 0) ? 1 : 0;
|
---|
1418 | }
|
---|
1419 | return res;
|
---|
1420 | }
|
---|
1421 |
|
---|
1422 | /* check if a bit is set */
|
---|
1423 | int mp_is_bit_set (mp_int *a, mp_digit b)
|
---|
1424 | {
|
---|
1425 | if ((mp_digit)a->used < b/DIGIT_BIT)
|
---|
1426 | return 0;
|
---|
1427 |
|
---|
1428 | return (int)((a->dp[b/DIGIT_BIT] >> b%DIGIT_BIT) & (mp_digit)1);
|
---|
1429 | }
|
---|
1430 |
|
---|
1431 | /* c = a mod b, 0 <= c < b */
|
---|
1432 | #if defined(FREESCALE_LTC_TFM)
|
---|
1433 | int wolfcrypt_mp_mod(mp_int * a, mp_int * b, mp_int * c)
|
---|
1434 | #else
|
---|
1435 | int mp_mod (mp_int * a, mp_int * b, mp_int * c)
|
---|
1436 | #endif
|
---|
1437 | {
|
---|
1438 | mp_int t;
|
---|
1439 | int res;
|
---|
1440 |
|
---|
1441 | if ((res = mp_init_size (&t, b->used)) != MP_OKAY) {
|
---|
1442 | return res;
|
---|
1443 | }
|
---|
1444 |
|
---|
1445 | if ((res = mp_div (a, b, NULL, &t)) != MP_OKAY) {
|
---|
1446 | mp_clear (&t);
|
---|
1447 | return res;
|
---|
1448 | }
|
---|
1449 |
|
---|
1450 | if ((mp_iszero(&t) != MP_NO) || (t.sign == b->sign)) {
|
---|
1451 | res = MP_OKAY;
|
---|
1452 | mp_exch (&t, c);
|
---|
1453 | } else {
|
---|
1454 | res = mp_add (b, &t, c);
|
---|
1455 | }
|
---|
1456 |
|
---|
1457 | mp_clear (&t);
|
---|
1458 | return res;
|
---|
1459 | }
|
---|
1460 |
|
---|
1461 |
|
---|
1462 | /* slower bit-bang division... also smaller */
|
---|
1463 | int mp_div(mp_int * a, mp_int * b, mp_int * c, mp_int * d)
|
---|
1464 | {
|
---|
1465 | mp_int ta, tb, tq, q;
|
---|
1466 | int res, n, n2;
|
---|
1467 |
|
---|
1468 | /* is divisor zero ? */
|
---|
1469 | if (mp_iszero (b) == MP_YES) {
|
---|
1470 | return MP_VAL;
|
---|
1471 | }
|
---|
1472 |
|
---|
1473 | /* if a < b then q=0, r = a */
|
---|
1474 | if (mp_cmp_mag (a, b) == MP_LT) {
|
---|
1475 | if (d != NULL) {
|
---|
1476 | res = mp_copy (a, d);
|
---|
1477 | } else {
|
---|
1478 | res = MP_OKAY;
|
---|
1479 | }
|
---|
1480 | if (c != NULL) {
|
---|
1481 | mp_zero (c);
|
---|
1482 | }
|
---|
1483 | return res;
|
---|
1484 | }
|
---|
1485 |
|
---|
1486 | /* init our temps */
|
---|
1487 | if ((res = mp_init_multi(&ta, &tb, &tq, &q, 0, 0)) != MP_OKAY) {
|
---|
1488 | return res;
|
---|
1489 | }
|
---|
1490 |
|
---|
1491 | if ((res = mp_set(&tq, 1)) != MP_OKAY) {
|
---|
1492 | return res;
|
---|
1493 | }
|
---|
1494 | n = mp_count_bits(a) - mp_count_bits(b);
|
---|
1495 | if (((res = mp_abs(a, &ta)) != MP_OKAY) ||
|
---|
1496 | ((res = mp_abs(b, &tb)) != MP_OKAY) ||
|
---|
1497 | ((res = mp_mul_2d(&tb, n, &tb)) != MP_OKAY) ||
|
---|
1498 | ((res = mp_mul_2d(&tq, n, &tq)) != MP_OKAY)) {
|
---|
1499 | goto LBL_ERR;
|
---|
1500 | }
|
---|
1501 |
|
---|
1502 | while (n-- >= 0) {
|
---|
1503 | if (mp_cmp(&tb, &ta) != MP_GT) {
|
---|
1504 | if (((res = mp_sub(&ta, &tb, &ta)) != MP_OKAY) ||
|
---|
1505 | ((res = mp_add(&q, &tq, &q)) != MP_OKAY)) {
|
---|
1506 | goto LBL_ERR;
|
---|
1507 | }
|
---|
1508 | }
|
---|
1509 | if (((res = mp_div_2d(&tb, 1, &tb, NULL)) != MP_OKAY) ||
|
---|
1510 | ((res = mp_div_2d(&tq, 1, &tq, NULL)) != MP_OKAY)) {
|
---|
1511 | goto LBL_ERR;
|
---|
1512 | }
|
---|
1513 | }
|
---|
1514 |
|
---|
1515 | /* now q == quotient and ta == remainder */
|
---|
1516 | n = a->sign;
|
---|
1517 | n2 = (a->sign == b->sign ? MP_ZPOS : MP_NEG);
|
---|
1518 | if (c != NULL) {
|
---|
1519 | mp_exch(c, &q);
|
---|
1520 | c->sign = (mp_iszero(c) == MP_YES) ? MP_ZPOS : n2;
|
---|
1521 | }
|
---|
1522 | if (d != NULL) {
|
---|
1523 | mp_exch(d, &ta);
|
---|
1524 | d->sign = (mp_iszero(d) == MP_YES) ? MP_ZPOS : n;
|
---|
1525 | }
|
---|
1526 | LBL_ERR:
|
---|
1527 | mp_clear(&ta);
|
---|
1528 | mp_clear(&tb);
|
---|
1529 | mp_clear(&tq);
|
---|
1530 | mp_clear(&q);
|
---|
1531 | return res;
|
---|
1532 | }
|
---|
1533 |
|
---|
1534 |
|
---|
1535 | /* b = a/2 */
|
---|
1536 | int mp_div_2(mp_int * a, mp_int * b)
|
---|
1537 | {
|
---|
1538 | int x, res, oldused;
|
---|
1539 |
|
---|
1540 | /* copy */
|
---|
1541 | if (b->alloc < a->used) {
|
---|
1542 | if ((res = mp_grow (b, a->used)) != MP_OKAY) {
|
---|
1543 | return res;
|
---|
1544 | }
|
---|
1545 | }
|
---|
1546 |
|
---|
1547 | oldused = b->used;
|
---|
1548 | b->used = a->used;
|
---|
1549 | {
|
---|
1550 | mp_digit r, rr, *tmpa, *tmpb;
|
---|
1551 |
|
---|
1552 | /* source alias */
|
---|
1553 | tmpa = a->dp + b->used - 1;
|
---|
1554 |
|
---|
1555 | /* dest alias */
|
---|
1556 | tmpb = b->dp + b->used - 1;
|
---|
1557 |
|
---|
1558 | /* carry */
|
---|
1559 | r = 0;
|
---|
1560 | for (x = b->used - 1; x >= 0; x--) {
|
---|
1561 | /* get the carry for the next iteration */
|
---|
1562 | rr = *tmpa & 1;
|
---|
1563 |
|
---|
1564 | /* shift the current digit, add in carry and store */
|
---|
1565 | *tmpb-- = (*tmpa-- >> 1) | (r << (DIGIT_BIT - 1));
|
---|
1566 |
|
---|
1567 | /* forward carry to next iteration */
|
---|
1568 | r = rr;
|
---|
1569 | }
|
---|
1570 |
|
---|
1571 | /* zero excess digits */
|
---|
1572 | tmpb = b->dp + b->used;
|
---|
1573 | for (x = b->used; x < oldused; x++) {
|
---|
1574 | *tmpb++ = 0;
|
---|
1575 | }
|
---|
1576 | }
|
---|
1577 | b->sign = a->sign;
|
---|
1578 | mp_clamp (b);
|
---|
1579 | return MP_OKAY;
|
---|
1580 | }
|
---|
1581 |
|
---|
1582 |
|
---|
1583 | /* high level addition (handles signs) */
|
---|
1584 | int mp_add (mp_int * a, mp_int * b, mp_int * c)
|
---|
1585 | {
|
---|
1586 | int sa, sb, res;
|
---|
1587 |
|
---|
1588 | /* get sign of both inputs */
|
---|
1589 | sa = a->sign;
|
---|
1590 | sb = b->sign;
|
---|
1591 |
|
---|
1592 | /* handle two cases, not four */
|
---|
1593 | if (sa == sb) {
|
---|
1594 | /* both positive or both negative */
|
---|
1595 | /* add their magnitudes, copy the sign */
|
---|
1596 | c->sign = sa;
|
---|
1597 | res = s_mp_add (a, b, c);
|
---|
1598 | } else {
|
---|
1599 | /* one positive, the other negative */
|
---|
1600 | /* subtract the one with the greater magnitude from */
|
---|
1601 | /* the one of the lesser magnitude. The result gets */
|
---|
1602 | /* the sign of the one with the greater magnitude. */
|
---|
1603 | if (mp_cmp_mag (a, b) == MP_LT) {
|
---|
1604 | c->sign = sb;
|
---|
1605 | res = s_mp_sub (b, a, c);
|
---|
1606 | } else {
|
---|
1607 | c->sign = sa;
|
---|
1608 | res = s_mp_sub (a, b, c);
|
---|
1609 | }
|
---|
1610 | }
|
---|
1611 | return res;
|
---|
1612 | }
|
---|
1613 |
|
---|
1614 |
|
---|
1615 | /* low level addition, based on HAC pp.594, Algorithm 14.7 */
|
---|
1616 | int s_mp_add (mp_int * a, mp_int * b, mp_int * c)
|
---|
1617 | {
|
---|
1618 | mp_int *x;
|
---|
1619 | int olduse, res, min_ab, max_ab;
|
---|
1620 |
|
---|
1621 | /* find sizes, we let |a| <= |b| which means we have to sort
|
---|
1622 | * them. "x" will point to the input with the most digits
|
---|
1623 | */
|
---|
1624 | if (a->used > b->used) {
|
---|
1625 | min_ab = b->used;
|
---|
1626 | max_ab = a->used;
|
---|
1627 | x = a;
|
---|
1628 | } else {
|
---|
1629 | min_ab = a->used;
|
---|
1630 | max_ab = b->used;
|
---|
1631 | x = b;
|
---|
1632 | }
|
---|
1633 |
|
---|
1634 | /* init result */
|
---|
1635 | if (c->alloc < max_ab + 1) {
|
---|
1636 | if ((res = mp_grow (c, max_ab + 1)) != MP_OKAY) {
|
---|
1637 | return res;
|
---|
1638 | }
|
---|
1639 | }
|
---|
1640 |
|
---|
1641 | /* get old used digit count and set new one */
|
---|
1642 | olduse = c->used;
|
---|
1643 | c->used = max_ab + 1;
|
---|
1644 |
|
---|
1645 | {
|
---|
1646 | mp_digit u, *tmpa, *tmpb, *tmpc;
|
---|
1647 | int i;
|
---|
1648 |
|
---|
1649 | /* alias for digit pointers */
|
---|
1650 |
|
---|
1651 | /* first input */
|
---|
1652 | tmpa = a->dp;
|
---|
1653 |
|
---|
1654 | /* second input */
|
---|
1655 | tmpb = b->dp;
|
---|
1656 |
|
---|
1657 | /* destination */
|
---|
1658 | tmpc = c->dp;
|
---|
1659 |
|
---|
1660 | /* zero the carry */
|
---|
1661 | u = 0;
|
---|
1662 | for (i = 0; i < min_ab; i++) {
|
---|
1663 | /* Compute the sum at one digit, T[i] = A[i] + B[i] + U */
|
---|
1664 | *tmpc = *tmpa++ + *tmpb++ + u;
|
---|
1665 |
|
---|
1666 | /* U = carry bit of T[i] */
|
---|
1667 | u = *tmpc >> ((mp_digit)DIGIT_BIT);
|
---|
1668 |
|
---|
1669 | /* take away carry bit from T[i] */
|
---|
1670 | *tmpc++ &= MP_MASK;
|
---|
1671 | }
|
---|
1672 |
|
---|
1673 | /* now copy higher words if any, that is in A+B
|
---|
1674 | * if A or B has more digits add those in
|
---|
1675 | */
|
---|
1676 | if (min_ab != max_ab) {
|
---|
1677 | for (; i < max_ab; i++) {
|
---|
1678 | /* T[i] = X[i] + U */
|
---|
1679 | *tmpc = x->dp[i] + u;
|
---|
1680 |
|
---|
1681 | /* U = carry bit of T[i] */
|
---|
1682 | u = *tmpc >> ((mp_digit)DIGIT_BIT);
|
---|
1683 |
|
---|
1684 | /* take away carry bit from T[i] */
|
---|
1685 | *tmpc++ &= MP_MASK;
|
---|
1686 | }
|
---|
1687 | }
|
---|
1688 |
|
---|
1689 | /* add carry */
|
---|
1690 | *tmpc++ = u;
|
---|
1691 |
|
---|
1692 | /* clear digits above olduse */
|
---|
1693 | for (i = c->used; i < olduse; i++) {
|
---|
1694 | *tmpc++ = 0;
|
---|
1695 | }
|
---|
1696 | }
|
---|
1697 |
|
---|
1698 | mp_clamp (c);
|
---|
1699 | return MP_OKAY;
|
---|
1700 | }
|
---|
1701 |
|
---|
1702 |
|
---|
1703 | /* low level subtraction (assumes |a| > |b|), HAC pp.595 Algorithm 14.9 */
|
---|
1704 | int s_mp_sub (mp_int * a, mp_int * b, mp_int * c)
|
---|
1705 | {
|
---|
1706 | int olduse, res, min_b, max_a;
|
---|
1707 |
|
---|
1708 | /* find sizes */
|
---|
1709 | min_b = b->used;
|
---|
1710 | max_a = a->used;
|
---|
1711 |
|
---|
1712 | /* init result */
|
---|
1713 | if (c->alloc < max_a) {
|
---|
1714 | if ((res = mp_grow (c, max_a)) != MP_OKAY) {
|
---|
1715 | return res;
|
---|
1716 | }
|
---|
1717 | }
|
---|
1718 |
|
---|
1719 | /* sanity check on destination */
|
---|
1720 | if (c->dp == NULL)
|
---|
1721 | return MP_VAL;
|
---|
1722 |
|
---|
1723 | olduse = c->used;
|
---|
1724 | c->used = max_a;
|
---|
1725 |
|
---|
1726 | {
|
---|
1727 | mp_digit u, *tmpa, *tmpb, *tmpc;
|
---|
1728 | int i;
|
---|
1729 |
|
---|
1730 | /* alias for digit pointers */
|
---|
1731 | tmpa = a->dp;
|
---|
1732 | tmpb = b->dp;
|
---|
1733 | tmpc = c->dp;
|
---|
1734 |
|
---|
1735 | /* set carry to zero */
|
---|
1736 | u = 0;
|
---|
1737 | for (i = 0; i < min_b; i++) {
|
---|
1738 | /* T[i] = A[i] - B[i] - U */
|
---|
1739 | *tmpc = *tmpa++ - *tmpb++ - u;
|
---|
1740 |
|
---|
1741 | /* U = carry bit of T[i]
|
---|
1742 | * Note this saves performing an AND operation since
|
---|
1743 | * if a carry does occur it will propagate all the way to the
|
---|
1744 | * MSB. As a result a single shift is enough to get the carry
|
---|
1745 | */
|
---|
1746 | u = *tmpc >> ((mp_digit)(CHAR_BIT * sizeof (mp_digit) - 1));
|
---|
1747 |
|
---|
1748 | /* Clear carry from T[i] */
|
---|
1749 | *tmpc++ &= MP_MASK;
|
---|
1750 | }
|
---|
1751 |
|
---|
1752 | /* now copy higher words if any, e.g. if A has more digits than B */
|
---|
1753 | for (; i < max_a; i++) {
|
---|
1754 | /* T[i] = A[i] - U */
|
---|
1755 | *tmpc = *tmpa++ - u;
|
---|
1756 |
|
---|
1757 | /* U = carry bit of T[i] */
|
---|
1758 | u = *tmpc >> ((mp_digit)(CHAR_BIT * sizeof (mp_digit) - 1));
|
---|
1759 |
|
---|
1760 | /* Clear carry from T[i] */
|
---|
1761 | *tmpc++ &= MP_MASK;
|
---|
1762 | }
|
---|
1763 |
|
---|
1764 | /* clear digits above used (since we may not have grown result above) */
|
---|
1765 | for (i = c->used; i < olduse; i++) {
|
---|
1766 | *tmpc++ = 0;
|
---|
1767 | }
|
---|
1768 | }
|
---|
1769 |
|
---|
1770 | mp_clamp (c);
|
---|
1771 | return MP_OKAY;
|
---|
1772 | }
|
---|
1773 |
|
---|
1774 |
|
---|
1775 | /* high level subtraction (handles signs) */
|
---|
1776 | int mp_sub (mp_int * a, mp_int * b, mp_int * c)
|
---|
1777 | {
|
---|
1778 | int sa, sb, res;
|
---|
1779 |
|
---|
1780 | sa = a->sign;
|
---|
1781 | sb = b->sign;
|
---|
1782 |
|
---|
1783 | if (sa != sb) {
|
---|
1784 | /* subtract a negative from a positive, OR */
|
---|
1785 | /* subtract a positive from a negative. */
|
---|
1786 | /* In either case, ADD their magnitudes, */
|
---|
1787 | /* and use the sign of the first number. */
|
---|
1788 | c->sign = sa;
|
---|
1789 | res = s_mp_add (a, b, c);
|
---|
1790 | } else {
|
---|
1791 | /* subtract a positive from a positive, OR */
|
---|
1792 | /* subtract a negative from a negative. */
|
---|
1793 | /* First, take the difference between their */
|
---|
1794 | /* magnitudes, then... */
|
---|
1795 | if (mp_cmp_mag (a, b) != MP_LT) {
|
---|
1796 | /* Copy the sign from the first */
|
---|
1797 | c->sign = sa;
|
---|
1798 | /* The first has a larger or equal magnitude */
|
---|
1799 | res = s_mp_sub (a, b, c);
|
---|
1800 | } else {
|
---|
1801 | /* The result has the *opposite* sign from */
|
---|
1802 | /* the first number. */
|
---|
1803 | c->sign = (sa == MP_ZPOS) ? MP_NEG : MP_ZPOS;
|
---|
1804 | /* The second has a larger magnitude */
|
---|
1805 | res = s_mp_sub (b, a, c);
|
---|
1806 | }
|
---|
1807 | }
|
---|
1808 | return res;
|
---|
1809 | }
|
---|
1810 |
|
---|
1811 |
|
---|
1812 | /* determines if reduce_2k_l can be used */
|
---|
1813 | int mp_reduce_is_2k_l(mp_int *a)
|
---|
1814 | {
|
---|
1815 | int ix, iy;
|
---|
1816 |
|
---|
1817 | if (a->used == 0) {
|
---|
1818 | return MP_NO;
|
---|
1819 | } else if (a->used == 1) {
|
---|
1820 | return MP_YES;
|
---|
1821 | } else if (a->used > 1) {
|
---|
1822 | /* if more than half of the digits are -1 we're sold */
|
---|
1823 | for (iy = ix = 0; ix < a->used; ix++) {
|
---|
1824 | if (a->dp[ix] == MP_MASK) {
|
---|
1825 | ++iy;
|
---|
1826 | }
|
---|
1827 | }
|
---|
1828 | return (iy >= (a->used/2)) ? MP_YES : MP_NO;
|
---|
1829 |
|
---|
1830 | }
|
---|
1831 | return MP_NO;
|
---|
1832 | }
|
---|
1833 |
|
---|
1834 |
|
---|
1835 | /* determines if mp_reduce_2k can be used */
|
---|
1836 | int mp_reduce_is_2k(mp_int *a)
|
---|
1837 | {
|
---|
1838 | int ix, iy, iw;
|
---|
1839 | mp_digit iz;
|
---|
1840 |
|
---|
1841 | if (a->used == 0) {
|
---|
1842 | return MP_NO;
|
---|
1843 | } else if (a->used == 1) {
|
---|
1844 | return MP_YES;
|
---|
1845 | } else if (a->used > 1) {
|
---|
1846 | iy = mp_count_bits(a);
|
---|
1847 | iz = 1;
|
---|
1848 | iw = 1;
|
---|
1849 |
|
---|
1850 | /* Test every bit from the second digit up, must be 1 */
|
---|
1851 | for (ix = DIGIT_BIT; ix < iy; ix++) {
|
---|
1852 | if ((a->dp[iw] & iz) == 0) {
|
---|
1853 | return MP_NO;
|
---|
1854 | }
|
---|
1855 | iz <<= 1;
|
---|
1856 | if (iz > (mp_digit)MP_MASK) {
|
---|
1857 | ++iw;
|
---|
1858 | iz = 1;
|
---|
1859 | }
|
---|
1860 | }
|
---|
1861 | }
|
---|
1862 | return MP_YES;
|
---|
1863 | }
|
---|
1864 |
|
---|
1865 |
|
---|
1866 | /* determines if a number is a valid DR modulus */
|
---|
1867 | int mp_dr_is_modulus(mp_int *a)
|
---|
1868 | {
|
---|
1869 | int ix;
|
---|
1870 |
|
---|
1871 | /* must be at least two digits */
|
---|
1872 | if (a->used < 2) {
|
---|
1873 | return 0;
|
---|
1874 | }
|
---|
1875 |
|
---|
1876 | /* must be of the form b**k - a [a <= b] so all
|
---|
1877 | * but the first digit must be equal to -1 (mod b).
|
---|
1878 | */
|
---|
1879 | for (ix = 1; ix < a->used; ix++) {
|
---|
1880 | if (a->dp[ix] != MP_MASK) {
|
---|
1881 | return 0;
|
---|
1882 | }
|
---|
1883 | }
|
---|
1884 | return 1;
|
---|
1885 | }
|
---|
1886 |
|
---|
1887 |
|
---|
1888 | /* computes Y == G**X mod P, HAC pp.616, Algorithm 14.85
|
---|
1889 | *
|
---|
1890 | * Uses a left-to-right k-ary sliding window to compute the modular
|
---|
1891 | * exponentiation.
|
---|
1892 | * The value of k changes based on the size of the exponent.
|
---|
1893 | *
|
---|
1894 | * Uses Montgomery or Diminished Radix reduction [whichever appropriate]
|
---|
1895 | */
|
---|
1896 |
|
---|
1897 | #ifdef MP_LOW_MEM
|
---|
1898 | #define TAB_SIZE 32
|
---|
1899 | #else
|
---|
1900 | #define TAB_SIZE 256
|
---|
1901 | #endif
|
---|
1902 |
|
---|
1903 | int mp_exptmod_fast (mp_int * G, mp_int * X, mp_int * P, mp_int * Y,
|
---|
1904 | int redmode)
|
---|
1905 | {
|
---|
1906 | mp_int res;
|
---|
1907 | mp_digit buf, mp;
|
---|
1908 | int err, bitbuf, bitcpy, bitcnt, mode, digidx, x, y, winsize;
|
---|
1909 | #ifdef WOLFSSL_SMALL_STACK
|
---|
1910 | mp_int* M;
|
---|
1911 | #else
|
---|
1912 | mp_int M[TAB_SIZE];
|
---|
1913 | #endif
|
---|
1914 | /* use a pointer to the reduction algorithm. This allows us to use
|
---|
1915 | * one of many reduction algorithms without modding the guts of
|
---|
1916 | * the code with if statements everywhere.
|
---|
1917 | */
|
---|
1918 | int (*redux)(mp_int*,mp_int*,mp_digit) = NULL;
|
---|
1919 |
|
---|
1920 | #ifdef WOLFSSL_SMALL_STACK
|
---|
1921 | M = (mp_int*) XMALLOC(sizeof(mp_int) * TAB_SIZE, NULL,
|
---|
1922 | DYNAMIC_TYPE_BIGINT);
|
---|
1923 | if (M == NULL)
|
---|
1924 | return MP_MEM;
|
---|
1925 | #endif
|
---|
1926 |
|
---|
1927 | /* find window size */
|
---|
1928 | x = mp_count_bits (X);
|
---|
1929 | if (x <= 7) {
|
---|
1930 | winsize = 2;
|
---|
1931 | } else if (x <= 36) {
|
---|
1932 | winsize = 3;
|
---|
1933 | } else if (x <= 140) {
|
---|
1934 | winsize = 4;
|
---|
1935 | } else if (x <= 450) {
|
---|
1936 | winsize = 5;
|
---|
1937 | } else if (x <= 1303) {
|
---|
1938 | winsize = 6;
|
---|
1939 | } else if (x <= 3529) {
|
---|
1940 | winsize = 7;
|
---|
1941 | } else {
|
---|
1942 | winsize = 8;
|
---|
1943 | }
|
---|
1944 |
|
---|
1945 | #ifdef MP_LOW_MEM
|
---|
1946 | if (winsize > 5) {
|
---|
1947 | winsize = 5;
|
---|
1948 | }
|
---|
1949 | #endif
|
---|
1950 |
|
---|
1951 | /* init M array */
|
---|
1952 | /* init first cell */
|
---|
1953 | if ((err = mp_init_size(&M[1], P->alloc)) != MP_OKAY) {
|
---|
1954 | #ifdef WOLFSSL_SMALL_STACK
|
---|
1955 | XFREE(M, NULL, DYNAMIC_TYPE_BIGINT);
|
---|
1956 | #endif
|
---|
1957 |
|
---|
1958 | return err;
|
---|
1959 | }
|
---|
1960 |
|
---|
1961 | /* now init the second half of the array */
|
---|
1962 | for (x = 1<<(winsize-1); x < (1 << winsize); x++) {
|
---|
1963 | if ((err = mp_init_size(&M[x], P->alloc)) != MP_OKAY) {
|
---|
1964 | for (y = 1<<(winsize-1); y < x; y++) {
|
---|
1965 | mp_clear (&M[y]);
|
---|
1966 | }
|
---|
1967 | mp_clear(&M[1]);
|
---|
1968 |
|
---|
1969 | #ifdef WOLFSSL_SMALL_STACK
|
---|
1970 | XFREE(M, NULL, DYNAMIC_TYPE_BIGINT);
|
---|
1971 | #endif
|
---|
1972 |
|
---|
1973 | return err;
|
---|
1974 | }
|
---|
1975 | }
|
---|
1976 |
|
---|
1977 | /* determine and setup reduction code */
|
---|
1978 | if (redmode == 0) {
|
---|
1979 | #ifdef BN_MP_MONTGOMERY_SETUP_C
|
---|
1980 | /* now setup montgomery */
|
---|
1981 | if ((err = mp_montgomery_setup (P, &mp)) != MP_OKAY) {
|
---|
1982 | goto LBL_M;
|
---|
1983 | }
|
---|
1984 | #else
|
---|
1985 | err = MP_VAL;
|
---|
1986 | goto LBL_M;
|
---|
1987 | #endif
|
---|
1988 |
|
---|
1989 | /* automatically pick the comba one if available (saves quite a few
|
---|
1990 | calls/ifs) */
|
---|
1991 | #ifdef BN_FAST_MP_MONTGOMERY_REDUCE_C
|
---|
1992 | if (((P->used * 2 + 1) < (int)MP_WARRAY) &&
|
---|
1993 | P->used < (1 << ((CHAR_BIT * sizeof (mp_word)) - (2 * DIGIT_BIT)))) {
|
---|
1994 | redux = fast_mp_montgomery_reduce;
|
---|
1995 | } else
|
---|
1996 | #endif
|
---|
1997 | {
|
---|
1998 | #ifdef BN_MP_MONTGOMERY_REDUCE_C
|
---|
1999 | /* use slower baseline Montgomery method */
|
---|
2000 | redux = mp_montgomery_reduce;
|
---|
2001 | #endif
|
---|
2002 | }
|
---|
2003 | } else if (redmode == 1) {
|
---|
2004 | #if defined(BN_MP_DR_SETUP_C) && defined(BN_MP_DR_REDUCE_C)
|
---|
2005 | /* setup DR reduction for moduli of the form B**k - b */
|
---|
2006 | mp_dr_setup(P, &mp);
|
---|
2007 | redux = mp_dr_reduce;
|
---|
2008 | #endif
|
---|
2009 | } else {
|
---|
2010 | #if defined(BN_MP_REDUCE_2K_SETUP_C) && defined(BN_MP_REDUCE_2K_C)
|
---|
2011 | /* setup DR reduction for moduli of the form 2**k - b */
|
---|
2012 | if ((err = mp_reduce_2k_setup(P, &mp)) != MP_OKAY) {
|
---|
2013 | goto LBL_M;
|
---|
2014 | }
|
---|
2015 | redux = mp_reduce_2k;
|
---|
2016 | #endif
|
---|
2017 | }
|
---|
2018 |
|
---|
2019 | if (redux == NULL) {
|
---|
2020 | err = MP_VAL;
|
---|
2021 | goto LBL_M;
|
---|
2022 | }
|
---|
2023 |
|
---|
2024 | /* setup result */
|
---|
2025 | if ((err = mp_init_size (&res, P->alloc)) != MP_OKAY) {
|
---|
2026 | goto LBL_M;
|
---|
2027 | }
|
---|
2028 |
|
---|
2029 | /* create M table
|
---|
2030 | *
|
---|
2031 |
|
---|
2032 | *
|
---|
2033 | * The first half of the table is not computed though accept for M[0] and M[1]
|
---|
2034 | */
|
---|
2035 |
|
---|
2036 | if (redmode == 0) {
|
---|
2037 | #ifdef BN_MP_MONTGOMERY_CALC_NORMALIZATION_C
|
---|
2038 | /* now we need R mod m */
|
---|
2039 | if ((err = mp_montgomery_calc_normalization (&res, P)) != MP_OKAY) {
|
---|
2040 | goto LBL_RES;
|
---|
2041 | }
|
---|
2042 |
|
---|
2043 | /* now set M[1] to G * R mod m */
|
---|
2044 | if ((err = mp_mulmod (G, &res, P, &M[1])) != MP_OKAY) {
|
---|
2045 | goto LBL_RES;
|
---|
2046 | }
|
---|
2047 | #else
|
---|
2048 | err = MP_VAL;
|
---|
2049 | goto LBL_RES;
|
---|
2050 | #endif
|
---|
2051 | } else {
|
---|
2052 | if ((err = mp_set(&res, 1)) != MP_OKAY) {
|
---|
2053 | goto LBL_RES;
|
---|
2054 | }
|
---|
2055 | if ((err = mp_mod(G, P, &M[1])) != MP_OKAY) {
|
---|
2056 | goto LBL_RES;
|
---|
2057 | }
|
---|
2058 | }
|
---|
2059 |
|
---|
2060 | /* compute the value at M[1<<(winsize-1)] by squaring M[1] (winsize-1) times*/
|
---|
2061 | if ((err = mp_copy (&M[1], &M[(mp_digit)(1 << (winsize - 1))])) != MP_OKAY) {
|
---|
2062 | goto LBL_RES;
|
---|
2063 | }
|
---|
2064 |
|
---|
2065 | for (x = 0; x < (winsize - 1); x++) {
|
---|
2066 | if ((err = mp_sqr (&M[(mp_digit)(1 << (winsize - 1))],
|
---|
2067 | &M[(mp_digit)(1 << (winsize - 1))])) != MP_OKAY) {
|
---|
2068 | goto LBL_RES;
|
---|
2069 | }
|
---|
2070 | if ((err = redux (&M[(mp_digit)(1 << (winsize - 1))], P, mp)) != MP_OKAY) {
|
---|
2071 | goto LBL_RES;
|
---|
2072 | }
|
---|
2073 | }
|
---|
2074 |
|
---|
2075 | /* create upper table */
|
---|
2076 | for (x = (1 << (winsize - 1)) + 1; x < (1 << winsize); x++) {
|
---|
2077 | if ((err = mp_mul (&M[x - 1], &M[1], &M[x])) != MP_OKAY) {
|
---|
2078 | goto LBL_RES;
|
---|
2079 | }
|
---|
2080 | if ((err = redux (&M[x], P, mp)) != MP_OKAY) {
|
---|
2081 | goto LBL_RES;
|
---|
2082 | }
|
---|
2083 | }
|
---|
2084 |
|
---|
2085 | /* set initial mode and bit cnt */
|
---|
2086 | mode = 0;
|
---|
2087 | bitcnt = 1;
|
---|
2088 | buf = 0;
|
---|
2089 | digidx = X->used - 1;
|
---|
2090 | bitcpy = 0;
|
---|
2091 | bitbuf = 0;
|
---|
2092 |
|
---|
2093 | for (;;) {
|
---|
2094 | /* grab next digit as required */
|
---|
2095 | if (--bitcnt == 0) {
|
---|
2096 | /* if digidx == -1 we are out of digits so break */
|
---|
2097 | if (digidx == -1) {
|
---|
2098 | break;
|
---|
2099 | }
|
---|
2100 | /* read next digit and reset bitcnt */
|
---|
2101 | buf = X->dp[digidx--];
|
---|
2102 | bitcnt = (int)DIGIT_BIT;
|
---|
2103 | }
|
---|
2104 |
|
---|
2105 | /* grab the next msb from the exponent */
|
---|
2106 | y = (int)(buf >> (DIGIT_BIT - 1)) & 1;
|
---|
2107 | buf <<= (mp_digit)1;
|
---|
2108 |
|
---|
2109 | /* if the bit is zero and mode == 0 then we ignore it
|
---|
2110 | * These represent the leading zero bits before the first 1 bit
|
---|
2111 | * in the exponent. Technically this opt is not required but it
|
---|
2112 | * does lower the # of trivial squaring/reductions used
|
---|
2113 | */
|
---|
2114 | if (mode == 0 && y == 0) {
|
---|
2115 | continue;
|
---|
2116 | }
|
---|
2117 |
|
---|
2118 | /* if the bit is zero and mode == 1 then we square */
|
---|
2119 | if (mode == 1 && y == 0) {
|
---|
2120 | if ((err = mp_sqr (&res, &res)) != MP_OKAY) {
|
---|
2121 | goto LBL_RES;
|
---|
2122 | }
|
---|
2123 | if ((err = redux (&res, P, mp)) != MP_OKAY) {
|
---|
2124 | goto LBL_RES;
|
---|
2125 | }
|
---|
2126 | continue;
|
---|
2127 | }
|
---|
2128 |
|
---|
2129 | /* else we add it to the window */
|
---|
2130 | bitbuf |= (y << (winsize - ++bitcpy));
|
---|
2131 | mode = 2;
|
---|
2132 |
|
---|
2133 | if (bitcpy == winsize) {
|
---|
2134 | /* ok window is filled so square as required and multiply */
|
---|
2135 | /* square first */
|
---|
2136 | for (x = 0; x < winsize; x++) {
|
---|
2137 | if ((err = mp_sqr (&res, &res)) != MP_OKAY) {
|
---|
2138 | goto LBL_RES;
|
---|
2139 | }
|
---|
2140 | if ((err = redux (&res, P, mp)) != MP_OKAY) {
|
---|
2141 | goto LBL_RES;
|
---|
2142 | }
|
---|
2143 | }
|
---|
2144 |
|
---|
2145 | /* then multiply */
|
---|
2146 | if ((err = mp_mul (&res, &M[bitbuf], &res)) != MP_OKAY) {
|
---|
2147 | goto LBL_RES;
|
---|
2148 | }
|
---|
2149 | if ((err = redux (&res, P, mp)) != MP_OKAY) {
|
---|
2150 | goto LBL_RES;
|
---|
2151 | }
|
---|
2152 |
|
---|
2153 | /* empty window and reset */
|
---|
2154 | bitcpy = 0;
|
---|
2155 | bitbuf = 0;
|
---|
2156 | mode = 1;
|
---|
2157 | }
|
---|
2158 | }
|
---|
2159 |
|
---|
2160 | /* if bits remain then square/multiply */
|
---|
2161 | if (mode == 2 && bitcpy > 0) {
|
---|
2162 | /* square then multiply if the bit is set */
|
---|
2163 | for (x = 0; x < bitcpy; x++) {
|
---|
2164 | if ((err = mp_sqr (&res, &res)) != MP_OKAY) {
|
---|
2165 | goto LBL_RES;
|
---|
2166 | }
|
---|
2167 | if ((err = redux (&res, P, mp)) != MP_OKAY) {
|
---|
2168 | goto LBL_RES;
|
---|
2169 | }
|
---|
2170 |
|
---|
2171 | /* get next bit of the window */
|
---|
2172 | bitbuf <<= 1;
|
---|
2173 | if ((bitbuf & (1 << winsize)) != 0) {
|
---|
2174 | /* then multiply */
|
---|
2175 | if ((err = mp_mul (&res, &M[1], &res)) != MP_OKAY) {
|
---|
2176 | goto LBL_RES;
|
---|
2177 | }
|
---|
2178 | if ((err = redux (&res, P, mp)) != MP_OKAY) {
|
---|
2179 | goto LBL_RES;
|
---|
2180 | }
|
---|
2181 | }
|
---|
2182 | }
|
---|
2183 | }
|
---|
2184 |
|
---|
2185 | if (redmode == 0) {
|
---|
2186 | /* fixup result if Montgomery reduction is used
|
---|
2187 | * recall that any value in a Montgomery system is
|
---|
2188 | * actually multiplied by R mod n. So we have
|
---|
2189 | * to reduce one more time to cancel out the factor
|
---|
2190 | * of R.
|
---|
2191 | */
|
---|
2192 | if ((err = redux(&res, P, mp)) != MP_OKAY) {
|
---|
2193 | goto LBL_RES;
|
---|
2194 | }
|
---|
2195 | }
|
---|
2196 |
|
---|
2197 | /* swap res with Y */
|
---|
2198 | mp_exch (&res, Y);
|
---|
2199 | err = MP_OKAY;
|
---|
2200 | LBL_RES:mp_clear (&res);
|
---|
2201 | LBL_M:
|
---|
2202 | mp_clear(&M[1]);
|
---|
2203 | for (x = 1<<(winsize-1); x < (1 << winsize); x++) {
|
---|
2204 | mp_clear (&M[x]);
|
---|
2205 | }
|
---|
2206 |
|
---|
2207 | #ifdef WOLFSSL_SMALL_STACK
|
---|
2208 | XFREE(M, NULL, DYNAMIC_TYPE_BIGINT);
|
---|
2209 | #endif
|
---|
2210 |
|
---|
2211 | return err;
|
---|
2212 | }
|
---|
2213 |
|
---|
2214 | #ifdef BN_MP_EXPTMOD_BASE_2
|
---|
2215 | #if DIGIT_BIT < 16
|
---|
2216 | #define WINSIZE 3
|
---|
2217 | #elif DIGIT_BIT < 32
|
---|
2218 | #define WINSIZE 4
|
---|
2219 | #elif DIGIT_BIT < 64
|
---|
2220 | #define WINSIZE 5
|
---|
2221 | #elif DIGIT_BIT < 128
|
---|
2222 | #define WINSIZE 6
|
---|
2223 | #endif
|
---|
2224 | int mp_exptmod_base_2(mp_int * X, mp_int * P, mp_int * Y)
|
---|
2225 | {
|
---|
2226 | mp_digit buf, mp;
|
---|
2227 | int err = MP_OKAY, bitbuf, bitcpy, bitcnt, digidx, x, y;
|
---|
2228 | #ifdef WOLFSSL_SMALL_STACK
|
---|
2229 | mp_int *res = NULL;
|
---|
2230 | #else
|
---|
2231 | mp_int res[1];
|
---|
2232 | #endif
|
---|
2233 | int (*redux)(mp_int*,mp_int*,mp_digit) = NULL;
|
---|
2234 |
|
---|
2235 | /* automatically pick the comba one if available (saves quite a few
|
---|
2236 | calls/ifs) */
|
---|
2237 | #ifdef BN_FAST_MP_MONTGOMERY_REDUCE_C
|
---|
2238 | if (((P->used * 2 + 1) < (int)MP_WARRAY) &&
|
---|
2239 | P->used < (1 << ((CHAR_BIT * sizeof (mp_word)) - (2 * DIGIT_BIT)))) {
|
---|
2240 | redux = fast_mp_montgomery_reduce;
|
---|
2241 | } else
|
---|
2242 | #endif
|
---|
2243 | {
|
---|
2244 | #ifdef BN_MP_MONTGOMERY_REDUCE_C
|
---|
2245 | /* use slower baseline Montgomery method */
|
---|
2246 | redux = mp_montgomery_reduce;
|
---|
2247 | #else
|
---|
2248 | return MP_VAL;
|
---|
2249 | #endif
|
---|
2250 | }
|
---|
2251 |
|
---|
2252 | #ifdef WOLFSSL_SMALL_STACK
|
---|
2253 | res = (mp_int*)XMALLOC(sizeof(mp_int), NULL, DYNAMIC_TYPE_TMP_BUFFER);
|
---|
2254 | if (res == NULL) {
|
---|
2255 | return MP_MEM;
|
---|
2256 | }
|
---|
2257 | #endif
|
---|
2258 |
|
---|
2259 | /* now setup montgomery */
|
---|
2260 | if ((err = mp_montgomery_setup(P, &mp)) != MP_OKAY) {
|
---|
2261 | goto LBL_M;
|
---|
2262 | }
|
---|
2263 |
|
---|
2264 | /* setup result */
|
---|
2265 | if ((err = mp_init(res)) != MP_OKAY) {
|
---|
2266 | goto LBL_M;
|
---|
2267 | }
|
---|
2268 |
|
---|
2269 | /* now we need R mod m */
|
---|
2270 | if ((err = mp_montgomery_calc_normalization(res, P)) != MP_OKAY) {
|
---|
2271 | goto LBL_RES;
|
---|
2272 | }
|
---|
2273 |
|
---|
2274 | /* Get the top bits left over after taking WINSIZE bits starting at the
|
---|
2275 | * least-significant.
|
---|
2276 | */
|
---|
2277 | digidx = X->used - 1;
|
---|
2278 | bitcpy = (X->used * DIGIT_BIT) % WINSIZE;
|
---|
2279 | if (bitcpy > 0) {
|
---|
2280 | bitcnt = (int)DIGIT_BIT - bitcpy;
|
---|
2281 | buf = X->dp[digidx--];
|
---|
2282 | bitbuf = (int)(buf >> bitcnt);
|
---|
2283 | /* Multiply montgomery representation of 1 by 2 ^ top */
|
---|
2284 | err = mp_mul_2d(res, bitbuf, res);
|
---|
2285 | if (err != MP_OKAY) {
|
---|
2286 | goto LBL_RES;
|
---|
2287 | }
|
---|
2288 | err = mp_mod(res, P, res);
|
---|
2289 | if (err != MP_OKAY) {
|
---|
2290 | goto LBL_RES;
|
---|
2291 | }
|
---|
2292 | /* Move out bits used */
|
---|
2293 | buf <<= bitcpy;
|
---|
2294 | bitcnt++;
|
---|
2295 | }
|
---|
2296 | else {
|
---|
2297 | bitcnt = 1;
|
---|
2298 | buf = 0;
|
---|
2299 | }
|
---|
2300 |
|
---|
2301 | /* empty window and reset */
|
---|
2302 | bitbuf = 0;
|
---|
2303 | bitcpy = 0;
|
---|
2304 |
|
---|
2305 | for (;;) {
|
---|
2306 | /* grab next digit as required */
|
---|
2307 | if (--bitcnt == 0) {
|
---|
2308 | /* if digidx == -1 we are out of digits so break */
|
---|
2309 | if (digidx == -1) {
|
---|
2310 | break;
|
---|
2311 | }
|
---|
2312 | /* read next digit and reset bitcnt */
|
---|
2313 | buf = X->dp[digidx--];
|
---|
2314 | bitcnt = (int)DIGIT_BIT;
|
---|
2315 | }
|
---|
2316 |
|
---|
2317 | /* grab the next msb from the exponent */
|
---|
2318 | y = (int)(buf >> (DIGIT_BIT - 1)) & 1;
|
---|
2319 | buf <<= (mp_digit)1;
|
---|
2320 | /* add bit to the window */
|
---|
2321 | bitbuf |= (y << (WINSIZE - ++bitcpy));
|
---|
2322 |
|
---|
2323 | if (bitcpy == WINSIZE) {
|
---|
2324 | /* ok window is filled so square as required and multiply */
|
---|
2325 | /* square first */
|
---|
2326 | for (x = 0; x < WINSIZE; x++) {
|
---|
2327 | err = mp_sqr(res, res);
|
---|
2328 | if (err != MP_OKAY) {
|
---|
2329 | goto LBL_RES;
|
---|
2330 | }
|
---|
2331 | err = (*redux)(res, P, mp);
|
---|
2332 | if (err != MP_OKAY) {
|
---|
2333 | goto LBL_RES;
|
---|
2334 | }
|
---|
2335 | }
|
---|
2336 |
|
---|
2337 | /* then multiply by 2^bitbuf */
|
---|
2338 | err = mp_mul_2d(res, bitbuf, res);
|
---|
2339 | if (err != MP_OKAY) {
|
---|
2340 | goto LBL_RES;
|
---|
2341 | }
|
---|
2342 | err = mp_mod(res, P, res);
|
---|
2343 | if (err != MP_OKAY) {
|
---|
2344 | goto LBL_RES;
|
---|
2345 | }
|
---|
2346 |
|
---|
2347 | /* empty window and reset */
|
---|
2348 | bitcpy = 0;
|
---|
2349 | bitbuf = 0;
|
---|
2350 | }
|
---|
2351 | }
|
---|
2352 |
|
---|
2353 | /* fixup result if Montgomery reduction is used
|
---|
2354 | * recall that any value in a Montgomery system is
|
---|
2355 | * actually multiplied by R mod n. So we have
|
---|
2356 | * to reduce one more time to cancel out the factor
|
---|
2357 | * of R.
|
---|
2358 | */
|
---|
2359 | err = (*redux)(res, P, mp);
|
---|
2360 | if (err != MP_OKAY) {
|
---|
2361 | goto LBL_RES;
|
---|
2362 | }
|
---|
2363 |
|
---|
2364 | /* swap res with Y */
|
---|
2365 | mp_copy(res, Y);
|
---|
2366 |
|
---|
2367 | LBL_RES:mp_clear (res);
|
---|
2368 | LBL_M:
|
---|
2369 | #ifdef WOLFSSL_SMALL_STACK
|
---|
2370 | XFREE(res, NULL, DYNAMIC_TYPE_TMP_BUFFER);
|
---|
2371 | #endif
|
---|
2372 | return err;
|
---|
2373 | }
|
---|
2374 |
|
---|
2375 | #undef WINSIZE
|
---|
2376 | #endif /* BN_MP_EXPTMOD_BASE_2 */
|
---|
2377 |
|
---|
2378 |
|
---|
2379 | /* setups the montgomery reduction stuff */
|
---|
2380 | int mp_montgomery_setup (mp_int * n, mp_digit * rho)
|
---|
2381 | {
|
---|
2382 | mp_digit x, b;
|
---|
2383 |
|
---|
2384 | /* fast inversion mod 2**k
|
---|
2385 | *
|
---|
2386 | * Based on the fact that
|
---|
2387 | *
|
---|
2388 | * XA = 1 (mod 2**n) => (X(2-XA)) A = 1 (mod 2**2n)
|
---|
2389 | * => 2*X*A - X*X*A*A = 1
|
---|
2390 | * => 2*(1) - (1) = 1
|
---|
2391 | */
|
---|
2392 | b = n->dp[0];
|
---|
2393 |
|
---|
2394 | if ((b & 1) == 0) {
|
---|
2395 | return MP_VAL;
|
---|
2396 | }
|
---|
2397 |
|
---|
2398 | x = (((b + 2) & 4) << 1) + b; /* here x*a==1 mod 2**4 */
|
---|
2399 | x *= 2 - b * x; /* here x*a==1 mod 2**8 */
|
---|
2400 | #if !defined(MP_8BIT)
|
---|
2401 | x *= 2 - b * x; /* here x*a==1 mod 2**16 */
|
---|
2402 | #endif
|
---|
2403 | #if defined(MP_64BIT) || !(defined(MP_8BIT) || defined(MP_16BIT))
|
---|
2404 | x *= 2 - b * x; /* here x*a==1 mod 2**32 */
|
---|
2405 | #endif
|
---|
2406 | #ifdef MP_64BIT
|
---|
2407 | x *= 2 - b * x; /* here x*a==1 mod 2**64 */
|
---|
2408 | #endif
|
---|
2409 |
|
---|
2410 | /* rho = -1/m mod b */
|
---|
2411 | /* TAO, switched mp_word casts to mp_digit to shut up compiler */
|
---|
2412 | *rho = (mp_digit)((((mp_digit)1 << ((mp_digit) DIGIT_BIT)) - x) & MP_MASK);
|
---|
2413 |
|
---|
2414 | return MP_OKAY;
|
---|
2415 | }
|
---|
2416 |
|
---|
2417 |
|
---|
2418 | /* computes xR**-1 == x (mod N) via Montgomery Reduction
|
---|
2419 | *
|
---|
2420 | * This is an optimized implementation of montgomery_reduce
|
---|
2421 | * which uses the comba method to quickly calculate the columns of the
|
---|
2422 | * reduction.
|
---|
2423 | *
|
---|
2424 | * Based on Algorithm 14.32 on pp.601 of HAC.
|
---|
2425 | */
|
---|
2426 | int fast_mp_montgomery_reduce (mp_int * x, mp_int * n, mp_digit rho)
|
---|
2427 | {
|
---|
2428 | int ix, res, olduse;
|
---|
2429 | #ifdef WOLFSSL_SMALL_STACK
|
---|
2430 | mp_word* W; /* uses dynamic memory and slower */
|
---|
2431 | #else
|
---|
2432 | mp_word W[MP_WARRAY];
|
---|
2433 | #endif
|
---|
2434 |
|
---|
2435 | /* get old used count */
|
---|
2436 | olduse = x->used;
|
---|
2437 |
|
---|
2438 | /* grow a as required */
|
---|
2439 | if (x->alloc < n->used + 1) {
|
---|
2440 | if ((res = mp_grow (x, n->used + 1)) != MP_OKAY) {
|
---|
2441 | return res;
|
---|
2442 | }
|
---|
2443 | }
|
---|
2444 |
|
---|
2445 | #ifdef WOLFSSL_SMALL_STACK
|
---|
2446 | W = (mp_word*)XMALLOC(sizeof(mp_word) * MP_WARRAY, NULL, DYNAMIC_TYPE_BIGINT);
|
---|
2447 | if (W == NULL)
|
---|
2448 | return MP_MEM;
|
---|
2449 | #endif
|
---|
2450 |
|
---|
2451 | /* first we have to get the digits of the input into
|
---|
2452 | * an array of double precision words W[...]
|
---|
2453 | */
|
---|
2454 | {
|
---|
2455 | mp_word *_W;
|
---|
2456 | mp_digit *tmpx;
|
---|
2457 |
|
---|
2458 | /* alias for the W[] array */
|
---|
2459 | _W = W;
|
---|
2460 |
|
---|
2461 | /* alias for the digits of x*/
|
---|
2462 | tmpx = x->dp;
|
---|
2463 |
|
---|
2464 | /* copy the digits of a into W[0..a->used-1] */
|
---|
2465 | for (ix = 0; ix < x->used; ix++) {
|
---|
2466 | *_W++ = *tmpx++;
|
---|
2467 | }
|
---|
2468 |
|
---|
2469 | /* zero the high words of W[a->used..m->used*2] */
|
---|
2470 | for (; ix < n->used * 2 + 1; ix++) {
|
---|
2471 | *_W++ = 0;
|
---|
2472 | }
|
---|
2473 | }
|
---|
2474 |
|
---|
2475 | /* now we proceed to zero successive digits
|
---|
2476 | * from the least significant upwards
|
---|
2477 | */
|
---|
2478 | for (ix = 0; ix < n->used; ix++) {
|
---|
2479 | /* mu = ai * m' mod b
|
---|
2480 | *
|
---|
2481 | * We avoid a double precision multiplication (which isn't required)
|
---|
2482 | * by casting the value down to a mp_digit. Note this requires
|
---|
2483 | * that W[ix-1] have the carry cleared (see after the inner loop)
|
---|
2484 | */
|
---|
2485 | mp_digit mu;
|
---|
2486 | mu = (mp_digit) (((W[ix] & MP_MASK) * rho) & MP_MASK);
|
---|
2487 |
|
---|
2488 | /* a = a + mu * m * b**i
|
---|
2489 | *
|
---|
2490 | * This is computed in place and on the fly. The multiplication
|
---|
2491 | * by b**i is handled by offsetting which columns the results
|
---|
2492 | * are added to.
|
---|
2493 | *
|
---|
2494 | * Note the comba method normally doesn't handle carries in the
|
---|
2495 | * inner loop In this case we fix the carry from the previous
|
---|
2496 | * column since the Montgomery reduction requires digits of the
|
---|
2497 | * result (so far) [see above] to work. This is
|
---|
2498 | * handled by fixing up one carry after the inner loop. The
|
---|
2499 | * carry fixups are done in order so after these loops the
|
---|
2500 | * first m->used words of W[] have the carries fixed
|
---|
2501 | */
|
---|
2502 | {
|
---|
2503 | int iy;
|
---|
2504 | mp_digit *tmpn;
|
---|
2505 | mp_word *_W;
|
---|
2506 |
|
---|
2507 | /* alias for the digits of the modulus */
|
---|
2508 | tmpn = n->dp;
|
---|
2509 |
|
---|
2510 | /* Alias for the columns set by an offset of ix */
|
---|
2511 | _W = W + ix;
|
---|
2512 |
|
---|
2513 | /* inner loop */
|
---|
2514 | for (iy = 0; iy < n->used; iy++) {
|
---|
2515 | *_W++ += ((mp_word)mu) * ((mp_word)*tmpn++);
|
---|
2516 | }
|
---|
2517 | }
|
---|
2518 |
|
---|
2519 | /* now fix carry for next digit, W[ix+1] */
|
---|
2520 | W[ix + 1] += W[ix] >> ((mp_word) DIGIT_BIT);
|
---|
2521 | }
|
---|
2522 |
|
---|
2523 | /* now we have to propagate the carries and
|
---|
2524 | * shift the words downward [all those least
|
---|
2525 | * significant digits we zeroed].
|
---|
2526 | */
|
---|
2527 | {
|
---|
2528 | mp_digit *tmpx;
|
---|
2529 | mp_word *_W, *_W1;
|
---|
2530 |
|
---|
2531 | /* nox fix rest of carries */
|
---|
2532 |
|
---|
2533 | /* alias for current word */
|
---|
2534 | _W1 = W + ix;
|
---|
2535 |
|
---|
2536 | /* alias for next word, where the carry goes */
|
---|
2537 | _W = W + ++ix;
|
---|
2538 |
|
---|
2539 | for (; ix <= n->used * 2 + 1; ix++) {
|
---|
2540 | *_W++ += *_W1++ >> ((mp_word) DIGIT_BIT);
|
---|
2541 | }
|
---|
2542 |
|
---|
2543 | /* copy out, A = A/b**n
|
---|
2544 | *
|
---|
2545 | * The result is A/b**n but instead of converting from an
|
---|
2546 | * array of mp_word to mp_digit than calling mp_rshd
|
---|
2547 | * we just copy them in the right order
|
---|
2548 | */
|
---|
2549 |
|
---|
2550 | /* alias for destination word */
|
---|
2551 | tmpx = x->dp;
|
---|
2552 |
|
---|
2553 | /* alias for shifted double precision result */
|
---|
2554 | _W = W + n->used;
|
---|
2555 |
|
---|
2556 | for (ix = 0; ix < n->used + 1; ix++) {
|
---|
2557 | *tmpx++ = (mp_digit)(*_W++ & ((mp_word) MP_MASK));
|
---|
2558 | }
|
---|
2559 |
|
---|
2560 | /* zero olduse digits, if the input a was larger than
|
---|
2561 | * m->used+1 we'll have to clear the digits
|
---|
2562 | */
|
---|
2563 | for (; ix < olduse; ix++) {
|
---|
2564 | *tmpx++ = 0;
|
---|
2565 | }
|
---|
2566 | }
|
---|
2567 |
|
---|
2568 | /* set the max used and clamp */
|
---|
2569 | x->used = n->used + 1;
|
---|
2570 | mp_clamp (x);
|
---|
2571 |
|
---|
2572 | #ifdef WOLFSSL_SMALL_STACK
|
---|
2573 | XFREE(W, NULL, DYNAMIC_TYPE_BIGINT);
|
---|
2574 | #endif
|
---|
2575 |
|
---|
2576 | /* if A >= m then A = A - m */
|
---|
2577 | if (mp_cmp_mag (x, n) != MP_LT) {
|
---|
2578 | return s_mp_sub (x, n, x);
|
---|
2579 | }
|
---|
2580 | return MP_OKAY;
|
---|
2581 | }
|
---|
2582 |
|
---|
2583 |
|
---|
2584 | /* computes xR**-1 == x (mod N) via Montgomery Reduction */
|
---|
2585 | int mp_montgomery_reduce (mp_int * x, mp_int * n, mp_digit rho)
|
---|
2586 | {
|
---|
2587 | int ix, res, digs;
|
---|
2588 | mp_digit mu;
|
---|
2589 |
|
---|
2590 | /* can the fast reduction [comba] method be used?
|
---|
2591 | *
|
---|
2592 | * Note that unlike in mul you're safely allowed *less*
|
---|
2593 | * than the available columns [255 per default] since carries
|
---|
2594 | * are fixed up in the inner loop.
|
---|
2595 | */
|
---|
2596 | digs = n->used * 2 + 1;
|
---|
2597 | if ((digs < (int)MP_WARRAY) &&
|
---|
2598 | n->used <
|
---|
2599 | (1 << ((CHAR_BIT * sizeof (mp_word)) - (2 * DIGIT_BIT)))) {
|
---|
2600 | return fast_mp_montgomery_reduce (x, n, rho);
|
---|
2601 | }
|
---|
2602 |
|
---|
2603 | /* grow the input as required */
|
---|
2604 | if (x->alloc < digs) {
|
---|
2605 | if ((res = mp_grow (x, digs)) != MP_OKAY) {
|
---|
2606 | return res;
|
---|
2607 | }
|
---|
2608 | }
|
---|
2609 | x->used = digs;
|
---|
2610 |
|
---|
2611 | for (ix = 0; ix < n->used; ix++) {
|
---|
2612 | /* mu = ai * rho mod b
|
---|
2613 | *
|
---|
2614 | * The value of rho must be precalculated via
|
---|
2615 | * montgomery_setup() such that
|
---|
2616 | * it equals -1/n0 mod b this allows the
|
---|
2617 | * following inner loop to reduce the
|
---|
2618 | * input one digit at a time
|
---|
2619 | */
|
---|
2620 | mu = (mp_digit) (((mp_word)x->dp[ix]) * ((mp_word)rho) & MP_MASK);
|
---|
2621 |
|
---|
2622 | /* a = a + mu * m * b**i */
|
---|
2623 | {
|
---|
2624 | int iy;
|
---|
2625 | mp_digit *tmpn, *tmpx, u;
|
---|
2626 | mp_word r;
|
---|
2627 |
|
---|
2628 | /* alias for digits of the modulus */
|
---|
2629 | tmpn = n->dp;
|
---|
2630 |
|
---|
2631 | /* alias for the digits of x [the input] */
|
---|
2632 | tmpx = x->dp + ix;
|
---|
2633 |
|
---|
2634 | /* set the carry to zero */
|
---|
2635 | u = 0;
|
---|
2636 |
|
---|
2637 | /* Multiply and add in place */
|
---|
2638 | for (iy = 0; iy < n->used; iy++) {
|
---|
2639 | /* compute product and sum */
|
---|
2640 | r = ((mp_word)mu) * ((mp_word)*tmpn++) +
|
---|
2641 | ((mp_word) u) + ((mp_word) * tmpx);
|
---|
2642 |
|
---|
2643 | /* get carry */
|
---|
2644 | u = (mp_digit)(r >> ((mp_word) DIGIT_BIT));
|
---|
2645 |
|
---|
2646 | /* fix digit */
|
---|
2647 | *tmpx++ = (mp_digit)(r & ((mp_word) MP_MASK));
|
---|
2648 | }
|
---|
2649 | /* At this point the ix'th digit of x should be zero */
|
---|
2650 |
|
---|
2651 |
|
---|
2652 | /* propagate carries upwards as required*/
|
---|
2653 | while (u) {
|
---|
2654 | *tmpx += u;
|
---|
2655 | u = *tmpx >> DIGIT_BIT;
|
---|
2656 | *tmpx++ &= MP_MASK;
|
---|
2657 | }
|
---|
2658 | }
|
---|
2659 | }
|
---|
2660 |
|
---|
2661 | /* at this point the n.used'th least
|
---|
2662 | * significant digits of x are all zero
|
---|
2663 | * which means we can shift x to the
|
---|
2664 | * right by n.used digits and the
|
---|
2665 | * residue is unchanged.
|
---|
2666 | */
|
---|
2667 |
|
---|
2668 | /* x = x/b**n.used */
|
---|
2669 | mp_clamp(x);
|
---|
2670 | mp_rshd (x, n->used);
|
---|
2671 |
|
---|
2672 | /* if x >= n then x = x - n */
|
---|
2673 | if (mp_cmp_mag (x, n) != MP_LT) {
|
---|
2674 | return s_mp_sub (x, n, x);
|
---|
2675 | }
|
---|
2676 |
|
---|
2677 | return MP_OKAY;
|
---|
2678 | }
|
---|
2679 |
|
---|
2680 |
|
---|
2681 | /* determines the setup value */
|
---|
2682 | void mp_dr_setup(mp_int *a, mp_digit *d)
|
---|
2683 | {
|
---|
2684 | /* the casts are required if DIGIT_BIT is one less than
|
---|
2685 | * the number of bits in a mp_digit [e.g. DIGIT_BIT==31]
|
---|
2686 | */
|
---|
2687 | *d = (mp_digit)((((mp_word)1) << ((mp_word)DIGIT_BIT)) -
|
---|
2688 | ((mp_word)a->dp[0]));
|
---|
2689 | }
|
---|
2690 |
|
---|
2691 |
|
---|
2692 | /* reduce "x" in place modulo "n" using the Diminished Radix algorithm.
|
---|
2693 | *
|
---|
2694 | * Based on algorithm from the paper
|
---|
2695 | *
|
---|
2696 | * "Generating Efficient Primes for Discrete Log Cryptosystems"
|
---|
2697 | * Chae Hoon Lim, Pil Joong Lee,
|
---|
2698 | * POSTECH Information Research Laboratories
|
---|
2699 | *
|
---|
2700 | * The modulus must be of a special format [see manual]
|
---|
2701 | *
|
---|
2702 | * Has been modified to use algorithm 7.10 from the LTM book instead
|
---|
2703 | *
|
---|
2704 | * Input x must be in the range 0 <= x <= (n-1)**2
|
---|
2705 | */
|
---|
2706 | int mp_dr_reduce (mp_int * x, mp_int * n, mp_digit k)
|
---|
2707 | {
|
---|
2708 | int err, i, m;
|
---|
2709 | mp_word r;
|
---|
2710 | mp_digit mu, *tmpx1, *tmpx2;
|
---|
2711 |
|
---|
2712 | /* m = digits in modulus */
|
---|
2713 | m = n->used;
|
---|
2714 |
|
---|
2715 | /* ensure that "x" has at least 2m digits */
|
---|
2716 | if (x->alloc < m + m) {
|
---|
2717 | if ((err = mp_grow (x, m + m)) != MP_OKAY) {
|
---|
2718 | return err;
|
---|
2719 | }
|
---|
2720 | }
|
---|
2721 |
|
---|
2722 | /* top of loop, this is where the code resumes if
|
---|
2723 | * another reduction pass is required.
|
---|
2724 | */
|
---|
2725 | top:
|
---|
2726 | /* aliases for digits */
|
---|
2727 | /* alias for lower half of x */
|
---|
2728 | tmpx1 = x->dp;
|
---|
2729 |
|
---|
2730 | /* alias for upper half of x, or x/B**m */
|
---|
2731 | tmpx2 = x->dp + m;
|
---|
2732 |
|
---|
2733 | /* set carry to zero */
|
---|
2734 | mu = 0;
|
---|
2735 |
|
---|
2736 | /* compute (x mod B**m) + k * [x/B**m] inline and inplace */
|
---|
2737 | for (i = 0; i < m; i++) {
|
---|
2738 | r = ((mp_word)*tmpx2++) * ((mp_word)k) + *tmpx1 + mu;
|
---|
2739 | *tmpx1++ = (mp_digit)(r & MP_MASK);
|
---|
2740 | mu = (mp_digit)(r >> ((mp_word)DIGIT_BIT));
|
---|
2741 | }
|
---|
2742 |
|
---|
2743 | /* set final carry */
|
---|
2744 | *tmpx1++ = mu;
|
---|
2745 |
|
---|
2746 | /* zero words above m */
|
---|
2747 | for (i = m + 1; i < x->used; i++) {
|
---|
2748 | *tmpx1++ = 0;
|
---|
2749 | }
|
---|
2750 |
|
---|
2751 | /* clamp, sub and return */
|
---|
2752 | mp_clamp (x);
|
---|
2753 |
|
---|
2754 | /* if x >= n then subtract and reduce again
|
---|
2755 | * Each successive "recursion" makes the input smaller and smaller.
|
---|
2756 | */
|
---|
2757 | if (mp_cmp_mag (x, n) != MP_LT) {
|
---|
2758 | if ((err = s_mp_sub(x, n, x)) != MP_OKAY) {
|
---|
2759 | return err;
|
---|
2760 | }
|
---|
2761 | goto top;
|
---|
2762 | }
|
---|
2763 | return MP_OKAY;
|
---|
2764 | }
|
---|
2765 |
|
---|
2766 |
|
---|
2767 | /* reduces a modulo n where n is of the form 2**p - d */
|
---|
2768 | int mp_reduce_2k(mp_int *a, mp_int *n, mp_digit d)
|
---|
2769 | {
|
---|
2770 | mp_int q;
|
---|
2771 | int p, res;
|
---|
2772 |
|
---|
2773 | if ((res = mp_init(&q)) != MP_OKAY) {
|
---|
2774 | return res;
|
---|
2775 | }
|
---|
2776 |
|
---|
2777 | p = mp_count_bits(n);
|
---|
2778 | top:
|
---|
2779 | /* q = a/2**p, a = a mod 2**p */
|
---|
2780 | if ((res = mp_div_2d(a, p, &q, a)) != MP_OKAY) {
|
---|
2781 | goto ERR;
|
---|
2782 | }
|
---|
2783 |
|
---|
2784 | if (d != 1) {
|
---|
2785 | /* q = q * d */
|
---|
2786 | if ((res = mp_mul_d(&q, d, &q)) != MP_OKAY) {
|
---|
2787 | goto ERR;
|
---|
2788 | }
|
---|
2789 | }
|
---|
2790 |
|
---|
2791 | /* a = a + q */
|
---|
2792 | if ((res = s_mp_add(a, &q, a)) != MP_OKAY) {
|
---|
2793 | goto ERR;
|
---|
2794 | }
|
---|
2795 |
|
---|
2796 | if (mp_cmp_mag(a, n) != MP_LT) {
|
---|
2797 | if ((res = s_mp_sub(a, n, a)) != MP_OKAY) {
|
---|
2798 | goto ERR;
|
---|
2799 | }
|
---|
2800 | goto top;
|
---|
2801 | }
|
---|
2802 |
|
---|
2803 | ERR:
|
---|
2804 | mp_clear(&q);
|
---|
2805 | return res;
|
---|
2806 | }
|
---|
2807 |
|
---|
2808 |
|
---|
2809 | /* determines the setup value */
|
---|
2810 | int mp_reduce_2k_setup(mp_int *a, mp_digit *d)
|
---|
2811 | {
|
---|
2812 | int res, p;
|
---|
2813 | mp_int tmp;
|
---|
2814 |
|
---|
2815 | if ((res = mp_init(&tmp)) != MP_OKAY) {
|
---|
2816 | return res;
|
---|
2817 | }
|
---|
2818 |
|
---|
2819 | p = mp_count_bits(a);
|
---|
2820 | if ((res = mp_2expt(&tmp, p)) != MP_OKAY) {
|
---|
2821 | mp_clear(&tmp);
|
---|
2822 | return res;
|
---|
2823 | }
|
---|
2824 |
|
---|
2825 | if ((res = s_mp_sub(&tmp, a, &tmp)) != MP_OKAY) {
|
---|
2826 | mp_clear(&tmp);
|
---|
2827 | return res;
|
---|
2828 | }
|
---|
2829 |
|
---|
2830 | *d = tmp.dp[0];
|
---|
2831 | mp_clear(&tmp);
|
---|
2832 | return MP_OKAY;
|
---|
2833 | }
|
---|
2834 |
|
---|
2835 |
|
---|
2836 | /* set the b bit of a */
|
---|
2837 | int mp_set_bit (mp_int * a, int b)
|
---|
2838 | {
|
---|
2839 | int i = b / DIGIT_BIT, res;
|
---|
2840 |
|
---|
2841 | /*
|
---|
2842 | * Require:
|
---|
2843 | * bit index b >= 0
|
---|
2844 | * a->alloc == a->used == 0 if a->dp == NULL
|
---|
2845 | */
|
---|
2846 | if (b < 0 || (a->dp == NULL && (a->alloc != 0 || a->used != 0)))
|
---|
2847 | return MP_VAL;
|
---|
2848 |
|
---|
2849 | if (a->dp == NULL || a->used < (int)(i + 1)) {
|
---|
2850 | /* grow a to accommodate the single bit */
|
---|
2851 | if ((res = mp_grow (a, i + 1)) != MP_OKAY) {
|
---|
2852 | return res;
|
---|
2853 | }
|
---|
2854 |
|
---|
2855 | /* set the used count of where the bit will go */
|
---|
2856 | a->used = (int)(i + 1);
|
---|
2857 | }
|
---|
2858 |
|
---|
2859 | /* put the single bit in its place */
|
---|
2860 | a->dp[i] |= ((mp_digit)1) << (b % DIGIT_BIT);
|
---|
2861 |
|
---|
2862 | return MP_OKAY;
|
---|
2863 | }
|
---|
2864 |
|
---|
2865 | /* computes a = 2**b
|
---|
2866 | *
|
---|
2867 | * Simple algorithm which zeros the int, set the required bit
|
---|
2868 | */
|
---|
2869 | int mp_2expt (mp_int * a, int b)
|
---|
2870 | {
|
---|
2871 | /* zero a as per default */
|
---|
2872 | mp_zero (a);
|
---|
2873 |
|
---|
2874 | return mp_set_bit(a, b);
|
---|
2875 | }
|
---|
2876 |
|
---|
2877 | /* multiply by a digit */
|
---|
2878 | int mp_mul_d (mp_int * a, mp_digit b, mp_int * c)
|
---|
2879 | {
|
---|
2880 | mp_digit u, *tmpa, *tmpc;
|
---|
2881 | mp_word r;
|
---|
2882 | int ix, res, olduse;
|
---|
2883 |
|
---|
2884 | /* make sure c is big enough to hold a*b */
|
---|
2885 | if (c->alloc < a->used + 1) {
|
---|
2886 | if ((res = mp_grow (c, a->used + 1)) != MP_OKAY) {
|
---|
2887 | return res;
|
---|
2888 | }
|
---|
2889 | }
|
---|
2890 |
|
---|
2891 | /* get the original destinations used count */
|
---|
2892 | olduse = c->used;
|
---|
2893 |
|
---|
2894 | /* set the sign */
|
---|
2895 | c->sign = a->sign;
|
---|
2896 |
|
---|
2897 | /* alias for a->dp [source] */
|
---|
2898 | tmpa = a->dp;
|
---|
2899 |
|
---|
2900 | /* alias for c->dp [dest] */
|
---|
2901 | tmpc = c->dp;
|
---|
2902 |
|
---|
2903 | /* zero carry */
|
---|
2904 | u = 0;
|
---|
2905 |
|
---|
2906 | /* compute columns */
|
---|
2907 | for (ix = 0; ix < a->used; ix++) {
|
---|
2908 | /* compute product and carry sum for this term */
|
---|
2909 | r = ((mp_word) u) + ((mp_word)*tmpa++) * ((mp_word)b);
|
---|
2910 |
|
---|
2911 | /* mask off higher bits to get a single digit */
|
---|
2912 | *tmpc++ = (mp_digit) (r & ((mp_word) MP_MASK));
|
---|
2913 |
|
---|
2914 | /* send carry into next iteration */
|
---|
2915 | u = (mp_digit) (r >> ((mp_word) DIGIT_BIT));
|
---|
2916 | }
|
---|
2917 |
|
---|
2918 | /* store final carry [if any] and increment ix offset */
|
---|
2919 | *tmpc++ = u;
|
---|
2920 | ++ix;
|
---|
2921 |
|
---|
2922 | /* now zero digits above the top */
|
---|
2923 | while (ix++ < olduse) {
|
---|
2924 | *tmpc++ = 0;
|
---|
2925 | }
|
---|
2926 |
|
---|
2927 | /* set used count */
|
---|
2928 | c->used = a->used + 1;
|
---|
2929 | mp_clamp(c);
|
---|
2930 |
|
---|
2931 | return MP_OKAY;
|
---|
2932 | }
|
---|
2933 |
|
---|
2934 |
|
---|
2935 | /* d = a * b (mod c) */
|
---|
2936 | #if defined(FREESCALE_LTC_TFM)
|
---|
2937 | int wolfcrypt_mp_mulmod(mp_int *a, mp_int *b, mp_int *c, mp_int *d)
|
---|
2938 | #else
|
---|
2939 | int mp_mulmod (mp_int * a, mp_int * b, mp_int * c, mp_int * d)
|
---|
2940 | #endif
|
---|
2941 | {
|
---|
2942 | int res;
|
---|
2943 | mp_int t;
|
---|
2944 |
|
---|
2945 | if ((res = mp_init_size (&t, c->used)) != MP_OKAY) {
|
---|
2946 | return res;
|
---|
2947 | }
|
---|
2948 |
|
---|
2949 | res = mp_mul (a, b, &t);
|
---|
2950 | if (res == MP_OKAY) {
|
---|
2951 | res = mp_mod (&t, c, d);
|
---|
2952 | }
|
---|
2953 |
|
---|
2954 | mp_clear (&t);
|
---|
2955 | return res;
|
---|
2956 | }
|
---|
2957 |
|
---|
2958 |
|
---|
2959 | /* d = a - b (mod c) */
|
---|
2960 | int mp_submod(mp_int* a, mp_int* b, mp_int* c, mp_int* d)
|
---|
2961 | {
|
---|
2962 | int res;
|
---|
2963 | mp_int t;
|
---|
2964 |
|
---|
2965 | if ((res = mp_init (&t)) != MP_OKAY) {
|
---|
2966 | return res;
|
---|
2967 | }
|
---|
2968 |
|
---|
2969 | res = mp_sub (a, b, &t);
|
---|
2970 | if (res == MP_OKAY) {
|
---|
2971 | res = mp_mod (&t, c, d);
|
---|
2972 | }
|
---|
2973 |
|
---|
2974 | mp_clear (&t);
|
---|
2975 |
|
---|
2976 | return res;
|
---|
2977 | }
|
---|
2978 |
|
---|
2979 | /* d = a + b (mod c) */
|
---|
2980 | int mp_addmod(mp_int* a, mp_int* b, mp_int* c, mp_int* d)
|
---|
2981 | {
|
---|
2982 | int res;
|
---|
2983 | mp_int t;
|
---|
2984 |
|
---|
2985 | if ((res = mp_init (&t)) != MP_OKAY) {
|
---|
2986 | return res;
|
---|
2987 | }
|
---|
2988 |
|
---|
2989 | res = mp_add (a, b, &t);
|
---|
2990 | if (res == MP_OKAY) {
|
---|
2991 | res = mp_mod (&t, c, d);
|
---|
2992 | }
|
---|
2993 |
|
---|
2994 | mp_clear (&t);
|
---|
2995 |
|
---|
2996 | return res;
|
---|
2997 | }
|
---|
2998 |
|
---|
2999 | /* computes b = a*a */
|
---|
3000 | int mp_sqr (mp_int * a, mp_int * b)
|
---|
3001 | {
|
---|
3002 | int res;
|
---|
3003 |
|
---|
3004 | {
|
---|
3005 | #ifdef BN_FAST_S_MP_SQR_C
|
---|
3006 | /* can we use the fast comba multiplier? */
|
---|
3007 | if ((a->used * 2 + 1) < (int)MP_WARRAY &&
|
---|
3008 | a->used <
|
---|
3009 | (1 << (sizeof(mp_word) * CHAR_BIT - 2*DIGIT_BIT - 1))) {
|
---|
3010 | res = fast_s_mp_sqr (a, b);
|
---|
3011 | } else
|
---|
3012 | #endif
|
---|
3013 | #ifdef BN_S_MP_SQR_C
|
---|
3014 | res = s_mp_sqr (a, b);
|
---|
3015 | #else
|
---|
3016 | res = MP_VAL;
|
---|
3017 | #endif
|
---|
3018 | }
|
---|
3019 | b->sign = MP_ZPOS;
|
---|
3020 | return res;
|
---|
3021 | }
|
---|
3022 |
|
---|
3023 |
|
---|
3024 | /* high level multiplication (handles sign) */
|
---|
3025 | #if defined(FREESCALE_LTC_TFM)
|
---|
3026 | int wolfcrypt_mp_mul(mp_int *a, mp_int *b, mp_int *c)
|
---|
3027 | #else
|
---|
3028 | int mp_mul (mp_int * a, mp_int * b, mp_int * c)
|
---|
3029 | #endif
|
---|
3030 | {
|
---|
3031 | int res, neg;
|
---|
3032 | neg = (a->sign == b->sign) ? MP_ZPOS : MP_NEG;
|
---|
3033 |
|
---|
3034 | {
|
---|
3035 | #ifdef BN_FAST_S_MP_MUL_DIGS_C
|
---|
3036 | /* can we use the fast multiplier?
|
---|
3037 | *
|
---|
3038 | * The fast multiplier can be used if the output will
|
---|
3039 | * have less than MP_WARRAY digits and the number of
|
---|
3040 | * digits won't affect carry propagation
|
---|
3041 | */
|
---|
3042 | int digs = a->used + b->used + 1;
|
---|
3043 |
|
---|
3044 | if ((digs < (int)MP_WARRAY) &&
|
---|
3045 | MIN(a->used, b->used) <=
|
---|
3046 | (1 << ((CHAR_BIT * sizeof (mp_word)) - (2 * DIGIT_BIT)))) {
|
---|
3047 | res = fast_s_mp_mul_digs (a, b, c, digs);
|
---|
3048 | } else
|
---|
3049 | #endif
|
---|
3050 | #ifdef BN_S_MP_MUL_DIGS_C
|
---|
3051 | res = s_mp_mul (a, b, c); /* uses s_mp_mul_digs */
|
---|
3052 | #else
|
---|
3053 | res = MP_VAL;
|
---|
3054 | #endif
|
---|
3055 |
|
---|
3056 | }
|
---|
3057 | c->sign = (c->used > 0) ? neg : MP_ZPOS;
|
---|
3058 | return res;
|
---|
3059 | }
|
---|
3060 |
|
---|
3061 |
|
---|
3062 | /* b = a*2 */
|
---|
3063 | int mp_mul_2(mp_int * a, mp_int * b)
|
---|
3064 | {
|
---|
3065 | int x, res, oldused;
|
---|
3066 |
|
---|
3067 | /* grow to accommodate result */
|
---|
3068 | if (b->alloc < a->used + 1) {
|
---|
3069 | if ((res = mp_grow (b, a->used + 1)) != MP_OKAY) {
|
---|
3070 | return res;
|
---|
3071 | }
|
---|
3072 | }
|
---|
3073 |
|
---|
3074 | oldused = b->used;
|
---|
3075 | b->used = a->used;
|
---|
3076 |
|
---|
3077 | {
|
---|
3078 | mp_digit r, rr, *tmpa, *tmpb;
|
---|
3079 |
|
---|
3080 | /* alias for source */
|
---|
3081 | tmpa = a->dp;
|
---|
3082 |
|
---|
3083 | /* alias for dest */
|
---|
3084 | tmpb = b->dp;
|
---|
3085 |
|
---|
3086 | /* carry */
|
---|
3087 | r = 0;
|
---|
3088 | for (x = 0; x < a->used; x++) {
|
---|
3089 |
|
---|
3090 | /* get what will be the *next* carry bit from the
|
---|
3091 | * MSB of the current digit
|
---|
3092 | */
|
---|
3093 | rr = *tmpa >> ((mp_digit)(DIGIT_BIT - 1));
|
---|
3094 |
|
---|
3095 | /* now shift up this digit, add in the carry [from the previous] */
|
---|
3096 | *tmpb++ = (mp_digit)(((*tmpa++ << ((mp_digit)1)) | r) & MP_MASK);
|
---|
3097 |
|
---|
3098 | /* copy the carry that would be from the source
|
---|
3099 | * digit into the next iteration
|
---|
3100 | */
|
---|
3101 | r = rr;
|
---|
3102 | }
|
---|
3103 |
|
---|
3104 | /* new leading digit? */
|
---|
3105 | if (r != 0) {
|
---|
3106 | /* add a MSB which is always 1 at this point */
|
---|
3107 | *tmpb = 1;
|
---|
3108 | ++(b->used);
|
---|
3109 | }
|
---|
3110 |
|
---|
3111 | /* now zero any excess digits on the destination
|
---|
3112 | * that we didn't write to
|
---|
3113 | */
|
---|
3114 | tmpb = b->dp + b->used;
|
---|
3115 | for (x = b->used; x < oldused; x++) {
|
---|
3116 | *tmpb++ = 0;
|
---|
3117 | }
|
---|
3118 | }
|
---|
3119 | b->sign = a->sign;
|
---|
3120 | return MP_OKAY;
|
---|
3121 | }
|
---|
3122 |
|
---|
3123 |
|
---|
3124 | /* divide by three (based on routine from MPI and the GMP manual) */
|
---|
3125 | int mp_div_3 (mp_int * a, mp_int *c, mp_digit * d)
|
---|
3126 | {
|
---|
3127 | mp_int q;
|
---|
3128 | mp_word w, t;
|
---|
3129 | mp_digit b;
|
---|
3130 | int res, ix;
|
---|
3131 |
|
---|
3132 | /* b = 2**DIGIT_BIT / 3 */
|
---|
3133 | b = (mp_digit) ( (((mp_word)1) << ((mp_word)DIGIT_BIT)) / ((mp_word)3) );
|
---|
3134 |
|
---|
3135 | if ((res = mp_init_size(&q, a->used)) != MP_OKAY) {
|
---|
3136 | return res;
|
---|
3137 | }
|
---|
3138 |
|
---|
3139 | q.used = a->used;
|
---|
3140 | q.sign = a->sign;
|
---|
3141 | w = 0;
|
---|
3142 | for (ix = a->used - 1; ix >= 0; ix--) {
|
---|
3143 | w = (w << ((mp_word)DIGIT_BIT)) | ((mp_word)a->dp[ix]);
|
---|
3144 |
|
---|
3145 | if (w >= 3) {
|
---|
3146 | /* multiply w by [1/3] */
|
---|
3147 | t = (w * ((mp_word)b)) >> ((mp_word)DIGIT_BIT);
|
---|
3148 |
|
---|
3149 | /* now subtract 3 * [w/3] from w, to get the remainder */
|
---|
3150 | w -= t+t+t;
|
---|
3151 |
|
---|
3152 | /* fixup the remainder as required since
|
---|
3153 | * the optimization is not exact.
|
---|
3154 | */
|
---|
3155 | while (w >= 3) {
|
---|
3156 | t += 1;
|
---|
3157 | w -= 3;
|
---|
3158 | }
|
---|
3159 | } else {
|
---|
3160 | t = 0;
|
---|
3161 | }
|
---|
3162 | q.dp[ix] = (mp_digit)t;
|
---|
3163 | }
|
---|
3164 |
|
---|
3165 | /* [optional] store the remainder */
|
---|
3166 | if (d != NULL) {
|
---|
3167 | *d = (mp_digit)w;
|
---|
3168 | }
|
---|
3169 |
|
---|
3170 | /* [optional] store the quotient */
|
---|
3171 | if (c != NULL) {
|
---|
3172 | mp_clamp(&q);
|
---|
3173 | mp_exch(&q, c);
|
---|
3174 | }
|
---|
3175 | mp_clear(&q);
|
---|
3176 |
|
---|
3177 | return res;
|
---|
3178 | }
|
---|
3179 |
|
---|
3180 |
|
---|
3181 | /* init an mp_init for a given size */
|
---|
3182 | int mp_init_size (mp_int * a, int size)
|
---|
3183 | {
|
---|
3184 | int x;
|
---|
3185 |
|
---|
3186 | /* pad size so there are always extra digits */
|
---|
3187 | size += (MP_PREC * 2) - (size % MP_PREC);
|
---|
3188 |
|
---|
3189 | /* alloc mem */
|
---|
3190 | a->dp = OPT_CAST(mp_digit) XMALLOC (sizeof (mp_digit) * size, NULL,
|
---|
3191 | DYNAMIC_TYPE_BIGINT);
|
---|
3192 | if (a->dp == NULL) {
|
---|
3193 | return MP_MEM;
|
---|
3194 | }
|
---|
3195 |
|
---|
3196 | /* set the members */
|
---|
3197 | a->used = 0;
|
---|
3198 | a->alloc = size;
|
---|
3199 | a->sign = MP_ZPOS;
|
---|
3200 | #ifdef HAVE_WOLF_BIGINT
|
---|
3201 | wc_bigint_init(&a->raw);
|
---|
3202 | #endif
|
---|
3203 |
|
---|
3204 | /* zero the digits */
|
---|
3205 | for (x = 0; x < size; x++) {
|
---|
3206 | a->dp[x] = 0;
|
---|
3207 | }
|
---|
3208 |
|
---|
3209 | return MP_OKAY;
|
---|
3210 | }
|
---|
3211 |
|
---|
3212 |
|
---|
3213 | /* the jist of squaring...
|
---|
3214 | * you do like mult except the offset of the tmpx [one that
|
---|
3215 | * starts closer to zero] can't equal the offset of tmpy.
|
---|
3216 | * So basically you set up iy like before then you min it with
|
---|
3217 | * (ty-tx) so that it never happens. You double all those
|
---|
3218 | * you add in the inner loop
|
---|
3219 |
|
---|
3220 | After that loop you do the squares and add them in.
|
---|
3221 | */
|
---|
3222 |
|
---|
3223 | int fast_s_mp_sqr (mp_int * a, mp_int * b)
|
---|
3224 | {
|
---|
3225 | int olduse, res, pa, ix, iz;
|
---|
3226 | #ifdef WOLFSSL_SMALL_STACK
|
---|
3227 | mp_digit* W; /* uses dynamic memory and slower */
|
---|
3228 | #else
|
---|
3229 | mp_digit W[MP_WARRAY];
|
---|
3230 | #endif
|
---|
3231 | mp_digit *tmpx;
|
---|
3232 | mp_word W1;
|
---|
3233 |
|
---|
3234 | /* grow the destination as required */
|
---|
3235 | pa = a->used + a->used;
|
---|
3236 | if (b->alloc < pa) {
|
---|
3237 | if ((res = mp_grow (b, pa)) != MP_OKAY) {
|
---|
3238 | return res;
|
---|
3239 | }
|
---|
3240 | }
|
---|
3241 |
|
---|
3242 | if (pa > (int)MP_WARRAY)
|
---|
3243 | return MP_RANGE; /* TAO range check */
|
---|
3244 |
|
---|
3245 | #ifdef WOLFSSL_SMALL_STACK
|
---|
3246 | W = (mp_digit*)XMALLOC(sizeof(mp_digit) * MP_WARRAY, NULL, DYNAMIC_TYPE_BIGINT);
|
---|
3247 | if (W == NULL)
|
---|
3248 | return MP_MEM;
|
---|
3249 | #endif
|
---|
3250 |
|
---|
3251 | /* number of output digits to produce */
|
---|
3252 | W1 = 0;
|
---|
3253 | for (ix = 0; ix < pa; ix++) {
|
---|
3254 | int tx, ty, iy;
|
---|
3255 | mp_word _W;
|
---|
3256 | mp_digit *tmpy;
|
---|
3257 |
|
---|
3258 | /* clear counter */
|
---|
3259 | _W = 0;
|
---|
3260 |
|
---|
3261 | /* get offsets into the two bignums */
|
---|
3262 | ty = MIN(a->used-1, ix);
|
---|
3263 | tx = ix - ty;
|
---|
3264 |
|
---|
3265 | /* setup temp aliases */
|
---|
3266 | tmpx = a->dp + tx;
|
---|
3267 | tmpy = a->dp + ty;
|
---|
3268 |
|
---|
3269 | /* this is the number of times the loop will iterate, essentially
|
---|
3270 | while (tx++ < a->used && ty-- >= 0) { ... }
|
---|
3271 | */
|
---|
3272 | iy = MIN(a->used-tx, ty+1);
|
---|
3273 |
|
---|
3274 | /* now for squaring tx can never equal ty
|
---|
3275 | * we halve the distance since they approach at a rate of 2x
|
---|
3276 | * and we have to round because odd cases need to be executed
|
---|
3277 | */
|
---|
3278 | iy = MIN(iy, (ty-tx+1)>>1);
|
---|
3279 |
|
---|
3280 | /* execute loop */
|
---|
3281 | for (iz = 0; iz < iy; iz++) {
|
---|
3282 | _W += ((mp_word)*tmpx++)*((mp_word)*tmpy--);
|
---|
3283 | }
|
---|
3284 |
|
---|
3285 | /* double the inner product and add carry */
|
---|
3286 | _W = _W + _W + W1;
|
---|
3287 |
|
---|
3288 | /* even columns have the square term in them */
|
---|
3289 | if ((ix&1) == 0) {
|
---|
3290 | _W += ((mp_word)a->dp[ix>>1])*((mp_word)a->dp[ix>>1]);
|
---|
3291 | }
|
---|
3292 |
|
---|
3293 | /* store it */
|
---|
3294 | W[ix] = (mp_digit)(_W & MP_MASK);
|
---|
3295 |
|
---|
3296 | /* make next carry */
|
---|
3297 | W1 = _W >> ((mp_word)DIGIT_BIT);
|
---|
3298 | }
|
---|
3299 |
|
---|
3300 | /* setup dest */
|
---|
3301 | olduse = b->used;
|
---|
3302 | b->used = a->used+a->used;
|
---|
3303 |
|
---|
3304 | {
|
---|
3305 | mp_digit *tmpb;
|
---|
3306 | tmpb = b->dp;
|
---|
3307 | for (ix = 0; ix < pa; ix++) {
|
---|
3308 | *tmpb++ = (mp_digit)(W[ix] & MP_MASK);
|
---|
3309 | }
|
---|
3310 |
|
---|
3311 | /* clear unused digits [that existed in the old copy of c] */
|
---|
3312 | for (; ix < olduse; ix++) {
|
---|
3313 | *tmpb++ = 0;
|
---|
3314 | }
|
---|
3315 | }
|
---|
3316 | mp_clamp (b);
|
---|
3317 |
|
---|
3318 | #ifdef WOLFSSL_SMALL_STACK
|
---|
3319 | XFREE(W, NULL, DYNAMIC_TYPE_BIGINT);
|
---|
3320 | #endif
|
---|
3321 |
|
---|
3322 | return MP_OKAY;
|
---|
3323 | }
|
---|
3324 |
|
---|
3325 |
|
---|
3326 | /* Fast (comba) multiplier
|
---|
3327 | *
|
---|
3328 | * This is the fast column-array [comba] multiplier. It is
|
---|
3329 | * designed to compute the columns of the product first
|
---|
3330 | * then handle the carries afterwards. This has the effect
|
---|
3331 | * of making the nested loops that compute the columns very
|
---|
3332 | * simple and schedulable on super-scalar processors.
|
---|
3333 | *
|
---|
3334 | * This has been modified to produce a variable number of
|
---|
3335 | * digits of output so if say only a half-product is required
|
---|
3336 | * you don't have to compute the upper half (a feature
|
---|
3337 | * required for fast Barrett reduction).
|
---|
3338 | *
|
---|
3339 | * Based on Algorithm 14.12 on pp.595 of HAC.
|
---|
3340 | *
|
---|
3341 | */
|
---|
3342 | int fast_s_mp_mul_digs (mp_int * a, mp_int * b, mp_int * c, int digs)
|
---|
3343 | {
|
---|
3344 | int olduse, res, pa, ix, iz;
|
---|
3345 | #ifdef WOLFSSL_SMALL_STACK
|
---|
3346 | mp_digit* W; /* uses dynamic memory and slower */
|
---|
3347 | #else
|
---|
3348 | mp_digit W[MP_WARRAY];
|
---|
3349 | #endif
|
---|
3350 | mp_word _W;
|
---|
3351 |
|
---|
3352 | /* grow the destination as required */
|
---|
3353 | if (c->alloc < digs) {
|
---|
3354 | if ((res = mp_grow (c, digs)) != MP_OKAY) {
|
---|
3355 | return res;
|
---|
3356 | }
|
---|
3357 | }
|
---|
3358 |
|
---|
3359 | /* number of output digits to produce */
|
---|
3360 | pa = MIN(digs, a->used + b->used);
|
---|
3361 | if (pa > (int)MP_WARRAY)
|
---|
3362 | return MP_RANGE; /* TAO range check */
|
---|
3363 |
|
---|
3364 | #ifdef WOLFSSL_SMALL_STACK
|
---|
3365 | W = (mp_digit*)XMALLOC(sizeof(mp_digit) * MP_WARRAY, NULL, DYNAMIC_TYPE_BIGINT);
|
---|
3366 | if (W == NULL)
|
---|
3367 | return MP_MEM;
|
---|
3368 | #endif
|
---|
3369 |
|
---|
3370 | /* clear the carry */
|
---|
3371 | _W = 0;
|
---|
3372 | for (ix = 0; ix < pa; ix++) {
|
---|
3373 | int tx, ty;
|
---|
3374 | int iy;
|
---|
3375 | mp_digit *tmpx, *tmpy;
|
---|
3376 |
|
---|
3377 | /* get offsets into the two bignums */
|
---|
3378 | ty = MIN(b->used-1, ix);
|
---|
3379 | tx = ix - ty;
|
---|
3380 |
|
---|
3381 | /* setup temp aliases */
|
---|
3382 | tmpx = a->dp + tx;
|
---|
3383 | tmpy = b->dp + ty;
|
---|
3384 |
|
---|
3385 | /* this is the number of times the loop will iterate, essentially
|
---|
3386 | while (tx++ < a->used && ty-- >= 0) { ... }
|
---|
3387 | */
|
---|
3388 | iy = MIN(a->used-tx, ty+1);
|
---|
3389 |
|
---|
3390 | /* execute loop */
|
---|
3391 | for (iz = 0; iz < iy; ++iz) {
|
---|
3392 | _W += ((mp_word)*tmpx++)*((mp_word)*tmpy--);
|
---|
3393 |
|
---|
3394 | }
|
---|
3395 |
|
---|
3396 | /* store term */
|
---|
3397 | W[ix] = (mp_digit)(((mp_digit)_W) & MP_MASK);
|
---|
3398 |
|
---|
3399 | /* make next carry */
|
---|
3400 | _W = _W >> ((mp_word)DIGIT_BIT);
|
---|
3401 | }
|
---|
3402 |
|
---|
3403 | /* setup dest */
|
---|
3404 | olduse = c->used;
|
---|
3405 | c->used = pa;
|
---|
3406 |
|
---|
3407 | {
|
---|
3408 | mp_digit *tmpc;
|
---|
3409 | tmpc = c->dp;
|
---|
3410 | for (ix = 0; ix < pa; ix++) { /* JRB, +1 could read uninitialized data */
|
---|
3411 | /* now extract the previous digit [below the carry] */
|
---|
3412 | *tmpc++ = W[ix];
|
---|
3413 | }
|
---|
3414 |
|
---|
3415 | /* clear unused digits [that existed in the old copy of c] */
|
---|
3416 | for (; ix < olduse; ix++) {
|
---|
3417 | *tmpc++ = 0;
|
---|
3418 | }
|
---|
3419 | }
|
---|
3420 | mp_clamp (c);
|
---|
3421 |
|
---|
3422 | #ifdef WOLFSSL_SMALL_STACK
|
---|
3423 | XFREE(W, NULL, DYNAMIC_TYPE_BIGINT);
|
---|
3424 | #endif
|
---|
3425 |
|
---|
3426 | return MP_OKAY;
|
---|
3427 | }
|
---|
3428 |
|
---|
3429 |
|
---|
3430 | /* low level squaring, b = a*a, HAC pp.596-597, Algorithm 14.16 */
|
---|
3431 | int s_mp_sqr (mp_int * a, mp_int * b)
|
---|
3432 | {
|
---|
3433 | mp_int t;
|
---|
3434 | int res, ix, iy, pa;
|
---|
3435 | mp_word r;
|
---|
3436 | mp_digit u, tmpx, *tmpt;
|
---|
3437 |
|
---|
3438 | pa = a->used;
|
---|
3439 | if ((res = mp_init_size (&t, 2*pa + 1)) != MP_OKAY) {
|
---|
3440 | return res;
|
---|
3441 | }
|
---|
3442 |
|
---|
3443 | /* default used is maximum possible size */
|
---|
3444 | t.used = 2*pa + 1;
|
---|
3445 |
|
---|
3446 | for (ix = 0; ix < pa; ix++) {
|
---|
3447 | /* first calculate the digit at 2*ix */
|
---|
3448 | /* calculate double precision result */
|
---|
3449 | r = ((mp_word) t.dp[2*ix]) +
|
---|
3450 | ((mp_word)a->dp[ix])*((mp_word)a->dp[ix]);
|
---|
3451 |
|
---|
3452 | /* store lower part in result */
|
---|
3453 | t.dp[ix+ix] = (mp_digit) (r & ((mp_word) MP_MASK));
|
---|
3454 |
|
---|
3455 | /* get the carry */
|
---|
3456 | u = (mp_digit)(r >> ((mp_word) DIGIT_BIT));
|
---|
3457 |
|
---|
3458 | /* left hand side of A[ix] * A[iy] */
|
---|
3459 | tmpx = a->dp[ix];
|
---|
3460 |
|
---|
3461 | /* alias for where to store the results */
|
---|
3462 | tmpt = t.dp + (2*ix + 1);
|
---|
3463 |
|
---|
3464 | for (iy = ix + 1; iy < pa; iy++) {
|
---|
3465 | /* first calculate the product */
|
---|
3466 | r = ((mp_word)tmpx) * ((mp_word)a->dp[iy]);
|
---|
3467 |
|
---|
3468 | /* now calculate the double precision result, note we use
|
---|
3469 | * addition instead of *2 since it's easier to optimize
|
---|
3470 | */
|
---|
3471 | r = ((mp_word) *tmpt) + r + r + ((mp_word) u);
|
---|
3472 |
|
---|
3473 | /* store lower part */
|
---|
3474 | *tmpt++ = (mp_digit) (r & ((mp_word) MP_MASK));
|
---|
3475 |
|
---|
3476 | /* get carry */
|
---|
3477 | u = (mp_digit)(r >> ((mp_word) DIGIT_BIT));
|
---|
3478 | }
|
---|
3479 | /* propagate upwards */
|
---|
3480 | while (u != ((mp_digit) 0)) {
|
---|
3481 | r = ((mp_word) *tmpt) + ((mp_word) u);
|
---|
3482 | *tmpt++ = (mp_digit) (r & ((mp_word) MP_MASK));
|
---|
3483 | u = (mp_digit)(r >> ((mp_word) DIGIT_BIT));
|
---|
3484 | }
|
---|
3485 | }
|
---|
3486 |
|
---|
3487 | mp_clamp (&t);
|
---|
3488 | mp_exch (&t, b);
|
---|
3489 | mp_clear (&t);
|
---|
3490 | return MP_OKAY;
|
---|
3491 | }
|
---|
3492 |
|
---|
3493 |
|
---|
3494 | /* multiplies |a| * |b| and only computes up to digs digits of result
|
---|
3495 | * HAC pp. 595, Algorithm 14.12 Modified so you can control how
|
---|
3496 | * many digits of output are created.
|
---|
3497 | */
|
---|
3498 | int s_mp_mul_digs (mp_int * a, mp_int * b, mp_int * c, int digs)
|
---|
3499 | {
|
---|
3500 | mp_int t;
|
---|
3501 | int res, pa, pb, ix, iy;
|
---|
3502 | mp_digit u;
|
---|
3503 | mp_word r;
|
---|
3504 | mp_digit tmpx, *tmpt, *tmpy;
|
---|
3505 |
|
---|
3506 | /* can we use the fast multiplier? */
|
---|
3507 | if ((digs < (int)MP_WARRAY) &&
|
---|
3508 | MIN (a->used, b->used) <
|
---|
3509 | (1 << ((CHAR_BIT * sizeof (mp_word)) - (2 * DIGIT_BIT)))) {
|
---|
3510 | return fast_s_mp_mul_digs (a, b, c, digs);
|
---|
3511 | }
|
---|
3512 |
|
---|
3513 | if ((res = mp_init_size (&t, digs)) != MP_OKAY) {
|
---|
3514 | return res;
|
---|
3515 | }
|
---|
3516 | t.used = digs;
|
---|
3517 |
|
---|
3518 | /* compute the digits of the product directly */
|
---|
3519 | pa = a->used;
|
---|
3520 | for (ix = 0; ix < pa; ix++) {
|
---|
3521 | /* set the carry to zero */
|
---|
3522 | u = 0;
|
---|
3523 |
|
---|
3524 | /* limit ourselves to making digs digits of output */
|
---|
3525 | pb = MIN (b->used, digs - ix);
|
---|
3526 |
|
---|
3527 | /* setup some aliases */
|
---|
3528 | /* copy of the digit from a used within the nested loop */
|
---|
3529 | tmpx = a->dp[ix];
|
---|
3530 |
|
---|
3531 | /* an alias for the destination shifted ix places */
|
---|
3532 | tmpt = t.dp + ix;
|
---|
3533 |
|
---|
3534 | /* an alias for the digits of b */
|
---|
3535 | tmpy = b->dp;
|
---|
3536 |
|
---|
3537 | /* compute the columns of the output and propagate the carry */
|
---|
3538 | for (iy = 0; iy < pb; iy++) {
|
---|
3539 | /* compute the column as a mp_word */
|
---|
3540 | r = ((mp_word)*tmpt) +
|
---|
3541 | ((mp_word)tmpx) * ((mp_word)*tmpy++) +
|
---|
3542 | ((mp_word) u);
|
---|
3543 |
|
---|
3544 | /* the new column is the lower part of the result */
|
---|
3545 | *tmpt++ = (mp_digit) (r & ((mp_word) MP_MASK));
|
---|
3546 |
|
---|
3547 | /* get the carry word from the result */
|
---|
3548 | u = (mp_digit) (r >> ((mp_word) DIGIT_BIT));
|
---|
3549 | }
|
---|
3550 | /* set carry if it is placed below digs */
|
---|
3551 | if (ix + iy < digs) {
|
---|
3552 | *tmpt = u;
|
---|
3553 | }
|
---|
3554 | }
|
---|
3555 |
|
---|
3556 | mp_clamp (&t);
|
---|
3557 | mp_exch (&t, c);
|
---|
3558 |
|
---|
3559 | mp_clear (&t);
|
---|
3560 | return MP_OKAY;
|
---|
3561 | }
|
---|
3562 |
|
---|
3563 |
|
---|
3564 | /*
|
---|
3565 | * shifts with subtractions when the result is greater than b.
|
---|
3566 | *
|
---|
3567 | * The method is slightly modified to shift B unconditionally up to just under
|
---|
3568 | * the leading bit of b. This saves a lot of multiple precision shifting.
|
---|
3569 | */
|
---|
3570 | int mp_montgomery_calc_normalization (mp_int * a, mp_int * b)
|
---|
3571 | {
|
---|
3572 | int x, bits, res;
|
---|
3573 |
|
---|
3574 | /* how many bits of last digit does b use */
|
---|
3575 | bits = mp_count_bits (b) % DIGIT_BIT;
|
---|
3576 |
|
---|
3577 | if (b->used > 1) {
|
---|
3578 | if ((res = mp_2expt (a, (b->used - 1) * DIGIT_BIT + bits - 1))
|
---|
3579 | != MP_OKAY) {
|
---|
3580 | return res;
|
---|
3581 | }
|
---|
3582 | } else {
|
---|
3583 | if ((res = mp_set(a, 1)) != MP_OKAY) {
|
---|
3584 | return res;
|
---|
3585 | }
|
---|
3586 | bits = 1;
|
---|
3587 | }
|
---|
3588 |
|
---|
3589 | /* now compute C = A * B mod b */
|
---|
3590 | for (x = bits - 1; x < (int)DIGIT_BIT; x++) {
|
---|
3591 | if ((res = mp_mul_2 (a, a)) != MP_OKAY) {
|
---|
3592 | return res;
|
---|
3593 | }
|
---|
3594 | if (mp_cmp_mag (a, b) != MP_LT) {
|
---|
3595 | if ((res = s_mp_sub (a, b, a)) != MP_OKAY) {
|
---|
3596 | return res;
|
---|
3597 | }
|
---|
3598 | }
|
---|
3599 | }
|
---|
3600 |
|
---|
3601 | return MP_OKAY;
|
---|
3602 | }
|
---|
3603 |
|
---|
3604 |
|
---|
3605 | #ifdef MP_LOW_MEM
|
---|
3606 | #define TAB_SIZE 32
|
---|
3607 | #else
|
---|
3608 | #define TAB_SIZE 256
|
---|
3609 | #endif
|
---|
3610 |
|
---|
3611 | int s_mp_exptmod (mp_int * G, mp_int * X, mp_int * P, mp_int * Y, int redmode)
|
---|
3612 | {
|
---|
3613 | mp_int M[TAB_SIZE], res, mu;
|
---|
3614 | mp_digit buf;
|
---|
3615 | int err, bitbuf, bitcpy, bitcnt, mode, digidx, x, y, winsize;
|
---|
3616 | int (*redux)(mp_int*,mp_int*,mp_int*);
|
---|
3617 |
|
---|
3618 | /* find window size */
|
---|
3619 | x = mp_count_bits (X);
|
---|
3620 | if (x <= 7) {
|
---|
3621 | winsize = 2;
|
---|
3622 | } else if (x <= 36) {
|
---|
3623 | winsize = 3;
|
---|
3624 | } else if (x <= 140) {
|
---|
3625 | winsize = 4;
|
---|
3626 | } else if (x <= 450) {
|
---|
3627 | winsize = 5;
|
---|
3628 | } else if (x <= 1303) {
|
---|
3629 | winsize = 6;
|
---|
3630 | } else if (x <= 3529) {
|
---|
3631 | winsize = 7;
|
---|
3632 | } else {
|
---|
3633 | winsize = 8;
|
---|
3634 | }
|
---|
3635 |
|
---|
3636 | #ifdef MP_LOW_MEM
|
---|
3637 | if (winsize > 5) {
|
---|
3638 | winsize = 5;
|
---|
3639 | }
|
---|
3640 | #endif
|
---|
3641 |
|
---|
3642 | /* init M array */
|
---|
3643 | /* init first cell */
|
---|
3644 | if ((err = mp_init(&M[1])) != MP_OKAY) {
|
---|
3645 | return err;
|
---|
3646 | }
|
---|
3647 |
|
---|
3648 | /* now init the second half of the array */
|
---|
3649 | for (x = 1<<(winsize-1); x < (1 << winsize); x++) {
|
---|
3650 | if ((err = mp_init(&M[x])) != MP_OKAY) {
|
---|
3651 | for (y = 1<<(winsize-1); y < x; y++) {
|
---|
3652 | mp_clear (&M[y]);
|
---|
3653 | }
|
---|
3654 | mp_clear(&M[1]);
|
---|
3655 | return err;
|
---|
3656 | }
|
---|
3657 | }
|
---|
3658 |
|
---|
3659 | /* create mu, used for Barrett reduction */
|
---|
3660 | if ((err = mp_init (&mu)) != MP_OKAY) {
|
---|
3661 | goto LBL_M;
|
---|
3662 | }
|
---|
3663 |
|
---|
3664 | if (redmode == 0) {
|
---|
3665 | if ((err = mp_reduce_setup (&mu, P)) != MP_OKAY) {
|
---|
3666 | goto LBL_MU;
|
---|
3667 | }
|
---|
3668 | redux = mp_reduce;
|
---|
3669 | } else {
|
---|
3670 | if ((err = mp_reduce_2k_setup_l (P, &mu)) != MP_OKAY) {
|
---|
3671 | goto LBL_MU;
|
---|
3672 | }
|
---|
3673 | redux = mp_reduce_2k_l;
|
---|
3674 | }
|
---|
3675 |
|
---|
3676 | /* create M table
|
---|
3677 | *
|
---|
3678 | * The M table contains powers of the base,
|
---|
3679 | * e.g. M[x] = G**x mod P
|
---|
3680 | *
|
---|
3681 | * The first half of the table is not
|
---|
3682 | * computed though accept for M[0] and M[1]
|
---|
3683 | */
|
---|
3684 | if ((err = mp_mod (G, P, &M[1])) != MP_OKAY) {
|
---|
3685 | goto LBL_MU;
|
---|
3686 | }
|
---|
3687 |
|
---|
3688 | /* compute the value at M[1<<(winsize-1)] by squaring
|
---|
3689 | * M[1] (winsize-1) times
|
---|
3690 | */
|
---|
3691 | if ((err = mp_copy (&M[1], &M[(mp_digit)(1 << (winsize - 1))])) != MP_OKAY) {
|
---|
3692 | goto LBL_MU;
|
---|
3693 | }
|
---|
3694 |
|
---|
3695 | for (x = 0; x < (winsize - 1); x++) {
|
---|
3696 | /* square it */
|
---|
3697 | if ((err = mp_sqr (&M[(mp_digit)(1 << (winsize - 1))],
|
---|
3698 | &M[(mp_digit)(1 << (winsize - 1))])) != MP_OKAY) {
|
---|
3699 | goto LBL_MU;
|
---|
3700 | }
|
---|
3701 |
|
---|
3702 | /* reduce modulo P */
|
---|
3703 | if ((err = redux (&M[(mp_digit)(1 << (winsize - 1))], P, &mu)) != MP_OKAY) {
|
---|
3704 | goto LBL_MU;
|
---|
3705 | }
|
---|
3706 | }
|
---|
3707 |
|
---|
3708 | /* create upper table, that is M[x] = M[x-1] * M[1] (mod P)
|
---|
3709 | * for x = (2**(winsize - 1) + 1) to (2**winsize - 1)
|
---|
3710 | */
|
---|
3711 | for (x = (1 << (winsize - 1)) + 1; x < (1 << winsize); x++) {
|
---|
3712 | if ((err = mp_mul (&M[x - 1], &M[1], &M[x])) != MP_OKAY) {
|
---|
3713 | goto LBL_MU;
|
---|
3714 | }
|
---|
3715 | if ((err = redux (&M[x], P, &mu)) != MP_OKAY) {
|
---|
3716 | goto LBL_MU;
|
---|
3717 | }
|
---|
3718 | }
|
---|
3719 |
|
---|
3720 | /* setup result */
|
---|
3721 | if ((err = mp_init (&res)) != MP_OKAY) {
|
---|
3722 | goto LBL_MU;
|
---|
3723 | }
|
---|
3724 | if ((err = mp_set (&res, 1)) != MP_OKAY) {
|
---|
3725 | goto LBL_MU;
|
---|
3726 | }
|
---|
3727 |
|
---|
3728 | /* set initial mode and bit cnt */
|
---|
3729 | mode = 0;
|
---|
3730 | bitcnt = 1;
|
---|
3731 | buf = 0;
|
---|
3732 | digidx = X->used - 1;
|
---|
3733 | bitcpy = 0;
|
---|
3734 | bitbuf = 0;
|
---|
3735 |
|
---|
3736 | for (;;) {
|
---|
3737 | /* grab next digit as required */
|
---|
3738 | if (--bitcnt == 0) {
|
---|
3739 | /* if digidx == -1 we are out of digits */
|
---|
3740 | if (digidx == -1) {
|
---|
3741 | break;
|
---|
3742 | }
|
---|
3743 | /* read next digit and reset the bitcnt */
|
---|
3744 | buf = X->dp[digidx--];
|
---|
3745 | bitcnt = (int) DIGIT_BIT;
|
---|
3746 | }
|
---|
3747 |
|
---|
3748 | /* grab the next msb from the exponent */
|
---|
3749 | y = (int)(buf >> (mp_digit)(DIGIT_BIT - 1)) & 1;
|
---|
3750 | buf <<= (mp_digit)1;
|
---|
3751 |
|
---|
3752 | /* if the bit is zero and mode == 0 then we ignore it
|
---|
3753 | * These represent the leading zero bits before the first 1 bit
|
---|
3754 | * in the exponent. Technically this opt is not required but it
|
---|
3755 | * does lower the # of trivial squaring/reductions used
|
---|
3756 | */
|
---|
3757 | if (mode == 0 && y == 0) {
|
---|
3758 | continue;
|
---|
3759 | }
|
---|
3760 |
|
---|
3761 | /* if the bit is zero and mode == 1 then we square */
|
---|
3762 | if (mode == 1 && y == 0) {
|
---|
3763 | if ((err = mp_sqr (&res, &res)) != MP_OKAY) {
|
---|
3764 | goto LBL_RES;
|
---|
3765 | }
|
---|
3766 | if ((err = redux (&res, P, &mu)) != MP_OKAY) {
|
---|
3767 | goto LBL_RES;
|
---|
3768 | }
|
---|
3769 | continue;
|
---|
3770 | }
|
---|
3771 |
|
---|
3772 | /* else we add it to the window */
|
---|
3773 | bitbuf |= (y << (winsize - ++bitcpy));
|
---|
3774 | mode = 2;
|
---|
3775 |
|
---|
3776 | if (bitcpy == winsize) {
|
---|
3777 | /* ok window is filled so square as required and multiply */
|
---|
3778 | /* square first */
|
---|
3779 | for (x = 0; x < winsize; x++) {
|
---|
3780 | if ((err = mp_sqr (&res, &res)) != MP_OKAY) {
|
---|
3781 | goto LBL_RES;
|
---|
3782 | }
|
---|
3783 | if ((err = redux (&res, P, &mu)) != MP_OKAY) {
|
---|
3784 | goto LBL_RES;
|
---|
3785 | }
|
---|
3786 | }
|
---|
3787 |
|
---|
3788 | /* then multiply */
|
---|
3789 | if ((err = mp_mul (&res, &M[bitbuf], &res)) != MP_OKAY) {
|
---|
3790 | goto LBL_RES;
|
---|
3791 | }
|
---|
3792 | if ((err = redux (&res, P, &mu)) != MP_OKAY) {
|
---|
3793 | goto LBL_RES;
|
---|
3794 | }
|
---|
3795 |
|
---|
3796 | /* empty window and reset */
|
---|
3797 | bitcpy = 0;
|
---|
3798 | bitbuf = 0;
|
---|
3799 | mode = 1;
|
---|
3800 | }
|
---|
3801 | }
|
---|
3802 |
|
---|
3803 | /* if bits remain then square/multiply */
|
---|
3804 | if (mode == 2 && bitcpy > 0) {
|
---|
3805 | /* square then multiply if the bit is set */
|
---|
3806 | for (x = 0; x < bitcpy; x++) {
|
---|
3807 | if ((err = mp_sqr (&res, &res)) != MP_OKAY) {
|
---|
3808 | goto LBL_RES;
|
---|
3809 | }
|
---|
3810 | if ((err = redux (&res, P, &mu)) != MP_OKAY) {
|
---|
3811 | goto LBL_RES;
|
---|
3812 | }
|
---|
3813 |
|
---|
3814 | bitbuf <<= 1;
|
---|
3815 | if ((bitbuf & (1 << winsize)) != 0) {
|
---|
3816 | /* then multiply */
|
---|
3817 | if ((err = mp_mul (&res, &M[1], &res)) != MP_OKAY) {
|
---|
3818 | goto LBL_RES;
|
---|
3819 | }
|
---|
3820 | if ((err = redux (&res, P, &mu)) != MP_OKAY) {
|
---|
3821 | goto LBL_RES;
|
---|
3822 | }
|
---|
3823 | }
|
---|
3824 | }
|
---|
3825 | }
|
---|
3826 |
|
---|
3827 | mp_exch (&res, Y);
|
---|
3828 | err = MP_OKAY;
|
---|
3829 | LBL_RES:mp_clear (&res);
|
---|
3830 | LBL_MU:mp_clear (&mu);
|
---|
3831 | LBL_M:
|
---|
3832 | mp_clear(&M[1]);
|
---|
3833 | for (x = 1<<(winsize-1); x < (1 << winsize); x++) {
|
---|
3834 | mp_clear (&M[x]);
|
---|
3835 | }
|
---|
3836 | return err;
|
---|
3837 | }
|
---|
3838 |
|
---|
3839 |
|
---|
3840 | /* pre-calculate the value required for Barrett reduction
|
---|
3841 | * For a given modulus "b" it calculates the value required in "a"
|
---|
3842 | */
|
---|
3843 | int mp_reduce_setup (mp_int * a, mp_int * b)
|
---|
3844 | {
|
---|
3845 | int res;
|
---|
3846 |
|
---|
3847 | if ((res = mp_2expt (a, b->used * 2 * DIGIT_BIT)) != MP_OKAY) {
|
---|
3848 | return res;
|
---|
3849 | }
|
---|
3850 | return mp_div (a, b, a, NULL);
|
---|
3851 | }
|
---|
3852 |
|
---|
3853 |
|
---|
3854 | /* reduces x mod m, assumes 0 < x < m**2, mu is
|
---|
3855 | * precomputed via mp_reduce_setup.
|
---|
3856 | * From HAC pp.604 Algorithm 14.42
|
---|
3857 | */
|
---|
3858 | int mp_reduce (mp_int * x, mp_int * m, mp_int * mu)
|
---|
3859 | {
|
---|
3860 | mp_int q;
|
---|
3861 | int res, um = m->used;
|
---|
3862 |
|
---|
3863 | /* q = x */
|
---|
3864 | if ((res = mp_init_copy (&q, x)) != MP_OKAY) {
|
---|
3865 | return res;
|
---|
3866 | }
|
---|
3867 |
|
---|
3868 | /* q1 = x / b**(k-1) */
|
---|
3869 | mp_rshd (&q, um - 1);
|
---|
3870 |
|
---|
3871 | /* according to HAC this optimization is ok */
|
---|
3872 | if (((mp_word) um) > (((mp_digit)1) << (DIGIT_BIT - 1))) {
|
---|
3873 | if ((res = mp_mul (&q, mu, &q)) != MP_OKAY) {
|
---|
3874 | goto CLEANUP;
|
---|
3875 | }
|
---|
3876 | } else {
|
---|
3877 | #ifdef BN_S_MP_MUL_HIGH_DIGS_C
|
---|
3878 | if ((res = s_mp_mul_high_digs (&q, mu, &q, um)) != MP_OKAY) {
|
---|
3879 | goto CLEANUP;
|
---|
3880 | }
|
---|
3881 | #elif defined(BN_FAST_S_MP_MUL_HIGH_DIGS_C)
|
---|
3882 | if ((res = fast_s_mp_mul_high_digs (&q, mu, &q, um)) != MP_OKAY) {
|
---|
3883 | goto CLEANUP;
|
---|
3884 | }
|
---|
3885 | #else
|
---|
3886 | {
|
---|
3887 | res = MP_VAL;
|
---|
3888 | goto CLEANUP;
|
---|
3889 | }
|
---|
3890 | #endif
|
---|
3891 | }
|
---|
3892 |
|
---|
3893 | /* q3 = q2 / b**(k+1) */
|
---|
3894 | mp_rshd (&q, um + 1);
|
---|
3895 |
|
---|
3896 | /* x = x mod b**(k+1), quick (no division) */
|
---|
3897 | if ((res = mp_mod_2d (x, DIGIT_BIT * (um + 1), x)) != MP_OKAY) {
|
---|
3898 | goto CLEANUP;
|
---|
3899 | }
|
---|
3900 |
|
---|
3901 | /* q = q * m mod b**(k+1), quick (no division) */
|
---|
3902 | if ((res = s_mp_mul_digs (&q, m, &q, um + 1)) != MP_OKAY) {
|
---|
3903 | goto CLEANUP;
|
---|
3904 | }
|
---|
3905 |
|
---|
3906 | /* x = x - q */
|
---|
3907 | if ((res = mp_sub (x, &q, x)) != MP_OKAY) {
|
---|
3908 | goto CLEANUP;
|
---|
3909 | }
|
---|
3910 |
|
---|
3911 | /* If x < 0, add b**(k+1) to it */
|
---|
3912 | if (mp_cmp_d (x, 0) == MP_LT) {
|
---|
3913 | if ((res = mp_set (&q, 1)) != MP_OKAY)
|
---|
3914 | goto CLEANUP;
|
---|
3915 | if ((res = mp_lshd (&q, um + 1)) != MP_OKAY)
|
---|
3916 | goto CLEANUP;
|
---|
3917 | if ((res = mp_add (x, &q, x)) != MP_OKAY)
|
---|
3918 | goto CLEANUP;
|
---|
3919 | }
|
---|
3920 |
|
---|
3921 | /* Back off if it's too big */
|
---|
3922 | while (mp_cmp (x, m) != MP_LT) {
|
---|
3923 | if ((res = s_mp_sub (x, m, x)) != MP_OKAY) {
|
---|
3924 | goto CLEANUP;
|
---|
3925 | }
|
---|
3926 | }
|
---|
3927 |
|
---|
3928 | CLEANUP:
|
---|
3929 | mp_clear (&q);
|
---|
3930 |
|
---|
3931 | return res;
|
---|
3932 | }
|
---|
3933 |
|
---|
3934 |
|
---|
3935 | /* reduces a modulo n where n is of the form 2**p - d
|
---|
3936 | This differs from reduce_2k since "d" can be larger
|
---|
3937 | than a single digit.
|
---|
3938 | */
|
---|
3939 | int mp_reduce_2k_l(mp_int *a, mp_int *n, mp_int *d)
|
---|
3940 | {
|
---|
3941 | mp_int q;
|
---|
3942 | int p, res;
|
---|
3943 |
|
---|
3944 | if ((res = mp_init(&q)) != MP_OKAY) {
|
---|
3945 | return res;
|
---|
3946 | }
|
---|
3947 |
|
---|
3948 | p = mp_count_bits(n);
|
---|
3949 | top:
|
---|
3950 | /* q = a/2**p, a = a mod 2**p */
|
---|
3951 | if ((res = mp_div_2d(a, p, &q, a)) != MP_OKAY) {
|
---|
3952 | goto ERR;
|
---|
3953 | }
|
---|
3954 |
|
---|
3955 | /* q = q * d */
|
---|
3956 | if ((res = mp_mul(&q, d, &q)) != MP_OKAY) {
|
---|
3957 | goto ERR;
|
---|
3958 | }
|
---|
3959 |
|
---|
3960 | /* a = a + q */
|
---|
3961 | if ((res = s_mp_add(a, &q, a)) != MP_OKAY) {
|
---|
3962 | goto ERR;
|
---|
3963 | }
|
---|
3964 |
|
---|
3965 | if (mp_cmp_mag(a, n) != MP_LT) {
|
---|
3966 | if ((res = s_mp_sub(a, n, a)) != MP_OKAY) {
|
---|
3967 | goto ERR;
|
---|
3968 | }
|
---|
3969 | goto top;
|
---|
3970 | }
|
---|
3971 |
|
---|
3972 | ERR:
|
---|
3973 | mp_clear(&q);
|
---|
3974 | return res;
|
---|
3975 | }
|
---|
3976 |
|
---|
3977 |
|
---|
3978 | /* determines the setup value */
|
---|
3979 | int mp_reduce_2k_setup_l(mp_int *a, mp_int *d)
|
---|
3980 | {
|
---|
3981 | int res;
|
---|
3982 | mp_int tmp;
|
---|
3983 |
|
---|
3984 | if ((res = mp_init(&tmp)) != MP_OKAY) {
|
---|
3985 | return res;
|
---|
3986 | }
|
---|
3987 |
|
---|
3988 | if ((res = mp_2expt(&tmp, mp_count_bits(a))) != MP_OKAY) {
|
---|
3989 | goto ERR;
|
---|
3990 | }
|
---|
3991 |
|
---|
3992 | if ((res = s_mp_sub(&tmp, a, d)) != MP_OKAY) {
|
---|
3993 | goto ERR;
|
---|
3994 | }
|
---|
3995 |
|
---|
3996 | ERR:
|
---|
3997 | mp_clear(&tmp);
|
---|
3998 | return res;
|
---|
3999 | }
|
---|
4000 |
|
---|
4001 |
|
---|
4002 | /* multiplies |a| * |b| and does not compute the lower digs digits
|
---|
4003 | * [meant to get the higher part of the product]
|
---|
4004 | */
|
---|
4005 | int s_mp_mul_high_digs (mp_int * a, mp_int * b, mp_int * c, int digs)
|
---|
4006 | {
|
---|
4007 | mp_int t;
|
---|
4008 | int res, pa, pb, ix, iy;
|
---|
4009 | mp_digit u;
|
---|
4010 | mp_word r;
|
---|
4011 | mp_digit tmpx, *tmpt, *tmpy;
|
---|
4012 |
|
---|
4013 | /* can we use the fast multiplier? */
|
---|
4014 | #ifdef BN_FAST_S_MP_MUL_HIGH_DIGS_C
|
---|
4015 | if (((a->used + b->used + 1) < (int)MP_WARRAY)
|
---|
4016 | && MIN (a->used, b->used) <
|
---|
4017 | (1 << ((CHAR_BIT * sizeof (mp_word)) - (2 * DIGIT_BIT)))) {
|
---|
4018 | return fast_s_mp_mul_high_digs (a, b, c, digs);
|
---|
4019 | }
|
---|
4020 | #endif
|
---|
4021 |
|
---|
4022 | if ((res = mp_init_size (&t, a->used + b->used + 1)) != MP_OKAY) {
|
---|
4023 | return res;
|
---|
4024 | }
|
---|
4025 | t.used = a->used + b->used + 1;
|
---|
4026 |
|
---|
4027 | pa = a->used;
|
---|
4028 | pb = b->used;
|
---|
4029 | for (ix = 0; ix < pa && a->dp; ix++) {
|
---|
4030 | /* clear the carry */
|
---|
4031 | u = 0;
|
---|
4032 |
|
---|
4033 | /* left hand side of A[ix] * B[iy] */
|
---|
4034 | tmpx = a->dp[ix];
|
---|
4035 |
|
---|
4036 | /* alias to the address of where the digits will be stored */
|
---|
4037 | tmpt = &(t.dp[digs]);
|
---|
4038 |
|
---|
4039 | /* alias for where to read the right hand side from */
|
---|
4040 | tmpy = b->dp + (digs - ix);
|
---|
4041 |
|
---|
4042 | for (iy = digs - ix; iy < pb; iy++) {
|
---|
4043 | /* calculate the double precision result */
|
---|
4044 | r = ((mp_word)*tmpt) +
|
---|
4045 | ((mp_word)tmpx) * ((mp_word)*tmpy++) +
|
---|
4046 | ((mp_word) u);
|
---|
4047 |
|
---|
4048 | /* get the lower part */
|
---|
4049 | *tmpt++ = (mp_digit) (r & ((mp_word) MP_MASK));
|
---|
4050 |
|
---|
4051 | /* carry the carry */
|
---|
4052 | u = (mp_digit) (r >> ((mp_word) DIGIT_BIT));
|
---|
4053 | }
|
---|
4054 | *tmpt = u;
|
---|
4055 | }
|
---|
4056 | mp_clamp (&t);
|
---|
4057 | mp_exch (&t, c);
|
---|
4058 | mp_clear (&t);
|
---|
4059 | return MP_OKAY;
|
---|
4060 | }
|
---|
4061 |
|
---|
4062 |
|
---|
4063 | /* this is a modified version of fast_s_mul_digs that only produces
|
---|
4064 | * output digits *above* digs. See the comments for fast_s_mul_digs
|
---|
4065 | * to see how it works.
|
---|
4066 | *
|
---|
4067 | * This is used in the Barrett reduction since for one of the multiplications
|
---|
4068 | * only the higher digits were needed. This essentially halves the work.
|
---|
4069 | *
|
---|
4070 | * Based on Algorithm 14.12 on pp.595 of HAC.
|
---|
4071 | */
|
---|
4072 | int fast_s_mp_mul_high_digs (mp_int * a, mp_int * b, mp_int * c, int digs)
|
---|
4073 | {
|
---|
4074 | int olduse, res, pa, ix, iz;
|
---|
4075 | #ifdef WOLFSSL_SMALL_STACK
|
---|
4076 | mp_digit* W; /* uses dynamic memory and slower */
|
---|
4077 | #else
|
---|
4078 | mp_digit W[MP_WARRAY];
|
---|
4079 | #endif
|
---|
4080 | mp_word _W;
|
---|
4081 |
|
---|
4082 | if (a->dp == NULL) { /* JRB, avoid reading uninitialized values */
|
---|
4083 | return MP_VAL;
|
---|
4084 | }
|
---|
4085 |
|
---|
4086 | /* grow the destination as required */
|
---|
4087 | pa = a->used + b->used;
|
---|
4088 | if (c->alloc < pa) {
|
---|
4089 | if ((res = mp_grow (c, pa)) != MP_OKAY) {
|
---|
4090 | return res;
|
---|
4091 | }
|
---|
4092 | }
|
---|
4093 |
|
---|
4094 | if (pa > (int)MP_WARRAY)
|
---|
4095 | return MP_RANGE; /* TAO range check */
|
---|
4096 |
|
---|
4097 | #ifdef WOLFSSL_SMALL_STACK
|
---|
4098 | W = (mp_digit*)XMALLOC(sizeof(mp_digit) * MP_WARRAY, NULL, DYNAMIC_TYPE_BIGINT);
|
---|
4099 | if (W == NULL)
|
---|
4100 | return MP_MEM;
|
---|
4101 | #endif
|
---|
4102 |
|
---|
4103 | /* number of output digits to produce */
|
---|
4104 | pa = a->used + b->used;
|
---|
4105 | _W = 0;
|
---|
4106 | for (ix = digs; ix < pa; ix++) { /* JRB, have a->dp check at top of function*/
|
---|
4107 | int tx, ty, iy;
|
---|
4108 | mp_digit *tmpx, *tmpy;
|
---|
4109 |
|
---|
4110 | /* get offsets into the two bignums */
|
---|
4111 | ty = MIN(b->used-1, ix);
|
---|
4112 | tx = ix - ty;
|
---|
4113 |
|
---|
4114 | /* setup temp aliases */
|
---|
4115 | tmpx = a->dp + tx;
|
---|
4116 | tmpy = b->dp + ty;
|
---|
4117 |
|
---|
4118 | /* this is the number of times the loop will iterate, essentially its
|
---|
4119 | while (tx++ < a->used && ty-- >= 0) { ... }
|
---|
4120 | */
|
---|
4121 | iy = MIN(a->used-tx, ty+1);
|
---|
4122 |
|
---|
4123 | /* execute loop */
|
---|
4124 | for (iz = 0; iz < iy; iz++) {
|
---|
4125 | _W += ((mp_word)*tmpx++)*((mp_word)*tmpy--);
|
---|
4126 | }
|
---|
4127 |
|
---|
4128 | /* store term */
|
---|
4129 | W[ix] = (mp_digit)(((mp_digit)_W) & MP_MASK);
|
---|
4130 |
|
---|
4131 | /* make next carry */
|
---|
4132 | _W = _W >> ((mp_word)DIGIT_BIT);
|
---|
4133 | }
|
---|
4134 |
|
---|
4135 | /* setup dest */
|
---|
4136 | olduse = c->used;
|
---|
4137 | c->used = pa;
|
---|
4138 |
|
---|
4139 | {
|
---|
4140 | mp_digit *tmpc;
|
---|
4141 |
|
---|
4142 | tmpc = c->dp + digs;
|
---|
4143 | for (ix = digs; ix < pa; ix++) { /* TAO, <= could potentially overwrite */
|
---|
4144 | /* now extract the previous digit [below the carry] */
|
---|
4145 | *tmpc++ = W[ix];
|
---|
4146 | }
|
---|
4147 |
|
---|
4148 | /* clear unused digits [that existed in the old copy of c] */
|
---|
4149 | for (; ix < olduse; ix++) {
|
---|
4150 | *tmpc++ = 0;
|
---|
4151 | }
|
---|
4152 | }
|
---|
4153 | mp_clamp (c);
|
---|
4154 |
|
---|
4155 | #ifdef WOLFSSL_SMALL_STACK
|
---|
4156 | XFREE(W, NULL, DYNAMIC_TYPE_BIGINT);
|
---|
4157 | #endif
|
---|
4158 |
|
---|
4159 | return MP_OKAY;
|
---|
4160 | }
|
---|
4161 |
|
---|
4162 |
|
---|
4163 | #ifndef MP_SET_CHUNK_BITS
|
---|
4164 | #define MP_SET_CHUNK_BITS 4
|
---|
4165 | #endif
|
---|
4166 | int mp_set_int (mp_int * a, unsigned long b)
|
---|
4167 | {
|
---|
4168 | int x, res;
|
---|
4169 |
|
---|
4170 | /* use direct mp_set if b is less than mp_digit max */
|
---|
4171 | if (b < MP_DIGIT_MAX) {
|
---|
4172 | return mp_set (a, (mp_digit)b);
|
---|
4173 | }
|
---|
4174 |
|
---|
4175 | mp_zero (a);
|
---|
4176 |
|
---|
4177 | /* set chunk bits at a time */
|
---|
4178 | for (x = 0; x < (int)(sizeof(b) * 8) / MP_SET_CHUNK_BITS; x++) {
|
---|
4179 | /* shift the number up chunk bits */
|
---|
4180 | if ((res = mp_mul_2d (a, MP_SET_CHUNK_BITS, a)) != MP_OKAY) {
|
---|
4181 | return res;
|
---|
4182 | }
|
---|
4183 |
|
---|
4184 | /* OR in the top bits of the source */
|
---|
4185 | a->dp[0] |= (b >> ((sizeof(b) * 8) - MP_SET_CHUNK_BITS)) &
|
---|
4186 | ((1 << MP_SET_CHUNK_BITS) - 1);
|
---|
4187 |
|
---|
4188 | /* shift the source up to the next chunk bits */
|
---|
4189 | b <<= MP_SET_CHUNK_BITS;
|
---|
4190 |
|
---|
4191 | /* ensure that digits are not clamped off */
|
---|
4192 | a->used += 1;
|
---|
4193 | }
|
---|
4194 | mp_clamp (a);
|
---|
4195 | return MP_OKAY;
|
---|
4196 | }
|
---|
4197 |
|
---|
4198 |
|
---|
4199 | #if defined(WOLFSSL_KEY_GEN) || defined(HAVE_ECC) || !defined(NO_RSA) || \
|
---|
4200 | !defined(NO_DSA) | !defined(NO_DH)
|
---|
4201 |
|
---|
4202 | /* c = a * a (mod b) */
|
---|
4203 | int mp_sqrmod (mp_int * a, mp_int * b, mp_int * c)
|
---|
4204 | {
|
---|
4205 | int res;
|
---|
4206 | mp_int t;
|
---|
4207 |
|
---|
4208 | if ((res = mp_init (&t)) != MP_OKAY) {
|
---|
4209 | return res;
|
---|
4210 | }
|
---|
4211 |
|
---|
4212 | if ((res = mp_sqr (a, &t)) != MP_OKAY) {
|
---|
4213 | mp_clear (&t);
|
---|
4214 | return res;
|
---|
4215 | }
|
---|
4216 | res = mp_mod (&t, b, c);
|
---|
4217 | mp_clear (&t);
|
---|
4218 | return res;
|
---|
4219 | }
|
---|
4220 |
|
---|
4221 | #endif
|
---|
4222 |
|
---|
4223 |
|
---|
4224 | #if defined(HAVE_ECC) || !defined(NO_PWDBASED) || defined(WOLFSSL_SNIFFER) || \
|
---|
4225 | defined(WOLFSSL_HAVE_WOLFSCEP) || defined(WOLFSSL_KEY_GEN) || \
|
---|
4226 | defined(OPENSSL_EXTRA) || defined(WC_RSA_BLINDING) || \
|
---|
4227 | (!defined(NO_RSA) && !defined(NO_RSA_BOUNDS_CHECK))
|
---|
4228 |
|
---|
4229 | /* single digit addition */
|
---|
4230 | int mp_add_d (mp_int* a, mp_digit b, mp_int* c)
|
---|
4231 | {
|
---|
4232 | int res, ix, oldused;
|
---|
4233 | mp_digit *tmpa, *tmpc, mu;
|
---|
4234 |
|
---|
4235 | /* grow c as required */
|
---|
4236 | if (c->alloc < a->used + 1) {
|
---|
4237 | if ((res = mp_grow(c, a->used + 1)) != MP_OKAY) {
|
---|
4238 | return res;
|
---|
4239 | }
|
---|
4240 | }
|
---|
4241 |
|
---|
4242 | /* if a is negative and |a| >= b, call c = |a| - b */
|
---|
4243 | if (a->sign == MP_NEG && (a->used > 1 || a->dp[0] >= b)) {
|
---|
4244 | /* temporarily fix sign of a */
|
---|
4245 | a->sign = MP_ZPOS;
|
---|
4246 |
|
---|
4247 | /* c = |a| - b */
|
---|
4248 | res = mp_sub_d(a, b, c);
|
---|
4249 |
|
---|
4250 | /* fix sign */
|
---|
4251 | a->sign = c->sign = MP_NEG;
|
---|
4252 |
|
---|
4253 | /* clamp */
|
---|
4254 | mp_clamp(c);
|
---|
4255 |
|
---|
4256 | return res;
|
---|
4257 | }
|
---|
4258 |
|
---|
4259 | /* old number of used digits in c */
|
---|
4260 | oldused = c->used;
|
---|
4261 |
|
---|
4262 | /* sign always positive */
|
---|
4263 | c->sign = MP_ZPOS;
|
---|
4264 |
|
---|
4265 | /* source alias */
|
---|
4266 | tmpa = a->dp;
|
---|
4267 |
|
---|
4268 | /* destination alias */
|
---|
4269 | tmpc = c->dp;
|
---|
4270 |
|
---|
4271 | /* if a is positive */
|
---|
4272 | if (a->sign == MP_ZPOS) {
|
---|
4273 | /* add digit, after this we're propagating
|
---|
4274 | * the carry.
|
---|
4275 | */
|
---|
4276 | *tmpc = *tmpa++ + b;
|
---|
4277 | mu = *tmpc >> DIGIT_BIT;
|
---|
4278 | *tmpc++ &= MP_MASK;
|
---|
4279 |
|
---|
4280 | /* now handle rest of the digits */
|
---|
4281 | for (ix = 1; ix < a->used; ix++) {
|
---|
4282 | *tmpc = *tmpa++ + mu;
|
---|
4283 | mu = *tmpc >> DIGIT_BIT;
|
---|
4284 | *tmpc++ &= MP_MASK;
|
---|
4285 | }
|
---|
4286 | /* set final carry */
|
---|
4287 | if (ix < c->alloc) {
|
---|
4288 | ix++;
|
---|
4289 | *tmpc++ = mu;
|
---|
4290 | }
|
---|
4291 |
|
---|
4292 | /* setup size */
|
---|
4293 | c->used = a->used + 1;
|
---|
4294 | } else {
|
---|
4295 | /* a was negative and |a| < b */
|
---|
4296 | c->used = 1;
|
---|
4297 |
|
---|
4298 | /* the result is a single digit */
|
---|
4299 | if (a->used == 1) {
|
---|
4300 | *tmpc++ = b - a->dp[0];
|
---|
4301 | } else {
|
---|
4302 | *tmpc++ = b;
|
---|
4303 | }
|
---|
4304 |
|
---|
4305 | /* setup count so the clearing of oldused
|
---|
4306 | * can fall through correctly
|
---|
4307 | */
|
---|
4308 | ix = 1;
|
---|
4309 | }
|
---|
4310 |
|
---|
4311 | /* now zero to oldused */
|
---|
4312 | while (ix++ < oldused) {
|
---|
4313 | *tmpc++ = 0;
|
---|
4314 | }
|
---|
4315 | mp_clamp(c);
|
---|
4316 |
|
---|
4317 | return MP_OKAY;
|
---|
4318 | }
|
---|
4319 |
|
---|
4320 |
|
---|
4321 | /* single digit subtraction */
|
---|
4322 | int mp_sub_d (mp_int * a, mp_digit b, mp_int * c)
|
---|
4323 | {
|
---|
4324 | mp_digit *tmpa, *tmpc, mu;
|
---|
4325 | int res, ix, oldused;
|
---|
4326 |
|
---|
4327 | /* grow c as required */
|
---|
4328 | if (c->alloc < a->used + 1) {
|
---|
4329 | if ((res = mp_grow(c, a->used + 1)) != MP_OKAY) {
|
---|
4330 | return res;
|
---|
4331 | }
|
---|
4332 | }
|
---|
4333 |
|
---|
4334 | /* if a is negative just do an unsigned
|
---|
4335 | * addition [with fudged signs]
|
---|
4336 | */
|
---|
4337 | if (a->sign == MP_NEG) {
|
---|
4338 | a->sign = MP_ZPOS;
|
---|
4339 | res = mp_add_d(a, b, c);
|
---|
4340 | a->sign = c->sign = MP_NEG;
|
---|
4341 |
|
---|
4342 | /* clamp */
|
---|
4343 | mp_clamp(c);
|
---|
4344 |
|
---|
4345 | return res;
|
---|
4346 | }
|
---|
4347 |
|
---|
4348 | /* setup regs */
|
---|
4349 | oldused = c->used;
|
---|
4350 | tmpa = a->dp;
|
---|
4351 | tmpc = c->dp;
|
---|
4352 |
|
---|
4353 | /* if a <= b simply fix the single digit */
|
---|
4354 | if ((a->used == 1 && a->dp[0] <= b) || a->used == 0) {
|
---|
4355 | if (a->used == 1) {
|
---|
4356 | *tmpc++ = b - *tmpa;
|
---|
4357 | } else {
|
---|
4358 | *tmpc++ = b;
|
---|
4359 | }
|
---|
4360 | ix = 1;
|
---|
4361 |
|
---|
4362 | /* negative/1digit */
|
---|
4363 | c->sign = MP_NEG;
|
---|
4364 | c->used = 1;
|
---|
4365 | } else {
|
---|
4366 | /* positive/size */
|
---|
4367 | c->sign = MP_ZPOS;
|
---|
4368 | c->used = a->used;
|
---|
4369 |
|
---|
4370 | /* subtract first digit */
|
---|
4371 | *tmpc = *tmpa++ - b;
|
---|
4372 | mu = *tmpc >> (sizeof(mp_digit) * CHAR_BIT - 1);
|
---|
4373 | *tmpc++ &= MP_MASK;
|
---|
4374 |
|
---|
4375 | /* handle rest of the digits */
|
---|
4376 | for (ix = 1; ix < a->used; ix++) {
|
---|
4377 | *tmpc = *tmpa++ - mu;
|
---|
4378 | mu = *tmpc >> (sizeof(mp_digit) * CHAR_BIT - 1);
|
---|
4379 | *tmpc++ &= MP_MASK;
|
---|
4380 | }
|
---|
4381 | }
|
---|
4382 |
|
---|
4383 | /* zero excess digits */
|
---|
4384 | while (ix++ < oldused) {
|
---|
4385 | *tmpc++ = 0;
|
---|
4386 | }
|
---|
4387 | mp_clamp(c);
|
---|
4388 | return MP_OKAY;
|
---|
4389 | }
|
---|
4390 |
|
---|
4391 | #endif /* defined(HAVE_ECC) || !defined(NO_PWDBASED) */
|
---|
4392 |
|
---|
4393 |
|
---|
4394 | #if defined(WOLFSSL_KEY_GEN) || defined(HAVE_COMP_KEY) || defined(HAVE_ECC) || \
|
---|
4395 | defined(DEBUG_WOLFSSL) || !defined(NO_RSA) || !defined(NO_DSA) || \
|
---|
4396 | !defined(NO_DH)
|
---|
4397 |
|
---|
4398 | static const int lnz[16] = {
|
---|
4399 | 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
|
---|
4400 | };
|
---|
4401 |
|
---|
4402 | /* Counts the number of lsbs which are zero before the first zero bit */
|
---|
4403 | int mp_cnt_lsb(mp_int *a)
|
---|
4404 | {
|
---|
4405 | int x;
|
---|
4406 | mp_digit q = 0, qq;
|
---|
4407 |
|
---|
4408 | /* easy out */
|
---|
4409 | if (mp_iszero(a) == MP_YES) {
|
---|
4410 | return 0;
|
---|
4411 | }
|
---|
4412 |
|
---|
4413 | /* scan lower digits until non-zero */
|
---|
4414 | for (x = 0; x < a->used && a->dp[x] == 0; x++) {}
|
---|
4415 | if (a->dp)
|
---|
4416 | q = a->dp[x];
|
---|
4417 | x *= DIGIT_BIT;
|
---|
4418 |
|
---|
4419 | /* now scan this digit until a 1 is found */
|
---|
4420 | if ((q & 1) == 0) {
|
---|
4421 | do {
|
---|
4422 | qq = q & 15;
|
---|
4423 | x += lnz[qq];
|
---|
4424 | q >>= 4;
|
---|
4425 | } while (qq == 0);
|
---|
4426 | }
|
---|
4427 | return x;
|
---|
4428 | }
|
---|
4429 |
|
---|
4430 |
|
---|
4431 |
|
---|
4432 |
|
---|
4433 | static int s_is_power_of_two(mp_digit b, int *p)
|
---|
4434 | {
|
---|
4435 | int x;
|
---|
4436 |
|
---|
4437 | /* fast return if no power of two */
|
---|
4438 | if ((b==0) || (b & (b-1))) {
|
---|
4439 | return 0;
|
---|
4440 | }
|
---|
4441 |
|
---|
4442 | for (x = 0; x < DIGIT_BIT; x++) {
|
---|
4443 | if (b == (((mp_digit)1)<<x)) {
|
---|
4444 | *p = x;
|
---|
4445 | return 1;
|
---|
4446 | }
|
---|
4447 | }
|
---|
4448 | return 0;
|
---|
4449 | }
|
---|
4450 |
|
---|
4451 | /* single digit division (based on routine from MPI) */
|
---|
4452 | static int mp_div_d (mp_int * a, mp_digit b, mp_int * c, mp_digit * d)
|
---|
4453 | {
|
---|
4454 | mp_int q;
|
---|
4455 | mp_word w;
|
---|
4456 | mp_digit t;
|
---|
4457 | int res = MP_OKAY, ix;
|
---|
4458 |
|
---|
4459 | /* cannot divide by zero */
|
---|
4460 | if (b == 0) {
|
---|
4461 | return MP_VAL;
|
---|
4462 | }
|
---|
4463 |
|
---|
4464 | /* quick outs */
|
---|
4465 | if (b == 1 || mp_iszero(a) == MP_YES) {
|
---|
4466 | if (d != NULL) {
|
---|
4467 | *d = 0;
|
---|
4468 | }
|
---|
4469 | if (c != NULL) {
|
---|
4470 | return mp_copy(a, c);
|
---|
4471 | }
|
---|
4472 | return MP_OKAY;
|
---|
4473 | }
|
---|
4474 |
|
---|
4475 | /* power of two ? */
|
---|
4476 | if (s_is_power_of_two(b, &ix) == 1) {
|
---|
4477 | if (d != NULL) {
|
---|
4478 | *d = a->dp[0] & ((((mp_digit)1)<<ix) - 1);
|
---|
4479 | }
|
---|
4480 | if (c != NULL) {
|
---|
4481 | return mp_div_2d(a, ix, c, NULL);
|
---|
4482 | }
|
---|
4483 | return MP_OKAY;
|
---|
4484 | }
|
---|
4485 |
|
---|
4486 | #ifdef BN_MP_DIV_3_C
|
---|
4487 | /* three? */
|
---|
4488 | if (b == 3) {
|
---|
4489 | return mp_div_3(a, c, d);
|
---|
4490 | }
|
---|
4491 | #endif
|
---|
4492 |
|
---|
4493 | /* no easy answer [c'est la vie]. Just division */
|
---|
4494 | if (c != NULL) {
|
---|
4495 | if ((res = mp_init_size(&q, a->used)) != MP_OKAY) {
|
---|
4496 | return res;
|
---|
4497 | }
|
---|
4498 |
|
---|
4499 | q.used = a->used;
|
---|
4500 | q.sign = a->sign;
|
---|
4501 | }
|
---|
4502 | else {
|
---|
4503 | if ((res = mp_init(&q)) != MP_OKAY) {
|
---|
4504 | return res;
|
---|
4505 | }
|
---|
4506 | }
|
---|
4507 |
|
---|
4508 |
|
---|
4509 | w = 0;
|
---|
4510 | for (ix = a->used - 1; ix >= 0; ix--) {
|
---|
4511 | w = (w << ((mp_word)DIGIT_BIT)) | ((mp_word)a->dp[ix]);
|
---|
4512 |
|
---|
4513 | if (w >= b) {
|
---|
4514 | t = (mp_digit)(w / b);
|
---|
4515 | w -= ((mp_word)t) * ((mp_word)b);
|
---|
4516 | } else {
|
---|
4517 | t = 0;
|
---|
4518 | }
|
---|
4519 | if (c != NULL)
|
---|
4520 | q.dp[ix] = (mp_digit)t;
|
---|
4521 | }
|
---|
4522 |
|
---|
4523 | if (d != NULL) {
|
---|
4524 | *d = (mp_digit)w;
|
---|
4525 | }
|
---|
4526 |
|
---|
4527 | if (c != NULL) {
|
---|
4528 | mp_clamp(&q);
|
---|
4529 | mp_exch(&q, c);
|
---|
4530 | }
|
---|
4531 | mp_clear(&q);
|
---|
4532 |
|
---|
4533 | return res;
|
---|
4534 | }
|
---|
4535 |
|
---|
4536 |
|
---|
4537 | int mp_mod_d (mp_int * a, mp_digit b, mp_digit * c)
|
---|
4538 | {
|
---|
4539 | return mp_div_d(a, b, NULL, c);
|
---|
4540 | }
|
---|
4541 |
|
---|
4542 | #endif /* WOLFSSL_KEY_GEN || HAVE_COMP_KEY || HAVE_ECC || DEBUG_WOLFSSL */
|
---|
4543 |
|
---|
4544 | #if defined(WOLFSSL_KEY_GEN) || !defined(NO_DH) || !defined(NO_DSA) || !defined(NO_RSA)
|
---|
4545 |
|
---|
4546 | const mp_digit ltm_prime_tab[PRIME_SIZE] = {
|
---|
4547 | 0x0002, 0x0003, 0x0005, 0x0007, 0x000B, 0x000D, 0x0011, 0x0013,
|
---|
4548 | 0x0017, 0x001D, 0x001F, 0x0025, 0x0029, 0x002B, 0x002F, 0x0035,
|
---|
4549 | 0x003B, 0x003D, 0x0043, 0x0047, 0x0049, 0x004F, 0x0053, 0x0059,
|
---|
4550 | 0x0061, 0x0065, 0x0067, 0x006B, 0x006D, 0x0071, 0x007F,
|
---|
4551 | #ifndef MP_8BIT
|
---|
4552 | 0x0083,
|
---|
4553 | 0x0089, 0x008B, 0x0095, 0x0097, 0x009D, 0x00A3, 0x00A7, 0x00AD,
|
---|
4554 | 0x00B3, 0x00B5, 0x00BF, 0x00C1, 0x00C5, 0x00C7, 0x00D3, 0x00DF,
|
---|
4555 | 0x00E3, 0x00E5, 0x00E9, 0x00EF, 0x00F1, 0x00FB, 0x0101, 0x0107,
|
---|
4556 | 0x010D, 0x010F, 0x0115, 0x0119, 0x011B, 0x0125, 0x0133, 0x0137,
|
---|
4557 |
|
---|
4558 | 0x0139, 0x013D, 0x014B, 0x0151, 0x015B, 0x015D, 0x0161, 0x0167,
|
---|
4559 | 0x016F, 0x0175, 0x017B, 0x017F, 0x0185, 0x018D, 0x0191, 0x0199,
|
---|
4560 | 0x01A3, 0x01A5, 0x01AF, 0x01B1, 0x01B7, 0x01BB, 0x01C1, 0x01C9,
|
---|
4561 | 0x01CD, 0x01CF, 0x01D3, 0x01DF, 0x01E7, 0x01EB, 0x01F3, 0x01F7,
|
---|
4562 | 0x01FD, 0x0209, 0x020B, 0x021D, 0x0223, 0x022D, 0x0233, 0x0239,
|
---|
4563 | 0x023B, 0x0241, 0x024B, 0x0251, 0x0257, 0x0259, 0x025F, 0x0265,
|
---|
4564 | 0x0269, 0x026B, 0x0277, 0x0281, 0x0283, 0x0287, 0x028D, 0x0293,
|
---|
4565 | 0x0295, 0x02A1, 0x02A5, 0x02AB, 0x02B3, 0x02BD, 0x02C5, 0x02CF,
|
---|
4566 |
|
---|
4567 | 0x02D7, 0x02DD, 0x02E3, 0x02E7, 0x02EF, 0x02F5, 0x02F9, 0x0301,
|
---|
4568 | 0x0305, 0x0313, 0x031D, 0x0329, 0x032B, 0x0335, 0x0337, 0x033B,
|
---|
4569 | 0x033D, 0x0347, 0x0355, 0x0359, 0x035B, 0x035F, 0x036D, 0x0371,
|
---|
4570 | 0x0373, 0x0377, 0x038B, 0x038F, 0x0397, 0x03A1, 0x03A9, 0x03AD,
|
---|
4571 | 0x03B3, 0x03B9, 0x03C7, 0x03CB, 0x03D1, 0x03D7, 0x03DF, 0x03E5,
|
---|
4572 | 0x03F1, 0x03F5, 0x03FB, 0x03FD, 0x0407, 0x0409, 0x040F, 0x0419,
|
---|
4573 | 0x041B, 0x0425, 0x0427, 0x042D, 0x043F, 0x0443, 0x0445, 0x0449,
|
---|
4574 | 0x044F, 0x0455, 0x045D, 0x0463, 0x0469, 0x047F, 0x0481, 0x048B,
|
---|
4575 |
|
---|
4576 | 0x0493, 0x049D, 0x04A3, 0x04A9, 0x04B1, 0x04BD, 0x04C1, 0x04C7,
|
---|
4577 | 0x04CD, 0x04CF, 0x04D5, 0x04E1, 0x04EB, 0x04FD, 0x04FF, 0x0503,
|
---|
4578 | 0x0509, 0x050B, 0x0511, 0x0515, 0x0517, 0x051B, 0x0527, 0x0529,
|
---|
4579 | 0x052F, 0x0551, 0x0557, 0x055D, 0x0565, 0x0577, 0x0581, 0x058F,
|
---|
4580 | 0x0593, 0x0595, 0x0599, 0x059F, 0x05A7, 0x05AB, 0x05AD, 0x05B3,
|
---|
4581 | 0x05BF, 0x05C9, 0x05CB, 0x05CF, 0x05D1, 0x05D5, 0x05DB, 0x05E7,
|
---|
4582 | 0x05F3, 0x05FB, 0x0607, 0x060D, 0x0611, 0x0617, 0x061F, 0x0623,
|
---|
4583 | 0x062B, 0x062F, 0x063D, 0x0641, 0x0647, 0x0649, 0x064D, 0x0653
|
---|
4584 | #endif
|
---|
4585 | };
|
---|
4586 |
|
---|
4587 |
|
---|
4588 | /* Miller-Rabin test of "a" to the base of "b" as described in
|
---|
4589 | * HAC pp. 139 Algorithm 4.24
|
---|
4590 | *
|
---|
4591 | * Sets result to 0 if definitely composite or 1 if probably prime.
|
---|
4592 | * Randomly the chance of error is no more than 1/4 and often
|
---|
4593 | * very much lower.
|
---|
4594 | */
|
---|
4595 | static int mp_prime_miller_rabin (mp_int * a, mp_int * b, int *result)
|
---|
4596 | {
|
---|
4597 | mp_int n1, y, r;
|
---|
4598 | int s, j, err;
|
---|
4599 |
|
---|
4600 | /* default */
|
---|
4601 | *result = MP_NO;
|
---|
4602 |
|
---|
4603 | /* ensure b > 1 */
|
---|
4604 | if (mp_cmp_d(b, 1) != MP_GT) {
|
---|
4605 | return MP_VAL;
|
---|
4606 | }
|
---|
4607 |
|
---|
4608 | /* get n1 = a - 1 */
|
---|
4609 | if ((err = mp_init_copy (&n1, a)) != MP_OKAY) {
|
---|
4610 | return err;
|
---|
4611 | }
|
---|
4612 | if ((err = mp_sub_d (&n1, 1, &n1)) != MP_OKAY) {
|
---|
4613 | goto LBL_N1;
|
---|
4614 | }
|
---|
4615 |
|
---|
4616 | /* set 2**s * r = n1 */
|
---|
4617 | if ((err = mp_init_copy (&r, &n1)) != MP_OKAY) {
|
---|
4618 | goto LBL_N1;
|
---|
4619 | }
|
---|
4620 |
|
---|
4621 | /* count the number of least significant bits
|
---|
4622 | * which are zero
|
---|
4623 | */
|
---|
4624 | s = mp_cnt_lsb(&r);
|
---|
4625 |
|
---|
4626 | /* now divide n - 1 by 2**s */
|
---|
4627 | if ((err = mp_div_2d (&r, s, &r, NULL)) != MP_OKAY) {
|
---|
4628 | goto LBL_R;
|
---|
4629 | }
|
---|
4630 |
|
---|
4631 | /* compute y = b**r mod a */
|
---|
4632 | if ((err = mp_init (&y)) != MP_OKAY) {
|
---|
4633 | goto LBL_R;
|
---|
4634 | }
|
---|
4635 | #if defined(WOLFSSL_HAVE_SP_RSA) || defined(WOLFSSL_HAVE_SP_DH)
|
---|
4636 | #ifndef WOLFSSL_SP_NO_2048
|
---|
4637 | if (mp_count_bits(a) == 1024)
|
---|
4638 | err = sp_ModExp_1024(b, &r, a, &y);
|
---|
4639 | else if (mp_count_bits(a) == 2048)
|
---|
4640 | err = sp_ModExp_2048(b, &r, a, &y);
|
---|
4641 | else
|
---|
4642 | #endif
|
---|
4643 | #ifndef WOLFSSL_SP_NO_3072
|
---|
4644 | if (mp_count_bits(a) == 1536)
|
---|
4645 | err = sp_ModExp_1536(b, &r, a, &y);
|
---|
4646 | else if (mp_count_bits(a) == 3072)
|
---|
4647 | err = sp_ModExp_3072(b, &r, a, &y);
|
---|
4648 | else
|
---|
4649 | #endif
|
---|
4650 | #ifdef WOLFSSL_SP_4096
|
---|
4651 | if (mp_count_bits(a) == 4096)
|
---|
4652 | err = sp_ModExp_4096(b, &r, a, &y);
|
---|
4653 | else
|
---|
4654 | #endif
|
---|
4655 | #endif
|
---|
4656 | err = mp_exptmod (b, &r, a, &y);
|
---|
4657 | if (err != MP_OKAY)
|
---|
4658 | goto LBL_Y;
|
---|
4659 |
|
---|
4660 | /* if y != 1 and y != n1 do */
|
---|
4661 | if (mp_cmp_d (&y, 1) != MP_EQ && mp_cmp (&y, &n1) != MP_EQ) {
|
---|
4662 | j = 1;
|
---|
4663 | /* while j <= s-1 and y != n1 */
|
---|
4664 | while ((j <= (s - 1)) && mp_cmp (&y, &n1) != MP_EQ) {
|
---|
4665 | if ((err = mp_sqrmod (&y, a, &y)) != MP_OKAY) {
|
---|
4666 | goto LBL_Y;
|
---|
4667 | }
|
---|
4668 |
|
---|
4669 | /* if y == 1 then composite */
|
---|
4670 | if (mp_cmp_d (&y, 1) == MP_EQ) {
|
---|
4671 | goto LBL_Y;
|
---|
4672 | }
|
---|
4673 |
|
---|
4674 | ++j;
|
---|
4675 | }
|
---|
4676 |
|
---|
4677 | /* if y != n1 then composite */
|
---|
4678 | if (mp_cmp (&y, &n1) != MP_EQ) {
|
---|
4679 | goto LBL_Y;
|
---|
4680 | }
|
---|
4681 | }
|
---|
4682 |
|
---|
4683 | /* probably prime now */
|
---|
4684 | *result = MP_YES;
|
---|
4685 | LBL_Y:mp_clear (&y);
|
---|
4686 | LBL_R:mp_clear (&r);
|
---|
4687 | LBL_N1:mp_clear (&n1);
|
---|
4688 | return err;
|
---|
4689 | }
|
---|
4690 |
|
---|
4691 |
|
---|
4692 | /* determines if an integers is divisible by one
|
---|
4693 | * of the first PRIME_SIZE primes or not
|
---|
4694 | *
|
---|
4695 | * sets result to 0 if not, 1 if yes
|
---|
4696 | */
|
---|
4697 | static int mp_prime_is_divisible (mp_int * a, int *result)
|
---|
4698 | {
|
---|
4699 | int err, ix;
|
---|
4700 | mp_digit res;
|
---|
4701 |
|
---|
4702 | /* default to not */
|
---|
4703 | *result = MP_NO;
|
---|
4704 |
|
---|
4705 | for (ix = 0; ix < PRIME_SIZE; ix++) {
|
---|
4706 | /* what is a mod LBL_prime_tab[ix] */
|
---|
4707 | if ((err = mp_mod_d (a, ltm_prime_tab[ix], &res)) != MP_OKAY) {
|
---|
4708 | return err;
|
---|
4709 | }
|
---|
4710 |
|
---|
4711 | /* is the residue zero? */
|
---|
4712 | if (res == 0) {
|
---|
4713 | *result = MP_YES;
|
---|
4714 | return MP_OKAY;
|
---|
4715 | }
|
---|
4716 | }
|
---|
4717 |
|
---|
4718 | return MP_OKAY;
|
---|
4719 | }
|
---|
4720 |
|
---|
4721 | /*
|
---|
4722 | * Sets result to 1 if probably prime, 0 otherwise
|
---|
4723 | */
|
---|
4724 | int mp_prime_is_prime (mp_int * a, int t, int *result)
|
---|
4725 | {
|
---|
4726 | mp_int b;
|
---|
4727 | int ix, err, res;
|
---|
4728 |
|
---|
4729 | /* default to no */
|
---|
4730 | *result = MP_NO;
|
---|
4731 |
|
---|
4732 | /* valid value of t? */
|
---|
4733 | if (t <= 0 || t > PRIME_SIZE) {
|
---|
4734 | return MP_VAL;
|
---|
4735 | }
|
---|
4736 |
|
---|
4737 | if (mp_isone(a)) {
|
---|
4738 | *result = MP_NO;
|
---|
4739 | return MP_OKAY;
|
---|
4740 | }
|
---|
4741 |
|
---|
4742 | /* is the input equal to one of the primes in the table? */
|
---|
4743 | for (ix = 0; ix < PRIME_SIZE; ix++) {
|
---|
4744 | if (mp_cmp_d(a, ltm_prime_tab[ix]) == MP_EQ) {
|
---|
4745 | *result = MP_YES;
|
---|
4746 | return MP_OKAY;
|
---|
4747 | }
|
---|
4748 | }
|
---|
4749 |
|
---|
4750 | /* first perform trial division */
|
---|
4751 | if ((err = mp_prime_is_divisible (a, &res)) != MP_OKAY) {
|
---|
4752 | return err;
|
---|
4753 | }
|
---|
4754 |
|
---|
4755 | /* return if it was trivially divisible */
|
---|
4756 | if (res == MP_YES) {
|
---|
4757 | return MP_OKAY;
|
---|
4758 | }
|
---|
4759 |
|
---|
4760 | /* now perform the miller-rabin rounds */
|
---|
4761 | if ((err = mp_init (&b)) != MP_OKAY) {
|
---|
4762 | return err;
|
---|
4763 | }
|
---|
4764 |
|
---|
4765 | for (ix = 0; ix < t; ix++) {
|
---|
4766 | /* set the prime */
|
---|
4767 | if ((err = mp_set (&b, ltm_prime_tab[ix])) != MP_OKAY) {
|
---|
4768 | goto LBL_B;
|
---|
4769 | }
|
---|
4770 |
|
---|
4771 | if ((err = mp_prime_miller_rabin (a, &b, &res)) != MP_OKAY) {
|
---|
4772 | goto LBL_B;
|
---|
4773 | }
|
---|
4774 |
|
---|
4775 | if (res == MP_NO) {
|
---|
4776 | goto LBL_B;
|
---|
4777 | }
|
---|
4778 | }
|
---|
4779 |
|
---|
4780 | /* passed the test */
|
---|
4781 | *result = MP_YES;
|
---|
4782 | LBL_B:mp_clear (&b);
|
---|
4783 | return err;
|
---|
4784 | }
|
---|
4785 |
|
---|
4786 |
|
---|
4787 | /*
|
---|
4788 | * Sets result to 1 if probably prime, 0 otherwise
|
---|
4789 | */
|
---|
4790 | int mp_prime_is_prime_ex (mp_int * a, int t, int *result, WC_RNG *rng)
|
---|
4791 | {
|
---|
4792 | mp_int b, c;
|
---|
4793 | int ix, err, res;
|
---|
4794 | byte* base = NULL;
|
---|
4795 | word32 baseSz = 0;
|
---|
4796 |
|
---|
4797 | /* default to no */
|
---|
4798 | *result = MP_NO;
|
---|
4799 |
|
---|
4800 | /* valid value of t? */
|
---|
4801 | if (t <= 0 || t > PRIME_SIZE) {
|
---|
4802 | return MP_VAL;
|
---|
4803 | }
|
---|
4804 |
|
---|
4805 | if (mp_isone(a)) {
|
---|
4806 | *result = MP_NO;
|
---|
4807 | return MP_OKAY;
|
---|
4808 | }
|
---|
4809 |
|
---|
4810 | /* is the input equal to one of the primes in the table? */
|
---|
4811 | for (ix = 0; ix < PRIME_SIZE; ix++) {
|
---|
4812 | if (mp_cmp_d(a, ltm_prime_tab[ix]) == MP_EQ) {
|
---|
4813 | *result = MP_YES;
|
---|
4814 | return MP_OKAY;
|
---|
4815 | }
|
---|
4816 | }
|
---|
4817 |
|
---|
4818 | /* first perform trial division */
|
---|
4819 | if ((err = mp_prime_is_divisible (a, &res)) != MP_OKAY) {
|
---|
4820 | return err;
|
---|
4821 | }
|
---|
4822 |
|
---|
4823 | /* return if it was trivially divisible */
|
---|
4824 | if (res == MP_YES) {
|
---|
4825 | return MP_OKAY;
|
---|
4826 | }
|
---|
4827 |
|
---|
4828 | /* now perform the miller-rabin rounds */
|
---|
4829 | if ((err = mp_init (&b)) != MP_OKAY) {
|
---|
4830 | return err;
|
---|
4831 | }
|
---|
4832 | if ((err = mp_init (&c)) != MP_OKAY) {
|
---|
4833 | mp_clear(&b);
|
---|
4834 | return err;
|
---|
4835 | }
|
---|
4836 |
|
---|
4837 | baseSz = mp_count_bits(a);
|
---|
4838 | baseSz = (baseSz / 8) + ((baseSz % 8) ? 1 : 0);
|
---|
4839 |
|
---|
4840 | base = (byte*)XMALLOC(baseSz, NULL, DYNAMIC_TYPE_TMP_BUFFER);
|
---|
4841 | if (base == NULL) {
|
---|
4842 | err = MP_MEM;
|
---|
4843 | goto LBL_B;
|
---|
4844 | }
|
---|
4845 |
|
---|
4846 | if ((err = mp_sub_d(a, 2, &c)) != MP_OKAY) {
|
---|
4847 | goto LBL_B;
|
---|
4848 | }
|
---|
4849 |
|
---|
4850 | /* now do a miller rabin with up to t random numbers, this should
|
---|
4851 | * give a (1/4)^t chance of a false prime. */
|
---|
4852 | for (ix = 0; ix < t; ix++) {
|
---|
4853 | /* Set a test candidate. */
|
---|
4854 | if ((err = wc_RNG_GenerateBlock(rng, base, baseSz)) != 0) {
|
---|
4855 | goto LBL_B;
|
---|
4856 | }
|
---|
4857 |
|
---|
4858 | if ((err = mp_read_unsigned_bin(&b, base, baseSz)) != MP_OKAY) {
|
---|
4859 | goto LBL_B;
|
---|
4860 | }
|
---|
4861 |
|
---|
4862 | if (mp_cmp_d(&b, 2) != MP_GT || mp_cmp(&b, &c) != MP_LT) {
|
---|
4863 | ix--;
|
---|
4864 | continue;
|
---|
4865 | }
|
---|
4866 |
|
---|
4867 | if ((err = mp_prime_miller_rabin (a, &b, &res)) != MP_OKAY) {
|
---|
4868 | goto LBL_B;
|
---|
4869 | }
|
---|
4870 |
|
---|
4871 | if (res == MP_NO) {
|
---|
4872 | goto LBL_B;
|
---|
4873 | }
|
---|
4874 | }
|
---|
4875 |
|
---|
4876 | /* passed the test */
|
---|
4877 | *result = MP_YES;
|
---|
4878 | LBL_B:mp_clear (&b);
|
---|
4879 | mp_clear (&c);
|
---|
4880 | XFREE(base, NULL, DYNAMIC_TYPE_TMP_BUFFER);
|
---|
4881 | return err;
|
---|
4882 | }
|
---|
4883 |
|
---|
4884 | #endif /* WOLFSSL_KEY_GEN NO_DH NO_DSA NO_RSA */
|
---|
4885 |
|
---|
4886 | #ifdef WOLFSSL_KEY_GEN
|
---|
4887 |
|
---|
4888 | static const int USE_BBS = 1;
|
---|
4889 |
|
---|
4890 | int mp_rand_prime(mp_int* N, int len, WC_RNG* rng, void* heap)
|
---|
4891 | {
|
---|
4892 | int err, res, type;
|
---|
4893 | byte* buf;
|
---|
4894 |
|
---|
4895 | if (N == NULL || rng == NULL)
|
---|
4896 | return MP_VAL;
|
---|
4897 |
|
---|
4898 | /* get type */
|
---|
4899 | if (len < 0) {
|
---|
4900 | type = USE_BBS;
|
---|
4901 | len = -len;
|
---|
4902 | } else {
|
---|
4903 | type = 0;
|
---|
4904 | }
|
---|
4905 |
|
---|
4906 | /* allow sizes between 2 and 512 bytes for a prime size */
|
---|
4907 | if (len < 2 || len > 512) {
|
---|
4908 | return MP_VAL;
|
---|
4909 | }
|
---|
4910 |
|
---|
4911 | /* allocate buffer to work with */
|
---|
4912 | buf = (byte*)XMALLOC(len, heap, DYNAMIC_TYPE_RSA);
|
---|
4913 | if (buf == NULL) {
|
---|
4914 | return MP_MEM;
|
---|
4915 | }
|
---|
4916 | XMEMSET(buf, 0, len);
|
---|
4917 |
|
---|
4918 | do {
|
---|
4919 | #ifdef SHOW_GEN
|
---|
4920 | printf(".");
|
---|
4921 | fflush(stdout);
|
---|
4922 | #endif
|
---|
4923 | /* generate value */
|
---|
4924 | err = wc_RNG_GenerateBlock(rng, buf, len);
|
---|
4925 | if (err != 0) {
|
---|
4926 | XFREE(buf, heap, DYNAMIC_TYPE_RSA);
|
---|
4927 | return err;
|
---|
4928 | }
|
---|
4929 |
|
---|
4930 | /* munge bits */
|
---|
4931 | buf[0] |= 0x80 | 0x40;
|
---|
4932 | buf[len-1] |= 0x01 | ((type & USE_BBS) ? 0x02 : 0x00);
|
---|
4933 |
|
---|
4934 | /* load value */
|
---|
4935 | if ((err = mp_read_unsigned_bin(N, buf, len)) != MP_OKAY) {
|
---|
4936 | XFREE(buf, heap, DYNAMIC_TYPE_RSA);
|
---|
4937 | return err;
|
---|
4938 | }
|
---|
4939 |
|
---|
4940 | /* test */
|
---|
4941 | /* Running Miller-Rabin up to 3 times gives us a 2^{-80} chance
|
---|
4942 | * of a 1024-bit candidate being a false positive, when it is our
|
---|
4943 | * prime candidate. (Note 4.49 of Handbook of Applied Cryptography.)
|
---|
4944 | * Using 8 because we've always used 8. */
|
---|
4945 | if ((err = mp_prime_is_prime_ex(N, 8, &res, rng)) != MP_OKAY) {
|
---|
4946 | XFREE(buf, heap, DYNAMIC_TYPE_RSA);
|
---|
4947 | return err;
|
---|
4948 | }
|
---|
4949 | } while (res == MP_NO);
|
---|
4950 |
|
---|
4951 | XMEMSET(buf, 0, len);
|
---|
4952 | XFREE(buf, heap, DYNAMIC_TYPE_RSA);
|
---|
4953 |
|
---|
4954 | return MP_OKAY;
|
---|
4955 | }
|
---|
4956 |
|
---|
4957 |
|
---|
4958 | /* computes least common multiple as |a*b|/(a, b) */
|
---|
4959 | int mp_lcm (mp_int * a, mp_int * b, mp_int * c)
|
---|
4960 | {
|
---|
4961 | int res;
|
---|
4962 | mp_int t1, t2;
|
---|
4963 |
|
---|
4964 |
|
---|
4965 | if ((res = mp_init_multi (&t1, &t2, NULL, NULL, NULL, NULL)) != MP_OKAY) {
|
---|
4966 | return res;
|
---|
4967 | }
|
---|
4968 |
|
---|
4969 | /* t1 = get the GCD of the two inputs */
|
---|
4970 | if ((res = mp_gcd (a, b, &t1)) != MP_OKAY) {
|
---|
4971 | goto LBL_T;
|
---|
4972 | }
|
---|
4973 |
|
---|
4974 | /* divide the smallest by the GCD */
|
---|
4975 | if (mp_cmp_mag(a, b) == MP_LT) {
|
---|
4976 | /* store quotient in t2 such that t2 * b is the LCM */
|
---|
4977 | if ((res = mp_div(a, &t1, &t2, NULL)) != MP_OKAY) {
|
---|
4978 | goto LBL_T;
|
---|
4979 | }
|
---|
4980 | res = mp_mul(b, &t2, c);
|
---|
4981 | } else {
|
---|
4982 | /* store quotient in t2 such that t2 * a is the LCM */
|
---|
4983 | if ((res = mp_div(b, &t1, &t2, NULL)) != MP_OKAY) {
|
---|
4984 | goto LBL_T;
|
---|
4985 | }
|
---|
4986 | res = mp_mul(a, &t2, c);
|
---|
4987 | }
|
---|
4988 |
|
---|
4989 | /* fix the sign to positive */
|
---|
4990 | c->sign = MP_ZPOS;
|
---|
4991 |
|
---|
4992 | LBL_T:
|
---|
4993 | mp_clear(&t1);
|
---|
4994 | mp_clear(&t2);
|
---|
4995 | return res;
|
---|
4996 | }
|
---|
4997 |
|
---|
4998 |
|
---|
4999 |
|
---|
5000 | /* Greatest Common Divisor using the binary method */
|
---|
5001 | int mp_gcd (mp_int * a, mp_int * b, mp_int * c)
|
---|
5002 | {
|
---|
5003 | mp_int u, v;
|
---|
5004 | int k, u_lsb, v_lsb, res;
|
---|
5005 |
|
---|
5006 | /* either zero than gcd is the largest */
|
---|
5007 | if (mp_iszero (a) == MP_YES) {
|
---|
5008 | return mp_abs (b, c);
|
---|
5009 | }
|
---|
5010 | if (mp_iszero (b) == MP_YES) {
|
---|
5011 | return mp_abs (a, c);
|
---|
5012 | }
|
---|
5013 |
|
---|
5014 | /* get copies of a and b we can modify */
|
---|
5015 | if ((res = mp_init_copy (&u, a)) != MP_OKAY) {
|
---|
5016 | return res;
|
---|
5017 | }
|
---|
5018 |
|
---|
5019 | if ((res = mp_init_copy (&v, b)) != MP_OKAY) {
|
---|
5020 | goto LBL_U;
|
---|
5021 | }
|
---|
5022 |
|
---|
5023 | /* must be positive for the remainder of the algorithm */
|
---|
5024 | u.sign = v.sign = MP_ZPOS;
|
---|
5025 |
|
---|
5026 | /* B1. Find the common power of two for u and v */
|
---|
5027 | u_lsb = mp_cnt_lsb(&u);
|
---|
5028 | v_lsb = mp_cnt_lsb(&v);
|
---|
5029 | k = MIN(u_lsb, v_lsb);
|
---|
5030 |
|
---|
5031 | if (k > 0) {
|
---|
5032 | /* divide the power of two out */
|
---|
5033 | if ((res = mp_div_2d(&u, k, &u, NULL)) != MP_OKAY) {
|
---|
5034 | goto LBL_V;
|
---|
5035 | }
|
---|
5036 |
|
---|
5037 | if ((res = mp_div_2d(&v, k, &v, NULL)) != MP_OKAY) {
|
---|
5038 | goto LBL_V;
|
---|
5039 | }
|
---|
5040 | }
|
---|
5041 |
|
---|
5042 | /* divide any remaining factors of two out */
|
---|
5043 | if (u_lsb != k) {
|
---|
5044 | if ((res = mp_div_2d(&u, u_lsb - k, &u, NULL)) != MP_OKAY) {
|
---|
5045 | goto LBL_V;
|
---|
5046 | }
|
---|
5047 | }
|
---|
5048 |
|
---|
5049 | if (v_lsb != k) {
|
---|
5050 | if ((res = mp_div_2d(&v, v_lsb - k, &v, NULL)) != MP_OKAY) {
|
---|
5051 | goto LBL_V;
|
---|
5052 | }
|
---|
5053 | }
|
---|
5054 |
|
---|
5055 | while (mp_iszero(&v) == MP_NO) {
|
---|
5056 | /* make sure v is the largest */
|
---|
5057 | if (mp_cmp_mag(&u, &v) == MP_GT) {
|
---|
5058 | /* swap u and v to make sure v is >= u */
|
---|
5059 | mp_exch(&u, &v);
|
---|
5060 | }
|
---|
5061 |
|
---|
5062 | /* subtract smallest from largest */
|
---|
5063 | if ((res = s_mp_sub(&v, &u, &v)) != MP_OKAY) {
|
---|
5064 | goto LBL_V;
|
---|
5065 | }
|
---|
5066 |
|
---|
5067 | /* Divide out all factors of two */
|
---|
5068 | if ((res = mp_div_2d(&v, mp_cnt_lsb(&v), &v, NULL)) != MP_OKAY) {
|
---|
5069 | goto LBL_V;
|
---|
5070 | }
|
---|
5071 | }
|
---|
5072 |
|
---|
5073 | /* multiply by 2**k which we divided out at the beginning */
|
---|
5074 | if ((res = mp_mul_2d (&u, k, c)) != MP_OKAY) {
|
---|
5075 | goto LBL_V;
|
---|
5076 | }
|
---|
5077 | c->sign = MP_ZPOS;
|
---|
5078 | res = MP_OKAY;
|
---|
5079 | LBL_V:mp_clear (&v);
|
---|
5080 | LBL_U:mp_clear (&u);
|
---|
5081 | return res;
|
---|
5082 | }
|
---|
5083 |
|
---|
5084 | #endif /* WOLFSSL_KEY_GEN */
|
---|
5085 |
|
---|
5086 |
|
---|
5087 | #if !defined(NO_DSA) || defined(HAVE_ECC) || defined(WOLFSSL_KEY_GEN) || \
|
---|
5088 | defined(HAVE_COMP_KEY) || defined(WOLFSSL_DEBUG_MATH) || \
|
---|
5089 | defined(DEBUG_WOLFSSL) || defined(OPENSSL_EXTRA)
|
---|
5090 |
|
---|
5091 | /* chars used in radix conversions */
|
---|
5092 | const char *mp_s_rmap = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ\
|
---|
5093 | abcdefghijklmnopqrstuvwxyz+/";
|
---|
5094 | #endif
|
---|
5095 |
|
---|
5096 | #if !defined(NO_DSA) || defined(HAVE_ECC)
|
---|
5097 | /* read a string [ASCII] in a given radix */
|
---|
5098 | int mp_read_radix (mp_int * a, const char *str, int radix)
|
---|
5099 | {
|
---|
5100 | int y, res, neg;
|
---|
5101 | char ch;
|
---|
5102 |
|
---|
5103 | /* zero the digit bignum */
|
---|
5104 | mp_zero(a);
|
---|
5105 |
|
---|
5106 | /* make sure the radix is ok */
|
---|
5107 | if (radix < MP_RADIX_BIN || radix > MP_RADIX_MAX) {
|
---|
5108 | return MP_VAL;
|
---|
5109 | }
|
---|
5110 |
|
---|
5111 | /* if the leading digit is a
|
---|
5112 | * minus set the sign to negative.
|
---|
5113 | */
|
---|
5114 | if (*str == '-') {
|
---|
5115 | ++str;
|
---|
5116 | neg = MP_NEG;
|
---|
5117 | } else {
|
---|
5118 | neg = MP_ZPOS;
|
---|
5119 | }
|
---|
5120 |
|
---|
5121 | /* set the integer to the default of zero */
|
---|
5122 | mp_zero (a);
|
---|
5123 |
|
---|
5124 | /* process each digit of the string */
|
---|
5125 | while (*str != '\0') {
|
---|
5126 | /* if the radix <= 36 the conversion is case insensitive
|
---|
5127 | * this allows numbers like 1AB and 1ab to represent the same value
|
---|
5128 | * [e.g. in hex]
|
---|
5129 | */
|
---|
5130 | ch = (radix <= 36) ? (char)XTOUPPER((unsigned char)*str) : *str;
|
---|
5131 | for (y = 0; y < 64; y++) {
|
---|
5132 | if (ch == mp_s_rmap[y]) {
|
---|
5133 | break;
|
---|
5134 | }
|
---|
5135 | }
|
---|
5136 |
|
---|
5137 | /* if the char was found in the map
|
---|
5138 | * and is less than the given radix add it
|
---|
5139 | * to the number, otherwise exit the loop.
|
---|
5140 | */
|
---|
5141 | if (y < radix) {
|
---|
5142 | if ((res = mp_mul_d (a, (mp_digit) radix, a)) != MP_OKAY) {
|
---|
5143 | return res;
|
---|
5144 | }
|
---|
5145 | if ((res = mp_add_d (a, (mp_digit) y, a)) != MP_OKAY) {
|
---|
5146 | return res;
|
---|
5147 | }
|
---|
5148 | } else {
|
---|
5149 | break;
|
---|
5150 | }
|
---|
5151 | ++str;
|
---|
5152 | }
|
---|
5153 |
|
---|
5154 | /* if digit in isn't null term, then invalid character was found */
|
---|
5155 | if (*str != '\0') {
|
---|
5156 | mp_zero (a);
|
---|
5157 | return MP_VAL;
|
---|
5158 | }
|
---|
5159 |
|
---|
5160 | /* set the sign only if a != 0 */
|
---|
5161 | if (mp_iszero(a) != MP_YES) {
|
---|
5162 | a->sign = neg;
|
---|
5163 | }
|
---|
5164 | return MP_OKAY;
|
---|
5165 | }
|
---|
5166 | #endif /* !defined(NO_DSA) || defined(HAVE_ECC) */
|
---|
5167 |
|
---|
5168 | #ifdef WC_MP_TO_RADIX
|
---|
5169 |
|
---|
5170 | /* returns size of ASCII representation */
|
---|
5171 | int mp_radix_size (mp_int *a, int radix, int *size)
|
---|
5172 | {
|
---|
5173 | int res, digs;
|
---|
5174 | mp_int t;
|
---|
5175 | mp_digit d;
|
---|
5176 |
|
---|
5177 | *size = 0;
|
---|
5178 |
|
---|
5179 | /* special case for binary */
|
---|
5180 | if (radix == MP_RADIX_BIN) {
|
---|
5181 | *size = mp_count_bits (a) + (a->sign == MP_NEG ? 1 : 0) + 1;
|
---|
5182 | return MP_OKAY;
|
---|
5183 | }
|
---|
5184 |
|
---|
5185 | /* make sure the radix is in range */
|
---|
5186 | if (radix < MP_RADIX_BIN || radix > MP_RADIX_MAX) {
|
---|
5187 | return MP_VAL;
|
---|
5188 | }
|
---|
5189 |
|
---|
5190 | if (mp_iszero(a) == MP_YES) {
|
---|
5191 | *size = 2;
|
---|
5192 | return MP_OKAY;
|
---|
5193 | }
|
---|
5194 |
|
---|
5195 | /* digs is the digit count */
|
---|
5196 | digs = 0;
|
---|
5197 |
|
---|
5198 | /* if it's negative add one for the sign */
|
---|
5199 | if (a->sign == MP_NEG) {
|
---|
5200 | ++digs;
|
---|
5201 | }
|
---|
5202 |
|
---|
5203 | /* init a copy of the input */
|
---|
5204 | if ((res = mp_init_copy (&t, a)) != MP_OKAY) {
|
---|
5205 | return res;
|
---|
5206 | }
|
---|
5207 |
|
---|
5208 | /* force temp to positive */
|
---|
5209 | t.sign = MP_ZPOS;
|
---|
5210 |
|
---|
5211 | /* fetch out all of the digits */
|
---|
5212 | while (mp_iszero (&t) == MP_NO) {
|
---|
5213 | if ((res = mp_div_d (&t, (mp_digit) radix, &t, &d)) != MP_OKAY) {
|
---|
5214 | mp_clear (&t);
|
---|
5215 | return res;
|
---|
5216 | }
|
---|
5217 | ++digs;
|
---|
5218 | }
|
---|
5219 | mp_clear (&t);
|
---|
5220 |
|
---|
5221 | /* return digs + 1, the 1 is for the NULL byte that would be required. */
|
---|
5222 | *size = digs + 1;
|
---|
5223 | return MP_OKAY;
|
---|
5224 | }
|
---|
5225 |
|
---|
5226 | /* stores a bignum as a ASCII string in a given radix (2..64) */
|
---|
5227 | int mp_toradix (mp_int *a, char *str, int radix)
|
---|
5228 | {
|
---|
5229 | int res, digs;
|
---|
5230 | mp_int t;
|
---|
5231 | mp_digit d;
|
---|
5232 | char *_s = str;
|
---|
5233 |
|
---|
5234 | /* check range of the radix */
|
---|
5235 | if (radix < MP_RADIX_BIN || radix > MP_RADIX_MAX) {
|
---|
5236 | return MP_VAL;
|
---|
5237 | }
|
---|
5238 |
|
---|
5239 | /* quick out if its zero */
|
---|
5240 | if (mp_iszero(a) == MP_YES) {
|
---|
5241 | *str++ = '0';
|
---|
5242 | *str = '\0';
|
---|
5243 | return MP_OKAY;
|
---|
5244 | }
|
---|
5245 |
|
---|
5246 | if ((res = mp_init_copy (&t, a)) != MP_OKAY) {
|
---|
5247 | return res;
|
---|
5248 | }
|
---|
5249 |
|
---|
5250 | /* if it is negative output a - */
|
---|
5251 | if (t.sign == MP_NEG) {
|
---|
5252 | ++_s;
|
---|
5253 | *str++ = '-';
|
---|
5254 | t.sign = MP_ZPOS;
|
---|
5255 | }
|
---|
5256 |
|
---|
5257 | digs = 0;
|
---|
5258 | while (mp_iszero (&t) == MP_NO) {
|
---|
5259 | if ((res = mp_div_d (&t, (mp_digit) radix, &t, &d)) != MP_OKAY) {
|
---|
5260 | mp_clear (&t);
|
---|
5261 | return res;
|
---|
5262 | }
|
---|
5263 | *str++ = mp_s_rmap[d];
|
---|
5264 | ++digs;
|
---|
5265 | }
|
---|
5266 | #ifndef WC_DISABLE_RADIX_ZERO_PAD
|
---|
5267 | /* For hexadecimal output, add zero padding when number of digits is odd */
|
---|
5268 | if ((digs & 1) && (radix == 16)) {
|
---|
5269 | *str++ = mp_s_rmap[0];
|
---|
5270 | ++digs;
|
---|
5271 | }
|
---|
5272 | #endif
|
---|
5273 | /* reverse the digits of the string. In this case _s points
|
---|
5274 | * to the first digit [excluding the sign] of the number]
|
---|
5275 | */
|
---|
5276 | bn_reverse ((unsigned char *)_s, digs);
|
---|
5277 |
|
---|
5278 | /* append a NULL so the string is properly terminated */
|
---|
5279 | *str = '\0';
|
---|
5280 |
|
---|
5281 | mp_clear (&t);
|
---|
5282 | return MP_OKAY;
|
---|
5283 | }
|
---|
5284 |
|
---|
5285 | #ifdef WOLFSSL_DEBUG_MATH
|
---|
5286 | void mp_dump(const char* desc, mp_int* a, byte verbose)
|
---|
5287 | {
|
---|
5288 | char *buffer;
|
---|
5289 | int size = a->alloc;
|
---|
5290 |
|
---|
5291 | buffer = (char*)XMALLOC(size * sizeof(mp_digit) * 2, NULL, DYNAMIC_TYPE_TMP_BUFFER);
|
---|
5292 | if (buffer == NULL) {
|
---|
5293 | return;
|
---|
5294 | }
|
---|
5295 |
|
---|
5296 | printf("%s: ptr=%p, used=%d, sign=%d, size=%d, mpd=%d\n",
|
---|
5297 | desc, a, a->used, a->sign, size, (int)sizeof(mp_digit));
|
---|
5298 |
|
---|
5299 | mp_tohex(a, buffer);
|
---|
5300 | printf(" %s\n ", buffer);
|
---|
5301 |
|
---|
5302 | if (verbose) {
|
---|
5303 | int i;
|
---|
5304 | for(i=0; i<a->alloc * (int)sizeof(mp_digit); i++) {
|
---|
5305 | printf("%02x ", *(((byte*)a->dp) + i));
|
---|
5306 | }
|
---|
5307 | printf("\n");
|
---|
5308 | }
|
---|
5309 |
|
---|
5310 | XFREE(buffer, NULL, DYNAMIC_TYPE_TMP_BUFFER);
|
---|
5311 | }
|
---|
5312 | #endif /* WOLFSSL_DEBUG_MATH */
|
---|
5313 |
|
---|
5314 | #endif /* WC_MP_TO_RADIX */
|
---|
5315 |
|
---|
5316 | #endif /* WOLFSSL_SP_MATH */
|
---|
5317 |
|
---|
5318 | #endif /* USE_FAST_MATH */
|
---|
5319 |
|
---|
5320 | #endif /* NO_BIG_INT */
|
---|