/src/boringssl/crypto/fipsmodule/bn/gcd_extra.c.inc
Line | Count | Source (jump to first uncovered line) |
1 | | /* Copyright (c) 2018, Google Inc. |
2 | | * |
3 | | * Permission to use, copy, modify, and/or distribute this software for any |
4 | | * purpose with or without fee is hereby granted, provided that the above |
5 | | * copyright notice and this permission notice appear in all copies. |
6 | | * |
7 | | * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES |
8 | | * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF |
9 | | * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY |
10 | | * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES |
11 | | * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION |
12 | | * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN |
13 | | * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */ |
14 | | |
15 | | #include <openssl/bn.h> |
16 | | |
17 | | #include <assert.h> |
18 | | |
19 | | #include <openssl/err.h> |
20 | | |
21 | | #include "internal.h" |
22 | | |
23 | | |
24 | 3.66M | static BN_ULONG word_is_odd_mask(BN_ULONG a) { return (BN_ULONG)0 - (a & 1); } |
25 | | |
26 | | static void maybe_rshift1_words(BN_ULONG *a, BN_ULONG mask, BN_ULONG *tmp, |
27 | 2.42M | size_t num) { |
28 | 2.42M | bn_rshift1_words(tmp, a, num); |
29 | 2.42M | bn_select_words(a, mask, tmp, a, num); |
30 | 2.42M | } |
31 | | |
32 | | static void maybe_rshift1_words_carry(BN_ULONG *a, BN_ULONG carry, |
33 | | BN_ULONG mask, BN_ULONG *tmp, |
34 | 1.18M | size_t num) { |
35 | 1.18M | maybe_rshift1_words(a, mask, tmp, num); |
36 | 1.18M | if (num != 0) { |
37 | 1.18M | carry &= mask; |
38 | 1.18M | a[num - 1] |= carry << (BN_BITS2-1); |
39 | 1.18M | } |
40 | 1.18M | } |
41 | | |
42 | | static BN_ULONG maybe_add_words(BN_ULONG *a, BN_ULONG mask, const BN_ULONG *b, |
43 | 1.18M | BN_ULONG *tmp, size_t num) { |
44 | 1.18M | BN_ULONG carry = bn_add_words(tmp, a, b, num); |
45 | 1.18M | bn_select_words(a, mask, tmp, a, num); |
46 | 1.18M | return carry & mask; |
47 | 1.18M | } |
48 | | |
49 | | static int bn_gcd_consttime(BIGNUM *r, unsigned *out_shift, const BIGNUM *x, |
50 | 48 | const BIGNUM *y, BN_CTX *ctx) { |
51 | 48 | size_t width = x->width > y->width ? x->width : y->width; |
52 | 48 | if (width == 0) { |
53 | 0 | *out_shift = 0; |
54 | 0 | BN_zero(r); |
55 | 0 | return 1; |
56 | 0 | } |
57 | | |
58 | | // This is a constant-time implementation of Stein's algorithm (binary GCD). |
59 | 48 | int ret = 0; |
60 | 48 | BN_CTX_start(ctx); |
61 | 48 | BIGNUM *u = BN_CTX_get(ctx); |
62 | 48 | BIGNUM *v = BN_CTX_get(ctx); |
63 | 48 | BIGNUM *tmp = BN_CTX_get(ctx); |
64 | 48 | if (u == NULL || v == NULL || tmp == NULL || |
65 | 48 | !BN_copy(u, x) || |
66 | 48 | !BN_copy(v, y) || |
67 | 48 | !bn_resize_words(u, width) || |
68 | 48 | !bn_resize_words(v, width) || |
69 | 48 | !bn_resize_words(tmp, width)) { |
70 | 0 | goto err; |
71 | 0 | } |
72 | | |
73 | | // Each loop iteration halves at least one of |u| and |v|. Thus we need at |
74 | | // most the combined bit width of inputs for at least one value to be zero. |
75 | 48 | unsigned x_bits = x->width * BN_BITS2, y_bits = y->width * BN_BITS2; |
76 | 48 | unsigned num_iters = x_bits + y_bits; |
77 | 48 | if (num_iters < x_bits) { |
78 | 0 | OPENSSL_PUT_ERROR(BN, BN_R_BIGNUM_TOO_LONG); |
79 | 0 | goto err; |
80 | 0 | } |
81 | | |
82 | 48 | unsigned shift = 0; |
83 | 322k | for (unsigned i = 0; i < num_iters; i++) { |
84 | 322k | BN_ULONG both_odd = word_is_odd_mask(u->d[0]) & word_is_odd_mask(v->d[0]); |
85 | | |
86 | | // If both |u| and |v| are odd, subtract the smaller from the larger. |
87 | 322k | BN_ULONG u_less_than_v = |
88 | 322k | (BN_ULONG)0 - bn_sub_words(tmp->d, u->d, v->d, width); |
89 | 322k | bn_select_words(u->d, both_odd & ~u_less_than_v, tmp->d, u->d, width); |
90 | 322k | bn_sub_words(tmp->d, v->d, u->d, width); |
91 | 322k | bn_select_words(v->d, both_odd & u_less_than_v, tmp->d, v->d, width); |
92 | | |
93 | | // At least one of |u| and |v| is now even. |
94 | 322k | BN_ULONG u_is_odd = word_is_odd_mask(u->d[0]); |
95 | 322k | BN_ULONG v_is_odd = word_is_odd_mask(v->d[0]); |
96 | 322k | declassify_assert(!(u_is_odd & v_is_odd)); |
97 | | |
98 | | // If both are even, the final GCD gains a factor of two. |
99 | 322k | shift += 1 & (~u_is_odd & ~v_is_odd); |
100 | | |
101 | | // Halve any which are even. |
102 | 322k | maybe_rshift1_words(u->d, ~u_is_odd, tmp->d, width); |
103 | 322k | maybe_rshift1_words(v->d, ~v_is_odd, tmp->d, width); |
104 | 322k | } |
105 | | |
106 | | // One of |u| or |v| is zero at this point. The algorithm usually makes |u| |
107 | | // zero, unless |y| was already zero on input. Fix this by combining the |
108 | | // values. |
109 | 48 | declassify_assert(BN_is_zero(u) | BN_is_zero(v)); |
110 | 3.37k | for (size_t i = 0; i < width; i++) { |
111 | 3.32k | v->d[i] |= u->d[i]; |
112 | 3.32k | } |
113 | | |
114 | 48 | *out_shift = shift; |
115 | 48 | ret = bn_set_words(r, v->d, width); |
116 | | |
117 | 48 | err: |
118 | 48 | BN_CTX_end(ctx); |
119 | 48 | return ret; |
120 | 48 | } |
121 | | |
122 | 18 | int BN_gcd(BIGNUM *r, const BIGNUM *x, const BIGNUM *y, BN_CTX *ctx) { |
123 | 18 | unsigned shift; |
124 | 18 | return bn_gcd_consttime(r, &shift, x, y, ctx) && |
125 | 18 | BN_lshift(r, r, shift); |
126 | 18 | } |
127 | | |
128 | | int bn_is_relatively_prime(int *out_relatively_prime, const BIGNUM *x, |
129 | 4 | const BIGNUM *y, BN_CTX *ctx) { |
130 | 4 | int ret = 0; |
131 | 4 | BN_CTX_start(ctx); |
132 | 4 | unsigned shift; |
133 | 4 | BIGNUM *gcd = BN_CTX_get(ctx); |
134 | 4 | if (gcd == NULL || |
135 | 4 | !bn_gcd_consttime(gcd, &shift, x, y, ctx)) { |
136 | 0 | goto err; |
137 | 0 | } |
138 | | |
139 | | // Check that 2^|shift| * |gcd| is one. |
140 | 4 | if (gcd->width == 0) { |
141 | 0 | *out_relatively_prime = 0; |
142 | 4 | } else { |
143 | 4 | BN_ULONG mask = shift | (gcd->d[0] ^ 1); |
144 | 212 | for (int i = 1; i < gcd->width; i++) { |
145 | 208 | mask |= gcd->d[i]; |
146 | 208 | } |
147 | 4 | *out_relatively_prime = mask == 0; |
148 | 4 | } |
149 | 4 | ret = 1; |
150 | | |
151 | 4 | err: |
152 | 4 | BN_CTX_end(ctx); |
153 | 4 | return ret; |
154 | 4 | } |
155 | | |
156 | 26 | int bn_lcm_consttime(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) { |
157 | 26 | BN_CTX_start(ctx); |
158 | 26 | unsigned shift; |
159 | 26 | BIGNUM *gcd = BN_CTX_get(ctx); |
160 | 26 | int ret = gcd != NULL && // |
161 | 26 | bn_mul_consttime(r, a, b, ctx) && |
162 | 26 | bn_gcd_consttime(gcd, &shift, a, b, ctx) && |
163 | | // |gcd| has a secret bit width. |
164 | 26 | bn_div_consttime(r, NULL, r, gcd, /*divisor_min_bits=*/0, ctx) && |
165 | 26 | bn_rshift_secret_shift(r, r, shift, ctx); |
166 | 26 | BN_CTX_end(ctx); |
167 | 26 | return ret; |
168 | 26 | } |
169 | | |
170 | | int bn_mod_inverse_consttime(BIGNUM *r, int *out_no_inverse, const BIGNUM *a, |
171 | 92 | const BIGNUM *n, BN_CTX *ctx) { |
172 | 92 | *out_no_inverse = 0; |
173 | 92 | if (BN_is_negative(a) || BN_ucmp(a, n) >= 0) { |
174 | 0 | OPENSSL_PUT_ERROR(BN, BN_R_INPUT_NOT_REDUCED); |
175 | 0 | return 0; |
176 | 0 | } |
177 | 92 | if (BN_is_zero(a)) { |
178 | 2 | if (BN_is_one(n)) { |
179 | 0 | BN_zero(r); |
180 | 0 | return 1; |
181 | 0 | } |
182 | 2 | *out_no_inverse = 1; |
183 | 2 | OPENSSL_PUT_ERROR(BN, BN_R_NO_INVERSE); |
184 | 2 | return 0; |
185 | 2 | } |
186 | | |
187 | | // This is a constant-time implementation of the extended binary GCD |
188 | | // algorithm. It is adapted from the Handbook of Applied Cryptography, section |
189 | | // 14.4.3, algorithm 14.51, and modified to bound coefficients and avoid |
190 | | // negative numbers. |
191 | | // |
192 | | // For more details and proof of correctness, see |
193 | | // https://github.com/mit-plv/fiat-crypto/pull/333. In particular, see |step| |
194 | | // and |mod_inverse_consttime| for the algorithm in Gallina and see |
195 | | // |mod_inverse_consttime_spec| for the correctness result. |
196 | | |
197 | 90 | if (!BN_is_odd(a) && !BN_is_odd(n)) { |
198 | 28 | *out_no_inverse = 1; |
199 | 28 | OPENSSL_PUT_ERROR(BN, BN_R_NO_INVERSE); |
200 | 28 | return 0; |
201 | 28 | } |
202 | | |
203 | | // This function exists to compute the RSA private exponent, where |a| is one |
204 | | // word. We'll thus use |a_width| when available. |
205 | 62 | size_t n_width = n->width, a_width = a->width; |
206 | 62 | if (a_width > n_width) { |
207 | 0 | a_width = n_width; |
208 | 0 | } |
209 | | |
210 | 62 | int ret = 0; |
211 | 62 | BN_CTX_start(ctx); |
212 | 62 | BIGNUM *u = BN_CTX_get(ctx); |
213 | 62 | BIGNUM *v = BN_CTX_get(ctx); |
214 | 62 | BIGNUM *A = BN_CTX_get(ctx); |
215 | 62 | BIGNUM *B = BN_CTX_get(ctx); |
216 | 62 | BIGNUM *C = BN_CTX_get(ctx); |
217 | 62 | BIGNUM *D = BN_CTX_get(ctx); |
218 | 62 | BIGNUM *tmp = BN_CTX_get(ctx); |
219 | 62 | BIGNUM *tmp2 = BN_CTX_get(ctx); |
220 | 62 | if (u == NULL || v == NULL || A == NULL || B == NULL || C == NULL || |
221 | 62 | D == NULL || tmp == NULL || tmp2 == NULL || |
222 | 62 | !BN_copy(u, a) || |
223 | 62 | !BN_copy(v, n) || |
224 | 62 | !BN_one(A) || |
225 | 62 | !BN_one(D) || |
226 | | // For convenience, size |u| and |v| equivalently. |
227 | 62 | !bn_resize_words(u, n_width) || |
228 | 62 | !bn_resize_words(v, n_width) || |
229 | | // |A| and |C| are bounded by |m|. |
230 | 62 | !bn_resize_words(A, n_width) || |
231 | 62 | !bn_resize_words(C, n_width) || |
232 | | // |B| and |D| are bounded by |a|. |
233 | 62 | !bn_resize_words(B, a_width) || |
234 | 62 | !bn_resize_words(D, a_width) || |
235 | | // |tmp| and |tmp2| may be used at either size. |
236 | 62 | !bn_resize_words(tmp, n_width) || |
237 | 62 | !bn_resize_words(tmp2, n_width)) { |
238 | 0 | goto err; |
239 | 0 | } |
240 | | |
241 | | // Each loop iteration halves at least one of |u| and |v|. Thus we need at |
242 | | // most the combined bit width of inputs for at least one value to be zero. |
243 | | // |a_bits| and |n_bits| cannot overflow because |bn_wexpand| ensures bit |
244 | | // counts fit in even |int|. |
245 | 62 | size_t a_bits = a_width * BN_BITS2, n_bits = n_width * BN_BITS2; |
246 | 62 | size_t num_iters = a_bits + n_bits; |
247 | 62 | if (num_iters < a_bits) { |
248 | 0 | OPENSSL_PUT_ERROR(BN, BN_R_BIGNUM_TOO_LONG); |
249 | 0 | goto err; |
250 | 0 | } |
251 | | |
252 | | // Before and after each loop iteration, the following hold: |
253 | | // |
254 | | // u = A*a - B*n |
255 | | // v = D*n - C*a |
256 | | // 0 < u <= a |
257 | | // 0 <= v <= n |
258 | | // 0 <= A < n |
259 | | // 0 <= B <= a |
260 | | // 0 <= C < n |
261 | | // 0 <= D <= a |
262 | | // |
263 | | // After each loop iteration, u and v only get smaller, and at least one of |
264 | | // them shrinks by at least a factor of two. |
265 | 296k | for (size_t i = 0; i < num_iters; i++) { |
266 | 296k | BN_ULONG both_odd = word_is_odd_mask(u->d[0]) & word_is_odd_mask(v->d[0]); |
267 | | |
268 | | // If both |u| and |v| are odd, subtract the smaller from the larger. |
269 | 296k | BN_ULONG v_less_than_u = |
270 | 296k | (BN_ULONG)0 - bn_sub_words(tmp->d, v->d, u->d, n_width); |
271 | 296k | bn_select_words(v->d, both_odd & ~v_less_than_u, tmp->d, v->d, n_width); |
272 | 296k | bn_sub_words(tmp->d, u->d, v->d, n_width); |
273 | 296k | bn_select_words(u->d, both_odd & v_less_than_u, tmp->d, u->d, n_width); |
274 | | |
275 | | // If we updated one of the values, update the corresponding coefficient. |
276 | 296k | BN_ULONG carry = bn_add_words(tmp->d, A->d, C->d, n_width); |
277 | 296k | carry -= bn_sub_words(tmp2->d, tmp->d, n->d, n_width); |
278 | 296k | bn_select_words(tmp->d, carry, tmp->d, tmp2->d, n_width); |
279 | 296k | bn_select_words(A->d, both_odd & v_less_than_u, tmp->d, A->d, n_width); |
280 | 296k | bn_select_words(C->d, both_odd & ~v_less_than_u, tmp->d, C->d, n_width); |
281 | | |
282 | 296k | bn_add_words(tmp->d, B->d, D->d, a_width); |
283 | 296k | bn_sub_words(tmp2->d, tmp->d, a->d, a_width); |
284 | 296k | bn_select_words(tmp->d, carry, tmp->d, tmp2->d, a_width); |
285 | 296k | bn_select_words(B->d, both_odd & v_less_than_u, tmp->d, B->d, a_width); |
286 | 296k | bn_select_words(D->d, both_odd & ~v_less_than_u, tmp->d, D->d, a_width); |
287 | | |
288 | | // Our loop invariants hold at this point. Additionally, exactly one of |u| |
289 | | // and |v| is now even. |
290 | 296k | BN_ULONG u_is_even = ~word_is_odd_mask(u->d[0]); |
291 | 296k | BN_ULONG v_is_even = ~word_is_odd_mask(v->d[0]); |
292 | 296k | declassify_assert(u_is_even != v_is_even); |
293 | | |
294 | | // Halve the even one and adjust the corresponding coefficient. |
295 | 296k | maybe_rshift1_words(u->d, u_is_even, tmp->d, n_width); |
296 | 296k | BN_ULONG A_or_B_is_odd = |
297 | 296k | word_is_odd_mask(A->d[0]) | word_is_odd_mask(B->d[0]); |
298 | 296k | BN_ULONG A_carry = |
299 | 296k | maybe_add_words(A->d, A_or_B_is_odd & u_is_even, n->d, tmp->d, n_width); |
300 | 296k | BN_ULONG B_carry = |
301 | 296k | maybe_add_words(B->d, A_or_B_is_odd & u_is_even, a->d, tmp->d, a_width); |
302 | 296k | maybe_rshift1_words_carry(A->d, A_carry, u_is_even, tmp->d, n_width); |
303 | 296k | maybe_rshift1_words_carry(B->d, B_carry, u_is_even, tmp->d, a_width); |
304 | | |
305 | 296k | maybe_rshift1_words(v->d, v_is_even, tmp->d, n_width); |
306 | 296k | BN_ULONG C_or_D_is_odd = |
307 | 296k | word_is_odd_mask(C->d[0]) | word_is_odd_mask(D->d[0]); |
308 | 296k | BN_ULONG C_carry = |
309 | 296k | maybe_add_words(C->d, C_or_D_is_odd & v_is_even, n->d, tmp->d, n_width); |
310 | 296k | BN_ULONG D_carry = |
311 | 296k | maybe_add_words(D->d, C_or_D_is_odd & v_is_even, a->d, tmp->d, a_width); |
312 | 296k | maybe_rshift1_words_carry(C->d, C_carry, v_is_even, tmp->d, n_width); |
313 | 296k | maybe_rshift1_words_carry(D->d, D_carry, v_is_even, tmp->d, a_width); |
314 | 296k | } |
315 | | |
316 | 62 | declassify_assert(BN_is_zero(v)); |
317 | | // While the inputs and output are secret, this function considers whether the |
318 | | // input was invertible to be public. It is used as part of RSA key |
319 | | // generation, where inputs are chosen to already be invertible. |
320 | 62 | if (constant_time_declassify_int(!BN_is_one(u))) { |
321 | 10 | *out_no_inverse = 1; |
322 | 10 | OPENSSL_PUT_ERROR(BN, BN_R_NO_INVERSE); |
323 | 10 | goto err; |
324 | 10 | } |
325 | | |
326 | 52 | ret = BN_copy(r, A) != NULL; |
327 | | |
328 | 62 | err: |
329 | 62 | BN_CTX_end(ctx); |
330 | 62 | return ret; |
331 | 52 | } |