/src/boringssl/crypto/fipsmodule/bn/gcd.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 | | /* ==================================================================== |
58 | | * Copyright (c) 1998-2001 The OpenSSL Project. All rights reserved. |
59 | | * |
60 | | * Redistribution and use in source and binary forms, with or without |
61 | | * modification, are permitted provided that the following conditions |
62 | | * are met: |
63 | | * |
64 | | * 1. Redistributions of source code must retain the above copyright |
65 | | * notice, this list of conditions and the following disclaimer. |
66 | | * |
67 | | * 2. Redistributions in binary form must reproduce the above copyright |
68 | | * notice, this list of conditions and the following disclaimer in |
69 | | * the documentation and/or other materials provided with the |
70 | | * distribution. |
71 | | * |
72 | | * 3. All advertising materials mentioning features or use of this |
73 | | * software must display the following acknowledgment: |
74 | | * "This product includes software developed by the OpenSSL Project |
75 | | * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" |
76 | | * |
77 | | * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to |
78 | | * endorse or promote products derived from this software without |
79 | | * prior written permission. For written permission, please contact |
80 | | * openssl-core@openssl.org. |
81 | | * |
82 | | * 5. Products derived from this software may not be called "OpenSSL" |
83 | | * nor may "OpenSSL" appear in their names without prior written |
84 | | * permission of the OpenSSL Project. |
85 | | * |
86 | | * 6. Redistributions of any form whatsoever must retain the following |
87 | | * acknowledgment: |
88 | | * "This product includes software developed by the OpenSSL Project |
89 | | * for use in the OpenSSL Toolkit (http://www.openssl.org/)" |
90 | | * |
91 | | * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY |
92 | | * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
93 | | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR |
94 | | * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR |
95 | | * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
96 | | * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
97 | | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; |
98 | | * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
99 | | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, |
100 | | * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
101 | | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED |
102 | | * OF THE POSSIBILITY OF SUCH DAMAGE. |
103 | | * ==================================================================== |
104 | | * |
105 | | * This product includes cryptographic software written by Eric Young |
106 | | * (eay@cryptsoft.com). This product includes software written by Tim |
107 | | * Hudson (tjh@cryptsoft.com). */ |
108 | | |
109 | | #include <openssl/bn.h> |
110 | | |
111 | | #include <openssl/err.h> |
112 | | |
113 | | #include "internal.h" |
114 | | |
115 | | |
116 | | int BN_mod_inverse_odd(BIGNUM *out, int *out_no_inverse, const BIGNUM *a, |
117 | 36 | const BIGNUM *n, BN_CTX *ctx) { |
118 | 36 | *out_no_inverse = 0; |
119 | | |
120 | 36 | if (!BN_is_odd(n)) { |
121 | 0 | OPENSSL_PUT_ERROR(BN, BN_R_CALLED_WITH_EVEN_MODULUS); |
122 | 0 | return 0; |
123 | 0 | } |
124 | | |
125 | 36 | if (BN_is_negative(a) || BN_cmp(a, n) >= 0) { |
126 | 0 | OPENSSL_PUT_ERROR(BN, BN_R_INPUT_NOT_REDUCED); |
127 | 0 | return 0; |
128 | 0 | } |
129 | | |
130 | 36 | BIGNUM *A, *B, *X, *Y; |
131 | 36 | int ret = 0; |
132 | 36 | int sign; |
133 | | |
134 | 36 | BN_CTX_start(ctx); |
135 | 36 | A = BN_CTX_get(ctx); |
136 | 36 | B = BN_CTX_get(ctx); |
137 | 36 | X = BN_CTX_get(ctx); |
138 | 36 | Y = BN_CTX_get(ctx); |
139 | 36 | if (Y == NULL) { |
140 | 0 | goto err; |
141 | 0 | } |
142 | | |
143 | 36 | BIGNUM *R = out; |
144 | | |
145 | 36 | BN_zero(Y); |
146 | 36 | if (!BN_one(X) || BN_copy(B, a) == NULL || BN_copy(A, n) == NULL) { |
147 | 0 | goto err; |
148 | 0 | } |
149 | 36 | A->neg = 0; |
150 | 36 | sign = -1; |
151 | | // From B = a mod |n|, A = |n| it follows that |
152 | | // |
153 | | // 0 <= B < A, |
154 | | // -sign*X*a == B (mod |n|), |
155 | | // sign*Y*a == A (mod |n|). |
156 | | |
157 | | // Binary inversion algorithm; requires odd modulus. This is faster than the |
158 | | // general algorithm if the modulus is sufficiently small (about 400 .. 500 |
159 | | // bits on 32-bit systems, but much more on 64-bit systems) |
160 | 36 | int shift; |
161 | | |
162 | 52.9k | while (!BN_is_zero(B)) { |
163 | | // 0 < B < |n|, |
164 | | // 0 < A <= |n|, |
165 | | // (1) -sign*X*a == B (mod |n|), |
166 | | // (2) sign*Y*a == A (mod |n|) |
167 | | |
168 | | // Now divide B by the maximum possible power of two in the integers, |
169 | | // and divide X by the same value mod |n|. |
170 | | // When we're done, (1) still holds. |
171 | 52.8k | shift = 0; |
172 | 88.2k | while (!BN_is_bit_set(B, shift)) { |
173 | | // note that 0 < B |
174 | 35.3k | shift++; |
175 | | |
176 | 35.3k | if (BN_is_odd(X)) { |
177 | 17.7k | if (!BN_uadd(X, X, n)) { |
178 | 0 | goto err; |
179 | 0 | } |
180 | 17.7k | } |
181 | | // now X is even, so we can easily divide it by two |
182 | 35.3k | if (!BN_rshift1(X, X)) { |
183 | 0 | goto err; |
184 | 0 | } |
185 | 35.3k | } |
186 | 52.8k | if (shift > 0) { |
187 | 17.4k | if (!BN_rshift(B, B, shift)) { |
188 | 0 | goto err; |
189 | 0 | } |
190 | 17.4k | } |
191 | | |
192 | | // Same for A and Y. Afterwards, (2) still holds. |
193 | 52.8k | shift = 0; |
194 | 123k | while (!BN_is_bit_set(A, shift)) { |
195 | | // note that 0 < A |
196 | 70.9k | shift++; |
197 | | |
198 | 70.9k | if (BN_is_odd(Y)) { |
199 | 35.7k | if (!BN_uadd(Y, Y, n)) { |
200 | 0 | goto err; |
201 | 0 | } |
202 | 35.7k | } |
203 | | // now Y is even |
204 | 70.9k | if (!BN_rshift1(Y, Y)) { |
205 | 0 | goto err; |
206 | 0 | } |
207 | 70.9k | } |
208 | 52.8k | if (shift > 0) { |
209 | 35.3k | if (!BN_rshift(A, A, shift)) { |
210 | 0 | goto err; |
211 | 0 | } |
212 | 35.3k | } |
213 | | |
214 | | // We still have (1) and (2). |
215 | | // Both A and B are odd. |
216 | | // The following computations ensure that |
217 | | // |
218 | | // 0 <= B < |n|, |
219 | | // 0 < A < |n|, |
220 | | // (1) -sign*X*a == B (mod |n|), |
221 | | // (2) sign*Y*a == A (mod |n|), |
222 | | // |
223 | | // and that either A or B is even in the next iteration. |
224 | 52.8k | if (BN_ucmp(B, A) >= 0) { |
225 | | // -sign*(X + Y)*a == B - A (mod |n|) |
226 | 17.5k | if (!BN_uadd(X, X, Y)) { |
227 | 0 | goto err; |
228 | 0 | } |
229 | | // NB: we could use BN_mod_add_quick(X, X, Y, n), but that |
230 | | // actually makes the algorithm slower |
231 | 17.5k | if (!BN_usub(B, B, A)) { |
232 | 0 | goto err; |
233 | 0 | } |
234 | 35.3k | } else { |
235 | | // sign*(X + Y)*a == A - B (mod |n|) |
236 | 35.3k | if (!BN_uadd(Y, Y, X)) { |
237 | 0 | goto err; |
238 | 0 | } |
239 | | // as above, BN_mod_add_quick(Y, Y, X, n) would slow things down |
240 | 35.3k | if (!BN_usub(A, A, B)) { |
241 | 0 | goto err; |
242 | 0 | } |
243 | 35.3k | } |
244 | 52.8k | } |
245 | | |
246 | 36 | if (!BN_is_one(A)) { |
247 | 10 | *out_no_inverse = 1; |
248 | 10 | OPENSSL_PUT_ERROR(BN, BN_R_NO_INVERSE); |
249 | 10 | goto err; |
250 | 10 | } |
251 | | |
252 | | // The while loop (Euclid's algorithm) ends when |
253 | | // A == gcd(a,n); |
254 | | // we have |
255 | | // sign*Y*a == A (mod |n|), |
256 | | // where Y is non-negative. |
257 | | |
258 | 26 | if (sign < 0) { |
259 | 26 | if (!BN_sub(Y, n, Y)) { |
260 | 0 | goto err; |
261 | 0 | } |
262 | 26 | } |
263 | | // Now Y*a == A (mod |n|). |
264 | | |
265 | | // Y*a == 1 (mod |n|) |
266 | 26 | if (Y->neg || BN_ucmp(Y, n) >= 0) { |
267 | 12 | if (!BN_nnmod(Y, Y, n, ctx)) { |
268 | 0 | goto err; |
269 | 0 | } |
270 | 12 | } |
271 | 26 | if (!BN_copy(R, Y)) { |
272 | 0 | goto err; |
273 | 0 | } |
274 | | |
275 | 26 | ret = 1; |
276 | | |
277 | 36 | err: |
278 | 36 | BN_CTX_end(ctx); |
279 | 36 | return ret; |
280 | 26 | } |
281 | | |
282 | | BIGNUM *BN_mod_inverse(BIGNUM *out, const BIGNUM *a, const BIGNUM *n, |
283 | 128 | BN_CTX *ctx) { |
284 | 128 | BIGNUM *new_out = NULL; |
285 | 128 | if (out == NULL) { |
286 | 0 | new_out = BN_new(); |
287 | 0 | if (new_out == NULL) { |
288 | 0 | return NULL; |
289 | 0 | } |
290 | 0 | out = new_out; |
291 | 0 | } |
292 | | |
293 | 128 | int ok = 0; |
294 | 128 | BIGNUM *a_reduced = NULL; |
295 | 128 | if (a->neg || BN_ucmp(a, n) >= 0) { |
296 | 26 | a_reduced = BN_dup(a); |
297 | 26 | if (a_reduced == NULL) { |
298 | 0 | goto err; |
299 | 0 | } |
300 | 26 | if (!BN_nnmod(a_reduced, a_reduced, n, ctx)) { |
301 | 2 | goto err; |
302 | 2 | } |
303 | 24 | a = a_reduced; |
304 | 24 | } |
305 | | |
306 | 126 | int no_inverse; |
307 | 126 | if (!BN_is_odd(n)) { |
308 | 92 | if (!bn_mod_inverse_consttime(out, &no_inverse, a, n, ctx)) { |
309 | 40 | goto err; |
310 | 40 | } |
311 | 92 | } else if (!BN_mod_inverse_odd(out, &no_inverse, a, n, ctx)) { |
312 | 9 | goto err; |
313 | 9 | } |
314 | | |
315 | 77 | ok = 1; |
316 | | |
317 | 128 | err: |
318 | 128 | if (!ok) { |
319 | 51 | BN_free(new_out); |
320 | 51 | out = NULL; |
321 | 51 | } |
322 | 128 | BN_free(a_reduced); |
323 | 128 | return out; |
324 | 77 | } |
325 | | |
326 | | int BN_mod_inverse_blinded(BIGNUM *out, int *out_no_inverse, const BIGNUM *a, |
327 | 3 | const BN_MONT_CTX *mont, BN_CTX *ctx) { |
328 | 3 | *out_no_inverse = 0; |
329 | | |
330 | | // |a| is secret, but it is required to be in range, so these comparisons may |
331 | | // be leaked. |
332 | 3 | if (BN_is_negative(a) || |
333 | 3 | constant_time_declassify_int(BN_cmp(a, &mont->N) >= 0)) { |
334 | 2 | OPENSSL_PUT_ERROR(BN, BN_R_INPUT_NOT_REDUCED); |
335 | 2 | return 0; |
336 | 2 | } |
337 | | |
338 | 1 | int ret = 0; |
339 | 1 | BIGNUM blinding_factor; |
340 | 1 | BN_init(&blinding_factor); |
341 | | |
342 | | // |BN_mod_inverse_odd| is leaky, so generate a secret blinding factor and |
343 | | // blind |a|. This works because (ar)^-1 * r = a^-1, supposing r is |
344 | | // invertible. If r is not invertible, this function will fail. However, we |
345 | | // only use this in RSA, where stumbling on an uninvertible element means |
346 | | // stumbling on the key's factorization. That is, if this function fails, the |
347 | | // RSA key was not actually a product of two large primes. |
348 | | // |
349 | | // TODO(crbug.com/boringssl/677): When the PRNG output is marked secret by |
350 | | // default, the explicit |bn_secret| call can be removed. |
351 | 1 | if (!BN_rand_range_ex(&blinding_factor, 1, &mont->N)) { |
352 | 0 | goto err; |
353 | 0 | } |
354 | 1 | bn_secret(&blinding_factor); |
355 | 1 | if (!BN_mod_mul_montgomery(out, &blinding_factor, a, mont, ctx)) { |
356 | 0 | goto err; |
357 | 0 | } |
358 | | |
359 | | // Once blinded, |out| is no longer secret, so it may be passed to a leaky |
360 | | // mod inverse function. Note |blinding_factor| is secret, so |out| will be |
361 | | // secret again after multiplying. |
362 | 1 | bn_declassify(out); |
363 | 1 | if (!BN_mod_inverse_odd(out, out_no_inverse, out, &mont->N, ctx) || |
364 | 1 | !BN_mod_mul_montgomery(out, &blinding_factor, out, mont, ctx)) { |
365 | 1 | goto err; |
366 | 1 | } |
367 | | |
368 | 0 | ret = 1; |
369 | |
|
370 | 1 | err: |
371 | 1 | BN_free(&blinding_factor); |
372 | 1 | return ret; |
373 | 0 | } |
374 | | |
375 | | int bn_mod_inverse_prime(BIGNUM *out, const BIGNUM *a, const BIGNUM *p, |
376 | 0 | BN_CTX *ctx, const BN_MONT_CTX *mont_p) { |
377 | 0 | BN_CTX_start(ctx); |
378 | 0 | BIGNUM *p_minus_2 = BN_CTX_get(ctx); |
379 | 0 | int ok = p_minus_2 != NULL && |
380 | 0 | BN_copy(p_minus_2, p) && |
381 | 0 | BN_sub_word(p_minus_2, 2) && |
382 | 0 | BN_mod_exp_mont(out, a, p_minus_2, p, ctx, mont_p); |
383 | 0 | BN_CTX_end(ctx); |
384 | 0 | return ok; |
385 | 0 | } |
386 | | |
387 | | int bn_mod_inverse_secret_prime(BIGNUM *out, const BIGNUM *a, const BIGNUM *p, |
388 | 0 | BN_CTX *ctx, const BN_MONT_CTX *mont_p) { |
389 | 0 | BN_CTX_start(ctx); |
390 | 0 | BIGNUM *p_minus_2 = BN_CTX_get(ctx); |
391 | 0 | int ok = p_minus_2 != NULL && |
392 | 0 | BN_copy(p_minus_2, p) && |
393 | 0 | BN_sub_word(p_minus_2, 2) && |
394 | 0 | BN_mod_exp_mont_consttime(out, a, p_minus_2, p, ctx, mont_p); |
395 | 0 | BN_CTX_end(ctx); |
396 | 0 | return ok; |
397 | 0 | } |