Mercurial > projects > hoofbaby
comparison deps/Platinum/ThirdParty/Neptune/ThirdParty/axTLS/crypto/bigint.c @ 0:3425707ddbf6
Initial import (hopefully this mercurial stuff works...)
author | fraserofthenight |
---|---|
date | Mon, 06 Jul 2009 08:06:28 -0700 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:3425707ddbf6 |
---|---|
1 /* | |
2 * Copyright (c) 2007, Cameron Rich | |
3 * | |
4 * All rights reserved. | |
5 * | |
6 * Redistribution and use in source and binary forms, with or without | |
7 * modification, are permitted provided that the following conditions are met: | |
8 * | |
9 * * Redistributions of source code must retain the above copyright notice, | |
10 * this list of conditions and the following disclaimer. | |
11 * * Redistributions in binary form must reproduce the above copyright notice, | |
12 * this list of conditions and the following disclaimer in the documentation | |
13 * and/or other materials provided with the distribution. | |
14 * * Neither the name of the axTLS project nor the names of its contributors | |
15 * may be used to endorse or promote products derived from this software | |
16 * without specific prior written permission. | |
17 * | |
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | |
19 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | |
20 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR | |
21 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR | |
22 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, | |
23 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, | |
24 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR | |
25 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF | |
26 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING | |
27 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS | |
28 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | |
29 */ | |
30 | |
31 /** | |
32 * @defgroup bigint_api Big Integer API | |
33 * @brief The bigint implementation as used by the axTLS project. | |
34 * | |
35 * The bigint library is for RSA encryption/decryption as well as signing. | |
36 * This code tries to minimise use of malloc/free by maintaining a small | |
37 * cache. A bigint context may maintain state by being made "permanent". | |
38 * It be be later released with a bi_depermanent() and bi_free() call. | |
39 * | |
40 * It supports the following reduction techniques: | |
41 * - Classical | |
42 * - Barrett | |
43 * - Montgomery | |
44 * | |
45 * It also implements the following: | |
46 * - Karatsuba multiplication | |
47 * - Squaring | |
48 * - Sliding window exponentiation | |
49 * - Chinese Remainder Theorem (implemented in rsa.c). | |
50 * | |
51 * All the algorithms used are pretty standard, and designed for different | |
52 * data bus sizes. Negative numbers are not dealt with at all, so a subtraction | |
53 * may need to be tested for negativity. | |
54 * | |
55 * This library steals some ideas from Jef Poskanzer | |
56 * <http://cs.marlboro.edu/term/cs-fall02/algorithms/crypto/RSA/bigint> | |
57 * and GMP <http://www.swox.com/gmp>. It gets most of its implementation | |
58 * detail from "The Handbook of Applied Cryptography" | |
59 * <http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf> | |
60 * @{ | |
61 */ | |
62 | |
63 #include <stdlib.h> | |
64 #include <limits.h> | |
65 #include <string.h> | |
66 #include <stdio.h> | |
67 #include <time.h> | |
68 #include "bigint.h" | |
69 | |
70 #define V1 v->comps[v->size-1] /**< v1 for division */ | |
71 #define V2 v->comps[v->size-2] /**< v2 for division */ | |
72 #define U(j) tmp_u->comps[tmp_u->size-j-1] /**< uj for division */ | |
73 #define Q(j) quotient->comps[quotient->size-j-1] /**< qj for division */ | |
74 | |
75 static bigint *bi_int_multiply(BI_CTX *ctx, bigint *bi, comp i); | |
76 static bigint *bi_int_divide(BI_CTX *ctx, bigint *biR, comp denom); | |
77 static bigint *alloc(BI_CTX *ctx, int size); | |
78 static bigint *trim(bigint *bi); | |
79 static void more_comps(bigint *bi, int n); | |
80 #if defined(CONFIG_BIGINT_KARATSUBA) || defined(CONFIG_BIGINT_BARRETT) || \ | |
81 defined(CONFIG_BIGINT_MONTGOMERY) | |
82 static bigint *comp_right_shift(bigint *biR, int num_shifts); | |
83 static bigint *comp_left_shift(bigint *biR, int num_shifts); | |
84 #endif | |
85 | |
86 #ifdef CONFIG_BIGINT_CHECK_ON | |
87 static void check(const bigint *bi); | |
88 #else | |
89 #define check(A) /**< disappears in normal production mode */ | |
90 #endif | |
91 | |
92 | |
93 /** | |
94 * @brief Start a new bigint context. | |
95 * @return A bigint context. | |
96 */ | |
97 BI_CTX *bi_initialize(void) | |
98 { | |
99 /* calloc() sets everything to zero */ | |
100 BI_CTX *ctx = (BI_CTX *)calloc(1, sizeof(BI_CTX)); | |
101 | |
102 /* the radix */ | |
103 ctx->bi_radix = alloc(ctx, 2); | |
104 ctx->bi_radix->comps[0] = 0; | |
105 ctx->bi_radix->comps[1] = 1; | |
106 bi_permanent(ctx->bi_radix); | |
107 return ctx; | |
108 } | |
109 | |
110 /** | |
111 * @brief Close the bigint context and free any resources. | |
112 * | |
113 * Free up any used memory - a check is done if all objects were not | |
114 * properly freed. | |
115 * @param ctx [in] The bigint session context. | |
116 */ | |
117 void bi_terminate(BI_CTX *ctx) | |
118 { | |
119 bi_depermanent(ctx->bi_radix); | |
120 bi_free(ctx, ctx->bi_radix); | |
121 | |
122 if (ctx->active_count != 0) | |
123 { | |
124 #ifdef CONFIG_SSL_FULL_MODE | |
125 printf("bi_terminate: there were %d un-freed bigints\n", | |
126 ctx->active_count); | |
127 #endif | |
128 abort(); | |
129 } | |
130 | |
131 bi_clear_cache(ctx); | |
132 free(ctx); | |
133 } | |
134 | |
135 /** | |
136 *@brief Clear the memory cache. | |
137 */ | |
138 void bi_clear_cache(BI_CTX *ctx) | |
139 { | |
140 bigint *p, *pn; | |
141 | |
142 if (ctx->free_list == NULL) | |
143 return; | |
144 | |
145 for (p = ctx->free_list; p != NULL; p = pn) | |
146 { | |
147 pn = p->next; | |
148 free(p->comps); | |
149 free(p); | |
150 } | |
151 | |
152 ctx->free_count = 0; | |
153 ctx->free_list = NULL; | |
154 } | |
155 | |
156 /** | |
157 * @brief Increment the number of references to this object. | |
158 * It does not do a full copy. | |
159 * @param bi [in] The bigint to copy. | |
160 * @return A reference to the same bigint. | |
161 */ | |
162 bigint *bi_copy(bigint *bi) | |
163 { | |
164 check(bi); | |
165 if (bi->refs != PERMANENT) | |
166 bi->refs++; | |
167 return bi; | |
168 } | |
169 | |
170 /** | |
171 * @brief Simply make a bigint object "unfreeable" if bi_free() is called on it. | |
172 * | |
173 * For this object to be freed, bi_depermanent() must be called. | |
174 * @param bi [in] The bigint to be made permanent. | |
175 */ | |
176 void bi_permanent(bigint *bi) | |
177 { | |
178 check(bi); | |
179 if (bi->refs != 1) | |
180 { | |
181 #ifdef CONFIG_SSL_FULL_MODE | |
182 printf("bi_permanent: refs was not 1\n"); | |
183 #endif | |
184 abort(); | |
185 } | |
186 | |
187 bi->refs = PERMANENT; | |
188 } | |
189 | |
190 /** | |
191 * @brief Take a permanent object and make it eligible for freedom. | |
192 * @param bi [in] The bigint to be made back to temporary. | |
193 */ | |
194 void bi_depermanent(bigint *bi) | |
195 { | |
196 check(bi); | |
197 if (bi->refs != PERMANENT) | |
198 { | |
199 #ifdef CONFIG_SSL_FULL_MODE | |
200 printf("bi_depermanent: bigint was not permanent\n"); | |
201 #endif | |
202 abort(); | |
203 } | |
204 | |
205 bi->refs = 1; | |
206 } | |
207 | |
208 /** | |
209 * @brief Free a bigint object so it can be used again. | |
210 * | |
211 * The memory itself it not actually freed, just tagged as being available | |
212 * @param ctx [in] The bigint session context. | |
213 * @param bi [in] The bigint to be freed. | |
214 */ | |
215 void bi_free(BI_CTX *ctx, bigint *bi) | |
216 { | |
217 check(bi); | |
218 if (bi->refs == PERMANENT) | |
219 { | |
220 return; | |
221 } | |
222 | |
223 if (--bi->refs > 0) | |
224 { | |
225 return; | |
226 } | |
227 | |
228 bi->next = ctx->free_list; | |
229 ctx->free_list = bi; | |
230 ctx->free_count++; | |
231 | |
232 if (--ctx->active_count < 0) | |
233 { | |
234 #ifdef CONFIG_SSL_FULL_MODE | |
235 printf("bi_free: active_count went negative " | |
236 "- double-freed bigint?\n"); | |
237 #endif | |
238 abort(); | |
239 } | |
240 } | |
241 | |
242 /** | |
243 * @brief Convert an (unsigned) integer into a bigint. | |
244 * @param ctx [in] The bigint session context. | |
245 * @param i [in] The (unsigned) integer to be converted. | |
246 * | |
247 */ | |
248 bigint *int_to_bi(BI_CTX *ctx, comp i) | |
249 { | |
250 bigint *biR = alloc(ctx, 1); | |
251 biR->comps[0] = i; | |
252 return biR; | |
253 } | |
254 | |
255 /** | |
256 * @brief Do a full copy of the bigint object. | |
257 * @param ctx [in] The bigint session context. | |
258 * @param bi [in] The bigint object to be copied. | |
259 */ | |
260 bigint *bi_clone(BI_CTX *ctx, const bigint *bi) | |
261 { | |
262 bigint *biR = alloc(ctx, bi->size); | |
263 check(bi); | |
264 memcpy(biR->comps, bi->comps, bi->size*COMP_BYTE_SIZE); | |
265 return biR; | |
266 } | |
267 | |
268 /** | |
269 * @brief Perform an addition operation between two bigints. | |
270 * @param ctx [in] The bigint session context. | |
271 * @param bia [in] A bigint. | |
272 * @param bib [in] Another bigint. | |
273 * @return The result of the addition. | |
274 */ | |
275 bigint *bi_add(BI_CTX *ctx, bigint *bia, bigint *bib) | |
276 { | |
277 int n; | |
278 comp carry = 0; | |
279 comp *pa, *pb; | |
280 | |
281 check(bia); | |
282 check(bib); | |
283 | |
284 n = max(bia->size, bib->size); | |
285 more_comps(bia, n+1); | |
286 more_comps(bib, n); | |
287 pa = bia->comps; | |
288 pb = bib->comps; | |
289 | |
290 do | |
291 { | |
292 comp sl, rl, cy1; | |
293 sl = *pa + *pb++; | |
294 rl = sl + carry; | |
295 cy1 = sl < *pa; | |
296 carry = cy1 | (rl < sl); | |
297 *pa++ = rl; | |
298 } while (--n != 0); | |
299 | |
300 *pa = carry; /* do overflow */ | |
301 bi_free(ctx, bib); | |
302 return trim(bia); | |
303 } | |
304 | |
305 /** | |
306 * @brief Perform a subtraction operation between two bigints. | |
307 * @param ctx [in] The bigint session context. | |
308 * @param bia [in] A bigint. | |
309 * @param bib [in] Another bigint. | |
310 * @param is_negative [out] If defined, indicates that the result was negative. | |
311 * is_negative may be null. | |
312 * @return The result of the subtraction. The result is always positive. | |
313 */ | |
314 bigint *bi_subtract(BI_CTX *ctx, | |
315 bigint *bia, bigint *bib, int *is_negative) | |
316 { | |
317 int n = bia->size; | |
318 comp *pa, *pb, carry = 0; | |
319 | |
320 check(bia); | |
321 check(bib); | |
322 | |
323 more_comps(bib, n); | |
324 pa = bia->comps; | |
325 pb = bib->comps; | |
326 | |
327 do | |
328 { | |
329 comp sl, rl, cy1; | |
330 sl = *pa - *pb++; | |
331 rl = sl - carry; | |
332 cy1 = sl > *pa; | |
333 carry = cy1 | (rl > sl); | |
334 *pa++ = rl; | |
335 } while (--n != 0); | |
336 | |
337 if (is_negative) /* indicate a negative result */ | |
338 { | |
339 *is_negative = carry; | |
340 } | |
341 | |
342 bi_free(ctx, trim(bib)); /* put bib back to the way it was */ | |
343 return trim(bia); | |
344 } | |
345 | |
346 /** | |
347 * Perform a multiply between a bigint an an (unsigned) integer | |
348 */ | |
349 static bigint *bi_int_multiply(BI_CTX *ctx, bigint *bia, comp b) | |
350 { | |
351 int j = 0, n = bia->size; | |
352 bigint *biR = alloc(ctx, n + 1); | |
353 comp carry = 0; | |
354 comp *r = biR->comps; | |
355 comp *a = bia->comps; | |
356 | |
357 check(bia); | |
358 | |
359 /* clear things to start with */ | |
360 memset(r, 0, ((n+1)*COMP_BYTE_SIZE)); | |
361 | |
362 do | |
363 { | |
364 long_comp tmp = *r + (long_comp)a[j]*b + carry; | |
365 *r++ = (comp)tmp; /* downsize */ | |
366 carry = (comp)(tmp >> COMP_BIT_SIZE); | |
367 } while (++j < n); | |
368 | |
369 *r = carry; | |
370 bi_free(ctx, bia); | |
371 return trim(biR); | |
372 } | |
373 | |
374 /** | |
375 * @brief Does both division and modulo calculations. | |
376 * | |
377 * Used extensively when doing classical reduction. | |
378 * @param ctx [in] The bigint session context. | |
379 * @param u [in] A bigint which is the numerator. | |
380 * @param v [in] Either the denominator or the modulus depending on the mode. | |
381 * @param is_mod [n] Determines if this is a normal division (0) or a reduction | |
382 * (1). | |
383 * @return The result of the division/reduction. | |
384 */ | |
385 bigint *bi_divide(BI_CTX *ctx, bigint *u, bigint *v, int is_mod) | |
386 { | |
387 int n = v->size, m = u->size-n; | |
388 int j = 0, orig_u_size = u->size; | |
389 uint8_t mod_offset = ctx->mod_offset; | |
390 comp d; | |
391 bigint *quotient, *tmp_u; | |
392 comp q_dash; | |
393 | |
394 check(u); | |
395 check(v); | |
396 | |
397 /* if doing reduction and we are < mod, then return mod */ | |
398 if (is_mod && bi_compare(v, u) > 0) | |
399 { | |
400 bi_free(ctx, v); | |
401 return u; | |
402 } | |
403 | |
404 quotient = alloc(ctx, m+1); | |
405 tmp_u = alloc(ctx, n+1); | |
406 v = trim(v); /* make sure we have no leading 0's */ | |
407 d = (comp)((long_comp)COMP_RADIX/(V1+1)); | |
408 | |
409 /* clear things to start with */ | |
410 memset(quotient->comps, 0, ((quotient->size)*COMP_BYTE_SIZE)); | |
411 | |
412 /* normalise */ | |
413 if (d > 1) | |
414 { | |
415 u = bi_int_multiply(ctx, u, d); | |
416 | |
417 if (is_mod) | |
418 { | |
419 v = ctx->bi_normalised_mod[mod_offset]; | |
420 } | |
421 else | |
422 { | |
423 v = bi_int_multiply(ctx, v, d); | |
424 } | |
425 } | |
426 | |
427 if (orig_u_size == u->size) /* new digit position u0 */ | |
428 { | |
429 more_comps(u, orig_u_size + 1); | |
430 } | |
431 | |
432 do | |
433 { | |
434 /* get a temporary short version of u */ | |
435 memcpy(tmp_u->comps, &u->comps[u->size-n-1-j], (n+1)*COMP_BYTE_SIZE); | |
436 | |
437 /* calculate q' */ | |
438 if (U(0) == V1) | |
439 { | |
440 q_dash = COMP_RADIX-1; | |
441 } | |
442 else | |
443 { | |
444 q_dash = (comp)(((long_comp)U(0)*COMP_RADIX + U(1))/V1); | |
445 } | |
446 | |
447 if (v->size > 1 && V2) | |
448 { | |
449 /* we are implementing the following: | |
450 if (V2*q_dash > (((U(0)*COMP_RADIX + U(1) - | |
451 q_dash*V1)*COMP_RADIX) + U(2))) ... */ | |
452 comp inner = (comp)((long_comp)COMP_RADIX*U(0) + U(1) - | |
453 (long_comp)q_dash*V1); | |
454 if ((long_comp)V2*q_dash > (long_comp)inner*COMP_RADIX + U(2)) | |
455 { | |
456 q_dash--; | |
457 } | |
458 } | |
459 | |
460 /* multiply and subtract */ | |
461 if (q_dash) | |
462 { | |
463 int is_negative; | |
464 tmp_u = bi_subtract(ctx, tmp_u, | |
465 bi_int_multiply(ctx, bi_copy(v), q_dash), &is_negative); | |
466 more_comps(tmp_u, n+1); | |
467 | |
468 Q(j) = q_dash; | |
469 | |
470 /* add back */ | |
471 if (is_negative) | |
472 { | |
473 Q(j)--; | |
474 tmp_u = bi_add(ctx, tmp_u, bi_copy(v)); | |
475 | |
476 /* lop off the carry */ | |
477 tmp_u->size--; | |
478 v->size--; | |
479 } | |
480 } | |
481 else | |
482 { | |
483 Q(j) = 0; | |
484 } | |
485 | |
486 /* copy back to u */ | |
487 memcpy(&u->comps[u->size-n-1-j], tmp_u->comps, (n+1)*COMP_BYTE_SIZE); | |
488 } while (++j <= m); | |
489 | |
490 bi_free(ctx, tmp_u); | |
491 bi_free(ctx, v); | |
492 | |
493 if (is_mod) /* get the remainder */ | |
494 { | |
495 bi_free(ctx, quotient); | |
496 return bi_int_divide(ctx, trim(u), d); | |
497 } | |
498 else /* get the quotient */ | |
499 { | |
500 bi_free(ctx, u); | |
501 return trim(quotient); | |
502 } | |
503 } | |
504 | |
505 /* | |
506 * Perform an integer divide on a bigint. | |
507 */ | |
508 static bigint *bi_int_divide(BI_CTX *ctx, bigint *biR, comp denom) | |
509 { | |
510 int i = biR->size - 1; | |
511 (void)ctx; /* unused */ | |
512 long_comp r = 0; | |
513 | |
514 check(biR); | |
515 | |
516 do | |
517 { | |
518 r = (r<<COMP_BIT_SIZE) + biR->comps[i]; | |
519 biR->comps[i] = (comp)(r / denom); | |
520 r %= denom; | |
521 } while (--i >= 0); | |
522 | |
523 return trim(biR); | |
524 } | |
525 | |
526 #ifdef CONFIG_BIGINT_MONTGOMERY | |
527 /** | |
528 * There is a need for the value of integer N' such that B^-1(B-1)-N^-1N'=1, | |
529 * where B^-1(B-1) mod N=1. Actually, only the least significant part of | |
530 * N' is needed, hence the definition N0'=N' mod b. We reproduce below the | |
531 * simple algorithm from an article by Dusse and Kaliski to efficiently | |
532 * find N0' from N0 and b */ | |
533 static comp modular_inverse(bigint *bim) | |
534 { | |
535 int i; | |
536 comp t = 1; | |
537 comp two_2_i_minus_1 = 2; /* 2^(i-1) */ | |
538 long_comp two_2_i = 4; /* 2^i */ | |
539 comp N = bim->comps[0]; | |
540 | |
541 for (i = 2; i <= COMP_BIT_SIZE; i++) | |
542 { | |
543 if ((long_comp)N*t%two_2_i >= two_2_i_minus_1) | |
544 { | |
545 t += two_2_i_minus_1; | |
546 } | |
547 | |
548 two_2_i_minus_1 <<= 1; | |
549 two_2_i <<= 1; | |
550 } | |
551 | |
552 return (comp)(COMP_RADIX-t); | |
553 } | |
554 #endif | |
555 | |
556 #if defined(CONFIG_BIGINT_KARATSUBA) || defined(CONFIG_BIGINT_BARRETT) || \ | |
557 defined(CONFIG_BIGINT_MONTGOMERY) | |
558 /** | |
559 * Take each component and shift down (in terms of components) | |
560 */ | |
561 static bigint *comp_right_shift(bigint *biR, int num_shifts) | |
562 { | |
563 int i = biR->size-num_shifts; | |
564 comp *x = biR->comps; | |
565 comp *y = &biR->comps[num_shifts]; | |
566 | |
567 check(biR); | |
568 | |
569 if (i <= 0) /* have we completely right shifted? */ | |
570 { | |
571 biR->comps[0] = 0; /* return 0 */ | |
572 biR->size = 1; | |
573 return biR; | |
574 } | |
575 | |
576 do | |
577 { | |
578 *x++ = *y++; | |
579 } while (--i > 0); | |
580 | |
581 biR->size -= num_shifts; | |
582 return biR; | |
583 } | |
584 | |
585 /** | |
586 * Take each component and shift it up (in terms of components) | |
587 */ | |
588 static bigint *comp_left_shift(bigint *biR, int num_shifts) | |
589 { | |
590 int i = biR->size-1; | |
591 comp *x, *y; | |
592 | |
593 check(biR); | |
594 | |
595 if (num_shifts <= 0) | |
596 { | |
597 return biR; | |
598 } | |
599 | |
600 more_comps(biR, biR->size + num_shifts); | |
601 | |
602 x = &biR->comps[i+num_shifts]; | |
603 y = &biR->comps[i]; | |
604 | |
605 do | |
606 { | |
607 *x-- = *y--; | |
608 } while (i--); | |
609 | |
610 memset(biR->comps, 0, num_shifts*COMP_BYTE_SIZE); /* zero LS comps */ | |
611 return biR; | |
612 } | |
613 #endif | |
614 | |
615 /** | |
616 * @brief Allow a binary sequence to be imported as a bigint. | |
617 * @param ctx [in] The bigint session context. | |
618 * @param data [in] The data to be converted. | |
619 * @param size [in] The number of bytes of data. | |
620 * @return A bigint representing this data. | |
621 */ | |
622 bigint *bi_import(BI_CTX *ctx, const uint8_t *data, int size) | |
623 { | |
624 bigint *biR = alloc(ctx, (size+COMP_BYTE_SIZE-1)/COMP_BYTE_SIZE); | |
625 int i, j = 0, offset = 0; | |
626 | |
627 memset(biR->comps, 0, biR->size*COMP_BYTE_SIZE); | |
628 | |
629 for (i = size-1; i >= 0; i--) | |
630 { | |
631 biR->comps[offset] += data[i] << (j*8); | |
632 | |
633 if (++j == COMP_BYTE_SIZE) | |
634 { | |
635 j = 0; | |
636 offset ++; | |
637 } | |
638 } | |
639 | |
640 return trim(biR); | |
641 } | |
642 | |
643 #ifdef CONFIG_SSL_FULL_MODE | |
644 /** | |
645 * @brief The testharness uses this code to import text hex-streams and | |
646 * convert them into bigints. | |
647 * @param ctx [in] The bigint session context. | |
648 * @param data [in] A string consisting of hex characters. The characters must | |
649 * be in upper case. | |
650 * @return A bigint representing this data. | |
651 */ | |
652 bigint *bi_str_import(BI_CTX *ctx, const char *data) | |
653 { | |
654 int size = strlen(data); | |
655 bigint *biR = alloc(ctx, (size+COMP_NUM_NIBBLES-1)/COMP_NUM_NIBBLES); | |
656 int i, j = 0, offset = 0; | |
657 memset(biR->comps, 0, biR->size*COMP_BYTE_SIZE); | |
658 | |
659 for (i = size-1; i >= 0; i--) | |
660 { | |
661 int num = (data[i] <= '9') ? (data[i] - '0') : (data[i] - 'A' + 10); | |
662 biR->comps[offset] += num << (j*4); | |
663 | |
664 if (++j == COMP_NUM_NIBBLES) | |
665 { | |
666 j = 0; | |
667 offset ++; | |
668 } | |
669 } | |
670 | |
671 return biR; | |
672 } | |
673 | |
674 void bi_print(const char *label, bigint *x) | |
675 { | |
676 int i, j; | |
677 | |
678 if (x == NULL) | |
679 { | |
680 printf("%s: (null)\n", label); | |
681 return; | |
682 } | |
683 | |
684 printf("%s: (size %d)\n", label, x->size); | |
685 for (i = x->size-1; i >= 0; i--) | |
686 { | |
687 for (j = COMP_NUM_NIBBLES-1; j >= 0; j--) | |
688 { | |
689 comp mask = 0x0f << (j*4); | |
690 comp num = (x->comps[i] & mask) >> (j*4); | |
691 putc((num <= 9) ? (num + '0') : (num + 'A' - 10), stdout); | |
692 } | |
693 } | |
694 | |
695 printf("\n"); | |
696 } | |
697 #endif | |
698 | |
699 /** | |
700 * @brief Take a bigint and convert it into a byte sequence. | |
701 * | |
702 * This is useful after a decrypt operation. | |
703 * @param ctx [in] The bigint session context. | |
704 * @param x [in] The bigint to be converted. | |
705 * @param data [out] The converted data as a byte stream. | |
706 * @param size [in] The maximum size of the byte stream. Unused bytes will be | |
707 * zeroed. | |
708 */ | |
709 void bi_export(BI_CTX *ctx, bigint *x, uint8_t *data, int size) | |
710 { | |
711 int i, j, k = size-1; | |
712 | |
713 check(x); | |
714 memset(data, 0, size); /* ensure all leading 0's are cleared */ | |
715 | |
716 for (i = 0; i < x->size; i++) | |
717 { | |
718 for (j = 0; j < COMP_BYTE_SIZE; j++) | |
719 { | |
720 comp mask = 0xff << (j*8); | |
721 int num = (x->comps[i] & mask) >> (j*8); | |
722 data[k--] = num; | |
723 | |
724 if (k < 0) | |
725 { | |
726 break; | |
727 } | |
728 } | |
729 } | |
730 | |
731 bi_free(ctx, x); | |
732 } | |
733 | |
734 /** | |
735 * @brief Pre-calculate some of the expensive steps in reduction. | |
736 * | |
737 * This function should only be called once (normally when a session starts). | |
738 * When the session is over, bi_free_mod() should be called. bi_mod_power() | |
739 * relies on this function being called. | |
740 * @param ctx [in] The bigint session context. | |
741 * @param bim [in] The bigint modulus that will be used. | |
742 * @param mod_offset [in] There are three moduluii that can be stored - the | |
743 * standard modulus, and its two primes p and q. This offset refers to which | |
744 * modulus we are referring to. | |
745 * @see bi_free_mod(), bi_mod_power(). | |
746 */ | |
747 void bi_set_mod(BI_CTX *ctx, bigint *bim, int mod_offset) | |
748 { | |
749 int k = bim->size; | |
750 comp d = (comp)((long_comp)COMP_RADIX/(bim->comps[k-1]+1)); | |
751 #ifdef CONFIG_BIGINT_MONTGOMERY | |
752 bigint *R, *R2; | |
753 #endif | |
754 | |
755 ctx->bi_mod[mod_offset] = bim; | |
756 bi_permanent(ctx->bi_mod[mod_offset]); | |
757 ctx->bi_normalised_mod[mod_offset] = bi_int_multiply(ctx, bim, d); | |
758 bi_permanent(ctx->bi_normalised_mod[mod_offset]); | |
759 | |
760 #if defined(CONFIG_BIGINT_MONTGOMERY) | |
761 /* set montgomery variables */ | |
762 R = comp_left_shift(bi_clone(ctx, ctx->bi_radix), k-1); /* R */ | |
763 R2 = comp_left_shift(bi_clone(ctx, ctx->bi_radix), k*2-1); /* R^2 */ | |
764 ctx->bi_RR_mod_m[mod_offset] = bi_mod(ctx, R2); /* R^2 mod m */ | |
765 ctx->bi_R_mod_m[mod_offset] = bi_mod(ctx, R); /* R mod m */ | |
766 | |
767 bi_permanent(ctx->bi_RR_mod_m[mod_offset]); | |
768 bi_permanent(ctx->bi_R_mod_m[mod_offset]); | |
769 | |
770 ctx->N0_dash[mod_offset] = modular_inverse(ctx->bi_mod[mod_offset]); | |
771 | |
772 #elif defined (CONFIG_BIGINT_BARRETT) | |
773 ctx->bi_mu[mod_offset] = | |
774 bi_divide(ctx, comp_left_shift( | |
775 bi_clone(ctx, ctx->bi_radix), k*2-1), ctx->bi_mod[mod_offset], 0); | |
776 bi_permanent(ctx->bi_mu[mod_offset]); | |
777 #endif | |
778 } | |
779 | |
780 /** | |
781 * @brief Used when cleaning various bigints at the end of a session. | |
782 * @param ctx [in] The bigint session context. | |
783 * @param mod_offset [in] The offset to use. | |
784 * @see bi_set_mod(). | |
785 */ | |
786 void bi_free_mod(BI_CTX *ctx, int mod_offset) | |
787 { | |
788 bi_depermanent(ctx->bi_mod[mod_offset]); | |
789 bi_free(ctx, ctx->bi_mod[mod_offset]); | |
790 #if defined (CONFIG_BIGINT_MONTGOMERY) | |
791 bi_depermanent(ctx->bi_RR_mod_m[mod_offset]); | |
792 bi_depermanent(ctx->bi_R_mod_m[mod_offset]); | |
793 bi_free(ctx, ctx->bi_RR_mod_m[mod_offset]); | |
794 bi_free(ctx, ctx->bi_R_mod_m[mod_offset]); | |
795 #elif defined(CONFIG_BIGINT_BARRETT) | |
796 bi_depermanent(ctx->bi_mu[mod_offset]); | |
797 bi_free(ctx, ctx->bi_mu[mod_offset]); | |
798 #endif | |
799 bi_depermanent(ctx->bi_normalised_mod[mod_offset]); | |
800 bi_free(ctx, ctx->bi_normalised_mod[mod_offset]); | |
801 } | |
802 | |
803 /** | |
804 * Perform a standard multiplication between two bigints. | |
805 */ | |
806 static bigint *regular_multiply(BI_CTX *ctx, bigint *bia, bigint *bib) | |
807 { | |
808 int i, j, i_plus_j; | |
809 int n = bia->size; | |
810 int t = bib->size; | |
811 bigint *biR = alloc(ctx, n + t); | |
812 comp *sr = biR->comps; | |
813 comp *sa = bia->comps; | |
814 comp *sb = bib->comps; | |
815 | |
816 check(bia); | |
817 check(bib); | |
818 | |
819 /* clear things to start with */ | |
820 memset(biR->comps, 0, ((n+t)*COMP_BYTE_SIZE)); | |
821 i = 0; | |
822 | |
823 do | |
824 { | |
825 comp carry = 0; | |
826 comp b = *sb++; | |
827 i_plus_j = i; | |
828 j = 0; | |
829 | |
830 do | |
831 { | |
832 long_comp tmp = sr[i_plus_j] + (long_comp)sa[j]*b + carry; | |
833 sr[i_plus_j++] = (comp)tmp; /* downsize */ | |
834 carry = (comp)(tmp >> COMP_BIT_SIZE); | |
835 } while (++j < n); | |
836 | |
837 sr[i_plus_j] = carry; | |
838 } while (++i < t); | |
839 | |
840 bi_free(ctx, bia); | |
841 bi_free(ctx, bib); | |
842 return trim(biR); | |
843 } | |
844 | |
845 #ifdef CONFIG_BIGINT_KARATSUBA | |
846 /* | |
847 * Karatsuba improves on regular multiplication due to only 3 multiplications | |
848 * being done instead of 4. The additional additions/subtractions are O(N) | |
849 * rather than O(N^2) and so for big numbers it saves on a few operations | |
850 */ | |
851 static bigint *karatsuba(BI_CTX *ctx, bigint *bia, bigint *bib, int is_square) | |
852 { | |
853 bigint *x0, *x1; | |
854 bigint *p0, *p1, *p2; | |
855 int m; | |
856 | |
857 if (is_square) | |
858 { | |
859 m = (bia->size + 1)/2; | |
860 } | |
861 else | |
862 { | |
863 m = (max(bia->size, bib->size) + 1)/2; | |
864 } | |
865 | |
866 x0 = bi_clone(ctx, bia); | |
867 x0->size = m; | |
868 x1 = bi_clone(ctx, bia); | |
869 comp_right_shift(x1, m); | |
870 bi_free(ctx, bia); | |
871 | |
872 /* work out the 3 partial products */ | |
873 if (is_square) | |
874 { | |
875 p0 = bi_square(ctx, bi_copy(x0)); | |
876 p2 = bi_square(ctx, bi_copy(x1)); | |
877 p1 = bi_square(ctx, bi_add(ctx, x0, x1)); | |
878 } | |
879 else /* normal multiply */ | |
880 { | |
881 bigint *y0, *y1; | |
882 y0 = bi_clone(ctx, bib); | |
883 y0->size = m; | |
884 y1 = bi_clone(ctx, bib); | |
885 comp_right_shift(y1, m); | |
886 bi_free(ctx, bib); | |
887 | |
888 p0 = bi_multiply(ctx, bi_copy(x0), bi_copy(y0)); | |
889 p2 = bi_multiply(ctx, bi_copy(x1), bi_copy(y1)); | |
890 p1 = bi_multiply(ctx, bi_add(ctx, x0, x1), bi_add(ctx, y0, y1)); | |
891 } | |
892 | |
893 p1 = bi_subtract(ctx, | |
894 bi_subtract(ctx, p1, bi_copy(p2), NULL), bi_copy(p0), NULL); | |
895 | |
896 comp_left_shift(p1, m); | |
897 comp_left_shift(p2, 2*m); | |
898 return bi_add(ctx, p1, bi_add(ctx, p0, p2)); | |
899 } | |
900 #endif | |
901 | |
902 /** | |
903 * @brief Perform a multiplication operation between two bigints. | |
904 * @param ctx [in] The bigint session context. | |
905 * @param bia [in] A bigint. | |
906 * @param bib [in] Another bigint. | |
907 * @return The result of the multiplication. | |
908 */ | |
909 bigint *bi_multiply(BI_CTX *ctx, bigint *bia, bigint *bib) | |
910 { | |
911 check(bia); | |
912 check(bib); | |
913 | |
914 #ifdef CONFIG_BIGINT_KARATSUBA | |
915 if (min(bia->size, bib->size) < MUL_KARATSUBA_THRESH) | |
916 { | |
917 return regular_multiply(ctx, bia, bib); | |
918 } | |
919 | |
920 return karatsuba(ctx, bia, bib, 0); | |
921 #else | |
922 return regular_multiply(ctx, bia, bib); | |
923 #endif | |
924 } | |
925 | |
926 #ifdef CONFIG_BIGINT_SQUARE | |
927 /* | |
928 * Perform the actual square operion. It takes into account overflow. | |
929 */ | |
930 static bigint *regular_square(BI_CTX *ctx, bigint *bi) | |
931 { | |
932 int t = bi->size; | |
933 int i = 0, j; | |
934 bigint *biR = alloc(ctx, t*2); | |
935 comp *w = biR->comps; | |
936 comp *x = bi->comps; | |
937 comp carry; | |
938 | |
939 memset(w, 0, biR->size*COMP_BYTE_SIZE); | |
940 | |
941 do | |
942 { | |
943 long_comp tmp = w[2*i] + (long_comp)x[i]*x[i]; | |
944 comp u = 0; | |
945 w[2*i] = (comp)tmp; | |
946 carry = (comp)(tmp >> COMP_BIT_SIZE); | |
947 | |
948 for (j = i+1; j < t; j++) | |
949 { | |
950 long_comp xx = (long_comp)x[i]*x[j]; | |
951 long_comp xx2 = 2*xx; | |
952 long_comp blob = (long_comp)w[i+j]+carry; | |
953 | |
954 if (u) /* previous overflow */ | |
955 { | |
956 blob += COMP_RADIX; | |
957 } | |
958 | |
959 | |
960 u = 0; | |
961 tmp = xx2 + blob; | |
962 | |
963 /* check for overflow */ | |
964 if ((COMP_MAX-xx) < xx || (COMP_MAX-xx2) < blob) | |
965 { | |
966 u = 1; | |
967 } | |
968 | |
969 w[i+j] = (comp)tmp; | |
970 carry = (comp)(tmp >> COMP_BIT_SIZE); | |
971 } | |
972 | |
973 w[i+t] += carry; | |
974 | |
975 if (u) | |
976 { | |
977 w[i+t+1] = 1; /* add carry */ | |
978 } | |
979 } while (++i < t); | |
980 | |
981 bi_free(ctx, bi); | |
982 return trim(biR); | |
983 } | |
984 | |
985 /** | |
986 * @brief Perform a square operation on a bigint. | |
987 * @param ctx [in] The bigint session context. | |
988 * @param bia [in] A bigint. | |
989 * @return The result of the multiplication. | |
990 */ | |
991 bigint *bi_square(BI_CTX *ctx, bigint *bia) | |
992 { | |
993 check(bia); | |
994 | |
995 #ifdef CONFIG_BIGINT_KARATSUBA | |
996 if (bia->size < SQU_KARATSUBA_THRESH) | |
997 { | |
998 return regular_square(ctx, bia); | |
999 } | |
1000 | |
1001 return karatsuba(ctx, bia, NULL, 1); | |
1002 #else | |
1003 return regular_square(ctx, bia); | |
1004 #endif | |
1005 } | |
1006 #endif | |
1007 | |
1008 /** | |
1009 * @brief Compare two bigints. | |
1010 * @param bia [in] A bigint. | |
1011 * @param bib [in] Another bigint. | |
1012 * @return -1 if smaller, 1 if larger and 0 if equal. | |
1013 */ | |
1014 int bi_compare(bigint *bia, bigint *bib) | |
1015 { | |
1016 int r, i; | |
1017 | |
1018 check(bia); | |
1019 check(bib); | |
1020 | |
1021 if (bia->size > bib->size) | |
1022 r = 1; | |
1023 else if (bia->size < bib->size) | |
1024 r = -1; | |
1025 else | |
1026 { | |
1027 comp *a = bia->comps; | |
1028 comp *b = bib->comps; | |
1029 | |
1030 /* Same number of components. Compare starting from the high end | |
1031 * and working down. */ | |
1032 r = 0; | |
1033 i = bia->size - 1; | |
1034 | |
1035 do | |
1036 { | |
1037 if (a[i] > b[i]) | |
1038 { | |
1039 r = 1; | |
1040 break; | |
1041 } | |
1042 else if (a[i] < b[i]) | |
1043 { | |
1044 r = -1; | |
1045 break; | |
1046 } | |
1047 } while (--i >= 0); | |
1048 } | |
1049 | |
1050 return r; | |
1051 } | |
1052 | |
1053 /* | |
1054 * Allocate and zero more components. Does not consume bi. | |
1055 */ | |
1056 static void more_comps(bigint *bi, int n) | |
1057 { | |
1058 if (n > bi->max_comps) | |
1059 { | |
1060 bi->max_comps = max(bi->max_comps * 2, n); | |
1061 bi->comps = (comp*)realloc(bi->comps, bi->max_comps * COMP_BYTE_SIZE); | |
1062 } | |
1063 | |
1064 if (n > bi->size) | |
1065 { | |
1066 memset(&bi->comps[bi->size], 0, (n-bi->size)*COMP_BYTE_SIZE); | |
1067 } | |
1068 | |
1069 bi->size = n; | |
1070 } | |
1071 | |
1072 /* | |
1073 * Make a new empty bigint. It may just use an old one if one is available. | |
1074 * Otherwise get one off the heap. | |
1075 */ | |
1076 static bigint *alloc(BI_CTX *ctx, int size) | |
1077 { | |
1078 bigint *biR; | |
1079 | |
1080 /* Can we recycle an old bigint? */ | |
1081 if (ctx->free_list != NULL) | |
1082 { | |
1083 biR = ctx->free_list; | |
1084 ctx->free_list = biR->next; | |
1085 ctx->free_count--; | |
1086 | |
1087 if (biR->refs != 0) | |
1088 { | |
1089 #ifdef CONFIG_SSL_FULL_MODE | |
1090 printf("alloc: refs was not 0\n"); | |
1091 #endif | |
1092 abort(); /* create a stack trace from a core dump */ | |
1093 } | |
1094 | |
1095 more_comps(biR, size); | |
1096 } | |
1097 else | |
1098 { | |
1099 /* No free bigints available - create a new one. */ | |
1100 biR = (bigint *)malloc(sizeof(bigint)); | |
1101 biR->comps = (comp*)malloc(size * COMP_BYTE_SIZE); | |
1102 biR->max_comps = size; /* give some space to spare */ | |
1103 } | |
1104 | |
1105 biR->size = size; | |
1106 biR->refs = 1; | |
1107 biR->next = NULL; | |
1108 ctx->active_count++; | |
1109 return biR; | |
1110 } | |
1111 | |
1112 /* | |
1113 * Work out the highest '1' bit in an exponent. Used when doing sliding-window | |
1114 * exponentiation. | |
1115 */ | |
1116 static int find_max_exp_index(bigint *biexp) | |
1117 { | |
1118 int i = COMP_BIT_SIZE-1; | |
1119 comp shift = COMP_RADIX/2; | |
1120 comp test = biexp->comps[biexp->size-1]; /* assume no leading zeroes */ | |
1121 | |
1122 check(biexp); | |
1123 | |
1124 do | |
1125 { | |
1126 if (test & shift) | |
1127 { | |
1128 return i+(biexp->size-1)*COMP_BIT_SIZE; | |
1129 } | |
1130 | |
1131 shift >>= 1; | |
1132 } while (--i != 0); | |
1133 | |
1134 return -1; /* error - must have been a leading 0 */ | |
1135 } | |
1136 | |
1137 /* | |
1138 * Is a particular bit is an exponent 1 or 0? Used when doing sliding-window | |
1139 * exponentiation. | |
1140 */ | |
1141 static int exp_bit_is_one(bigint *biexp, int offset) | |
1142 { | |
1143 comp test = biexp->comps[offset / COMP_BIT_SIZE]; | |
1144 int num_shifts = offset % COMP_BIT_SIZE; | |
1145 comp shift = 1; | |
1146 int i; | |
1147 | |
1148 check(biexp); | |
1149 | |
1150 for (i = 0; i < num_shifts; i++) | |
1151 { | |
1152 shift <<= 1; | |
1153 } | |
1154 | |
1155 return test & shift; | |
1156 } | |
1157 | |
1158 #ifdef CONFIG_BIGINT_CHECK_ON | |
1159 /* | |
1160 * Perform a sanity check on bi. | |
1161 */ | |
1162 static void check(const bigint *bi) | |
1163 { | |
1164 if (bi->refs <= 0) | |
1165 { | |
1166 printf("check: zero or negative refs in bigint\n"); | |
1167 abort(); | |
1168 } | |
1169 | |
1170 if (bi->next != NULL) | |
1171 { | |
1172 printf("check: attempt to use a bigint from " | |
1173 "the free list\n"); | |
1174 abort(); | |
1175 } | |
1176 } | |
1177 #endif | |
1178 | |
1179 /* | |
1180 * Delete any leading 0's (and allow for 0). | |
1181 */ | |
1182 static bigint *trim(bigint *bi) | |
1183 { | |
1184 check(bi); | |
1185 | |
1186 while (bi->comps[bi->size-1] == 0 && bi->size > 1) | |
1187 { | |
1188 bi->size--; | |
1189 } | |
1190 | |
1191 return bi; | |
1192 } | |
1193 | |
1194 #if defined(CONFIG_BIGINT_MONTGOMERY) | |
1195 /** | |
1196 * @brief Perform a single montgomery reduction. | |
1197 * @param ctx [in] The bigint session context. | |
1198 * @param bixy [in] A bigint. | |
1199 * @return The result of the montgomery reduction. | |
1200 */ | |
1201 bigint *bi_mont(BI_CTX *ctx, bigint *bixy) | |
1202 { | |
1203 int i = 0, n; | |
1204 uint8_t mod_offset = ctx->mod_offset; | |
1205 bigint *bim = ctx->bi_mod[mod_offset]; | |
1206 comp mod_inv = ctx->N0_dash[mod_offset]; | |
1207 | |
1208 check(bixy); | |
1209 | |
1210 if (ctx->use_classical) /* just use classical instead */ | |
1211 { | |
1212 return bi_mod(ctx, bixy); | |
1213 } | |
1214 | |
1215 n = bim->size; | |
1216 | |
1217 do | |
1218 { | |
1219 bixy = bi_add(ctx, bixy, comp_left_shift( | |
1220 bi_int_multiply(ctx, bim, bixy->comps[i]*mod_inv), i)); | |
1221 } while (++i < n); | |
1222 | |
1223 comp_right_shift(bixy, n); | |
1224 | |
1225 if (bi_compare(bixy, bim) >= 0) | |
1226 { | |
1227 bixy = bi_subtract(ctx, bixy, bim, NULL); | |
1228 } | |
1229 | |
1230 return bixy; | |
1231 } | |
1232 | |
1233 #elif defined(CONFIG_BIGINT_BARRETT) | |
1234 /* | |
1235 * Stomp on the most significant components to give the illusion of a "mod base | |
1236 * radix" operation | |
1237 */ | |
1238 static bigint *comp_mod(bigint *bi, int mod) | |
1239 { | |
1240 check(bi); | |
1241 | |
1242 if (bi->size > mod) | |
1243 { | |
1244 bi->size = mod; | |
1245 } | |
1246 | |
1247 return bi; | |
1248 } | |
1249 | |
1250 /* | |
1251 * Barrett reduction has no need for some parts of the product, so ignore bits | |
1252 * of the multiply. This routine gives Barrett its big performance | |
1253 * improvements over Classical/Montgomery reduction methods. | |
1254 */ | |
1255 static bigint *partial_multiply(BI_CTX *ctx, bigint *bia, bigint *bib, | |
1256 int inner_partial, int outer_partial) | |
1257 { | |
1258 int i = 0, j, n = bia->size, t = bib->size; | |
1259 bigint *biR; | |
1260 comp carry; | |
1261 comp *sr, *sa, *sb; | |
1262 | |
1263 check(bia); | |
1264 check(bib); | |
1265 | |
1266 biR = alloc(ctx, n + t); | |
1267 sa = bia->comps; | |
1268 sb = bib->comps; | |
1269 sr = biR->comps; | |
1270 | |
1271 if (inner_partial) | |
1272 { | |
1273 memset(sr, 0, inner_partial*COMP_BYTE_SIZE); | |
1274 } | |
1275 else /* outer partial */ | |
1276 { | |
1277 if (n < outer_partial || t < outer_partial) /* should we bother? */ | |
1278 { | |
1279 bi_free(ctx, bia); | |
1280 bi_free(ctx, bib); | |
1281 biR->comps[0] = 0; /* return 0 */ | |
1282 biR->size = 1; | |
1283 return biR; | |
1284 } | |
1285 | |
1286 memset(&sr[outer_partial], 0, (n+t-outer_partial)*COMP_BYTE_SIZE); | |
1287 } | |
1288 | |
1289 do | |
1290 { | |
1291 comp *a = sa; | |
1292 comp b = *sb++; | |
1293 long_comp tmp; | |
1294 int i_plus_j = i; | |
1295 carry = 0; | |
1296 j = n; | |
1297 | |
1298 if (outer_partial && i_plus_j < outer_partial) | |
1299 { | |
1300 i_plus_j = outer_partial; | |
1301 a = &sa[outer_partial-i]; | |
1302 j = n-(outer_partial-i); | |
1303 } | |
1304 | |
1305 do | |
1306 { | |
1307 if (inner_partial && i_plus_j >= inner_partial) | |
1308 { | |
1309 break; | |
1310 } | |
1311 | |
1312 tmp = sr[i_plus_j] + ((long_comp)*a++)*b + carry; | |
1313 sr[i_plus_j++] = (comp)tmp; /* downsize */ | |
1314 carry = (comp)(tmp >> COMP_BIT_SIZE); | |
1315 } while (--j != 0); | |
1316 | |
1317 sr[i_plus_j] = carry; | |
1318 } while (++i < t); | |
1319 | |
1320 bi_free(ctx, bia); | |
1321 bi_free(ctx, bib); | |
1322 return trim(biR); | |
1323 } | |
1324 | |
1325 /** | |
1326 * @brief Perform a single Barrett reduction. | |
1327 * @param ctx [in] The bigint session context. | |
1328 * @param bi [in] A bigint. | |
1329 * @return The result of the Barrett reduction. | |
1330 */ | |
1331 bigint *bi_barrett(BI_CTX *ctx, bigint *bi) | |
1332 { | |
1333 bigint *q1, *q2, *q3, *r1, *r2, *r; | |
1334 uint8_t mod_offset = ctx->mod_offset; | |
1335 bigint *bim = ctx->bi_mod[mod_offset]; | |
1336 int k = bim->size; | |
1337 | |
1338 check(bi); | |
1339 check(bim); | |
1340 | |
1341 /* use Classical method instead - Barrett cannot help here */ | |
1342 if (bi->size > k*2) | |
1343 { | |
1344 return bi_mod(ctx, bi); | |
1345 } | |
1346 | |
1347 q1 = comp_right_shift(bi_clone(ctx, bi), k-1); | |
1348 | |
1349 /* do outer partial multiply */ | |
1350 q2 = partial_multiply(ctx, q1, ctx->bi_mu[mod_offset], 0, k-1); | |
1351 q3 = comp_right_shift(q2, k+1); | |
1352 r1 = comp_mod(bi, k+1); | |
1353 | |
1354 /* do inner partial multiply */ | |
1355 r2 = comp_mod(partial_multiply(ctx, q3, bim, k+1, 0), k+1); | |
1356 r = bi_subtract(ctx, r1, r2, NULL); | |
1357 | |
1358 /* if (r >= m) r = r - m; */ | |
1359 if (bi_compare(r, bim) >= 0) | |
1360 { | |
1361 r = bi_subtract(ctx, r, bim, NULL); | |
1362 } | |
1363 | |
1364 return r; | |
1365 } | |
1366 #endif /* CONFIG_BIGINT_BARRETT */ | |
1367 | |
1368 #ifdef CONFIG_BIGINT_SLIDING_WINDOW | |
1369 /* | |
1370 * Work out g1, g3, g5, g7... etc for the sliding-window algorithm | |
1371 */ | |
1372 static void precompute_slide_window(BI_CTX *ctx, int window, bigint *g1) | |
1373 { | |
1374 int k = 1, i; | |
1375 bigint *g2; | |
1376 | |
1377 for (i = 0; i < window-1; i++) /* compute 2^(window-1) */ | |
1378 { | |
1379 k <<= 1; | |
1380 } | |
1381 | |
1382 ctx->g = (bigint **)malloc(k*sizeof(bigint *)); | |
1383 ctx->g[0] = bi_clone(ctx, g1); | |
1384 bi_permanent(ctx->g[0]); | |
1385 g2 = bi_residue(ctx, bi_square(ctx, ctx->g[0])); /* g^2 */ | |
1386 | |
1387 for (i = 1; i < k; i++) | |
1388 { | |
1389 ctx->g[i] = bi_residue(ctx, bi_multiply(ctx, ctx->g[i-1], bi_copy(g2))); | |
1390 bi_permanent(ctx->g[i]); | |
1391 } | |
1392 | |
1393 bi_free(ctx, g2); | |
1394 ctx->window = k; | |
1395 } | |
1396 #endif | |
1397 | |
1398 /** | |
1399 * @brief Perform a modular exponentiation. | |
1400 * | |
1401 * This function requires bi_set_mod() to have been called previously. This is | |
1402 * one of the optimisations used for performance. | |
1403 * @param ctx [in] The bigint session context. | |
1404 * @param bi [in] The bigint on which to perform the mod power operation. | |
1405 * @param biexp [in] The bigint exponent. | |
1406 * @return The result of the mod exponentiation operation | |
1407 * @see bi_set_mod(). | |
1408 */ | |
1409 bigint *bi_mod_power(BI_CTX *ctx, bigint *bi, bigint *biexp) | |
1410 { | |
1411 int i = find_max_exp_index(biexp), j, window_size = 1; | |
1412 bigint *biR = int_to_bi(ctx, 1); | |
1413 | |
1414 #if defined(CONFIG_BIGINT_MONTGOMERY) | |
1415 uint8_t mod_offset = ctx->mod_offset; | |
1416 if (!ctx->use_classical) | |
1417 { | |
1418 /* preconvert */ | |
1419 bi = bi_mont(ctx, | |
1420 bi_multiply(ctx, bi, ctx->bi_RR_mod_m[mod_offset])); /* x' */ | |
1421 bi_free(ctx, biR); | |
1422 biR = ctx->bi_R_mod_m[mod_offset]; /* A */ | |
1423 } | |
1424 #endif | |
1425 | |
1426 check(bi); | |
1427 check(biexp); | |
1428 | |
1429 #ifdef CONFIG_BIGINT_SLIDING_WINDOW | |
1430 for (j = i; j > 32; j /= 5) /* work out an optimum size */ | |
1431 window_size++; | |
1432 | |
1433 /* work out the slide constants */ | |
1434 precompute_slide_window(ctx, window_size, bi); | |
1435 #else /* just one constant */ | |
1436 ctx->g = (bigint **)malloc(sizeof(bigint *)); | |
1437 ctx->g[0] = bi_clone(ctx, bi); | |
1438 ctx->window = 1; | |
1439 bi_permanent(ctx->g[0]); | |
1440 #endif | |
1441 | |
1442 /* if sliding-window is off, then only one bit will be done at a time and | |
1443 * will reduce to standard left-to-right exponentiation */ | |
1444 do | |
1445 { | |
1446 if (exp_bit_is_one(biexp, i)) | |
1447 { | |
1448 int l = i-window_size+1; | |
1449 int part_exp = 0; | |
1450 | |
1451 if (l < 0) /* LSB of exponent will always be 1 */ | |
1452 l = 0; | |
1453 else | |
1454 { | |
1455 while (exp_bit_is_one(biexp, l) == 0) | |
1456 l++; /* go back up */ | |
1457 } | |
1458 | |
1459 /* build up the section of the exponent */ | |
1460 for (j = i; j >= l; j--) | |
1461 { | |
1462 biR = bi_residue(ctx, bi_square(ctx, biR)); | |
1463 if (exp_bit_is_one(biexp, j)) | |
1464 part_exp++; | |
1465 | |
1466 if (j != l) | |
1467 part_exp <<= 1; | |
1468 } | |
1469 | |
1470 part_exp = (part_exp-1)/2; /* adjust for array */ | |
1471 biR = bi_residue(ctx, bi_multiply(ctx, biR, ctx->g[part_exp])); | |
1472 i = l-1; | |
1473 } | |
1474 else /* square it */ | |
1475 { | |
1476 biR = bi_residue(ctx, bi_square(ctx, biR)); | |
1477 i--; | |
1478 } | |
1479 } while (i >= 0); | |
1480 | |
1481 /* cleanup */ | |
1482 for (i = 0; i < ctx->window; i++) | |
1483 { | |
1484 bi_depermanent(ctx->g[i]); | |
1485 bi_free(ctx, ctx->g[i]); | |
1486 } | |
1487 | |
1488 free(ctx->g); | |
1489 bi_free(ctx, bi); | |
1490 bi_free(ctx, biexp); | |
1491 #if defined CONFIG_BIGINT_MONTGOMERY | |
1492 return ctx->use_classical ? biR : bi_mont(ctx, biR); /* convert back */ | |
1493 #else /* CONFIG_BIGINT_CLASSICAL or CONFIG_BIGINT_BARRETT */ | |
1494 return biR; | |
1495 #endif | |
1496 } | |
1497 | |
1498 #ifdef CONFIG_SSL_CERT_VERIFICATION | |
1499 /** | |
1500 * @brief Perform a modular exponentiation using a temporary modulus. | |
1501 * | |
1502 * We need this function to check the signatures of certificates. The modulus | |
1503 * of this function is temporary as it's just used for authentication. | |
1504 * @param ctx [in] The bigint session context. | |
1505 * @param bi [in] The bigint to perform the exp/mod. | |
1506 * @param bim [in] The temporary modulus. | |
1507 * @param biexp [in] The bigint exponent. | |
1508 * @return The result of the mod exponentiation operation | |
1509 * @see bi_set_mod(). | |
1510 */ | |
1511 bigint *bi_mod_power2(BI_CTX *ctx, bigint *bi, bigint *bim, bigint *biexp) | |
1512 { | |
1513 bigint *biR, *tmp_biR; | |
1514 | |
1515 /* Set up a temporary bigint context and transfer what we need between | |
1516 * them. We need to do this since we want to keep the original modulus | |
1517 * which is already in this context. This operation is only called when | |
1518 * doing peer verification, and so is not expensive :-) */ | |
1519 BI_CTX *tmp_ctx = bi_initialize(); | |
1520 bi_set_mod(tmp_ctx, bi_clone(tmp_ctx, bim), BIGINT_M_OFFSET); | |
1521 tmp_biR = bi_mod_power(tmp_ctx, | |
1522 bi_clone(tmp_ctx, bi), | |
1523 bi_clone(tmp_ctx, biexp)); | |
1524 biR = bi_clone(ctx, tmp_biR); | |
1525 bi_free(tmp_ctx, tmp_biR); | |
1526 bi_free_mod(tmp_ctx, BIGINT_M_OFFSET); | |
1527 bi_terminate(tmp_ctx); | |
1528 | |
1529 bi_free(ctx, bi); | |
1530 bi_free(ctx, bim); | |
1531 bi_free(ctx, biexp); | |
1532 return biR; | |
1533 } | |
1534 #endif | |
1535 | |
1536 #ifdef CONFIG_BIGINT_CRT | |
1537 /** | |
1538 * @brief Use the Chinese Remainder Theorem to quickly perform RSA decrypts. | |
1539 * | |
1540 * @param ctx [in] The bigint session context. | |
1541 * @param bi [in] The bigint to perform the exp/mod. | |
1542 * @param dP [in] CRT's dP bigint | |
1543 * @param dQ [in] CRT's dQ bigint | |
1544 * @param p [in] CRT's p bigint | |
1545 * @param q [in] CRT's q bigint | |
1546 * @param qInv [in] CRT's qInv bigint | |
1547 * @return The result of the CRT operation | |
1548 */ | |
1549 bigint *bi_crt(BI_CTX *ctx, bigint *bi, | |
1550 bigint *dP, bigint *dQ, | |
1551 bigint *p, bigint *q, bigint *qInv) | |
1552 { | |
1553 bigint *m1, *m2, *h; | |
1554 | |
1555 /* Montgomery has a condition the 0 < x, y < m and these products violate | |
1556 * that condition. So disable Montgomery when using CRT */ | |
1557 #if defined(CONFIG_BIGINT_MONTGOMERY) | |
1558 ctx->use_classical = 1; | |
1559 #endif | |
1560 ctx->mod_offset = BIGINT_P_OFFSET; | |
1561 m1 = bi_mod_power(ctx, bi_copy(bi), dP); | |
1562 | |
1563 ctx->mod_offset = BIGINT_Q_OFFSET; | |
1564 m2 = bi_mod_power(ctx, bi, dQ); | |
1565 | |
1566 h = bi_subtract(ctx, bi_add(ctx, m1, p), bi_copy(m2), NULL); | |
1567 h = bi_multiply(ctx, h, qInv); | |
1568 ctx->mod_offset = BIGINT_P_OFFSET; | |
1569 h = bi_residue(ctx, h); | |
1570 #if defined(CONFIG_BIGINT_MONTGOMERY) | |
1571 ctx->use_classical = 0; /* reset for any further operation */ | |
1572 #endif | |
1573 return bi_add(ctx, m2, bi_multiply(ctx, q, h)); | |
1574 } | |
1575 #endif | |
1576 /** @} */ |