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