1 /* $OpenBSD: bn_kron.c,v 1.10 2022/07/12 16:08:19 tb Exp $ */
2 /* ====================================================================
3 * Copyright (c) 1998-2000 The OpenSSL Project. All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 *
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in
14 * the documentation and/or other materials provided with the
15 * distribution.
16 *
17 * 3. All advertising materials mentioning features or use of this
18 * software must display the following acknowledgment:
19 * "This product includes software developed by the OpenSSL Project
20 * for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
21 *
22 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
23 * endorse or promote products derived from this software without
24 * prior written permission. For written permission, please contact
25 * openssl-core@openssl.org.
26 *
27 * 5. Products derived from this software may not be called "OpenSSL"
28 * nor may "OpenSSL" appear in their names without prior written
29 * permission of the OpenSSL Project.
30 *
31 * 6. Redistributions of any form whatsoever must retain the following
32 * acknowledgment:
33 * "This product includes software developed by the OpenSSL Project
34 * for use in the OpenSSL Toolkit (http://www.openssl.org/)"
35 *
36 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
37 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
38 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
39 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR
40 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
41 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
42 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
43 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
44 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
45 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
46 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
47 * OF THE POSSIBILITY OF SUCH DAMAGE.
48 * ====================================================================
49 *
50 * This product includes cryptographic software written by Eric Young
51 * (eay@cryptsoft.com). This product includes software written by Tim
52 * Hudson (tjh@cryptsoft.com).
53 *
54 */
55
56 #include "bn_lcl.h"
57
58 /*
59 * Kronecker symbol, implemented according to Henri Cohen, "A Course in
60 * Computational Algebraic Number Theory", Algorithm 1.4.10.
61 *
62 * Returns -1, 0, or 1 on success and -2 on error.
63 */
64
65 int
BN_kronecker(const BIGNUM * A,const BIGNUM * B,BN_CTX * ctx)66 BN_kronecker(const BIGNUM *A, const BIGNUM *B, BN_CTX *ctx)
67 {
68 /* tab[BN_lsw(n) & 7] = (-1)^((n^2 - 1)) / 8) for odd values of n. */
69 static const int tab[8] = {0, 1, 0, -1, 0, -1, 0, 1};
70 BIGNUM *a, *b, *tmp;
71 int k, v;
72 int ret = -2;
73
74 bn_check_top(A);
75 bn_check_top(B);
76
77 BN_CTX_start(ctx);
78
79 if ((a = BN_CTX_get(ctx)) == NULL)
80 goto end;
81 if ((b = BN_CTX_get(ctx)) == NULL)
82 goto end;
83
84 if (BN_copy(a, A) == NULL)
85 goto end;
86 if (BN_copy(b, B) == NULL)
87 goto end;
88
89 /*
90 * Cohen's step 1:
91 */
92
93 /* If b is zero, output 1 if |a| is 1, otherwise output 0. */
94 if (BN_is_zero(b)) {
95 ret = BN_abs_is_word(a, 1);
96 goto end;
97 }
98
99 /*
100 * Cohen's step 2:
101 */
102
103 /* If both are even, they have a factor in common, so output 0. */
104 if (!BN_is_odd(a) && !BN_is_odd(b)) {
105 ret = 0;
106 goto end;
107 }
108
109 /* Factorize b = 2^v * u with odd u and replace b with u. */
110 v = 0;
111 while (!BN_is_bit_set(b, v))
112 v++;
113 if (!BN_rshift(b, b, v))
114 goto end;
115
116 /* If v is even set k = 1, otherwise set it to (-1)^((a^2 - 1) / 8). */
117 k = 1;
118 if (v % 2 != 0)
119 k = tab[BN_lsw(a) & 7];
120
121 /*
122 * If b is negative, replace it with -b and if a is also negative
123 * replace k with -k.
124 */
125 if (BN_is_negative(b)) {
126 BN_set_negative(b, 0);
127
128 if (BN_is_negative(a))
129 k = -k;
130 }
131
132 /*
133 * Now b is positive and odd, so compute the Jacobi symbol (a/b)
134 * and multiply it by k.
135 */
136
137 while (1) {
138 /*
139 * Cohen's step 3:
140 */
141
142 /* b is positive and odd. */
143
144 /* If a is zero output k if b is one, otherwise output 0. */
145 if (BN_is_zero(a)) {
146 ret = BN_is_one(b) ? k : 0;
147 goto end;
148 }
149
150 /* Factorize a = 2^v * u with odd u and replace a with u. */
151 v = 0;
152 while (!BN_is_bit_set(a, v))
153 v++;
154 if (!BN_rshift(a, a, v))
155 goto end;
156
157 /* If v is odd, multiply k with (-1)^((b^2 - 1) / 8). */
158 if (v % 2 != 0)
159 k *= tab[BN_lsw(b) & 7];
160
161 /*
162 * Cohen's step 4:
163 */
164
165 /*
166 * Apply the reciprocity law: multiply k by (-1)^((a-1)(b-1)/4).
167 *
168 * This expression is -1 if and only if a and b are 3 (mod 4).
169 * In turn, this is the case if and only if their two's
170 * complement representations have the second bit set.
171 * a could be negative in the first iteration, b is positive.
172 */
173 if ((BN_is_negative(a) ? ~BN_lsw(a) : BN_lsw(a)) & BN_lsw(b) & 2)
174 k = -k;
175
176 /*
177 * (a, b) := (b mod |a|, |a|)
178 *
179 * Once this is done, we know that 0 < a < b at the start of the
180 * loop. Since b is strictly decreasing, the loop terminates.
181 */
182
183 if (!BN_nnmod(b, b, a, ctx))
184 goto end;
185
186 tmp = a;
187 a = b;
188 b = tmp;
189
190 BN_set_negative(b, 0);
191 }
192
193 end:
194 BN_CTX_end(ctx);
195
196 return ret;
197 }
198