crypto/bn/bn_exp.c

   1 /* crypto/bn/bn_exp.c */
   2 /* Copyright (C) 1995-1997 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 int BN_mod_exp(r,a,p,m,ctx)
 124 BIGNUM *r;
 125 BIGNUM *a;
 126 BIGNUM *p;
 127 BIGNUM *m;
 128 BN_CTX *ctx;
 129         {
 130         int ret;
 131
 132 #ifdef MONT_MUL_MOD
 133         /* I have finally been able to take out this pre-condition of
 134          * the top bit being set.  It was caused by an error in BN_div
 135          * with negatives.  There was also another problem when for a^b%m
 136          * a >= m.  eay 07-May-97 */
 137 /*      if ((m->d[m->top-1]&BN_TBIT) && BN_is_odd(m)) */
 138
 139         if (BN_is_odd(m))
 140                 { ret=BN_mod_exp_mont(r,a,p,m,ctx); }
 141         else
 142 #endif
 143 #ifdef RECP_MUL_MOD
 144                 { ret=BN_mod_exp_recp(r,a,p,m,ctx); }
 145 #else
 146                 { ret=BN_mod_exp_simple(r,a,p,m,ctx); }
 147 #endif
 148
 149         return(ret);
 150         }
 151
 152 /* #ifdef RECP_MUL_MOD */
 153 int BN_mod_exp_recp(r,a,p,m,ctx)
 154 BIGNUM *r;
 155 BIGNUM *a;
 156 BIGNUM *p;
 157 BIGNUM *m;
 158 BN_CTX *ctx;
 159         {
 160         int nb,i,j,bits,ret=0,wstart,wend,window,wvalue;
 161         int start=1;
 162         BIGNUM *d,*aa;
 163         BIGNUM *val[16];
 164
 165         d=ctx->bn[ctx->tos++];
 166         aa=ctx->bn[ctx->tos++];
 167         bits=BN_num_bits(p);
 168
 169         if (bits == 0)
 170                 {
 171                 BN_one(r);
 172                 return(1);
 173                 }
 174         nb=BN_reciprocal(d,m,ctx);
 175         if (nb == -1) goto err;
 176
 177         val[0]=BN_new();
 178         if (!BN_mod(val[0],a,m,ctx)) goto err;          /* 1 */
 179         if (!BN_mod_mul_reciprocal(aa,val[0],val[0],m,d,nb,ctx))
 180                 goto err;                               /* 2 */
 181
 182         if (bits <= 17) /* This is probably 3 or 0x10001, so just do singles */
 183                 window=1;
 184         else if (bits >= 256)
 185                 window=5;       /* max size of window */
 186         else if (bits >= 128)
 187                 window=4;
 188         else
 189                 window=3;
 190
 191         j=1<<(window-1);
 192         for (i=1; i<j; i++)
 193                 {
 194                 val[i]=BN_new();
 195                 if (!BN_mod_mul_reciprocal(val[i],val[i-1],aa,m,d,nb,ctx))
 196                         goto err;
 197                 }
 198         for (; i<16; i++)
 199                 val[i]=NULL;
 200
 201         start=1;        /* This is used to avoid multiplication etc
 202                          * when there is only the value '1' in the
 203                          * buffer. */
 204         wvalue=0;       /* The 'value' of the window */
 205         wstart=bits-1;  /* The top bit of the window */
 206         wend=0;         /* The bottom bit of the window */
 207
 208         if (!BN_one(r)) goto err;
 209
 210         for (;;)
 211                 {
 212                 if (BN_is_bit_set(p,wstart) == 0)
 213                         {
 214                         if (!start)
 215                                 if (!BN_mod_mul_reciprocal(r,r,r,m,d,nb,ctx))
 216                                 goto err;
 217                         if (wstart == 0) break;
 218                         wstart--;
 219                         continue;
 220                         }
 221                 /* We now have wstart on a 'set' bit, we now need to work out
 222                  * how bit a window to do.  To do this we need to scan
 223                  * forward until the last set bit before the end of the
 224                  * window */
 225                 j=wstart;
 226                 wvalue=1;
 227                 wend=0;
 228                 for (i=1; i<window; i++)
 229                         {
 230                         if (wstart-i < 0) break;
 231                         if (BN_is_bit_set(p,wstart-i))
 232                                 {
 233                                 wvalue<<=(i-wend);
 234                                 wvalue|=1;
 235                                 wend=i;
 236                                 }
 237                         }
 238
 239                 /* wend is the size of the current window */
 240                 j=wend+1;
 241                 /* add the 'bytes above' */
 242                 if (!start)
 243                         for (i=0; i<j; i++)
 244                                 {
 245                                 if (!BN_mod_mul_reciprocal(r,r,r,m,d,nb,ctx))
 246                                         goto err;
 247                                 }
 248
 249                 /* wvalue will be an odd number < 2^window */
 250                 if (!BN_mod_mul_reciprocal(r,r,val[wvalue>>1],m,d,nb,ctx))
 251                         goto err;
 252
 253                 /* move the 'window' down further */
 254                 wstart-=wend+1;
 255                 wvalue=0;
 256                 start=0;
 257                 if (wstart < 0) break;
 258                 }
 259         ret=1;
 260 err:
 261         ctx->tos-=2;
 262         for (i=0; i<16; i++)
 263                 if (val[i] != NULL) BN_clear_free(val[i]);
 264         return(ret);
 265         }
 266 /* #endif */
 267
 268 /* #ifdef MONT_MUL_MOD */
 269 int BN_mod_exp_mont(r,a,p,m,ctx)
 270 BIGNUM *r;
 271 BIGNUM *a;
 272 BIGNUM *p;
 273 BIGNUM *m;
 274 BN_CTX *ctx;
 275         {
 276         int i,j,bits,ret=0,wstart,wend,window,wvalue;
 277         int start=1;
 278         BIGNUM *d,*aa;
 279         BIGNUM *val[16];
 280         BN_MONT_CTX *mont=NULL;
 281
 282         if (!(m->d[0] & 1))
 283                 {
 284                 BNerr(BN_F_BN_MOD_EXP_MONT,BN_R_CALLED_WITH_EVEN_MODULUS);
 285                 return(0);
 286                 }
 287         d=ctx->bn[ctx->tos++];
 288         bits=BN_num_bits(p);
 289         if (bits == 0)
 290                 {
 291                 BN_one(r);
 292                 return(1);
 293                 }
 294
 295         /* If this is not done, things will break in the montgomery
 296          * part */
 297
 298         if ((mont=BN_MONT_CTX_new()) == NULL) goto err;
 299         if (!BN_MONT_CTX_set(mont,m,ctx)) goto err;
 300
 301         val[0]=BN_new();
 302         if (BN_ucmp(a,m) >= 0)
 303                 {
 304                 BN_mod(val[0],a,m,ctx);
 305                 aa=val[0];
 306                 }
 307         else
 308                 aa=a;
 309         if (!BN_to_montgomery(val[0],aa,mont,ctx)) goto err; /* 1 */
 310         if (!BN_mod_mul_montgomery(d,val[0],val[0],mont,ctx)) goto err; /* 2 */
 311
 312         if (bits <= 17) /* This is probably 3 or 0x10001, so just do singles */
 313                 window=1;
 314         else if (bits >= 256)
 315                 window=5;       /* max size of window */
 316         else if (bits >= 128)
 317                 window=4;
 318         else
 319                 window=3;
 320
 321         j=1<<(window-1);
 322         for (i=1; i<j; i++)
 323                 {
 324                 val[i]=BN_new();
 325                 if (!BN_mod_mul_montgomery(val[i],val[i-1],d,mont,ctx))
 326                         goto err;
 327                 }
 328         for (; i<16; i++)
 329                 val[i]=NULL;
 330
 331         start=1;        /* This is used to avoid multiplication etc
 332                          * when there is only the value '1' in the
 333                          * buffer. */
 334         wvalue=0;       /* The 'value' of the window */
 335         wstart=bits-1;  /* The top bit of the window */
 336         wend=0;         /* The bottom bit of the window */
 337
 338         if (!BN_to_montgomery(r,BN_value_one(),mont,ctx)) goto err;
 339         for (;;)
 340                 {
 341                 if (BN_is_bit_set(p,wstart) == 0)
 342                         {
 343                         if (!start)
 344                                 if (!BN_mod_mul_montgomery(r,r,r,mont,ctx))
 345                                 goto err;
 346                         if (wstart == 0) break;
 347                         wstart--;
 348                         continue;
 349                         }
 350                 /* We now have wstart on a 'set' bit, we now need to work out
 351                  * how bit a window to do.  To do this we need to scan
 352                  * forward until the last set bit before the end of the
 353                  * window */
 354                 j=wstart;
 355                 wvalue=1;
 356                 wend=0;
 357                 for (i=1; i<window; i++)
 358                         {
 359                         if (wstart-i < 0) break;
 360                         if (BN_is_bit_set(p,wstart-i))
 361                                 {
 362                                 wvalue<<=(i-wend);
 363                                 wvalue|=1;
 364                                 wend=i;
 365                                 }
 366                         }
 367
 368                 /* wend is the size of the current window */
 369                 j=wend+1;
 370                 /* add the 'bytes above' */
 371                 if (!start)
 372                         for (i=0; i<j; i++)
 373                                 {
 374                                 if (!BN_mod_mul_montgomery(r,r,r,mont,ctx))
 375                                         goto err;
 376                                 }
 377
 378                 /* wvalue will be an odd number < 2^window */
 379                 if (!BN_mod_mul_montgomery(r,r,val[wvalue>>1],mont,ctx))
 380                         goto err;
 381
 382                 /* move the 'window' down further */
 383                 wstart-=wend+1;
 384                 wvalue=0;
 385                 start=0;
 386                 if (wstart < 0) break;
 387                 }
 388         BN_from_montgomery(r,r,mont,ctx);
 389         ret=1;
 390 err:
 391         if (mont != NULL) BN_MONT_CTX_free(mont);
 392         ctx->tos--;
 393         for (i=0; i<16; i++)
 394                 if (val[i] != NULL) BN_clear_free(val[i]);
 395         return(ret);
 396         }
 397 /* #endif */
 398
 399 /* The old fallback, simple version :-) */
 400 int BN_mod_exp_simple(r,a,p,m,ctx)
 401 BIGNUM *r;
 402 BIGNUM *a;
 403 BIGNUM *p;
 404 BIGNUM *m;
 405 BN_CTX *ctx;
 406         {
 407         int i,j,bits,ret=0,wstart,wend,window,wvalue;
 408         int start=1;
 409         BIGNUM *d;
 410         BIGNUM *val[16];
 411
 412         d=ctx->bn[ctx->tos++];
 413         bits=BN_num_bits(p);
 414
 415         if (bits == 0)
 416                 {
 417                 BN_one(r);
 418                 return(1);
 419                 }
 420
 421         val[0]=BN_new();
 422         if (!BN_mod(val[0],a,m,ctx)) goto err;          /* 1 */
 423         if (!BN_mod_mul(d,val[0],val[0],m,ctx))
 424                 goto err;                               /* 2 */
 425
 426         if (bits <= 17) /* This is probably 3 or 0x10001, so just do singles */
 427                 window=1;
 428         else if (bits >= 256)
 429                 window=5;       /* max size of window */
 430         else if (bits >= 128)
 431                 window=4;
 432         else
 433                 window=3;
 434
 435         j=1<<(window-1);
 436         for (i=1; i<j; i++)
 437                 {
 438                 val[i]=BN_new();
 439                 if (!BN_mod_mul(val[i],val[i-1],d,m,ctx))
 440                         goto err;
 441                 }
 442         for (; i<16; i++)
 443                 val[i]=NULL;
 444
 445         start=1;        /* This is used to avoid multiplication etc
 446                          * when there is only the value '1' in the
 447                          * buffer. */
 448         wvalue=0;       /* The 'value' of the window */
 449         wstart=bits-1;  /* The top bit of the window */
 450         wend=0;         /* The bottom bit of the window */
 451
 452         if (!BN_one(r)) goto err;
 453
 454         for (;;)
 455                 {
 456                 if (BN_is_bit_set(p,wstart) == 0)
 457                         {
 458                         if (!start)
 459                                 if (!BN_mod_mul(r,r,r,m,ctx))
 460                                 goto err;
 461                         if (wstart == 0) break;
 462                         wstart--;
 463                         continue;
 464                         }
 465                 /* We now have wstart on a 'set' bit, we now need to work out
 466                  * how bit a window to do.  To do this we need to scan
 467                  * forward until the last set bit before the end of the
 468                  * window */
 469                 j=wstart;
 470                 wvalue=1;
 471                 wend=0;
 472                 for (i=1; i<window; i++)
 473                         {
 474                         if (wstart-i < 0) break;
 475                         if (BN_is_bit_set(p,wstart-i))
 476                                 {
 477                                 wvalue<<=(i-wend);
 478                                 wvalue|=1;
 479                                 wend=i;
 480                                 }
 481                         }
 482
 483                 /* wend is the size of the current window */
 484                 j=wend+1;
 485                 /* add the 'bytes above' */
 486                 if (!start)
 487                         for (i=0; i<j; i++)
 488                                 {
 489                                 if (!BN_mod_mul(r,r,r,m,ctx))
 490                                         goto err;
 491                                 }
 492
 493                 /* wvalue will be an odd number < 2^window */
 494                 if (!BN_mod_mul(r,r,val[wvalue>>1],m,ctx))
 495                         goto err;
 496
 497                 /* move the 'window' down further */
 498                 wstart-=wend+1;
 499                 wvalue=0;
 500                 start=0;
 501                 if (wstart < 0) break;
 502                 }
 503         ret=1;
 504 err:
 505         ctx->tos--;
 506         for (i=0; i<16; i++)
 507                 if (val[i] != NULL) BN_clear_free(val[i]);
 508         return(ret);
 509         }
 510