crypto/bn/bn_mont.c

   1 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
   2  * All rights reserved.
   3  *
   4  * This package is an SSL implementation written
   5  * by Eric Young (eay@cryptsoft.com).
   6  * The implementation was written so as to conform with Netscapes SSL.
   7  *
   8  * This library is free for commercial and non-commercial use as long as
   9  * the following conditions are aheared to.  The following conditions
  10  * apply to all code found in this distribution, be it the RC4, RSA,
  11  * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
  12  * included with this distribution is covered by the same copyright terms
  13  * except that the holder is Tim Hudson (tjh@cryptsoft.com).
  14  *
  15  * Copyright remains Eric Young's, and as such any Copyright notices in
  16  * the code are not to be removed.
  17  * If this package is used in a product, Eric Young should be given attribution
  18  * as the author of the parts of the library used.
  19  * This can be in the form of a textual message at program startup or
  20  * in documentation (online or textual) provided with the package.
  21  *
  22  * Redistribution and use in source and binary forms, with or without
  23  * modification, are permitted provided that the following conditions
  24  * are met:
  25  * 1. Redistributions of source code must retain the copyright
  26  *    notice, this list of conditions and the following disclaimer.
  27  * 2. Redistributions in binary form must reproduce the above copyright
  28  *    notice, this list of conditions and the following disclaimer in the
  29  *    documentation and/or other materials provided with the distribution.
  30  * 3. All advertising materials mentioning features or use of this software
  31  *    must display the following acknowledgement:
  32  *    "This product includes cryptographic software written by
  33  *     Eric Young (eay@cryptsoft.com)"
  34  *    The word 'cryptographic' can be left out if the rouines from the library
  35  *    being used are not cryptographic related :-).
  36  * 4. If you include any Windows specific code (or a derivative thereof) from
  37  *    the apps directory (application code) you must include an acknowledgement:
  38  *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
  39  *
  40  * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
  41  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  42  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  43  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  44  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  45  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  46  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  47  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  48  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  49  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  50  * SUCH DAMAGE.
  51  *
  52  * The licence and distribution terms for any publically available version or
  53  * derivative of this code cannot be changed.  i.e. this code cannot simply be
  54  * copied and put under another distribution licence
  55  * [including the GNU Public Licence.]
  56  */
  57 /* ====================================================================
  58  * Copyright (c) 1998-2006 The OpenSSL Project.  All rights reserved.
  59  *
  60  * Redistribution and use in source and binary forms, with or without
  61  * modification, are permitted provided that the following conditions
  62  * are met:
  63  *
  64  * 1. Redistributions of source code must retain the above copyright
  65  *    notice, this list of conditions and the following disclaimer.
  66  *
  67  * 2. Redistributions in binary form must reproduce the above copyright
  68  *    notice, this list of conditions and the following disclaimer in
  69  *    the documentation and/or other materials provided with the
  70  *    distribution.
  71  *
  72  * 3. All advertising materials mentioning features or use of this
  73  *    software must display the following acknowledgment:
  74  *    "This product includes software developed by the OpenSSL Project
  75  *    for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
  76  *
  77  * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
  78  *    endorse or promote products derived from this software without
  79  *    prior written permission. For written permission, please contact
  80  *    openssl-core@openssl.org.
  81  *
  82  * 5. Products derived from this software may not be called "OpenSSL"
  83  *    nor may "OpenSSL" appear in their names without prior written
  84  *    permission of the OpenSSL Project.
  85  *
  86  * 6. Redistributions of any form whatsoever must retain the following
  87  *    acknowledgment:
  88  *    "This product includes software developed by the OpenSSL Project
  89  *    for use in the OpenSSL Toolkit (http://www.openssl.org/)"
  90  *
  91  * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
  92  * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  93  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  94  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
  95  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  96  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  97  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  98  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  99  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
 100  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 101  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
 102  * OF THE POSSIBILITY OF SUCH DAMAGE.
 103  * ====================================================================
 104  *
 105  * This product includes cryptographic software written by Eric Young
 106  * (eay@cryptsoft.com).  This product includes software written by Tim
 107  * Hudson (tjh@cryptsoft.com).
 108  *
 109  */
 110
 111 /*
 112  * Details about Montgomery multiplication algorithms can be found at
 113  * http://security.ece.orst.edu/publications.html, e.g.
 114  * http://security.ece.orst.edu/koc/papers/j37acmon.pdf and
 115  * sections 3.8 and 4.2 in http://security.ece.orst.edu/koc/papers/r01rsasw.pdf
 116  */
 117
 118 #include "internal/cryptlib.h"
 119 #include "bn_lcl.h"
 120
 121 #define MONT_WORD               /* use the faster word-based algorithm */
 122
 123 #ifdef MONT_WORD
 124 static int BN_from_montgomery_word(BIGNUM *ret, BIGNUM *r, BN_MONT_CTX *mont);
 125 #endif
 126
 127 int BN_mod_mul_montgomery(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
 128                           BN_MONT_CTX *mont, BN_CTX *ctx)
 129 {
 130     BIGNUM *tmp;
 131     int ret = 0;
 132 #if defined(OPENSSL_BN_ASM_MONT) && defined(MONT_WORD)
 133     int num = mont->N.top;
 134
 135     if (num > 1 && a->top == num && b->top == num) {
 136         if (bn_wexpand(r, num) == NULL)
 137             return (0);
 138         if (bn_mul_mont(r->d, a->d, b->d, mont->N.d, mont->n0, num)) {
 139             r->neg = a->neg ^ b->neg;
 140             r->top = num;
 141             bn_correct_top(r);
 142             return (1);
 143         }
 144     }
 145 #endif
 146
 147     BN_CTX_start(ctx);
 148     tmp = BN_CTX_get(ctx);
 149     if (tmp == NULL)
 150         goto err;
 151
 152     bn_check_top(tmp);
 153     if (a == b) {
 154         if (!BN_sqr(tmp, a, ctx))
 155             goto err;
 156     } else {
 157         if (!BN_mul(tmp, a, b, ctx))
 158             goto err;
 159     }
 160     /* reduce from aRR to aR */
 161 #ifdef MONT_WORD
 162     if (!BN_from_montgomery_word(r, tmp, mont))
 163         goto err;
 164 #else
 165     if (!BN_from_montgomery(r, tmp, mont, ctx))
 166         goto err;
 167 #endif
 168     bn_check_top(r);
 169     ret = 1;
 170  err:
 171     BN_CTX_end(ctx);
 172     return (ret);
 173 }
 174
 175 #ifdef MONT_WORD
 176 static int BN_from_montgomery_word(BIGNUM *ret, BIGNUM *r, BN_MONT_CTX *mont)
 177 {
 178     BIGNUM *n;
 179     BN_ULONG *ap, *np, *rp, n0, v, carry;
 180     int nl, max, i;
 181
 182     n = &(mont->N);
 183     nl = n->top;
 184     if (nl == 0) {
 185         ret->top = 0;
 186         return (1);
 187     }
 188
 189     max = (2 * nl);             /* carry is stored separately */
 190     if (bn_wexpand(r, max) == NULL)
 191         return (0);
 192
 193     r->neg ^= n->neg;
 194     np = n->d;
 195     rp = r->d;
 196
 197     /* clear the top words of T */
 198     i = max - r->top;
 199     if (i)
 200         memset(&rp[r->top], 0, sizeof(*rp) * i);
 201
 202     r->top = max;
 203     n0 = mont->n0[0];
 204
 205     for (carry = 0, i = 0; i < nl; i++, rp++) {
 206         v = bn_mul_add_words(rp, np, nl, (rp[0] * n0) & BN_MASK2);
 207         v = (v + carry + rp[nl]) & BN_MASK2;
 208         carry |= (v != rp[nl]);
 209         carry &= (v <= rp[nl]);
 210         rp[nl] = v;
 211     }
 212
 213     if (bn_wexpand(ret, nl) == NULL)
 214         return (0);
 215     ret->top = nl;
 216     ret->neg = r->neg;
 217
 218     rp = ret->d;
 219     ap = &(r->d[nl]);
 220
 221 # define BRANCH_FREE 1
 222 # if BRANCH_FREE
 223     {
 224         BN_ULONG *nrp;
 225         size_t m;
 226
 227         v = bn_sub_words(rp, ap, np, nl) - carry;
 228         /*
 229          * if subtraction result is real, then trick unconditional memcpy
 230          * below to perform in-place "refresh" instead of actual copy.
 231          */
 232         m = (0 - (size_t)v);
 233         nrp =
 234             (BN_ULONG *)(((PTR_SIZE_INT) rp & ~m) | ((PTR_SIZE_INT) ap & m));
 235
 236         for (i = 0, nl -= 4; i < nl; i += 4) {
 237             BN_ULONG t1, t2, t3, t4;
 238
 239             t1 = nrp[i + 0];
 240             t2 = nrp[i + 1];
 241             t3 = nrp[i + 2];
 242             ap[i + 0] = 0;
 243             t4 = nrp[i + 3];
 244             ap[i + 1] = 0;
 245             rp[i + 0] = t1;
 246             ap[i + 2] = 0;
 247             rp[i + 1] = t2;
 248             ap[i + 3] = 0;
 249             rp[i + 2] = t3;
 250             rp[i + 3] = t4;
 251         }
 252         for (nl += 4; i < nl; i++)
 253             rp[i] = nrp[i], ap[i] = 0;
 254     }
 255 # else
 256     if (bn_sub_words(rp, ap, np, nl) - carry)
 257         memcpy(rp, ap, nl * sizeof(BN_ULONG));
 258 # endif
 259     bn_correct_top(r);
 260     bn_correct_top(ret);
 261     bn_check_top(ret);
 262
 263     return (1);
 264 }
 265 #endif                          /* MONT_WORD */
 266
 267 int BN_from_montgomery(BIGNUM *ret, const BIGNUM *a, BN_MONT_CTX *mont,
 268                        BN_CTX *ctx)
 269 {
 270     int retn = 0;
 271 #ifdef MONT_WORD
 272     BIGNUM *t;
 273
 274     BN_CTX_start(ctx);
 275     if ((t = BN_CTX_get(ctx)) && BN_copy(t, a))
 276         retn = BN_from_montgomery_word(ret, t, mont);
 277     BN_CTX_end(ctx);
 278 #else                           /* !MONT_WORD */
 279     BIGNUM *t1, *t2;
 280
 281     BN_CTX_start(ctx);
 282     t1 = BN_CTX_get(ctx);
 283     t2 = BN_CTX_get(ctx);
 284     if (t1 == NULL || t2 == NULL)
 285         goto err;
 286
 287     if (!BN_copy(t1, a))
 288         goto err;
 289     BN_mask_bits(t1, mont->ri);
 290
 291     if (!BN_mul(t2, t1, &mont->Ni, ctx))
 292         goto err;
 293     BN_mask_bits(t2, mont->ri);
 294
 295     if (!BN_mul(t1, t2, &mont->N, ctx))
 296         goto err;
 297     if (!BN_add(t2, a, t1))
 298         goto err;
 299     if (!BN_rshift(ret, t2, mont->ri))
 300         goto err;
 301
 302     if (BN_ucmp(ret, &(mont->N)) >= 0) {
 303         if (!BN_usub(ret, ret, &(mont->N)))
 304             goto err;
 305     }
 306     retn = 1;
 307     bn_check_top(ret);
 308  err:
 309     BN_CTX_end(ctx);
 310 #endif                          /* MONT_WORD */
 311     return (retn);
 312 }
 313
 314 BN_MONT_CTX *BN_MONT_CTX_new(void)
 315 {
 316     BN_MONT_CTX *ret;
 317
 318     if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL)
 319         return (NULL);
 320
 321     BN_MONT_CTX_init(ret);
 322     ret->flags = BN_FLG_MALLOCED;
 323     return (ret);
 324 }
 325
 326 void BN_MONT_CTX_init(BN_MONT_CTX *ctx)
 327 {
 328     ctx->ri = 0;
 329     bn_init(&(ctx->RR));
 330     bn_init(&(ctx->N));
 331     bn_init(&(ctx->Ni));
 332     ctx->n0[0] = ctx->n0[1] = 0;
 333     ctx->flags = 0;
 334 }
 335
 336 void BN_MONT_CTX_free(BN_MONT_CTX *mont)
 337 {
 338     if (mont == NULL)
 339         return;
 340
 341     BN_clear_free(&(mont->RR));
 342     BN_clear_free(&(mont->N));
 343     BN_clear_free(&(mont->Ni));
 344     if (mont->flags & BN_FLG_MALLOCED)
 345         OPENSSL_free(mont);
 346 }
 347
 348 int BN_MONT_CTX_set(BN_MONT_CTX *mont, const BIGNUM *mod, BN_CTX *ctx)
 349 {
 350     int ret = 0;
 351     BIGNUM *Ri, *R;
 352
 353     if (BN_is_zero(mod))
 354         return 0;
 355
 356     BN_CTX_start(ctx);
 357     if ((Ri = BN_CTX_get(ctx)) == NULL)
 358         goto err;
 359     R = &(mont->RR);            /* grab RR as a temp */
 360     if (!BN_copy(&(mont->N), mod))
 361         goto err;               /* Set N */
 362     mont->N.neg = 0;
 363
 364 #ifdef MONT_WORD
 365     {
 366         BIGNUM tmod;
 367         BN_ULONG buf[2];
 368
 369         bn_init(&tmod);
 370         tmod.d = buf;
 371         tmod.dmax = 2;
 372         tmod.neg = 0;
 373
 374         mont->ri = (BN_num_bits(mod) + (BN_BITS2 - 1)) / BN_BITS2 * BN_BITS2;
 375
 376 # if defined(OPENSSL_BN_ASM_MONT) && (BN_BITS2<=32)
 377         /*
 378          * Only certain BN_BITS2<=32 platforms actually make use of n0[1],
 379          * and we could use the #else case (with a shorter R value) for the
 380          * others.  However, currently only the assembler files do know which
 381          * is which.
 382          */
 383
 384         BN_zero(R);
 385         if (!(BN_set_bit(R, 2 * BN_BITS2)))
 386             goto err;
 387
 388         tmod.top = 0;
 389         if ((buf[0] = mod->d[0]))
 390             tmod.top = 1;
 391         if ((buf[1] = mod->top > 1 ? mod->d[1] : 0))
 392             tmod.top = 2;
 393
 394         if ((BN_mod_inverse(Ri, R, &tmod, ctx)) == NULL)
 395             goto err;
 396         if (!BN_lshift(Ri, Ri, 2 * BN_BITS2))
 397             goto err;           /* R*Ri */
 398         if (!BN_is_zero(Ri)) {
 399             if (!BN_sub_word(Ri, 1))
 400                 goto err;
 401         } else {                /* if N mod word size == 1 */
 402
 403             if (bn_expand(Ri, (int)sizeof(BN_ULONG) * 2) == NULL)
 404                 goto err;
 405             /* Ri-- (mod double word size) */
 406             Ri->neg = 0;
 407             Ri->d[0] = BN_MASK2;
 408             Ri->d[1] = BN_MASK2;
 409             Ri->top = 2;
 410         }
 411         if (!BN_div(Ri, NULL, Ri, &tmod, ctx))
 412             goto err;
 413         /*
 414          * Ni = (R*Ri-1)/N, keep only couple of least significant words:
 415          */
 416         mont->n0[0] = (Ri->top > 0) ? Ri->d[0] : 0;
 417         mont->n0[1] = (Ri->top > 1) ? Ri->d[1] : 0;
 418 # else
 419         BN_zero(R);
 420         if (!(BN_set_bit(R, BN_BITS2)))
 421             goto err;           /* R */
 422
 423         buf[0] = mod->d[0];     /* tmod = N mod word size */
 424         buf[1] = 0;
 425         tmod.top = buf[0] != 0 ? 1 : 0;
 426         /* Ri = R^-1 mod N */
 427         if ((BN_mod_inverse(Ri, R, &tmod, ctx)) == NULL)
 428             goto err;
 429         if (!BN_lshift(Ri, Ri, BN_BITS2))
 430             goto err;           /* R*Ri */
 431         if (!BN_is_zero(Ri)) {
 432             if (!BN_sub_word(Ri, 1))
 433                 goto err;
 434         } else {                /* if N mod word size == 1 */
 435
 436             if (!BN_set_word(Ri, BN_MASK2))
 437                 goto err;       /* Ri-- (mod word size) */
 438         }
 439         if (!BN_div(Ri, NULL, Ri, &tmod, ctx))
 440             goto err;
 441         /*
 442          * Ni = (R*Ri-1)/N, keep only least significant word:
 443          */
 444         mont->n0[0] = (Ri->top > 0) ? Ri->d[0] : 0;
 445         mont->n0[1] = 0;
 446 # endif
 447     }
 448 #else                           /* !MONT_WORD */
 449     {                           /* bignum version */
 450         mont->ri = BN_num_bits(&mont->N);
 451         BN_zero(R);
 452         if (!BN_set_bit(R, mont->ri))
 453             goto err;           /* R = 2^ri */
 454         /* Ri = R^-1 mod N */
 455         if ((BN_mod_inverse(Ri, R, &mont->N, ctx)) == NULL)
 456             goto err;
 457         if (!BN_lshift(Ri, Ri, mont->ri))
 458             goto err;           /* R*Ri */
 459         if (!BN_sub_word(Ri, 1))
 460             goto err;
 461         /*
 462          * Ni = (R*Ri-1) / N
 463          */
 464         if (!BN_div(&(mont->Ni), NULL, Ri, &mont->N, ctx))
 465             goto err;
 466     }
 467 #endif
 468
 469     /* setup RR for conversions */
 470     BN_zero(&(mont->RR));
 471     if (!BN_set_bit(&(mont->RR), mont->ri * 2))
 472         goto err;
 473     if (!BN_mod(&(mont->RR), &(mont->RR), &(mont->N), ctx))
 474         goto err;
 475
 476     ret = 1;
 477  err:
 478     BN_CTX_end(ctx);
 479     return ret;
 480 }
 481
 482 BN_MONT_CTX *BN_MONT_CTX_copy(BN_MONT_CTX *to, BN_MONT_CTX *from)
 483 {
 484     if (to == from)
 485         return (to);
 486
 487     if (!BN_copy(&(to->RR), &(from->RR)))
 488         return NULL;
 489     if (!BN_copy(&(to->N), &(from->N)))
 490         return NULL;
 491     if (!BN_copy(&(to->Ni), &(from->Ni)))
 492         return NULL;
 493     to->ri = from->ri;
 494     to->n0[0] = from->n0[0];
 495     to->n0[1] = from->n0[1];
 496     return (to);
 497 }
 498
 499 BN_MONT_CTX *BN_MONT_CTX_set_locked(BN_MONT_CTX **pmont, int lock,
 500                                     const BIGNUM *mod, BN_CTX *ctx)
 501 {
 502     BN_MONT_CTX *ret;
 503
 504     CRYPTO_r_lock(lock);
 505     ret = *pmont;
 506     CRYPTO_r_unlock(lock);
 507     if (ret)
 508         return ret;
 509
 510     /*
 511      * We don't want to serialise globally while doing our lazy-init math in
 512      * BN_MONT_CTX_set. That punishes threads that are doing independent
 513      * things. Instead, punish the case where more than one thread tries to
 514      * lazy-init the same 'pmont', by having each do the lazy-init math work
 515      * independently and only use the one from the thread that wins the race
 516      * (the losers throw away the work they've done).
 517      */
 518     ret = BN_MONT_CTX_new();
 519     if (ret == NULL)
 520         return NULL;
 521     if (!BN_MONT_CTX_set(ret, mod, ctx)) {
 522         BN_MONT_CTX_free(ret);
 523         return NULL;
 524     }
 525
 526     /* The locked compare-and-set, after the local work is done. */
 527     CRYPTO_w_lock(lock);
 528     if (*pmont) {
 529         BN_MONT_CTX_free(ret);
 530         ret = *pmont;
 531     } else
 532         *pmont = ret;
 533     CRYPTO_w_unlock(lock);
 534     return ret;
 535 }