AppleCSP/open_ssl/bn/bn_exp.c

   1 /*
   2  * Copyright (c) 2000-2001 Apple Computer, 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 /* crypto/bn/bn_exp.c */
  20 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  21  * All rights reserved.
  22  *
  23  * This package is an SSL implementation written
  24  * by Eric Young (eay@cryptsoft.com).
  25  * The implementation was written so as to conform with Netscapes SSL.
  26  *
  27  * This library is free for commercial and non-commercial use as long as
  28  * the following conditions are aheared to.  The following conditions
  29  * apply to all code found in this distribution, be it the RC4, RSA,
  30  * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
  31  * included with this distribution is covered by the same copyright terms
  32  * except that the holder is Tim Hudson (tjh@cryptsoft.com).
  33  *
  34  * Copyright remains Eric Young's, and as such any Copyright notices in
  35  * the code are not to be removed.
  36  * If this package is used in a product, Eric Young should be given attribution
  37  * as the author of the parts of the library used.
  38  * This can be in the form of a textual message at program startup or
  39  * in documentation (online or textual) provided with the package.
  40  *
  41  * Redistribution and use in source and binary forms, with or without
  42  * modification, are permitted provided that the following conditions
  43  * are met:
  44  * 1. Redistributions of source code must retain the copyright
  45  *    notice, this list of conditions and the following disclaimer.
  46  * 2. Redistributions in binary form must reproduce the above copyright
  47  *    notice, this list of conditions and the following disclaimer in the
  48  *    documentation and/or other materials provided with the distribution.
  49  * 3. All advertising materials mentioning features or use of this software
  50  *    must display the following acknowledgement:
  51  *    "This product includes cryptographic software written by
  52  *     Eric Young (eay@cryptsoft.com)"
  53  *    The word 'cryptographic' can be left out if the rouines from the library
  54  *    being used are not cryptographic related :-).
  55  * 4. If you include any Windows specific code (or a derivative thereof) from
  56  *    the apps directory (application code) you must include an acknowledgement:
  57  *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
  58  *
  59  * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
  60  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  61  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  62  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  63  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  64  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  65  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  66  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  67  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  68  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  69  * SUCH DAMAGE.
  70  *
  71  * The licence and distribution terms for any publically available version or
  72  * derivative of this code cannot be changed.  i.e. this code cannot simply be
  73  * copied and put under another distribution licence
  74  * [including the GNU Public Licence.]
  75  */
  76
  77 #include <stdio.h>
  78 #include "cryptlib.h"
  79 #include "bn_lcl.h"
  80 #ifdef ATALLA
  81 # include <alloca.h>
  82 # include <atasi.h>
  83 # include <assert.h>
  84 # include <dlfcn.h>
  85 #endif
  86
  87 #define TABLE_SIZE      16
  88
  89 /* slow but works */
  90 int BN_mod_mul(BIGNUM *ret, BIGNUM *a, BIGNUM *b, const BIGNUM *m, BN_CTX *ctx)
  91         {
  92         BIGNUM *t;
  93         int r=0;
  94
  95         bn_check_top(a);
  96         bn_check_top(b);
  97         bn_check_top(m);
  98
  99         BN_CTX_start(ctx);
 100         if ((t = BN_CTX_get(ctx)) == NULL) goto err;
 101         if (a == b)
 102                 { if (!BN_sqr(t,a,ctx)) goto err; }
 103         else
 104                 { if (!BN_mul(t,a,b,ctx)) goto err; }
 105         if (!BN_mod(ret,t,m,ctx)) goto err;
 106         r=1;
 107 err:
 108         BN_CTX_end(ctx);
 109         return(r);
 110         }
 111
 112 #if 0
 113 /* this one works - simple but works */
 114 int BN_mod_exp(BIGNUM *r, BIGNUM *a, BIGNUM *p, BIGNUM *m, BN_CTX *ctx)
 115         {
 116         int i,bits,ret=0;
 117         BIGNUM *v,*tmp;
 118
 119         BN_CTX_start(ctx);
 120         v = BN_CTX_get(ctx);
 121         tmp = BN_CTX_get(ctx);
 122         if (v == NULL || tmp == NULL) goto err;
 123
 124         if (BN_copy(v,a) == NULL) goto err;
 125         bits=BN_num_bits(p);
 126
 127         if (BN_is_odd(p))
 128                 { if (BN_copy(r,a) == NULL) goto err; }
 129         else    { if (!BN_one(r)) goto err; }
 130
 131         for (i=1; i<bits; i++)
 132                 {
 133                 if (!BN_sqr(tmp,v,ctx)) goto err;
 134                 if (!BN_mod(v,tmp,m,ctx)) goto err;
 135                 if (BN_is_bit_set(p,i))
 136                         {
 137                         if (!BN_mul(tmp,r,v,ctx)) goto err;
 138                         if (!BN_mod(r,tmp,m,ctx)) goto err;
 139                         }
 140                 }
 141         ret=1;
 142 err:
 143         BN_CTX_end(ctx);
 144         return(ret);
 145         }
 146
 147 #endif
 148
 149 /* this one works - simple but works */
 150 int BN_exp(BIGNUM *r, BIGNUM *a, BIGNUM *p, BN_CTX *ctx)
 151         {
 152         int i,bits,ret=0;
 153         BIGNUM *v,*rr;
 154
 155         BN_CTX_start(ctx);
 156         if ((r == a) || (r == p))
 157                 rr = BN_CTX_get(ctx);
 158         else
 159                 rr = r;
 160         if ((v = BN_CTX_get(ctx)) == NULL) goto err;
 161
 162         if (BN_copy(v,a) == NULL) goto err;
 163         bits=BN_num_bits(p);
 164
 165         if (BN_is_odd(p))
 166                 { if (BN_copy(rr,a) == NULL) goto err; }
 167         else    { if (!BN_one(rr)) goto err; }
 168
 169         for (i=1; i<bits; i++)
 170                 {
 171                 if (!BN_sqr(v,v,ctx)) goto err;
 172                 if (BN_is_bit_set(p,i))
 173                         {
 174                         if (!BN_mul(rr,rr,v,ctx)) goto err;
 175                         }
 176                 }
 177         ret=1;
 178 err:
 179         if (r != rr) BN_copy(r,rr);
 180         BN_CTX_end(ctx);
 181         return(ret);
 182         }
 183
 184 #ifdef ATALLA
 185
 186 /*
 187  * This routine will dynamically check for the existance of an Atalla AXL-200
 188  * SSL accelerator module.  If one is found, the variable
 189  * asi_accelerator_present is set to 1 and the function pointers
 190  * ptr_ASI_xxxxxx above will be initialized to corresponding ASI API calls.
 191  */
 192 typedef int tfnASI_GetPerformanceStatistics(int reset_flag,
 193                                             unsigned int *ret_buf);
 194 typedef int tfnASI_GetHardwareConfig(long card_num, unsigned int *ret_buf);
 195 typedef int tfnASI_RSAPrivateKeyOpFn(RSAPrivateKey * rsaKey,
 196                                      unsigned char *output,
 197                                      unsigned char *input,
 198                                      unsigned int modulus_len);
 199
 200 static tfnASI_GetHardwareConfig *ptr_ASI_GetHardwareConfig;
 201 static tfnASI_RSAPrivateKeyOpFn *ptr_ASI_RSAPrivateKeyOpFn;
 202 static tfnASI_GetPerformanceStatistics *ptr_ASI_GetPerformanceStatistics;
 203 static int asi_accelerator_present;
 204 static int tried_atalla;
 205
 206 void atalla_initialize_accelerator_handle(void)
 207         {
 208         void *dl_handle;
 209         int status;
 210         unsigned int config_buf[1024];
 211         static int tested;
 212
 213         if(tested)
 214                 return;
 215
 216         tested=1;
 217
 218         bzero((void *)config_buf, 1024);
 219
 220         /*
 221          * Check to see if the library is present on the system
 222          */
 223         dl_handle = dlopen("atasi.so", RTLD_NOW);
 224         if (dl_handle == (void *) NULL)
 225                 {
 226 /*              printf("atasi.so library is not present on the system\n");
 227                 printf("No HW acceleration available\n");*/
 228                 return;
 229                 }
 230
 231         /*
 232          * The library is present.  Now we'll check to insure that the
 233          * LDM is up and running. First we'll get the address of the
 234          * function in the atasi library that we need to see if the
 235          * LDM is operating.
 236          */
 237
 238         ptr_ASI_GetHardwareConfig =
 239           (tfnASI_GetHardwareConfig *)dlsym(dl_handle,"ASI_GetHardwareConfig");
 240
 241         if (ptr_ASI_GetHardwareConfig)
 242                 {
 243                 /*
 244                  * We found the call, now we'll get our config
 245                  * status.  If we get a non 0 result, the LDM is not
 246                  * running and we cannot use the Atalla ASI *
 247                  * library.
 248                  */
 249                 status = (*ptr_ASI_GetHardwareConfig)(0L, config_buf);
 250                 if (status != 0)
 251                         {
 252                         printf("atasi.so library is present but not initialized\n");
 253                         printf("No HW acceleration available\n");
 254                         return;
 255                         }
 256                 }
 257         else
 258                 {
 259 /*              printf("We found the library, but not the function. Very Strange!\n");*/
 260                 return ;
 261                 }
 262
 263         /*
 264          * It looks like we have acceleration capabilities.  Load up the
 265          * pointers to our ASI API calls.
 266          */
 267         ptr_ASI_RSAPrivateKeyOpFn=
 268           (tfnASI_RSAPrivateKeyOpFn *)dlsym(dl_handle, "ASI_RSAPrivateKeyOpFn");
 269         if (ptr_ASI_RSAPrivateKeyOpFn == NULL)
 270                 {
 271 /*              printf("We found the library, but no RSA function. Very Strange!\n");*/
 272                 return;
 273                 }
 274
 275         ptr_ASI_GetPerformanceStatistics =
 276           (tfnASI_GetPerformanceStatistics *)dlsym(dl_handle, "ASI_GetPerformanceStatistics");
 277         if (ptr_ASI_GetPerformanceStatistics == NULL)
 278                 {
 279 /*              printf("We found the library, but no stat function. Very Strange!\n");*/
 280                 return;
 281               }
 282
 283         /*
 284          * Indicate that acceleration is available
 285          */
 286         asi_accelerator_present = 1;
 287
 288 /*      printf("This system has acceleration!\n");*/
 289
 290         return;
 291         }
 292
 293 /* make sure this only gets called once when bn_mod_exp calls bn_mod_exp_mont */
 294 int BN_mod_exp_atalla(BIGNUM *r, BIGNUM *a, const BIGNUM *p, const BIGNUM *m)
 295         {
 296         unsigned char *abin;
 297         unsigned char *pbin;
 298         unsigned char *mbin;
 299         unsigned char *rbin;
 300         int an,pn,mn,ret;
 301         RSAPrivateKey keydata;
 302
 303         atalla_initialize_accelerator_handle();
 304         if(!asi_accelerator_present)
 305                 return 0;
 306
 307
 308 /* We should be able to run without size testing */
 309 # define ASIZE  128
 310         an=BN_num_bytes(a);
 311         pn=BN_num_bytes(p);
 312         mn=BN_num_bytes(m);
 313
 314         if(an <= ASIZE && pn <= ASIZE && mn <= ASIZE)
 315             {
 316             int size=mn;
 317
 318             assert(an <= mn);
 319             abin=alloca(size);
 320             memset(abin,'\0',mn);
 321             BN_bn2bin(a,abin+size-an);
 322
 323             pbin=alloca(pn);
 324             BN_bn2bin(p,pbin);
 325
 326             mbin=alloca(size);
 327             memset(mbin,'\0',mn);
 328             BN_bn2bin(m,mbin+size-mn);
 329
 330             rbin=alloca(size);
 331
 332             memset(&keydata,'\0',sizeof keydata);
 333             keydata.privateExponent.data=pbin;
 334             keydata.privateExponent.len=pn;
 335             keydata.modulus.data=mbin;
 336             keydata.modulus.len=size;
 337
 338             ret=(*ptr_ASI_RSAPrivateKeyOpFn)(&keydata,rbin,abin,keydata.modulus.len);
 339 /*fprintf(stderr,"!%s\n",BN_bn2hex(a));*/
 340             if(!ret)
 341                 {
 342                 BN_bin2bn(rbin,keydata.modulus.len,r);
 343 /*fprintf(stderr,"?%s\n",BN_bn2hex(r));*/
 344                 return 1;
 345                 }
 346             }
 347         return 0;
 348         }
 349 #endif /* def ATALLA */
 350
 351 int BN_mod_exp(BIGNUM *r, BIGNUM *a, const BIGNUM *p, const BIGNUM *m,
 352                BN_CTX *ctx)
 353         {
 354         int ret;
 355
 356         bn_check_top(a);
 357         bn_check_top(p);
 358         bn_check_top(m);
 359
 360 #ifdef ATALLA
 361         if(BN_mod_exp_atalla(r,a,p,m))
 362             return 1;
 363 /* If it fails, try the other methods (but don't try atalla again) */
 364         tried_atalla=1;
 365 #endif
 366
 367 #ifdef MONT_MUL_MOD
 368         /* I have finally been able to take out this pre-condition of
 369          * the top bit being set.  It was caused by an error in BN_div
 370          * with negatives.  There was also another problem when for a^b%m
 371          * a >= m.  eay 07-May-97 */
 372 /*      if ((m->d[m->top-1]&BN_TBIT) && BN_is_odd(m)) */
 373
 374         if (BN_is_odd(m))
 375                 { ret=BN_mod_exp_mont(r,a,p,m,ctx,NULL); }
 376         else
 377 #endif
 378 #ifdef RECP_MUL_MOD
 379                 { ret=BN_mod_exp_recp(r,a,p,m,ctx); }
 380 #else
 381                 { ret=BN_mod_exp_simple(r,a,p,m,ctx); }
 382 #endif
 383
 384 #ifdef ATALLA
 385         tried_atalla=0;
 386 #endif
 387
 388         return(ret);
 389         }
 390
 391 /* #ifdef RECP_MUL_MOD */
 392 int BN_mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p,
 393                     const BIGNUM *m, BN_CTX *ctx)
 394         {
 395         int i,j,bits,ret=0,wstart,wend,window,wvalue;
 396         int start=1,ts=0;
 397         BIGNUM *aa;
 398         BIGNUM val[TABLE_SIZE];
 399         BN_RECP_CTX recp;
 400
 401         bits=BN_num_bits(p);
 402
 403         if (bits == 0)
 404                 {
 405                 BN_one(r);
 406                 return(1);
 407                 }
 408
 409         BN_CTX_start(ctx);
 410         if ((aa = BN_CTX_get(ctx)) == NULL) goto err;
 411
 412         BN_RECP_CTX_init(&recp);
 413         if (BN_RECP_CTX_set(&recp,m,ctx) <= 0) goto err;
 414
 415         BN_init(&(val[0]));
 416         ts=1;
 417
 418         if (!BN_mod(&(val[0]),a,m,ctx)) goto err;               /* 1 */
 419         if (!BN_mod_mul_reciprocal(aa,&(val[0]),&(val[0]),&recp,ctx))
 420                 goto err;                               /* 2 */
 421
 422         if (bits <= 17) /* This is probably 3 or 0x10001, so just do singles */
 423                 window=1;
 424         else if (bits >= 256)
 425                 window=5;       /* max size of window */
 426         else if (bits >= 128)
 427                 window=4;
 428         else
 429                 window=3;
 430
 431         j=1<<(window-1);
 432         for (i=1; i<j; i++)
 433                 {
 434                 BN_init(&val[i]);
 435                 if (!BN_mod_mul_reciprocal(&(val[i]),&(val[i-1]),aa,&recp,ctx))
 436                         goto err;
 437                 }
 438         ts=i;
 439
 440         start=1;        /* This is used to avoid multiplication etc
 441                          * when there is only the value '1' in the
 442                          * buffer. */
 443         wvalue=0;       /* The 'value' of the window */
 444         wstart=bits-1;  /* The top bit of the window */
 445         wend=0;         /* The bottom bit of the window */
 446
 447         if (!BN_one(r)) goto err;
 448
 449         for (;;)
 450                 {
 451                 if (BN_is_bit_set(p,wstart) == 0)
 452                         {
 453                         if (!start)
 454                                 if (!BN_mod_mul_reciprocal(r,r,r,&recp,ctx))
 455                                 goto err;
 456                         if (wstart == 0) break;
 457                         wstart--;
 458                         continue;
 459                         }
 460                 /* We now have wstart on a 'set' bit, we now need to work out
 461                  * how bit a window to do.  To do this we need to scan
 462                  * forward until the last set bit before the end of the
 463                  * window */
 464                 j=wstart;
 465                 wvalue=1;
 466                 wend=0;
 467                 for (i=1; i<window; i++)
 468                         {
 469                         if (wstart-i < 0) break;
 470                         if (BN_is_bit_set(p,wstart-i))
 471                                 {
 472                                 wvalue<<=(i-wend);
 473                                 wvalue|=1;
 474                                 wend=i;
 475                                 }
 476                         }
 477
 478                 /* wend is the size of the current window */
 479                 j=wend+1;
 480                 /* add the 'bytes above' */
 481                 if (!start)
 482                         for (i=0; i<j; i++)
 483                                 {
 484                                 if (!BN_mod_mul_reciprocal(r,r,r,&recp,ctx))
 485                                         goto err;
 486                                 }
 487
 488                 /* wvalue will be an odd number < 2^window */
 489                 if (!BN_mod_mul_reciprocal(r,r,&(val[wvalue>>1]),&recp,ctx))
 490                         goto err;
 491
 492                 /* move the 'window' down further */
 493                 wstart-=wend+1;
 494                 wvalue=0;
 495                 start=0;
 496                 if (wstart < 0) break;
 497                 }
 498         ret=1;
 499 err:
 500         BN_CTX_end(ctx);
 501         for (i=0; i<ts; i++)
 502                 BN_clear_free(&(val[i]));
 503         BN_RECP_CTX_free(&recp);
 504         return(ret);
 505         }
 506 /* #endif */
 507
 508 /* #ifdef MONT_MUL_MOD */
 509 int BN_mod_exp_mont(BIGNUM *rr, BIGNUM *a, const BIGNUM *p,
 510                     const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont)
 511         {
 512         int i,j,bits,ret=0,wstart,wend,window,wvalue;
 513         int start=1,ts=0;
 514         BIGNUM *d,*r;
 515         BIGNUM *aa;
 516         BIGNUM val[TABLE_SIZE];
 517         BN_MONT_CTX *mont=NULL;
 518
 519         bn_check_top(a);
 520         bn_check_top(p);
 521         bn_check_top(m);
 522
 523 #ifdef ATALLA
 524         if(!tried_atalla && BN_mod_exp_atalla(rr,a,p,m))
 525             return 1;
 526 /* If it fails, try the other methods */
 527 #endif
 528
 529         if (!(m->d[0] & 1))
 530                 {
 531                 BNerr(BN_F_BN_MOD_EXP_MONT,BN_R_CALLED_WITH_EVEN_MODULUS);
 532                 return(0);
 533                 }
 534         bits=BN_num_bits(p);
 535         if (bits == 0)
 536                 {
 537                 BN_one(rr);
 538                 return(1);
 539                 }
 540         BN_CTX_start(ctx);
 541         d = BN_CTX_get(ctx);
 542         r = BN_CTX_get(ctx);
 543         if (d == NULL || r == NULL) goto err;
 544
 545         /* If this is not done, things will break in the montgomery
 546          * part */
 547
 548 #if 1
 549         if (in_mont != NULL)
 550                 mont=in_mont;
 551         else
 552 #endif
 553                 {
 554                 if ((mont=BN_MONT_CTX_new()) == NULL) goto err;
 555                 if (!BN_MONT_CTX_set(mont,m,ctx)) goto err;
 556                 }
 557
 558         BN_init(&val[0]);
 559         ts=1;
 560         if (BN_ucmp(a,m) >= 0)
 561                 {
 562                 BN_mod(&(val[0]),a,m,ctx);
 563                 aa= &(val[0]);
 564                 }
 565         else
 566                 aa=a;
 567         if (!BN_to_montgomery(&(val[0]),aa,mont,ctx)) goto err; /* 1 */
 568         if (!BN_mod_mul_montgomery(d,&(val[0]),&(val[0]),mont,ctx)) goto err; /* 2 */
 569
 570         if (bits <= 20) /* This is probably 3 or 0x10001, so just do singles */
 571                 window=1;
 572         else if (bits >= 256)
 573                 window=5;       /* max size of window */
 574         else if (bits >= 128)
 575                 window=4;
 576         else
 577                 window=3;
 578
 579         j=1<<(window-1);
 580         for (i=1; i<j; i++)
 581                 {
 582                 BN_init(&(val[i]));
 583                 if (!BN_mod_mul_montgomery(&(val[i]),&(val[i-1]),d,mont,ctx))
 584                         goto err;
 585                 }
 586         ts=i;
 587
 588         start=1;        /* This is used to avoid multiplication etc
 589                          * when there is only the value '1' in the
 590                          * buffer. */
 591         wvalue=0;       /* The 'value' of the window */
 592         wstart=bits-1;  /* The top bit of the window */
 593         wend=0;         /* The bottom bit of the window */
 594
 595         if (!BN_to_montgomery(r,BN_value_one(),mont,ctx)) goto err;
 596         for (;;)
 597                 {
 598                 if (BN_is_bit_set(p,wstart) == 0)
 599                         {
 600                         if (!start)
 601                                 {
 602                                 if (!BN_mod_mul_montgomery(r,r,r,mont,ctx))
 603                                 goto err;
 604                                 }
 605                         if (wstart == 0) break;
 606                         wstart--;
 607                         continue;
 608                         }
 609                 /* We now have wstart on a 'set' bit, we now need to work out
 610                  * how bit a window to do.  To do this we need to scan
 611                  * forward until the last set bit before the end of the
 612                  * window */
 613                 j=wstart;
 614                 wvalue=1;
 615                 wend=0;
 616                 for (i=1; i<window; i++)
 617                         {
 618                         if (wstart-i < 0) break;
 619                         if (BN_is_bit_set(p,wstart-i))
 620                                 {
 621                                 wvalue<<=(i-wend);
 622                                 wvalue|=1;
 623                                 wend=i;
 624                                 }
 625                         }
 626
 627                 /* wend is the size of the current window */
 628                 j=wend+1;
 629                 /* add the 'bytes above' */
 630                 if (!start)
 631                         for (i=0; i<j; i++)
 632                                 {
 633                                 if (!BN_mod_mul_montgomery(r,r,r,mont,ctx))
 634                                         goto err;
 635                                 }
 636
 637                 /* wvalue will be an odd number < 2^window */
 638                 if (!BN_mod_mul_montgomery(r,r,&(val[wvalue>>1]),mont,ctx))
 639                         goto err;
 640
 641                 /* move the 'window' down further */
 642                 wstart-=wend+1;
 643                 wvalue=0;
 644                 start=0;
 645                 if (wstart < 0) break;
 646                 }
 647         BN_from_montgomery(rr,r,mont,ctx);
 648         ret=1;
 649 err:
 650         if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont);
 651         BN_CTX_end(ctx);
 652         for (i=0; i<ts; i++)
 653                 BN_clear_free(&(val[i]));
 654         return(ret);
 655         }
 656 /* #endif */
 657
 658 /* The old fallback, simple version :-) */
 659 int BN_mod_exp_simple(BIGNUM *r, BIGNUM *a, BIGNUM *p, BIGNUM *m,
 660              BN_CTX *ctx)
 661         {
 662         int i,j,bits,ret=0,wstart,wend,window,wvalue,ts=0;
 663         int start=1;
 664         BIGNUM *d;
 665         BIGNUM val[TABLE_SIZE];
 666
 667         bits=BN_num_bits(p);
 668
 669         if (bits == 0)
 670                 {
 671                 BN_one(r);
 672                 return(1);
 673                 }
 674
 675         BN_CTX_start(ctx);
 676         if ((d = BN_CTX_get(ctx)) == NULL) goto err;
 677
 678         BN_init(&(val[0]));
 679         ts=1;
 680         if (!BN_mod(&(val[0]),a,m,ctx)) goto err;               /* 1 */
 681         if (!BN_mod_mul(d,&(val[0]),&(val[0]),m,ctx))
 682                 goto err;                               /* 2 */
 683
 684         if (bits <= 17) /* This is probably 3 or 0x10001, so just do singles */
 685                 window=1;
 686         else if (bits >= 256)
 687                 window=5;       /* max size of window */
 688         else if (bits >= 128)
 689                 window=4;
 690         else
 691                 window=3;
 692
 693         j=1<<(window-1);
 694         for (i=1; i<j; i++)
 695                 {
 696                 BN_init(&(val[i]));
 697                 if (!BN_mod_mul(&(val[i]),&(val[i-1]),d,m,ctx))
 698                         goto err;
 699                 }
 700         ts=i;
 701
 702         start=1;        /* This is used to avoid multiplication etc
 703                          * when there is only the value '1' in the
 704                          * buffer. */
 705         wvalue=0;       /* The 'value' of the window */
 706         wstart=bits-1;  /* The top bit of the window */
 707         wend=0;         /* The bottom bit of the window */
 708
 709         if (!BN_one(r)) goto err;
 710
 711         for (;;)
 712                 {
 713                 if (BN_is_bit_set(p,wstart) == 0)
 714                         {
 715                         if (!start)
 716                                 if (!BN_mod_mul(r,r,r,m,ctx))
 717                                 goto err;
 718                         if (wstart == 0) break;
 719                         wstart--;
 720                         continue;
 721                         }
 722                 /* We now have wstart on a 'set' bit, we now need to work out
 723                  * how bit a window to do.  To do this we need to scan
 724                  * forward until the last set bit before the end of the
 725                  * window */
 726                 j=wstart;
 727                 wvalue=1;
 728                 wend=0;
 729                 for (i=1; i<window; i++)
 730                         {
 731                         if (wstart-i < 0) break;
 732                         if (BN_is_bit_set(p,wstart-i))
 733                                 {
 734                                 wvalue<<=(i-wend);
 735                                 wvalue|=1;
 736                                 wend=i;
 737                                 }
 738                         }
 739
 740                 /* wend is the size of the current window */
 741                 j=wend+1;
 742                 /* add the 'bytes above' */
 743                 if (!start)
 744                         for (i=0; i<j; i++)
 745                                 {
 746                                 if (!BN_mod_mul(r,r,r,m,ctx))
 747                                         goto err;
 748                                 }
 749
 750                 /* wvalue will be an odd number < 2^window */
 751                 if (!BN_mod_mul(r,r,&(val[wvalue>>1]),m,ctx))
 752                         goto err;
 753
 754                 /* move the 'window' down further */
 755                 wstart-=wend+1;
 756                 wvalue=0;
 757                 start=0;
 758                 if (wstart < 0) break;
 759                 }
 760         ret=1;
 761 err:
 762         BN_CTX_end(ctx);
 763         for (i=0; i<ts; i++)
 764                 BN_clear_free(&(val[i]));
 765         return(ret);
 766         }
 767