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