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