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