1 /* 2 * Copyright 1995-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 <openssl/bn.h> 11 #include "internal/cryptlib.h" 12 #include "bn_lcl.h" 13 14 /* The old slow way */ 15 #if 0 16 int BN_div(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, const BIGNUM *d, 17 BN_CTX *ctx) 18 { 19 int i, nm, nd; 20 int ret = 0; 21 BIGNUM *D; 22 23 bn_check_top(m); 24 bn_check_top(d); 25 if (BN_is_zero(d)) { 26 BNerr(BN_F_BN_DIV, BN_R_DIV_BY_ZERO); 27 return 0; 28 } 29 30 if (BN_ucmp(m, d) < 0) { 31 if (rem != NULL) { 32 if (BN_copy(rem, m) == NULL) 33 return 0; 34 } 35 if (dv != NULL) 36 BN_zero(dv); 37 return 1; 38 } 39 40 BN_CTX_start(ctx); 41 D = BN_CTX_get(ctx); 42 if (dv == NULL) 43 dv = BN_CTX_get(ctx); 44 if (rem == NULL) 45 rem = BN_CTX_get(ctx); 46 if (D == NULL || dv == NULL || rem == NULL) 47 goto end; 48 49 nd = BN_num_bits(d); 50 nm = BN_num_bits(m); 51 if (BN_copy(D, d) == NULL) 52 goto end; 53 if (BN_copy(rem, m) == NULL) 54 goto end; 55 56 /* 57 * The next 2 are needed so we can do a dv->d[0]|=1 later since 58 * BN_lshift1 will only work once there is a value :-) 59 */ 60 BN_zero(dv); 61 if (bn_wexpand(dv, 1) == NULL) 62 goto end; 63 dv->top = 1; 64 65 if (!BN_lshift(D, D, nm - nd)) 66 goto end; 67 for (i = nm - nd; i >= 0; i--) { 68 if (!BN_lshift1(dv, dv)) 69 goto end; 70 if (BN_ucmp(rem, D) >= 0) { 71 dv->d[0] |= 1; 72 if (!BN_usub(rem, rem, D)) 73 goto end; 74 } 75 /* CAN IMPROVE (and have now :=) */ 76 if (!BN_rshift1(D, D)) 77 goto end; 78 } 79 rem->neg = BN_is_zero(rem) ? 0 : m->neg; 80 dv->neg = m->neg ^ d->neg; 81 ret = 1; 82 end: 83 BN_CTX_end(ctx); 84 return ret; 85 } 86 87 #else 88 89 # if !defined(OPENSSL_NO_ASM) && !defined(OPENSSL_NO_INLINE_ASM) \ 90 && !defined(PEDANTIC) && !defined(BN_DIV3W) 91 # if defined(__GNUC__) && __GNUC__>=2 92 # if defined(__i386) || defined (__i386__) 93 /*- 94 * There were two reasons for implementing this template: 95 * - GNU C generates a call to a function (__udivdi3 to be exact) 96 * in reply to ((((BN_ULLONG)n0)<<BN_BITS2)|n1)/d0 (I fail to 97 * understand why...); 98 * - divl doesn't only calculate quotient, but also leaves 99 * remainder in %edx which we can definitely use here:-) 100 */ 101 # undef bn_div_words 102 # define bn_div_words(n0,n1,d0) \ 103 ({ asm volatile ( \ 104 "divl %4" \ 105 : "=a"(q), "=d"(rem) \ 106 : "a"(n1), "d"(n0), "r"(d0) \ 107 : "cc"); \ 108 q; \ 109 }) 110 # define REMAINDER_IS_ALREADY_CALCULATED 111 # elif defined(__x86_64) && defined(SIXTY_FOUR_BIT_LONG) 112 /* 113 * Same story here, but it's 128-bit by 64-bit division. Wow! 114 */ 115 # undef bn_div_words 116 # define bn_div_words(n0,n1,d0) \ 117 ({ asm volatile ( \ 118 "divq %4" \ 119 : "=a"(q), "=d"(rem) \ 120 : "a"(n1), "d"(n0), "r"(d0) \ 121 : "cc"); \ 122 q; \ 123 }) 124 # define REMAINDER_IS_ALREADY_CALCULATED 125 # endif /* __<cpu> */ 126 # endif /* __GNUC__ */ 127 # endif /* OPENSSL_NO_ASM */ 128 129 /*- 130 * BN_div computes dv := num / divisor, rounding towards 131 * zero, and sets up rm such that dv*divisor + rm = num holds. 132 * Thus: 133 * dv->neg == num->neg ^ divisor->neg (unless the result is zero) 134 * rm->neg == num->neg (unless the remainder is zero) 135 * If 'dv' or 'rm' is NULL, the respective value is not returned. 136 */ 137 int BN_div(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor, 138 BN_CTX *ctx) 139 { 140 int norm_shift, i, loop; 141 BIGNUM *tmp, wnum, *snum, *sdiv, *res; 142 BN_ULONG *resp, *wnump; 143 BN_ULONG d0, d1; 144 int num_n, div_n; 145 int no_branch = 0; 146 147 /* 148 * Invalid zero-padding would have particularly bad consequences so don't 149 * just rely on bn_check_top() here (bn_check_top() works only for 150 * BN_DEBUG builds) 151 */ 152 if ((num->top > 0 && num->d[num->top - 1] == 0) || 153 (divisor->top > 0 && divisor->d[divisor->top - 1] == 0)) { 154 BNerr(BN_F_BN_DIV, BN_R_NOT_INITIALIZED); 155 return 0; 156 } 157 158 bn_check_top(num); 159 bn_check_top(divisor); 160 161 if ((BN_get_flags(num, BN_FLG_CONSTTIME) != 0) 162 || (BN_get_flags(divisor, BN_FLG_CONSTTIME) != 0)) { 163 no_branch = 1; 164 } 165 166 bn_check_top(dv); 167 bn_check_top(rm); 168 /*- bn_check_top(num); *//* 169 * 'num' has been checked already 170 */ 171 /*- bn_check_top(divisor); *//* 172 * 'divisor' has been checked already 173 */ 174 175 if (BN_is_zero(divisor)) { 176 BNerr(BN_F_BN_DIV, BN_R_DIV_BY_ZERO); 177 return 0; 178 } 179 180 if (!no_branch && BN_ucmp(num, divisor) < 0) { 181 if (rm != NULL) { 182 if (BN_copy(rm, num) == NULL) 183 return 0; 184 } 185 if (dv != NULL) 186 BN_zero(dv); 187 return 1; 188 } 189 190 BN_CTX_start(ctx); 191 res = (dv == NULL) ? BN_CTX_get(ctx) : dv; 192 tmp = BN_CTX_get(ctx); 193 snum = BN_CTX_get(ctx); 194 sdiv = BN_CTX_get(ctx); 195 if (sdiv == NULL) 196 goto err; 197 198 /* First we normalise the numbers */ 199 norm_shift = BN_BITS2 - ((BN_num_bits(divisor)) % BN_BITS2); 200 if (!(BN_lshift(sdiv, divisor, norm_shift))) 201 goto err; 202 sdiv->neg = 0; 203 norm_shift += BN_BITS2; 204 if (!(BN_lshift(snum, num, norm_shift))) 205 goto err; 206 snum->neg = 0; 207 208 if (no_branch) { 209 /* 210 * Since we don't know whether snum is larger than sdiv, we pad snum 211 * with enough zeroes without changing its value. 212 */ 213 if (snum->top <= sdiv->top + 1) { 214 if (bn_wexpand(snum, sdiv->top + 2) == NULL) 215 goto err; 216 for (i = snum->top; i < sdiv->top + 2; i++) 217 snum->d[i] = 0; 218 snum->top = sdiv->top + 2; 219 } else { 220 if (bn_wexpand(snum, snum->top + 1) == NULL) 221 goto err; 222 snum->d[snum->top] = 0; 223 snum->top++; 224 } 225 } 226 227 div_n = sdiv->top; 228 num_n = snum->top; 229 loop = num_n - div_n; 230 /* 231 * Lets setup a 'window' into snum This is the part that corresponds to 232 * the current 'area' being divided 233 */ 234 wnum.neg = 0; 235 wnum.d = &(snum->d[loop]); 236 wnum.top = div_n; 237 wnum.flags = BN_FLG_STATIC_DATA; 238 /* 239 * only needed when BN_ucmp messes up the values between top and max 240 */ 241 wnum.dmax = snum->dmax - loop; /* so we don't step out of bounds */ 242 243 /* Get the top 2 words of sdiv */ 244 /* div_n=sdiv->top; */ 245 d0 = sdiv->d[div_n - 1]; 246 d1 = (div_n == 1) ? 0 : sdiv->d[div_n - 2]; 247 248 /* pointer to the 'top' of snum */ 249 wnump = &(snum->d[num_n - 1]); 250 251 /* Setup to 'res' */ 252 if (!bn_wexpand(res, (loop + 1))) 253 goto err; 254 res->neg = (num->neg ^ divisor->neg); 255 res->top = loop - no_branch; 256 resp = &(res->d[loop - 1]); 257 258 /* space for temp */ 259 if (!bn_wexpand(tmp, (div_n + 1))) 260 goto err; 261 262 if (!no_branch) { 263 if (BN_ucmp(&wnum, sdiv) >= 0) { 264 /* 265 * If BN_DEBUG_RAND is defined BN_ucmp changes (via bn_pollute) 266 * the const bignum arguments => clean the values between top and 267 * max again 268 */ 269 bn_clear_top2max(&wnum); 270 bn_sub_words(wnum.d, wnum.d, sdiv->d, div_n); 271 *resp = 1; 272 } else 273 res->top--; 274 } 275 276 /* Increase the resp pointer so that we never create an invalid pointer. */ 277 resp++; 278 279 /* 280 * if res->top == 0 then clear the neg value otherwise decrease the resp 281 * pointer 282 */ 283 if (res->top == 0) 284 res->neg = 0; 285 else 286 resp--; 287 288 for (i = 0; i < loop - 1; i++, wnump--) { 289 BN_ULONG q, l0; 290 /* 291 * the first part of the loop uses the top two words of snum and sdiv 292 * to calculate a BN_ULONG q such that | wnum - sdiv * q | < sdiv 293 */ 294 # if defined(BN_DIV3W) && !defined(OPENSSL_NO_ASM) 295 BN_ULONG bn_div_3_words(BN_ULONG *, BN_ULONG, BN_ULONG); 296 q = bn_div_3_words(wnump, d1, d0); 297 # else 298 BN_ULONG n0, n1, rem = 0; 299 300 n0 = wnump[0]; 301 n1 = wnump[-1]; 302 if (n0 == d0) 303 q = BN_MASK2; 304 else { /* n0 < d0 */ 305 306 # ifdef BN_LLONG 307 BN_ULLONG t2; 308 309 # if defined(BN_LLONG) && defined(BN_DIV2W) && !defined(bn_div_words) 310 q = (BN_ULONG)(((((BN_ULLONG) n0) << BN_BITS2) | n1) / d0); 311 # else 312 q = bn_div_words(n0, n1, d0); 313 # endif 314 315 # ifndef REMAINDER_IS_ALREADY_CALCULATED 316 /* 317 * rem doesn't have to be BN_ULLONG. The least we 318 * know it's less that d0, isn't it? 319 */ 320 rem = (n1 - q * d0) & BN_MASK2; 321 # endif 322 t2 = (BN_ULLONG) d1 *q; 323 324 for (;;) { 325 if (t2 <= ((((BN_ULLONG) rem) << BN_BITS2) | wnump[-2])) 326 break; 327 q--; 328 rem += d0; 329 if (rem < d0) 330 break; /* don't let rem overflow */ 331 t2 -= d1; 332 } 333 # else /* !BN_LLONG */ 334 BN_ULONG t2l, t2h; 335 336 q = bn_div_words(n0, n1, d0); 337 # ifndef REMAINDER_IS_ALREADY_CALCULATED 338 rem = (n1 - q * d0) & BN_MASK2; 339 # endif 340 341 # if defined(BN_UMULT_LOHI) 342 BN_UMULT_LOHI(t2l, t2h, d1, q); 343 # elif defined(BN_UMULT_HIGH) 344 t2l = d1 * q; 345 t2h = BN_UMULT_HIGH(d1, q); 346 # else 347 { 348 BN_ULONG ql, qh; 349 t2l = LBITS(d1); 350 t2h = HBITS(d1); 351 ql = LBITS(q); 352 qh = HBITS(q); 353 mul64(t2l, t2h, ql, qh); /* t2=(BN_ULLONG)d1*q; */ 354 } 355 # endif 356 357 for (;;) { 358 if ((t2h < rem) || ((t2h == rem) && (t2l <= wnump[-2]))) 359 break; 360 q--; 361 rem += d0; 362 if (rem < d0) 363 break; /* don't let rem overflow */ 364 if (t2l < d1) 365 t2h--; 366 t2l -= d1; 367 } 368 # endif /* !BN_LLONG */ 369 } 370 # endif /* !BN_DIV3W */ 371 372 l0 = bn_mul_words(tmp->d, sdiv->d, div_n, q); 373 tmp->d[div_n] = l0; 374 wnum.d--; 375 /* 376 * ingore top values of the bignums just sub the two BN_ULONG arrays 377 * with bn_sub_words 378 */ 379 if (bn_sub_words(wnum.d, wnum.d, tmp->d, div_n + 1)) { 380 /* 381 * Note: As we have considered only the leading two BN_ULONGs in 382 * the calculation of q, sdiv * q might be greater than wnum (but 383 * then (q-1) * sdiv is less or equal than wnum) 384 */ 385 q--; 386 if (bn_add_words(wnum.d, wnum.d, sdiv->d, div_n)) 387 /* 388 * we can't have an overflow here (assuming that q != 0, but 389 * if q == 0 then tmp is zero anyway) 390 */ 391 (*wnump)++; 392 } 393 /* store part of the result */ 394 resp--; 395 *resp = q; 396 } 397 bn_correct_top(snum); 398 if (rm != NULL) { 399 /* 400 * Keep a copy of the neg flag in num because if rm==num BN_rshift() 401 * will overwrite it. 402 */ 403 int neg = num->neg; 404 BN_rshift(rm, snum, norm_shift); 405 if (!BN_is_zero(rm)) 406 rm->neg = neg; 407 bn_check_top(rm); 408 } 409 if (no_branch) 410 bn_correct_top(res); 411 BN_CTX_end(ctx); 412 return 1; 413 err: 414 bn_check_top(rm); 415 BN_CTX_end(ctx); 416 return 0; 417 } 418 #endif 419