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