OSX/libsecurity_apple_csp/open_ssl/bn/bn_exp2.c

   1 /*
   2  * Copyright (c) 2000-2001,2011,2014 Apple Inc. All Rights Reserved.
   3  *
   4  * The contents of this file constitute Original Code as defined in and are
   5  * subject to the Apple Public Source License Version 1.2 (the 'License').
   6  * You may not use this file except in compliance with the License. Please obtain
   7  * a copy of the License at http://www.apple.com/publicsource and read it before
   8  * using this file.
   9  *
  10  * This Original Code and all software distributed under the License are
  11  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESS
  12  * OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, INCLUDING WITHOUT
  13  * LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
  14  * PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. Please see the License for the
  15  * specific language governing rights and limitations under the License.
  16  */
  17
  18
  19 #include <stdio.h>
  20 #include "cryptlib.h"
  21 #include "bn_lcl.h"
  22
  23 /* I've done some timing with different table sizes.
  24  * The main hassle is that even with bits set at 3, this requires
  25  * 63 BIGNUMs to store the pre-calculated values.
  26  *          512   1024
  27  * bits=1  75.4%  79.4%
  28  * bits=2  61.2%  62.4%
  29  * bits=3  61.3%  59.3%
  30  * The lack of speed improvement is also a function of the pre-calculation
  31  * which could be removed.
  32  */
  33 #define EXP2_TABLE_BITS 2 /* 1  2  3  4  5  */
  34 #define EXP2_TABLE_SIZE 4 /* 2  4  8 16 32  */
  35
  36 int BN_mod_exp2_mont(BIGNUM *rr, BIGNUM *a1, BIGNUM *p1, BIGNUM *a2,
  37              BIGNUM *p2, BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont)
  38         {
  39         int i,j,k,bits,bits1,bits2,ret=0,wstart,wend,window,xvalue,yvalue;
  40         int start=1,ts=0,x,y;
  41         BIGNUM *d,*aa1,*aa2,*r;
  42         BIGNUM val[EXP2_TABLE_SIZE][EXP2_TABLE_SIZE];
  43         BN_MONT_CTX *mont=NULL;
  44
  45         bn_check_top(a1);
  46         bn_check_top(p1);
  47         bn_check_top(a2);
  48         bn_check_top(p2);
  49         bn_check_top(m);
  50
  51         if (!(m->d[0] & 1))
  52                 {
  53                 BNerr(BN_F_BN_MOD_EXP_MONT,BN_R_CALLED_WITH_EVEN_MODULUS);
  54                 return(0);
  55                 }
  56         bits1=BN_num_bits(p1);
  57         bits2=BN_num_bits(p2);
  58         if ((bits1 == 0) && (bits2 == 0))
  59                 {
  60                 BN_one(rr);
  61                 return(1);
  62                 }
  63
  64         BN_CTX_start(ctx);
  65         d = BN_CTX_get(ctx);
  66         r = BN_CTX_get(ctx);
  67         if (d == NULL || r == NULL) goto err;
  68
  69         bits=(bits1 > bits2)?bits1:bits2;
  70
  71         /* If this is not done, things will break in the montgomery
  72          * part */
  73
  74         if (in_mont != NULL)
  75                 mont=in_mont;
  76         else
  77                 {
  78                 if ((mont=BN_MONT_CTX_new()) == NULL) goto err;
  79                 if (!BN_MONT_CTX_set(mont,m,ctx)) goto err;
  80                 }
  81
  82         BN_init(&(val[0][0]));
  83         BN_init(&(val[1][1]));
  84         BN_init(&(val[0][1]));
  85         BN_init(&(val[1][0]));
  86         ts=1;
  87         if (BN_ucmp(a1,m) >= 0)
  88                 {
  89                 BN_mod(&(val[1][0]),a1,m,ctx);
  90                 aa1= &(val[1][0]);
  91                 }
  92         else
  93                 aa1=a1;
  94         if (BN_ucmp(a2,m) >= 0)
  95                 {
  96                 BN_mod(&(val[0][1]),a2,m,ctx);
  97                 aa2= &(val[0][1]);
  98                 }
  99         else
 100                 aa2=a2;
 101         if (!BN_to_montgomery(&(val[1][0]),aa1,mont,ctx)) goto err;
 102         if (!BN_to_montgomery(&(val[0][1]),aa2,mont,ctx)) goto err;
 103         if (!BN_mod_mul_montgomery(&(val[1][1]),
 104                 &(val[1][0]),&(val[0][1]),mont,ctx))
 105                 goto err;
 106
 107 #if 0
 108         if (bits <= 20) /* This is probably 3 or 0x10001, so just do singles */
 109                 window=1;
 110         else if (bits > 250)
 111                 window=5;       /* max size of window */
 112         else if (bits >= 120)
 113                 window=4;
 114         else
 115                 window=3;
 116 #else
 117         window=EXP2_TABLE_BITS;
 118 #endif
 119
 120         k=1<<window;
 121         for (x=0; x<k; x++)
 122                 {
 123                 if (x >= 2)
 124                         {
 125                         BN_init(&(val[x][0]));
 126                         BN_init(&(val[x][1]));
 127                         if (!BN_mod_mul_montgomery(&(val[x][0]),
 128                                 &(val[1][0]),&(val[x-1][0]),mont,ctx)) goto err;
 129                         if (!BN_mod_mul_montgomery(&(val[x][1]),
 130                                 &(val[1][0]),&(val[x-1][1]),mont,ctx)) goto err;
 131                         }
 132                 for (y=2; y<k; y++)
 133                         {
 134                         BN_init(&(val[x][y]));
 135                         if (!BN_mod_mul_montgomery(&(val[x][y]),
 136                                 &(val[x][y-1]),&(val[0][1]),mont,ctx))
 137                                 goto err;
 138                         }
 139                 }
 140         ts=k;
 141
 142         start=1;        /* This is used to avoid multiplication etc
 143                          * when there is only the value '1' in the
 144                          * buffer. */
 145         xvalue=0;       /* The 'x value' of the window */
 146         yvalue=0;       /* The 'y value' of the window */
 147         wstart=bits-1;  /* The top bit of the window */
 148         wend=0;         /* The bottom bit of the window */
 149
 150         if (!BN_to_montgomery(r,BN_value_one(),mont,ctx)) goto err;
 151         for (;;)
 152                 {
 153                 xvalue=BN_is_bit_set(p1,wstart);
 154                 yvalue=BN_is_bit_set(p2,wstart);
 155                 if (!(xvalue || yvalue))
 156                         {
 157                         if (!start)
 158                                 {
 159                                 if (!BN_mod_mul_montgomery(r,r,r,mont,ctx))
 160                                         goto err;
 161                                 }
 162                         wstart--;
 163                         if (wstart < 0) break;
 164                         continue;
 165                         }
 166                 /* We now have wstart on a 'set' bit, we now need to work out
 167                  * how bit a window to do.  To do this we need to scan
 168                  * forward until the last set bit before the end of the
 169                  * window */
 170                 j=wstart;
 171                 /* xvalue=BN_is_bit_set(p1,wstart); already set */
 172                 /* yvalue=BN_is_bit_set(p1,wstart); already set */
 173                 wend=0;
 174                 for (i=1; i<window; i++)
 175                         {
 176                         if (wstart-i < 0) break;
 177                         xvalue+=xvalue;
 178                         xvalue|=BN_is_bit_set(p1,wstart-i);
 179                         yvalue+=yvalue;
 180                         yvalue|=BN_is_bit_set(p2,wstart-i);
 181                         }
 182
 183                 /* i is the size of the current window */
 184                 /* add the 'bytes above' */
 185                 if (!start)
 186                         for (j=0; j<i; j++)
 187                                 {
 188                                 if (!BN_mod_mul_montgomery(r,r,r,mont,ctx))
 189                                         goto err;
 190                                 }
 191
 192                 /* wvalue will be an odd number < 2^window */
 193                 if (xvalue || yvalue)
 194                         {
 195                         if (!BN_mod_mul_montgomery(r,r,&(val[xvalue][yvalue]),
 196                                 mont,ctx)) goto err;
 197                         }
 198
 199                 /* move the 'window' down further */
 200                 wstart-=i;
 201                 start=0;
 202                 if (wstart < 0) break;
 203                 }
 204         BN_from_montgomery(rr,r,mont,ctx);
 205         ret=1;
 206 err:
 207         if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont);
 208         BN_CTX_end(ctx);
 209         for (i=0; i<ts; i++)
 210                 {
 211                 for (j=0; j<ts; j++)
 212                         {
 213                         BN_clear_free(&(val[i][j]));
 214                         }
 215                 }
 216         return(ret);
 217         }