crypto/bn/bn_mod.c

   1 /*
   2  * Copyright 1998-2021 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_local.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 (r == d) {
  21         ERR_raise(ERR_LIB_BN, ERR_R_PASSED_INVALID_ARGUMENT);
  22         return 0;
  23     }
  24
  25     if (!(BN_mod(r, m, d, ctx)))
  26         return 0;
  27     if (!r->neg)
  28         return 1;
  29     /* now   -|d| < r < 0,  so we have to set  r := r + |d| */
  30     return (d->neg ? BN_sub : BN_add) (r, r, d);
  31 }
  32
  33 int BN_mod_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m,
  34                BN_CTX *ctx)
  35 {
  36     if (!BN_add(r, a, b))
  37         return 0;
  38     return BN_nnmod(r, r, m, ctx);
  39 }
  40
  41 /*
  42  * BN_mod_add variant that may be used if both a and b are non-negative and
  43  * less than m. The original algorithm was
  44  *
  45  *    if (!BN_uadd(r, a, b))
  46  *       return 0;
  47  *    if (BN_ucmp(r, m) >= 0)
  48  *       return BN_usub(r, r, m);
  49  *
  50  * which is replaced with addition, subtracting modulus, and conditional
  51  * move depending on whether or not subtraction borrowed.
  52  */
  53 int bn_mod_add_fixed_top(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
  54                          const BIGNUM *m)
  55 {
  56     size_t i, ai, bi, mtop = m->top;
  57     BN_ULONG storage[1024 / BN_BITS2];
  58     BN_ULONG carry, temp, mask, *rp, *tp = storage;
  59     const BN_ULONG *ap, *bp;
  60
  61     if (bn_wexpand(r, mtop) == NULL)
  62         return 0;
  63
  64     if (mtop > sizeof(storage) / sizeof(storage[0])) {
  65         tp = OPENSSL_malloc(mtop * sizeof(BN_ULONG));
  66         if (tp == NULL)
  67             return 0;
  68     }
  69
  70     ap = a->d != NULL ? a->d : tp;
  71     bp = b->d != NULL ? b->d : tp;
  72
  73     for (i = 0, ai = 0, bi = 0, carry = 0; i < mtop;) {
  74         mask = (BN_ULONG)0 - ((i - a->top) >> (8 * sizeof(i) - 1));
  75         temp = ((ap[ai] & mask) + carry) & BN_MASK2;
  76         carry = (temp < carry);
  77
  78         mask = (BN_ULONG)0 - ((i - b->top) >> (8 * sizeof(i) - 1));
  79         tp[i] = ((bp[bi] & mask) + temp) & BN_MASK2;
  80         carry += (tp[i] < temp);
  81
  82         i++;
  83         ai += (i - a->dmax) >> (8 * sizeof(i) - 1);
  84         bi += (i - b->dmax) >> (8 * sizeof(i) - 1);
  85     }
  86     rp = r->d;
  87     carry -= bn_sub_words(rp, tp, m->d, mtop);
  88     for (i = 0; i < mtop; i++) {
  89         rp[i] = (carry & tp[i]) | (~carry & rp[i]);
  90         ((volatile BN_ULONG *)tp)[i] = 0;
  91     }
  92     r->top = mtop;
  93     r->flags |= BN_FLG_FIXED_TOP;
  94     r->neg = 0;
  95
  96     if (tp != storage)
  97         OPENSSL_free(tp);
  98
  99     return 1;
 100 }
 101
 102 int BN_mod_add_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
 103                      const BIGNUM *m)
 104 {
 105     int ret = bn_mod_add_fixed_top(r, a, b, m);
 106
 107     if (ret)
 108         bn_correct_top(r);
 109
 110     return ret;
 111 }
 112
 113 int BN_mod_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m,
 114                BN_CTX *ctx)
 115 {
 116     if (!BN_sub(r, a, b))
 117         return 0;
 118     return BN_nnmod(r, r, m, ctx);
 119 }
 120
 121 /*
 122  * BN_mod_sub variant that may be used if both a and b are non-negative,
 123  * a is less than m, while b is of same bit width as m. It's implemented
 124  * as subtraction followed by two conditional additions.
 125  *
 126  * 0 <= a < m
 127  * 0 <= b < 2^w < 2*m
 128  *
 129  * after subtraction
 130  *
 131  * -2*m < r = a - b < m
 132  *
 133  * Thus it takes up to two conditional additions to make |r| positive.
 134  */
 135 int bn_mod_sub_fixed_top(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
 136                          const BIGNUM *m)
 137 {
 138     size_t i, ai, bi, mtop = m->top;
 139     BN_ULONG borrow, carry, ta, tb, mask, *rp;
 140     const BN_ULONG *ap, *bp;
 141
 142     if (bn_wexpand(r, mtop) == NULL)
 143         return 0;
 144
 145     rp = r->d;
 146     ap = a->d != NULL ? a->d : rp;
 147     bp = b->d != NULL ? b->d : rp;
 148
 149     for (i = 0, ai = 0, bi = 0, borrow = 0; i < mtop;) {
 150         mask = (BN_ULONG)0 - ((i - a->top) >> (8 * sizeof(i) - 1));
 151         ta = ap[ai] & mask;
 152
 153         mask = (BN_ULONG)0 - ((i - b->top) >> (8 * sizeof(i) - 1));
 154         tb = bp[bi] & mask;
 155         rp[i] = ta - tb - borrow;
 156         if (ta != tb)
 157             borrow = (ta < tb);
 158
 159         i++;
 160         ai += (i - a->dmax) >> (8 * sizeof(i) - 1);
 161         bi += (i - b->dmax) >> (8 * sizeof(i) - 1);
 162     }
 163     ap = m->d;
 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     borrow -= carry;
 171     for (i = 0, mask = 0 - borrow, carry = 0; i < mtop; i++) {
 172         ta = ((ap[i] & mask) + carry) & BN_MASK2;
 173         carry = (ta < carry);
 174         rp[i] = (rp[i] + ta) & BN_MASK2;
 175         carry += (rp[i] < ta);
 176     }
 177
 178     r->top = mtop;
 179     r->flags |= BN_FLG_FIXED_TOP;
 180     r->neg = 0;
 181
 182     return 1;
 183 }
 184
 185 /*
 186  * BN_mod_sub variant that may be used if both a and b are non-negative and
 187  * less than m
 188  */
 189 int BN_mod_sub_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
 190                      const BIGNUM *m)
 191 {
 192     if (r == m) {
 193         ERR_raise(ERR_LIB_BN, ERR_R_PASSED_INVALID_ARGUMENT);
 194         return 0;
 195     }
 196
 197     if (!BN_sub(r, a, b))
 198         return 0;
 199     if (r->neg)
 200         return BN_add(r, r, m);
 201     return 1;
 202 }
 203
 204 /* slow but works */
 205 int BN_mod_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m,
 206                BN_CTX *ctx)
 207 {
 208     BIGNUM *t;
 209     int ret = 0;
 210
 211     bn_check_top(a);
 212     bn_check_top(b);
 213     bn_check_top(m);
 214
 215     BN_CTX_start(ctx);
 216     if ((t = BN_CTX_get(ctx)) == NULL)
 217         goto err;
 218     if (a == b) {
 219         if (!BN_sqr(t, a, ctx))
 220             goto err;
 221     } else {
 222         if (!BN_mul(t, a, b, ctx))
 223             goto err;
 224     }
 225     if (!BN_nnmod(r, t, m, ctx))
 226         goto err;
 227     bn_check_top(r);
 228     ret = 1;
 229  err:
 230     BN_CTX_end(ctx);
 231     return ret;
 232 }
 233
 234 int BN_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx)
 235 {
 236     if (!BN_sqr(r, a, ctx))
 237         return 0;
 238     /* r->neg == 0,  thus we don't need BN_nnmod */
 239     return BN_mod(r, r, m, ctx);
 240 }
 241
 242 int BN_mod_lshift1(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx)
 243 {
 244     if (!BN_lshift1(r, a))
 245         return 0;
 246     bn_check_top(r);
 247     return BN_nnmod(r, r, m, ctx);
 248 }
 249
 250 /*
 251  * BN_mod_lshift1 variant that may be used if a is non-negative and less than
 252  * m
 253  */
 254 int BN_mod_lshift1_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *m)
 255 {
 256     if (!BN_lshift1(r, a))
 257         return 0;
 258     bn_check_top(r);
 259     if (BN_cmp(r, m) >= 0)
 260         return BN_sub(r, r, m);
 261     return 1;
 262 }
 263
 264 int BN_mod_lshift(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m,
 265                   BN_CTX *ctx)
 266 {
 267     BIGNUM *abs_m = NULL;
 268     int ret;
 269
 270     if (!BN_nnmod(r, a, m, ctx))
 271         return 0;
 272
 273     if (m->neg) {
 274         abs_m = BN_dup(m);
 275         if (abs_m == NULL)
 276             return 0;
 277         abs_m->neg = 0;
 278     }
 279
 280     ret = BN_mod_lshift_quick(r, r, n, (abs_m ? abs_m : m));
 281     bn_check_top(r);
 282
 283     BN_free(abs_m);
 284     return ret;
 285 }
 286
 287 /*
 288  * BN_mod_lshift variant that may be used if a is non-negative and less than
 289  * m
 290  */
 291 int BN_mod_lshift_quick(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m)
 292 {
 293     if (r != a) {
 294         if (BN_copy(r, a) == NULL)
 295             return 0;
 296     }
 297
 298     while (n > 0) {
 299         int max_shift;
 300
 301         /* 0 < r < m */
 302         max_shift = BN_num_bits(m) - BN_num_bits(r);
 303         /* max_shift >= 0 */
 304
 305         if (max_shift < 0) {
 306             ERR_raise(ERR_LIB_BN, BN_R_INPUT_NOT_REDUCED);
 307             return 0;
 308         }
 309
 310         if (max_shift > n)
 311             max_shift = n;
 312
 313         if (max_shift) {
 314             if (!BN_lshift(r, r, max_shift))
 315                 return 0;
 316             n -= max_shift;
 317         } else {
 318             if (!BN_lshift1(r, r))
 319                 return 0;
 320             --n;
 321         }
 322
 323         /* BN_num_bits(r) <= BN_num_bits(m) */
 324
 325         if (BN_cmp(r, m) >= 0) {
 326             if (!BN_sub(r, r, m))
 327                 return 0;
 328         }
 329     }
 330     bn_check_top(r);
 331
 332     return 1;
 333 }