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 
00715     for (i = 0; i < x->size; i++)
00716     {
00717         for (j = 0; j < COMP_BYTE_SIZE; j++)
00718         {
00719             comp mask = 0xff << (j*8);
00720             int num = (x->comps[i] & mask) >> (j*8);
00721             data[k--] = num;
00722 
00723             if (k < 0)
00724             {
00725                 goto buf_done;
00726             }
00727         }
00728     }
00729 buf_done:
00730 
00731     bi_free(ctx, x);
00732 }
00733 
00734 /**
00735  * @brief Pre-calculate some of the expensive steps in reduction. 
00736  *
00737  * This function should only be called once (normally when a session starts).
00738  * When the session is over, bi_free_mod() should be called. bi_mod_power()
00739  * relies on this function being called.
00740  * @param ctx [in]  The bigint session context.
00741  * @param bim [in]  The bigint modulus that will be used.
00742  * @param mod_offset [in] There are three moduluii that can be stored - the
00743  * standard modulus, and its two primes p and q. This offset refers to which
00744  * modulus we are referring to.
00745  * @see bi_free_mod(), bi_mod_power().
00746  */
00747 void bi_set_mod(BI_CTX *ctx, bigint *bim, int mod_offset)
00748 {
00749     int k = bim->size;
00750     comp d = (comp)((long_comp)COMP_RADIX/(bim->comps[k-1]+1));
00751 #ifdef CONFIG_BIGINT_MONTGOMERY
00752     bigint *R, *R2;
00753 #endif
00754 
00755     ctx->bi_mod[mod_offset] = bim;
00756     bi_permanent(ctx->bi_mod[mod_offset]);
00757     ctx->bi_normalised_mod[mod_offset] = bi_int_multiply(ctx, bim, d);
00758     bi_permanent(ctx->bi_normalised_mod[mod_offset]);
00759 
00760 #if defined(CONFIG_BIGINT_MONTGOMERY)
00761     /* set montgomery variables */
00762     R = comp_left_shift(bi_clone(ctx, ctx->bi_radix), k-1);     /* R */
00763     R2 = comp_left_shift(bi_clone(ctx, ctx->bi_radix), k*2-1);  /* R^2 */
00764     ctx->bi_RR_mod_m[mod_offset] = bi_mod(ctx, R2);             /* R^2 mod m */
00765     ctx->bi_R_mod_m[mod_offset] = bi_mod(ctx, R);               /* R mod m */
00766 
00767     bi_permanent(ctx->bi_RR_mod_m[mod_offset]);
00768     bi_permanent(ctx->bi_R_mod_m[mod_offset]);
00769 
00770     ctx->N0_dash[mod_offset] = modular_inverse(ctx->bi_mod[mod_offset]);
00771 
00772 #elif defined (CONFIG_BIGINT_BARRETT)
00773     ctx->bi_mu[mod_offset] = 
00774         bi_divide(ctx, comp_left_shift(
00775             bi_clone(ctx, ctx->bi_radix), k*2-1), ctx->bi_mod[mod_offset], 0);
00776     bi_permanent(ctx->bi_mu[mod_offset]);
00777 #endif
00778 }
00779 
00780 /**
00781  * @brief Used when cleaning various bigints at the end of a session.
00782  * @param ctx [in]  The bigint session context.
00783  * @param mod_offset [in] The offset to use.
00784  * @see bi_set_mod().
00785  */
00786 void bi_free_mod(BI_CTX *ctx, int mod_offset)
00787 {
00788     bi_depermanent(ctx->bi_mod[mod_offset]);
00789     bi_free(ctx, ctx->bi_mod[mod_offset]);
00790 #if defined (CONFIG_BIGINT_MONTGOMERY)
00791     bi_depermanent(ctx->bi_RR_mod_m[mod_offset]);
00792     bi_depermanent(ctx->bi_R_mod_m[mod_offset]);
00793     bi_free(ctx, ctx->bi_RR_mod_m[mod_offset]);
00794     bi_free(ctx, ctx->bi_R_mod_m[mod_offset]);
00795 #elif defined(CONFIG_BIGINT_BARRETT)
00796     bi_depermanent(ctx->bi_mu[mod_offset]); 
00797     bi_free(ctx, ctx->bi_mu[mod_offset]);
00798 #endif
00799     bi_depermanent(ctx->bi_normalised_mod[mod_offset]); 
00800     bi_free(ctx, ctx->bi_normalised_mod[mod_offset]);
00801 }
00802 
00803 /** 
00804  * Perform a standard multiplication between two bigints.
00805  *
00806  * Barrett reduction has no need for some parts of the product, so ignore bits
00807  * of the multiply. This routine gives Barrett its big performance
00808  * improvements over Classical/Montgomery reduction methods. 
00809  */
00810 static bigint *regular_multiply(BI_CTX *ctx, bigint *bia, bigint *bib, 
00811         int inner_partial, int outer_partial)
00812 {
00813     int i = 0, j;
00814     int n = bia->size;
00815     int t = bib->size;
00816     bigint *biR = alloc(ctx, n + t);
00817     comp *sr = biR->comps;
00818     comp *sa = bia->comps;
00819     comp *sb = bib->comps;
00820 
00821     check(bia);
00822     check(bib);
00823 
00824     /* clear things to start with */
00825     memset(biR->comps, 0, ((n+t)*COMP_BYTE_SIZE));
00826 
00827     do 
00828     {
00829         long_comp tmp;
00830         comp carry = 0;
00831         int r_index = i;
00832         j = 0;
00833 
00834         if (outer_partial && outer_partial-i > 0 && outer_partial < n)
00835         {
00836             r_index = outer_partial-1;
00837             j = outer_partial-i-1;
00838         }
00839 
00840         do
00841         {
00842             if (inner_partial && r_index >= inner_partial) 
00843             {
00844                 break;
00845             }
00846 
00847             tmp = sr[r_index] + ((long_comp)sa[j])*sb[i] + carry;
00848             sr[r_index++] = (comp)tmp;              /* downsize */
00849             carry = tmp >> COMP_BIT_SIZE;
00850         } while (++j < n);
00851 
00852         sr[r_index] = carry;
00853     } while (++i < t);
00854 
00855     bi_free(ctx, bia);
00856     bi_free(ctx, bib);
00857     return trim(biR);
00858 }
00859 
00860 #ifdef CONFIG_BIGINT_KARATSUBA
00861 /*
00862  * Karatsuba improves on regular multiplication due to only 3 multiplications 
00863  * being done instead of 4. The additional additions/subtractions are O(N) 
00864  * rather than O(N^2) and so for big numbers it saves on a few operations 
00865  */
00866 static bigint *karatsuba(BI_CTX *ctx, bigint *bia, bigint *bib, int is_square)
00867 {
00868     bigint *x0, *x1;
00869     bigint *p0, *p1, *p2;
00870     int m;
00871 
00872     if (is_square)
00873     {
00874         m = (bia->size + 1)/2;
00875     }
00876     else
00877     {
00878         m = (max(bia->size, bib->size) + 1)/2;
00879     }
00880 
00881     x0 = bi_clone(ctx, bia);
00882     x0->size = m;
00883     x1 = bi_clone(ctx, bia);
00884     comp_right_shift(x1, m);
00885     bi_free(ctx, bia);
00886 
00887     /* work out the 3 partial products */
00888     if (is_square)
00889     {
00890         p0 = bi_square(ctx, bi_copy(x0));
00891         p2 = bi_square(ctx, bi_copy(x1));
00892         p1 = bi_square(ctx, bi_add(ctx, x0, x1));
00893     }
00894     else /* normal multiply */
00895     {
00896         bigint *y0, *y1;
00897         y0 = bi_clone(ctx, bib);
00898         y0->size = m;
00899         y1 = bi_clone(ctx, bib);
00900         comp_right_shift(y1, m);
00901         bi_free(ctx, bib);
00902 
00903         p0 = bi_multiply(ctx, bi_copy(x0), bi_copy(y0));
00904         p2 = bi_multiply(ctx, bi_copy(x1), bi_copy(y1));
00905         p1 = bi_multiply(ctx, bi_add(ctx, x0, x1), bi_add(ctx, y0, y1));
00906     }
00907 
00908     p1 = bi_subtract(ctx, 
00909             bi_subtract(ctx, p1, bi_copy(p2), NULL), bi_copy(p0), NULL);
00910 
00911     comp_left_shift(p1, m);
00912     comp_left_shift(p2, 2*m);
00913     return bi_add(ctx, p1, bi_add(ctx, p0, p2));
00914 }
00915 #endif
00916 
00917 /**
00918  * @brief Perform a multiplication operation between two bigints.
00919  * @param ctx [in]  The bigint session context.
00920  * @param bia [in]  A bigint.
00921  * @param bib [in]  Another bigint.
00922  * @return The result of the multiplication.
00923  */
00924 bigint *bi_multiply(BI_CTX *ctx, bigint *bia, bigint *bib)
00925 {
00926     check(bia);
00927     check(bib);
00928 
00929 #ifdef CONFIG_BIGINT_KARATSUBA
00930     if (min(bia->size, bib->size) < MUL_KARATSUBA_THRESH)
00931     {
00932         return regular_multiply(ctx, bia, bib, 0, 0);
00933     }
00934 
00935     return karatsuba(ctx, bia, bib, 0);
00936 #else
00937     return regular_multiply(ctx, bia, bib, 0, 0);
00938 #endif
00939 }
00940 
00941 #ifdef CONFIG_BIGINT_SQUARE
00942 /*
00943  * Perform the actual square operion. It takes into account overflow.
00944  */
00945 static bigint *regular_square(BI_CTX *ctx, bigint *bi)
00946 {
00947     int t = bi->size;
00948     int i = 0, j;
00949     bigint *biR = alloc(ctx, t*2+1);
00950     comp *w = biR->comps;
00951     comp *x = bi->comps;
00952     long_comp carry;
00953     memset(w, 0, biR->size*COMP_BYTE_SIZE);
00954 
00955     do
00956     {
00957         long_comp tmp = w[2*i] + (long_comp)x[i]*x[i];
00958         w[2*i] = (comp)tmp;
00959         carry = tmp >> COMP_BIT_SIZE;
00960 
00961         for (j = i+1; j < t; j++)
00962         {
00963             uint8_t c = 0;
00964             long_comp xx = (long_comp)x[i]*x[j];
00965             if ((COMP_MAX-xx) < xx)
00966                 c = 1;
00967 
00968             tmp = (xx<<1);
00969 
00970             if ((COMP_MAX-tmp) < w[i+j])
00971                 c = 1;
00972 
00973             tmp += w[i+j];
00974 
00975             if ((COMP_MAX-tmp) < carry)
00976                 c = 1;
00977 
00978             tmp += carry;
00979             w[i+j] = (comp)tmp;
00980             carry = tmp >> COMP_BIT_SIZE;
00981 
00982             if (c)
00983                 carry += COMP_RADIX;
00984         }
00985 
00986         tmp = w[i+t] + carry;
00987         w[i+t] = (comp)tmp;
00988         w[i+t+1] = tmp >> COMP_BIT_SIZE;
00989     } while (++i < t);
00990 
00991     bi_free(ctx, bi);
00992     return trim(biR);
00993 }
00994 
00995 /**
00996  * @brief Perform a square operation on a bigint.
00997  * @param ctx [in]  The bigint session context.
00998  * @param bia [in]  A bigint.
00999  * @return The result of the multiplication.
01000  */
01001 bigint *bi_square(BI_CTX *ctx, bigint *bia)
01002 {
01003     check(bia);
01004 
01005 #ifdef CONFIG_BIGINT_KARATSUBA
01006     if (bia->size < SQU_KARATSUBA_THRESH) 
01007     {
01008         return regular_square(ctx, bia);
01009     }
01010 
01011     return karatsuba(ctx, bia, NULL, 1);
01012 #else
01013     return regular_square(ctx, bia);
01014 #endif
01015 }
01016 #endif
01017 
01018 /**
01019  * @brief Compare two bigints.
01020  * @param bia [in]  A bigint.
01021  * @param bib [in]  Another bigint.
01022  * @return -1 if smaller, 1 if larger and 0 if equal.
01023  */
01024 int bi_compare(bigint *bia, bigint *bib)
01025 {
01026     int r, i;
01027 
01028     check(bia);
01029     check(bib);
01030 
01031     if (bia->size > bib->size)
01032         r = 1;
01033     else if (bia->size < bib->size)
01034         r = -1;
01035     else
01036     {
01037         comp *a = bia->comps; 
01038         comp *b = bib->comps; 
01039 
01040         /* Same number of components.  Compare starting from the high end
01041          * and working down. */
01042         r = 0;
01043         i = bia->size - 1;
01044 
01045         do 
01046         {
01047             if (a[i] > b[i])
01048             { 
01049                 r = 1;
01050                 break; 
01051             }
01052             else if (a[i] < b[i])
01053             { 
01054                 r = -1;
01055                 break; 
01056             }
01057         } while (--i >= 0);
01058     }
01059 
01060     return r;
01061 }
01062 
01063 /*
01064  * Allocate and zero more components.  Does not consume bi. 
01065  */
01066 static void more_comps(bigint *bi, int n)
01067 {
01068     if (n > bi->max_comps)
01069     {
01070         bi->max_comps = max(bi->max_comps * 2, n);
01071         bi->comps = (comp*)realloc(bi->comps, bi->max_comps * COMP_BYTE_SIZE);
01072     }
01073 
01074     if (n > bi->size)
01075     {
01076         memset(&bi->comps[bi->size], 0, (n-bi->size)*COMP_BYTE_SIZE);
01077     }
01078 
01079     bi->size = n;
01080 }
01081 
01082 /*
01083  * Make a new empty bigint. It may just use an old one if one is available.
01084  * Otherwise get one off the heap.
01085  */
01086 static bigint *alloc(BI_CTX *ctx, int size)
01087 {
01088     bigint *biR;
01089 
01090     /* Can we recycle an old bigint? */
01091     if (ctx->free_list != NULL)
01092     {
01093         biR = ctx->free_list;
01094         ctx->free_list = biR->next;
01095         ctx->free_count--;
01096 
01097         if (biR->refs != 0)
01098         {
01099 #ifdef CONFIG_SSL_FULL_MODE
01100             printf("alloc: refs was not 0\n");
01101 #endif
01102             abort();    /* create a stack trace from a core dump */
01103         }
01104 
01105         more_comps(biR, size);
01106     }
01107     else
01108     {
01109         /* No free bigints available - create a new one. */
01110         biR = (bigint *)malloc(sizeof(bigint));
01111         biR->comps = (comp*)malloc(size * COMP_BYTE_SIZE);
01112         biR->max_comps = size;  /* give some space to spare */
01113     }
01114 
01115     biR->size = size;
01116     biR->refs = 1;
01117     biR->next = NULL;
01118     ctx->active_count++;
01119     return biR;
01120 }
01121 
01122 /*
01123  * Work out the highest '1' bit in an exponent. Used when doing sliding-window
01124  * exponentiation.
01125  */
01126 static int find_max_exp_index(bigint *biexp)
01127 {
01128     int i = COMP_BIT_SIZE-1;
01129     comp shift = COMP_RADIX/2;
01130     comp test = biexp->comps[biexp->size-1];    /* assume no leading zeroes */
01131 
01132     check(biexp);
01133 
01134     do
01135     {
01136         if (test & shift)
01137         {
01138             return i+(biexp->size-1)*COMP_BIT_SIZE;
01139         }
01140 
01141         shift >>= 1;
01142     } while (i-- != 0);
01143 
01144     return -1;      /* error - must have been a leading 0 */
01145 }
01146 
01147 /*
01148  * Is a particular bit is an exponent 1 or 0? Used when doing sliding-window
01149  * exponentiation.
01150  */
01151 static int exp_bit_is_one(bigint *biexp, int offset)
01152 {
01153     comp test = biexp->comps[offset / COMP_BIT_SIZE];
01154     int num_shifts = offset % COMP_BIT_SIZE;
01155     comp shift = 1;
01156     int i;
01157 
01158     check(biexp);
01159 
01160     for (i = 0; i < num_shifts; i++)
01161     {
01162         shift <<= 1;
01163     }
01164 
01165     return (test & shift) != 0;
01166 }
01167 
01168 #ifdef CONFIG_BIGINT_CHECK_ON
01169 /*
01170  * Perform a sanity check on bi.
01171  */
01172 static void check(const bigint *bi)
01173 {
01174     if (bi->refs <= 0)
01175     {
01176         printf("check: zero or negative refs in bigint\n");
01177         abort();
01178     }
01179 
01180     if (bi->next != NULL)
01181     {
01182         printf("check: attempt to use a bigint from "
01183                 "the free list\n");
01184         abort();
01185     }
01186 }
01187 #endif
01188 
01189 /*
01190  * Delete any leading 0's (and allow for 0).
01191  */
01192 static bigint *trim(bigint *bi)
01193 {
01194     check(bi);
01195 
01196     while (bi->comps[bi->size-1] == 0 && bi->size > 1)
01197     {
01198         bi->size--;
01199     }
01200 
01201     return bi;
01202 }
01203 
01204 #if defined(CONFIG_BIGINT_MONTGOMERY)
01205 /**
01206  * @brief Perform a single montgomery reduction.
01207  * @param ctx [in]  The bigint session context.
01208  * @param bixy [in]  A bigint.
01209  * @return The result of the montgomery reduction.
01210  */
01211 bigint *bi_mont(BI_CTX *ctx, bigint *bixy)
01212 {
01213     int i = 0, n;
01214     uint8_t mod_offset = ctx->mod_offset;
01215     bigint *bim = ctx->bi_mod[mod_offset];
01216     comp mod_inv = ctx->N0_dash[mod_offset];
01217 
01218     check(bixy);
01219 
01220     if (ctx->use_classical)     /* just use classical instead */
01221     {
01222         return bi_mod(ctx, bixy);
01223     }
01224 
01225     n = bim->size;
01226 
01227     do
01228     {
01229         bixy = bi_add(ctx, bixy, comp_left_shift(
01230                     bi_int_multiply(ctx, bim, bixy->comps[i]*mod_inv), i));
01231     } while (++i < n);
01232 
01233     comp_right_shift(bixy, n);
01234 
01235     if (bi_compare(bixy, bim) >= 0)
01236     {
01237         bixy = bi_subtract(ctx, bixy, bim, NULL);
01238     }
01239 
01240     return bixy;
01241 }
01242 
01243 #elif defined(CONFIG_BIGINT_BARRETT)
01244 /*
01245  * Stomp on the most significant components to give the illusion of a "mod base
01246  * radix" operation 
01247  */
01248 static bigint *comp_mod(bigint *bi, int mod)
01249 {
01250     check(bi);
01251 
01252     if (bi->size > mod)
01253     {
01254         bi->size = mod;
01255     }
01256 
01257     return bi;
01258 }
01259 
01260 /**
01261  * @brief Perform a single Barrett reduction.
01262  * @param ctx [in]  The bigint session context.
01263  * @param bi [in]  A bigint.
01264  * @return The result of the Barrett reduction.
01265  */
01266 bigint *bi_barrett(BI_CTX *ctx, bigint *bi)
01267 {
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 
01281         return bi_mod(ctx, bi);
01282     }
01283     bigint* a = bi_clone(ctx, bi);
01284     q1 = comp_right_shift(a, k-1);
01285 
01286     /* do outer partial multiply */
01287     q2 = regular_multiply(ctx, q1, ctx->bi_mu[mod_offset], 0, k-1); 
01288     q3 = comp_right_shift(q2, k+1);
01289     r1 = comp_mod(bi, k+1);
01290 
01291     /* do inner partial multiply */
01292     r2 = comp_mod(regular_multiply(ctx, q3, bim, k+1, 0), k+1);
01293     r = bi_subtract(ctx, r1, r2, NULL);
01294 
01295     /* if (r >= m) r = r - m; */
01296     if (bi_compare(r, bim) >= 0)
01297     {
01298 
01299         r = bi_subtract(ctx, r, bim, NULL);
01300     }
01301 
01302     return r;
01303 }
01304 #endif /* CONFIG_BIGINT_BARRETT */
01305 
01306 #ifdef CONFIG_BIGINT_SLIDING_WINDOW
01307 /*
01308  * Work out g1, g3, g5, g7... etc for the sliding-window algorithm 
01309  */
01310 static void precompute_slide_window(BI_CTX *ctx, int window, bigint *g1)
01311 {
01312     int k = 1, i;
01313     bigint *g2;
01314 
01315     for (i = 0; i < window-1; i++)   /* compute 2^(window-1) */
01316     {
01317         k <<= 1;
01318     }
01319 
01320     ctx->g = (bigint **)malloc(k*sizeof(bigint *));
01321     ctx->g[0] = bi_clone(ctx, g1);
01322     bi_permanent(ctx->g[0]);
01323     g2 = bi_residue(ctx, bi_square(ctx, ctx->g[0]));   /* g^2 */
01324 
01325     for (i = 1; i < k; i++)
01326     {
01327         ctx->g[i] = bi_residue(ctx, bi_multiply(ctx, ctx->g[i-1], bi_copy(g2)));
01328         bi_permanent(ctx->g[i]);
01329     }
01330 
01331     bi_free(ctx, g2);
01332     ctx->window = k;
01333 }
01334 #endif
01335 
01336 /**
01337  * @brief Perform a modular exponentiation.
01338  *
01339  * This function requires bi_set_mod() to have been called previously. This is 
01340  * one of the optimisations used for performance.
01341  * @param ctx [in]  The bigint session context.
01342  * @param bi  [in]  The bigint on which to perform the mod power operation.
01343  * @param biexp [in] The bigint exponent.
01344  * @return The result of the mod exponentiation operation
01345  * @see bi_set_mod().
01346  */
01347 bigint *bi_mod_power(BI_CTX *ctx, bigint *bi, bigint *biexp)
01348 {
01349     int i = find_max_exp_index(biexp), j, window_size = 1;
01350     bigint *biR = int_to_bi(ctx, 1);
01351 
01352 
01353 #if defined(CONFIG_BIGINT_MONTGOMERY)
01354     uint8_t mod_offset = ctx->mod_offset;
01355     if (!ctx->use_classical)
01356     {
01357         /* preconvert */
01358         bi = bi_mont(ctx, 
01359                 bi_multiply(ctx, bi, ctx->bi_RR_mod_m[mod_offset]));    /* x' */
01360         bi_free(ctx, biR);
01361         biR = ctx->bi_R_mod_m[mod_offset];                              /* A */
01362     }
01363 #endif
01364 
01365     check(bi);
01366     check(biexp);
01367 
01368 #ifdef CONFIG_BIGINT_SLIDING_WINDOW
01369     for (j = i; j > 32; j /= 5) /* work out an optimum size */
01370         window_size++;
01371 
01372     /* work out the slide constants */
01373     precompute_slide_window(ctx, window_size, bi);
01374 #else   /* just one constant */
01375     ctx->g = (bigint **)malloc(sizeof(bigint *));
01376     ctx->g[0] = bi_clone(ctx, bi);
01377     ctx->window = 1;
01378     bi_permanent(ctx->g[0]);
01379 #endif
01380 
01381     /* if sliding-window is off, then only one bit will be done at a time and
01382      * will reduce to standard left-to-right exponentiation */
01383     do
01384     {
01385         if (exp_bit_is_one(biexp, i))
01386         {
01387             int l = i-window_size+1;
01388             int part_exp = 0;
01389 
01390             if (l < 0)  /* LSB of exponent will always be 1 */
01391                 l = 0;
01392             else
01393             {
01394                 while (exp_bit_is_one(biexp, l) == 0)
01395                     l++;    /* go back up */
01396             }
01397             /* build up the section of the exponent */
01398             for (j = i; j >= l; j--)
01399             {
01400                 biR = bi_residue(ctx, bi_square(ctx, biR));
01401                 if (exp_bit_is_one(biexp, j))
01402                     part_exp++;
01403 
01404                 if (j != l)
01405                     part_exp <<= 1;
01406             }
01407             part_exp = (part_exp-1)/2;  /* adjust for array */
01408             bigint* a = bi_multiply(ctx, biR, ctx->g[part_exp]);
01409             biR = bi_residue(ctx, a);
01410             i = l-1;
01411         }
01412         else    /* square it */
01413         {
01414             biR = bi_residue(ctx, bi_square(ctx, biR));
01415             i--;
01416         }
01417         
01418     } while (i >= 0);
01419 
01420     /* cleanup */
01421     for (i = 0; i < ctx->window; i++)
01422     {
01423         bi_depermanent(ctx->g[i]);
01424         bi_free(ctx, ctx->g[i]);
01425     }
01426 
01427     free(ctx->g);
01428     bi_free(ctx, bi);
01429     bi_free(ctx, biexp);
01430 #if defined CONFIG_BIGINT_MONTGOMERY
01431     return ctx->use_classical ? biR : bi_mont(ctx, biR); /* convert back */
01432 #else /* CONFIG_BIGINT_CLASSICAL or CONFIG_BIGINT_BARRETT */
01433     return biR;
01434 #endif
01435 }
01436 
01437 #ifdef CONFIG_SSL_CERT_VERIFICATION
01438 /**
01439  * @brief Perform a modular exponentiation using a temporary modulus.
01440  *
01441  * We need this function to check the signatures of certificates. The modulus
01442  * of this function is temporary as it's just used for authentication.
01443  * @param ctx [in]  The bigint session context.
01444  * @param bi  [in]  The bigint to perform the exp/mod.
01445  * @param bim [in]  The temporary modulus.
01446  * @param biexp [in] The bigint exponent.
01447  * @return The result of the mod exponentiation operation
01448  * @see bi_set_mod().
01449  */
01450 bigint *bi_mod_power2(BI_CTX *ctx, bigint *bi, bigint *bim, bigint *biexp)
01451 {
01452     bigint *biR, *tmp_biR;
01453 
01454     /* Set up a temporary bigint context and transfer what we need between
01455      * them. We need to do this since we want to keep the original modulus
01456      * which is already in this context. This operation is only called when
01457      * doing peer verification, and so is not expensive :-) */
01458     BI_CTX *tmp_ctx = bi_initialize();
01459     bi_set_mod(tmp_ctx, bi_clone(tmp_ctx, bim), BIGINT_M_OFFSET);
01460     tmp_biR = bi_mod_power(tmp_ctx, 
01461                 bi_clone(tmp_ctx, bi), 
01462                 bi_clone(tmp_ctx, biexp));
01463     biR = bi_clone(ctx, tmp_biR);
01464     bi_free(tmp_ctx, tmp_biR);
01465     bi_free_mod(tmp_ctx, BIGINT_M_OFFSET);
01466     bi_terminate(tmp_ctx);
01467 
01468     bi_free(ctx, bi);
01469     bi_free(ctx, bim);
01470     bi_free(ctx, biexp);
01471     return biR;
01472 }
01473 #endif
01474 
01475 #ifdef CONFIG_BIGINT_CRT
01476 /**
01477  * @brief Use the Chinese Remainder Theorem to quickly perform RSA decrypts.
01478  *
01479  * @param ctx [in]  The bigint session context.
01480  * @param bi  [in]  The bigint to perform the exp/mod.
01481  * @param dP [in] CRT's dP bigint
01482  * @param dQ [in] CRT's dQ bigint
01483  * @param p [in] CRT's p bigint
01484  * @param q [in] CRT's q bigint
01485  * @param qInv [in] CRT's qInv bigint
01486  * @return The result of the CRT operation
01487  */
01488 bigint *bi_crt(BI_CTX *ctx, bigint *bi,
01489         bigint *dP, bigint *dQ,
01490         bigint *p, bigint *q, bigint *qInv)
01491 {
01492     bigint *m1, *m2, *h;
01493 
01494     /* Montgomery has a condition the 0 < x, y < m and these products violate
01495      * that condition. So disable Montgomery when using CRT */
01496 #if defined(CONFIG_BIGINT_MONTGOMERY)
01497     ctx->use_classical = 1;
01498 #endif
01499     ctx->mod_offset = BIGINT_P_OFFSET;
01500     m1 = bi_mod_power(ctx, bi_copy(bi), dP);
01501 
01502     ctx->mod_offset = BIGINT_Q_OFFSET;
01503     m2 = bi_mod_power(ctx, bi, dQ);
01504 
01505     h = bi_subtract(ctx, bi_add(ctx, m1, p), bi_copy(m2), NULL);
01506     h = bi_multiply(ctx, h, qInv);
01507     ctx->mod_offset = BIGINT_P_OFFSET;
01508     h = bi_residue(ctx, h);
01509 #if defined(CONFIG_BIGINT_MONTGOMERY)
01510     ctx->use_classical = 0;         /* reset for any further operation */
01511 #endif
01512     return bi_add(ctx, m2, bi_multiply(ctx, q, h));
01513 }
01514 #endif
01515 /** @} */