diff options
author | James Muir <muir.james.a@gmail.com> | 2022-01-18 15:04:33 -0500 |
---|---|---|
committer | Tomas Mraz <tomas@openssl.org> | 2022-11-09 15:32:44 +0100 |
commit | 08043118d1d303921537997543cafeaaae972383 (patch) | |
tree | 9f82a6b1936281352aa4e926677d6029bc79ec50 /crypto/ec | |
parent | 5948336502afca679c0d26e22ae6f9e41c807350 (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/
Note that the Ed448 implementation (see
ossl_curve448_point_decode_like_eddsa_and_mul_by_ratio() in
./crypto/ec/curve448/curve448.c) appears to already use this simpler
method (i.e. it does not follow the method suggested in RFC 8032).
Testing:
Build and then run the test suite:
./Configure -Werror --strict-warnings
make update
make
make test
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")
# 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).
# 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.
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!")
Reviewed-by: Paul Dale <pauli@openssl.org>
Reviewed-by: Tomas Mraz <tomas@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/17544)
(cherry picked from commit a822a0cb3c8466adbcee510a6234c0fe95ff4bfe)
Diffstat (limited to 'crypto/ec')
-rw-r--r-- | crypto/ec/curve25519.c | 13 |
1 files changed, 4 insertions, 9 deletions
diff --git a/crypto/ec/curve25519.c b/crypto/ec/curve25519.c index 50a8e6b169..2b57bd594b 100644 --- a/crypto/ec/curve25519.c +++ b/crypto/ec/curve25519.c @@ -1868,7 +1868,7 @@ static int ge_frombytes_vartime(ge_p3 *h, const uint8_t *s) { fe u; fe v; - fe v3; + fe w; fe vxx; fe check; @@ -1879,15 +1879,10 @@ static int ge_frombytes_vartime(ge_p3 *h, const uint8_t *s) fe_sub(u, u, h->Z); /* u = y^2-1 */ fe_add(v, v, h->Z); /* v = dy^2+1 */ - fe_sq(v3, v); - fe_mul(v3, v3, v); /* v3 = v^3 */ - fe_sq(h->X, v3); - fe_mul(h->X, h->X, v); - fe_mul(h->X, h->X, u); /* x = uv^7 */ + fe_mul(w, u, v); /* w = u*v */ - fe_pow22523(h->X, h->X); /* x = (uv^7)^((q-5)/8) */ - fe_mul(h->X, h->X, v3); - fe_mul(h->X, h->X, u); /* x = uv^3(uv^7)^((q-5)/8) */ + fe_pow22523(h->X, w); /* x = w^((q-5)/8) */ + fe_mul(h->X, h->X, u); /* x = u * w^((q-5)/8) */ fe_sq(vxx, h->X); fe_mul(vxx, vxx, v); |