/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 | 11.6M | 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 | 6.08M | size_t num) { |
28 | 6.08M | bn_rshift1_words(tmp, a, num); |
29 | 6.08M | bn_select_words(a, mask, tmp, a, num); |
30 | 6.08M | } |
31 | | |
32 | | static void maybe_rshift1_words_carry(BN_ULONG *a, BN_ULONG carry, |
33 | | BN_ULONG mask, BN_ULONG *tmp, |
34 | 502k | size_t num) { |
35 | 502k | maybe_rshift1_words(a, mask, tmp, num); |
36 | 502k | if (num != 0) { |
37 | 502k | carry &= mask; |
38 | 502k | a[num - 1] |= carry << (BN_BITS2-1); |
39 | 502k | } |
40 | 502k | } |
41 | | |
42 | | static BN_ULONG maybe_add_words(BN_ULONG *a, BN_ULONG mask, const BN_ULONG *b, |
43 | 502k | BN_ULONG *tmp, size_t num) { |
44 | 502k | BN_ULONG carry = bn_add_words(tmp, a, b, num); |
45 | 502k | bn_select_words(a, mask, tmp, a, num); |
46 | 502k | return carry & mask; |
47 | 502k | } |
48 | | |
49 | | static int bn_gcd_consttime(BIGNUM *r, unsigned *out_shift, const BIGNUM *x, |
50 | 5.33k | const BIGNUM *y, BN_CTX *ctx) { |
51 | 5.33k | size_t width = x->width > y->width ? x->width : y->width; |
52 | 5.33k | if (width == 0) { |
53 | 36 | *out_shift = 0; |
54 | 36 | BN_zero(r); |
55 | 36 | return 1; |
56 | 36 | } |
57 | | |
58 | | // This is a constant-time implementation of Stein's algorithm (binary GCD). |
59 | 5.29k | int ret = 0; |
60 | 5.29k | BN_CTX_start(ctx); |
61 | 5.29k | BIGNUM *u = BN_CTX_get(ctx); |
62 | 5.29k | BIGNUM *v = BN_CTX_get(ctx); |
63 | 5.29k | BIGNUM *tmp = BN_CTX_get(ctx); |
64 | 5.29k | if (u == NULL || v == NULL || tmp == NULL || |
65 | 5.29k | !BN_copy(u, x) || |
66 | 5.29k | !BN_copy(v, y) || |
67 | 5.29k | !bn_resize_words(u, width) || |
68 | 5.29k | !bn_resize_words(v, width) || |
69 | 5.29k | !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 | 5.29k | unsigned x_bits = x->width * BN_BITS2, y_bits = y->width * BN_BITS2; |
76 | 5.29k | unsigned num_iters = x_bits + y_bits; |
77 | 5.29k | if (num_iters < x_bits) { |
78 | 0 | OPENSSL_PUT_ERROR(BN, BN_R_BIGNUM_TOO_LONG); |
79 | 0 | goto err; |
80 | 0 | } |
81 | | |
82 | 5.29k | unsigned shift = 0; |
83 | 2.67M | for (unsigned i = 0; i < num_iters; i++) { |
84 | 2.66M | 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 | 2.66M | BN_ULONG u_less_than_v = |
88 | 2.66M | (BN_ULONG)0 - bn_sub_words(tmp->d, u->d, v->d, width); |
89 | 2.66M | bn_select_words(u->d, both_odd & ~u_less_than_v, tmp->d, u->d, width); |
90 | 2.66M | bn_sub_words(tmp->d, v->d, u->d, width); |
91 | 2.66M | 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 | 2.66M | BN_ULONG u_is_odd = word_is_odd_mask(u->d[0]); |
95 | 2.66M | BN_ULONG v_is_odd = word_is_odd_mask(v->d[0]); |
96 | 2.66M | declassify_assert(!(u_is_odd & v_is_odd)); |
97 | | |
98 | | // If both are even, the final GCD gains a factor of two. |
99 | 2.66M | shift += 1 & (~u_is_odd & ~v_is_odd); |
100 | | |
101 | | // Halve any which are even. |
102 | 2.66M | maybe_rshift1_words(u->d, ~u_is_odd, tmp->d, width); |
103 | 2.66M | maybe_rshift1_words(v->d, ~v_is_odd, tmp->d, width); |
104 | 2.66M | } |
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 | 5.29k | declassify_assert(BN_is_zero(u) | BN_is_zero(v)); |
110 | 30.3k | for (size_t i = 0; i < width; i++) { |
111 | 25.0k | v->d[i] |= u->d[i]; |
112 | 25.0k | } |
113 | | |
114 | 5.29k | *out_shift = shift; |
115 | 5.29k | ret = bn_set_words(r, v->d, width); |
116 | | |
117 | 5.29k | err: |
118 | 5.29k | BN_CTX_end(ctx); |
119 | 5.29k | return ret; |
120 | 5.29k | } |
121 | | |
122 | 5.33k | int BN_gcd(BIGNUM *r, const BIGNUM *x, const BIGNUM *y, BN_CTX *ctx) { |
123 | 5.33k | unsigned shift; |
124 | 5.33k | return bn_gcd_consttime(r, &shift, x, y, ctx) && |
125 | 5.33k | BN_lshift(r, r, shift); |
126 | 5.33k | } |
127 | | |
128 | | int bn_is_relatively_prime(int *out_relatively_prime, const BIGNUM *x, |
129 | 0 | const BIGNUM *y, BN_CTX *ctx) { |
130 | 0 | int ret = 0; |
131 | 0 | BN_CTX_start(ctx); |
132 | 0 | unsigned shift; |
133 | 0 | BIGNUM *gcd = BN_CTX_get(ctx); |
134 | 0 | if (gcd == NULL || |
135 | 0 | !bn_gcd_consttime(gcd, &shift, x, y, ctx)) { |
136 | 0 | goto err; |
137 | 0 | } |
138 | | |
139 | | // Check that 2^|shift| * |gcd| is one. |
140 | 0 | if (gcd->width == 0) { |
141 | 0 | *out_relatively_prime = 0; |
142 | 0 | } else { |
143 | 0 | BN_ULONG mask = shift | (gcd->d[0] ^ 1); |
144 | 0 | for (int i = 1; i < gcd->width; i++) { |
145 | 0 | mask |= gcd->d[i]; |
146 | 0 | } |
147 | 0 | *out_relatively_prime = mask == 0; |
148 | 0 | } |
149 | 0 | ret = 1; |
150 | |
|
151 | 0 | err: |
152 | 0 | BN_CTX_end(ctx); |
153 | 0 | return ret; |
154 | 0 | } |
155 | | |
156 | 0 | int bn_lcm_consttime(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) { |
157 | 0 | BN_CTX_start(ctx); |
158 | 0 | unsigned shift; |
159 | 0 | BIGNUM *gcd = BN_CTX_get(ctx); |
160 | 0 | int ret = gcd != NULL && // |
161 | 0 | bn_mul_consttime(r, a, b, ctx) && |
162 | 0 | bn_gcd_consttime(gcd, &shift, a, b, ctx) && |
163 | | // |gcd| has a secret bit width. |
164 | 0 | bn_div_consttime(r, NULL, r, gcd, /*divisor_min_bits=*/0, ctx) && |
165 | 0 | bn_rshift_secret_shift(r, r, shift, ctx); |
166 | 0 | BN_CTX_end(ctx); |
167 | 0 | return ret; |
168 | 0 | } |
169 | | |
170 | | int bn_mod_inverse_consttime(BIGNUM *r, int *out_no_inverse, const BIGNUM *a, |
171 | 697 | const BIGNUM *n, BN_CTX *ctx) { |
172 | 697 | *out_no_inverse = 0; |
173 | 697 | 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 | 697 | if (BN_is_zero(a)) { |
178 | 246 | if (BN_is_one(n)) { |
179 | 0 | BN_zero(r); |
180 | 0 | return 1; |
181 | 0 | } |
182 | 246 | *out_no_inverse = 1; |
183 | 246 | OPENSSL_PUT_ERROR(BN, BN_R_NO_INVERSE); |
184 | 246 | return 0; |
185 | 246 | } |
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 | 451 | if (!BN_is_odd(a) && !BN_is_odd(n)) { |
198 | 209 | *out_no_inverse = 1; |
199 | 209 | OPENSSL_PUT_ERROR(BN, BN_R_NO_INVERSE); |
200 | 209 | return 0; |
201 | 209 | } |
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 | 242 | size_t n_width = n->width, a_width = a->width; |
206 | 242 | if (a_width > n_width) { |
207 | 0 | a_width = n_width; |
208 | 0 | } |
209 | | |
210 | 242 | int ret = 0; |
211 | 242 | BN_CTX_start(ctx); |
212 | 242 | BIGNUM *u = BN_CTX_get(ctx); |
213 | 242 | BIGNUM *v = BN_CTX_get(ctx); |
214 | 242 | BIGNUM *A = BN_CTX_get(ctx); |
215 | 242 | BIGNUM *B = BN_CTX_get(ctx); |
216 | 242 | BIGNUM *C = BN_CTX_get(ctx); |
217 | 242 | BIGNUM *D = BN_CTX_get(ctx); |
218 | 242 | BIGNUM *tmp = BN_CTX_get(ctx); |
219 | 242 | BIGNUM *tmp2 = BN_CTX_get(ctx); |
220 | 242 | if (u == NULL || v == NULL || A == NULL || B == NULL || C == NULL || |
221 | 242 | D == NULL || tmp == NULL || tmp2 == NULL || |
222 | 242 | !BN_copy(u, a) || |
223 | 242 | !BN_copy(v, n) || |
224 | 242 | !BN_one(A) || |
225 | 242 | !BN_one(D) || |
226 | | // For convenience, size |u| and |v| equivalently. |
227 | 242 | !bn_resize_words(u, n_width) || |
228 | 242 | !bn_resize_words(v, n_width) || |
229 | | // |A| and |C| are bounded by |m|. |
230 | 242 | !bn_resize_words(A, n_width) || |
231 | 242 | !bn_resize_words(C, n_width) || |
232 | | // |B| and |D| are bounded by |a|. |
233 | 242 | !bn_resize_words(B, a_width) || |
234 | 242 | !bn_resize_words(D, a_width) || |
235 | | // |tmp| and |tmp2| may be used at either size. |
236 | 242 | !bn_resize_words(tmp, n_width) || |
237 | 242 | !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 | 242 | size_t a_bits = a_width * BN_BITS2, n_bits = n_width * BN_BITS2; |
246 | 242 | size_t num_iters = a_bits + n_bits; |
247 | 242 | 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 | 125k | for (size_t i = 0; i < num_iters; i++) { |
266 | 125k | 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 | 125k | BN_ULONG v_less_than_u = |
270 | 125k | (BN_ULONG)0 - bn_sub_words(tmp->d, v->d, u->d, n_width); |
271 | 125k | bn_select_words(v->d, both_odd & ~v_less_than_u, tmp->d, v->d, n_width); |
272 | 125k | bn_sub_words(tmp->d, u->d, v->d, n_width); |
273 | 125k | 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 | 125k | BN_ULONG carry = bn_add_words(tmp->d, A->d, C->d, n_width); |
277 | 125k | carry -= bn_sub_words(tmp2->d, tmp->d, n->d, n_width); |
278 | 125k | bn_select_words(tmp->d, carry, tmp->d, tmp2->d, n_width); |
279 | 125k | bn_select_words(A->d, both_odd & v_less_than_u, tmp->d, A->d, n_width); |
280 | 125k | bn_select_words(C->d, both_odd & ~v_less_than_u, tmp->d, C->d, n_width); |
281 | | |
282 | 125k | bn_add_words(tmp->d, B->d, D->d, a_width); |
283 | 125k | bn_sub_words(tmp2->d, tmp->d, a->d, a_width); |
284 | 125k | bn_select_words(tmp->d, carry, tmp->d, tmp2->d, a_width); |
285 | 125k | bn_select_words(B->d, both_odd & v_less_than_u, tmp->d, B->d, a_width); |
286 | 125k | 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 | 125k | BN_ULONG u_is_even = ~word_is_odd_mask(u->d[0]); |
291 | 125k | BN_ULONG v_is_even = ~word_is_odd_mask(v->d[0]); |
292 | 125k | declassify_assert(u_is_even != v_is_even); |
293 | | |
294 | | // Halve the even one and adjust the corresponding coefficient. |
295 | 125k | maybe_rshift1_words(u->d, u_is_even, tmp->d, n_width); |
296 | 125k | BN_ULONG A_or_B_is_odd = |
297 | 125k | word_is_odd_mask(A->d[0]) | word_is_odd_mask(B->d[0]); |
298 | 125k | BN_ULONG A_carry = |
299 | 125k | maybe_add_words(A->d, A_or_B_is_odd & u_is_even, n->d, tmp->d, n_width); |
300 | 125k | BN_ULONG B_carry = |
301 | 125k | maybe_add_words(B->d, A_or_B_is_odd & u_is_even, a->d, tmp->d, a_width); |
302 | 125k | maybe_rshift1_words_carry(A->d, A_carry, u_is_even, tmp->d, n_width); |
303 | 125k | maybe_rshift1_words_carry(B->d, B_carry, u_is_even, tmp->d, a_width); |
304 | | |
305 | 125k | maybe_rshift1_words(v->d, v_is_even, tmp->d, n_width); |
306 | 125k | BN_ULONG C_or_D_is_odd = |
307 | 125k | word_is_odd_mask(C->d[0]) | word_is_odd_mask(D->d[0]); |
308 | 125k | BN_ULONG C_carry = |
309 | 125k | maybe_add_words(C->d, C_or_D_is_odd & v_is_even, n->d, tmp->d, n_width); |
310 | 125k | BN_ULONG D_carry = |
311 | 125k | maybe_add_words(D->d, C_or_D_is_odd & v_is_even, a->d, tmp->d, a_width); |
312 | 125k | maybe_rshift1_words_carry(C->d, C_carry, v_is_even, tmp->d, n_width); |
313 | 125k | maybe_rshift1_words_carry(D->d, D_carry, v_is_even, tmp->d, a_width); |
314 | 125k | } |
315 | | |
316 | 242 | 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 | 242 | if (constant_time_declassify_int(!BN_is_one(u))) { |
321 | 85 | *out_no_inverse = 1; |
322 | 85 | OPENSSL_PUT_ERROR(BN, BN_R_NO_INVERSE); |
323 | 85 | goto err; |
324 | 85 | } |
325 | | |
326 | 157 | ret = BN_copy(r, A) != NULL; |
327 | | |
328 | 242 | err: |
329 | 242 | BN_CTX_end(ctx); |
330 | 242 | return ret; |
331 | 157 | } |