Downgrade BN_kronecker to bn_jacobi and unexport.
We only ever compute it for odd (actually, prime) modulus as part of
BN_mod_sqrt.
If we cared, we could probably drop this from most binaries. This is
used to when modular square root needs Tonelli-Shanks. Modular square
root is only used for compressed coordinates. Of our supported curves
(I'm handwaiving away EC_GROUP_new_curve_GFp here[*]), only P-224 needs
the full Tonelli-Shanks algorithm (p is 1 mod 8). That computes the
Legendre symbol a bunch to find a non-square mod p. But p is known at
compile-time, so we can just hard-code a sample non-square.
Sadly, BN_mod_sqrt has some callers outside of crypto/ec, so there's
also that. Anyway, it's also not that large of a function.
[*] Glancing through SEC 2 and Brainpool, secp224r1 is the only curve
listed in either document whose prime is not either 3 mod 4 or 5 mod 8.
Even 5 mod 8 is rare: only secp224k1. It's unlikely anyone would notice
if we broke annoying primes. Though OpenSSL does support "WTLS" curves
which has an additional 1 mod 8 case.
Change-Id: If36aa78c0d41253ec024f2d90692949515356cd1
Reviewed-on: https://boringssl-review.googlesource.com/15425
Reviewed-by: Adam Langley <agl@google.com>
diff --git a/crypto/bn/CMakeLists.txt b/crypto/bn/CMakeLists.txt
index 9dd24b4..5da72e9 100644
--- a/crypto/bn/CMakeLists.txt
+++ b/crypto/bn/CMakeLists.txt
@@ -54,7 +54,7 @@
exponentiation.c
generic.c
gcd.c
- kronecker.c
+ jacobi.c
montgomery.c
montgomery_inv.c
mul.c
diff --git a/crypto/bn/internal.h b/crypto/bn/internal.h
index 7a3903b..e90b435 100644
--- a/crypto/bn/internal.h
+++ b/crypto/bn/internal.h
@@ -259,6 +259,10 @@
int bn_mod_inverse_secret_prime(BIGNUM *out, const BIGNUM *a, const BIGNUM *p,
BN_CTX *ctx, const BN_MONT_CTX *mont_p);
+/* bn_jacobi returns the Jacobi symbol of |a| and |b| (which is -1, 0 or 1), or
+ * -2 on error. */
+int bn_jacobi(const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx);
+
#if defined(__cplusplus)
} /* extern C */
diff --git a/crypto/bn/kronecker.c b/crypto/bn/jacobi.c
similarity index 78%
rename from crypto/bn/kronecker.c
rename to crypto/bn/jacobi.c
index 2089851..93e8fd9 100644
--- a/crypto/bn/kronecker.c
+++ b/crypto/bn/jacobi.c
@@ -52,17 +52,15 @@
#include <openssl/bn.h>
+#include <openssl/err.h>
+
#include "internal.h"
/* 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. */
-int BN_kronecker(const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) {
- int i;
- int ret = -2;
- BIGNUM *A, *B, *tmp;
+int bn_jacobi(const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) {
/* In 'tab', only odd-indexed entries are relevant:
* For any odd BIGNUM n,
* tab[BN_lsw(n) & 7]
@@ -70,9 +68,22 @@
* Note that the sign of n does not matter. */
static const int tab[8] = {0, 1, 0, -1, 0, -1, 0, 1};
+ /* The Jacobi symbol is only defined for odd modulus. */
+ if (!BN_is_odd(b)) {
+ OPENSSL_PUT_ERROR(BN, BN_R_CALLED_WITH_EVEN_MODULUS);
+ return -2;
+ }
+
+ /* Require b be positive. */
+ if (BN_is_negative(b)) {
+ OPENSSL_PUT_ERROR(BN, BN_R_NEGATIVE_NUMBER);
+ return -2;
+ }
+
+ int ret = -2;
BN_CTX_start(ctx);
- A = BN_CTX_get(ctx);
- B = BN_CTX_get(ctx);
+ BIGNUM *A = BN_CTX_get(ctx);
+ BIGNUM *B = BN_CTX_get(ctx);
if (B == NULL) {
goto end;
}
@@ -82,52 +93,11 @@
goto end;
}
- /* Kronecker symbol, imlemented according to Henri Cohen,
- * "A Course in Computational Algebraic Number Theory"
- * (algorithm 1.4.10). */
+ /* Adapted from logic to compute the Kronecker symbol, originally implemented
+ * according to Henri Cohen, "A Course in Computational Algebraic Number
+ * Theory" (algorithm 1.4.10). */
- /* Cohen's step 1: */
-
- if (BN_is_zero(B)) {
- ret = BN_abs_is_word(A, 1);
- goto end;
- }
-
- /* Cohen's step 2: */
-
- 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++;
- }
- if (!BN_rshift(B, B, i)) {
- 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;
- }
- }
-
- /* 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' */
+ ret = 1;
while (1) {
/* Cohen's step 3: */
@@ -139,7 +109,7 @@
}
/* now A is non-zero */
- i = 0;
+ int i = 0;
while (!BN_is_bit_set(A, i)) {
i++;
}
@@ -164,7 +134,7 @@
ret = -2;
goto end;
}
- tmp = A;
+ BIGNUM *tmp = A;
A = B;
B = tmp;
tmp->neg = 0;
diff --git a/crypto/bn/sqrt.c b/crypto/bn/sqrt.c
index f806ea2..0342bc0 100644
--- a/crypto/bn/sqrt.c
+++ b/crypto/bn/sqrt.c
@@ -56,6 +56,8 @@
#include <openssl/err.h>
+#include "internal.h"
+
BIGNUM *BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) {
/* Compute a square root of |a| mod |p| using the Tonelli/Shanks algorithm
@@ -253,7 +255,7 @@
}
}
- r = BN_kronecker(y, q, ctx); /* here 'q' is |p| */
+ r = bn_jacobi(y, q, ctx); /* here 'q' is |p| */
if (r < -1) {
goto end;
}
diff --git a/include/openssl/bn.h b/include/openssl/bn.h
index 49d4495..5ebdade 100644
--- a/include/openssl/bn.h
+++ b/include/openssl/bn.h
@@ -797,10 +797,6 @@
int BN_mod_inverse_odd(BIGNUM *out, int *out_no_inverse, const BIGNUM *a,
const BIGNUM *n, BN_CTX *ctx);
-/* BN_kronecker returns the Kronecker symbol of |a| and |b| (which is -1, 0 or
- * 1), or -2 on error. */
-OPENSSL_EXPORT int BN_kronecker(const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx);
-
/* Montgomery arithmetic. */
