1/* $OpenBSD: bn_kron.c,v 1.15 2023/07/08 12:21:58 beck 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_local.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
65int
66BN_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_CTX_start(ctx);
75
76	if ((a = BN_CTX_get(ctx)) == NULL)
77		goto end;
78	if ((b = BN_CTX_get(ctx)) == NULL)
79		goto end;
80
81	if (!bn_copy(a, A))
82		goto end;
83	if (!bn_copy(b, B))
84		goto end;
85
86	/*
87	 * Cohen's step 1:
88	 */
89
90	/* If b is zero, output 1 if |a| is 1, otherwise output 0. */
91	if (BN_is_zero(b)) {
92		ret = BN_abs_is_word(a, 1);
93		goto end;
94	}
95
96	/*
97	 * Cohen's step 2:
98	 */
99
100	/* If both are even, they have a factor in common, so output 0. */
101	if (!BN_is_odd(a) && !BN_is_odd(b)) {
102		ret = 0;
103		goto end;
104	}
105
106	/* Factorize b = 2^v * u with odd u and replace b with u. */
107	v = 0;
108	while (!BN_is_bit_set(b, v))
109		v++;
110	if (!BN_rshift(b, b, v))
111		goto end;
112
113	/* If v is even set k = 1, otherwise set it to (-1)^((a^2 - 1) / 8). */
114	k = 1;
115	if (v % 2 != 0)
116		k = tab[BN_lsw(a) & 7];
117
118	/*
119	 * If b is negative, replace it with -b and if a is also negative
120	 * replace k with -k.
121	 */
122	if (BN_is_negative(b)) {
123		BN_set_negative(b, 0);
124
125		if (BN_is_negative(a))
126			k = -k;
127	}
128
129	/*
130	 * Now b is positive and odd, so compute the Jacobi symbol (a/b)
131	 * and multiply it by k.
132	 */
133
134	while (1) {
135		/*
136		 * Cohen's step 3:
137		 */
138
139		/* b is positive and odd. */
140
141		/* If a is zero output k if b is one, otherwise output 0. */
142		if (BN_is_zero(a)) {
143			ret = BN_is_one(b) ? k : 0;
144			goto end;
145		}
146
147		/* Factorize a = 2^v * u with odd u and replace a with u. */
148		v = 0;
149		while (!BN_is_bit_set(a, v))
150			v++;
151		if (!BN_rshift(a, a, v))
152			goto end;
153
154		/* If v is odd, multiply k with (-1)^((b^2 - 1) / 8). */
155		if (v % 2 != 0)
156			k *= tab[BN_lsw(b) & 7];
157
158		/*
159		 * Cohen's step 4:
160		 */
161
162		/*
163		 * Apply the reciprocity law: multiply k by (-1)^((a-1)(b-1)/4).
164		 *
165		 * This expression is -1 if and only if a and b are 3 (mod 4).
166		 * In turn, this is the case if and only if their two's
167		 * complement representations have the second bit set.
168		 * a could be negative in the first iteration, b is positive.
169		 */
170		if ((BN_is_negative(a) ? ~BN_lsw(a) : BN_lsw(a)) & BN_lsw(b) & 2)
171			k = -k;
172
173		/*
174		 * (a, b) := (b mod |a|, |a|)
175		 *
176		 * Once this is done, we know that 0 < a < b at the start of the
177		 * loop. Since b is strictly decreasing, the loop terminates.
178		 */
179
180		if (!BN_nnmod(b, b, a, ctx))
181			goto end;
182
183		tmp = a;
184		a = b;
185		b = tmp;
186
187		BN_set_negative(b, 0);
188	}
189
190 end:
191	BN_CTX_end(ctx);
192
193	return ret;
194}
195LCRYPTO_ALIAS(BN_kronecker);
196