bigint.c

00001 /*
00002  * Copyright (c) 2007, Cameron Rich
00003  * 
00004  * All rights reserved.
00005  * 
00006  * Redistribution and use in source and binary forms, with or without 
00007  * modification, are permitted provided that the following conditions are met:
00008  *
00009  * * Redistributions of source code must retain the above copyright notice, 
00010  *   this list of conditions and the following disclaimer.
00011  * * Redistributions in binary form must reproduce the above copyright notice, 
00012  *   this list of conditions and the following disclaimer in the documentation 
00013  *   and/or other materials provided with the distribution.
00014  * * Neither the name of the axTLS project nor the names of its contributors 
00015  *   may be used to endorse or promote products derived from this software 
00016  *   without specific prior written permission.
00017  *
00018  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
00019  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
00020  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
00021  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
00022  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
00023  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
00024  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
00025  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
00026  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
00027  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
00028  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00029  */
00030 
00031 /**
00032  * @defgroup bigint_api Big Integer API
00033  * @brief The bigint implementation as used by the axTLS project.
00034  *
00035  * The bigint library is for RSA encryption/decryption as well as signing.
00036  * This code tries to minimise use of malloc/free by maintaining a small 
00037  * cache. A bigint context may maintain state by being made "permanent". 
00038  * It be be later released with a bi_depermanent() and bi_free() call.
00039  *
00040  * It supports the following reduction techniques:
00041  * - Classical
00042  * - Barrett
00043  * - Montgomery
00044  *
00045  * It also implements the following:
00046  * - Karatsuba multiplication
00047  * - Squaring
00048  * - Sliding window exponentiation
00049  * - Chinese Remainder Theorem (implemented in rsa.c).
00050  *
00051  * All the algorithms used are pretty standard, and designed for different
00052  * data bus sizes. Negative numbers are not dealt with at all, so a subtraction
00053  * may need to be tested for negativity.
00054  *
00055  * This library steals some ideas from Jef Poskanzer
00056  * <http://cs.marlboro.edu/term/cs-fall02/algorithms/crypto/RSA/bigint>
00057  * and GMP <http://www.swox.com/gmp>. It gets most of its implementation
00058  * detail from "The Handbook of Applied Cryptography"
00059  * <http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf>
00060  * @{
00061  */
00062 
00063 #include <stdlib.h>
00064 #include <limits.h>
00065 #include <string.h>
00066 #include <stdio.h>
00067 #include <time.h>
00068 #include "os_port.h"
00069 #include "bigint.h"
00070 
00071 #define V1      v->comps[v->size-1]                 /**< v1 for division */
00072 #define V2      v->comps[v->size-2]                 /**< v2 for division */
00073 #define U(j)    tmp_u->comps[tmp_u->size-j-1]       /**< uj for division */
00074 #define Q(j)    quotient->comps[quotient->size-j-1] /**< qj for division */
00075 
00076 static bigint *bi_int_multiply(BI_CTX *ctx, bigint *bi, comp i);
00077 static bigint *bi_int_divide(BI_CTX *ctx, bigint *biR, comp denom);
00078 static bigint *alloc(BI_CTX *ctx, int size);
00079 static bigint *trim(bigint *bi);
00080 static void more_comps(bigint *bi, int n);
00081 #if defined(CONFIG_BIGINT_KARATSUBA) || defined(CONFIG_BIGINT_BARRETT) || \
00082     defined(CONFIG_BIGINT_MONTGOMERY)
00083 static bigint *comp_right_shift(bigint *biR, int num_shifts);
00084 static bigint *comp_left_shift(bigint *biR, int num_shifts);
00085 #endif
00086 
00087 #ifdef CONFIG_BIGINT_CHECK_ON
00088 static void check(const bigint *bi);
00089 #else
00090 #define check(A)                /**< disappears in normal production mode */
00091 #endif
00092 
00093 
00094 /**
00095  * @brief Start a new bigint context.
00096  * @return A bigint context.
00097  */
00098 BI_CTX *bi_initialize(void)
00099 {
00100     /* calloc() sets everything to zero */
00101     BI_CTX *ctx = (BI_CTX *)calloc(1, sizeof(BI_CTX));
00102    
00103     /* the radix */
00104     ctx->bi_radix = alloc(ctx, 2); 
00105     ctx->bi_radix->comps[0] = 0;
00106     ctx->bi_radix->comps[1] = 1;
00107     bi_permanent(ctx->bi_radix);
00108     return ctx;
00109 }
00110 
00111 /**
00112  * @brief Close the bigint context and free any resources.
00113  *
00114  * Free up any used memory - a check is done if all objects were not 
00115  * properly freed.
00116  * @param ctx [in]   The bigint session context.
00117  */
00118 void bi_terminate(BI_CTX *ctx)
00119 {
00120     bi_depermanent(ctx->bi_radix); 
00121     bi_free(ctx, ctx->bi_radix);
00122 
00123     if (ctx->active_count != 0)
00124     {
00125 #ifdef CONFIG_SSL_FULL_MODE
00126         printf("bi_terminate: there were %d un-freed bigints\n",
00127                        ctx->active_count);
00128 #endif
00129         abort();
00130     }
00131 
00132     bi_clear_cache(ctx);
00133     free(ctx);
00134 }
00135 
00136 /**
00137  *@brief Clear the memory cache.
00138  */
00139 void bi_clear_cache(BI_CTX *ctx)
00140 {
00141     bigint *p, *pn;
00142 
00143     if (ctx->free_list == NULL)
00144         return;
00145     
00146     for (p = ctx->free_list; p != NULL; p = pn)
00147     {
00148         pn = p->next;
00149         free(p->comps);
00150         free(p);
00151     }
00152 
00153     ctx->free_count = 0;
00154     ctx->free_list = NULL;
00155 }
00156 
00157 /**
00158  * @brief Increment the number of references to this object. 
00159  * It does not do a full copy.
00160  * @param bi [in]   The bigint to copy.
00161  * @return A reference to the same bigint.
00162  */
00163 bigint *bi_copy(bigint *bi)
00164 {
00165     check(bi);
00166     if (bi->refs != PERMANENT)
00167         bi->refs++;
00168     return bi;
00169 }
00170 
00171 /**
00172  * @brief Simply make a bigint object "unfreeable" if bi_free() is called on it.
00173  *
00174  * For this object to be freed, bi_depermanent() must be called.
00175  * @param bi [in]   The bigint to be made permanent.
00176  */
00177 void bi_permanent(bigint *bi)
00178 {
00179     check(bi);
00180     if (bi->refs != 1)
00181     {
00182 #ifdef CONFIG_SSL_FULL_MODE
00183         printf("bi_permanent: refs was not 1\n");
00184 #endif
00185         abort();
00186     }
00187 
00188     bi->refs = PERMANENT;
00189 }
00190 
00191 /**
00192  * @brief Take a permanent object and make it eligible for freedom.
00193  * @param bi [in]   The bigint to be made back to temporary.
00194  */
00195 void bi_depermanent(bigint *bi)
00196 {
00197     check(bi);
00198     if (bi->refs != PERMANENT)
00199     {
00200 #ifdef CONFIG_SSL_FULL_MODE
00201         printf("bi_depermanent: bigint was not permanent\n");
00202 #endif
00203         abort();
00204     }
00205 
00206     bi->refs = 1;
00207 }
00208 
00209 /**
00210  * @brief Free a bigint object so it can be used again. 
00211  *
00212  * The memory itself it not actually freed, just tagged as being available 
00213  * @param ctx [in]   The bigint session context.
00214  * @param bi [in]    The bigint to be freed.
00215  */
00216 void bi_free(BI_CTX *ctx, bigint *bi)
00217 {
00218     check(bi);
00219     if (bi->refs == PERMANENT)
00220     {
00221         return;
00222     }
00223 
00224     if (--bi->refs > 0)
00225     {
00226         return;
00227     }
00228 
00229     bi->next = ctx->free_list;
00230     ctx->free_list = bi;
00231     ctx->free_count++;
00232 
00233     if (--ctx->active_count < 0)
00234     {
00235 #ifdef CONFIG_SSL_FULL_MODE
00236         printf("bi_free: active_count went negative "
00237                 "- double-freed bigint?\n");
00238 #endif
00239         abort();
00240     }
00241 }
00242 
00243 /**
00244  * @brief Convert an (unsigned) integer into a bigint.
00245  * @param ctx [in]   The bigint session context.
00246  * @param i [in]     The (unsigned) integer to be converted.
00247  * 
00248  */
00249 bigint *int_to_bi(BI_CTX *ctx, comp i)
00250 {
00251     bigint *biR = alloc(ctx, 1);
00252     biR->comps[0] = i;
00253     return biR;
00254 }
00255 
00256 /**
00257  * @brief Do a full copy of the bigint object.
00258  * @param ctx [in]   The bigint session context.
00259  * @param bi  [in]   The bigint object to be copied.
00260  */
00261 bigint *bi_clone(BI_CTX *ctx, const bigint *bi)
00262 {
00263     bigint *biR = alloc(ctx, bi->size);
00264     check(bi);
00265     memcpy(biR->comps, bi->comps, bi->size*COMP_BYTE_SIZE);
00266     return biR;
00267 }
00268 
00269 /**
00270  * @brief Perform an addition operation between two bigints.
00271  * @param ctx [in]  The bigint session context.
00272  * @param bia [in]  A bigint.
00273  * @param bib [in]  Another bigint.
00274  * @return The result of the addition.
00275  */
00276 bigint *bi_add(BI_CTX *ctx, bigint *bia, bigint *bib)
00277 {
00278     int n;
00279     comp carry = 0;
00280     comp *pa, *pb;
00281 
00282     check(bia);
00283     check(bib);
00284 
00285     n = max(bia->size, bib->size);
00286     more_comps(bia, n+1);
00287     more_comps(bib, n);
00288     pa = bia->comps;
00289     pb = bib->comps;
00290 
00291     do
00292     {
00293         comp  sl, rl, cy1;
00294         sl = *pa + *pb++;
00295         rl = sl + carry;
00296         cy1 = sl < *pa;
00297         carry = cy1 | (rl < sl);
00298         *pa++ = rl;
00299     } while (--n != 0);
00300 
00301     *pa = carry;                  /* do overflow */
00302     bi_free(ctx, bib);
00303     return trim(bia);
00304 }
00305 
00306 /**
00307  * @brief Perform a subtraction operation between two bigints.
00308  * @param ctx [in]  The bigint session context.
00309  * @param bia [in]  A bigint.
00310  * @param bib [in]  Another bigint.
00311  * @param is_negative [out] If defined, indicates that the result was negative.
00312  * is_negative may be null.
00313  * @return The result of the subtraction. The result is always positive.
00314  */
00315 bigint *bi_subtract(BI_CTX *ctx, 
00316         bigint *bia, bigint *bib, int *is_negative)
00317 {
00318     int n = bia->size;
00319     comp *pa, *pb, carry = 0;
00320 
00321     check(bia);
00322     check(bib);
00323 
00324     more_comps(bib, n);
00325     pa = bia->comps;
00326     pb = bib->comps;
00327 
00328     do 
00329     {
00330         comp sl, rl, cy1;
00331         sl = *pa - *pb++;
00332         rl = sl - carry;
00333         cy1 = sl > *pa;
00334         carry = cy1 | (rl > sl);
00335         *pa++ = rl;
00336     } while (--n != 0);
00337 
00338     if (is_negative)    /* indicate a negative result */
00339     {
00340         *is_negative = carry;
00341     }
00342 
00343     bi_free(ctx, trim(bib));    /* put bib back to the way it was */
00344     return trim(bia);
00345 }
00346 
00347 /**
00348  * Perform a multiply between a bigint an an (unsigned) integer
00349  */
00350 static bigint *bi_int_multiply(BI_CTX *ctx, bigint *bia, comp b)
00351 {
00352     int j = 0, n = bia->size;
00353     bigint *biR = alloc(ctx, n + 1);
00354     comp carry = 0;
00355     comp *r = biR->comps;
00356     comp *a = bia->comps;
00357 
00358     check(bia);
00359 
00360     /* clear things to start with */
00361     memset(r, 0, ((n+1)*COMP_BYTE_SIZE));
00362 
00363     do
00364     {
00365         long_comp tmp = *r + (long_comp)a[j]*b + carry;
00366         *r++ = (comp)tmp;              /* downsize */
00367         carry = (comp)(tmp >> COMP_BIT_SIZE);
00368     } while (++j < n);
00369 
00370     *r = carry;
00371     bi_free(ctx, bia);
00372     return trim(biR);
00373 }
00374 
00375 /**
00376  * @brief Does both division and modulo calculations. 
00377  *
00378  * Used extensively when doing classical reduction.
00379  * @param ctx [in]  The bigint session context.
00380  * @param u [in]    A bigint which is the numerator.
00381  * @param v [in]    Either the denominator or the modulus depending on the mode.
00382  * @param is_mod [n] Determines if this is a normal division (0) or a reduction
00383  * (1).
00384  * @return  The result of the division/reduction.
00385  */
00386 bigint *bi_divide(BI_CTX *ctx, bigint *u, bigint *v, int is_mod)
00387 {
00388     int n = v->size, m = u->size-n;
00389     int j = 0, orig_u_size = u->size;
00390     uint8_t mod_offset = ctx->mod_offset;
00391     comp d;
00392     bigint *quotient, *tmp_u;
00393     comp q_dash;
00394 
00395     check(u);
00396     check(v);
00397 
00398     /* if doing reduction and we are < mod, then return mod */
00399     if (is_mod && bi_compare(v, u) > 0)
00400     {
00401         bi_free(ctx, v);
00402         return u;
00403     }
00404 
00405     quotient = alloc(ctx, m+1);
00406     tmp_u = alloc(ctx, n+1);
00407     v = trim(v);        /* make sure we have no leading 0's */
00408     d = (comp)((long_comp)COMP_RADIX/(V1+1));
00409 
00410     /* clear things to start with */
00411     memset(quotient->comps, 0, ((quotient->size)*COMP_BYTE_SIZE));
00412 
00413     /* normalise */
00414     if (d > 1)
00415     {
00416         u = bi_int_multiply(ctx, u, d);
00417 
00418         if (is_mod)
00419         {
00420             v = ctx->bi_normalised_mod[mod_offset];
00421         }
00422         else
00423         {
00424             v = bi_int_multiply(ctx, v, d);
00425         }
00426     }
00427 
00428     if (orig_u_size == u->size)  /* new digit position u0 */
00429     {
00430         more_comps(u, orig_u_size + 1);
00431     }
00432 
00433     do
00434     {
00435         /* get a temporary short version of u */
00436         memcpy(tmp_u->comps, &u->comps[u->size-n-1-j], (n+1)*COMP_BYTE_SIZE);
00437 
00438         /* calculate q' */
00439         if (U(0) == V1)
00440         {
00441             q_dash = COMP_RADIX-1;
00442         }
00443         else
00444         {
00445             q_dash = (comp)(((long_comp)U(0)*COMP_RADIX + U(1))/V1);
00446 
00447             if (v->size > 1 && V2)
00448             {
00449                 /* we are implementing the following:
00450                 if (V2*q_dash > (((U(0)*COMP_RADIX + U(1) - 
00451                         q_dash*V1)*COMP_RADIX) + U(2))) ... */
00452                 comp inner = (comp)((long_comp)COMP_RADIX*U(0) + U(1) - 
00453                                             (long_comp)q_dash*V1);
00454                 if ((long_comp)V2*q_dash > (long_comp)inner*COMP_RADIX + U(2))
00455                 {
00456                     q_dash--;
00457                 }
00458             }
00459         }
00460 
00461         /* multiply and subtract */
00462         if (q_dash)
00463         {
00464             int is_negative;
00465             tmp_u = bi_subtract(ctx, tmp_u, 
00466                     bi_int_multiply(ctx, bi_copy(v), q_dash), &is_negative);
00467             more_comps(tmp_u, n+1);
00468 
00469             Q(j) = q_dash; 
00470 
00471             /* add back */
00472             if (is_negative)
00473             {
00474                 Q(j)--;
00475                 tmp_u = bi_add(ctx, tmp_u, bi_copy(v));
00476 
00477                 /* lop off the carry */
00478                 tmp_u->size--;
00479                 v->size--;
00480             }
00481         }
00482         else
00483         {
00484             Q(j) = 0; 
00485         }
00486 
00487         /* copy back to u */
00488         memcpy(&u->comps[u->size-n-1-j], tmp_u->comps, (n+1)*COMP_BYTE_SIZE);
00489     } while (++j <= m);
00490 
00491     bi_free(ctx, tmp_u);
00492     bi_free(ctx, v);
00493 
00494     if (is_mod)     /* get the remainder */
00495     {
00496         bi_free(ctx, quotient);
00497         return bi_int_divide(ctx, trim(u), d);
00498     }
00499     else            /* get the quotient */
00500     {
00501         bi_free(ctx, u);
00502         return trim(quotient);
00503     }
00504 }
00505 
00506 /*
00507  * Perform an integer divide on a bigint.
00508  */
00509 static bigint *bi_int_divide(BI_CTX *ctx, bigint *biR, comp denom)
00510 {
00511     int i = biR->size - 1;
00512     long_comp r = 0;
00513 
00514     check(biR);
00515 
00516     do
00517     {
00518         r = (r<<COMP_BIT_SIZE) + biR->comps[i];
00519         biR->comps[i] = (comp)(r / denom);
00520         r %= denom;
00521     } while (--i >= 0);
00522 
00523     return trim(biR);
00524 }
00525 
00526 #ifdef CONFIG_BIGINT_MONTGOMERY
00527 /**
00528  * There is a need for the value of integer N' such that B^-1(B-1)-N^-1N'=1, 
00529  * where B^-1(B-1) mod N=1. Actually, only the least significant part of 
00530  * N' is needed, hence the definition N0'=N' mod b. We reproduce below the 
00531  * simple algorithm from an article by Dusse and Kaliski to efficiently 
00532  * find N0' from N0 and b */
00533 static comp modular_inverse(bigint *bim)
00534 {
00535     int i;
00536     comp t = 1;
00537     comp two_2_i_minus_1 = 2;   /* 2^(i-1) */
00538     long_comp two_2_i = 4;      /* 2^i */
00539     comp N = bim->comps[0];
00540 
00541     for (i = 2; i <= COMP_BIT_SIZE; i++)
00542     {
00543         if ((long_comp)N*t%two_2_i >= two_2_i_minus_1)
00544         {
00545             t += two_2_i_minus_1;
00546         }
00547 
00548         two_2_i_minus_1 <<= 1;
00549         two_2_i <<= 1;
00550     }
00551 
00552     return (comp)(COMP_RADIX-t);
00553 }
00554 #endif
00555 
00556 #if defined(CONFIG_BIGINT_KARATSUBA) || defined(CONFIG_BIGINT_BARRETT) || \
00557     defined(CONFIG_BIGINT_MONTGOMERY)
00558 /**
00559  * Take each component and shift down (in terms of components) 
00560  */
00561 static bigint *comp_right_shift(bigint *biR, int num_shifts)
00562 {
00563     int i = biR->size-num_shifts;
00564     comp *x = biR->comps;
00565     comp *y = &biR->comps[num_shifts];
00566 
00567     check(biR);
00568 
00569     if (i <= 0)     /* have we completely right shifted? */
00570     {
00571         biR->comps[0] = 0;  /* return 0 */
00572         biR->size = 1;
00573         return biR;
00574     }
00575 
00576     do
00577     {
00578         *x++ = *y++;
00579     } while (--i > 0);
00580 
00581     biR->size -= num_shifts;
00582     return biR;
00583 }
00584 
00585 /**
00586  * Take each component and shift it up (in terms of components) 
00587  */
00588 static bigint *comp_left_shift(bigint *biR, int num_shifts)
00589 {
00590     int i = biR->size-1;
00591     comp *x, *y;
00592 
00593     check(biR);
00594 
00595     if (num_shifts <= 0)
00596     {
00597         return biR;
00598     }
00599 
00600     more_comps(biR, biR->size + num_shifts);
00601 
00602     x = &biR->comps[i+num_shifts];
00603     y = &biR->comps[i];
00604 
00605     do
00606     {
00607         *x-- = *y--;
00608     } while (i--);
00609 
00610     memset(biR->comps, 0, num_shifts*COMP_BYTE_SIZE); /* zero LS comps */
00611     return biR;
00612 }
00613 #endif
00614 
00615 /**
00616  * @brief Allow a binary sequence to be imported as a bigint.
00617  * @param ctx [in]  The bigint session context.
00618  * @param data [in] The data to be converted.
00619  * @param size [in] The number of bytes of data.
00620  * @return A bigint representing this data.
00621  */
00622 bigint *bi_import(BI_CTX *ctx, const uint8_t *data, int size)
00623 {
00624     bigint *biR = alloc(ctx, (size+COMP_BYTE_SIZE-1)/COMP_BYTE_SIZE);
00625     int i, j = 0, offset = 0;
00626 
00627     memset(biR->comps, 0, biR->size*COMP_BYTE_SIZE);
00628 
00629     for (i = size-1; i >= 0; i--)
00630     {
00631         biR->comps[offset] += data[i] << (j*8);
00632 
00633         if (++j == COMP_BYTE_SIZE)
00634         {
00635             j = 0;
00636             offset ++;
00637         }
00638     }
00639 
00640     return trim(biR);
00641 }
00642 
00643 #ifdef CONFIG_SSL_FULL_MODE
00644 /**
00645  * @brief The testharness uses this code to import text hex-streams and 
00646  * convert them into bigints.
00647  * @param ctx [in]  The bigint session context.
00648  * @param data [in] A string consisting of hex characters. The characters must
00649  * be in upper case.
00650  * @return A bigint representing this data.
00651  */
00652 bigint *bi_str_import(BI_CTX *ctx, const char *data)
00653 {
00654     int size = strlen(data);
00655     bigint *biR = alloc(ctx, (size+COMP_NUM_NIBBLES-1)/COMP_NUM_NIBBLES);
00656     int i, j = 0, offset = 0;
00657     memset(biR->comps, 0, biR->size*COMP_BYTE_SIZE);
00658 
00659     for (i = size-1; i >= 0; i--)
00660     {
00661         int num = (data[i] <= '9') ? (data[i] - '0') : (data[i] - 'A' + 10);
00662         biR->comps[offset] += num << (j*4);
00663 
00664         if (++j == COMP_NUM_NIBBLES)
00665         {
00666             j = 0;
00667             offset ++;
00668         }
00669     }
00670 
00671     return biR;
00672 }
00673 
00674 void bi_print(const char *label, bigint *x)
00675 {
00676     int i, j;
00677 
00678     if (x == NULL)
00679     {
00680         printf("%s: (null)\n", label);
00681         return;
00682     }
00683 
00684     printf("%s: (size %d)\n", label, x->size);
00685     for (i = x->size-1; i >= 0; i--)
00686     {
00687         for (j = COMP_NUM_NIBBLES-1; j >= 0; j--)
00688         {
00689             comp mask = 0x0f << (j*4);
00690             comp num = (x->comps[i] & mask) >> (j*4);
00691             putc((num <= 9) ? (num + '0') : (num + 'A' - 10), stdout);
00692         }
00693     }  
00694 
00695     printf("\r\n");
00696 }
00697 #endif
00698 
00699 /**
00700  * @brief Take a bigint and convert it into a byte sequence. 
00701  *
00702  * This is useful after a decrypt operation.
00703  * @param ctx [in]  The bigint session context.
00704  * @param x [in]  The bigint to be converted.
00705  * @param data [out] The converted data as a byte stream.
00706  * @param size [in] The maximum size of the byte stream. Unused bytes will be
00707  * zeroed.
00708  */
00709 void bi_export(BI_CTX *ctx, bigint *x, uint8_t *data, int size)
00710 {
00711     int i, j, k = size-1;
00712 
00713     check(x);
00714     memset(data, 0, size);  /* ensure all leading 0's are cleared */
00715 
00716     for (i = 0; i < x->size; i++)
00717     {
00718         for (j = 0; j < COMP_BYTE_SIZE; j++)
00719         {
00720             comp mask = 0xff << (j*8);
00721             int num = (x->comps[i] & mask) >> (j*8);
00722             data[k--] = num;
00723 
00724             if (k < 0)
00725             {
00726                 goto buf_done;
00727             }
00728         }
00729     }
00730 buf_done:
00731 
00732     bi_free(ctx, x);
00733 }
00734 
00735 /**
00736  * @brief Pre-calculate some of the expensive steps in reduction. 
00737  *
00738  * This function should only be called once (normally when a session starts).
00739  * When the session is over, bi_free_mod() should be called. bi_mod_power()
00740  * relies on this function being called.
00741  * @param ctx [in]  The bigint session context.
00742  * @param bim [in]  The bigint modulus that will be used.
00743  * @param mod_offset [in] There are three moduluii that can be stored - the
00744  * standard modulus, and its two primes p and q. This offset refers to which
00745  * modulus we are referring to.
00746  * @see bi_free_mod(), bi_mod_power().
00747  */
00748 void bi_set_mod(BI_CTX *ctx, bigint *bim, int mod_offset)
00749 {
00750     int k = bim->size;
00751     comp d = (comp)((long_comp)COMP_RADIX/(bim->comps[k-1]+1));
00752 #ifdef CONFIG_BIGINT_MONTGOMERY
00753     bigint *R, *R2;
00754 #endif
00755 
00756     ctx->bi_mod[mod_offset] = bim;
00757     bi_permanent(ctx->bi_mod[mod_offset]);
00758     ctx->bi_normalised_mod[mod_offset] = bi_int_multiply(ctx, bim, d);
00759     bi_permanent(ctx->bi_normalised_mod[mod_offset]);
00760 
00761 #if defined(CONFIG_BIGINT_MONTGOMERY)
00762     /* set montgomery variables */
00763     R = comp_left_shift(bi_clone(ctx, ctx->bi_radix), k-1);     /* R */
00764     R2 = comp_left_shift(bi_clone(ctx, ctx->bi_radix), k*2-1);  /* R^2 */
00765     ctx->bi_RR_mod_m[mod_offset] = bi_mod(ctx, R2);             /* R^2 mod m */
00766     ctx->bi_R_mod_m[mod_offset] = bi_mod(ctx, R);               /* R mod m */
00767 
00768     bi_permanent(ctx->bi_RR_mod_m[mod_offset]);
00769     bi_permanent(ctx->bi_R_mod_m[mod_offset]);
00770 
00771     ctx->N0_dash[mod_offset] = modular_inverse(ctx->bi_mod[mod_offset]);
00772 
00773 #elif defined (CONFIG_BIGINT_BARRETT)
00774     ctx->bi_mu[mod_offset] = 
00775         bi_divide(ctx, comp_left_shift(
00776             bi_clone(ctx, ctx->bi_radix), k*2-1), ctx->bi_mod[mod_offset], 0);
00777     bi_permanent(ctx->bi_mu[mod_offset]);
00778 #endif
00779 }
00780 
00781 /**
00782  * @brief Used when cleaning various bigints at the end of a session.
00783  * @param ctx [in]  The bigint session context.
00784  * @param mod_offset [in] The offset to use.
00785  * @see bi_set_mod().
00786  */
00787 void bi_free_mod(BI_CTX *ctx, int mod_offset)
00788 {
00789     bi_depermanent(ctx->bi_mod[mod_offset]);
00790     bi_free(ctx, ctx->bi_mod[mod_offset]);
00791 #if defined (CONFIG_BIGINT_MONTGOMERY)
00792     bi_depermanent(ctx->bi_RR_mod_m[mod_offset]);
00793     bi_depermanent(ctx->bi_R_mod_m[mod_offset]);
00794     bi_free(ctx, ctx->bi_RR_mod_m[mod_offset]);
00795     bi_free(ctx, ctx->bi_R_mod_m[mod_offset]);
00796 #elif defined(CONFIG_BIGINT_BARRETT)
00797     bi_depermanent(ctx->bi_mu[mod_offset]); 
00798     bi_free(ctx, ctx->bi_mu[mod_offset]);
00799 #endif
00800     bi_depermanent(ctx->bi_normalised_mod[mod_offset]); 
00801     bi_free(ctx, ctx->bi_normalised_mod[mod_offset]);
00802 }
00803 
00804 /** 
00805  * Perform a standard multiplication between two bigints.
00806  *
00807  * Barrett reduction has no need for some parts of the product, so ignore bits
00808  * of the multiply. This routine gives Barrett its big performance
00809  * improvements over Classical/Montgomery reduction methods. 
00810  */
00811 static bigint *regular_multiply(BI_CTX *ctx, bigint *bia, bigint *bib, 
00812         int inner_partial, int outer_partial)
00813 {
00814     int i = 0, j;
00815     int n = bia->size;
00816     int t = bib->size;
00817     bigint *biR = alloc(ctx, n + t);
00818     comp *sr = biR->comps;
00819     comp *sa = bia->comps;
00820     comp *sb = bib->comps;
00821 
00822     check(bia);
00823     check(bib);
00824 
00825     /* clear things to start with */
00826     memset(biR->comps, 0, ((n+t)*COMP_BYTE_SIZE));
00827 
00828     do 
00829     {
00830         long_comp tmp;
00831         comp carry = 0;
00832         int r_index = i;
00833         j = 0;
00834 
00835         if (outer_partial && outer_partial-i > 0 && outer_partial < n)
00836         {
00837             r_index = outer_partial-1;
00838             j = outer_partial-i-1;
00839         }
00840 
00841         do
00842         {
00843             if (inner_partial && r_index >= inner_partial) 
00844             {
00845                 break;
00846             }
00847 
00848             tmp = sr[r_index] + ((long_comp)sa[j])*sb[i] + carry;
00849             sr[r_index++] = (comp)tmp;              /* downsize */
00850             carry = tmp >> COMP_BIT_SIZE;
00851         } while (++j < n);
00852 
00853         sr[r_index] = carry;
00854     } while (++i < t);
00855 
00856     bi_free(ctx, bia);
00857     bi_free(ctx, bib);
00858     return trim(biR);
00859 }
00860 
00861 #ifdef CONFIG_BIGINT_KARATSUBA
00862 /*
00863  * Karatsuba improves on regular multiplication due to only 3 multiplications 
00864  * being done instead of 4. The additional additions/subtractions are O(N) 
00865  * rather than O(N^2) and so for big numbers it saves on a few operations 
00866  */
00867 static bigint *karatsuba(BI_CTX *ctx, bigint *bia, bigint *bib, int is_square)
00868 {
00869     bigint *x0, *x1;
00870     bigint *p0, *p1, *p2;
00871     int m;
00872 
00873     if (is_square)
00874     {
00875         m = (bia->size + 1)/2;
00876     }
00877     else
00878     {
00879         m = (max(bia->size, bib->size) + 1)/2;
00880     }
00881 
00882     x0 = bi_clone(ctx, bia);
00883     x0->size = m;
00884     x1 = bi_clone(ctx, bia);
00885     comp_right_shift(x1, m);
00886     bi_free(ctx, bia);
00887 
00888     /* work out the 3 partial products */
00889     if (is_square)
00890     {
00891         p0 = bi_square(ctx, bi_copy(x0));
00892         p2 = bi_square(ctx, bi_copy(x1));
00893         p1 = bi_square(ctx, bi_add(ctx, x0, x1));
00894     }
00895     else /* normal multiply */
00896     {
00897         bigint *y0, *y1;
00898         y0 = bi_clone(ctx, bib);
00899         y0->size = m;
00900         y1 = bi_clone(ctx, bib);
00901         comp_right_shift(y1, m);
00902         bi_free(ctx, bib);
00903 
00904         p0 = bi_multiply(ctx, bi_copy(x0), bi_copy(y0));
00905         p2 = bi_multiply(ctx, bi_copy(x1), bi_copy(y1));
00906         p1 = bi_multiply(ctx, bi_add(ctx, x0, x1), bi_add(ctx, y0, y1));
00907     }
00908 
00909     p1 = bi_subtract(ctx, 
00910             bi_subtract(ctx, p1, bi_copy(p2), NULL), bi_copy(p0), NULL);
00911 
00912     comp_left_shift(p1, m);
00913     comp_left_shift(p2, 2*m);
00914     return bi_add(ctx, p1, bi_add(ctx, p0, p2));
00915 }
00916 #endif
00917 
00918 /**
00919  * @brief Perform a multiplication operation between two bigints.
00920  * @param ctx [in]  The bigint session context.
00921  * @param bia [in]  A bigint.
00922  * @param bib [in]  Another bigint.
00923  * @return The result of the multiplication.
00924  */
00925 bigint *bi_multiply(BI_CTX *ctx, bigint *bia, bigint *bib)
00926 {
00927     check(bia);
00928     check(bib);
00929 
00930 #ifdef CONFIG_BIGINT_KARATSUBA
00931     if (min(bia->size, bib->size) < MUL_KARATSUBA_THRESH)
00932     {
00933         return regular_multiply(ctx, bia, bib, 0, 0);
00934     }
00935 
00936     return karatsuba(ctx, bia, bib, 0);
00937 #else
00938     return regular_multiply(ctx, bia, bib, 0, 0);
00939 #endif
00940 }
00941 
00942 #ifdef CONFIG_BIGINT_SQUARE
00943 /*
00944  * Perform the actual square operion. It takes into account overflow.
00945  */
00946 static bigint *regular_square(BI_CTX *ctx, bigint *bi)
00947 {
00948     int t = bi->size;
00949     int i = 0, j;
00950     bigint *biR = alloc(ctx, t*2+1);
00951     comp *w = biR->comps;
00952     comp *x = bi->comps;
00953     long_comp carry;
00954     memset(w, 0, biR->size*COMP_BYTE_SIZE);
00955 
00956     do
00957     {
00958         long_comp tmp = w[2*i] + (long_comp)x[i]*x[i];
00959         w[2*i] = (comp)tmp;
00960         carry = tmp >> COMP_BIT_SIZE;
00961 
00962         for (j = i+1; j < t; j++)
00963         {
00964             uint8_t c = 0;
00965             long_comp xx = (long_comp)x[i]*x[j];
00966             if ((COMP_MAX-xx) < xx)
00967                 c = 1;
00968 
00969             tmp = (xx<<1);
00970 
00971             if ((COMP_MAX-tmp) < w[i+j])
00972                 c = 1;
00973 
00974             tmp += w[i+j];
00975 
00976             if ((COMP_MAX-tmp) < carry)
00977                 c = 1;
00978 
00979             tmp += carry;
00980             w[i+j] = (comp)tmp;
00981             carry = tmp >> COMP_BIT_SIZE;
00982 
00983             if (c)
00984                 carry += COMP_RADIX;
00985         }
00986 
00987         tmp = w[i+t] + carry;
00988         w[i+t] = (comp)tmp;
00989         w[i+t+1] = tmp >> COMP_BIT_SIZE;
00990     } while (++i < t);
00991 
00992     bi_free(ctx, bi);
00993     return trim(biR);
00994 }
00995 
00996 /**
00997  * @brief Perform a square operation on a bigint.
00998  * @param ctx [in]  The bigint session context.
00999  * @param bia [in]  A bigint.
01000  * @return The result of the multiplication.
01001  */
01002 bigint *bi_square(BI_CTX *ctx, bigint *bia)
01003 {
01004     check(bia);
01005 
01006 #ifdef CONFIG_BIGINT_KARATSUBA
01007     if (bia->size < SQU_KARATSUBA_THRESH) 
01008     {
01009         return regular_square(ctx, bia);
01010     }
01011 
01012     return karatsuba(ctx, bia, NULL, 1);
01013 #else
01014     return regular_square(ctx, bia);
01015 #endif
01016 }
01017 #endif
01018 
01019 /**
01020  * @brief Compare two bigints.
01021  * @param bia [in]  A bigint.
01022  * @param bib [in]  Another bigint.
01023  * @return -1 if smaller, 1 if larger and 0 if equal.
01024  */
01025 int bi_compare(bigint *bia, bigint *bib)
01026 {
01027     int r, i;
01028 
01029     check(bia);
01030     check(bib);
01031 
01032     if (bia->size > bib->size)
01033         r = 1;
01034     else if (bia->size < bib->size)
01035         r = -1;
01036     else
01037     {
01038         comp *a = bia->comps; 
01039         comp *b = bib->comps; 
01040 
01041         /* Same number of components.  Compare starting from the high end
01042          * and working down. */
01043         r = 0;
01044         i = bia->size - 1;
01045 
01046         do 
01047         {
01048             if (a[i] > b[i])
01049             { 
01050                 r = 1;
01051                 break; 
01052             }
01053             else if (a[i] < b[i])
01054             { 
01055                 r = -1;
01056                 break; 
01057             }
01058         } while (--i >= 0);
01059     }
01060 
01061     return r;
01062 }
01063 
01064 /*
01065  * Allocate and zero more components.  Does not consume bi. 
01066  */
01067 static void more_comps(bigint *bi, int n)
01068 {
01069     if (n > bi->max_comps)
01070     {
01071         bi->max_comps = max(bi->max_comps * 2, n);
01072         bi->comps = (comp*)realloc(bi->comps, bi->max_comps * COMP_BYTE_SIZE);
01073     }
01074 
01075     if (n > bi->size)
01076     {
01077         memset(&bi->comps[bi->size], 0, (n-bi->size)*COMP_BYTE_SIZE);
01078     }
01079 
01080     bi->size = n;
01081 }
01082 
01083 /*
01084  * Make a new empty bigint. It may just use an old one if one is available.
01085  * Otherwise get one off the heap.
01086  */
01087 static bigint *alloc(BI_CTX *ctx, int size)
01088 {
01089     bigint *biR;
01090 
01091     /* Can we recycle an old bigint? */
01092     if (ctx->free_list != NULL)
01093     {
01094         biR = ctx->free_list;
01095         ctx->free_list = biR->next;
01096         ctx->free_count--;
01097 
01098         if (biR->refs != 0)
01099         {
01100 #ifdef CONFIG_SSL_FULL_MODE
01101             printf("alloc: refs was not 0\n");
01102 #endif
01103             abort();    /* create a stack trace from a core dump */
01104         }
01105 
01106         more_comps(biR, size);
01107     }
01108     else
01109     {
01110         /* No free bigints available - create a new one. */
01111         biR = (bigint *)malloc(sizeof(bigint));
01112         biR->comps = (comp*)malloc(size * COMP_BYTE_SIZE);
01113         biR->max_comps = size;  /* give some space to spare */
01114     }
01115 
01116     biR->size = size;
01117     biR->refs = 1;
01118     biR->next = NULL;
01119     ctx->active_count++;
01120     return biR;
01121 }
01122 
01123 /*
01124  * Work out the highest '1' bit in an exponent. Used when doing sliding-window
01125  * exponentiation.
01126  */
01127 static int find_max_exp_index(bigint *biexp)
01128 {
01129     int i = COMP_BIT_SIZE-1;
01130     comp shift = COMP_RADIX/2;
01131     comp test = biexp->comps[biexp->size-1];    /* assume no leading zeroes */
01132 
01133     check(biexp);
01134 
01135     do
01136     {
01137         if (test & shift)
01138         {
01139             return i+(biexp->size-1)*COMP_BIT_SIZE;
01140         }
01141 
01142         shift >>= 1;
01143     } while (i-- != 0);
01144 
01145     return -1;      /* error - must have been a leading 0 */
01146 }
01147 
01148 /*
01149  * Is a particular bit is an exponent 1 or 0? Used when doing sliding-window
01150  * exponentiation.
01151  */
01152 static int exp_bit_is_one(bigint *biexp, int offset)
01153 {
01154     comp test = biexp->comps[offset / COMP_BIT_SIZE];
01155     int num_shifts = offset % COMP_BIT_SIZE;
01156     comp shift = 1;
01157     int i;
01158 
01159     check(biexp);
01160 
01161     for (i = 0; i < num_shifts; i++)
01162     {
01163         shift <<= 1;
01164     }
01165 
01166     return (test & shift) != 0;
01167 }
01168 
01169 #ifdef CONFIG_BIGINT_CHECK_ON
01170 /*
01171  * Perform a sanity check on bi.
01172  */
01173 static void check(const bigint *bi)
01174 {
01175     if (bi->refs <= 0)
01176     {
01177         printf("check: zero or negative refs in bigint\n");
01178         abort();
01179     }
01180 
01181     if (bi->next != NULL)
01182     {
01183         printf("check: attempt to use a bigint from "
01184                 "the free list\n");
01185         abort();
01186     }
01187 }
01188 #endif
01189 
01190 /*
01191  * Delete any leading 0's (and allow for 0).
01192  */
01193 static bigint *trim(bigint *bi)
01194 {
01195     check(bi);
01196 
01197     while (bi->comps[bi->size-1] == 0 && bi->size > 1)
01198     {
01199         bi->size--;
01200     }
01201 
01202     return bi;
01203 }
01204 
01205 #if defined(CONFIG_BIGINT_MONTGOMERY)
01206 /**
01207  * @brief Perform a single montgomery reduction.
01208  * @param ctx [in]  The bigint session context.
01209  * @param bixy [in]  A bigint.
01210  * @return The result of the montgomery reduction.
01211  */
01212 bigint *bi_mont(BI_CTX *ctx, bigint *bixy)
01213 {
01214     int i = 0, n;
01215     uint8_t mod_offset = ctx->mod_offset;
01216     bigint *bim = ctx->bi_mod[mod_offset];
01217     comp mod_inv = ctx->N0_dash[mod_offset];
01218 
01219     check(bixy);
01220 
01221     if (ctx->use_classical)     /* just use classical instead */
01222     {
01223         return bi_mod(ctx, bixy);
01224     }
01225 
01226     n = bim->size;
01227 
01228     do
01229     {
01230         bixy = bi_add(ctx, bixy, comp_left_shift(
01231                     bi_int_multiply(ctx, bim, bixy->comps[i]*mod_inv), i));
01232     } while (++i < n);
01233 
01234     comp_right_shift(bixy, n);
01235 
01236     if (bi_compare(bixy, bim) >= 0)
01237     {
01238         bixy = bi_subtract(ctx, bixy, bim, NULL);
01239     }
01240 
01241     return bixy;
01242 }
01243 
01244 #elif defined(CONFIG_BIGINT_BARRETT)
01245 /*
01246  * Stomp on the most significant components to give the illusion of a "mod base
01247  * radix" operation 
01248  */
01249 static bigint *comp_mod(bigint *bi, int mod)
01250 {
01251     check(bi);
01252 
01253     if (bi->size > mod)
01254     {
01255         bi->size = mod;
01256     }
01257 
01258     return bi;
01259 }
01260 
01261 /**
01262  * @brief Perform a single Barrett reduction.
01263  * @param ctx [in]  The bigint session context.
01264  * @param bi [in]  A bigint.
01265  * @return The result of the Barrett reduction.
01266  */
01267 bigint *bi_barrett(BI_CTX *ctx, bigint *bi)
01268 {
01269     bigint *q1, *q2, *q3, *r1, *r2, *r;
01270     uint8_t mod_offset = ctx->mod_offset;
01271     bigint *bim = ctx->bi_mod[mod_offset];
01272     int k = bim->size;
01273 
01274     check(bi);
01275     check(bim);
01276 
01277     /* use Classical method instead  - Barrett cannot help here */
01278     if (bi->size > k*2)
01279     {
01280         return bi_mod(ctx, bi);
01281     }
01282 
01283     q1 = comp_right_shift(bi_clone(ctx, bi), k-1);
01284 
01285     /* do outer partial multiply */
01286     q2 = regular_multiply(ctx, q1, ctx->bi_mu[mod_offset], 0, k-1); 
01287     q3 = comp_right_shift(q2, k+1);
01288     r1 = comp_mod(bi, k+1);
01289 
01290     /* do inner partial multiply */
01291     r2 = comp_mod(regular_multiply(ctx, q3, bim, k+1, 0), k+1);
01292     r = bi_subtract(ctx, r1, r2, NULL);
01293 
01294     /* if (r >= m) r = r - m; */
01295     if (bi_compare(r, bim) >= 0)
01296     {
01297         r = bi_subtract(ctx, r, bim, NULL);
01298     }
01299 
01300     return r;
01301 }
01302 #endif /* CONFIG_BIGINT_BARRETT */
01303 
01304 #ifdef CONFIG_BIGINT_SLIDING_WINDOW
01305 /*
01306  * Work out g1, g3, g5, g7... etc for the sliding-window algorithm 
01307  */
01308 static void precompute_slide_window(BI_CTX *ctx, int window, bigint *g1)
01309 {
01310     int k = 1, i;
01311     bigint *g2;
01312 
01313     for (i = 0; i < window-1; i++)   /* compute 2^(window-1) */
01314     {
01315         k <<= 1;
01316     }
01317 
01318     ctx->g = (bigint **)malloc(k*sizeof(bigint *));
01319     ctx->g[0] = bi_clone(ctx, g1);
01320     bi_permanent(ctx->g[0]);
01321     g2 = bi_residue(ctx, bi_square(ctx, ctx->g[0]));   /* g^2 */
01322 
01323     for (i = 1; i < k; i++)
01324     {
01325         ctx->g[i] = bi_residue(ctx, bi_multiply(ctx, ctx->g[i-1], bi_copy(g2)));
01326         bi_permanent(ctx->g[i]);
01327     }
01328 
01329     bi_free(ctx, g2);
01330     ctx->window = k;
01331 }
01332 #endif
01333 
01334 /**
01335  * @brief Perform a modular exponentiation.
01336  *
01337  * This function requires bi_set_mod() to have been called previously. This is 
01338  * one of the optimisations used for performance.
01339  * @param ctx [in]  The bigint session context.
01340  * @param bi  [in]  The bigint on which to perform the mod power operation.
01341  * @param biexp [in] The bigint exponent.
01342  * @return The result of the mod exponentiation operation
01343  * @see bi_set_mod().
01344  */
01345 bigint *bi_mod_power(BI_CTX *ctx, bigint *bi, bigint *biexp)
01346 {
01347     int i = find_max_exp_index(biexp), j, window_size = 1;
01348     bigint *biR = int_to_bi(ctx, 1);
01349 
01350 #if defined(CONFIG_BIGINT_MONTGOMERY)
01351     uint8_t mod_offset = ctx->mod_offset;
01352     if (!ctx->use_classical)
01353     {
01354         /* preconvert */
01355         bi = bi_mont(ctx, 
01356                 bi_multiply(ctx, bi, ctx->bi_RR_mod_m[mod_offset]));    /* x' */
01357         bi_free(ctx, biR);
01358         biR = ctx->bi_R_mod_m[mod_offset];                              /* A */
01359     }
01360 #endif
01361 
01362     check(bi);
01363     check(biexp);
01364 
01365 #ifdef CONFIG_BIGINT_SLIDING_WINDOW
01366     for (j = i; j > 32; j /= 5) /* work out an optimum size */
01367         window_size++;
01368 
01369     /* work out the slide constants */
01370     precompute_slide_window(ctx, window_size, bi);
01371 #else   /* just one constant */
01372     ctx->g = (bigint **)malloc(sizeof(bigint *));
01373     ctx->g[0] = bi_clone(ctx, bi);
01374     ctx->window = 1;
01375     bi_permanent(ctx->g[0]);
01376 #endif
01377 
01378     /* if sliding-window is off, then only one bit will be done at a time and
01379      * will reduce to standard left-to-right exponentiation */
01380     do
01381     {
01382         if (exp_bit_is_one(biexp, i))
01383         {
01384             int l = i-window_size+1;
01385             int part_exp = 0;
01386 
01387             if (l < 0)  /* LSB of exponent will always be 1 */
01388                 l = 0;
01389             else
01390             {
01391                 while (exp_bit_is_one(biexp, l) == 0)
01392                     l++;    /* go back up */
01393             }
01394 
01395             /* build up the section of the exponent */
01396             for (j = i; j >= l; j--)
01397             {
01398                 biR = bi_residue(ctx, bi_square(ctx, biR));
01399                 if (exp_bit_is_one(biexp, j))
01400                     part_exp++;
01401 
01402                 if (j != l)
01403                     part_exp <<= 1;
01404             }
01405 
01406             part_exp = (part_exp-1)/2;  /* adjust for array */
01407             biR = bi_residue(ctx, bi_multiply(ctx, biR, ctx->g[part_exp]));
01408             i = l-1;
01409         }
01410         else    /* square it */
01411         {
01412             biR = bi_residue(ctx, bi_square(ctx, biR));
01413             i--;
01414         }
01415     } while (i >= 0);
01416      
01417     /* cleanup */
01418     for (i = 0; i < ctx->window; i++)
01419     {
01420         bi_depermanent(ctx->g[i]);
01421         bi_free(ctx, ctx->g[i]);
01422     }
01423 
01424     free(ctx->g);
01425     bi_free(ctx, bi);
01426     bi_free(ctx, biexp);
01427 #if defined CONFIG_BIGINT_MONTGOMERY
01428     return ctx->use_classical ? biR : bi_mont(ctx, biR); /* convert back */
01429 #else /* CONFIG_BIGINT_CLASSICAL or CONFIG_BIGINT_BARRETT */
01430     return biR;
01431 #endif
01432 }
01433 
01434 #ifdef CONFIG_SSL_CERT_VERIFICATION
01435 /**
01436  * @brief Perform a modular exponentiation using a temporary modulus.
01437  *
01438  * We need this function to check the signatures of certificates. The modulus
01439  * of this function is temporary as it's just used for authentication.
01440  * @param ctx [in]  The bigint session context.
01441  * @param bi  [in]  The bigint to perform the exp/mod.
01442  * @param bim [in]  The temporary modulus.
01443  * @param biexp [in] The bigint exponent.
01444  * @return The result of the mod exponentiation operation
01445  * @see bi_set_mod().
01446  */
01447 bigint *bi_mod_power2(BI_CTX *ctx, bigint *bi, bigint *bim, bigint *biexp)
01448 {
01449     bigint *biR, *tmp_biR;
01450 
01451     /* Set up a temporary bigint context and transfer what we need between
01452      * them. We need to do this since we want to keep the original modulus
01453      * which is already in this context. This operation is only called when
01454      * doing peer verification, and so is not expensive :-) */
01455     BI_CTX *tmp_ctx = bi_initialize();
01456     bi_set_mod(tmp_ctx, bi_clone(tmp_ctx, bim), BIGINT_M_OFFSET);
01457     tmp_biR = bi_mod_power(tmp_ctx, 
01458                 bi_clone(tmp_ctx, bi), 
01459                 bi_clone(tmp_ctx, biexp));
01460     biR = bi_clone(ctx, tmp_biR);
01461     bi_free(tmp_ctx, tmp_biR);
01462     bi_free_mod(tmp_ctx, BIGINT_M_OFFSET);
01463     bi_terminate(tmp_ctx);
01464 
01465     bi_free(ctx, bi);
01466     bi_free(ctx, bim);
01467     bi_free(ctx, biexp);
01468     return biR;
01469 }
01470 #endif
01471 
01472 #ifdef CONFIG_BIGINT_CRT
01473 /**
01474  * @brief Use the Chinese Remainder Theorem to quickly perform RSA decrypts.
01475  *
01476  * @param ctx [in]  The bigint session context.
01477  * @param bi  [in]  The bigint to perform the exp/mod.
01478  * @param dP [in] CRT's dP bigint
01479  * @param dQ [in] CRT's dQ bigint
01480  * @param p [in] CRT's p bigint
01481  * @param q [in] CRT's q bigint
01482  * @param qInv [in] CRT's qInv bigint
01483  * @return The result of the CRT operation
01484  */
01485 bigint *bi_crt(BI_CTX *ctx, bigint *bi,
01486         bigint *dP, bigint *dQ,
01487         bigint *p, bigint *q, bigint *qInv)
01488 {
01489     bigint *m1, *m2, *h;
01490 
01491     /* Montgomery has a condition the 0 < x, y < m and these products violate
01492      * that condition. So disable Montgomery when using CRT */
01493 #if defined(CONFIG_BIGINT_MONTGOMERY)
01494     ctx->use_classical = 1;
01495 #endif
01496     ctx->mod_offset = BIGINT_P_OFFSET;
01497     m1 = bi_mod_power(ctx, bi_copy(bi), dP);
01498 
01499     ctx->mod_offset = BIGINT_Q_OFFSET;
01500     m2 = bi_mod_power(ctx, bi, dQ);
01501 
01502     h = bi_subtract(ctx, bi_add(ctx, m1, p), bi_copy(m2), NULL);
01503     h = bi_multiply(ctx, h, qInv);
01504     ctx->mod_offset = BIGINT_P_OFFSET;
01505     h = bi_residue(ctx, h);
01506 #if defined(CONFIG_BIGINT_MONTGOMERY)
01507     ctx->use_classical = 0;         /* reset for any further operation */
01508 #endif
01509     return bi_add(ctx, m2, bi_multiply(ctx, q, h));
01510 }
01511 #endif
01512 /** @} */