crypto/bn/bn_mod.c

   1 /*
   2  * Copyright 1998-2018 The OpenSSL Project Authors. All Rights Reserved.
   3  *
   4  * Licensed under the Apache License 2.0 (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->flags |= BN_FLG_FIXED_TOP;
  87     r->neg = 0;
  88
  89     if (tp != storage)
  90         OPENSSL_free(tp);
  91
  92     return 1;
  93 }
  94
  95 int BN_mod_add_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
  96                      const BIGNUM *m)
  97 {
  98     int ret = bn_mod_add_fixed_top(r, a, b, m);
  99
 100     if (ret)
 101         bn_correct_top(r);
 102
 103     return ret;
 104 }
 105
 106 int BN_mod_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m,
 107                BN_CTX *ctx)
 108 {
 109     if (!BN_sub(r, a, b))
 110         return 0;
 111     return BN_nnmod(r, r, m, ctx);
 112 }
 113
 114 /*
 115  * BN_mod_sub variant that may be used if both a and b are non-negative,
 116  * a is less than m, while b is of same bit width as m. It's implemented
 117  * as subtraction followed by two conditional additions.
 118  *
 119  * 0 <= a < m
 120  * 0 <= b < 2^w < 2*m
 121  *
 122  * after subtraction
 123  *
 124  * -2*m < r = a - b < m
 125  *
 126  * Thus it takes up to two conditional additions to make |r| positive.
 127  */
 128 int bn_mod_sub_fixed_top(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
 129                          const BIGNUM *m)
 130 {
 131     size_t i, ai, bi, mtop = m->top;
 132     BN_ULONG borrow, carry, ta, tb, mask, *rp;
 133     const BN_ULONG *ap, *bp;
 134
 135     if (bn_wexpand(r, mtop) == NULL)
 136         return 0;
 137
 138     rp = r->d;
 139     ap = a->d != NULL ? a->d : rp;
 140     bp = b->d != NULL ? b->d : rp;
 141
 142     for (i = 0, ai = 0, bi = 0, borrow = 0; i < mtop;) {
 143         mask = (BN_ULONG)0 - ((i - a->top) >> (8 * sizeof(i) - 1));
 144         ta = ap[ai] & mask;
 145
 146         mask = (BN_ULONG)0 - ((i - b->top) >> (8 * sizeof(i) - 1));
 147         tb = bp[bi] & mask;
 148         rp[i] = ta - tb - borrow;
 149         if (ta != tb)
 150             borrow = (ta < tb);
 151
 152         i++;
 153         ai += (i - a->dmax) >> (8 * sizeof(i) - 1);
 154         bi += (i - b->dmax) >> (8 * sizeof(i) - 1);
 155     }
 156     ap = m->d;
 157     for (i = 0, mask = 0 - borrow, carry = 0; i < mtop; i++) {
 158         ta = ((ap[i] & mask) + carry) & BN_MASK2;
 159         carry = (ta < carry);
 160         rp[i] = (rp[i] + ta) & BN_MASK2;
 161         carry += (rp[i] < ta);
 162     }
 163     borrow -= carry;
 164     for (i = 0, mask = 0 - borrow, carry = 0; i < mtop; i++) {
 165         ta = ((ap[i] & mask) + carry) & BN_MASK2;
 166         carry = (ta < carry);
 167         rp[i] = (rp[i] + ta) & BN_MASK2;
 168         carry += (rp[i] < ta);
 169     }
 170
 171     r->top = mtop;
 172     r->flags |= BN_FLG_FIXED_TOP;
 173     r->neg = 0;
 174
 175     return 1;
 176 }
 177
 178 /*
 179  * BN_mod_sub variant that may be used if both a and b are non-negative and
 180  * less than m
 181  */
 182 int BN_mod_sub_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
 183                      const BIGNUM *m)
 184 {
 185     if (!BN_sub(r, a, b))
 186         return 0;
 187     if (r->neg)
 188         return BN_add(r, r, m);
 189     return 1;
 190 }
 191
 192 /* slow but works */
 193 int BN_mod_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m,
 194                BN_CTX *ctx)
 195 {
 196     BIGNUM *t;
 197     int ret = 0;
 198
 199     bn_check_top(a);
 200     bn_check_top(b);
 201     bn_check_top(m);
 202
 203     BN_CTX_start(ctx);
 204     if ((t = BN_CTX_get(ctx)) == NULL)
 205         goto err;
 206     if (a == b) {
 207         if (!BN_sqr(t, a, ctx))
 208             goto err;
 209     } else {
 210         if (!BN_mul(t, a, b, ctx))
 211             goto err;
 212     }
 213     if (!BN_nnmod(r, t, m, ctx))
 214         goto err;
 215     bn_check_top(r);
 216     ret = 1;
 217  err:
 218     BN_CTX_end(ctx);
 219     return ret;
 220 }
 221
 222 int BN_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx)
 223 {
 224     if (!BN_sqr(r, a, ctx))
 225         return 0;
 226     /* r->neg == 0,  thus we don't need BN_nnmod */
 227     return BN_mod(r, r, m, ctx);
 228 }
 229
 230 int BN_mod_lshift1(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx)
 231 {
 232     if (!BN_lshift1(r, a))
 233         return 0;
 234     bn_check_top(r);
 235     return BN_nnmod(r, r, m, ctx);
 236 }
 237
 238 /*
 239  * BN_mod_lshift1 variant that may be used if a is non-negative and less than
 240  * m
 241  */
 242 int BN_mod_lshift1_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *m)
 243 {
 244     if (!BN_lshift1(r, a))
 245         return 0;
 246     bn_check_top(r);
 247     if (BN_cmp(r, m) >= 0)
 248         return BN_sub(r, r, m);
 249     return 1;
 250 }
 251
 252 int BN_mod_lshift(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m,
 253                   BN_CTX *ctx)
 254 {
 255     BIGNUM *abs_m = NULL;
 256     int ret;
 257
 258     if (!BN_nnmod(r, a, m, ctx))
 259         return 0;
 260
 261     if (m->neg) {
 262         abs_m = BN_dup(m);
 263         if (abs_m == NULL)
 264             return 0;
 265         abs_m->neg = 0;
 266     }
 267
 268     ret = BN_mod_lshift_quick(r, r, n, (abs_m ? abs_m : m));
 269     bn_check_top(r);
 270
 271     BN_free(abs_m);
 272     return ret;
 273 }
 274
 275 /*
 276  * BN_mod_lshift variant that may be used if a is non-negative and less than
 277  * m
 278  */
 279 int BN_mod_lshift_quick(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m)
 280 {
 281     if (r != a) {
 282         if (BN_copy(r, a) == NULL)
 283             return 0;
 284     }
 285
 286     while (n > 0) {
 287         int max_shift;
 288
 289         /* 0 < r < m */
 290         max_shift = BN_num_bits(m) - BN_num_bits(r);
 291         /* max_shift >= 0 */
 292
 293         if (max_shift < 0) {
 294             BNerr(BN_F_BN_MOD_LSHIFT_QUICK, BN_R_INPUT_NOT_REDUCED);
 295             return 0;
 296         }
 297
 298         if (max_shift > n)
 299             max_shift = n;
 300
 301         if (max_shift) {
 302             if (!BN_lshift(r, r, max_shift))
 303                 return 0;
 304             n -= max_shift;
 305         } else {
 306             if (!BN_lshift1(r, r))
 307                 return 0;
 308             --n;
 309         }
 310
 311         /* BN_num_bits(r) <= BN_num_bits(m) */
 312
 313         if (BN_cmp(r, m) >= 0) {
 314             if (!BN_sub(r, r, m))
 315                 return 0;
 316         }
 317     }
 318     bn_check_top(r);
 319
 320     return 1;
 321 }