| commit | 0fc57bef1821c163ac023a0aa96e4fb2a67c0d82 | [log] [tgz] |
|---|---|---|
| author | James Muir <muir.james.a@gmail.com> | Sun Jan 16 09:28:34 2022 -0500 |
| committer | Boringssl LUCI CQ <boringssl-scoped@luci-project-accounts.iam.gserviceaccount.com> | Thu Jan 27 20:02:40 2022 +0000 |
| tree | 2a9ec3484d9c94f69ae14c7f9c7d81c7795eb652 | |
| parent | 0f4454c07545e6f4465ad88e83fcbaa95a08d28f [diff] |
Simpler square-root computation for Ed25519 Description: Mark Wooden and Franck Rondepierre noted that the square-root-mod-p operations used in the EdDSA RFC (RFC 8032) can be simplified. For Ed25519, instead of computing u*v^3 * (u * v^7)^((p-5)/8), we can compute u * (u*v)^((p-5)/8). This saves 3 multiplications and 2 squarings. For more details (including a proof), see the following message from the CFRG mailing list: https://mailarchive.ietf.org/arch/msg/cfrg/qlKpMBqxXZYmDpXXIx6LO3Oznv4/ Testing: Build and run the Ed25519 tests: mkdir build cd build cmake -GNinja .. ninja && ./crypto/crypto_test --gtest_filter="Ed25519Test*" Numerical testing of the square-root computation can be done using the following sage script: def legendre(x,p): return kronecker(x,p) # Ed25519 p = 2**255-19 # -1 is a square if legendre(-1,p)==1: print("-1 is a square") # 2 is a non-square if legendre(2,p)==-1: print("2 is a non-square") # 2 is a generator # this can be checked by factoring p-1 # and then showing 2**((p-1)/q) != 1 (mod p) # for all primes q dividing p-1. # suppose u/v is a square. # to compute one of its square roots, find x such that # x**4 == (u/v)**2 . # this implies # x**2 == u/v, or # x**2 == -(u/v) , # which implies either x or i*x is a square-root of u/v (where i is a square root of -1). # we can take x equal to u * (u*v)**((p-5)/8). g = 2 s = p>>2 # s = (p-1)/4 i = power_mod(g, s, p) t = p>>3 # t = (p-5)/8 COUNT = 1<<18 while COUNT > 0: COUNT -= 1 r = randint(0,p-1) # r = u/v v = randint(1,p-1) u = mod(r*v,p) # compute x = u * (u*v)**((p-5)/8) w = mod(u*v,p) x = mod(u*power_mod(w, t, p), p) # check that x**2 == r, or (i*x)**2 == r, or r is not a square rr = power_mod(x, 2, p) if rr==r: continue rr = power_mod(mod(i*x,p), 2, p) if rr==r: continue if legendre(r,p) != 1: continue print("failure!") exit() print("passed!") Change-Id: Iaa284d3365dd8c9fa18a4584121013f05a3f4cc6 Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/50965 Reviewed-by: David Benjamin <davidben@google.com> Reviewed-by: Adam Langley <agl@google.com> Commit-Queue: Adam Langley <agl@google.com>
BoringSSL is a fork of OpenSSL that is designed to meet Google's needs.
Although BoringSSL is an open source project, it is not intended for general use, as OpenSSL is. We don't recommend that third parties depend upon it. Doing so is likely to be frustrating because there are no guarantees of API or ABI stability.
Programs ship their own copies of BoringSSL when they use it and we update everything as needed when deciding to make API changes. This allows us to mostly avoid compromises in the name of compatibility. It works for us, but it may not work for you.
BoringSSL arose because Google used OpenSSL for many years in various ways and, over time, built up a large number of patches that were maintained while tracking upstream OpenSSL. As Google's product portfolio became more complex, more copies of OpenSSL sprung up and the effort involved in maintaining all these patches in multiple places was growing steadily.
Currently BoringSSL is the SSL library in Chrome/Chromium, Android (but it's not part of the NDK) and a number of other apps/programs.
Project links:
There are other files in this directory which might be helpful: