/src/boringssl/crypto/fipsmodule/bn/jacobi.c.inc
Line | Count | Source (jump to first uncovered line) |
1 | | /* ==================================================================== |
2 | | * Copyright (c) 1998-2000 The OpenSSL Project. All rights reserved. |
3 | | * |
4 | | * Redistribution and use in source and binary forms, with or without |
5 | | * modification, are permitted provided that the following conditions |
6 | | * are met: |
7 | | * |
8 | | * 1. Redistributions of source code must retain the above copyright |
9 | | * notice, this list of conditions and the following disclaimer. |
10 | | * |
11 | | * 2. Redistributions in binary form must reproduce the above copyright |
12 | | * notice, this list of conditions and the following disclaimer in |
13 | | * the documentation and/or other materials provided with the |
14 | | * distribution. |
15 | | * |
16 | | * 3. All advertising materials mentioning features or use of this |
17 | | * software must display the following acknowledgment: |
18 | | * "This product includes software developed by the OpenSSL Project |
19 | | * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" |
20 | | * |
21 | | * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to |
22 | | * endorse or promote products derived from this software without |
23 | | * prior written permission. For written permission, please contact |
24 | | * openssl-core@openssl.org. |
25 | | * |
26 | | * 5. Products derived from this software may not be called "OpenSSL" |
27 | | * nor may "OpenSSL" appear in their names without prior written |
28 | | * permission of the OpenSSL Project. |
29 | | * |
30 | | * 6. Redistributions of any form whatsoever must retain the following |
31 | | * acknowledgment: |
32 | | * "This product includes software developed by the OpenSSL Project |
33 | | * for use in the OpenSSL Toolkit (http://www.openssl.org/)" |
34 | | * |
35 | | * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY |
36 | | * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
37 | | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR |
38 | | * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR |
39 | | * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
40 | | * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
41 | | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; |
42 | | * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
43 | | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, |
44 | | * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
45 | | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED |
46 | | * OF THE POSSIBILITY OF SUCH DAMAGE. |
47 | | * ==================================================================== |
48 | | * |
49 | | * This product includes cryptographic software written by Eric Young |
50 | | * (eay@cryptsoft.com). This product includes software written by Tim |
51 | | * Hudson (tjh@cryptsoft.com). */ |
52 | | |
53 | | #include <openssl/bn.h> |
54 | | |
55 | | #include <openssl/err.h> |
56 | | |
57 | | #include "internal.h" |
58 | | |
59 | | |
60 | | // least significant word |
61 | 113k | #define BN_lsw(n) (((n)->width == 0) ? (BN_ULONG) 0 : (n)->d[0]) |
62 | | |
63 | 113 | int bn_jacobi(const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) { |
64 | | // In 'tab', only odd-indexed entries are relevant: |
65 | | // For any odd BIGNUM n, |
66 | | // tab[BN_lsw(n) & 7] |
67 | | // is $(-1)^{(n^2-1)/8}$ (using TeX notation). |
68 | | // Note that the sign of n does not matter. |
69 | 113 | static const int tab[8] = {0, 1, 0, -1, 0, -1, 0, 1}; |
70 | | |
71 | | // The Jacobi symbol is only defined for odd modulus. |
72 | 113 | if (!BN_is_odd(b)) { |
73 | 20 | OPENSSL_PUT_ERROR(BN, BN_R_CALLED_WITH_EVEN_MODULUS); |
74 | 20 | return -2; |
75 | 20 | } |
76 | | |
77 | | // Require b be positive. |
78 | 93 | if (BN_is_negative(b)) { |
79 | 0 | OPENSSL_PUT_ERROR(BN, BN_R_NEGATIVE_NUMBER); |
80 | 0 | return -2; |
81 | 0 | } |
82 | | |
83 | 93 | int ret = -2; |
84 | 93 | BN_CTX_start(ctx); |
85 | 93 | BIGNUM *A = BN_CTX_get(ctx); |
86 | 93 | BIGNUM *B = BN_CTX_get(ctx); |
87 | 93 | if (B == NULL) { |
88 | 0 | goto end; |
89 | 0 | } |
90 | | |
91 | 93 | if (!BN_copy(A, a) || |
92 | 93 | !BN_copy(B, b)) { |
93 | 0 | goto end; |
94 | 0 | } |
95 | | |
96 | | // Adapted from logic to compute the Kronecker symbol, originally implemented |
97 | | // according to Henri Cohen, "A Course in Computational Algebraic Number |
98 | | // Theory" (algorithm 1.4.10). |
99 | | |
100 | 93 | ret = 1; |
101 | | |
102 | 47.8k | while (1) { |
103 | | // Cohen's step 3: |
104 | | |
105 | | // B is positive and odd |
106 | 47.8k | if (BN_is_zero(A)) { |
107 | 93 | ret = BN_is_one(B) ? ret : 0; |
108 | 93 | goto end; |
109 | 93 | } |
110 | | |
111 | | // now A is non-zero |
112 | 47.7k | int i = 0; |
113 | 99.9k | while (!BN_is_bit_set(A, i)) { |
114 | 52.1k | i++; |
115 | 52.1k | } |
116 | 47.7k | if (!BN_rshift(A, A, i)) { |
117 | 0 | ret = -2; |
118 | 0 | goto end; |
119 | 0 | } |
120 | 47.7k | if (i & 1) { |
121 | | // i is odd |
122 | | // multiply 'ret' by $(-1)^{(B^2-1)/8}$ |
123 | 17.4k | ret = ret * tab[BN_lsw(B) & 7]; |
124 | 17.4k | } |
125 | | |
126 | | // Cohen's step 4: |
127 | | // multiply 'ret' by $(-1)^{(A-1)(B-1)/4}$ |
128 | 47.7k | if ((A->neg ? ~BN_lsw(A) : BN_lsw(A)) & BN_lsw(B) & 2) { |
129 | 11.8k | ret = -ret; |
130 | 11.8k | } |
131 | | |
132 | | // (A, B) := (B mod |A|, |A|) |
133 | 47.7k | if (!BN_nnmod(B, B, A, ctx)) { |
134 | 0 | ret = -2; |
135 | 0 | goto end; |
136 | 0 | } |
137 | 47.7k | BIGNUM *tmp = A; |
138 | 47.7k | A = B; |
139 | 47.7k | B = tmp; |
140 | 47.7k | tmp->neg = 0; |
141 | 47.7k | } |
142 | | |
143 | 93 | end: |
144 | 93 | BN_CTX_end(ctx); |
145 | 93 | return ret; |
146 | 93 | } |