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
  87     if (tp != storage)
  88         OPENSSL_free(tp);
  89
  90     return 1;
  91 }
  92
  93 int BN_mod_add_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
  94                      const BIGNUM *m)
  95 {
  96     int ret = bn_mod_add_fixed_top(r, a, b, m);
  97
  98     if (ret)
  99         bn_correct_top(r);
 100
 101     return ret;
 102 }
 103
 104 int BN_mod_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m,
 105                BN_CTX *ctx)
 106 {
 107     if (!BN_sub(r, a, b))
 108         return 0;
 109     return BN_nnmod(r, r, m, ctx);
 110 }
 111
 112 /*
 113  * BN_mod_sub variant that may be used if both a and b are non-negative and
 114  * less than m
 115  */
 116 int BN_mod_sub_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
 117                      const BIGNUM *m)
 118 {
 119     if (!BN_sub(r, a, b))
 120         return 0;
 121     if (r->neg)
 122         return BN_add(r, r, m);
 123     return 1;
 124 }
 125
 126 /* slow but works */
 127 int BN_mod_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m,
 128                BN_CTX *ctx)
 129 {
 130     BIGNUM *t;
 131     int ret = 0;
 132
 133     bn_check_top(a);
 134     bn_check_top(b);
 135     bn_check_top(m);
 136
 137     BN_CTX_start(ctx);
 138     if ((t = BN_CTX_get(ctx)) == NULL)
 139         goto err;
 140     if (a == b) {
 141         if (!BN_sqr(t, a, ctx))
 142             goto err;
 143     } else {
 144         if (!BN_mul(t, a, b, ctx))
 145             goto err;
 146     }
 147     if (!BN_nnmod(r, t, m, ctx))
 148         goto err;
 149     bn_check_top(r);
 150     ret = 1;
 151  err:
 152     BN_CTX_end(ctx);
 153     return ret;
 154 }
 155
 156 int BN_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx)
 157 {
 158     if (!BN_sqr(r, a, ctx))
 159         return 0;
 160     /* r->neg == 0,  thus we don't need BN_nnmod */
 161     return BN_mod(r, r, m, ctx);
 162 }
 163
 164 int BN_mod_lshift1(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx)
 165 {
 166     if (!BN_lshift1(r, a))
 167         return 0;
 168     bn_check_top(r);
 169     return BN_nnmod(r, r, m, ctx);
 170 }
 171
 172 /*
 173  * BN_mod_lshift1 variant that may be used if a is non-negative and less than
 174  * m
 175  */
 176 int BN_mod_lshift1_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *m)
 177 {
 178     if (!BN_lshift1(r, a))
 179         return 0;
 180     bn_check_top(r);
 181     if (BN_cmp(r, m) >= 0)
 182         return BN_sub(r, r, m);
 183     return 1;
 184 }
 185
 186 int BN_mod_lshift(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m,
 187                   BN_CTX *ctx)
 188 {
 189     BIGNUM *abs_m = NULL;
 190     int ret;
 191
 192     if (!BN_nnmod(r, a, m, ctx))
 193         return 0;
 194
 195     if (m->neg) {
 196         abs_m = BN_dup(m);
 197         if (abs_m == NULL)
 198             return 0;
 199         abs_m->neg = 0;
 200     }
 201
 202     ret = BN_mod_lshift_quick(r, r, n, (abs_m ? abs_m : m));
 203     bn_check_top(r);
 204
 205     BN_free(abs_m);
 206     return ret;
 207 }
 208
 209 /*
 210  * BN_mod_lshift variant that may be used if a is non-negative and less than
 211  * m
 212  */
 213 int BN_mod_lshift_quick(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m)
 214 {
 215     if (r != a) {
 216         if (BN_copy(r, a) == NULL)
 217             return 0;
 218     }
 219
 220     while (n > 0) {
 221         int max_shift;
 222
 223         /* 0 < r < m */
 224         max_shift = BN_num_bits(m) - BN_num_bits(r);
 225         /* max_shift >= 0 */
 226
 227         if (max_shift < 0) {
 228             BNerr(BN_F_BN_MOD_LSHIFT_QUICK, BN_R_INPUT_NOT_REDUCED);
 229             return 0;
 230         }
 231
 232         if (max_shift > n)
 233             max_shift = n;
 234
 235         if (max_shift) {
 236             if (!BN_lshift(r, r, max_shift))
 237                 return 0;
 238             n -= max_shift;
 239         } else {
 240             if (!BN_lshift1(r, r))
 241                 return 0;
 242             --n;
 243         }
 244
 245         /* BN_num_bits(r) <= BN_num_bits(m) */
 246
 247         if (BN_cmp(r, m) >= 0) {
 248             if (!BN_sub(r, r, m))
 249                 return 0;
 250         }
 251     }
 252     bn_check_top(r);
 253
 254     return 1;
 255 }