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     more_comps(bib, n);
00324     pa = bia->comps;
00325     pb = bib->comps;
00326 
00327     do 
00328     {
00329         comp sl, rl, cy1;
00330         sl = *pa - *pb++;
00331         rl = sl - carry;
00332         cy1 = sl > *pa;
00333         carry = cy1 | (rl > sl);
00334         *pa++ = rl;
00335     } while (--n != 0);
00336 
00337     if (is_negative)    /* indicate a negative result */
00338     {
00339         *is_negative = carry;
00340     }
00341 
00342     bi_free(ctx, trim(bib));    /* put bib back to the way it was */
00343     return trim(bia);
00344 }
00345 
00346 /**
00347  * Perform a multiply between a bigint an an (unsigned) integer
00348  */
00349 static bigint *bi_int_multiply(BI_CTX *ctx, bigint *bia, comp b)
00350 {
00351     int j = 0, n = bia->size;
00352     bigint *biR = alloc(ctx, n + 1);
00353     comp carry = 0;
00354     comp *r = biR->comps;
00355     comp *a = bia->comps;
00356 
00357     check(bia);
00358 
00359     /* clear things to start with */
00360     memset(r, 0, ((n+1)*COMP_BYTE_SIZE));
00361 
00362     do
00363     {
00364         long_comp tmp = *r + (long_comp)a[j]*b + carry;
00365         *r++ = (comp)tmp;              /* downsize */
00366         carry = (comp)(tmp >> COMP_BIT_SIZE);
00367     } while (++j < n);
00368 
00369     *r = carry;
00370     bi_free(ctx, bia);
00371     return trim(biR);
00372 }
00373 
00374 /**
00375  * @brief Does both division and modulo calculations. 
00376  *
00377  * Used extensively when doing classical reduction.
00378  * @param ctx [in]  The bigint session context.
00379  * @param u [in]    A bigint which is the numerator.
00380  * @param v [in]    Either the denominator or the modulus depending on the mode.
00381  * @param is_mod [n] Determines if this is a normal division (0) or a reduction
00382  * (1).
00383  * @return  The result of the division/reduction.
00384  */
00385 bigint *bi_divide(BI_CTX *ctx, bigint *u, bigint *v, int is_mod)
00386 {
00387     int n = v->size, m = u->size-n;
00388     int j = 0, orig_u_size = u->size;
00389     uint8_t mod_offset = ctx->mod_offset;
00390     comp d;
00391     bigint *quotient, *tmp_u;
00392     comp q_dash;
00393 
00394     check(u);
00395     check(v);
00396 
00397     /* if doing reduction and we are < mod, then return mod */
00398     if (is_mod && bi_compare(v, u) > 0)
00399     {
00400         bi_free(ctx, v);
00401         return u;
00402     }
00403 
00404     quotient = alloc(ctx, m+1);
00405     tmp_u = alloc(ctx, n+1);
00406     v = trim(v);        /* make sure we have no leading 0's */
00407     d = (comp)((long_comp)COMP_RADIX/(V1+1));
00408 
00409     /* clear things to start with */
00410     memset(quotient->comps, 0, ((quotient->size)*COMP_BYTE_SIZE));
00411 
00412     /* normalise */
00413     if (d > 1)
00414     {
00415         u = bi_int_multiply(ctx, u, d);
00416 
00417         if (is_mod)
00418         {
00419             v = ctx->bi_normalised_mod[mod_offset];
00420         }
00421         else
00422         {
00423             v = bi_int_multiply(ctx, v, d);
00424         }
00425     }
00426 
00427     if (orig_u_size == u->size)  /* new digit position u0 */
00428     {
00429         more_comps(u, orig_u_size + 1);
00430     }
00431 
00432     do
00433     {
00434         /* get a temporary short version of u */
00435         memcpy(tmp_u->comps, &u->comps[u->size-n-1-j], (n+1)*COMP_BYTE_SIZE);
00436 
00437         /* calculate q' */
00438         if (U(0) == V1)
00439         {
00440             q_dash = COMP_RADIX-1;
00441         }
00442         else
00443         {
00444             q_dash = (comp)(((long_comp)U(0)*COMP_RADIX + U(1))/V1);
00445 
00446             if (v->size > 1 && V2)
00447             {
00448                 /* we are implementing the following:
00449                 if (V2*q_dash > (((U(0)*COMP_RADIX + U(1) - 
00450                         q_dash*V1)*COMP_RADIX) + U(2))) ... */
00451                 comp inner = (comp)((long_comp)COMP_RADIX*U(0) + U(1) - 
00452                                             (long_comp)q_dash*V1);
00453                 if ((long_comp)V2*q_dash > (long_comp)inner*COMP_RADIX + U(2))
00454                 {
00455                     q_dash--;
00456                 }
00457             }
00458         }
00459 
00460         /* multiply and subtract */
00461         if (q_dash)
00462         {
00463             int is_negative;
00464             tmp_u = bi_subtract(ctx, tmp_u, 
00465                     bi_int_multiply(ctx, bi_copy(v), q_dash), &is_negative);
00466             more_comps(tmp_u, n+1);
00467 
00468             Q(j) = q_dash; 
00469 
00470             /* add back */
00471             if (is_negative)
00472             {
00473                 Q(j)--;
00474                 tmp_u = bi_add(ctx, tmp_u, bi_copy(v));
00475 
00476                 /* lop off the carry */
00477                 tmp_u->size--;
00478                 v->size--;
00479             }
00480         }
00481         else
00482         {
00483             Q(j) = 0; 
00484         }
00485 
00486         /* copy back to u */
00487         memcpy(&u->comps[u->size-n-1-j], tmp_u->comps, (n+1)*COMP_BYTE_SIZE);
00488     } while (++j <= m);
00489 
00490     bi_free(ctx, tmp_u);
00491     bi_free(ctx, v);
00492 
00493     if (is_mod)     /* get the remainder */
00494     {
00495         bi_free(ctx, quotient);
00496         return bi_int_divide(ctx, trim(u), d);
00497     }
00498     else            /* get the quotient */
00499     {
00500         bi_free(ctx, u);
00501         return trim(quotient);
00502     }
00503 }
00504 
00505 /*
00506  * Perform an integer divide on a bigint.
00507  */
00508 static bigint *bi_int_divide(BI_CTX *ctx, bigint *biR, comp denom)
00509 {
00510     int i = biR->size - 1;
00511     long_comp r = 0;
00512 
00513     check(biR);
00514 
00515     do
00516     {
00517         r = (r<<COMP_BIT_SIZE) + biR->comps[i];
00518         biR->comps[i] = (comp)(r / denom);
00519         r %= denom;
00520     } while (--i >= 0);
00521 
00522     return trim(biR);
00523 }
00524 
00525 #ifdef CONFIG_BIGINT_MONTGOMERY
00526 /**
00527  * There is a need for the value of integer N' such that B^-1(B-1)-N^-1N'=1, 
00528  * where B^-1(B-1) mod N=1. Actually, only the least significant part of 
00529  * N' is needed, hence the definition N0'=N' mod b. We reproduce below the 
00530  * simple algorithm from an article by Dusse and Kaliski to efficiently 
00531  * find N0' from N0 and b */
00532 static comp modular_inverse(bigint *bim)
00533 {
00534     int i;
00535     comp t = 1;
00536     comp two_2_i_minus_1 = 2;   /* 2^(i-1) */
00537     long_comp two_2_i = 4;      /* 2^i */
00538     comp N = bim->comps[0];
00539 
00540     for (i = 2; i <= COMP_BIT_SIZE; i++)
00541     {
00542         if ((long_comp)N*t%two_2_i >= two_2_i_minus_1)
00543         {
00544             t += two_2_i_minus_1;
00545         }
00546 
00547         two_2_i_minus_1 <<= 1;
00548         two_2_i <<= 1;
00549     }
00550 
00551     return (comp)(COMP_RADIX-t);
00552 }
00553 #endif
00554 
00555 #if defined(CONFIG_BIGINT_KARATSUBA) || defined(CONFIG_BIGINT_BARRETT) || \
00556     defined(CONFIG_BIGINT_MONTGOMERY)
00557 /**
00558  * Take each component and shift down (in terms of components) 
00559  */
00560 static bigint *comp_right_shift(bigint *biR, int num_shifts)
00561 {
00562     int i = biR->size-num_shifts;
00563     comp *x = biR->comps;
00564     comp *y = &biR->comps[num_shifts];
00565 
00566     check(biR);
00567 
00568     if (i <= 0)     /* have we completely right shifted? */
00569     {
00570         biR->comps[0] = 0;  /* return 0 */
00571         biR->size = 1;
00572         return biR;
00573     }
00574 
00575     do
00576     {
00577         *x++ = *y++;
00578     } while (--i > 0);
00579 
00580     biR->size -= num_shifts;
00581     return biR;
00582 }
00583 
00584 /**
00585  * Take each component and shift it up (in terms of components) 
00586  */
00587 static bigint *comp_left_shift(bigint *biR, int num_shifts)
00588 {
00589     int i = biR->size-1;
00590     comp *x, *y;
00591 
00592     check(biR);
00593 
00594     if (num_shifts <= 0)
00595     {
00596         return biR;
00597     }
00598 
00599     more_comps(biR, biR->size + num_shifts);
00600 
00601     x = &biR->comps[i+num_shifts];
00602     y = &biR->comps[i];
00603 
00604     do
00605     {
00606         *x-- = *y--;
00607     } while (i--);
00608 
00609     memset(biR->comps, 0, num_shifts*COMP_BYTE_SIZE); /* zero LS comps */
00610     return biR;
00611 }
00612 #endif
00613 
00614 /**
00615  * @brief Allow a binary sequence to be imported as a bigint.
00616  * @param ctx [in]  The bigint session context.
00617  * @param data [in] The data to be converted.
00618  * @param size [in] The number of bytes of data.
00619  * @return A bigint representing this data.
00620  */
00621 bigint *bi_import(BI_CTX *ctx, const uint8_t *data, int size)
00622 {
00623     bigint *biR = alloc(ctx, (size+COMP_BYTE_SIZE-1)/COMP_BYTE_SIZE);
00624     int i, j = 0, offset = 0;
00625 
00626     memset(biR->comps, 0, biR->size*COMP_BYTE_SIZE);
00627 
00628     for (i = size-1; i >= 0; i--)
00629     {
00630         biR->comps[offset] += data[i] << (j*8);
00631 
00632         if (++j == COMP_BYTE_SIZE)
00633         {
00634             j = 0;
00635             offset ++;
00636         }
00637     }
00638 
00639     return trim(biR);
00640 }
00641 
00642 #ifdef CONFIG_SSL_FULL_MODE
00643 /**
00644  * @brief The testharness uses this code to import text hex-streams and 
00645  * convert them into bigints.
00646  * @param ctx [in]  The bigint session context.
00647  * @param data [in] A string consisting of hex characters. The characters must
00648  * be in upper case.
00649  * @return A bigint representing this data.
00650  */
00651 bigint *bi_str_import(BI_CTX *ctx, const char *data)
00652 {
00653     int size = strlen(data);
00654     bigint *biR = alloc(ctx, (size+COMP_NUM_NIBBLES-1)/COMP_NUM_NIBBLES);
00655     int i, j = 0, offset = 0;
00656     memset(biR->comps, 0, biR->size*COMP_BYTE_SIZE);
00657 
00658     for (i = size-1; i >= 0; i--)
00659     {
00660         int num = (data[i] <= '9') ? (data[i] - '0') : (data[i] - 'A' + 10);
00661         biR->comps[offset] += num << (j*4);
00662 
00663         if (++j == COMP_NUM_NIBBLES)
00664         {
00665             j = 0;
00666             offset ++;
00667         }
00668     }
00669 
00670     return biR;
00671 }
00672 
00673 void bi_print(const char *label, bigint *x)
00674 {
00675     int i, j;
00676 
00677     if (x == NULL)
00678     {
00679         printf("%s: (null)\n", label);
00680         return;
00681     }
00682 
00683     printf("%s: (size %d)\n", label, x->size);
00684     for (i = x->size-1; i >= 0; i--)
00685     {
00686         for (j = COMP_NUM_NIBBLES-1; j >= 0; j--)
00687         {
00688             comp mask = 0x0f << (j*4);
00689             comp num = (x->comps[i] & mask) >> (j*4);
00690             putc((num <= 9) ? (num + '0') : (num + 'A' - 10), stdout);
00691         }
00692     }  
00693 
00694     printf("\r\n");
00695 }
00696 #endif
00697 
00698 /**
00699  * @brief Take a bigint and convert it into a byte sequence. 
00700  *
00701  * This is useful after a decrypt operation.
00702  * @param ctx [in]  The bigint session context.
00703  * @param x [in]  The bigint to be converted.
00704  * @param data [out] The converted data as a byte stream.
00705  * @param size [in] The maximum size of the byte stream. Unused bytes will be
00706  * zeroed.
00707  */
00708 void bi_export(BI_CTX *ctx, bigint *x, uint8_t *data, int size)
00709 {
00710     int i, j, k = size-1;
00711 
00712     check(x);
00713     memset(data, 0, size);  /* ensure all leading 0's are cleared */
00714     for (i = 0; i < x->size; i++)
00715     {
00716         for (j = 0; j < COMP_BYTE_SIZE; j++)
00717         {
00718             comp mask = 0xff << (j*8);
00719             int num = (x->comps[i] & mask) >> (j*8);
00720             data[k--] = num;
00721 
00722             if (k < 0)
00723             {
00724                 goto buf_done;
00725             }
00726         }
00727     }
00728 buf_done:
00729     bi_free(ctx, x);
00730 }
00731 
00732 /**
00733  * @brief Pre-calculate some of the expensive steps in reduction. 
00734  *
00735  * This function should only be called once (normally when a session starts).
00736  * When the session is over, bi_free_mod() should be called. bi_mod_power()
00737  * relies on this function being called.
00738  * @param ctx [in]  The bigint session context.
00739  * @param bim [in]  The bigint modulus that will be used.
00740  * @param mod_offset [in] There are three moduluii that can be stored - the
00741  * standard modulus, and its two primes p and q. This offset refers to which
00742  * modulus we are referring to.
00743  * @see bi_free_mod(), bi_mod_power().
00744  */
00745 void bi_set_mod(BI_CTX *ctx, bigint *bim, int mod_offset)
00746 {
00747     int k = bim->size;
00748     comp d = (comp)((long_comp)COMP_RADIX/(bim->comps[k-1]+1));
00749 #ifdef CONFIG_BIGINT_MONTGOMERY
00750     bigint *R, *R2;
00751 #endif
00752 
00753     ctx->bi_mod[mod_offset] = bim;
00754     bi_permanent(ctx->bi_mod[mod_offset]);
00755     ctx->bi_normalised_mod[mod_offset] = bi_int_multiply(ctx, bim, d);
00756     bi_permanent(ctx->bi_normalised_mod[mod_offset]);
00757 
00758 #if defined(CONFIG_BIGINT_MONTGOMERY)
00759     /* set montgomery variables */
00760     R = comp_left_shift(bi_clone(ctx, ctx->bi_radix), k-1);     /* R */
00761     R2 = comp_left_shift(bi_clone(ctx, ctx->bi_radix), k*2-1);  /* R^2 */
00762     ctx->bi_RR_mod_m[mod_offset] = bi_mod(ctx, R2);             /* R^2 mod m */
00763     ctx->bi_R_mod_m[mod_offset] = bi_mod(ctx, R);               /* R mod m */
00764 
00765     bi_permanent(ctx->bi_RR_mod_m[mod_offset]);
00766     bi_permanent(ctx->bi_R_mod_m[mod_offset]);
00767 
00768     ctx->N0_dash[mod_offset] = modular_inverse(ctx->bi_mod[mod_offset]);
00769 
00770 #elif defined (CONFIG_BIGINT_BARRETT)
00771     ctx->bi_mu[mod_offset] = 
00772         bi_divide(ctx, comp_left_shift(
00773             bi_clone(ctx, ctx->bi_radix), k*2-1), ctx->bi_mod[mod_offset], 0);
00774     bi_permanent(ctx->bi_mu[mod_offset]);
00775 #endif
00776 }
00777 
00778 /**
00779  * @brief Used when cleaning various bigints at the end of a session.
00780  * @param ctx [in]  The bigint session context.
00781  * @param mod_offset [in] The offset to use.
00782  * @see bi_set_mod().
00783  */
00784 void bi_free_mod(BI_CTX *ctx, int mod_offset)
00785 {
00786     bi_depermanent(ctx->bi_mod[mod_offset]);
00787     bi_free(ctx, ctx->bi_mod[mod_offset]);
00788 #if defined (CONFIG_BIGINT_MONTGOMERY)
00789     bi_depermanent(ctx->bi_RR_mod_m[mod_offset]);
00790     bi_depermanent(ctx->bi_R_mod_m[mod_offset]);
00791     bi_free(ctx, ctx->bi_RR_mod_m[mod_offset]);
00792     bi_free(ctx, ctx->bi_R_mod_m[mod_offset]);
00793 #elif defined(CONFIG_BIGINT_BARRETT)
00794     bi_depermanent(ctx->bi_mu[mod_offset]); 
00795     bi_free(ctx, ctx->bi_mu[mod_offset]);
00796 #endif
00797     bi_depermanent(ctx->bi_normalised_mod[mod_offset]); 
00798     bi_free(ctx, ctx->bi_normalised_mod[mod_offset]);
00799 }
00800 
00801 /** 
00802  * Perform a standard multiplication between two bigints.
00803  *
00804  * Barrett reduction has no need for some parts of the product, so ignore bits
00805  * of the multiply. This routine gives Barrett its big performance
00806  * improvements over Classical/Montgomery reduction methods. 
00807  */
00808 static bigint *regular_multiply(BI_CTX *ctx, bigint *bia, bigint *bib, 
00809         int inner_partial, int outer_partial)
00810 {
00811     int i = 0, j;
00812     int n = bia->size;
00813     int t = bib->size;
00814     bigint *biR = alloc(ctx, n + t);
00815     comp *sr = biR->comps;
00816     comp *sa = bia->comps;
00817     comp *sb = bib->comps;
00818 
00819     check(bia);
00820     check(bib);
00821 
00822     /* clear things to start with */
00823     memset(biR->comps, 0, ((n+t)*COMP_BYTE_SIZE));
00824 
00825     do 
00826     {
00827         long_comp tmp;
00828         comp carry = 0;
00829         int r_index = i;
00830         j = 0;
00831 
00832         if (outer_partial && outer_partial-i > 0 && outer_partial < n)
00833         {
00834             r_index = outer_partial-1;
00835             j = outer_partial-i-1;
00836         }
00837 
00838         do
00839         {
00840             if (inner_partial && r_index >= inner_partial) 
00841             {
00842                 break;
00843             }
00844 
00845             tmp = sr[r_index] + ((long_comp)sa[j])*sb[i] + carry;
00846             sr[r_index++] = (comp)tmp;              /* downsize */
00847             carry = tmp >> COMP_BIT_SIZE;
00848         } while (++j < n);
00849 
00850         sr[r_index] = carry;
00851     } while (++i < t);
00852 
00853     bi_free(ctx, bia);
00854     bi_free(ctx, bib);
00855     return trim(biR);
00856 }
00857 
00858 #ifdef CONFIG_BIGINT_KARATSUBA
00859 /*
00860  * Karatsuba improves on regular multiplication due to only 3 multiplications 
00861  * being done instead of 4. The additional additions/subtractions are O(N) 
00862  * rather than O(N^2) and so for big numbers it saves on a few operations 
00863  */
00864 static bigint *karatsuba(BI_CTX *ctx, bigint *bia, bigint *bib, int is_square)
00865 {
00866     bigint *x0, *x1;
00867     bigint *p0, *p1, *p2;
00868     int m;
00869 
00870     if (is_square)
00871     {
00872         m = (bia->size + 1)/2;
00873     }
00874     else
00875     {
00876         m = (max(bia->size, bib->size) + 1)/2;
00877     }
00878 
00879     x0 = bi_clone(ctx, bia);
00880     x0->size = m;
00881     x1 = bi_clone(ctx, bia);
00882     comp_right_shift(x1, m);
00883     bi_free(ctx, bia);
00884 
00885     /* work out the 3 partial products */
00886     if (is_square)
00887     {
00888         p0 = bi_square(ctx, bi_copy(x0));
00889         p2 = bi_square(ctx, bi_copy(x1));
00890         p1 = bi_square(ctx, bi_add(ctx, x0, x1));
00891     }
00892     else /* normal multiply */
00893     {
00894         bigint *y0, *y1;
00895         y0 = bi_clone(ctx, bib);
00896         y0->size = m;
00897         y1 = bi_clone(ctx, bib);
00898         comp_right_shift(y1, m);
00899         bi_free(ctx, bib);
00900 
00901         p0 = bi_multiply(ctx, bi_copy(x0), bi_copy(y0));
00902         p2 = bi_multiply(ctx, bi_copy(x1), bi_copy(y1));
00903         p1 = bi_multiply(ctx, bi_add(ctx, x0, x1), bi_add(ctx, y0, y1));
00904     }
00905 
00906     p1 = bi_subtract(ctx, 
00907             bi_subtract(ctx, p1, bi_copy(p2), NULL), bi_copy(p0), NULL);
00908 
00909     comp_left_shift(p1, m);
00910     comp_left_shift(p2, 2*m);
00911     return bi_add(ctx, p1, bi_add(ctx, p0, p2));
00912 }
00913 #endif
00914 
00915 /**
00916  * @brief Perform a multiplication operation between two bigints.
00917  * @param ctx [in]  The bigint session context.
00918  * @param bia [in]  A bigint.
00919  * @param bib [in]  Another bigint.
00920  * @return The result of the multiplication.
00921  */
00922 bigint *bi_multiply(BI_CTX *ctx, bigint *bia, bigint *bib)
00923 {
00924     check(bia);
00925     check(bib);
00926 
00927 #ifdef CONFIG_BIGINT_KARATSUBA
00928     if (min(bia->size, bib->size) < MUL_KARATSUBA_THRESH)
00929     {
00930         return regular_multiply(ctx, bia, bib, 0, 0);
00931     }
00932 
00933     return karatsuba(ctx, bia, bib, 0);
00934 #else
00935     return regular_multiply(ctx, bia, bib, 0, 0);
00936 #endif
00937 }
00938 
00939 #ifdef CONFIG_BIGINT_SQUARE
00940 /*
00941  * Perform the actual square operion. It takes into account overflow.
00942  */
00943 static bigint *regular_square(BI_CTX *ctx, bigint *bi)
00944 {
00945     int t = bi->size;
00946     int i = 0, j;
00947     bigint *biR = alloc(ctx, t*2+1);
00948     comp *w = biR->comps;
00949     comp *x = bi->comps;
00950     long_comp carry;
00951     memset(w, 0, biR->size*COMP_BYTE_SIZE);
00952 
00953     do
00954     {
00955         long_comp tmp = w[2*i] + (long_comp)x[i]*x[i];
00956         w[2*i] = (comp)tmp;
00957         carry = tmp >> COMP_BIT_SIZE;
00958 
00959         for (j = i+1; j < t; j++)
00960         {
00961             uint8_t c = 0;
00962             long_comp xx = (long_comp)x[i]*x[j];
00963             if ((COMP_MAX-xx) < xx)
00964                 c = 1;
00965 
00966             tmp = (xx<<1);
00967 
00968             if ((COMP_MAX-tmp) < w[i+j])
00969                 c = 1;
00970 
00971             tmp += w[i+j];
00972 
00973             if ((COMP_MAX-tmp) < carry)
00974                 c = 1;
00975 
00976             tmp += carry;
00977             w[i+j] = (comp)tmp;
00978             carry = tmp >> COMP_BIT_SIZE;
00979 
00980             if (c)
00981                 carry += COMP_RADIX;
00982         }
00983 
00984         tmp = w[i+t] + carry;
00985         w[i+t] = (comp)tmp;
00986         w[i+t+1] = tmp >> COMP_BIT_SIZE;
00987     } while (++i < t);
00988 
00989     bi_free(ctx, bi);
00990     return trim(biR);
00991 }
00992 
00993 /**
00994  * @brief Perform a square operation on a bigint.
00995  * @param ctx [in]  The bigint session context.
00996  * @param bia [in]  A bigint.
00997  * @return The result of the multiplication.
00998  */
00999 bigint *bi_square(BI_CTX *ctx, bigint *bia)
01000 {
01001     check(bia);
01002 
01003 #ifdef CONFIG_BIGINT_KARATSUBA
01004     if (bia->size < SQU_KARATSUBA_THRESH) 
01005     {
01006         return regular_square(ctx, bia);
01007     }
01008 
01009     return karatsuba(ctx, bia, NULL, 1);
01010 #else
01011     return regular_square(ctx, bia);
01012 #endif
01013 }
01014 #endif
01015 
01016 /**
01017  * @brief Compare two bigints.
01018  * @param bia [in]  A bigint.
01019  * @param bib [in]  Another bigint.
01020  * @return -1 if smaller, 1 if larger and 0 if equal.
01021  */
01022 int bi_compare(bigint *bia, bigint *bib)
01023 {
01024     int r, i;
01025 
01026     check(bia);
01027     check(bib);
01028 
01029     if (bia->size > bib->size)
01030         r = 1;
01031     else if (bia->size < bib->size)
01032         r = -1;
01033     else
01034     {
01035         comp *a = bia->comps; 
01036         comp *b = bib->comps; 
01037 
01038         /* Same number of components.  Compare starting from the high end
01039          * and working down. */
01040         r = 0;
01041         i = bia->size - 1;
01042 
01043         do 
01044         {
01045             if (a[i] > b[i])
01046             { 
01047                 r = 1;
01048                 break; 
01049             }
01050             else if (a[i] < b[i])
01051             { 
01052                 r = -1;
01053                 break; 
01054             }
01055         } while (--i >= 0);
01056     }
01057 
01058     return r;
01059 }
01060 
01061 /*
01062  * Allocate and zero more components.  Does not consume bi. 
01063  */
01064 static void more_comps(bigint *bi, int n)
01065 {
01066     if (n > bi->max_comps)
01067     {
01068         bi->max_comps = max(bi->max_comps * 2, n);
01069         bi->comps = (comp*)realloc(bi->comps, bi->max_comps * COMP_BYTE_SIZE);
01070     }
01071 
01072     if (n > bi->size)
01073     {
01074         memset(&bi->comps[bi->size], 0, (n-bi->size)*COMP_BYTE_SIZE);
01075     }
01076 
01077     bi->size = n;
01078 }
01079 
01080 /*
01081  * Make a new empty bigint. It may just use an old one if one is available.
01082  * Otherwise get one off the heap.
01083  */
01084 static bigint *alloc(BI_CTX *ctx, int size)
01085 {
01086     bigint *biR;
01087 
01088     /* Can we recycle an old bigint? */
01089     if (ctx->free_list != NULL)
01090     {
01091         biR = ctx->free_list;
01092         ctx->free_list = biR->next;
01093         ctx->free_count--;
01094 
01095         if (biR->refs != 0)
01096         {
01097 #ifdef CONFIG_SSL_FULL_MODE
01098             printf("alloc: refs was not 0\n");
01099 #endif
01100             abort();    /* create a stack trace from a core dump */
01101         }
01102 
01103         more_comps(biR, size);
01104     }
01105     else
01106     {
01107         /* No free bigints available - create a new one. */
01108         biR = (bigint *)malloc(sizeof(bigint));
01109         biR->comps = (comp*)malloc(size * COMP_BYTE_SIZE);
01110         biR->max_comps = size;  /* give some space to spare */
01111     }
01112 
01113     biR->size = size;
01114     biR->refs = 1;
01115     biR->next = NULL;
01116     ctx->active_count++;
01117     return biR;
01118 }
01119 
01120 /*
01121  * Work out the highest '1' bit in an exponent. Used when doing sliding-window
01122  * exponentiation.
01123  */
01124 static int find_max_exp_index(bigint *biexp)
01125 {
01126     int i = COMP_BIT_SIZE-1;
01127     comp shift = COMP_RADIX/2;
01128     comp test = biexp->comps[biexp->size-1];    /* assume no leading zeroes */
01129 
01130     check(biexp);
01131 
01132     do
01133     {
01134         if (test & shift)
01135         {
01136             return i+(biexp->size-1)*COMP_BIT_SIZE;
01137         }
01138 
01139         shift >>= 1;
01140     } while (i-- != 0);
01141 
01142     return -1;      /* error - must have been a leading 0 */
01143 }
01144 
01145 /*
01146  * Is a particular bit is an exponent 1 or 0? Used when doing sliding-window
01147  * exponentiation.
01148  */
01149 static int exp_bit_is_one(bigint *biexp, int offset)
01150 {
01151     comp test = biexp->comps[offset / COMP_BIT_SIZE];
01152     int num_shifts = offset % COMP_BIT_SIZE;
01153     comp shift = 1;
01154     int i;
01155 
01156     check(biexp);
01157 
01158     for (i = 0; i < num_shifts; i++)
01159     {
01160         shift <<= 1;
01161     }
01162 
01163     return (test & shift) != 0;
01164 }
01165 
01166 #ifdef CONFIG_BIGINT_CHECK_ON
01167 /*
01168  * Perform a sanity check on bi.
01169  */
01170 static void check(const bigint *bi)
01171 {
01172     if (bi->refs <= 0)
01173     {
01174         printf("check: zero or negative refs in bigint\n");
01175         abort();
01176     }
01177 
01178     if (bi->next != NULL)
01179     {
01180         printf("check: attempt to use a bigint from "
01181                 "the free list\n");
01182         abort();
01183     }
01184 }
01185 #endif
01186 
01187 /*
01188  * Delete any leading 0's (and allow for 0).
01189  */
01190 static bigint *trim(bigint *bi)
01191 {
01192     check(bi);
01193 
01194     while (bi->comps[bi->size-1] == 0 && bi->size > 1)
01195     {
01196         bi->size--;
01197     }
01198 
01199     return bi;
01200 }
01201 
01202 #if defined(CONFIG_BIGINT_MONTGOMERY)
01203 /**
01204  * @brief Perform a single montgomery reduction.
01205  * @param ctx [in]  The bigint session context.
01206  * @param bixy [in]  A bigint.
01207  * @return The result of the montgomery reduction.
01208  */
01209 bigint *bi_mont(BI_CTX *ctx, bigint *bixy)
01210 {
01211     int i = 0, n;
01212     uint8_t mod_offset = ctx->mod_offset;
01213     bigint *bim = ctx->bi_mod[mod_offset];
01214     comp mod_inv = ctx->N0_dash[mod_offset];
01215 
01216     check(bixy);
01217 
01218     if (ctx->use_classical)     /* just use classical instead */
01219     {
01220         return bi_mod(ctx, bixy);
01221     }
01222 
01223     n = bim->size;
01224 
01225     do
01226     {
01227         bixy = bi_add(ctx, bixy, comp_left_shift(
01228                     bi_int_multiply(ctx, bim, bixy->comps[i]*mod_inv), i));
01229     } while (++i < n);
01230 
01231     comp_right_shift(bixy, n);
01232 
01233     if (bi_compare(bixy, bim) >= 0)
01234     {
01235         bixy = bi_subtract(ctx, bixy, bim, NULL);
01236     }
01237 
01238     return bixy;
01239 }
01240 
01241 #elif defined(CONFIG_BIGINT_BARRETT)
01242 /*
01243  * Stomp on the most significant components to give the illusion of a "mod base
01244  * radix" operation 
01245  */
01246 static bigint *comp_mod(bigint *bi, int mod)
01247 {
01248     check(bi);
01249 
01250     if (bi->size > mod)
01251     {
01252         bi->size = mod;
01253     }
01254 
01255     return bi;
01256 }
01257 
01258 /**
01259  * @brief Perform a single Barrett reduction.
01260  * @param ctx [in]  The bigint session context.
01261  * @param bi [in]  A bigint.
01262  * @return The result of the Barrett reduction.
01263  */
01264 bigint *bi_barrett(BI_CTX *ctx, bigint *bi)
01265 {
01266 
01267     bigint *q1, *q2, *q3, *r1, *r2, *r;
01268     uint8_t mod_offset = ctx->mod_offset;
01269     bigint *bim = ctx->bi_mod[mod_offset];
01270     int k = bim->size;
01271 
01272     check(bi);
01273     check(bim);
01274 
01275     /* use Classical method instead  - Barrett cannot help here */
01276     if (bi->size > k*2)
01277     {
01278 
01279         return bi_mod(ctx, bi);
01280     }
01281     bigint* a = bi_clone(ctx, bi);
01282     q1 = comp_right_shift(a, k-1);
01283 
01284     /* do outer partial multiply */
01285     q2 = regular_multiply(ctx, q1, ctx->bi_mu[mod_offset], 0, k-1); 
01286     q3 = comp_right_shift(q2, k+1);
01287     r1 = comp_mod(bi, k+1);
01288 
01289     /* do inner partial multiply */
01290     r2 = comp_mod(regular_multiply(ctx, q3, bim, k+1, 0), k+1);
01291     r = bi_subtract(ctx, r1, r2, NULL);
01292 
01293     /* if (r >= m) r = r - m; */
01294     if (bi_compare(r, bim) >= 0)
01295     {
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 
01351 #if defined(CONFIG_BIGINT_MONTGOMERY)
01352     uint8_t mod_offset = ctx->mod_offset;
01353     if (!ctx->use_classical)
01354     {
01355         /* preconvert */
01356         bi = bi_mont(ctx, 
01357                 bi_multiply(ctx, bi, ctx->bi_RR_mod_m[mod_offset]));    /* x' */
01358         bi_free(ctx, biR);
01359         biR = ctx->bi_R_mod_m[mod_offset];                              /* A */
01360     }
01361 #endif
01362 
01363     check(bi);
01364     check(biexp);
01365 
01366 #ifdef CONFIG_BIGINT_SLIDING_WINDOW
01367     for (j = i; j > 32; j /= 5) /* work out an optimum size */
01368         window_size++;
01369 
01370     /* work out the slide constants */
01371     precompute_slide_window(ctx, window_size, bi);
01372 #else   /* just one constant */
01373     ctx->g = (bigint **)malloc(sizeof(bigint *));
01374     ctx->g[0] = bi_clone(ctx, bi);
01375     ctx->window = 1;
01376     bi_permanent(ctx->g[0]);
01377 #endif
01378 
01379     /* if sliding-window is off, then only one bit will be done at a time and
01380      * will reduce to standard left-to-right exponentiation */
01381     do
01382     {
01383         if (exp_bit_is_one(biexp, i))
01384         {
01385             int l = i-window_size+1;
01386             int part_exp = 0;
01387 
01388             if (l < 0)  /* LSB of exponent will always be 1 */
01389                 l = 0;
01390             else
01391             {
01392                 while (exp_bit_is_one(biexp, l) == 0)
01393                     l++;    /* go back up */
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             part_exp = (part_exp-1)/2;  /* adjust for array */
01406             bigint* a = bi_multiply(ctx, biR, ctx->g[part_exp]);
01407             biR = bi_residue(ctx, a);
01408             i = l-1;
01409         }
01410         else    /* square it */
01411         {
01412             biR = bi_residue(ctx, bi_square(ctx, biR));
01413             i--;
01414         }
01415         
01416     } while (i >= 0);
01417 
01418     /* cleanup */
01419     for (i = 0; i < ctx->window; i++)
01420     {
01421         bi_depermanent(ctx->g[i]);
01422         bi_free(ctx, ctx->g[i]);
01423     }
01424 
01425     free(ctx->g);
01426     bi_free(ctx, bi);
01427     bi_free(ctx, biexp);
01428 #if defined CONFIG_BIGINT_MONTGOMERY
01429     return ctx->use_classical ? biR : bi_mont(ctx, biR); /* convert back */
01430 #else /* CONFIG_BIGINT_CLASSICAL or CONFIG_BIGINT_BARRETT */
01431     return biR;
01432 #endif
01433 }
01434 
01435 #ifdef CONFIG_SSL_CERT_VERIFICATION
01436 /**
01437  * @brief Perform a modular exponentiation using a temporary modulus.
01438  *
01439  * We need this function to check the signatures of certificates. The modulus
01440  * of this function is temporary as it's just used for authentication.
01441  * @param ctx [in]  The bigint session context.
01442  * @param bi  [in]  The bigint to perform the exp/mod.
01443  * @param bim [in]  The temporary modulus.
01444  * @param biexp [in] The bigint exponent.
01445  * @return The result of the mod exponentiation operation
01446  * @see bi_set_mod().
01447  */
01448 bigint *bi_mod_power2(BI_CTX *ctx, bigint *bi, bigint *bim, bigint *biexp)
01449 {
01450     bigint *biR, *tmp_biR;
01451 
01452     /* Set up a temporary bigint context and transfer what we need between
01453      * them. We need to do this since we want to keep the original modulus
01454      * which is already in this context. This operation is only called when
01455      * doing peer verification, and so is not expensive :-) */
01456     BI_CTX *tmp_ctx = bi_initialize();
01457     bi_set_mod(tmp_ctx, bi_clone(tmp_ctx, bim), BIGINT_M_OFFSET);
01458     tmp_biR = bi_mod_power(tmp_ctx, 
01459                 bi_clone(tmp_ctx, bi), 
01460                 bi_clone(tmp_ctx, biexp));
01461     biR = bi_clone(ctx, tmp_biR);
01462     bi_free(tmp_ctx, tmp_biR);
01463     bi_free_mod(tmp_ctx, BIGINT_M_OFFSET);
01464     bi_terminate(tmp_ctx);
01465 
01466     bi_free(ctx, bi);
01467     bi_free(ctx, bim);
01468     bi_free(ctx, biexp);
01469     return biR;
01470 }
01471 #endif
01472 
01473 #ifdef CONFIG_BIGINT_CRT
01474 /**
01475  * @brief Use the Chinese Remainder Theorem to quickly perform RSA decrypts.
01476  *
01477  * @param ctx [in]  The bigint session context.
01478  * @param bi  [in]  The bigint to perform the exp/mod.
01479  * @param dP [in] CRT's dP bigint
01480  * @param dQ [in] CRT's dQ bigint
01481  * @param p [in] CRT's p bigint
01482  * @param q [in] CRT's q bigint
01483  * @param qInv [in] CRT's qInv bigint
01484  * @return The result of the CRT operation
01485  */
01486 bigint *bi_crt(BI_CTX *ctx, bigint *bi,
01487         bigint *dP, bigint *dQ,
01488         bigint *p, bigint *q, bigint *qInv)
01489 {
01490     bigint *m1, *m2, *h;
01491 
01492     /* Montgomery has a condition the 0 < x, y < m and these products violate
01493      * that condition. So disable Montgomery when using CRT */
01494 #if defined(CONFIG_BIGINT_MONTGOMERY)
01495     ctx->use_classical = 1;
01496 #endif
01497     ctx->mod_offset = BIGINT_P_OFFSET;
01498     m1 = bi_mod_power(ctx, bi_copy(bi), dP);
01499 
01500     ctx->mod_offset = BIGINT_Q_OFFSET;
01501     m2 = bi_mod_power(ctx, bi, dQ);
01502 
01503     h = bi_subtract(ctx, bi_add(ctx, m1, p), bi_copy(m2), NULL);
01504     h = bi_multiply(ctx, h, qInv);
01505     ctx->mod_offset = BIGINT_P_OFFSET;
01506     h = bi_residue(ctx, h);
01507 #if defined(CONFIG_BIGINT_MONTGOMERY)
01508     ctx->use_classical = 0;         /* reset for any further operation */
01509 #endif
01510     return bi_add(ctx, m2, bi_multiply(ctx, q, h));
01511 }
01512 #endif
01513 /** @} */
01514 
01515