From ec07a3cad870cfc90b624b386e4200c1264fe56a Mon Sep 17 00:00:00 2001 From: tb Date: Mon, 20 Jun 2022 19:38:25 +0000 Subject: [PATCH] Flip roles of lowercase and uppercase A and B. This matches Cohen's text better and makes the entire thing easier to read. suggested by jsing --- lib/libcrypto/bn/bn_kron.c | 88 +++++++++++++++++++------------------- 1 file changed, 44 insertions(+), 44 deletions(-) diff --git a/lib/libcrypto/bn/bn_kron.c b/lib/libcrypto/bn/bn_kron.c index c7bc53535e8..774e9cef30d 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.7 2022/06/20 19:32:35 tb Exp $ */ +/* $OpenBSD: bn_kron.c,v 1.8 2022/06/20 19:38:25 tb Exp $ */ /* ==================================================================== * Copyright (c) 1998-2000 The OpenSSL Project. All rights reserved. * @@ -66,36 +66,36 @@ */ int -BN_kronecker(const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) +BN_kronecker(const BIGNUM *A, const BIGNUM *B, BN_CTX *ctx) { /* 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; + BIGNUM *a, *b, *tmp; int k, v; int ret = -2; - bn_check_top(a); - bn_check_top(b); + bn_check_top(A); + bn_check_top(B); BN_CTX_start(ctx); - if ((A = BN_CTX_get(ctx)) == NULL) + if ((a = BN_CTX_get(ctx)) == NULL) goto end; - if ((B = BN_CTX_get(ctx)) == NULL) + if ((b = BN_CTX_get(ctx)) == NULL) goto end; - if (BN_copy(A, a) == NULL) + if (BN_copy(a, A) == NULL) goto end; - if (BN_copy(B, b) == NULL) + if (BN_copy(b, B) == NULL) goto end; /* * 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); + /* 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; } @@ -104,36 +104,36 @@ BN_kronecker(const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) */ /* If both are even, they have a factor in common, so output 0. */ - if (!BN_is_odd(A) && !BN_is_odd(B)) { + if (!BN_is_odd(a) && !BN_is_odd(b)) { ret = 0; goto end; } - /* Factorize B = 2^v * u with odd u and replace B with u. */ + /* Factorize b = 2^v * u with odd u and replace b with u. */ v = 0; - while (!BN_is_bit_set(B, v)) + while (!BN_is_bit_set(b, v)) v++; - if (!BN_rshift(B, B, v)) + if (!BN_rshift(b, b, v)) goto end; - /* If v is even set k = 1, otherwise set it to (-1)^((A^2 - 1) / 8). */ + /* 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]; + k = tab[BN_lsw(a) & 7]; /* - * If B is negative, replace it with -B and if A is also negative + * 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(b)) { + BN_set_negative(b, 0); - if (BN_is_negative(A)) + if (BN_is_negative(a)) k = -k; } /* - * Now B is positive and odd, so compute the Jacobi symbol (A/B) + * Now b is positive and odd, so compute the Jacobi symbol (a/b) * and multiply it by k. */ @@ -142,55 +142,55 @@ BN_kronecker(const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) * 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) ? k : 0; + /* If a is zero output k if b is one, otherwise output 0. */ + if (BN_is_zero(a)) { + ret = BN_is_one(b) ? k : 0; goto end; } - /* Factorize A = 2^v * u with odd u and replace A with u. */ + /* Factorize a = 2^v * u with odd u and replace a with u. */ v = 0; - while (!BN_is_bit_set(A, v)) + while (!BN_is_bit_set(a, v)) v++; - if (!BN_rshift(A, A, v)) + if (!BN_rshift(a, a, v)) goto end; - /* If v is odd, multiply k with (-1)^((B^2 - 1) / 8). */ + /* If v is odd, multiply k with (-1)^((b^2 - 1) / 8). */ if (v % 2 != 0) - k *= tab[BN_lsw(B) & 7]; + k *= tab[BN_lsw(b) & 7]; /* * Cohen's step 4: */ /* - * Apply the reciprocity law: multiply k by (-1)^((A-1)(B-1)/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). + * 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. + * 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) + if ((BN_is_negative(a) ? ~BN_lsw(a) : BN_lsw(a)) & BN_lsw(b) & 2) k = -k; /* - * (A, B) := (B mod |A|, |A|) + * (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. + * 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)) + if (!BN_nnmod(b, b, a, ctx)) goto end; - tmp = A; - A = B; - B = tmp; + tmp = a; + a = b; + b = tmp; - BN_set_negative(B, 0); + BN_set_negative(b, 0); } end: -- 2.20.1