crypto/bn/bn_exp.c

   1 /* crypto/bn/bn_exp.c */
   2 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
   3  * All rights reserved.
   4  *
   5  * This package is an SSL implementation written
   6  * by Eric Young (eay@cryptsoft.com).
   7  * The implementation was written so as to conform with Netscapes SSL.
   8  *
   9  * This library is free for commercial and non-commercial use as long as
  10  * the following conditions are aheared to.  The following conditions
  11  * apply to all code found in this distribution, be it the RC4, RSA,
  12  * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
  13  * included with this distribution is covered by the same copyright terms
  14  * except that the holder is Tim Hudson (tjh@cryptsoft.com).
  15  *
  16  * Copyright remains Eric Young's, and as such any Copyright notices in
  17  * the code are not to be removed.
  18  * If this package is used in a product, Eric Young should be given attribution
  19  * as the author of the parts of the library used.
  20  * This can be in the form of a textual message at program startup or
  21  * in documentation (online or textual) provided with the package.
  22  *
  23  * Redistribution and use in source and binary forms, with or without
  24  * modification, are permitted provided that the following conditions
  25  * are met:
  26  * 1. Redistributions of source code must retain the copyright
  27  *    notice, this list of conditions and the following disclaimer.
  28  * 2. Redistributions in binary form must reproduce the above copyright
  29  *    notice, this list of conditions and the following disclaimer in the
  30  *    documentation and/or other materials provided with the distribution.
  31  * 3. All advertising materials mentioning features or use of this software
  32  *    must display the following acknowledgement:
  33  *    "This product includes cryptographic software written by
  34  *     Eric Young (eay@cryptsoft.com)"
  35  *    The word 'cryptographic' can be left out if the rouines from the library
  36  *    being used are not cryptographic related :-).
  37  * 4. If you include any Windows specific code (or a derivative thereof) from
  38  *    the apps directory (application code) you must include an acknowledgement:
  39  *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
  40  *
  41  * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
  42  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  43  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  44  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  45  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  46  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  47  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  48  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  49  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  50  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  51  * SUCH DAMAGE.
  52  *
  53  * The licence and distribution terms for any publically available version or
  54  * derivative of this code cannot be changed.  i.e. this code cannot simply be
  55  * copied and put under another distribution licence
  56  * [including the GNU Public Licence.]
  57  */
  58
  59 #include <stdio.h>
  60 #include "cryptlib.h"
  61 #include "bn_lcl.h"
  62
  63 /* slow but works */
  64 int BN_mod_mul(ret, a, b, m, ctx)
  65 BIGNUM *ret;
  66 BIGNUM *a;
  67 BIGNUM *b;
  68 BIGNUM *m;
  69 BN_CTX *ctx;
  70         {
  71         BIGNUM *t;
  72         int r=0;
  73
  74         t=ctx->bn[ctx->tos++];
  75         if (a == b)
  76                 { if (!BN_sqr(t,a,ctx)) goto err; }
  77         else
  78                 { if (!BN_mul(t,a,b)) goto err; }
  79         if (!BN_mod(ret,t,m,ctx)) goto err;
  80         r=1;
  81 err:
  82         ctx->tos--;
  83         return(r);
  84         }
  85
  86 #if 0
  87 /* this one works - simple but works */
  88 int BN_mod_exp(r,a,p,m,ctx)
  89 BIGNUM *r,*a,*p,*m;
  90 BN_CTX *ctx;
  91         {
  92         int i,bits,ret=0;
  93         BIGNUM *v,*tmp;
  94
  95         v=ctx->bn[ctx->tos++];
  96         tmp=ctx->bn[ctx->tos++];
  97
  98         if (BN_copy(v,a) == NULL) goto err;
  99         bits=BN_num_bits(p);
 100
 101         if (BN_is_odd(p))
 102                 { if (BN_copy(r,a) == NULL) goto err; }
 103         else    { if (BN_one(r)) goto err; }
 104
 105         for (i=1; i<bits; i++)
 106                 {
 107                 if (!BN_sqr(tmp,v,ctx)) goto err;
 108                 if (!BN_mod(v,tmp,m,ctx)) goto err;
 109                 if (BN_is_bit_set(p,i))
 110                         {
 111                         if (!BN_mul(tmp,r,v)) goto err;
 112                         if (!BN_mod(r,tmp,m,ctx)) goto err;
 113                         }
 114                 }
 115         ret=1;
 116 err:
 117         ctx->tos-=2;
 118         return(ret);
 119         }
 120
 121 #endif
 122
 123 /* this one works - simple but works */
 124 int BN_exp(r,a,p,ctx)
 125 BIGNUM *r,*a,*p;
 126 BN_CTX *ctx;
 127         {
 128         int i,bits,ret=0;
 129         BIGNUM *v,*tmp;
 130
 131         v=ctx->bn[ctx->tos++];
 132         tmp=ctx->bn[ctx->tos++];
 133
 134         if (BN_copy(v,a) == NULL) goto err;
 135         bits=BN_num_bits(p);
 136
 137         if (BN_is_odd(p))
 138                 { if (BN_copy(r,a) == NULL) goto err; }
 139         else    { if (BN_one(r)) goto err; }
 140
 141         for (i=1; i<bits; i++)
 142                 {
 143                 if (!BN_sqr(tmp,v,ctx)) goto err;
 144                 if (BN_is_bit_set(p,i))
 145                         {
 146                         if (!BN_mul(tmp,r,v)) goto err;
 147                         }
 148                 }
 149         ret=1;
 150 err:
 151         ctx->tos-=2;
 152         return(ret);
 153         }
 154
 155 int BN_mod_exp(r,a,p,m,ctx)
 156 BIGNUM *r;
 157 BIGNUM *a;
 158 BIGNUM *p;
 159 BIGNUM *m;
 160 BN_CTX *ctx;
 161         {
 162         int ret;
 163
 164 #ifdef MONT_MUL_MOD
 165         /* I have finally been able to take out this pre-condition of
 166          * the top bit being set.  It was caused by an error in BN_div
 167          * with negatives.  There was also another problem when for a^b%m
 168          * a >= m.  eay 07-May-97 */
 169 /*      if ((m->d[m->top-1]&BN_TBIT) && BN_is_odd(m)) */
 170
 171         if (BN_is_odd(m))
 172                 { ret=BN_mod_exp_mont(r,a,p,m,ctx,NULL); }
 173         else
 174 #endif
 175 #ifdef RECP_MUL_MOD
 176                 { ret=BN_mod_exp_recp(r,a,p,m,ctx); }
 177 #else
 178                 { ret=BN_mod_exp_simple(r,a,p,m,ctx); }
 179 #endif
 180
 181         return(ret);
 182         }
 183
 184 /* #ifdef RECP_MUL_MOD */
 185 int BN_mod_exp_recp(r,a,p,m,ctx)
 186 BIGNUM *r;
 187 BIGNUM *a;
 188 BIGNUM *p;
 189 BIGNUM *m;
 190 BN_CTX *ctx;
 191         {
 192         int nb,i,j,bits,ret=0,wstart,wend,window,wvalue;
 193         int start=1;
 194         BIGNUM *d,*aa;
 195         BIGNUM *val[16];
 196
 197         d=ctx->bn[ctx->tos++];
 198         aa=ctx->bn[ctx->tos++];
 199         bits=BN_num_bits(p);
 200
 201         if (bits == 0)
 202                 {
 203                 BN_one(r);
 204                 return(1);
 205                 }
 206         nb=BN_reciprocal(d,m,ctx);
 207         if (nb == -1) goto err;
 208
 209         val[0]=BN_new();
 210         if (!BN_mod(val[0],a,m,ctx)) goto err;          /* 1 */
 211         if (!BN_mod_mul_reciprocal(aa,val[0],val[0],m,d,nb,ctx))
 212                 goto err;                               /* 2 */
 213
 214         if (bits <= 17) /* This is probably 3 or 0x10001, so just do singles */
 215                 window=1;
 216         else if (bits >= 256)
 217                 window=5;       /* max size of window */
 218         else if (bits >= 128)
 219                 window=4;
 220         else
 221                 window=3;
 222
 223         j=1<<(window-1);
 224         for (i=1; i<j; i++)
 225                 {
 226                 val[i]=BN_new();
 227                 if (!BN_mod_mul_reciprocal(val[i],val[i-1],aa,m,d,nb,ctx))
 228                         goto err;
 229                 }
 230         for (; i<16; i++)
 231                 val[i]=NULL;
 232
 233         start=1;        /* This is used to avoid multiplication etc
 234                          * when there is only the value '1' in the
 235                          * buffer. */
 236         wvalue=0;       /* The 'value' of the window */
 237         wstart=bits-1;  /* The top bit of the window */
 238         wend=0;         /* The bottom bit of the window */
 239
 240         if (!BN_one(r)) goto err;
 241
 242         for (;;)
 243                 {
 244                 if (BN_is_bit_set(p,wstart) == 0)
 245                         {
 246                         if (!start)
 247                                 if (!BN_mod_mul_reciprocal(r,r,r,m,d,nb,ctx))
 248                                 goto err;
 249                         if (wstart == 0) break;
 250                         wstart--;
 251                         continue;
 252                         }
 253                 /* We now have wstart on a 'set' bit, we now need to work out
 254                  * how bit a window to do.  To do this we need to scan
 255                  * forward until the last set bit before the end of the
 256                  * window */
 257                 j=wstart;
 258                 wvalue=1;
 259                 wend=0;
 260                 for (i=1; i<window; i++)
 261                         {
 262                         if (wstart-i < 0) break;
 263                         if (BN_is_bit_set(p,wstart-i))
 264                                 {
 265                                 wvalue<<=(i-wend);
 266                                 wvalue|=1;
 267                                 wend=i;
 268                                 }
 269                         }
 270
 271                 /* wend is the size of the current window */
 272                 j=wend+1;
 273                 /* add the 'bytes above' */
 274                 if (!start)
 275                         for (i=0; i<j; i++)
 276                                 {
 277                                 if (!BN_mod_mul_reciprocal(r,r,r,m,d,nb,ctx))
 278                                         goto err;
 279                                 }
 280
 281                 /* wvalue will be an odd number < 2^window */
 282                 if (!BN_mod_mul_reciprocal(r,r,val[wvalue>>1],m,d,nb,ctx))
 283                         goto err;
 284
 285                 /* move the 'window' down further */
 286                 wstart-=wend+1;
 287                 wvalue=0;
 288                 start=0;
 289                 if (wstart < 0) break;
 290                 }
 291         ret=1;
 292 err:
 293         ctx->tos-=2;
 294         for (i=0; i<16; i++)
 295                 if (val[i] != NULL) BN_clear_free(val[i]);
 296         return(ret);
 297         }
 298 /* #endif */
 299
 300 /* #ifdef MONT_MUL_MOD */
 301 int BN_mod_exp_mont(r,a,p,m,ctx,in_mont)
 302 BIGNUM *r;
 303 BIGNUM *a;
 304 BIGNUM *p;
 305 BIGNUM *m;
 306 BN_CTX *ctx;
 307 BN_MONT_CTX *in_mont;
 308         {
 309 #define TABLE_SIZE      16
 310         int i,j,bits,ret=0,wstart,wend,window,wvalue;
 311         int start=1;
 312         BIGNUM *d,*aa;
 313         BIGNUM *val[TABLE_SIZE];
 314         BN_MONT_CTX *mont=NULL;
 315
 316         if (!(m->d[0] & 1))
 317                 {
 318                 BNerr(BN_F_BN_MOD_EXP_MONT,BN_R_CALLED_WITH_EVEN_MODULUS);
 319                 return(0);
 320                 }
 321         d=ctx->bn[ctx->tos++];
 322         bits=BN_num_bits(p);
 323         if (bits == 0)
 324                 {
 325                 BN_one(r);
 326                 return(1);
 327                 }
 328
 329         /* If this is not done, things will break in the montgomery
 330          * part */
 331
 332 #if 1
 333         if (in_mont != NULL)
 334                 mont=in_mont;
 335         else
 336 #endif
 337                 {
 338                 if ((mont=BN_MONT_CTX_new()) == NULL) goto err;
 339                 if (!BN_MONT_CTX_set(mont,m,ctx)) goto err;
 340                 }
 341
 342         val[0]=BN_new();
 343         if (BN_ucmp(a,m) >= 0)
 344                 {
 345                 BN_mod(val[0],a,m,ctx);
 346                 aa=val[0];
 347                 }
 348         else
 349                 aa=a;
 350         if (!BN_to_montgomery(val[0],aa,mont,ctx)) goto err; /* 1 */
 351         if (!BN_mod_mul_montgomery(d,val[0],val[0],mont,ctx)) goto err; /* 2 */
 352
 353         if (bits <= 20) /* This is probably 3 or 0x10001, so just do singles */
 354                 window=1;
 355         else if (bits > 250)
 356                 window=5;       /* max size of window */
 357         else if (bits >= 120)
 358                 window=4;
 359         else
 360                 window=3;
 361
 362         j=1<<(window-1);
 363         for (i=1; i<j; i++)
 364                 {
 365                 val[i]=BN_new();
 366                 if (!BN_mod_mul_montgomery(val[i],val[i-1],d,mont,ctx))
 367                         goto err;
 368                 }
 369         for (; i<TABLE_SIZE; i++)
 370                 val[i]=NULL;
 371
 372         start=1;        /* This is used to avoid multiplication etc
 373                          * when there is only the value '1' in the
 374                          * buffer. */
 375         wvalue=0;       /* The 'value' of the window */
 376         wstart=bits-1;  /* The top bit of the window */
 377         wend=0;         /* The bottom bit of the window */
 378
 379         if (!BN_to_montgomery(r,BN_value_one(),mont,ctx)) goto err;
 380         for (;;)
 381                 {
 382                 if (BN_is_bit_set(p,wstart) == 0)
 383                         {
 384                         if (!start)
 385                                 {
 386                                 if (!BN_mod_mul_montgomery(r,r,r,mont,ctx))
 387                                 goto err;
 388                                 }
 389                         if (wstart == 0) break;
 390                         wstart--;
 391                         continue;
 392                         }
 393                 /* We now have wstart on a 'set' bit, we now need to work out
 394                  * how bit a window to do.  To do this we need to scan
 395                  * forward until the last set bit before the end of the
 396                  * window */
 397                 j=wstart;
 398                 wvalue=1;
 399                 wend=0;
 400                 for (i=1; i<window; i++)
 401                         {
 402                         if (wstart-i < 0) break;
 403                         if (BN_is_bit_set(p,wstart-i))
 404                                 {
 405                                 wvalue<<=(i-wend);
 406                                 wvalue|=1;
 407                                 wend=i;
 408                                 }
 409                         }
 410
 411                 /* wend is the size of the current window */
 412                 j=wend+1;
 413                 /* add the 'bytes above' */
 414                 if (!start)
 415                         for (i=0; i<j; i++)
 416                                 {
 417                                 if (!BN_mod_mul_montgomery(r,r,r,mont,ctx))
 418                                         goto err;
 419                                 }
 420
 421                 /* wvalue will be an odd number < 2^window */
 422                 if (!BN_mod_mul_montgomery(r,r,val[wvalue>>1],mont,ctx))
 423                         goto err;
 424
 425                 /* move the 'window' down further */
 426                 wstart-=wend+1;
 427                 wvalue=0;
 428                 start=0;
 429                 if (wstart < 0) break;
 430                 }
 431         BN_from_montgomery(r,r,mont,ctx);
 432         ret=1;
 433 err:
 434         if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont);
 435         ctx->tos--;
 436         for (i=0; i<TABLE_SIZE; i++)
 437                 if (val[i] != NULL) BN_clear_free(val[i]);
 438         return(ret);
 439         }
 440 /* #endif */
 441
 442 /* The old fallback, simple version :-) */
 443 int BN_mod_exp_simple(r,a,p,m,ctx)
 444 BIGNUM *r;
 445 BIGNUM *a;
 446 BIGNUM *p;
 447 BIGNUM *m;
 448 BN_CTX *ctx;
 449         {
 450         int i,j,bits,ret=0,wstart,wend,window,wvalue;
 451         int start=1;
 452         BIGNUM *d;
 453         BIGNUM *val[16];
 454
 455         d=ctx->bn[ctx->tos++];
 456         bits=BN_num_bits(p);
 457
 458         if (bits == 0)
 459                 {
 460                 BN_one(r);
 461                 return(1);
 462                 }
 463
 464         val[0]=BN_new();
 465         if (!BN_mod(val[0],a,m,ctx)) goto err;          /* 1 */
 466         if (!BN_mod_mul(d,val[0],val[0],m,ctx))
 467                 goto err;                               /* 2 */
 468
 469         if (bits <= 17) /* This is probably 3 or 0x10001, so just do singles */
 470                 window=1;
 471         else if (bits >= 256)
 472                 window=5;       /* max size of window */
 473         else if (bits >= 128)
 474                 window=4;
 475         else
 476                 window=3;
 477
 478         j=1<<(window-1);
 479         for (i=1; i<j; i++)
 480                 {
 481                 val[i]=BN_new();
 482                 if (!BN_mod_mul(val[i],val[i-1],d,m,ctx))
 483                         goto err;
 484                 }
 485         for (; i<16; i++)
 486                 val[i]=NULL;
 487
 488         start=1;        /* This is used to avoid multiplication etc
 489                          * when there is only the value '1' in the
 490                          * buffer. */
 491         wvalue=0;       /* The 'value' of the window */
 492         wstart=bits-1;  /* The top bit of the window */
 493         wend=0;         /* The bottom bit of the window */
 494
 495         if (!BN_one(r)) goto err;
 496
 497         for (;;)
 498                 {
 499                 if (BN_is_bit_set(p,wstart) == 0)
 500                         {
 501                         if (!start)
 502                                 if (!BN_mod_mul(r,r,r,m,ctx))
 503                                 goto err;
 504                         if (wstart == 0) break;
 505                         wstart--;
 506                         continue;
 507                         }
 508                 /* We now have wstart on a 'set' bit, we now need to work out
 509                  * how bit a window to do.  To do this we need to scan
 510                  * forward until the last set bit before the end of the
 511                  * window */
 512                 j=wstart;
 513                 wvalue=1;
 514                 wend=0;
 515                 for (i=1; i<window; i++)
 516                         {
 517                         if (wstart-i < 0) break;
 518                         if (BN_is_bit_set(p,wstart-i))
 519                                 {
 520                                 wvalue<<=(i-wend);
 521                                 wvalue|=1;
 522                                 wend=i;
 523                                 }
 524                         }
 525
 526                 /* wend is the size of the current window */
 527                 j=wend+1;
 528                 /* add the 'bytes above' */
 529                 if (!start)
 530                         for (i=0; i<j; i++)
 531                                 {
 532                                 if (!BN_mod_mul(r,r,r,m,ctx))
 533                                         goto err;
 534                                 }
 535
 536                 /* wvalue will be an odd number < 2^window */
 537                 if (!BN_mod_mul(r,r,val[wvalue>>1],m,ctx))
 538                         goto err;
 539
 540                 /* move the 'window' down further */
 541                 wstart-=wend+1;
 542                 wvalue=0;
 543                 start=0;
 544                 if (wstart < 0) break;
 545                 }
 546         ret=1;
 547 err:
 548         ctx->tos--;
 549         for (i=0; i<16; i++)
 550                 if (val[i] != NULL) BN_clear_free(val[i]);
 551         return(ret);
 552         }
 553