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