Source File
scalar.go
Belonging Package
crypto/internal/fips140/edwards25519
// Copyright (c) 2016 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 edwards25519
import (
)
// A Scalar is an integer modulo
//
// l = 2^252 + 27742317777372353535851937790883648493
//
// which is the prime order of the edwards25519 group.
//
// This type works similarly to math/big.Int, and all arguments and
// receivers are allowed to alias.
//
// The zero value is a valid zero element.
type Scalar struct {
// s is the scalar in the Montgomery domain, in the format of the
// fiat-crypto implementation.
s fiatScalarMontgomeryDomainFieldElement
}
// The field implementation in scalar_fiat.go is generated by the fiat-crypto
// project (https://github.com/mit-plv/fiat-crypto) at version v0.0.9 (23d2dbc)
// from a formally verified model.
//
// fiat-crypto code comes under the following license.
//
// Copyright (c) 2015-2020 The fiat-crypto Authors. All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
// 1. Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
//
// THIS SOFTWARE IS PROVIDED BY the fiat-crypto authors "AS IS"
// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
// THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL Berkeley Software Design,
// Inc. BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
//
// NewScalar returns a new zero Scalar.
func () *Scalar {
return &Scalar{}
}
// MultiplyAdd sets s = x * y + z mod l, and returns s. It is equivalent to
// using Multiply and then Add.
func ( *Scalar) (, , *Scalar) *Scalar {
// Make a copy of z in case it aliases s.
:= new(Scalar).Set()
return .Multiply(, ).Add(, )
}
// Add sets s = x + y mod l, and returns s.
func ( *Scalar) (, *Scalar) *Scalar {
// s = 1 * x + y mod l
fiatScalarAdd(&.s, &.s, &.s)
return
}
// Subtract sets s = x - y mod l, and returns s.
func ( *Scalar) (, *Scalar) *Scalar {
// s = -1 * y + x mod l
fiatScalarSub(&.s, &.s, &.s)
return
}
// Negate sets s = -x mod l, and returns s.
func ( *Scalar) ( *Scalar) *Scalar {
// s = -1 * x + 0 mod l
fiatScalarOpp(&.s, &.s)
return
}
// Multiply sets s = x * y mod l, and returns s.
func ( *Scalar) (, *Scalar) *Scalar {
// s = x * y + 0 mod l
fiatScalarMul(&.s, &.s, &.s)
return
}
// Set sets s = x, and returns s.
func ( *Scalar) ( *Scalar) *Scalar {
* = *
return
}
// 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 a uniformly distributed value given
// 64 uniformly distributed random bytes.
func ( *Scalar) ( []byte) (*Scalar, error) {
if len() != 64 {
return nil, errors.New("edwards25519: invalid SetUniformBytes input length")
}
// We have a value x of 512 bits, but our fiatScalarFromBytes function
// expects an input lower than l, which is a little over 252 bits.
//
// Instead of writing a reduction function that operates on wider inputs, we
// can interpret x as the sum of three shorter values a, b, and c.
//
// x = a + b * 2^168 + c * 2^336 mod l
//
// We then precompute 2^168 and 2^336 modulo l, and perform the reduction
// with two multiplications and two additions.
.setShortBytes([:21])
:= new(Scalar).setShortBytes([21:42])
.Add(, .Multiply(, scalarTwo168))
.setShortBytes([42:])
.Add(, .Multiply(, scalarTwo336))
return , nil
}
// scalarTwo168 and scalarTwo336 are 2^168 and 2^336 modulo l, encoded as a
// fiatScalarMontgomeryDomainFieldElement, which is a little-endian 4-limb value
// in the 2^256 Montgomery domain.
var scalarTwo168 = &Scalar{s: [4]uint64{0x5b8ab432eac74798, 0x38afddd6de59d5d7,
0xa2c131b399411b7c, 0x6329a7ed9ce5a30}}
var scalarTwo336 = &Scalar{s: [4]uint64{0xbd3d108e2b35ecc5, 0x5c3a3718bdf9c90b,
0x63aa97a331b4f2ee, 0x3d217f5be65cb5c}}
// setShortBytes sets s = x mod l, where x is a little-endian integer shorter
// than 32 bytes.
func ( *Scalar) ( []byte) *Scalar {
if len() >= 32 {
panic("edwards25519: internal error: setShortBytes called with a long string")
}
var [32]byte
copy([:], )
fiatScalarFromBytes((*[4]uint64)(&.s), &)
fiatScalarToMontgomery(&.s, (*fiatScalarNonMontgomeryDomainFieldElement)(&.s))
return
}
// SetCanonicalBytes sets s = x, where x is a 32-byte little-endian encoding of
// s, and returns s. If x is not a canonical encoding of s, SetCanonicalBytes
// returns nil and an error, and the receiver is unchanged.
func ( *Scalar) ( []byte) (*Scalar, error) {
if len() != 32 {
return nil, errors.New("invalid scalar length")
}
if !isReduced() {
return nil, errors.New("invalid scalar encoding")
}
fiatScalarFromBytes((*[4]uint64)(&.s), (*[32]byte)())
fiatScalarToMontgomery(&.s, (*fiatScalarNonMontgomeryDomainFieldElement)(&.s))
return , nil
}
// scalarMinusOneBytes is l - 1 in little endian.
var scalarMinusOneBytes = [32]byte{236, 211, 245, 92, 26, 99, 18, 88, 214, 156, 247, 162, 222, 249, 222, 20, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 16}
// isReduced returns whether the given scalar in 32-byte little endian encoded
// form is reduced modulo l.
func isReduced( []byte) bool {
if len() != 32 {
return false
}
for := len() - 1; >= 0; -- {
switch {
case [] > scalarMinusOneBytes[]:
return false
case [] < scalarMinusOneBytes[]:
return true
}
}
return true
}
// SetBytesWithClamping applies the buffer pruning described in RFC 8032,
// Section 5.1.5 (also known as clamping) and sets s to the result. The input
// must be 32 bytes, and it is not modified. If x is not of the right length,
// SetBytesWithClamping returns nil and an error, and the receiver is unchanged.
//
// Note that since Scalar values are always reduced modulo the prime order of
// the curve, the resulting value will not preserve any of the cofactor-clearing
// properties that clamping is meant to provide. It will however work as
// expected as long as it is applied to points on the prime order subgroup, like
// in Ed25519. In fact, it is lost to history why RFC 8032 adopted the
// irrelevant RFC 7748 clamping, but it is now required for compatibility.
func ( *Scalar) ( []byte) (*Scalar, error) {
// The description above omits the purpose of the high bits of the clamping
// for brevity, but those are also lost to reductions, and are also
// irrelevant to edwards25519 as they protect against a specific
// implementation bug that was once observed in a generic Montgomery ladder.
if len() != 32 {
return nil, errors.New("edwards25519: invalid SetBytesWithClamping input length")
}
// We need to use the wide reduction from SetUniformBytes, since clamping
// sets the 2^254 bit, making the value higher than the order.
var [64]byte
copy([:], [:])
[0] &= 248
[31] &= 63
[31] |= 64
return .SetUniformBytes([:])
}
// Bytes returns the canonical 32-byte little-endian encoding of s.
func ( *Scalar) () []byte {
// This function is outlined to make the allocations inline in the caller
// rather than happen on the heap.
var [32]byte
return .bytes(&)
}
func ( *Scalar) ( *[32]byte) []byte {
var fiatScalarNonMontgomeryDomainFieldElement
fiatScalarFromMontgomery(&, &.s)
fiatScalarToBytes(, (*[4]uint64)(&))
return [:]
}
// Equal returns 1 if s and t are equal, and 0 otherwise.
func ( *Scalar) ( *Scalar) int {
var fiatScalarMontgomeryDomainFieldElement
fiatScalarSub(&, &.s, &.s)
var uint64
fiatScalarNonzero(&, (*[4]uint64)(&))
|= >> 32
|= >> 16
|= >> 8
|= >> 4
|= >> 2
|= >> 1
return int(^) & 1
}
// nonAdjacentForm computes a width-w non-adjacent form for this scalar.
//
// w must be between 2 and 8, or nonAdjacentForm will panic.
func ( *Scalar) ( uint) [256]int8 {
// This implementation is adapted from the one
// in curve25519-dalek and is documented there:
// https://github.com/dalek-cryptography/curve25519-dalek/blob/f630041af28e9a405255f98a8a93adca18e4315b/src/scalar.rs#L800-L871
:= .Bytes()
if [31] > 127 {
panic("scalar has high bit set illegally")
}
if < 2 {
panic("w must be at least 2 by the definition of NAF")
} else if > 8 {
panic("NAF digits must fit in int8")
}
var [256]int8
var [5]uint64
for := 0; < 4; ++ {
[] = byteorder.LEUint64([*8:])
}
:= uint64(1 << )
:= uint64( - 1)
:= uint(0)
:= uint64(0)
for < 256 {
:= / 64
:= % 64
var uint64
if < 64- {
// This window's bits are contained in a single u64
= [] >>
} else {
// Combine the current 64 bits with bits from the next 64
= ([] >> ) | ([1+] << (64 - ))
}
// Add carry into the current window
:= + ( & )
if &1 == 0 {
// If the window value is even, preserve the carry and continue.
// Why is the carry preserved?
// If carry == 0 and window & 1 == 0,
// then the next carry should be 0
// If carry == 1 and window & 1 == 0,
// then bit_buf & 1 == 1 so the next carry should be 1
+= 1
continue
}
if < /2 {
= 0
[] = int8()
} else {
= 1
[] = int8() - int8()
}
+=
}
return
}
func ( *Scalar) () [64]int8 {
:= .Bytes()
if [31] > 127 {
panic("scalar has high bit set illegally")
}
var [64]int8
// Compute unsigned radix-16 digits:
for := 0; < 32; ++ {
[2*] = int8([] & 15)
[2*+1] = int8(([] >> 4) & 15)
}
// Recenter coefficients:
for := 0; < 63; ++ {
:= ([] + 8) >> 4
[] -= << 4
[+1] +=
}
return
}
The pages are generated with Golds v0.7.3-preview. (GOOS=linux GOARCH=amd64) Golds is a Go 101 project developed by Tapir Liu. PR and bug reports are welcome and can be submitted to the issue list. Please follow @zigo_101 (reachable from the left QR code) to get the latest news of Golds. |