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