From 91cba18ca7af44ce390ac0c5714539b219c77f9d Mon Sep 17 00:00:00 2001 From: tb Date: Mon, 20 Jun 2022 19:32:35 +0000 Subject: [PATCH] Clean up BN_kronecker() Instead of "Cohen's step N" explain in words what is being done. Things such as (A & B & 2) != 0 being equivalent to (-1)^((A-1)(B-1)/4) being negative are not entirely obvious... Remove the strange error dance and adjust variable names to what Cohen's book uses. Simplify various curly bits. ok jsing --- lib/libcrypto/bn/bn_kron.c | 161 ++++++++++++++++++++----------------- 1 file changed, 88 insertions(+), 73 deletions(-) diff --git a/lib/libcrypto/bn/bn_kron.c b/lib/libcrypto/bn/bn_kron.c index 274da5d1868..c7bc53535e8 100644 --- a/lib/libcrypto/bn/bn_kron.c +++ b/lib/libcrypto/bn/bn_kron.c @@ -1,4 +1,4 @@ -/* $OpenBSD: bn_kron.c,v 1.6 2015/02/09 15:49:22 jsing Exp $ */ +/* $OpenBSD: bn_kron.c,v 1.7 2022/06/20 19:32:35 tb Exp $ */ /* ==================================================================== * Copyright (c) 1998-2000 The OpenSSL Project. All rights reserved. * @@ -58,128 +58,143 @@ /* least significant word */ #define BN_lsw(n) (((n)->top == 0) ? (BN_ULONG) 0 : (n)->d[0]) -/* Returns -2 for errors because both -1 and 0 are valid results. */ +/* + * Kronecker symbol, implemented according to Henri Cohen, "A Course in + * Computational Algebraic Number Theory", Algorithm 1.4.10. + * + * Returns -1, 0, or 1 on success and -2 on error. + */ + int BN_kronecker(const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) { - int i; - int ret = -2; /* avoid 'uninitialized' warning */ - int err = 0; - BIGNUM *A, *B, *tmp; - - /* In 'tab', only odd-indexed entries are relevant: - * For any odd BIGNUM n, - * tab[BN_lsw(n) & 7] - * is $(-1)^{(n^2-1)/8}$ (using TeX notation). - * Note that the sign of n does not matter. - */ + /* tab[BN_lsw(n) & 7] = (-1)^((n^2 - 1)) / 8) for odd values of n. */ static const int tab[8] = {0, 1, 0, -1, 0, -1, 0, 1}; + BIGNUM *A, *B, *tmp; + int k, v; + int ret = -2; bn_check_top(a); bn_check_top(b); BN_CTX_start(ctx); + if ((A = BN_CTX_get(ctx)) == NULL) goto end; if ((B = BN_CTX_get(ctx)) == NULL) goto end; - err = !BN_copy(A, a); - if (err) + if (BN_copy(A, a) == NULL) goto end; - err = !BN_copy(B, b); - if (err) + if (BN_copy(B, b) == NULL) goto end; /* - * Kronecker symbol, imlemented according to Henri Cohen, - * "A Course in Computational Algebraic Number Theory" - * (algorithm 1.4.10). + * Cohen's step 1: */ - /* Cohen's step 1: */ - + /* If B is zero, output 1 if |A| is 1, otherwise output 0. */ if (BN_is_zero(B)) { ret = BN_abs_is_word(A, 1); goto end; } - /* Cohen's step 2: */ + /* + * Cohen's step 2: + */ + /* If both are even, they have a factor in common, so output 0. */ if (!BN_is_odd(A) && !BN_is_odd(B)) { ret = 0; goto end; } - /* now B is non-zero */ - i = 0; - while (!BN_is_bit_set(B, i)) - i++; - err = !BN_rshift(B, B, i); - if (err) + /* Factorize B = 2^v * u with odd u and replace B with u. */ + v = 0; + while (!BN_is_bit_set(B, v)) + v++; + if (!BN_rshift(B, B, v)) goto end; - if (i & 1) { - /* i is odd */ - /* (thus B was even, thus A must be odd!) */ - - /* set 'ret' to $(-1)^{(A^2-1)/8}$ */ - ret = tab[BN_lsw(A) & 7]; - } else { - /* i is even */ - ret = 1; - } - if (B->neg) { - B->neg = 0; - if (A->neg) - ret = -ret; + /* If v is even set k = 1, otherwise set it to (-1)^((A^2 - 1) / 8). */ + k = 1; + if (v % 2 != 0) + k = tab[BN_lsw(A) & 7]; + + /* + * If B is negative, replace it with -B and if A is also negative + * replace k with -k. + */ + if (BN_is_negative(B)) { + BN_set_negative(B, 0); + + if (BN_is_negative(A)) + k = -k; } - /* now B is positive and odd, so what remains to be done is - * to compute the Jacobi symbol (A/B) and multiply it by 'ret' */ + /* + * Now B is positive and odd, so compute the Jacobi symbol (A/B) + * and multiply it by k. + */ while (1) { - /* Cohen's step 3: */ + /* + * Cohen's step 3: + */ - /* B is positive and odd */ + /* B is positive and odd. */ + /* If A is zero output k if B is one, otherwise output 0. */ if (BN_is_zero(A)) { - ret = BN_is_one(B) ? ret : 0; + ret = BN_is_one(B) ? k : 0; goto end; } - /* now A is non-zero */ - i = 0; - while (!BN_is_bit_set(A, i)) - i++; - err = !BN_rshift(A, A, i); - if (err) + /* Factorize A = 2^v * u with odd u and replace A with u. */ + v = 0; + while (!BN_is_bit_set(A, v)) + v++; + if (!BN_rshift(A, A, v)) goto end; - if (i & 1) { - /* i is odd */ - /* multiply 'ret' by $(-1)^{(B^2-1)/8}$ */ - ret = ret * tab[BN_lsw(B) & 7]; - } - - /* Cohen's step 4: */ - /* multiply 'ret' by $(-1)^{(A-1)(B-1)/4}$ */ - if ((A->neg ? ~BN_lsw(A) : BN_lsw(A)) & BN_lsw(B) & 2) - ret = -ret; - /* (A, B) := (B mod |A|, |A|) */ - err = !BN_nnmod(B, B, A, ctx); - if (err) + /* If v is odd, multiply k with (-1)^((B^2 - 1) / 8). */ + if (v % 2 != 0) + k *= tab[BN_lsw(B) & 7]; + + /* + * Cohen's step 4: + */ + + /* + * Apply the reciprocity law: multiply k by (-1)^((A-1)(B-1)/4). + * + * This expression is -1 if and only if A and B are 3 (mod 4). + * In turn, this is the case if and only if their two's + * complement representations have the second bit set. + * A could be negative in the first iteration, B is positive. + */ + if ((BN_is_negative(A) ? ~BN_lsw(A) : BN_lsw(A)) & BN_lsw(B) & 2) + k = -k; + + /* + * (A, B) := (B mod |A|, |A|) + * + * Once this is done, we know that 0 < A < B at the start of the + * loop. Since B is strictly decreasing, the loop terminates. + */ + + if (!BN_nnmod(B, B, A, ctx)) goto end; + tmp = A; A = B; B = tmp; - tmp->neg = 0; + + BN_set_negative(B, 0); } -end: + end: BN_CTX_end(ctx); - if (err) - return -2; - else - return ret; + + return ret; } -- 2.20.1