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