/src/boringssl/crypto/fipsmodule/bn/sqrt.c.inc
Line | Count | Source (jump to first uncovered line) |
1 | | /* Written by Lenka Fibikova <fibikova@exp-math.uni-essen.de> |
2 | | * and Bodo Moeller for the OpenSSL project. */ |
3 | | /* ==================================================================== |
4 | | * Copyright (c) 1998-2000 The OpenSSL Project. All rights reserved. |
5 | | * |
6 | | * Redistribution and use in source and binary forms, with or without |
7 | | * modification, are permitted provided that the following conditions |
8 | | * are met: |
9 | | * |
10 | | * 1. Redistributions of source code must retain the above copyright |
11 | | * notice, this list of conditions and the following disclaimer. |
12 | | * |
13 | | * 2. Redistributions in binary form must reproduce the above copyright |
14 | | * notice, this list of conditions and the following disclaimer in |
15 | | * the documentation and/or other materials provided with the |
16 | | * distribution. |
17 | | * |
18 | | * 3. All advertising materials mentioning features or use of this |
19 | | * software must display the following acknowledgment: |
20 | | * "This product includes software developed by the OpenSSL Project |
21 | | * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" |
22 | | * |
23 | | * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to |
24 | | * endorse or promote products derived from this software without |
25 | | * prior written permission. For written permission, please contact |
26 | | * openssl-core@openssl.org. |
27 | | * |
28 | | * 5. Products derived from this software may not be called "OpenSSL" |
29 | | * nor may "OpenSSL" appear in their names without prior written |
30 | | * permission of the OpenSSL Project. |
31 | | * |
32 | | * 6. Redistributions of any form whatsoever must retain the following |
33 | | * acknowledgment: |
34 | | * "This product includes software developed by the OpenSSL Project |
35 | | * for use in the OpenSSL Toolkit (http://www.openssl.org/)" |
36 | | * |
37 | | * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY |
38 | | * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
39 | | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR |
40 | | * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR |
41 | | * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
42 | | * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
43 | | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; |
44 | | * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
45 | | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, |
46 | | * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
47 | | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED |
48 | | * OF THE POSSIBILITY OF SUCH DAMAGE. |
49 | | * ==================================================================== |
50 | | * |
51 | | * This product includes cryptographic software written by Eric Young |
52 | | * (eay@cryptsoft.com). This product includes software written by Tim |
53 | | * Hudson (tjh@cryptsoft.com). */ |
54 | | |
55 | | #include <openssl/bn.h> |
56 | | |
57 | | #include <openssl/err.h> |
58 | | |
59 | | #include "internal.h" |
60 | | |
61 | | |
62 | 23 | BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) { |
63 | | // Compute a square root of |a| mod |p| using the Tonelli/Shanks algorithm |
64 | | // (cf. Henri Cohen, "A Course in Algebraic Computational Number Theory", |
65 | | // algorithm 1.5.1). |p| is assumed to be a prime. |
66 | | |
67 | 23 | BIGNUM *ret = in; |
68 | 23 | int err = 1; |
69 | 23 | int r; |
70 | 23 | BIGNUM *A, *b, *q, *t, *x, *y; |
71 | 23 | int e, i, j; |
72 | | |
73 | 23 | if (!BN_is_odd(p) || BN_abs_is_word(p, 1)) { |
74 | 0 | if (BN_abs_is_word(p, 2)) { |
75 | 0 | if (ret == NULL) { |
76 | 0 | ret = BN_new(); |
77 | 0 | } |
78 | 0 | if (ret == NULL || |
79 | 0 | !BN_set_word(ret, BN_is_bit_set(a, 0))) { |
80 | 0 | if (ret != in) { |
81 | 0 | BN_free(ret); |
82 | 0 | } |
83 | 0 | return NULL; |
84 | 0 | } |
85 | 0 | return ret; |
86 | 0 | } |
87 | | |
88 | 0 | OPENSSL_PUT_ERROR(BN, BN_R_P_IS_NOT_PRIME); |
89 | 0 | return NULL; |
90 | 0 | } |
91 | | |
92 | 23 | if (BN_is_zero(a) || BN_is_one(a)) { |
93 | 1 | if (ret == NULL) { |
94 | 0 | ret = BN_new(); |
95 | 0 | } |
96 | 1 | if (ret == NULL || |
97 | 1 | !BN_set_word(ret, BN_is_one(a))) { |
98 | 0 | if (ret != in) { |
99 | 0 | BN_free(ret); |
100 | 0 | } |
101 | 0 | return NULL; |
102 | 0 | } |
103 | 1 | return ret; |
104 | 1 | } |
105 | | |
106 | 22 | BN_CTX_start(ctx); |
107 | 22 | A = BN_CTX_get(ctx); |
108 | 22 | b = BN_CTX_get(ctx); |
109 | 22 | q = BN_CTX_get(ctx); |
110 | 22 | t = BN_CTX_get(ctx); |
111 | 22 | x = BN_CTX_get(ctx); |
112 | 22 | y = BN_CTX_get(ctx); |
113 | 22 | if (y == NULL) { |
114 | 0 | goto end; |
115 | 0 | } |
116 | | |
117 | 22 | if (ret == NULL) { |
118 | 0 | ret = BN_new(); |
119 | 0 | } |
120 | 22 | if (ret == NULL) { |
121 | 0 | goto end; |
122 | 0 | } |
123 | | |
124 | | // A = a mod p |
125 | 22 | if (!BN_nnmod(A, a, p, ctx)) { |
126 | 0 | goto end; |
127 | 0 | } |
128 | | |
129 | | // now write |p| - 1 as 2^e*q where q is odd |
130 | 22 | e = 1; |
131 | 456 | while (!BN_is_bit_set(p, e)) { |
132 | 434 | e++; |
133 | 434 | } |
134 | | // we'll set q later (if needed) |
135 | | |
136 | 22 | if (e == 1) { |
137 | | // The easy case: (|p|-1)/2 is odd, so 2 has an inverse |
138 | | // modulo (|p|-1)/2, and square roots can be computed |
139 | | // directly by modular exponentiation. |
140 | | // We have |
141 | | // 2 * (|p|+1)/4 == 1 (mod (|p|-1)/2), |
142 | | // so we can use exponent (|p|+1)/4, i.e. (|p|-3)/4 + 1. |
143 | 8 | if (!BN_rshift(q, p, 2)) { |
144 | 0 | goto end; |
145 | 0 | } |
146 | 8 | q->neg = 0; |
147 | 8 | if (!BN_add_word(q, 1) || |
148 | 8 | !BN_mod_exp_mont(ret, A, q, p, ctx, NULL)) { |
149 | 0 | goto end; |
150 | 0 | } |
151 | 8 | err = 0; |
152 | 8 | goto vrfy; |
153 | 8 | } |
154 | | |
155 | 14 | if (e == 2) { |
156 | | // |p| == 5 (mod 8) |
157 | | // |
158 | | // In this case 2 is always a non-square since |
159 | | // Legendre(2,p) = (-1)^((p^2-1)/8) for any odd prime. |
160 | | // So if a really is a square, then 2*a is a non-square. |
161 | | // Thus for |
162 | | // b := (2*a)^((|p|-5)/8), |
163 | | // i := (2*a)*b^2 |
164 | | // we have |
165 | | // i^2 = (2*a)^((1 + (|p|-5)/4)*2) |
166 | | // = (2*a)^((p-1)/2) |
167 | | // = -1; |
168 | | // so if we set |
169 | | // x := a*b*(i-1), |
170 | | // then |
171 | | // x^2 = a^2 * b^2 * (i^2 - 2*i + 1) |
172 | | // = a^2 * b^2 * (-2*i) |
173 | | // = a*(-i)*(2*a*b^2) |
174 | | // = a*(-i)*i |
175 | | // = a. |
176 | | // |
177 | | // (This is due to A.O.L. Atkin, |
178 | | // <URL: |
179 | | //http://listserv.nodak.edu/scripts/wa.exe?A2=ind9211&L=nmbrthry&O=T&P=562>, |
180 | | // November 1992.) |
181 | | |
182 | | // t := 2*a |
183 | 0 | if (!bn_mod_lshift1_consttime(t, A, p, ctx)) { |
184 | 0 | goto end; |
185 | 0 | } |
186 | | |
187 | | // b := (2*a)^((|p|-5)/8) |
188 | 0 | if (!BN_rshift(q, p, 3)) { |
189 | 0 | goto end; |
190 | 0 | } |
191 | 0 | q->neg = 0; |
192 | 0 | if (!BN_mod_exp_mont(b, t, q, p, ctx, NULL)) { |
193 | 0 | goto end; |
194 | 0 | } |
195 | | |
196 | | // y := b^2 |
197 | 0 | if (!BN_mod_sqr(y, b, p, ctx)) { |
198 | 0 | goto end; |
199 | 0 | } |
200 | | |
201 | | // t := (2*a)*b^2 - 1 |
202 | 0 | if (!BN_mod_mul(t, t, y, p, ctx) || |
203 | 0 | !BN_sub_word(t, 1)) { |
204 | 0 | goto end; |
205 | 0 | } |
206 | | |
207 | | // x = a*b*t |
208 | 0 | if (!BN_mod_mul(x, A, b, p, ctx) || |
209 | 0 | !BN_mod_mul(x, x, t, p, ctx)) { |
210 | 0 | goto end; |
211 | 0 | } |
212 | | |
213 | 0 | if (!BN_copy(ret, x)) { |
214 | 0 | goto end; |
215 | 0 | } |
216 | 0 | err = 0; |
217 | 0 | goto vrfy; |
218 | 0 | } |
219 | | |
220 | | // e > 2, so we really have to use the Tonelli/Shanks algorithm. |
221 | | // First, find some y that is not a square. |
222 | 14 | if (!BN_copy(q, p)) { |
223 | 0 | goto end; // use 'q' as temp |
224 | 0 | } |
225 | 14 | q->neg = 0; |
226 | 14 | i = 2; |
227 | 56 | do { |
228 | | // For efficiency, try small numbers first; |
229 | | // if this fails, try random numbers. |
230 | 56 | if (i < 22) { |
231 | 56 | if (!BN_set_word(y, i)) { |
232 | 0 | goto end; |
233 | 0 | } |
234 | 56 | } else { |
235 | 0 | if (!BN_pseudo_rand(y, BN_num_bits(p), 0, 0)) { |
236 | 0 | goto end; |
237 | 0 | } |
238 | 0 | if (BN_ucmp(y, p) >= 0) { |
239 | 0 | if (BN_usub(y, y, p)) { |
240 | 0 | goto end; |
241 | 0 | } |
242 | 0 | } |
243 | | // now 0 <= y < |p| |
244 | 0 | if (BN_is_zero(y)) { |
245 | 0 | if (!BN_set_word(y, i)) { |
246 | 0 | goto end; |
247 | 0 | } |
248 | 0 | } |
249 | 0 | } |
250 | | |
251 | 56 | r = bn_jacobi(y, q, ctx); // here 'q' is |p| |
252 | 56 | if (r < -1) { |
253 | 0 | goto end; |
254 | 0 | } |
255 | 56 | if (r == 0) { |
256 | | // m divides p |
257 | 0 | OPENSSL_PUT_ERROR(BN, BN_R_P_IS_NOT_PRIME); |
258 | 0 | goto end; |
259 | 0 | } |
260 | 56 | } while (r == 1 && ++i < 82); |
261 | | |
262 | 14 | if (r != -1) { |
263 | | // Many rounds and still no non-square -- this is more likely |
264 | | // a bug than just bad luck. |
265 | | // Even if p is not prime, we should have found some y |
266 | | // such that r == -1. |
267 | 0 | OPENSSL_PUT_ERROR(BN, BN_R_TOO_MANY_ITERATIONS); |
268 | 0 | goto end; |
269 | 0 | } |
270 | | |
271 | | // Here's our actual 'q': |
272 | 14 | if (!BN_rshift(q, q, e)) { |
273 | 0 | goto end; |
274 | 0 | } |
275 | | |
276 | | // Now that we have some non-square, we can find an element |
277 | | // of order 2^e by computing its q'th power. |
278 | 14 | if (!BN_mod_exp_mont(y, y, q, p, ctx, NULL)) { |
279 | 0 | goto end; |
280 | 0 | } |
281 | 14 | if (BN_is_one(y)) { |
282 | 0 | OPENSSL_PUT_ERROR(BN, BN_R_P_IS_NOT_PRIME); |
283 | 0 | goto end; |
284 | 0 | } |
285 | | |
286 | | // Now we know that (if p is indeed prime) there is an integer |
287 | | // k, 0 <= k < 2^e, such that |
288 | | // |
289 | | // a^q * y^k == 1 (mod p). |
290 | | // |
291 | | // As a^q is a square and y is not, k must be even. |
292 | | // q+1 is even, too, so there is an element |
293 | | // |
294 | | // X := a^((q+1)/2) * y^(k/2), |
295 | | // |
296 | | // and it satisfies |
297 | | // |
298 | | // X^2 = a^q * a * y^k |
299 | | // = a, |
300 | | // |
301 | | // so it is the square root that we are looking for. |
302 | | |
303 | | // t := (q-1)/2 (note that q is odd) |
304 | 14 | if (!BN_rshift1(t, q)) { |
305 | 0 | goto end; |
306 | 0 | } |
307 | | |
308 | | // x := a^((q-1)/2) |
309 | 14 | if (BN_is_zero(t)) { // special case: p = 2^e + 1 |
310 | 0 | if (!BN_nnmod(t, A, p, ctx)) { |
311 | 0 | goto end; |
312 | 0 | } |
313 | 0 | if (BN_is_zero(t)) { |
314 | | // special case: a == 0 (mod p) |
315 | 0 | BN_zero(ret); |
316 | 0 | err = 0; |
317 | 0 | goto end; |
318 | 0 | } else if (!BN_one(x)) { |
319 | 0 | goto end; |
320 | 0 | } |
321 | 14 | } else { |
322 | 14 | if (!BN_mod_exp_mont(x, A, t, p, ctx, NULL)) { |
323 | 0 | goto end; |
324 | 0 | } |
325 | 14 | if (BN_is_zero(x)) { |
326 | | // special case: a == 0 (mod p) |
327 | 0 | BN_zero(ret); |
328 | 0 | err = 0; |
329 | 0 | goto end; |
330 | 0 | } |
331 | 14 | } |
332 | | |
333 | | // b := a*x^2 (= a^q) |
334 | 14 | if (!BN_mod_sqr(b, x, p, ctx) || |
335 | 14 | !BN_mod_mul(b, b, A, p, ctx)) { |
336 | 0 | goto end; |
337 | 0 | } |
338 | | |
339 | | // x := a*x (= a^((q+1)/2)) |
340 | 14 | if (!BN_mod_mul(x, x, A, p, ctx)) { |
341 | 0 | goto end; |
342 | 0 | } |
343 | | |
344 | 212 | while (1) { |
345 | | // Now b is a^q * y^k for some even k (0 <= k < 2^E |
346 | | // where E refers to the original value of e, which we |
347 | | // don't keep in a variable), and x is a^((q+1)/2) * y^(k/2). |
348 | | // |
349 | | // We have a*b = x^2, |
350 | | // y^2^(e-1) = -1, |
351 | | // b^2^(e-1) = 1. |
352 | 212 | if (BN_is_one(b)) { |
353 | 12 | if (!BN_copy(ret, x)) { |
354 | 0 | goto end; |
355 | 0 | } |
356 | 12 | err = 0; |
357 | 12 | goto vrfy; |
358 | 12 | } |
359 | | |
360 | | // Find the smallest i, 0 < i < e, such that b^(2^i) = 1 |
361 | 3.34k | for (i = 1; i < e; i++) { |
362 | 3.34k | if (i == 1) { |
363 | 200 | if (!BN_mod_sqr(t, b, p, ctx)) { |
364 | 0 | goto end; |
365 | 0 | } |
366 | 3.14k | } else { |
367 | 3.14k | if (!BN_mod_mul(t, t, t, p, ctx)) { |
368 | 0 | goto end; |
369 | 0 | } |
370 | 3.14k | } |
371 | 3.34k | if (BN_is_one(t)) { |
372 | 198 | break; |
373 | 198 | } |
374 | 3.34k | } |
375 | | // If not found, a is not a square or p is not a prime. |
376 | 200 | if (i >= e) { |
377 | 2 | OPENSSL_PUT_ERROR(BN, BN_R_NOT_A_SQUARE); |
378 | 2 | goto end; |
379 | 2 | } |
380 | | |
381 | | // t := y^2^(e - i - 1) |
382 | 198 | if (!BN_copy(t, y)) { |
383 | 0 | goto end; |
384 | 0 | } |
385 | 352 | for (j = e - i - 1; j > 0; j--) { |
386 | 154 | if (!BN_mod_sqr(t, t, p, ctx)) { |
387 | 0 | goto end; |
388 | 0 | } |
389 | 154 | } |
390 | 198 | if (!BN_mod_mul(y, t, t, p, ctx) || |
391 | 198 | !BN_mod_mul(x, x, t, p, ctx) || |
392 | 198 | !BN_mod_mul(b, b, y, p, ctx)) { |
393 | 0 | goto end; |
394 | 0 | } |
395 | | |
396 | | // e decreases each iteration, so this loop will terminate. |
397 | 198 | assert(i < e); |
398 | 198 | e = i; |
399 | 198 | } |
400 | | |
401 | 20 | vrfy: |
402 | 20 | if (!err) { |
403 | | // Verify the result. The input might have been not a square. |
404 | 20 | if (!BN_mod_sqr(x, ret, p, ctx)) { |
405 | 0 | err = 1; |
406 | 0 | } |
407 | | |
408 | 20 | if (!err && 0 != BN_cmp(x, A)) { |
409 | 6 | OPENSSL_PUT_ERROR(BN, BN_R_NOT_A_SQUARE); |
410 | 6 | err = 1; |
411 | 6 | } |
412 | 20 | } |
413 | | |
414 | 22 | end: |
415 | 22 | if (err) { |
416 | 8 | if (ret != in) { |
417 | 0 | BN_clear_free(ret); |
418 | 0 | } |
419 | 8 | ret = NULL; |
420 | 8 | } |
421 | 22 | BN_CTX_end(ctx); |
422 | 22 | return ret; |
423 | 20 | } |
424 | | |
425 | 112 | int BN_sqrt(BIGNUM *out_sqrt, const BIGNUM *in, BN_CTX *ctx) { |
426 | 112 | BIGNUM *estimate, *tmp, *delta, *last_delta, *tmp2; |
427 | 112 | int ok = 0, last_delta_valid = 0; |
428 | | |
429 | 112 | if (in->neg) { |
430 | 0 | OPENSSL_PUT_ERROR(BN, BN_R_NEGATIVE_NUMBER); |
431 | 0 | return 0; |
432 | 0 | } |
433 | 112 | if (BN_is_zero(in)) { |
434 | 15 | BN_zero(out_sqrt); |
435 | 15 | return 1; |
436 | 15 | } |
437 | | |
438 | 97 | BN_CTX_start(ctx); |
439 | 97 | if (out_sqrt == in) { |
440 | 0 | estimate = BN_CTX_get(ctx); |
441 | 97 | } else { |
442 | 97 | estimate = out_sqrt; |
443 | 97 | } |
444 | 97 | tmp = BN_CTX_get(ctx); |
445 | 97 | last_delta = BN_CTX_get(ctx); |
446 | 97 | delta = BN_CTX_get(ctx); |
447 | 97 | if (estimate == NULL || tmp == NULL || last_delta == NULL || delta == NULL) { |
448 | 0 | goto err; |
449 | 0 | } |
450 | | |
451 | | // We estimate that the square root of an n-bit number is 2^{n/2}. |
452 | 97 | if (!BN_lshift(estimate, BN_value_one(), BN_num_bits(in)/2)) { |
453 | 0 | goto err; |
454 | 0 | } |
455 | | |
456 | | // This is Newton's method for finding a root of the equation |estimate|^2 - |
457 | | // |in| = 0. |
458 | 762 | for (;;) { |
459 | | // |estimate| = 1/2 * (|estimate| + |in|/|estimate|) |
460 | 762 | if (!BN_div(tmp, NULL, in, estimate, ctx) || |
461 | 762 | !BN_add(tmp, tmp, estimate) || |
462 | 762 | !BN_rshift1(estimate, tmp) || |
463 | | // |tmp| = |estimate|^2 |
464 | 762 | !BN_sqr(tmp, estimate, ctx) || |
465 | | // |delta| = |in| - |tmp| |
466 | 762 | !BN_sub(delta, in, tmp)) { |
467 | 0 | OPENSSL_PUT_ERROR(BN, ERR_R_BN_LIB); |
468 | 0 | goto err; |
469 | 0 | } |
470 | | |
471 | 762 | delta->neg = 0; |
472 | | // The difference between |in| and |estimate| squared is required to always |
473 | | // decrease. This ensures that the loop always terminates, but I don't have |
474 | | // a proof that it always finds the square root for a given square. |
475 | 762 | if (last_delta_valid && BN_cmp(delta, last_delta) >= 0) { |
476 | 97 | break; |
477 | 97 | } |
478 | | |
479 | 665 | last_delta_valid = 1; |
480 | | |
481 | 665 | tmp2 = last_delta; |
482 | 665 | last_delta = delta; |
483 | 665 | delta = tmp2; |
484 | 665 | } |
485 | | |
486 | 97 | if (BN_cmp(tmp, in) != 0) { |
487 | 97 | OPENSSL_PUT_ERROR(BN, BN_R_NOT_A_SQUARE); |
488 | 97 | goto err; |
489 | 97 | } |
490 | | |
491 | 0 | ok = 1; |
492 | |
|
493 | 97 | err: |
494 | 97 | if (ok && out_sqrt == in && !BN_copy(out_sqrt, estimate)) { |
495 | 0 | ok = 0; |
496 | 0 | } |
497 | 97 | BN_CTX_end(ctx); |
498 | 97 | return ok; |
499 | 0 | } |