crypto/bn/bn_mod.c

   1 /*
   2  * Copyright 1998-2016 The OpenSSL Project Authors. All Rights Reserved.
   3  *
   4  * Licensed under the OpenSSL license (the "License").  You may not use
   5  * this file except in compliance with the License.  You can obtain a copy
   6  * in the file LICENSE in the source distribution or at
   7  * https://www.openssl.org/source/license.html
   8  */
   9
  10 #include "internal/cryptlib.h"
  11 #include "bn_lcl.h"
  12
  13 int BN_nnmod(BIGNUM *r, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx)
  14 {
  15     /*
  16      * like BN_mod, but returns non-negative remainder (i.e., 0 <= r < |d|
  17      * always holds)
  18      */
  19
  20     if (!(BN_mod(r, m, d, ctx)))
  21         return 0;
  22     if (!r->neg)
  23         return 1;
  24     /* now   -|d| < r < 0,  so we have to set  r := r + |d| */
  25     return (d->neg ? BN_sub : BN_add) (r, r, d);
  26 }
  27
  28 int BN_mod_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m,
  29                BN_CTX *ctx)
  30 {
  31     if (!BN_add(r, a, b))
  32         return 0;
  33     return BN_nnmod(r, r, m, ctx);
  34 }
  35
  36 /*
  37  * BN_mod_add variant that may be used if both a and b are non-negative and
  38  * less than m. The original algorithm was
  39  *
  40  *    if (!BN_uadd(r, a, b))
  41  *       return 0;
  42  *    if (BN_ucmp(r, m) >= 0)
  43  *       return BN_usub(r, r, m);
  44  *
  45  * which is replaced with addition, subtracting modulus, and conditional
  46  * move depending on whether or not subtraction borrowed.
  47  */
  48 int bn_mod_add_fixed_top(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
  49                          const BIGNUM *m)
  50 {
  51     size_t i, ai, bi, mtop = m->top;
  52     BN_ULONG storage[1024 / BN_BITS2];
  53     BN_ULONG carry, temp, mask, *rp, *tp = storage;
  54     const BN_ULONG *ap, *bp;
  55
  56     if (bn_wexpand(r, mtop) == NULL)
  57         return 0;
  58
  59     if (mtop > sizeof(storage) / sizeof(storage[0])
  60         && (tp = OPENSSL_malloc(mtop * sizeof(BN_ULONG))) == NULL)
  61         return 0;
  62
  63     ap = a->d != NULL ? a->d : tp;
  64     bp = b->d != NULL ? b->d : tp;
  65
  66     for (i = 0, ai = 0, bi = 0, carry = 0; i < mtop;) {
  67         mask = (BN_ULONG)0 - ((i - a->top) >> (8 * sizeof(i) - 1));
  68         temp = ((ap[ai] & mask) + carry) & BN_MASK2;
  69         carry = (temp < carry);
  70
  71         mask = (BN_ULONG)0 - ((i - b->top) >> (8 * sizeof(i) - 1));
  72         tp[i] = ((bp[bi] & mask) + temp) & BN_MASK2;
  73         carry += (tp[i] < temp);
  74
  75         i++;
  76         ai += (i - a->dmax) >> (8 * sizeof(i) - 1);
  77         bi += (i - b->dmax) >> (8 * sizeof(i) - 1);
  78     }
  79     rp = r->d;
  80     carry -= bn_sub_words(rp, tp, m->d, mtop);
  81     for (i = 0; i < mtop; i++) {
  82         rp[i] = (carry & tp[i]) | (~carry & rp[i]);
  83         ((volatile BN_ULONG *)tp)[i] = 0;
  84     }
  85     r->top = mtop;
  86     r->neg = 0;
  87
  88     if (tp != storage)
  89         OPENSSL_free(tp);
  90
  91     return 1;
  92 }
  93
  94 int BN_mod_add_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
  95                      const BIGNUM *m)
  96 {
  97     int ret = bn_mod_add_fixed_top(r, a, b, m);
  98
  99     if (ret)
 100         bn_correct_top(r);
 101
 102     return ret;
 103 }
 104
 105 int BN_mod_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m,
 106                BN_CTX *ctx)
 107 {
 108     if (!BN_sub(r, a, b))
 109         return 0;
 110     return BN_nnmod(r, r, m, ctx);
 111 }
 112
 113 /*
 114  * BN_mod_sub variant that may be used if both a and b are non-negative and
 115  * less than m
 116  */
 117 int BN_mod_sub_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
 118                      const BIGNUM *m)
 119 {
 120     if (!BN_sub(r, a, b))
 121         return 0;
 122     if (r->neg)
 123         return BN_add(r, r, m);
 124     return 1;
 125 }
 126
 127 /* slow but works */
 128 int BN_mod_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m,
 129                BN_CTX *ctx)
 130 {
 131     BIGNUM *t;
 132     int ret = 0;
 133
 134     bn_check_top(a);
 135     bn_check_top(b);
 136     bn_check_top(m);
 137
 138     BN_CTX_start(ctx);
 139     if ((t = BN_CTX_get(ctx)) == NULL)
 140         goto err;
 141     if (a == b) {
 142         if (!BN_sqr(t, a, ctx))
 143             goto err;
 144     } else {
 145         if (!BN_mul(t, a, b, ctx))
 146             goto err;
 147     }
 148     if (!BN_nnmod(r, t, m, ctx))
 149         goto err;
 150     bn_check_top(r);
 151     ret = 1;
 152  err:
 153     BN_CTX_end(ctx);
 154     return ret;
 155 }
 156
 157 int BN_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx)
 158 {
 159     if (!BN_sqr(r, a, ctx))
 160         return 0;
 161     /* r->neg == 0,  thus we don't need BN_nnmod */
 162     return BN_mod(r, r, m, ctx);
 163 }
 164
 165 int BN_mod_lshift1(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx)
 166 {
 167     if (!BN_lshift1(r, a))
 168         return 0;
 169     bn_check_top(r);
 170     return BN_nnmod(r, r, m, ctx);
 171 }
 172
 173 /*
 174  * BN_mod_lshift1 variant that may be used if a is non-negative and less than
 175  * m
 176  */
 177 int BN_mod_lshift1_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *m)
 178 {
 179     if (!BN_lshift1(r, a))
 180         return 0;
 181     bn_check_top(r);
 182     if (BN_cmp(r, m) >= 0)
 183         return BN_sub(r, r, m);
 184     return 1;
 185 }
 186
 187 int BN_mod_lshift(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m,
 188                   BN_CTX *ctx)
 189 {
 190     BIGNUM *abs_m = NULL;
 191     int ret;
 192
 193     if (!BN_nnmod(r, a, m, ctx))
 194         return 0;
 195
 196     if (m->neg) {
 197         abs_m = BN_dup(m);
 198         if (abs_m == NULL)
 199             return 0;
 200         abs_m->neg = 0;
 201     }
 202
 203     ret = BN_mod_lshift_quick(r, r, n, (abs_m ? abs_m : m));
 204     bn_check_top(r);
 205
 206     BN_free(abs_m);
 207     return ret;
 208 }
 209
 210 /*
 211  * BN_mod_lshift variant that may be used if a is non-negative and less than
 212  * m
 213  */
 214 int BN_mod_lshift_quick(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m)
 215 {
 216     if (r != a) {
 217         if (BN_copy(r, a) == NULL)
 218             return 0;
 219     }
 220
 221     while (n > 0) {
 222         int max_shift;
 223
 224         /* 0 < r < m */
 225         max_shift = BN_num_bits(m) - BN_num_bits(r);
 226         /* max_shift >= 0 */
 227
 228         if (max_shift < 0) {
 229             BNerr(BN_F_BN_MOD_LSHIFT_QUICK, BN_R_INPUT_NOT_REDUCED);
 230             return 0;
 231         }
 232
 233         if (max_shift > n)
 234             max_shift = n;
 235
 236         if (max_shift) {
 237             if (!BN_lshift(r, r, max_shift))
 238                 return 0;
 239             n -= max_shift;
 240         } else {
 241             if (!BN_lshift1(r, r))
 242                 return 0;
 243             --n;
 244         }
 245
 246         /* BN_num_bits(r) <= BN_num_bits(m) */
 247
 248         if (BN_cmp(r, m) >= 0) {
 249             if (!BN_sub(r, r, m))
 250                 return 0;
 251         }
 252     }
 253     bn_check_top(r);
 254
 255     return 1;
 256 }