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 #define TABLE_SIZE      16
  64
  65 /* slow but works */
  66 int BN_mod_mul(BIGNUM *ret, BIGNUM *a, BIGNUM *b, const BIGNUM *m, BN_CTX *ctx)
  67         {
  68         BIGNUM *t;
  69         int r=0;
  70
  71         bn_check_top(a);
  72         bn_check_top(b);
  73         bn_check_top(m);
  74
  75         t= &(ctx->bn[ctx->tos++]);
  76         if (a == b)
  77                 { if (!BN_sqr(t,a,ctx)) goto err; }
  78         else
  79                 { if (!BN_mul(t,a,b,ctx)) goto err; }
  80         if (!BN_mod(ret,t,m,ctx)) goto err;
  81         r=1;
  82 err:
  83         ctx->tos--;
  84         return(r);
  85         }
  86
  87 #if 0
  88 /* this one works - simple but works */
  89 int BN_mod_exp(BIGNUM *r, BIGNUM *a, BIGNUM *p, BIGNUM *m, BN_CTX *ctx)
  90         {
  91         int i,bits,ret=0;
  92         BIGNUM *v,*tmp;
  93
  94         v= &(ctx->bn[ctx->tos++]);
  95         tmp= &(ctx->bn[ctx->tos++]);
  96
  97         if (BN_copy(v,a) == NULL) goto err;
  98         bits=BN_num_bits(p);
  99
 100         if (BN_is_odd(p))
 101                 { if (BN_copy(r,a) == NULL) goto err; }
 102         else    { if (!BN_one(r)) goto err; }
 103
 104         for (i=1; i<bits; i++)
 105                 {
 106                 if (!BN_sqr(tmp,v,ctx)) goto err;
 107                 if (!BN_mod(v,tmp,m,ctx)) goto err;
 108                 if (BN_is_bit_set(p,i))
 109                         {
 110                         if (!BN_mul(tmp,r,v,ctx)) goto err;
 111                         if (!BN_mod(r,tmp,m,ctx)) goto err;
 112                         }
 113                 }
 114         ret=1;
 115 err:
 116         ctx->tos-=2;
 117         return(ret);
 118         }
 119
 120 #endif
 121
 122 /* this one works - simple but works */
 123 int BN_exp(BIGNUM *r, BIGNUM *a, BIGNUM *p, BN_CTX *ctx)
 124         {
 125         int i,bits,ret=0,tos;
 126         BIGNUM *v,*rr;
 127
 128         tos=ctx->tos;
 129         v= &(ctx->bn[ctx->tos++]);
 130         if ((r == a) || (r == p))
 131                 rr= &(ctx->bn[ctx->tos++]);
 132         else
 133                 rr=r;
 134
 135         if (BN_copy(v,a) == NULL) goto err;
 136         bits=BN_num_bits(p);
 137
 138         if (BN_is_odd(p))
 139                 { if (BN_copy(rr,a) == NULL) goto err; }
 140         else    { if (!BN_one(rr)) goto err; }
 141
 142         for (i=1; i<bits; i++)
 143                 {
 144                 if (!BN_sqr(v,v,ctx)) goto err;
 145                 if (BN_is_bit_set(p,i))
 146                         {
 147                         if (!BN_mul(rr,rr,v,ctx)) goto err;
 148                         }
 149                 }
 150         ret=1;
 151 err:
 152         ctx->tos=tos;
 153         if (r != rr) BN_copy(r,rr);
 154         return(ret);
 155         }
 156
 157 int BN_mod_exp(BIGNUM *r, BIGNUM *a, const BIGNUM *p, const BIGNUM *m,
 158                BN_CTX *ctx)
 159         {
 160         int ret;
 161
 162         bn_check_top(a);
 163         bn_check_top(p);
 164         bn_check_top(m);
 165
 166 #ifdef MONT_MUL_MOD
 167         /* I have finally been able to take out this pre-condition of
 168          * the top bit being set.  It was caused by an error in BN_div
 169          * with negatives.  There was also another problem when for a^b%m
 170          * a >= m.  eay 07-May-97 */
 171 /*      if ((m->d[m->top-1]&BN_TBIT) && BN_is_odd(m)) */
 172
 173         if (BN_is_odd(m))
 174                 { ret=BN_mod_exp_mont(r,a,p,m,ctx,NULL); }
 175         else
 176 #endif
 177 #ifdef RECP_MUL_MOD
 178                 { ret=BN_mod_exp_recp(r,a,p,m,ctx); }
 179 #else
 180                 { ret=BN_mod_exp_simple(r,a,p,m,ctx); }
 181 #endif
 182
 183         return(ret);
 184         }
 185
 186 /* #ifdef RECP_MUL_MOD */
 187 int BN_mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p,
 188                     const BIGNUM *m, BN_CTX *ctx)
 189         {
 190         int i,j,bits,ret=0,wstart,wend,window,wvalue;
 191         int start=1,ts=0;
 192         BIGNUM *aa;
 193         BIGNUM val[TABLE_SIZE];
 194         BN_RECP_CTX recp;
 195
 196         aa= &(ctx->bn[ctx->tos++]);
 197         bits=BN_num_bits(p);
 198
 199         if (bits == 0)
 200                 {
 201                 BN_one(r);
 202                 return(1);
 203                 }
 204         BN_RECP_CTX_init(&recp);
 205         if (BN_RECP_CTX_set(&recp,m,ctx) <= 0) goto err;
 206
 207         BN_init(&(val[0]));
 208         ts=1;
 209
 210         if (!BN_mod(&(val[0]),a,m,ctx)) goto err;               /* 1 */
 211         if (!BN_mod_mul_reciprocal(aa,&(val[0]),&(val[0]),&recp,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                 BN_init(&val[i]);
 227                 if (!BN_mod_mul_reciprocal(&(val[i]),&(val[i-1]),aa,&recp,ctx))
 228                         goto err;
 229                 }
 230         ts=i;
 231
 232         start=1;        /* This is used to avoid multiplication etc
 233                          * when there is only the value '1' in the
 234                          * buffer. */
 235         wvalue=0;       /* The 'value' of the window */
 236         wstart=bits-1;  /* The top bit of the window */
 237         wend=0;         /* The bottom bit of the window */
 238
 239         if (!BN_one(r)) goto err;
 240
 241         for (;;)
 242                 {
 243                 if (BN_is_bit_set(p,wstart) == 0)
 244                         {
 245                         if (!start)
 246                                 if (!BN_mod_mul_reciprocal(r,r,r,&recp,ctx))
 247                                 goto err;
 248                         if (wstart == 0) break;
 249                         wstart--;
 250                         continue;
 251                         }
 252                 /* We now have wstart on a 'set' bit, we now need to work out
 253                  * how bit a window to do.  To do this we need to scan
 254                  * forward until the last set bit before the end of the
 255                  * window */
 256                 j=wstart;
 257                 wvalue=1;
 258                 wend=0;
 259                 for (i=1; i<window; i++)
 260                         {
 261                         if (wstart-i < 0) break;
 262                         if (BN_is_bit_set(p,wstart-i))
 263                                 {
 264                                 wvalue<<=(i-wend);
 265                                 wvalue|=1;
 266                                 wend=i;
 267                                 }
 268                         }
 269
 270                 /* wend is the size of the current window */
 271                 j=wend+1;
 272                 /* add the 'bytes above' */
 273                 if (!start)
 274                         for (i=0; i<j; i++)
 275                                 {
 276                                 if (!BN_mod_mul_reciprocal(r,r,r,&recp,ctx))
 277                                         goto err;
 278                                 }
 279
 280                 /* wvalue will be an odd number < 2^window */
 281                 if (!BN_mod_mul_reciprocal(r,r,&(val[wvalue>>1]),&recp,ctx))
 282                         goto err;
 283
 284                 /* move the 'window' down further */
 285                 wstart-=wend+1;
 286                 wvalue=0;
 287                 start=0;
 288                 if (wstart < 0) break;
 289                 }
 290         ret=1;
 291 err:
 292         ctx->tos--;
 293         for (i=0; i<ts; i++)
 294                 BN_clear_free(&(val[i]));
 295         BN_RECP_CTX_free(&recp);
 296         return(ret);
 297         }
 298 /* #endif */
 299
 300 /* #ifdef MONT_MUL_MOD */
 301 int BN_mod_exp_mont(BIGNUM *rr, BIGNUM *a, const BIGNUM *p,
 302                     const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont)
 303         {
 304         int i,j,bits,ret=0,wstart,wend,window,wvalue;
 305         int start=1,ts=0;
 306         BIGNUM *d,*r;
 307         BIGNUM *aa;
 308         BIGNUM val[TABLE_SIZE];
 309         BN_MONT_CTX *mont=NULL;
 310
 311         bn_check_top(a);
 312         bn_check_top(p);
 313         bn_check_top(m);
 314
 315         if (!(m->d[0] & 1))
 316                 {
 317                 BNerr(BN_F_BN_MOD_EXP_MONT,BN_R_CALLED_WITH_EVEN_MODULUS);
 318                 return(0);
 319                 }
 320         d= &(ctx->bn[ctx->tos++]);
 321         r= &(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         BN_init(&val[0]);
 343         ts=1;
 344         if (BN_ucmp(a,m) >= 0)
 345                 {
 346                 BN_mod(&(val[0]),a,m,ctx);
 347                 aa= &(val[0]);
 348                 }
 349         else
 350                 aa=a;
 351         if (!BN_to_montgomery(&(val[0]),aa,mont,ctx)) goto err; /* 1 */
 352         if (!BN_mod_mul_montgomery(d,&(val[0]),&(val[0]),mont,ctx)) goto err; /* 2 */
 353
 354         if (bits <= 20) /* This is probably 3 or 0x10001, so just do singles */
 355                 window=1;
 356         else if (bits >= 256)
 357                 window=5;       /* max size of window */
 358         else if (bits >= 128)
 359                 window=4;
 360         else
 361                 window=3;
 362
 363         j=1<<(window-1);
 364         for (i=1; i<j; i++)
 365                 {
 366                 BN_init(&(val[i]));
 367                 if (!BN_mod_mul_montgomery(&(val[i]),&(val[i-1]),d,mont,ctx))
 368                         goto err;
 369                 }
 370         ts=i;
 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(rr,r,mont,ctx);
 432         ret=1;
 433 err:
 434         if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont);
 435         ctx->tos-=2;
 436         for (i=0; i<ts; i++)
 437                 BN_clear_free(&(val[i]));
 438         return(ret);
 439         }
 440 /* #endif */
 441
 442 /* The old fallback, simple version :-) */
 443 int BN_mod_exp_simple(BIGNUM *r, BIGNUM *a, BIGNUM *p, BIGNUM *m,
 444              BN_CTX *ctx)
 445         {
 446         int i,j,bits,ret=0,wstart,wend,window,wvalue,ts=0;
 447         int start=1;
 448         BIGNUM *d;
 449         BIGNUM val[TABLE_SIZE];
 450
 451         d= &(ctx->bn[ctx->tos++]);
 452         bits=BN_num_bits(p);
 453
 454         if (bits == 0)
 455                 {
 456                 BN_one(r);
 457                 return(1);
 458                 }
 459
 460         BN_init(&(val[0]));
 461         ts=1;
 462         if (!BN_mod(&(val[0]),a,m,ctx)) goto err;               /* 1 */
 463         if (!BN_mod_mul(d,&(val[0]),&(val[0]),m,ctx))
 464                 goto err;                               /* 2 */
 465
 466         if (bits <= 17) /* This is probably 3 or 0x10001, so just do singles */
 467                 window=1;
 468         else if (bits >= 256)
 469                 window=5;       /* max size of window */
 470         else if (bits >= 128)
 471                 window=4;
 472         else
 473                 window=3;
 474
 475         j=1<<(window-1);
 476         for (i=1; i<j; i++)
 477                 {
 478                 BN_init(&(val[i]));
 479                 if (!BN_mod_mul(&(val[i]),&(val[i-1]),d,m,ctx))
 480                         goto err;
 481                 }
 482         ts=i;
 483
 484         start=1;        /* This is used to avoid multiplication etc
 485                          * when there is only the value '1' in the
 486                          * buffer. */
 487         wvalue=0;       /* The 'value' of the window */
 488         wstart=bits-1;  /* The top bit of the window */
 489         wend=0;         /* The bottom bit of the window */
 490
 491         if (!BN_one(r)) goto err;
 492
 493         for (;;)
 494                 {
 495                 if (BN_is_bit_set(p,wstart) == 0)
 496                         {
 497                         if (!start)
 498                                 if (!BN_mod_mul(r,r,r,m,ctx))
 499                                 goto err;
 500                         if (wstart == 0) break;
 501                         wstart--;
 502                         continue;
 503                         }
 504                 /* We now have wstart on a 'set' bit, we now need to work out
 505                  * how bit a window to do.  To do this we need to scan
 506                  * forward until the last set bit before the end of the
 507                  * window */
 508                 j=wstart;
 509                 wvalue=1;
 510                 wend=0;
 511                 for (i=1; i<window; i++)
 512                         {
 513                         if (wstart-i < 0) break;
 514                         if (BN_is_bit_set(p,wstart-i))
 515                                 {
 516                                 wvalue<<=(i-wend);
 517                                 wvalue|=1;
 518                                 wend=i;
 519                                 }
 520                         }
 521
 522                 /* wend is the size of the current window */
 523                 j=wend+1;
 524                 /* add the 'bytes above' */
 525                 if (!start)
 526                         for (i=0; i<j; i++)
 527                                 {
 528                                 if (!BN_mod_mul(r,r,r,m,ctx))
 529                                         goto err;
 530                                 }
 531
 532                 /* wvalue will be an odd number < 2^window */
 533                 if (!BN_mod_mul(r,r,&(val[wvalue>>1]),m,ctx))
 534                         goto err;
 535
 536                 /* move the 'window' down further */
 537                 wstart-=wend+1;
 538                 wvalue=0;
 539                 start=0;
 540                 if (wstart < 0) break;
 541                 }
 542         ret=1;
 543 err:
 544         ctx->tos--;
 545         for (i=0; i<ts; i++)
 546                 BN_clear_free(&(val[i]));
 547         return(ret);
 548         }
 549