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 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