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