tree 97003cee91c39f77902285d494cecb20ada4c050
parent 0d5bf8d86de1aad51e4740ba4e0335d8792b15af
author David Benjamin <davidben@google.com> 1481252139 -0500
committer Adam Langley <agl@google.com> 1493324987 +0000

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>