/src/boringssl/crypto/fipsmodule/bn/div.c.inc
Line | Count | Source (jump to first uncovered line) |
1 | | /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) |
2 | | * All rights reserved. |
3 | | * |
4 | | * This package is an SSL implementation written |
5 | | * by Eric Young (eay@cryptsoft.com). |
6 | | * The implementation was written so as to conform with Netscapes SSL. |
7 | | * |
8 | | * This library is free for commercial and non-commercial use as long as |
9 | | * the following conditions are aheared to. The following conditions |
10 | | * apply to all code found in this distribution, be it the RC4, RSA, |
11 | | * lhash, DES, etc., code; not just the SSL code. The SSL documentation |
12 | | * included with this distribution is covered by the same copyright terms |
13 | | * except that the holder is Tim Hudson (tjh@cryptsoft.com). |
14 | | * |
15 | | * Copyright remains Eric Young's, and as such any Copyright notices in |
16 | | * the code are not to be removed. |
17 | | * If this package is used in a product, Eric Young should be given attribution |
18 | | * as the author of the parts of the library used. |
19 | | * This can be in the form of a textual message at program startup or |
20 | | * in documentation (online or textual) provided with the package. |
21 | | * |
22 | | * Redistribution and use in source and binary forms, with or without |
23 | | * modification, are permitted provided that the following conditions |
24 | | * are met: |
25 | | * 1. Redistributions of source code must retain the copyright |
26 | | * notice, this list of conditions and the following disclaimer. |
27 | | * 2. Redistributions in binary form must reproduce the above copyright |
28 | | * notice, this list of conditions and the following disclaimer in the |
29 | | * documentation and/or other materials provided with the distribution. |
30 | | * 3. All advertising materials mentioning features or use of this software |
31 | | * must display the following acknowledgement: |
32 | | * "This product includes cryptographic software written by |
33 | | * Eric Young (eay@cryptsoft.com)" |
34 | | * The word 'cryptographic' can be left out if the rouines from the library |
35 | | * being used are not cryptographic related :-). |
36 | | * 4. If you include any Windows specific code (or a derivative thereof) from |
37 | | * the apps directory (application code) you must include an acknowledgement: |
38 | | * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" |
39 | | * |
40 | | * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND |
41 | | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
42 | | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
43 | | * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE |
44 | | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL |
45 | | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS |
46 | | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
47 | | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT |
48 | | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY |
49 | | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF |
50 | | * SUCH DAMAGE. |
51 | | * |
52 | | * The licence and distribution terms for any publically available version or |
53 | | * derivative of this code cannot be changed. i.e. this code cannot simply be |
54 | | * copied and put under another distribution licence |
55 | | * [including the GNU Public Licence.] */ |
56 | | |
57 | | #include <openssl/bn.h> |
58 | | |
59 | | #include <assert.h> |
60 | | #include <limits.h> |
61 | | |
62 | | #include <openssl/err.h> |
63 | | |
64 | | #include "internal.h" |
65 | | |
66 | | |
67 | | // bn_div_words divides a double-width |h|,|l| by |d| and returns the result, |
68 | | // which must fit in a |BN_ULONG|. |
69 | | OPENSSL_UNUSED static BN_ULONG bn_div_words(BN_ULONG h, BN_ULONG l, |
70 | 0 | BN_ULONG d) { |
71 | 0 | BN_ULONG dh, dl, q, ret = 0, th, tl, t; |
72 | 0 | int i, count = 2; |
73 | 0 |
|
74 | 0 | if (d == 0) { |
75 | 0 | return BN_MASK2; |
76 | 0 | } |
77 | 0 |
|
78 | 0 | i = BN_num_bits_word(d); |
79 | 0 | assert((i == BN_BITS2) || (h <= (BN_ULONG)1 << i)); |
80 | 0 |
|
81 | 0 | i = BN_BITS2 - i; |
82 | 0 | if (h >= d) { |
83 | 0 | h -= d; |
84 | 0 | } |
85 | 0 |
|
86 | 0 | if (i) { |
87 | 0 | d <<= i; |
88 | 0 | h = (h << i) | (l >> (BN_BITS2 - i)); |
89 | 0 | l <<= i; |
90 | 0 | } |
91 | 0 | dh = (d & BN_MASK2h) >> BN_BITS4; |
92 | 0 | dl = (d & BN_MASK2l); |
93 | 0 | for (;;) { |
94 | 0 | if ((h >> BN_BITS4) == dh) { |
95 | 0 | q = BN_MASK2l; |
96 | 0 | } else { |
97 | 0 | q = h / dh; |
98 | 0 | } |
99 | 0 |
|
100 | 0 | th = q * dh; |
101 | 0 | tl = dl * q; |
102 | 0 | for (;;) { |
103 | 0 | t = h - th; |
104 | 0 | if ((t & BN_MASK2h) || |
105 | 0 | ((tl) <= ((t << BN_BITS4) | ((l & BN_MASK2h) >> BN_BITS4)))) { |
106 | 0 | break; |
107 | 0 | } |
108 | 0 | q--; |
109 | 0 | th -= dh; |
110 | 0 | tl -= dl; |
111 | 0 | } |
112 | 0 | t = (tl >> BN_BITS4); |
113 | 0 | tl = (tl << BN_BITS4) & BN_MASK2h; |
114 | 0 | th += t; |
115 | 0 |
|
116 | 0 | if (l < tl) { |
117 | 0 | th++; |
118 | 0 | } |
119 | 0 | l -= tl; |
120 | 0 | if (h < th) { |
121 | 0 | h += d; |
122 | 0 | q--; |
123 | 0 | } |
124 | 0 | h -= th; |
125 | 0 |
|
126 | 0 | if (--count == 0) { |
127 | 0 | break; |
128 | 0 | } |
129 | 0 |
|
130 | 0 | ret = q << BN_BITS4; |
131 | 0 | h = (h << BN_BITS4) | (l >> BN_BITS4); |
132 | 0 | l = (l & BN_MASK2l) << BN_BITS4; |
133 | 0 | } |
134 | 0 |
|
135 | 0 | ret |= q; |
136 | 0 | return ret; |
137 | 0 | } |
138 | | |
139 | | static inline void bn_div_rem_words(BN_ULONG *quotient_out, BN_ULONG *rem_out, |
140 | 1.15M | BN_ULONG n0, BN_ULONG n1, BN_ULONG d0) { |
141 | | // GCC and Clang generate function calls to |__udivdi3| and |__umoddi3| when |
142 | | // the |BN_ULLONG|-based C code is used. |
143 | | // |
144 | | // GCC bugs: |
145 | | // * https://gcc.gnu.org/bugzilla/show_bug.cgi?id=14224 |
146 | | // * https://gcc.gnu.org/bugzilla/show_bug.cgi?id=43721 |
147 | | // * https://gcc.gnu.org/bugzilla/show_bug.cgi?id=54183 |
148 | | // * https://gcc.gnu.org/bugzilla/show_bug.cgi?id=58897 |
149 | | // * https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65668 |
150 | | // |
151 | | // Clang bugs: |
152 | | // * https://github.com/llvm/llvm-project/issues/6769 |
153 | | // * https://github.com/llvm/llvm-project/issues/12790 |
154 | | // |
155 | | // These is specific to x86 and x86_64; Arm and RISC-V do not have double-wide |
156 | | // division instructions. |
157 | | #if defined(BN_CAN_USE_INLINE_ASM) && defined(OPENSSL_X86) |
158 | | __asm__ volatile("divl %4" |
159 | | : "=a"(*quotient_out), "=d"(*rem_out) |
160 | | : "a"(n1), "d"(n0), "rm"(d0) |
161 | | : "cc"); |
162 | | #elif defined(BN_CAN_USE_INLINE_ASM) && defined(OPENSSL_X86_64) |
163 | | __asm__ volatile("divq %4" |
164 | | : "=a"(*quotient_out), "=d"(*rem_out) |
165 | | : "a"(n1), "d"(n0), "rm"(d0) |
166 | | : "cc"); |
167 | | #else |
168 | | #if defined(BN_CAN_DIVIDE_ULLONG) |
169 | 577k | BN_ULLONG n = (((BN_ULLONG)n0) << BN_BITS2) | n1; |
170 | | *quotient_out = (BN_ULONG)(n / d0); |
171 | | #else |
172 | | *quotient_out = bn_div_words(n0, n1, d0); |
173 | | #endif |
174 | | *rem_out = n1 - (*quotient_out * d0); |
175 | | #endif |
176 | 1.15M | } Line | Count | Source | 140 | 577k | BN_ULONG n0, BN_ULONG n1, BN_ULONG d0) { | 141 | | // GCC and Clang generate function calls to |__udivdi3| and |__umoddi3| when | 142 | | // the |BN_ULLONG|-based C code is used. | 143 | | // | 144 | | // GCC bugs: | 145 | | // * https://gcc.gnu.org/bugzilla/show_bug.cgi?id=14224 | 146 | | // * https://gcc.gnu.org/bugzilla/show_bug.cgi?id=43721 | 147 | | // * https://gcc.gnu.org/bugzilla/show_bug.cgi?id=54183 | 148 | | // * https://gcc.gnu.org/bugzilla/show_bug.cgi?id=58897 | 149 | | // * https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65668 | 150 | | // | 151 | | // Clang bugs: | 152 | | // * https://github.com/llvm/llvm-project/issues/6769 | 153 | | // * https://github.com/llvm/llvm-project/issues/12790 | 154 | | // | 155 | | // These is specific to x86 and x86_64; Arm and RISC-V do not have double-wide | 156 | | // division instructions. | 157 | | #if defined(BN_CAN_USE_INLINE_ASM) && defined(OPENSSL_X86) | 158 | | __asm__ volatile("divl %4" | 159 | | : "=a"(*quotient_out), "=d"(*rem_out) | 160 | | : "a"(n1), "d"(n0), "rm"(d0) | 161 | | : "cc"); | 162 | | #elif defined(BN_CAN_USE_INLINE_ASM) && defined(OPENSSL_X86_64) | 163 | | __asm__ volatile("divq %4" | 164 | | : "=a"(*quotient_out), "=d"(*rem_out) | 165 | | : "a"(n1), "d"(n0), "rm"(d0) | 166 | | : "cc"); | 167 | | #else | 168 | 577k | #if defined(BN_CAN_DIVIDE_ULLONG) | 169 | 577k | BN_ULLONG n = (((BN_ULLONG)n0) << BN_BITS2) | n1; | 170 | 577k | *quotient_out = (BN_ULONG)(n / d0); | 171 | | #else | 172 | | *quotient_out = bn_div_words(n0, n1, d0); | 173 | | #endif | 174 | 577k | *rem_out = n1 - (*quotient_out * d0); | 175 | 577k | #endif | 176 | 577k | } |
Line | Count | Source | 140 | 577k | BN_ULONG n0, BN_ULONG n1, BN_ULONG d0) { | 141 | | // GCC and Clang generate function calls to |__udivdi3| and |__umoddi3| when | 142 | | // the |BN_ULLONG|-based C code is used. | 143 | | // | 144 | | // GCC bugs: | 145 | | // * https://gcc.gnu.org/bugzilla/show_bug.cgi?id=14224 | 146 | | // * https://gcc.gnu.org/bugzilla/show_bug.cgi?id=43721 | 147 | | // * https://gcc.gnu.org/bugzilla/show_bug.cgi?id=54183 | 148 | | // * https://gcc.gnu.org/bugzilla/show_bug.cgi?id=58897 | 149 | | // * https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65668 | 150 | | // | 151 | | // Clang bugs: | 152 | | // * https://github.com/llvm/llvm-project/issues/6769 | 153 | | // * https://github.com/llvm/llvm-project/issues/12790 | 154 | | // | 155 | | // These is specific to x86 and x86_64; Arm and RISC-V do not have double-wide | 156 | | // division instructions. | 157 | | #if defined(BN_CAN_USE_INLINE_ASM) && defined(OPENSSL_X86) | 158 | | __asm__ volatile("divl %4" | 159 | | : "=a"(*quotient_out), "=d"(*rem_out) | 160 | | : "a"(n1), "d"(n0), "rm"(d0) | 161 | | : "cc"); | 162 | | #elif defined(BN_CAN_USE_INLINE_ASM) && defined(OPENSSL_X86_64) | 163 | 577k | __asm__ volatile("divq %4" | 164 | 577k | : "=a"(*quotient_out), "=d"(*rem_out) | 165 | 577k | : "a"(n1), "d"(n0), "rm"(d0) | 166 | 577k | : "cc"); | 167 | | #else | 168 | | #if defined(BN_CAN_DIVIDE_ULLONG) | 169 | | BN_ULLONG n = (((BN_ULLONG)n0) << BN_BITS2) | n1; | 170 | | *quotient_out = (BN_ULONG)(n / d0); | 171 | | #else | 172 | | *quotient_out = bn_div_words(n0, n1, d0); | 173 | | #endif | 174 | | *rem_out = n1 - (*quotient_out * d0); | 175 | | #endif | 176 | 577k | } |
|
177 | | |
178 | | int BN_div(BIGNUM *quotient, BIGNUM *rem, const BIGNUM *numerator, |
179 | 55.8k | const BIGNUM *divisor, BN_CTX *ctx) { |
180 | | // This function implements long division, per Knuth, The Art of Computer |
181 | | // Programming, Volume 2, Chapter 4.3.1, Algorithm D. This algorithm only |
182 | | // divides non-negative integers, but we round towards zero, so we divide |
183 | | // absolute values and adjust the signs separately. |
184 | | // |
185 | | // Inputs to this function are assumed public and may be leaked by timing and |
186 | | // cache side channels. Division with secret inputs should use other |
187 | | // implementation strategies such as Montgomery reduction. |
188 | 55.8k | if (BN_is_zero(divisor)) { |
189 | 69 | OPENSSL_PUT_ERROR(BN, BN_R_DIV_BY_ZERO); |
190 | 69 | return 0; |
191 | 69 | } |
192 | | |
193 | 55.7k | BN_CTX_start(ctx); |
194 | 55.7k | BIGNUM *tmp = BN_CTX_get(ctx); |
195 | 55.7k | BIGNUM *snum = BN_CTX_get(ctx); |
196 | 55.7k | BIGNUM *sdiv = BN_CTX_get(ctx); |
197 | 55.7k | BIGNUM *res = quotient == NULL ? BN_CTX_get(ctx) : quotient; |
198 | 55.7k | if (tmp == NULL || snum == NULL || sdiv == NULL || res == NULL) { |
199 | 0 | goto err; |
200 | 0 | } |
201 | | |
202 | | // Knuth step D1: Normalise the numbers such that the divisor's MSB is set. |
203 | | // This ensures, in Knuth's terminology, that v1 >= b/2, needed for the |
204 | | // quotient estimation step. |
205 | 55.7k | int norm_shift = BN_BITS2 - (BN_num_bits(divisor) % BN_BITS2); |
206 | 55.7k | if (!BN_lshift(sdiv, divisor, norm_shift) || |
207 | 55.7k | !BN_lshift(snum, numerator, norm_shift)) { |
208 | 0 | goto err; |
209 | 0 | } |
210 | | |
211 | | // This algorithm relies on |sdiv| being minimal width. We do not use this |
212 | | // function on secret inputs, so leaking this is fine. Also minimize |snum| to |
213 | | // avoid looping on leading zeros, as we're not trying to be leak-free. |
214 | 55.7k | bn_set_minimal_width(sdiv); |
215 | 55.7k | bn_set_minimal_width(snum); |
216 | 55.7k | int div_n = sdiv->width; |
217 | 55.7k | const BN_ULONG d0 = sdiv->d[div_n - 1]; |
218 | 55.7k | const BN_ULONG d1 = (div_n == 1) ? 0 : sdiv->d[div_n - 2]; |
219 | 55.7k | assert(d0 & (((BN_ULONG)1) << (BN_BITS2 - 1))); |
220 | | |
221 | | // Extend |snum| with zeros to satisfy the long division invariants: |
222 | | // - |snum| must have at least |div_n| + 1 words. |
223 | | // - |snum|'s most significant word must be zero to guarantee the first loop |
224 | | // iteration works with a prefix greater than |sdiv|. (This is the extra u0 |
225 | | // digit in Knuth step D1.) |
226 | 55.7k | int num_n = snum->width <= div_n ? div_n + 1 : snum->width + 1; |
227 | 55.7k | if (!bn_resize_words(snum, num_n)) { |
228 | 0 | goto err; |
229 | 0 | } |
230 | | |
231 | | // Knuth step D2: The quotient's width is the difference between numerator and |
232 | | // denominator. Also set up its sign and size a temporary for the loop. |
233 | 55.7k | int loop = num_n - div_n; |
234 | 55.7k | res->neg = snum->neg ^ sdiv->neg; |
235 | 55.7k | if (!bn_wexpand(res, loop) || // |
236 | 55.7k | !bn_wexpand(tmp, div_n + 1)) { |
237 | 0 | goto err; |
238 | 0 | } |
239 | 55.7k | res->width = loop; |
240 | | |
241 | | // Knuth steps D2 through D7: Compute the quotient with a word-by-word long |
242 | | // division. Note that Knuth indexes words from most to least significant, so |
243 | | // our index is reversed. Each loop iteration computes res->d[i] of the |
244 | | // quotient and updates snum with the running remainder. Before each loop |
245 | | // iteration, the div_n words beginning at snum->d[i+1] must be less than |
246 | | // snum. |
247 | 227k | for (int i = loop - 1; i >= 0; i--) { |
248 | | // The next word of the quotient, q, is floor(wnum / sdiv), where wnum is |
249 | | // the div_n + 1 words beginning at snum->d[i]. i starts at |
250 | | // num_n - div_n - 1, so there are at least div_n + 1 words available. |
251 | | // |
252 | | // Knuth step D3: Compute q', an estimate of q by looking at the top words |
253 | | // of wnum and sdiv. We must estimate such that q' = q or q' = q + 1. |
254 | 171k | BN_ULONG q, rm = 0; |
255 | 171k | BN_ULONG *wnum = snum->d + i; |
256 | 171k | BN_ULONG n0 = wnum[div_n]; |
257 | 171k | BN_ULONG n1 = wnum[div_n - 1]; |
258 | 171k | if (n0 == d0) { |
259 | | // Estimate q' = b - 1, where b is the base. |
260 | 37 | q = BN_MASK2; |
261 | | // Knuth also runs the fixup routine in this case, but this would require |
262 | | // computing rm and is unnecessary. q' is already close enough. That is, |
263 | | // the true quotient, q is either b - 1 or b - 2. |
264 | | // |
265 | | // By the loop invariant, q <= b - 1, so we must show that q >= b - 2. We |
266 | | // do this by showing wnum / sdiv >= b - 2. Suppose wnum / sdiv < b - 2. |
267 | | // wnum and sdiv have the same most significant word, so: |
268 | | // |
269 | | // wnum >= n0 * b^div_n |
270 | | // sdiv < (n0 + 1) * b^(d_div - 1) |
271 | | // |
272 | | // Thus: |
273 | | // |
274 | | // b - 2 > wnum / sdiv |
275 | | // > (n0 * b^div_n) / (n0 + 1) * b^(div_n - 1) |
276 | | // = (n0 * b) / (n0 + 1) |
277 | | // |
278 | | // (n0 + 1) * (b - 2) > n0 * b |
279 | | // n0 * b + b - 2 * n0 - 2 > n0 * b |
280 | | // b - 2 > 2 * n0 |
281 | | // b/2 - 1 > n0 |
282 | | // |
283 | | // This contradicts the normalization condition, so q >= b - 2 and our |
284 | | // estimate is close enough. |
285 | 171k | } else { |
286 | | // Estimate q' = floor(n0n1 / d0). Per Theorem B, q' - 2 <= q <= q', which |
287 | | // is slightly outside of our bounds. |
288 | 171k | assert(n0 < d0); |
289 | 171k | bn_div_rem_words(&q, &rm, n0, n1, d0); |
290 | | |
291 | | // Fix the estimate by examining one more word and adjusting q' as needed. |
292 | | // This is the second half of step D3 and is sufficient per exercises 19, |
293 | | // 20, and 21. Although only one iteration is needed to correct q + 2 to |
294 | | // q + 1, Knuth uses a loop. A loop will often also correct q + 1 to q, |
295 | | // saving the slightly more expensive underflow handling below. |
296 | 171k | if (div_n > 1) { |
297 | 169k | BN_ULONG n2 = wnum[div_n - 2]; |
298 | 169k | #ifdef BN_ULLONG |
299 | 169k | BN_ULLONG t2 = (BN_ULLONG)d1 * q; |
300 | 178k | for (;;) { |
301 | 178k | if (t2 <= ((((BN_ULLONG)rm) << BN_BITS2) | n2)) { |
302 | 160k | break; |
303 | 160k | } |
304 | 17.4k | q--; |
305 | 17.4k | rm += d0; |
306 | 17.4k | if (rm < d0) { |
307 | | // If rm overflows, the true value exceeds BN_ULONG and the next |
308 | | // t2 comparison should exit the loop. |
309 | 8.33k | break; |
310 | 8.33k | } |
311 | 9.16k | t2 -= d1; |
312 | 9.16k | } |
313 | | #else // !BN_ULLONG |
314 | | BN_ULONG t2l, t2h; |
315 | | BN_UMULT_LOHI(t2l, t2h, d1, q); |
316 | | for (;;) { |
317 | | if (t2h < rm || (t2h == rm && t2l <= n2)) { |
318 | | break; |
319 | | } |
320 | | q--; |
321 | | rm += d0; |
322 | | if (rm < d0) { |
323 | | // If rm overflows, the true value exceeds BN_ULONG and the next |
324 | | // t2 comparison should exit the loop. |
325 | | break; |
326 | | } |
327 | | if (t2l < d1) { |
328 | | t2h--; |
329 | | } |
330 | | t2l -= d1; |
331 | | } |
332 | | #endif // !BN_ULLONG |
333 | 169k | } |
334 | 171k | } |
335 | | |
336 | | // Knuth step D4 through D6: Now q' = q or q' = q + 1, and |
337 | | // -sdiv < wnum - sdiv * q < sdiv. If q' = q + 1, the subtraction will |
338 | | // underflow, and we fix it up below. |
339 | 171k | tmp->d[div_n] = bn_mul_words(tmp->d, sdiv->d, div_n, q); |
340 | 171k | if (bn_sub_words(wnum, wnum, tmp->d, div_n + 1)) { |
341 | 219 | q--; |
342 | | // The final addition is expected to overflow, canceling the underflow. |
343 | 219 | wnum[div_n] += bn_add_words(wnum, wnum, sdiv->d, div_n); |
344 | 219 | } |
345 | | |
346 | | // q is now correct, and wnum has been updated to the running remainder. |
347 | 171k | res->d[i] = q; |
348 | 171k | } |
349 | | |
350 | | // Trim leading zeros and correct any negative zeros. |
351 | 55.7k | bn_set_minimal_width(snum); |
352 | 55.7k | bn_set_minimal_width(res); |
353 | | |
354 | | // Knuth step D8: Unnormalize. snum now contains the remainder. |
355 | 55.7k | if (rem != NULL && !BN_rshift(rem, snum, norm_shift)) { |
356 | 0 | goto err; |
357 | 0 | } |
358 | | |
359 | 55.7k | BN_CTX_end(ctx); |
360 | 55.7k | return 1; |
361 | | |
362 | 0 | err: |
363 | 0 | BN_CTX_end(ctx); |
364 | 0 | return 0; |
365 | 55.7k | } |
366 | | |
367 | 51.9k | int BN_nnmod(BIGNUM *r, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx) { |
368 | 51.9k | if (!(BN_mod(r, m, d, ctx))) { |
369 | 20 | return 0; |
370 | 20 | } |
371 | 51.9k | if (!r->neg) { |
372 | 51.8k | return 1; |
373 | 51.8k | } |
374 | | |
375 | | // now -d < r < 0, so we have to set r := r + d. Ignoring the sign bits, this |
376 | | // is r = d - r. |
377 | 48 | return BN_usub(r, d, r); |
378 | 51.9k | } |
379 | | |
380 | | BN_ULONG bn_reduce_once(BN_ULONG *r, const BN_ULONG *a, BN_ULONG carry, |
381 | 2.47M | const BN_ULONG *m, size_t num) { |
382 | 2.47M | assert(r != a); |
383 | | // |r| = |a| - |m|. |bn_sub_words| performs the bulk of the subtraction, and |
384 | | // then we apply the borrow to |carry|. |
385 | 2.47M | carry -= bn_sub_words(r, a, m, num); |
386 | | // We know 0 <= |a| < 2*|m|, so -|m| <= |r| < |m|. |
387 | | // |
388 | | // If 0 <= |r| < |m|, |r| fits in |num| words and |carry| is zero. We then |
389 | | // wish to select |r| as the answer. Otherwise -m <= r < 0 and we wish to |
390 | | // return |r| + |m|, or |a|. |carry| must then be -1 or all ones. In both |
391 | | // cases, |carry| is a suitable input to |bn_select_words|. |
392 | | // |
393 | | // Although |carry| may be one if it was one on input and |bn_sub_words| |
394 | | // returns zero, this would give |r| > |m|, violating our input assumptions. |
395 | 2.47M | declassify_assert(carry + 1 <= 1); |
396 | 2.47M | bn_select_words(r, carry, a /* r < 0 */, r /* r >= 0 */, num); |
397 | 2.47M | return carry; |
398 | 2.47M | } |
399 | | |
400 | | BN_ULONG bn_reduce_once_in_place(BN_ULONG *r, BN_ULONG carry, const BN_ULONG *m, |
401 | 563k | BN_ULONG *tmp, size_t num) { |
402 | | // See |bn_reduce_once| for why this logic works. |
403 | 563k | carry -= bn_sub_words(tmp, r, m, num); |
404 | 563k | declassify_assert(carry + 1 <= 1); |
405 | 563k | bn_select_words(r, carry, r /* tmp < 0 */, tmp /* tmp >= 0 */, num); |
406 | 563k | return carry; |
407 | 563k | } |
408 | | |
409 | | void bn_mod_sub_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, |
410 | 151k | const BN_ULONG *m, BN_ULONG *tmp, size_t num) { |
411 | | // r = a - b |
412 | 151k | BN_ULONG borrow = bn_sub_words(r, a, b, num); |
413 | | // tmp = a - b + m |
414 | 151k | bn_add_words(tmp, r, m, num); |
415 | 151k | bn_select_words(r, 0 - borrow, tmp /* r < 0 */, r /* r >= 0 */, num); |
416 | 151k | } |
417 | | |
418 | | void bn_mod_add_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, |
419 | 249k | const BN_ULONG *m, BN_ULONG *tmp, size_t num) { |
420 | 249k | BN_ULONG carry = bn_add_words(r, a, b, num); |
421 | 249k | bn_reduce_once_in_place(r, carry, m, tmp, num); |
422 | 249k | } |
423 | | |
424 | | int bn_div_consttime(BIGNUM *quotient, BIGNUM *remainder, |
425 | | const BIGNUM *numerator, const BIGNUM *divisor, |
426 | 52 | unsigned divisor_min_bits, BN_CTX *ctx) { |
427 | 52 | if (BN_is_negative(numerator) || BN_is_negative(divisor)) { |
428 | 0 | OPENSSL_PUT_ERROR(BN, BN_R_NEGATIVE_NUMBER); |
429 | 0 | return 0; |
430 | 0 | } |
431 | 52 | if (BN_is_zero(divisor)) { |
432 | 0 | OPENSSL_PUT_ERROR(BN, BN_R_DIV_BY_ZERO); |
433 | 0 | return 0; |
434 | 0 | } |
435 | | |
436 | | // This function implements long division in binary. It is not very efficient, |
437 | | // but it is simple, easy to make constant-time, and performant enough for RSA |
438 | | // key generation. |
439 | | |
440 | 52 | int ret = 0; |
441 | 52 | BN_CTX_start(ctx); |
442 | 52 | BIGNUM *q = quotient, *r = remainder; |
443 | 52 | if (quotient == NULL || quotient == numerator || quotient == divisor) { |
444 | 34 | q = BN_CTX_get(ctx); |
445 | 34 | } |
446 | 52 | if (remainder == NULL || remainder == numerator || remainder == divisor) { |
447 | 44 | r = BN_CTX_get(ctx); |
448 | 44 | } |
449 | 52 | BIGNUM *tmp = BN_CTX_get(ctx); |
450 | 52 | if (q == NULL || r == NULL || tmp == NULL || |
451 | 52 | !bn_wexpand(q, numerator->width) || |
452 | 52 | !bn_wexpand(r, divisor->width) || |
453 | 52 | !bn_wexpand(tmp, divisor->width)) { |
454 | 0 | goto err; |
455 | 0 | } |
456 | | |
457 | 52 | OPENSSL_memset(q->d, 0, numerator->width * sizeof(BN_ULONG)); |
458 | 52 | q->width = numerator->width; |
459 | 52 | q->neg = 0; |
460 | | |
461 | 52 | OPENSSL_memset(r->d, 0, divisor->width * sizeof(BN_ULONG)); |
462 | 52 | r->width = divisor->width; |
463 | 52 | r->neg = 0; |
464 | | |
465 | | // Incorporate |numerator| into |r|, one bit at a time, reducing after each |
466 | | // step. We maintain the invariant that |0 <= r < divisor| and |
467 | | // |q * divisor + r = n| where |n| is the portion of |numerator| incorporated |
468 | | // so far. |
469 | | // |
470 | | // First, we short-circuit the loop: if we know |divisor| has at least |
471 | | // |divisor_min_bits| bits, the top |divisor_min_bits - 1| can be incorporated |
472 | | // without reductions. This significantly speeds up |RSA_check_key|. For |
473 | | // simplicity, we round down to a whole number of words. |
474 | 52 | declassify_assert(divisor_min_bits <= BN_num_bits(divisor)); |
475 | 52 | int initial_words = 0; |
476 | 52 | if (divisor_min_bits > 0) { |
477 | 17 | initial_words = (divisor_min_bits - 1) / BN_BITS2; |
478 | 17 | if (initial_words > numerator->width) { |
479 | 5 | initial_words = numerator->width; |
480 | 5 | } |
481 | 17 | OPENSSL_memcpy(r->d, numerator->d + numerator->width - initial_words, |
482 | 17 | initial_words * sizeof(BN_ULONG)); |
483 | 17 | } |
484 | | |
485 | 4.94k | for (int i = numerator->width - initial_words - 1; i >= 0; i--) { |
486 | 318k | for (int bit = BN_BITS2 - 1; bit >= 0; bit--) { |
487 | | // Incorporate the next bit of the numerator, by computing |
488 | | // r = 2*r or 2*r + 1. Note the result fits in one more word. We store the |
489 | | // extra word in |carry|. |
490 | 313k | BN_ULONG carry = bn_add_words(r->d, r->d, r->d, divisor->width); |
491 | 313k | r->d[0] |= (numerator->d[i] >> bit) & 1; |
492 | | // |r| was previously fully-reduced, so we know: |
493 | | // 2*0 <= r <= 2*(divisor-1) + 1 |
494 | | // 0 <= r <= 2*divisor - 1 < 2*divisor. |
495 | | // Thus |r| satisfies the preconditions for |bn_reduce_once_in_place|. |
496 | 313k | BN_ULONG subtracted = bn_reduce_once_in_place(r->d, carry, divisor->d, |
497 | 313k | tmp->d, divisor->width); |
498 | | // The corresponding bit of the quotient is set iff we needed to subtract. |
499 | 313k | q->d[i] |= (~subtracted & 1) << bit; |
500 | 313k | } |
501 | 4.89k | } |
502 | | |
503 | 52 | if ((quotient != NULL && !BN_copy(quotient, q)) || |
504 | 52 | (remainder != NULL && !BN_copy(remainder, r))) { |
505 | 0 | goto err; |
506 | 0 | } |
507 | | |
508 | 52 | ret = 1; |
509 | | |
510 | 52 | err: |
511 | 52 | BN_CTX_end(ctx); |
512 | 52 | return ret; |
513 | 52 | } |
514 | | |
515 | 862 | static BIGNUM *bn_scratch_space_from_ctx(size_t width, BN_CTX *ctx) { |
516 | 862 | BIGNUM *ret = BN_CTX_get(ctx); |
517 | 862 | if (ret == NULL || |
518 | 862 | !bn_wexpand(ret, width)) { |
519 | 0 | return NULL; |
520 | 0 | } |
521 | 862 | ret->neg = 0; |
522 | 862 | ret->width = (int)width; |
523 | 862 | return ret; |
524 | 862 | } |
525 | | |
526 | | // bn_resized_from_ctx returns |bn| with width at least |width| or NULL on |
527 | | // error. This is so it may be used with low-level "words" functions. If |
528 | | // necessary, it allocates a new |BIGNUM| with a lifetime of the current scope |
529 | | // in |ctx|, so the caller does not need to explicitly free it. |bn| must fit in |
530 | | // |width| words. |
531 | | static const BIGNUM *bn_resized_from_ctx(const BIGNUM *bn, size_t width, |
532 | 52 | BN_CTX *ctx) { |
533 | 52 | if ((size_t)bn->width >= width) { |
534 | | // Any excess words must be zero. |
535 | 14 | assert(bn_fits_in_words(bn, width)); |
536 | 14 | return bn; |
537 | 14 | } |
538 | 38 | BIGNUM *ret = bn_scratch_space_from_ctx(width, ctx); |
539 | 38 | if (ret == NULL || |
540 | 38 | !BN_copy(ret, bn) || |
541 | 38 | !bn_resize_words(ret, width)) { |
542 | 0 | return NULL; |
543 | 0 | } |
544 | 38 | return ret; |
545 | 38 | } |
546 | | |
547 | | int BN_mod_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, |
548 | 89 | BN_CTX *ctx) { |
549 | 89 | if (!BN_add(r, a, b)) { |
550 | 0 | return 0; |
551 | 0 | } |
552 | 89 | return BN_nnmod(r, r, m, ctx); |
553 | 89 | } |
554 | | |
555 | | int BN_mod_add_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, |
556 | 7 | const BIGNUM *m) { |
557 | 7 | BN_CTX *ctx = BN_CTX_new(); |
558 | 7 | int ok = ctx != NULL && |
559 | 7 | bn_mod_add_consttime(r, a, b, m, ctx); |
560 | 7 | BN_CTX_free(ctx); |
561 | 7 | return ok; |
562 | 7 | } |
563 | | |
564 | | int bn_mod_add_consttime(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, |
565 | 7 | const BIGNUM *m, BN_CTX *ctx) { |
566 | 7 | BN_CTX_start(ctx); |
567 | 7 | a = bn_resized_from_ctx(a, m->width, ctx); |
568 | 7 | b = bn_resized_from_ctx(b, m->width, ctx); |
569 | 7 | BIGNUM *tmp = bn_scratch_space_from_ctx(m->width, ctx); |
570 | 7 | int ok = a != NULL && b != NULL && tmp != NULL && |
571 | 7 | bn_wexpand(r, m->width); |
572 | 7 | if (ok) { |
573 | 7 | bn_mod_add_words(r->d, a->d, b->d, m->d, tmp->d, m->width); |
574 | 7 | r->width = m->width; |
575 | 7 | r->neg = 0; |
576 | 7 | } |
577 | 7 | BN_CTX_end(ctx); |
578 | 7 | return ok; |
579 | 7 | } |
580 | | |
581 | | int BN_mod_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, |
582 | 143 | BN_CTX *ctx) { |
583 | 143 | if (!BN_sub(r, a, b)) { |
584 | 0 | return 0; |
585 | 0 | } |
586 | 143 | return BN_nnmod(r, r, m, ctx); |
587 | 143 | } |
588 | | |
589 | | int bn_mod_sub_consttime(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, |
590 | 19 | const BIGNUM *m, BN_CTX *ctx) { |
591 | 19 | BN_CTX_start(ctx); |
592 | 19 | a = bn_resized_from_ctx(a, m->width, ctx); |
593 | 19 | b = bn_resized_from_ctx(b, m->width, ctx); |
594 | 19 | BIGNUM *tmp = bn_scratch_space_from_ctx(m->width, ctx); |
595 | 19 | int ok = a != NULL && b != NULL && tmp != NULL && |
596 | 19 | bn_wexpand(r, m->width); |
597 | 19 | if (ok) { |
598 | 19 | bn_mod_sub_words(r->d, a->d, b->d, m->d, tmp->d, m->width); |
599 | 19 | r->width = m->width; |
600 | 19 | r->neg = 0; |
601 | 19 | } |
602 | 19 | BN_CTX_end(ctx); |
603 | 19 | return ok; |
604 | 19 | } |
605 | | |
606 | | int BN_mod_sub_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, |
607 | 19 | const BIGNUM *m) { |
608 | 19 | BN_CTX *ctx = BN_CTX_new(); |
609 | 19 | int ok = ctx != NULL && |
610 | 19 | bn_mod_sub_consttime(r, a, b, m, ctx); |
611 | 19 | BN_CTX_free(ctx); |
612 | 19 | return ok; |
613 | 19 | } |
614 | | |
615 | | int BN_mod_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, |
616 | 355k | BN_CTX *ctx) { |
617 | 355k | BIGNUM *t; |
618 | 355k | int ret = 0; |
619 | | |
620 | 355k | BN_CTX_start(ctx); |
621 | 355k | t = BN_CTX_get(ctx); |
622 | 355k | if (t == NULL) { |
623 | 0 | goto err; |
624 | 0 | } |
625 | | |
626 | 355k | if (a == b) { |
627 | 314k | if (!BN_sqr(t, a, ctx)) { |
628 | 0 | goto err; |
629 | 0 | } |
630 | 314k | } else { |
631 | 40.6k | if (!BN_mul(t, a, b, ctx)) { |
632 | 0 | goto err; |
633 | 0 | } |
634 | 40.6k | } |
635 | | |
636 | 355k | if (!BN_nnmod(r, t, m, ctx)) { |
637 | 29 | goto err; |
638 | 29 | } |
639 | | |
640 | 355k | ret = 1; |
641 | | |
642 | 355k | err: |
643 | 355k | BN_CTX_end(ctx); |
644 | 355k | return ret; |
645 | 355k | } |
646 | | |
647 | 952 | int BN_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx) { |
648 | 952 | if (!BN_sqr(r, a, ctx)) { |
649 | 0 | return 0; |
650 | 0 | } |
651 | | |
652 | | // r->neg == 0, thus we don't need BN_nnmod |
653 | 952 | return BN_mod(r, r, m, ctx); |
654 | 952 | } |
655 | | |
656 | | int BN_mod_lshift(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m, |
657 | 2 | BN_CTX *ctx) { |
658 | 2 | BIGNUM *abs_m = NULL; |
659 | 2 | int ret; |
660 | | |
661 | 2 | if (!BN_nnmod(r, a, m, ctx)) { |
662 | 0 | return 0; |
663 | 0 | } |
664 | | |
665 | 2 | if (m->neg) { |
666 | 0 | abs_m = BN_dup(m); |
667 | 0 | if (abs_m == NULL) { |
668 | 0 | return 0; |
669 | 0 | } |
670 | 0 | abs_m->neg = 0; |
671 | 0 | } |
672 | | |
673 | 2 | ret = bn_mod_lshift_consttime(r, r, n, (abs_m ? abs_m : m), ctx); |
674 | | |
675 | 2 | BN_free(abs_m); |
676 | 2 | return ret; |
677 | 2 | } |
678 | | |
679 | | int bn_mod_lshift_consttime(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m, |
680 | 798 | BN_CTX *ctx) { |
681 | 798 | if (!BN_copy(r, a) || |
682 | 798 | !bn_resize_words(r, m->width)) { |
683 | 0 | return 0; |
684 | 0 | } |
685 | | |
686 | 798 | BN_CTX_start(ctx); |
687 | 798 | BIGNUM *tmp = bn_scratch_space_from_ctx(m->width, ctx); |
688 | 798 | int ok = tmp != NULL; |
689 | 798 | if (ok) { |
690 | 30.7k | for (int i = 0; i < n; i++) { |
691 | 29.9k | bn_mod_add_words(r->d, r->d, r->d, m->d, tmp->d, m->width); |
692 | 29.9k | } |
693 | 798 | r->neg = 0; |
694 | 798 | } |
695 | 798 | BN_CTX_end(ctx); |
696 | 798 | return ok; |
697 | 798 | } |
698 | | |
699 | | int BN_mod_lshift_quick(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m) { |
700 | | BN_CTX *ctx = BN_CTX_new(); |
701 | | int ok = ctx != NULL && |
702 | | bn_mod_lshift_consttime(r, a, n, m, ctx); |
703 | | BN_CTX_free(ctx); |
704 | | return ok; |
705 | | } |
706 | | |
707 | 0 | int BN_mod_lshift1(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx) { |
708 | 0 | if (!BN_lshift1(r, a)) { |
709 | 0 | return 0; |
710 | 0 | } |
711 | | |
712 | 0 | return BN_nnmod(r, r, m, ctx); |
713 | 0 | } |
714 | | |
715 | | int bn_mod_lshift1_consttime(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, |
716 | 0 | BN_CTX *ctx) { |
717 | 0 | return bn_mod_add_consttime(r, a, a, m, ctx); |
718 | 0 | } |
719 | | |
720 | 0 | int BN_mod_lshift1_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *m) { |
721 | 0 | BN_CTX *ctx = BN_CTX_new(); |
722 | 0 | int ok = ctx != NULL && |
723 | 0 | bn_mod_lshift1_consttime(r, a, m, ctx); |
724 | 0 | BN_CTX_free(ctx); |
725 | 0 | return ok; |
726 | 0 | } |
727 | | |
728 | 9.91k | BN_ULONG BN_div_word(BIGNUM *a, BN_ULONG w) { |
729 | 9.91k | BN_ULONG ret = 0; |
730 | 9.91k | int i, j; |
731 | | |
732 | 9.91k | if (!w) { |
733 | | // actually this an error (division by zero) |
734 | 0 | return (BN_ULONG) - 1; |
735 | 0 | } |
736 | | |
737 | 9.91k | if (a->width == 0) { |
738 | 0 | return 0; |
739 | 0 | } |
740 | | |
741 | | // normalize input for |bn_div_rem_words|. |
742 | 9.91k | j = BN_BITS2 - BN_num_bits_word(w); |
743 | 9.91k | w <<= j; |
744 | 9.91k | if (!BN_lshift(a, a, j)) { |
745 | 0 | return (BN_ULONG) - 1; |
746 | 0 | } |
747 | | |
748 | 415k | for (i = a->width - 1; i >= 0; i--) { |
749 | 405k | BN_ULONG l = a->d[i]; |
750 | 405k | BN_ULONG d; |
751 | 405k | BN_ULONG unused_rem; |
752 | 405k | bn_div_rem_words(&d, &unused_rem, ret, l, w); |
753 | 405k | ret = l - (d * w); |
754 | 405k | a->d[i] = d; |
755 | 405k | } |
756 | | |
757 | 9.91k | bn_set_minimal_width(a); |
758 | 9.91k | ret >>= j; |
759 | 9.91k | return ret; |
760 | 9.91k | } |
761 | | |
762 | 0 | BN_ULONG BN_mod_word(const BIGNUM *a, BN_ULONG w) { |
763 | | #ifndef BN_CAN_DIVIDE_ULLONG |
764 | | BN_ULONG ret = 0; |
765 | | #else |
766 | 0 | BN_ULLONG ret = 0; |
767 | 0 | #endif |
768 | 0 | int i; |
769 | |
|
770 | 0 | if (w == 0) { |
771 | 0 | return (BN_ULONG) -1; |
772 | 0 | } |
773 | | |
774 | | #ifndef BN_CAN_DIVIDE_ULLONG |
775 | | // If |w| is too long and we don't have |BN_ULLONG| division then we need to |
776 | | // fall back to using |BN_div_word|. |
777 | | if (w > ((BN_ULONG)1 << BN_BITS4)) { |
778 | | BIGNUM *tmp = BN_dup(a); |
779 | | if (tmp == NULL) { |
780 | | return (BN_ULONG)-1; |
781 | | } |
782 | | ret = BN_div_word(tmp, w); |
783 | | BN_free(tmp); |
784 | | return ret; |
785 | | } |
786 | | #endif |
787 | | |
788 | 0 | for (i = a->width - 1; i >= 0; i--) { |
789 | | #ifndef BN_CAN_DIVIDE_ULLONG |
790 | | ret = ((ret << BN_BITS4) | ((a->d[i] >> BN_BITS4) & BN_MASK2l)) % w; |
791 | | ret = ((ret << BN_BITS4) | (a->d[i] & BN_MASK2l)) % w; |
792 | | #else |
793 | 0 | ret = (BN_ULLONG)(((ret << (BN_ULLONG)BN_BITS2) | a->d[i]) % (BN_ULLONG)w); |
794 | 0 | #endif |
795 | 0 | } |
796 | 0 | return (BN_ULONG)ret; |
797 | 0 | } |
798 | | |
799 | 0 | int BN_mod_pow2(BIGNUM *r, const BIGNUM *a, size_t e) { |
800 | 0 | if (e == 0 || a->width == 0) { |
801 | 0 | BN_zero(r); |
802 | 0 | return 1; |
803 | 0 | } |
804 | | |
805 | 0 | size_t num_words = 1 + ((e - 1) / BN_BITS2); |
806 | | |
807 | | // If |a| definitely has less than |e| bits, just BN_copy. |
808 | 0 | if ((size_t) a->width < num_words) { |
809 | 0 | return BN_copy(r, a) != NULL; |
810 | 0 | } |
811 | | |
812 | | // Otherwise, first make sure we have enough space in |r|. |
813 | | // Note that this will fail if num_words > INT_MAX. |
814 | 0 | if (!bn_wexpand(r, num_words)) { |
815 | 0 | return 0; |
816 | 0 | } |
817 | | |
818 | | // Copy the content of |a| into |r|. |
819 | 0 | OPENSSL_memcpy(r->d, a->d, num_words * sizeof(BN_ULONG)); |
820 | | |
821 | | // If |e| isn't word-aligned, we have to mask off some of our bits. |
822 | 0 | size_t top_word_exponent = e % (sizeof(BN_ULONG) * 8); |
823 | 0 | if (top_word_exponent != 0) { |
824 | 0 | r->d[num_words - 1] &= (((BN_ULONG) 1) << top_word_exponent) - 1; |
825 | 0 | } |
826 | | |
827 | | // Fill in the remaining fields of |r|. |
828 | 0 | r->neg = a->neg; |
829 | 0 | r->width = (int) num_words; |
830 | 0 | bn_set_minimal_width(r); |
831 | 0 | return 1; |
832 | 0 | } |
833 | | |
834 | 0 | int BN_nnmod_pow2(BIGNUM *r, const BIGNUM *a, size_t e) { |
835 | 0 | if (!BN_mod_pow2(r, a, e)) { |
836 | 0 | return 0; |
837 | 0 | } |
838 | | |
839 | | // If the returned value was non-negative, we're done. |
840 | 0 | if (BN_is_zero(r) || !r->neg) { |
841 | 0 | return 1; |
842 | 0 | } |
843 | | |
844 | 0 | size_t num_words = 1 + (e - 1) / BN_BITS2; |
845 | | |
846 | | // Expand |r| to the size of our modulus. |
847 | 0 | if (!bn_wexpand(r, num_words)) { |
848 | 0 | return 0; |
849 | 0 | } |
850 | | |
851 | | // Clear the upper words of |r|. |
852 | 0 | OPENSSL_memset(&r->d[r->width], 0, (num_words - r->width) * BN_BYTES); |
853 | | |
854 | | // Set parameters of |r|. |
855 | 0 | r->neg = 0; |
856 | 0 | r->width = (int) num_words; |
857 | | |
858 | | // Now, invert every word. The idea here is that we want to compute 2^e-|x|, |
859 | | // which is actually equivalent to the twos-complement representation of |x| |
860 | | // in |e| bits, which is -x = ~x + 1. |
861 | 0 | for (int i = 0; i < r->width; i++) { |
862 | 0 | r->d[i] = ~r->d[i]; |
863 | 0 | } |
864 | | |
865 | | // If our exponent doesn't span the top word, we have to mask the rest. |
866 | 0 | size_t top_word_exponent = e % BN_BITS2; |
867 | 0 | if (top_word_exponent != 0) { |
868 | 0 | r->d[r->width - 1] &= (((BN_ULONG) 1) << top_word_exponent) - 1; |
869 | 0 | } |
870 | | |
871 | | // Keep the minimal-width invariant for |BIGNUM|. |
872 | 0 | bn_set_minimal_width(r); |
873 | | |
874 | | // Finally, add one, for the reason described above. |
875 | 0 | return BN_add(r, r, BN_value_one()); |
876 | 0 | } |