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