1 | /* |
2 | * Copyright 1995-2018 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 <assert.h> |
11 | #include <openssl/bn.h> |
12 | #include "internal/cryptlib.h" |
13 | #include "bn_local.h" |
14 | |
15 | /* The old slow way */ |
16 | #if 0 |
17 | int BN_div(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, const BIGNUM *d, |
18 | BN_CTX *ctx) |
19 | { |
20 | int i, nm, nd; |
21 | int ret = 0; |
22 | BIGNUM *D; |
23 | |
24 | bn_check_top(m); |
25 | bn_check_top(d); |
26 | if (BN_is_zero(d)) { |
27 | BNerr(BN_F_BN_DIV, BN_R_DIV_BY_ZERO); |
28 | return 0; |
29 | } |
30 | |
31 | if (BN_ucmp(m, d) < 0) { |
32 | if (rem != NULL) { |
33 | if (BN_copy(rem, m) == NULL) |
34 | return 0; |
35 | } |
36 | if (dv != NULL) |
37 | BN_zero(dv); |
38 | return 1; |
39 | } |
40 | |
41 | BN_CTX_start(ctx); |
42 | D = BN_CTX_get(ctx); |
43 | if (dv == NULL) |
44 | dv = BN_CTX_get(ctx); |
45 | if (rem == NULL) |
46 | rem = BN_CTX_get(ctx); |
47 | if (D == NULL || dv == NULL || rem == NULL) |
48 | goto end; |
49 | |
50 | nd = BN_num_bits(d); |
51 | nm = BN_num_bits(m); |
52 | if (BN_copy(D, d) == NULL) |
53 | goto end; |
54 | if (BN_copy(rem, m) == NULL) |
55 | goto end; |
56 | |
57 | /* |
58 | * The next 2 are needed so we can do a dv->d[0]|=1 later since |
59 | * BN_lshift1 will only work once there is a value :-) |
60 | */ |
61 | BN_zero(dv); |
62 | if (bn_wexpand(dv, 1) == NULL) |
63 | goto end; |
64 | dv->top = 1; |
65 | |
66 | if (!BN_lshift(D, D, nm - nd)) |
67 | goto end; |
68 | for (i = nm - nd; i >= 0; i--) { |
69 | if (!BN_lshift1(dv, dv)) |
70 | goto end; |
71 | if (BN_ucmp(rem, D) >= 0) { |
72 | dv->d[0] |= 1; |
73 | if (!BN_usub(rem, rem, D)) |
74 | goto end; |
75 | } |
76 | /* CAN IMPROVE (and have now :=) */ |
77 | if (!BN_rshift1(D, D)) |
78 | goto end; |
79 | } |
80 | rem->neg = BN_is_zero(rem) ? 0 : m->neg; |
81 | dv->neg = m->neg ^ d->neg; |
82 | ret = 1; |
83 | end: |
84 | BN_CTX_end(ctx); |
85 | return ret; |
86 | } |
87 | |
88 | #else |
89 | |
90 | # if defined(BN_DIV3W) |
91 | BN_ULONG bn_div_3_words(const BN_ULONG *m, BN_ULONG d1, BN_ULONG d0); |
92 | # elif 0 |
93 | /* |
94 | * This is #if-ed away, because it's a reference for assembly implementations, |
95 | * where it can and should be made constant-time. But if you want to test it, |
96 | * just replace 0 with 1. |
97 | */ |
98 | # if BN_BITS2 == 64 && defined(__SIZEOF_INT128__) && __SIZEOF_INT128__==16 |
99 | # undef BN_ULLONG |
100 | # define BN_ULLONG __uint128_t |
101 | # define BN_LLONG |
102 | # endif |
103 | |
104 | # ifdef BN_LLONG |
105 | # define BN_DIV3W |
106 | /* |
107 | * Interface is somewhat quirky, |m| is pointer to most significant limb, |
108 | * and less significant limb is referred at |m[-1]|. This means that caller |
109 | * is responsible for ensuring that |m[-1]| is valid. Second condition that |
110 | * has to be met is that |d0|'s most significant bit has to be set. Or in |
111 | * other words divisor has to be "bit-aligned to the left." bn_div_fixed_top |
112 | * does all this. The subroutine considers four limbs, two of which are |
113 | * "overlapping," hence the name... |
114 | */ |
115 | static BN_ULONG bn_div_3_words(const BN_ULONG *m, BN_ULONG d1, BN_ULONG d0) |
116 | { |
117 | BN_ULLONG R = ((BN_ULLONG)m[0] << BN_BITS2) | m[-1]; |
118 | BN_ULLONG D = ((BN_ULLONG)d0 << BN_BITS2) | d1; |
119 | BN_ULONG Q = 0, mask; |
120 | int i; |
121 | |
122 | for (i = 0; i < BN_BITS2; i++) { |
123 | Q <<= 1; |
124 | if (R >= D) { |
125 | Q |= 1; |
126 | R -= D; |
127 | } |
128 | D >>= 1; |
129 | } |
130 | |
131 | mask = 0 - (Q >> (BN_BITS2 - 1)); /* does it overflow? */ |
132 | |
133 | Q <<= 1; |
134 | Q |= (R >= D); |
135 | |
136 | return (Q | mask) & BN_MASK2; |
137 | } |
138 | # endif |
139 | # endif |
140 | |
141 | static int bn_left_align(BIGNUM *num) |
142 | { |
143 | BN_ULONG *d = num->d, n, m, rmask; |
144 | int top = num->top; |
145 | int rshift = BN_num_bits_word(d[top - 1]), lshift, i; |
146 | |
147 | lshift = BN_BITS2 - rshift; |
148 | rshift %= BN_BITS2; /* say no to undefined behaviour */ |
149 | rmask = (BN_ULONG)0 - rshift; /* rmask = 0 - (rshift != 0) */ |
150 | rmask |= rmask >> 8; |
151 | |
152 | for (i = 0, m = 0; i < top; i++) { |
153 | n = d[i]; |
154 | d[i] = ((n << lshift) | m) & BN_MASK2; |
155 | m = (n >> rshift) & rmask; |
156 | } |
157 | |
158 | return lshift; |
159 | } |
160 | |
161 | # if !defined(OPENSSL_NO_ASM) && !defined(OPENSSL_NO_INLINE_ASM) \ |
162 | && !defined(PEDANTIC) && !defined(BN_DIV3W) |
163 | # if defined(__GNUC__) && __GNUC__>=2 |
164 | # if defined(__i386) || defined (__i386__) |
165 | /*- |
166 | * There were two reasons for implementing this template: |
167 | * - GNU C generates a call to a function (__udivdi3 to be exact) |
168 | * in reply to ((((BN_ULLONG)n0)<<BN_BITS2)|n1)/d0 (I fail to |
169 | * understand why...); |
170 | * - divl doesn't only calculate quotient, but also leaves |
171 | * remainder in %edx which we can definitely use here:-) |
172 | */ |
173 | # undef bn_div_words |
174 | # define bn_div_words(n0,n1,d0) \ |
175 | ({ asm volatile ( \ |
176 | "divl %4" \ |
177 | : "=a"(q), "=d"(rem) \ |
178 | : "a"(n1), "d"(n0), "r"(d0) \ |
179 | : "cc"); \ |
180 | q; \ |
181 | }) |
182 | # define REMAINDER_IS_ALREADY_CALCULATED |
183 | # elif defined(__x86_64) && defined(SIXTY_FOUR_BIT_LONG) |
184 | /* |
185 | * Same story here, but it's 128-bit by 64-bit division. Wow! |
186 | */ |
187 | # undef bn_div_words |
188 | # define bn_div_words(n0,n1,d0) \ |
189 | ({ asm volatile ( \ |
190 | "divq %4" \ |
191 | : "=a"(q), "=d"(rem) \ |
192 | : "a"(n1), "d"(n0), "r"(d0) \ |
193 | : "cc"); \ |
194 | q; \ |
195 | }) |
196 | # define REMAINDER_IS_ALREADY_CALCULATED |
197 | # endif /* __<cpu> */ |
198 | # endif /* __GNUC__ */ |
199 | # endif /* OPENSSL_NO_ASM */ |
200 | |
201 | /*- |
202 | * BN_div computes dv := num / divisor, rounding towards |
203 | * zero, and sets up rm such that dv*divisor + rm = num holds. |
204 | * Thus: |
205 | * dv->neg == num->neg ^ divisor->neg (unless the result is zero) |
206 | * rm->neg == num->neg (unless the remainder is zero) |
207 | * If 'dv' or 'rm' is NULL, the respective value is not returned. |
208 | */ |
209 | int BN_div(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor, |
210 | BN_CTX *ctx) |
211 | { |
212 | int ret; |
213 | |
214 | if (BN_is_zero(divisor)) { |
215 | BNerr(BN_F_BN_DIV, BN_R_DIV_BY_ZERO); |
216 | return 0; |
217 | } |
218 | |
219 | /* |
220 | * Invalid zero-padding would have particularly bad consequences so don't |
221 | * just rely on bn_check_top() here (bn_check_top() works only for |
222 | * BN_DEBUG builds) |
223 | */ |
224 | if (divisor->d[divisor->top - 1] == 0) { |
225 | BNerr(BN_F_BN_DIV, BN_R_NOT_INITIALIZED); |
226 | return 0; |
227 | } |
228 | |
229 | ret = bn_div_fixed_top(dv, rm, num, divisor, ctx); |
230 | |
231 | if (ret) { |
232 | if (dv != NULL) |
233 | bn_correct_top(dv); |
234 | if (rm != NULL) |
235 | bn_correct_top(rm); |
236 | } |
237 | |
238 | return ret; |
239 | } |
240 | |
241 | /* |
242 | * It's argued that *length* of *significant* part of divisor is public. |
243 | * Even if it's private modulus that is. Again, *length* is assumed |
244 | * public, but not *value*. Former is likely to be pre-defined by |
245 | * algorithm with bit granularity, though below subroutine is invariant |
246 | * of limb length. Thanks to this assumption we can require that |divisor| |
247 | * may not be zero-padded, yet claim this subroutine "constant-time"(*). |
248 | * This is because zero-padded dividend, |num|, is tolerated, so that |
249 | * caller can pass dividend of public length(*), but with smaller amount |
250 | * of significant limbs. This naturally means that quotient, |dv|, would |
251 | * contain correspongly less significant limbs as well, and will be zero- |
252 | * padded accordingly. Returned remainder, |rm|, will have same bit length |
253 | * as divisor, also zero-padded if needed. These actually leave sign bits |
254 | * in ambiguous state. In sense that we try to avoid negative zeros, while |
255 | * zero-padded zeros would retain sign. |
256 | * |
257 | * (*) "Constant-time-ness" has two pre-conditions: |
258 | * |
259 | * - availability of constant-time bn_div_3_words; |
260 | * - dividend is at least as "wide" as divisor, limb-wise, zero-padded |
261 | * if so required, which shouldn't be a privacy problem, because |
262 | * divisor's length is considered public; |
263 | */ |
264 | int bn_div_fixed_top(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, |
265 | const BIGNUM *divisor, BN_CTX *ctx) |
266 | { |
267 | int norm_shift, i, j, loop; |
268 | BIGNUM *tmp, *snum, *sdiv, *res; |
269 | BN_ULONG *resp, *wnum, *wnumtop; |
270 | BN_ULONG d0, d1; |
271 | int num_n, div_n; |
272 | |
273 | assert(divisor->top > 0 && divisor->d[divisor->top - 1] != 0); |
274 | |
275 | bn_check_top(num); |
276 | bn_check_top(divisor); |
277 | bn_check_top(dv); |
278 | bn_check_top(rm); |
279 | |
280 | BN_CTX_start(ctx); |
281 | res = (dv == NULL) ? BN_CTX_get(ctx) : dv; |
282 | tmp = BN_CTX_get(ctx); |
283 | snum = BN_CTX_get(ctx); |
284 | sdiv = BN_CTX_get(ctx); |
285 | if (sdiv == NULL) |
286 | goto err; |
287 | |
288 | /* First we normalise the numbers */ |
289 | if (!BN_copy(sdiv, divisor)) |
290 | goto err; |
291 | norm_shift = bn_left_align(sdiv); |
292 | sdiv->neg = 0; |
293 | /* |
294 | * Note that bn_lshift_fixed_top's output is always one limb longer |
295 | * than input, even when norm_shift is zero. This means that amount of |
296 | * inner loop iterations is invariant of dividend value, and that one |
297 | * doesn't need to compare dividend and divisor if they were originally |
298 | * of the same bit length. |
299 | */ |
300 | if (!(bn_lshift_fixed_top(snum, num, norm_shift))) |
301 | goto err; |
302 | |
303 | div_n = sdiv->top; |
304 | num_n = snum->top; |
305 | |
306 | if (num_n <= div_n) { |
307 | /* caller didn't pad dividend -> no constant-time guarantee... */ |
308 | if (bn_wexpand(snum, div_n + 1) == NULL) |
309 | goto err; |
310 | memset(&(snum->d[num_n]), 0, (div_n - num_n + 1) * sizeof(BN_ULONG)); |
311 | snum->top = num_n = div_n + 1; |
312 | } |
313 | |
314 | loop = num_n - div_n; |
315 | /* |
316 | * Lets setup a 'window' into snum This is the part that corresponds to |
317 | * the current 'area' being divided |
318 | */ |
319 | wnum = &(snum->d[loop]); |
320 | wnumtop = &(snum->d[num_n - 1]); |
321 | |
322 | /* Get the top 2 words of sdiv */ |
323 | d0 = sdiv->d[div_n - 1]; |
324 | d1 = (div_n == 1) ? 0 : sdiv->d[div_n - 2]; |
325 | |
326 | /* Setup quotient */ |
327 | if (!bn_wexpand(res, loop)) |
328 | goto err; |
329 | res->neg = (num->neg ^ divisor->neg); |
330 | res->top = loop; |
331 | res->flags |= BN_FLG_FIXED_TOP; |
332 | resp = &(res->d[loop]); |
333 | |
334 | /* space for temp */ |
335 | if (!bn_wexpand(tmp, (div_n + 1))) |
336 | goto err; |
337 | |
338 | for (i = 0; i < loop; i++, wnumtop--) { |
339 | BN_ULONG q, l0; |
340 | /* |
341 | * the first part of the loop uses the top two words of snum and sdiv |
342 | * to calculate a BN_ULONG q such that | wnum - sdiv * q | < sdiv |
343 | */ |
344 | # if defined(BN_DIV3W) |
345 | q = bn_div_3_words(wnumtop, d1, d0); |
346 | # else |
347 | BN_ULONG n0, n1, rem = 0; |
348 | |
349 | n0 = wnumtop[0]; |
350 | n1 = wnumtop[-1]; |
351 | if (n0 == d0) |
352 | q = BN_MASK2; |
353 | else { /* n0 < d0 */ |
354 | BN_ULONG n2 = (wnumtop == wnum) ? 0 : wnumtop[-2]; |
355 | # ifdef BN_LLONG |
356 | BN_ULLONG t2; |
357 | |
358 | # if defined(BN_LLONG) && defined(BN_DIV2W) && !defined(bn_div_words) |
359 | q = (BN_ULONG)(((((BN_ULLONG) n0) << BN_BITS2) | n1) / d0); |
360 | # else |
361 | q = bn_div_words(n0, n1, d0); |
362 | # endif |
363 | |
364 | # ifndef REMAINDER_IS_ALREADY_CALCULATED |
365 | /* |
366 | * rem doesn't have to be BN_ULLONG. The least we |
367 | * know it's less that d0, isn't it? |
368 | */ |
369 | rem = (n1 - q * d0) & BN_MASK2; |
370 | # endif |
371 | t2 = (BN_ULLONG) d1 *q; |
372 | |
373 | for (;;) { |
374 | if (t2 <= ((((BN_ULLONG) rem) << BN_BITS2) | n2)) |
375 | break; |
376 | q--; |
377 | rem += d0; |
378 | if (rem < d0) |
379 | break; /* don't let rem overflow */ |
380 | t2 -= d1; |
381 | } |
382 | # else /* !BN_LLONG */ |
383 | BN_ULONG t2l, t2h; |
384 | |
385 | q = bn_div_words(n0, n1, d0); |
386 | # ifndef REMAINDER_IS_ALREADY_CALCULATED |
387 | rem = (n1 - q * d0) & BN_MASK2; |
388 | # endif |
389 | |
390 | # if defined(BN_UMULT_LOHI) |
391 | BN_UMULT_LOHI(t2l, t2h, d1, q); |
392 | # elif defined(BN_UMULT_HIGH) |
393 | t2l = d1 * q; |
394 | t2h = BN_UMULT_HIGH(d1, q); |
395 | # else |
396 | { |
397 | BN_ULONG ql, qh; |
398 | t2l = LBITS(d1); |
399 | t2h = HBITS(d1); |
400 | ql = LBITS(q); |
401 | qh = HBITS(q); |
402 | mul64(t2l, t2h, ql, qh); /* t2=(BN_ULLONG)d1*q; */ |
403 | } |
404 | # endif |
405 | |
406 | for (;;) { |
407 | if ((t2h < rem) || ((t2h == rem) && (t2l <= n2))) |
408 | break; |
409 | q--; |
410 | rem += d0; |
411 | if (rem < d0) |
412 | break; /* don't let rem overflow */ |
413 | if (t2l < d1) |
414 | t2h--; |
415 | t2l -= d1; |
416 | } |
417 | # endif /* !BN_LLONG */ |
418 | } |
419 | # endif /* !BN_DIV3W */ |
420 | |
421 | l0 = bn_mul_words(tmp->d, sdiv->d, div_n, q); |
422 | tmp->d[div_n] = l0; |
423 | wnum--; |
424 | /* |
425 | * ignore top values of the bignums just sub the two BN_ULONG arrays |
426 | * with bn_sub_words |
427 | */ |
428 | l0 = bn_sub_words(wnum, wnum, tmp->d, div_n + 1); |
429 | q -= l0; |
430 | /* |
431 | * Note: As we have considered only the leading two BN_ULONGs in |
432 | * the calculation of q, sdiv * q might be greater than wnum (but |
433 | * then (q-1) * sdiv is less or equal than wnum) |
434 | */ |
435 | for (l0 = 0 - l0, j = 0; j < div_n; j++) |
436 | tmp->d[j] = sdiv->d[j] & l0; |
437 | l0 = bn_add_words(wnum, wnum, tmp->d, div_n); |
438 | (*wnumtop) += l0; |
439 | assert((*wnumtop) == 0); |
440 | |
441 | /* store part of the result */ |
442 | *--resp = q; |
443 | } |
444 | /* snum holds remainder, it's as wide as divisor */ |
445 | snum->neg = num->neg; |
446 | snum->top = div_n; |
447 | snum->flags |= BN_FLG_FIXED_TOP; |
448 | if (rm != NULL) |
449 | bn_rshift_fixed_top(rm, snum, norm_shift); |
450 | BN_CTX_end(ctx); |
451 | return 1; |
452 | err: |
453 | bn_check_top(rm); |
454 | BN_CTX_end(ctx); |
455 | return 0; |
456 | } |
457 | #endif |
458 | |