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 } 326