diff options
Diffstat (limited to 'vendor/filippo.io/edwards25519')
| -rw-r--r-- | vendor/filippo.io/edwards25519/README.md | 2 | ||||
| -rw-r--r-- | vendor/filippo.io/edwards25519/field/fe.go | 31 | ||||
| -rw-r--r-- | vendor/filippo.io/edwards25519/field/fe_extra.go | 50 | ||||
| -rw-r--r-- | vendor/filippo.io/edwards25519/field/fe_generic.go | 2 | ||||
| -rw-r--r-- | vendor/filippo.io/edwards25519/scalar.go | 11 |
5 files changed, 76 insertions, 20 deletions
diff --git a/vendor/filippo.io/edwards25519/README.md b/vendor/filippo.io/edwards25519/README.md index e87d1654..2606f40b 100644 --- a/vendor/filippo.io/edwards25519/README.md +++ b/vendor/filippo.io/edwards25519/README.md @@ -7,7 +7,7 @@ import "filippo.io/edwards25519" This library implements the edwards25519 elliptic curve, exposing the necessary APIs to build a wide array of higher-level primitives. Read the docs at [pkg.go.dev/filippo.io/edwards25519](https://pkg.go.dev/filippo.io/edwards25519). -The code is originally derived from Adam Langley's internal implementation in the Go standard library, and includes George Tankersley's [performance improvements](https://golang.org/cl/71950). It was then further developed by Henry de Valence for use in ristretto255. +The code is originally derived from Adam Langley's internal implementation in the Go standard library, and includes George Tankersley's [performance improvements](https://golang.org/cl/71950). It was then further developed by Henry de Valence for use in ristretto255, and was finally [merged back into the Go standard library](https://golang.org/cl/276272) as of Go 1.17. It now tracks the upstream codebase and extends it with additional functionality. Most users don't need this package, and should instead use `crypto/ed25519` for signatures, `golang.org/x/crypto/curve25519` for Diffie-Hellman, or `github.com/gtank/ristretto255` for prime order group logic. However, for anyone currently using a fork of `crypto/ed25519/internal/edwards25519` or `github.com/agl/edwards25519`, this package should be a safer, faster, and more powerful alternative. diff --git a/vendor/filippo.io/edwards25519/field/fe.go b/vendor/filippo.io/edwards25519/field/fe.go index e5f53859..5518ef2b 100644 --- a/vendor/filippo.io/edwards25519/field/fe.go +++ b/vendor/filippo.io/edwards25519/field/fe.go @@ -188,12 +188,13 @@ func (v *Element) Set(a *Element) *Element { } // SetBytes sets v to x, where x is a 32-byte little-endian encoding. If x is -// not of the right length, SetUniformBytes returns nil and an error, and the +// not of the right length, SetBytes returns nil and an error, and the // receiver is unchanged. // // Consistent with RFC 7748, the most significant bit (the high bit of the // last byte) is ignored, and non-canonical values (2^255-19 through 2^255-1) -// are accepted. Note that this is laxer than specified by RFC 8032. +// are accepted. Note that this is laxer than specified by RFC 8032, but +// consistent with most Ed25519 implementations. func (v *Element) SetBytes(x []byte) (*Element, error) { if len(x) != 32 { return nil, errors.New("edwards25519: invalid field element input size") @@ -211,7 +212,7 @@ func (v *Element) SetBytes(x []byte) (*Element, error) { // Bits 153:204 (bytes 19:27, bits 152:216, shift 1, mask 51). v.l3 = binary.LittleEndian.Uint64(x[19:27]) >> 1 v.l3 &= maskLow51Bits - // Bits 204:251 (bytes 24:32, bits 192:256, shift 12, mask 51). + // Bits 204:255 (bytes 24:32, bits 192:256, shift 12, mask 51). // Note: not bytes 25:33, shift 4, to avoid overread. v.l4 = binary.LittleEndian.Uint64(x[24:32]) >> 12 v.l4 &= maskLow51Bits @@ -394,26 +395,26 @@ var sqrtM1 = &Element{1718705420411056, 234908883556509, // If u/v is square, SqrtRatio returns r and 1. If u/v is not square, SqrtRatio // sets r according to Section 4.3 of draft-irtf-cfrg-ristretto255-decaf448-00, // and returns r and 0. -func (r *Element) SqrtRatio(u, v *Element) (rr *Element, wasSquare int) { - var a, b Element +func (r *Element) SqrtRatio(u, v *Element) (R *Element, wasSquare int) { + t0 := new(Element) // r = (u * v3) * (u * v7)^((p-5)/8) - v2 := a.Square(v) - uv3 := b.Multiply(u, b.Multiply(v2, v)) - uv7 := a.Multiply(uv3, a.Square(v2)) - r.Multiply(uv3, r.Pow22523(uv7)) + v2 := new(Element).Square(v) + uv3 := new(Element).Multiply(u, t0.Multiply(v2, v)) + uv7 := new(Element).Multiply(uv3, t0.Square(v2)) + rr := new(Element).Multiply(uv3, t0.Pow22523(uv7)) - check := a.Multiply(v, a.Square(r)) // check = v * r^2 + check := new(Element).Multiply(v, t0.Square(rr)) // check = v * r^2 - uNeg := b.Negate(u) + uNeg := new(Element).Negate(u) correctSignSqrt := check.Equal(u) flippedSignSqrt := check.Equal(uNeg) - flippedSignSqrtI := check.Equal(uNeg.Multiply(uNeg, sqrtM1)) + flippedSignSqrtI := check.Equal(t0.Multiply(uNeg, sqrtM1)) - rPrime := b.Multiply(r, sqrtM1) // r_prime = SQRT_M1 * r + rPrime := new(Element).Multiply(rr, sqrtM1) // r_prime = SQRT_M1 * r // r = CT_SELECT(r_prime IF flipped_sign_sqrt | flipped_sign_sqrt_i ELSE r) - r.Select(rPrime, r, flippedSignSqrt|flippedSignSqrtI) + rr.Select(rPrime, rr, flippedSignSqrt|flippedSignSqrtI) - r.Absolute(r) // Choose the nonnegative square root. + r.Absolute(rr) // Choose the nonnegative square root. return r, correctSignSqrt | flippedSignSqrt } diff --git a/vendor/filippo.io/edwards25519/field/fe_extra.go b/vendor/filippo.io/edwards25519/field/fe_extra.go new file mode 100644 index 00000000..699238e9 --- /dev/null +++ b/vendor/filippo.io/edwards25519/field/fe_extra.go @@ -0,0 +1,50 @@ +// Copyright (c) 2021 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package field + +import "errors" + +// This file contains additional functionality that is not included in the +// upstream crypto/ed25519/internal/edwards25519/field package. + +// SetWideBytes sets v to x, where x is a 64-byte little-endian encoding, which +// is reduced modulo the field order. If x is not of the right length, +// SetWideBytes returns nil and an error, and the receiver is unchanged. +// +// SetWideBytes is not necessary to select a uniformly distributed value, and is +// only provided for compatibility: SetBytes can be used instead as the chance +// of bias is less than 2⁻²⁵⁰. +func (v *Element) SetWideBytes(x []byte) (*Element, error) { + if len(x) != 64 { + return nil, errors.New("edwards25519: invalid SetWideBytes input size") + } + + // Split the 64 bytes into two elements, and extract the most significant + // bit of each, which is ignored by SetBytes. + lo, _ := new(Element).SetBytes(x[:32]) + loMSB := uint64(x[31] >> 7) + hi, _ := new(Element).SetBytes(x[32:]) + hiMSB := uint64(x[63] >> 7) + + // The output we want is + // + // v = lo + loMSB * 2²⁵⁵ + hi * 2²⁵⁶ + hiMSB * 2⁵¹¹ + // + // which applying the reduction identity comes out to + // + // v = lo + loMSB * 19 + hi * 2 * 19 + hiMSB * 2 * 19² + // + // l0 will be the sum of a 52 bits value (lo.l0), plus a 5 bits value + // (loMSB * 19), a 6 bits value (hi.l0 * 2 * 19), and a 10 bits value + // (hiMSB * 2 * 19²), so it fits in a uint64. + + v.l0 = lo.l0 + loMSB*19 + hi.l0*2*19 + hiMSB*2*19*19 + v.l1 = lo.l1 + hi.l1*2*19 + v.l2 = lo.l2 + hi.l2*2*19 + v.l3 = lo.l3 + hi.l3*2*19 + v.l4 = lo.l4 + hi.l4*2*19 + + return v.carryPropagate(), nil +} diff --git a/vendor/filippo.io/edwards25519/field/fe_generic.go b/vendor/filippo.io/edwards25519/field/fe_generic.go index bccf8511..d6667b27 100644 --- a/vendor/filippo.io/edwards25519/field/fe_generic.go +++ b/vendor/filippo.io/edwards25519/field/fe_generic.go @@ -254,6 +254,8 @@ func (v *Element) carryPropagateGeneric() *Element { c3 := v.l3 >> 51 c4 := v.l4 >> 51 + // c4 is at most 64 - 51 = 13 bits, so c4*19 is at most 18 bits, and + // the final l0 will be at most 52 bits. Similarly for the rest. v.l0 = v.l0&maskLow51Bits + c4*19 v.l1 = v.l1&maskLow51Bits + c0 v.l2 = v.l2&maskLow51Bits + c1 diff --git a/vendor/filippo.io/edwards25519/scalar.go b/vendor/filippo.io/edwards25519/scalar.go index f3da71ce..3df2fb93 100644 --- a/vendor/filippo.io/edwards25519/scalar.go +++ b/vendor/filippo.io/edwards25519/scalar.go @@ -22,7 +22,7 @@ import ( // The zero value is a valid zero element. type Scalar struct { // s is the Scalar value in little-endian. The value is always reduced - // between operations. + // modulo l between operations. s [32]byte } @@ -79,9 +79,12 @@ func (s *Scalar) Set(x *Scalar) *Scalar { return s } -// SetUniformBytes sets s to an uniformly distributed value given 64 uniformly -// distributed random bytes. If x is not of the right length, SetUniformBytes -// returns nil and an error, and the receiver is unchanged. +// SetUniformBytes sets s = x mod l, where x is a 64-byte little-endian integer. +// If x is not of the right length, SetUniformBytes returns nil and an error, +// and the receiver is unchanged. +// +// SetUniformBytes can be used to set s to an uniformly distributed value given +// 64 uniformly distributed random bytes. func (s *Scalar) SetUniformBytes(x []byte) (*Scalar, error) { if len(x) != 64 { return nil, errors.New("edwards25519: invalid SetUniformBytes input length") |