crypto/bn/bn_exp2.c

   1 #include <stdio.h>
   2 #include "cryptlib.h"
   3 #include "bn_lcl.h"
   4
   5 /* I've done some timing with different table sizes.
   6  * The main hassle is that even with bits set at 3, this requires
   7  * 63 BIGNUMs to store the pre-calculated values.
   8  *          512   1024
   9  * bits=1  75.4%  79.4%
  10  * bits=2  61.2%  62.4%
  11  * bits=3  61.3%  59.3%
  12  * The lack of speed improvment is also a function of the pre-calculation
  13  * which could be removed.
  14  */
  15 #define EXP2_TABLE_BITS 2 /* 1  2  3  4  5  */
  16 #define EXP2_TABLE_SIZE 4 /* 2  4  8 16 32  */
  17
  18 int BN_mod_exp2_mont(BIGNUM *rr, BIGNUM *a1, BIGNUM *p1, BIGNUM *a2,
  19              BIGNUM *p2, BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont)
  20         {
  21         int i,j,k,bits,bits1,bits2,ret=0,wstart,wend,window,xvalue,yvalue;
  22         int start=1,ts=0,x,y;
  23         BIGNUM *d,*aa1,*aa2,*r;
  24         BIGNUM val[EXP2_TABLE_SIZE][EXP2_TABLE_SIZE];
  25         BN_MONT_CTX *mont=NULL;
  26
  27         bn_check_top(a1);
  28         bn_check_top(p1);
  29         bn_check_top(a2);
  30         bn_check_top(p2);
  31         bn_check_top(m);
  32
  33         if (!(m->d[0] & 1))
  34                 {
  35                 BNerr(BN_F_BN_MOD_EXP_MONT,BN_R_CALLED_WITH_EVEN_MODULUS);
  36                 return(0);
  37                 }
  38         d= &(ctx->bn[ctx->tos++]);
  39         r= &(ctx->bn[ctx->tos++]);
  40         bits1=BN_num_bits(p1);
  41         bits2=BN_num_bits(p2);
  42         if ((bits1 == 0) && (bits2 == 0))
  43                 {
  44                 BN_one(r);
  45                 return(1);
  46                 }
  47         bits=(bits1 > bits2)?bits1:bits2;
  48
  49         /* If this is not done, things will break in the montgomery
  50          * part */
  51
  52         if (in_mont != NULL)
  53                 mont=in_mont;
  54         else
  55                 {
  56                 if ((mont=BN_MONT_CTX_new()) == NULL) goto err;
  57                 if (!BN_MONT_CTX_set(mont,m,ctx)) goto err;
  58                 }
  59
  60         BN_init(&(val[0][0]));
  61         BN_init(&(val[1][1]));
  62         BN_init(&(val[0][1]));
  63         BN_init(&(val[1][0]));
  64         ts=1;
  65         if (BN_ucmp(a1,m) >= 0)
  66                 {
  67                 BN_mod(&(val[1][0]),a1,m,ctx);
  68                 aa1= &(val[1][0]);
  69                 }
  70         else
  71                 aa1=a1;
  72         if (BN_ucmp(a2,m) >= 0)
  73                 {
  74                 BN_mod(&(val[0][1]),a2,m,ctx);
  75                 aa2= &(val[0][1]);
  76                 }
  77         else
  78                 aa2=a2;
  79         if (!BN_to_montgomery(&(val[1][0]),aa1,mont,ctx)) goto err;
  80         if (!BN_to_montgomery(&(val[0][1]),aa2,mont,ctx)) goto err;
  81         if (!BN_mod_mul_montgomery(&(val[1][1]),
  82                 &(val[1][0]),&(val[0][1]),mont,ctx))
  83                 goto err;
  84
  85 #if 0
  86         if (bits <= 20) /* This is probably 3 or 0x10001, so just do singles */
  87                 window=1;
  88         else if (bits > 250)
  89                 window=5;       /* max size of window */
  90         else if (bits >= 120)
  91                 window=4;
  92         else
  93                 window=3;
  94 #else
  95         window=EXP2_TABLE_BITS;
  96 #endif
  97
  98         k=1<<window;
  99         for (x=0; x<k; x++)
 100                 {
 101                 if (x >= 2)
 102                         {
 103                         BN_init(&(val[x][0]));
 104                         BN_init(&(val[x][1]));
 105                         if (!BN_mod_mul_montgomery(&(val[x][0]),
 106                                 &(val[1][0]),&(val[x-1][0]),mont,ctx)) goto err;
 107                         if (!BN_mod_mul_montgomery(&(val[x][1]),
 108                                 &(val[1][0]),&(val[x-1][1]),mont,ctx)) goto err;
 109                         }
 110                 for (y=2; y<k; y++)
 111                         {
 112                         BN_init(&(val[x][y]));
 113                         if (!BN_mod_mul_montgomery(&(val[x][y]),
 114                                 &(val[x][y-1]),&(val[0][1]),mont,ctx))
 115                                 goto err;
 116                         }
 117                 }
 118         ts=k;
 119
 120         start=1;        /* This is used to avoid multiplication etc
 121                          * when there is only the value '1' in the
 122                          * buffer. */
 123         xvalue=0;       /* The 'x value' of the window */
 124         yvalue=0;       /* The 'y value' of the window */
 125         wstart=bits-1;  /* The top bit of the window */
 126         wend=0;         /* The bottom bit of the window */
 127
 128         if (!BN_to_montgomery(r,BN_value_one(),mont,ctx)) goto err;
 129         for (;;)
 130                 {
 131                 xvalue=BN_is_bit_set(p1,wstart);
 132                 yvalue=BN_is_bit_set(p2,wstart);
 133                 if (!(xvalue || yvalue))
 134                         {
 135                         if (!start)
 136                                 {
 137                                 if (!BN_mod_mul_montgomery(r,r,r,mont,ctx))
 138                                         goto err;
 139                                 }
 140                         wstart--;
 141                         if (wstart < 0) break;
 142                         continue;
 143                         }
 144                 /* We now have wstart on a 'set' bit, we now need to work out
 145                  * how bit a window to do.  To do this we need to scan
 146                  * forward until the last set bit before the end of the
 147                  * window */
 148                 j=wstart;
 149                 /* xvalue=BN_is_bit_set(p1,wstart); already set */
 150                 /* yvalue=BN_is_bit_set(p1,wstart); already set */
 151                 wend=0;
 152                 for (i=1; i<window; i++)
 153                         {
 154                         if (wstart-i < 0) break;
 155                         xvalue+=xvalue;
 156                         xvalue|=BN_is_bit_set(p1,wstart-i);
 157                         yvalue+=yvalue;
 158                         yvalue|=BN_is_bit_set(p2,wstart-i);
 159                         }
 160
 161                 /* i is the size of the current window */
 162                 /* add the 'bytes above' */
 163                 if (!start)
 164                         for (j=0; j<i; j++)
 165                                 {
 166                                 if (!BN_mod_mul_montgomery(r,r,r,mont,ctx))
 167                                         goto err;
 168                                 }
 169
 170                 /* wvalue will be an odd number < 2^window */
 171                 if (xvalue || yvalue)
 172                         {
 173                         if (!BN_mod_mul_montgomery(r,r,&(val[xvalue][yvalue]),
 174                                 mont,ctx)) goto err;
 175                         }
 176
 177                 /* move the 'window' down further */
 178                 wstart-=i;
 179                 start=0;
 180                 if (wstart < 0) break;
 181                 }
 182         BN_from_montgomery(rr,r,mont,ctx);
 183         ret=1;
 184 err:
 185         if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont);
 186         ctx->tos-=2;
 187         for (i=0; i<ts; i++)
 188                 {
 189                 for (j=0; j<ts; j++)
 190                         {
 191                         BN_clear_free(&(val[i][j]));
 192                         }
 193                 }
 194         return(ret);
 195         }