Home | History | Annotate | Download | only in bn
      1 /* Copyright (C) 1995-1998 Eric Young (eay (at) cryptsoft.com)
      2  * All rights reserved.
      3  *
      4  * This package is an SSL implementation written
      5  * by Eric Young (eay (at) 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 (at) 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 (at) 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 (at) 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 #include <openssl/bn.h>
     58 
     59 #include <limits.h>
     60 #include <openssl/err.h>
     61 
     62 #include "internal.h"
     63 
     64 
     65 #define asm __asm__
     66 
     67 #if !defined(OPENSSL_NO_ASM)
     68 # if defined(__GNUC__) && __GNUC__>=2
     69 #  if defined(OPENSSL_X86)
     70    /*
     71     * There were two reasons for implementing this template:
     72     * - GNU C generates a call to a function (__udivdi3 to be exact)
     73     *   in reply to ((((BN_ULLONG)n0)<<BN_BITS2)|n1)/d0 (I fail to
     74     *   understand why...);
     75     * - divl doesn't only calculate quotient, but also leaves
     76     *   remainder in %edx which we can definitely use here:-)
     77     *
     78     *					<appro (at) fy.chalmers.se>
     79     */
     80 #undef div_asm
     81 #  define div_asm(n0,n1,d0)		\
     82 	({  asm volatile (			\
     83 		"divl	%4"			\
     84 		: "=a"(q), "=d"(rem)		\
     85 		: "a"(n1), "d"(n0), "g"(d0)	\
     86 		: "cc");			\
     87 	    q;					\
     88 	})
     89 #  define REMAINDER_IS_ALREADY_CALCULATED
     90 #  elif defined(OPENSSL_X86_64)
     91    /*
     92     * Same story here, but it's 128-bit by 64-bit division. Wow!
     93     *					<appro (at) fy.chalmers.se>
     94     */
     95 #  undef div_asm
     96 #  define div_asm(n0,n1,d0)		\
     97 	({  asm volatile (			\
     98 		"divq	%4"			\
     99 		: "=a"(q), "=d"(rem)		\
    100 		: "a"(n1), "d"(n0), "g"(d0)	\
    101 		: "cc");			\
    102 	    q;					\
    103 	})
    104 #  define REMAINDER_IS_ALREADY_CALCULATED
    105 #  endif /* __<cpu> */
    106 # endif /* __GNUC__ */
    107 #endif /* OPENSSL_NO_ASM */
    108 
    109 /* BN_div computes  dv := num / divisor,  rounding towards
    110  * zero, and sets up rm  such that  dv*divisor + rm = num  holds.
    111  * Thus:
    112  *     dv->neg == num->neg ^ divisor->neg  (unless the result is zero)
    113  *     rm->neg == num->neg                 (unless the remainder is zero)
    114  * If 'dv' or 'rm' is NULL, the respective value is not returned. */
    115 int BN_div(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor,
    116            BN_CTX *ctx) {
    117   int norm_shift, i, loop;
    118   BIGNUM *tmp, wnum, *snum, *sdiv, *res;
    119   BN_ULONG *resp, *wnump;
    120   BN_ULONG d0, d1;
    121   int num_n, div_n;
    122   int no_branch = 0;
    123 
    124   /* Invalid zero-padding would have particularly bad consequences
    125    * so don't just rely on bn_check_top() here */
    126   if ((num->top > 0 && num->d[num->top - 1] == 0) ||
    127       (divisor->top > 0 && divisor->d[divisor->top - 1] == 0)) {
    128     OPENSSL_PUT_ERROR(BN, BN_R_NOT_INITIALIZED);
    129     return 0;
    130   }
    131 
    132   if ((num->flags & BN_FLG_CONSTTIME) != 0 ||
    133       (divisor->flags & BN_FLG_CONSTTIME) != 0) {
    134     no_branch = 1;
    135   }
    136 
    137   if (BN_is_zero(divisor)) {
    138     OPENSSL_PUT_ERROR(BN, BN_R_DIV_BY_ZERO);
    139     return 0;
    140   }
    141 
    142   if (!no_branch && BN_ucmp(num, divisor) < 0) {
    143     if (rm != NULL) {
    144       if (BN_copy(rm, num) == NULL) {
    145         return 0;
    146       }
    147     }
    148     if (dv != NULL) {
    149       BN_zero(dv);
    150     }
    151     return 1;
    152   }
    153 
    154   BN_CTX_start(ctx);
    155   tmp = BN_CTX_get(ctx);
    156   snum = BN_CTX_get(ctx);
    157   sdiv = BN_CTX_get(ctx);
    158   if (dv == NULL) {
    159     res = BN_CTX_get(ctx);
    160   } else {
    161     res = dv;
    162   }
    163   if (sdiv == NULL || res == NULL || tmp == NULL || snum == NULL) {
    164     goto err;
    165   }
    166 
    167   /* First we normalise the numbers */
    168   norm_shift = BN_BITS2 - ((BN_num_bits(divisor)) % BN_BITS2);
    169   if (!(BN_lshift(sdiv, divisor, norm_shift))) {
    170     goto err;
    171   }
    172   sdiv->neg = 0;
    173   norm_shift += BN_BITS2;
    174   if (!(BN_lshift(snum, num, norm_shift))) {
    175     goto err;
    176   }
    177   snum->neg = 0;
    178 
    179   if (no_branch) {
    180     /* Since we don't know whether snum is larger than sdiv,
    181      * we pad snum with enough zeroes without changing its
    182      * value.
    183      */
    184     if (snum->top <= sdiv->top + 1) {
    185       if (bn_wexpand(snum, sdiv->top + 2) == NULL) {
    186         goto err;
    187       }
    188       for (i = snum->top; i < sdiv->top + 2; i++) {
    189         snum->d[i] = 0;
    190       }
    191       snum->top = sdiv->top + 2;
    192     } else {
    193       if (bn_wexpand(snum, snum->top + 1) == NULL) {
    194         goto err;
    195       }
    196       snum->d[snum->top] = 0;
    197       snum->top++;
    198     }
    199   }
    200 
    201   div_n = sdiv->top;
    202   num_n = snum->top;
    203   loop = num_n - div_n;
    204   /* Lets setup a 'window' into snum
    205    * This is the part that corresponds to the current
    206    * 'area' being divided */
    207   wnum.neg = 0;
    208   wnum.d = &(snum->d[loop]);
    209   wnum.top = div_n;
    210   /* only needed when BN_ucmp messes up the values between top and max */
    211   wnum.dmax = snum->dmax - loop; /* so we don't step out of bounds */
    212 
    213   /* Get the top 2 words of sdiv */
    214   /* div_n=sdiv->top; */
    215   d0 = sdiv->d[div_n - 1];
    216   d1 = (div_n == 1) ? 0 : sdiv->d[div_n - 2];
    217 
    218   /* pointer to the 'top' of snum */
    219   wnump = &(snum->d[num_n - 1]);
    220 
    221   /* Setup to 'res' */
    222   res->neg = (num->neg ^ divisor->neg);
    223   if (!bn_wexpand(res, (loop + 1))) {
    224     goto err;
    225   }
    226   res->top = loop - no_branch;
    227   resp = &(res->d[loop - 1]);
    228 
    229   /* space for temp */
    230   if (!bn_wexpand(tmp, (div_n + 1))) {
    231     goto err;
    232   }
    233 
    234   if (!no_branch) {
    235     if (BN_ucmp(&wnum, sdiv) >= 0) {
    236       bn_sub_words(wnum.d, wnum.d, sdiv->d, div_n);
    237       *resp = 1;
    238     } else {
    239       res->top--;
    240     }
    241   }
    242 
    243   /* if res->top == 0 then clear the neg value otherwise decrease
    244    * the resp pointer */
    245   if (res->top == 0) {
    246     res->neg = 0;
    247   } else {
    248     resp--;
    249   }
    250 
    251   for (i = 0; i < loop - 1; i++, wnump--, resp--) {
    252     BN_ULONG q, l0;
    253     /* the first part of the loop uses the top two words of snum and sdiv to
    254      * calculate a BN_ULONG q such that | wnum - sdiv * q | < sdiv */
    255     BN_ULONG n0, n1, rem = 0;
    256 
    257     n0 = wnump[0];
    258     n1 = wnump[-1];
    259     if (n0 == d0) {
    260       q = BN_MASK2;
    261     } else {
    262       /* n0 < d0 */
    263 #ifdef BN_ULLONG
    264       BN_ULLONG t2;
    265 
    266 #if defined(BN_ULLONG) && !defined(div_asm)
    267       q = (BN_ULONG)(((((BN_ULLONG)n0) << BN_BITS2) | n1) / d0);
    268 #else
    269       q = div_asm(n0, n1, d0);
    270 #endif
    271 
    272 #ifndef REMAINDER_IS_ALREADY_CALCULATED
    273       /* rem doesn't have to be BN_ULLONG. The least we know it's less that d0,
    274        * isn't it? */
    275       rem = (n1 - q * d0) & BN_MASK2;
    276 #endif
    277 
    278       t2 = (BN_ULLONG)d1 * q;
    279 
    280       for (;;) {
    281         if (t2 <= ((((BN_ULLONG)rem) << BN_BITS2) | wnump[-2])) {
    282           break;
    283         }
    284         q--;
    285         rem += d0;
    286         if (rem < d0) {
    287           break; /* don't let rem overflow */
    288         }
    289         t2 -= d1;
    290       }
    291 #else /* !BN_ULLONG */
    292       BN_ULONG t2l, t2h;
    293 
    294 #if defined(div_asm)
    295       q = div_asm(n0, n1, d0);
    296 #else
    297       q = bn_div_words(n0, n1, d0);
    298 #endif
    299 
    300 #ifndef REMAINDER_IS_ALREADY_CALCULATED
    301       rem = (n1 - q * d0) & BN_MASK2;
    302 #endif
    303 
    304 #if defined(BN_UMULT_LOHI)
    305       BN_UMULT_LOHI(t2l, t2h, d1, q);
    306 #elif defined(BN_UMULT_HIGH)
    307       t2l = d1 * q;
    308       t2h = BN_UMULT_HIGH(d1, q);
    309 #else
    310       {
    311         BN_ULONG ql, qh;
    312         t2l = LBITS(d1);
    313         t2h = HBITS(d1);
    314         ql = LBITS(q);
    315         qh = HBITS(q);
    316         mul64(t2l, t2h, ql, qh); /* t2=(BN_ULLONG)d1*q; */
    317       }
    318 #endif
    319 
    320       for (;;) {
    321         if ((t2h < rem) || ((t2h == rem) && (t2l <= wnump[-2]))) {
    322           break;
    323         }
    324         q--;
    325         rem += d0;
    326         if (rem < d0) {
    327           break; /* don't let rem overflow */
    328         }
    329         if (t2l < d1) {
    330           t2h--;
    331         }
    332         t2l -= d1;
    333       }
    334 #endif /* !BN_ULLONG */
    335     }
    336 
    337     l0 = bn_mul_words(tmp->d, sdiv->d, div_n, q);
    338     tmp->d[div_n] = l0;
    339     wnum.d--;
    340     /* ingore top values of the bignums just sub the two
    341      * BN_ULONG arrays with bn_sub_words */
    342     if (bn_sub_words(wnum.d, wnum.d, tmp->d, div_n + 1)) {
    343       /* Note: As we have considered only the leading
    344        * two BN_ULONGs in the calculation of q, sdiv * q
    345        * might be greater than wnum (but then (q-1) * sdiv
    346        * is less or equal than wnum)
    347        */
    348       q--;
    349       if (bn_add_words(wnum.d, wnum.d, sdiv->d, div_n)) {
    350         /* we can't have an overflow here (assuming
    351          * that q != 0, but if q == 0 then tmp is
    352          * zero anyway) */
    353         (*wnump)++;
    354       }
    355     }
    356     /* store part of the result */
    357     *resp = q;
    358   }
    359   bn_correct_top(snum);
    360   if (rm != NULL) {
    361     /* Keep a copy of the neg flag in num because if rm==num
    362      * BN_rshift() will overwrite it.
    363      */
    364     int neg = num->neg;
    365     if (!BN_rshift(rm, snum, norm_shift)) {
    366       goto err;
    367     }
    368     if (!BN_is_zero(rm)) {
    369       rm->neg = neg;
    370     }
    371   }
    372   if (no_branch) {
    373     bn_correct_top(res);
    374   }
    375   BN_CTX_end(ctx);
    376   return 1;
    377 
    378 err:
    379   BN_CTX_end(ctx);
    380   return 0;
    381 }
    382 
    383 int BN_nnmod(BIGNUM *r, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx) {
    384   if (!(BN_mod(r, m, d, ctx))) {
    385     return 0;
    386   }
    387   if (!r->neg) {
    388     return 1;
    389   }
    390 
    391   /* now -|d| < r < 0, so we have to set r := r + |d|. */
    392   return (d->neg ? BN_sub : BN_add)(r, r, d);
    393 }
    394 
    395 int BN_mod_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m,
    396                BN_CTX *ctx) {
    397   if (!BN_add(r, a, b)) {
    398     return 0;
    399   }
    400   return BN_nnmod(r, r, m, ctx);
    401 }
    402 
    403 int BN_mod_add_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
    404                      const BIGNUM *m) {
    405   if (!BN_uadd(r, a, b)) {
    406     return 0;
    407   }
    408   if (BN_ucmp(r, m) >= 0) {
    409     return BN_usub(r, r, m);
    410   }
    411   return 1;
    412 }
    413 
    414 int BN_mod_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m,
    415                BN_CTX *ctx) {
    416   if (!BN_sub(r, a, b)) {
    417     return 0;
    418   }
    419   return BN_nnmod(r, r, m, ctx);
    420 }
    421 
    422 /* BN_mod_sub variant that may be used if both  a  and  b  are non-negative
    423  * and less than  m */
    424 int BN_mod_sub_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
    425                      const BIGNUM *m) {
    426   if (!BN_sub(r, a, b)) {
    427     return 0;
    428   }
    429   if (r->neg) {
    430     return BN_add(r, r, m);
    431   }
    432   return 1;
    433 }
    434 
    435 int BN_mod_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m,
    436                BN_CTX *ctx) {
    437   BIGNUM *t;
    438   int ret = 0;
    439 
    440   BN_CTX_start(ctx);
    441   t = BN_CTX_get(ctx);
    442   if (t == NULL) {
    443     goto err;
    444   }
    445 
    446   if (a == b) {
    447     if (!BN_sqr(t, a, ctx)) {
    448       goto err;
    449     }
    450   } else {
    451     if (!BN_mul(t, a, b, ctx)) {
    452       goto err;
    453     }
    454   }
    455 
    456   if (!BN_nnmod(r, t, m, ctx)) {
    457     goto err;
    458   }
    459 
    460   ret = 1;
    461 
    462 err:
    463   BN_CTX_end(ctx);
    464   return ret;
    465 }
    466 
    467 int BN_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx) {
    468   if (!BN_sqr(r, a, ctx)) {
    469     return 0;
    470   }
    471 
    472   /* r->neg == 0,  thus we don't need BN_nnmod */
    473   return BN_mod(r, r, m, ctx);
    474 }
    475 
    476 int BN_mod_lshift(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m,
    477                   BN_CTX *ctx) {
    478   BIGNUM *abs_m = NULL;
    479   int ret;
    480 
    481   if (!BN_nnmod(r, a, m, ctx)) {
    482     return 0;
    483   }
    484 
    485   if (m->neg) {
    486     abs_m = BN_dup(m);
    487     if (abs_m == NULL) {
    488       return 0;
    489     }
    490     abs_m->neg = 0;
    491   }
    492 
    493   ret = BN_mod_lshift_quick(r, r, n, (abs_m ? abs_m : m));
    494 
    495   BN_free(abs_m);
    496   return ret;
    497 }
    498 
    499 int BN_mod_lshift_quick(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m) {
    500   if (r != a) {
    501     if (BN_copy(r, a) == NULL) {
    502       return 0;
    503     }
    504   }
    505 
    506   while (n > 0) {
    507     int max_shift;
    508 
    509     /* 0 < r < m */
    510     max_shift = BN_num_bits(m) - BN_num_bits(r);
    511     /* max_shift >= 0 */
    512 
    513     if (max_shift < 0) {
    514       OPENSSL_PUT_ERROR(BN, BN_R_INPUT_NOT_REDUCED);
    515       return 0;
    516     }
    517 
    518     if (max_shift > n) {
    519       max_shift = n;
    520     }
    521 
    522     if (max_shift) {
    523       if (!BN_lshift(r, r, max_shift)) {
    524         return 0;
    525       }
    526       n -= max_shift;
    527     } else {
    528       if (!BN_lshift1(r, r)) {
    529         return 0;
    530       }
    531       --n;
    532     }
    533 
    534     /* BN_num_bits(r) <= BN_num_bits(m) */
    535     if (BN_cmp(r, m) >= 0) {
    536       if (!BN_sub(r, r, m)) {
    537         return 0;
    538       }
    539     }
    540   }
    541 
    542   return 1;
    543 }
    544 
    545 int BN_mod_lshift1(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx) {
    546   if (!BN_lshift1(r, a)) {
    547     return 0;
    548   }
    549 
    550   return BN_nnmod(r, r, m, ctx);
    551 }
    552 
    553 int BN_mod_lshift1_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *m) {
    554   if (!BN_lshift1(r, a)) {
    555     return 0;
    556   }
    557   if (BN_cmp(r, m) >= 0) {
    558     return BN_sub(r, r, m);
    559   }
    560 
    561   return 1;
    562 }
    563 
    564 BN_ULONG BN_div_word(BIGNUM *a, BN_ULONG w) {
    565   BN_ULONG ret = 0;
    566   int i, j;
    567 
    568   w &= BN_MASK2;
    569 
    570   if (!w) {
    571     /* actually this an error (division by zero) */
    572     return (BN_ULONG) - 1;
    573   }
    574 
    575   if (a->top == 0) {
    576     return 0;
    577   }
    578 
    579   /* normalize input (so bn_div_words doesn't complain) */
    580   j = BN_BITS2 - BN_num_bits_word(w);
    581   w <<= j;
    582   if (!BN_lshift(a, a, j)) {
    583     return (BN_ULONG) - 1;
    584   }
    585 
    586   for (i = a->top - 1; i >= 0; i--) {
    587     BN_ULONG l, d;
    588 
    589     l = a->d[i];
    590     d = bn_div_words(ret, l, w);
    591     ret = (l - ((d * w) & BN_MASK2)) & BN_MASK2;
    592     a->d[i] = d;
    593   }
    594 
    595   if ((a->top > 0) && (a->d[a->top - 1] == 0)) {
    596     a->top--;
    597   }
    598 
    599   ret >>= j;
    600   return ret;
    601 }
    602 
    603 BN_ULONG BN_mod_word(const BIGNUM *a, BN_ULONG w) {
    604 #ifndef BN_ULLONG
    605   BN_ULONG ret = 0;
    606 #else
    607   BN_ULLONG ret = 0;
    608 #endif
    609   int i;
    610 
    611   if (w == 0) {
    612     return (BN_ULONG) -1;
    613   }
    614 
    615   w &= BN_MASK2;
    616   for (i = a->top - 1; i >= 0; i--) {
    617 #ifndef BN_ULLONG
    618     ret = ((ret << BN_BITS4) | ((a->d[i] >> BN_BITS4) & BN_MASK2l)) % w;
    619     ret = ((ret << BN_BITS4) | (a->d[i] & BN_MASK2l)) % w;
    620 #else
    621     ret = (BN_ULLONG)(((ret << (BN_ULLONG)BN_BITS2) | a->d[i]) % (BN_ULLONG)w);
    622 #endif
    623   }
    624   return (BN_ULONG)ret;
    625 }
    626