sl@0: /* crypto/bn/bn_kron.c */ sl@0: /* ==================================================================== sl@0: * Copyright (c) 1998-2000 The OpenSSL Project. All rights reserved. sl@0: * sl@0: * Redistribution and use in source and binary forms, with or without sl@0: * modification, are permitted provided that the following conditions sl@0: * are met: sl@0: * sl@0: * 1. Redistributions of source code must retain the above copyright sl@0: * notice, this list of conditions and the following disclaimer. sl@0: * sl@0: * 2. Redistributions in binary form must reproduce the above copyright sl@0: * notice, this list of conditions and the following disclaimer in sl@0: * the documentation and/or other materials provided with the sl@0: * distribution. sl@0: * sl@0: * 3. All advertising materials mentioning features or use of this sl@0: * software must display the following acknowledgment: sl@0: * "This product includes software developed by the OpenSSL Project sl@0: * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" sl@0: * sl@0: * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to sl@0: * endorse or promote products derived from this software without sl@0: * prior written permission. For written permission, please contact sl@0: * openssl-core@openssl.org. sl@0: * sl@0: * 5. Products derived from this software may not be called "OpenSSL" sl@0: * nor may "OpenSSL" appear in their names without prior written sl@0: * permission of the OpenSSL Project. sl@0: * sl@0: * 6. Redistributions of any form whatsoever must retain the following sl@0: * acknowledgment: sl@0: * "This product includes software developed by the OpenSSL Project sl@0: * for use in the OpenSSL Toolkit (http://www.openssl.org/)" sl@0: * sl@0: * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY sl@0: * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE sl@0: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR sl@0: * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR sl@0: * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, sl@0: * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT sl@0: * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; sl@0: * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) sl@0: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, sl@0: * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) sl@0: * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED sl@0: * OF THE POSSIBILITY OF SUCH DAMAGE. sl@0: * ==================================================================== sl@0: * sl@0: * This product includes cryptographic software written by Eric Young sl@0: * (eay@cryptsoft.com). This product includes software written by Tim sl@0: * Hudson (tjh@cryptsoft.com). sl@0: * sl@0: */ sl@0: sl@0: #include "cryptlib.h" sl@0: #include "bn_lcl.h" sl@0: sl@0: /* least significant word */ sl@0: #define BN_lsw(n) (((n)->top == 0) ? (BN_ULONG) 0 : (n)->d[0]) sl@0: sl@0: /* Returns -2 for errors because both -1 and 0 are valid results. */ sl@0: EXPORT_C int BN_kronecker(const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) sl@0: { sl@0: int i; sl@0: int ret = -2; /* avoid 'uninitialized' warning */ sl@0: int err = 0; sl@0: BIGNUM *A, *B, *tmp; sl@0: /* In 'tab', only odd-indexed entries are relevant: sl@0: * For any odd BIGNUM n, sl@0: * tab[BN_lsw(n) & 7] sl@0: * is $(-1)^{(n^2-1)/8}$ (using TeX notation). sl@0: * Note that the sign of n does not matter. sl@0: */ sl@0: static const int tab[8] = {0, 1, 0, -1, 0, -1, 0, 1}; sl@0: sl@0: bn_check_top(a); sl@0: bn_check_top(b); sl@0: sl@0: BN_CTX_start(ctx); sl@0: A = BN_CTX_get(ctx); sl@0: B = BN_CTX_get(ctx); sl@0: if (B == NULL) goto end; sl@0: sl@0: err = !BN_copy(A, a); sl@0: if (err) goto end; sl@0: err = !BN_copy(B, b); sl@0: if (err) goto end; sl@0: sl@0: /* sl@0: * Kronecker symbol, imlemented according to Henri Cohen, sl@0: * "A Course in Computational Algebraic Number Theory" sl@0: * (algorithm 1.4.10). sl@0: */ sl@0: sl@0: /* Cohen's step 1: */ sl@0: sl@0: if (BN_is_zero(B)) sl@0: { sl@0: ret = BN_abs_is_word(A, 1); sl@0: goto end; sl@0: } sl@0: sl@0: /* Cohen's step 2: */ sl@0: sl@0: if (!BN_is_odd(A) && !BN_is_odd(B)) sl@0: { sl@0: ret = 0; sl@0: goto end; sl@0: } sl@0: sl@0: /* now B is non-zero */ sl@0: i = 0; sl@0: while (!BN_is_bit_set(B, i)) sl@0: i++; sl@0: err = !BN_rshift(B, B, i); sl@0: if (err) goto end; sl@0: if (i & 1) sl@0: { sl@0: /* i is odd */ sl@0: /* (thus B was even, thus A must be odd!) */ sl@0: sl@0: /* set 'ret' to $(-1)^{(A^2-1)/8}$ */ sl@0: ret = tab[BN_lsw(A) & 7]; sl@0: } sl@0: else sl@0: { sl@0: /* i is even */ sl@0: ret = 1; sl@0: } sl@0: sl@0: if (B->neg) sl@0: { sl@0: B->neg = 0; sl@0: if (A->neg) sl@0: ret = -ret; sl@0: } sl@0: sl@0: /* now B is positive and odd, so what remains to be done is sl@0: * to compute the Jacobi symbol (A/B) and multiply it by 'ret' */ sl@0: sl@0: while (1) sl@0: { sl@0: /* Cohen's step 3: */ sl@0: sl@0: /* B is positive and odd */ sl@0: sl@0: if (BN_is_zero(A)) sl@0: { sl@0: ret = BN_is_one(B) ? ret : 0; sl@0: goto end; sl@0: } sl@0: sl@0: /* now A is non-zero */ sl@0: i = 0; sl@0: while (!BN_is_bit_set(A, i)) sl@0: i++; sl@0: err = !BN_rshift(A, A, i); sl@0: if (err) goto end; sl@0: if (i & 1) sl@0: { sl@0: /* i is odd */ sl@0: /* multiply 'ret' by $(-1)^{(B^2-1)/8}$ */ sl@0: ret = ret * tab[BN_lsw(B) & 7]; sl@0: } sl@0: sl@0: /* Cohen's step 4: */ sl@0: /* multiply 'ret' by $(-1)^{(A-1)(B-1)/4}$ */ sl@0: if ((A->neg ? ~BN_lsw(A) : BN_lsw(A)) & BN_lsw(B) & 2) sl@0: ret = -ret; sl@0: sl@0: /* (A, B) := (B mod |A|, |A|) */ sl@0: err = !BN_nnmod(B, B, A, ctx); sl@0: if (err) goto end; sl@0: tmp = A; A = B; B = tmp; sl@0: tmp->neg = 0; sl@0: } sl@0: end: sl@0: BN_CTX_end(ctx); sl@0: if (err) sl@0: return -2; sl@0: else sl@0: return ret; sl@0: }