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