scalar.go

     1  // Copyright (c) 2016 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package edwards25519
     6  
     7  import (
     8  	"crypto/internal/fips140deps/byteorder"
     9  	"errors"
    10  	"math/bits"
    11  )
    12  
    13  // A Scalar is an integer modulo
    14  //
    15  //	l = 2^252 + 27742317777372353535851937790883648493
    16  //
    17  // which is the prime order of the edwards25519 group.
    18  //
    19  // This type works similarly to math/big.Int, and all arguments and
    20  // receivers are allowed to alias.
    21  //
    22  // The zero value is a valid zero element.
    23  type Scalar struct {
    24  	// s is the scalar in the Montgomery domain, in the format of the
    25  	// fiat-crypto implementation.
    26  	s fiatScalarMontgomeryDomainFieldElement
    27  }
    28  
    29  // The field implementation in scalar_fiat.go is generated by the fiat-crypto
    30  // project (https://github.com/mit-plv/fiat-crypto) at version v0.0.9 (23d2dbc)
    31  // from a formally verified model.
    32  //
    33  // fiat-crypto code comes under the following license.
    34  //
    35  //     Copyright (c) 2015-2020 The fiat-crypto Authors. All rights reserved.
    36  //
    37  //     Redistribution and use in source and binary forms, with or without
    38  //     modification, are permitted provided that the following conditions are
    39  //     met:
    40  //
    41  //         1. Redistributions of source code must retain the above copyright
    42  //         notice, this list of conditions and the following disclaimer.
    43  //
    44  //     THIS SOFTWARE IS PROVIDED BY the fiat-crypto authors "AS IS"
    45  //     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
    46  //     THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
    47  //     PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL Berkeley Software Design,
    48  //     Inc. BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
    49  //     EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
    50  //     PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
    51  //     PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
    52  //     LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
    53  //     NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
    54  //     SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
    55  //
    56  
    57  // NewScalar returns a new zero Scalar.
    58  func NewScalar() *Scalar {
    59  	return &Scalar{}
    60  }
    61  
    62  // MultiplyAdd sets s = x * y + z mod l, and returns s. It is equivalent to
    63  // using Multiply and then Add.
    64  func (s *Scalar) MultiplyAdd(x, y, z *Scalar) *Scalar {
    65  	// Make a copy of z in case it aliases s.
    66  	zCopy := new(Scalar).Set(z)
    67  	return s.Multiply(x, y).Add(s, zCopy)
    68  }
    69  
    70  // Add sets s = x + y mod l, and returns s.
    71  func (s *Scalar) Add(x, y *Scalar) *Scalar {
    72  	// s = 1 * x + y mod l
    73  	fiatScalarAdd(&s.s, &x.s, &y.s)
    74  	return s
    75  }
    76  
    77  // Subtract sets s = x - y mod l, and returns s.
    78  func (s *Scalar) Subtract(x, y *Scalar) *Scalar {
    79  	// s = -1 * y + x mod l
    80  	fiatScalarSub(&s.s, &x.s, &y.s)
    81  	return s
    82  }
    83  
    84  // Negate sets s = -x mod l, and returns s.
    85  func (s *Scalar) Negate(x *Scalar) *Scalar {
    86  	// s = -1 * x + 0 mod l
    87  	fiatScalarOpp(&s.s, &x.s)
    88  	return s
    89  }
    90  
    91  // Multiply sets s = x * y mod l, and returns s.
    92  func (s *Scalar) Multiply(x, y *Scalar) *Scalar {
    93  	// s = x * y + 0 mod l
    94  	fiatScalarMul(&s.s, &x.s, &y.s)
    95  	return s
    96  }
    97  
    98  // Set sets s = x, and returns s.
    99  func (s *Scalar) Set(x *Scalar) *Scalar {
   100  	*s = *x
   101  	return s
   102  }
   103  
   104  // SetUniformBytes sets s = x mod l, where x is a 64-byte little-endian integer.
   105  // If x is not of the right length, SetUniformBytes returns nil and an error,
   106  // and the receiver is unchanged.
   107  //
   108  // SetUniformBytes can be used to set s to a uniformly distributed value given
   109  // 64 uniformly distributed random bytes.
   110  func (s *Scalar) SetUniformBytes(x []byte) (*Scalar, error) {
   111  	if len(x) != 64 {
   112  		return nil, errors.New("edwards25519: invalid SetUniformBytes input length")
   113  	}
   114  
   115  	// We have a value x of 512 bits, but our fiatScalarFromBytes function
   116  	// expects an input lower than l, which is a little over 252 bits.
   117  	//
   118  	// Instead of writing a reduction function that operates on wider inputs, we
   119  	// can interpret x as the sum of three shorter values a, b, and c.
   120  	//
   121  	//    x = a + b * 2^168 + c * 2^336  mod l
   122  	//
   123  	// We then precompute 2^168 and 2^336 modulo l, and perform the reduction
   124  	// with two multiplications and two additions.
   125  
   126  	s.setShortBytes(x[:21])
   127  	t := new(Scalar).setShortBytes(x[21:42])
   128  	s.Add(s, t.Multiply(t, scalarTwo168))
   129  	t.setShortBytes(x[42:])
   130  	s.Add(s, t.Multiply(t, scalarTwo336))
   131  
   132  	return s, nil
   133  }
   134  
   135  // scalarTwo168 and scalarTwo336 are 2^168 and 2^336 modulo l, encoded as a
   136  // fiatScalarMontgomeryDomainFieldElement, which is a little-endian 4-limb value
   137  // in the 2^256 Montgomery domain.
   138  var scalarTwo168 = &Scalar{s: [4]uint64{0x5b8ab432eac74798, 0x38afddd6de59d5d7,
   139  	0xa2c131b399411b7c, 0x6329a7ed9ce5a30}}
   140  var scalarTwo336 = &Scalar{s: [4]uint64{0xbd3d108e2b35ecc5, 0x5c3a3718bdf9c90b,
   141  	0x63aa97a331b4f2ee, 0x3d217f5be65cb5c}}
   142  
   143  // setShortBytes sets s = x mod l, where x is a little-endian integer shorter
   144  // than 32 bytes.
   145  func (s *Scalar) setShortBytes(x []byte) *Scalar {
   146  	if len(x) >= 32 {
   147  		panic("edwards25519: internal error: setShortBytes called with a long string")
   148  	}
   149  	var buf [32]byte
   150  	copy(buf[:], x)
   151  	fiatScalarFromBytes((*[4]uint64)(&s.s), &buf)
   152  	fiatScalarToMontgomery(&s.s, (*fiatScalarNonMontgomeryDomainFieldElement)(&s.s))
   153  	return s
   154  }
   155  
   156  // SetCanonicalBytes sets s = x, where x is a 32-byte little-endian encoding of
   157  // s, and returns s. If x is not a canonical encoding of s, SetCanonicalBytes
   158  // returns nil and an error, and the receiver is unchanged.
   159  func (s *Scalar) SetCanonicalBytes(x []byte) (*Scalar, error) {
   160  	if len(x) != 32 {
   161  		return nil, errors.New("invalid scalar length")
   162  	}
   163  	if !isReduced(x) {
   164  		return nil, errors.New("invalid scalar encoding")
   165  	}
   166  
   167  	fiatScalarFromBytes((*[4]uint64)(&s.s), (*[32]byte)(x))
   168  	fiatScalarToMontgomery(&s.s, (*fiatScalarNonMontgomeryDomainFieldElement)(&s.s))
   169  
   170  	return s, nil
   171  }
   172  
   173  // scalarMinusOneBytes is l - 1 in little endian.
   174  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}
   175  
   176  // isReduced returns whether the given scalar in 32-byte little endian encoded
   177  // form is reduced modulo l.
   178  func isReduced(s []byte) bool {
   179  	if len(s) != 32 {
   180  		return false
   181  	}
   182  
   183  	s0 := byteorder.LEUint64(s[:8])
   184  	s1 := byteorder.LEUint64(s[8:16])
   185  	s2 := byteorder.LEUint64(s[16:24])
   186  	s3 := byteorder.LEUint64(s[24:])
   187  
   188  	l0 := byteorder.LEUint64(scalarMinusOneBytes[:8])
   189  	l1 := byteorder.LEUint64(scalarMinusOneBytes[8:16])
   190  	l2 := byteorder.LEUint64(scalarMinusOneBytes[16:24])
   191  	l3 := byteorder.LEUint64(scalarMinusOneBytes[24:])
   192  
   193  	// Do a constant time subtraction chain scalarMinusOneBytes - s. If there is
   194  	// a borrow at the end, then s > scalarMinusOneBytes.
   195  	_, b := bits.Sub64(l0, s0, 0)
   196  	_, b = bits.Sub64(l1, s1, b)
   197  	_, b = bits.Sub64(l2, s2, b)
   198  	_, b = bits.Sub64(l3, s3, b)
   199  	return b == 0
   200  }
   201  
   202  // SetBytesWithClamping applies the buffer pruning described in RFC 8032,
   203  // Section 5.1.5 (also known as clamping) and sets s to the result. The input
   204  // must be 32 bytes, and it is not modified. If x is not of the right length,
   205  // SetBytesWithClamping returns nil and an error, and the receiver is unchanged.
   206  //
   207  // Note that since Scalar values are always reduced modulo the prime order of
   208  // the curve, the resulting value will not preserve any of the cofactor-clearing
   209  // properties that clamping is meant to provide. It will however work as
   210  // expected as long as it is applied to points on the prime order subgroup, like
   211  // in Ed25519. In fact, it is lost to history why RFC 8032 adopted the
   212  // irrelevant RFC 7748 clamping, but it is now required for compatibility.
   213  func (s *Scalar) SetBytesWithClamping(x []byte) (*Scalar, error) {
   214  	// The description above omits the purpose of the high bits of the clamping
   215  	// for brevity, but those are also lost to reductions, and are also
   216  	// irrelevant to edwards25519 as they protect against a specific
   217  	// implementation bug that was once observed in a generic Montgomery ladder.
   218  	if len(x) != 32 {
   219  		return nil, errors.New("edwards25519: invalid SetBytesWithClamping input length")
   220  	}
   221  
   222  	// We need to use the wide reduction from SetUniformBytes, since clamping
   223  	// sets the 2^254 bit, making the value higher than the order.
   224  	var wideBytes [64]byte
   225  	copy(wideBytes[:], x[:])
   226  	wideBytes[0] &= 248
   227  	wideBytes[31] &= 63
   228  	wideBytes[31] |= 64
   229  	return s.SetUniformBytes(wideBytes[:])
   230  }
   231  
   232  // Bytes returns the canonical 32-byte little-endian encoding of s.
   233  func (s *Scalar) Bytes() []byte {
   234  	// This function is outlined to make the allocations inline in the caller
   235  	// rather than happen on the heap.
   236  	var encoded [32]byte
   237  	return s.bytes(&encoded)
   238  }
   239  
   240  func (s *Scalar) bytes(out *[32]byte) []byte {
   241  	var ss fiatScalarNonMontgomeryDomainFieldElement
   242  	fiatScalarFromMontgomery(&ss, &s.s)
   243  	fiatScalarToBytes(out, (*[4]uint64)(&ss))
   244  	return out[:]
   245  }
   246  
   247  // Equal returns 1 if s and t are equal, and 0 otherwise.
   248  func (s *Scalar) Equal(t *Scalar) int {
   249  	var diff fiatScalarMontgomeryDomainFieldElement
   250  	fiatScalarSub(&diff, &s.s, &t.s)
   251  	var nonzero uint64
   252  	fiatScalarNonzero(&nonzero, (*[4]uint64)(&diff))
   253  	nonzero |= nonzero >> 32
   254  	nonzero |= nonzero >> 16
   255  	nonzero |= nonzero >> 8
   256  	nonzero |= nonzero >> 4
   257  	nonzero |= nonzero >> 2
   258  	nonzero |= nonzero >> 1
   259  	return int(^nonzero) & 1
   260  }
   261  
   262  // nonAdjacentForm computes a width-w non-adjacent form for this scalar.
   263  //
   264  // w must be between 2 and 8, or nonAdjacentForm will panic.
   265  func (s *Scalar) nonAdjacentForm(w uint) [256]int8 {
   266  	// This implementation is adapted from the one
   267  	// in curve25519-dalek and is documented there:
   268  	// https://github.com/dalek-cryptography/curve25519-dalek/blob/f630041af28e9a405255f98a8a93adca18e4315b/src/scalar.rs#L800-L871
   269  	b := s.Bytes()
   270  	if b[31] > 127 {
   271  		panic("scalar has high bit set illegally")
   272  	}
   273  	if w < 2 {
   274  		panic("w must be at least 2 by the definition of NAF")
   275  	} else if w > 8 {
   276  		panic("NAF digits must fit in int8")
   277  	}
   278  
   279  	var naf [256]int8
   280  	var digits [5]uint64
   281  
   282  	for i := 0; i < 4; i++ {
   283  		digits[i] = byteorder.LEUint64(b[i*8:])
   284  	}
   285  
   286  	width := uint64(1 << w)
   287  	windowMask := uint64(width - 1)
   288  
   289  	pos := uint(0)
   290  	carry := uint64(0)
   291  	for pos < 256 {
   292  		indexU64 := pos / 64
   293  		indexBit := pos % 64
   294  		var bitBuf uint64
   295  		if indexBit < 64-w {
   296  			// This window's bits are contained in a single u64
   297  			bitBuf = digits[indexU64] >> indexBit
   298  		} else {
   299  			// Combine the current 64 bits with bits from the next 64
   300  			bitBuf = (digits[indexU64] >> indexBit) | (digits[1+indexU64] << (64 - indexBit))
   301  		}
   302  
   303  		// Add carry into the current window
   304  		window := carry + (bitBuf & windowMask)
   305  
   306  		if window&1 == 0 {
   307  			// If the window value is even, preserve the carry and continue.
   308  			// Why is the carry preserved?
   309  			// If carry == 0 and window & 1 == 0,
   310  			//    then the next carry should be 0
   311  			// If carry == 1 and window & 1 == 0,
   312  			//    then bit_buf & 1 == 1 so the next carry should be 1
   313  			pos += 1
   314  			continue
   315  		}
   316  
   317  		if window < width/2 {
   318  			carry = 0
   319  			naf[pos] = int8(window)
   320  		} else {
   321  			carry = 1
   322  			naf[pos] = int8(window) - int8(width)
   323  		}
   324  
   325  		pos += w
   326  	}
   327  	return naf
   328  }
   329  
   330  func (s *Scalar) signedRadix16() [64]int8 {
   331  	b := s.Bytes()
   332  	if b[31] > 127 {
   333  		panic("scalar has high bit set illegally")
   334  	}
   335  
   336  	var digits [64]int8
   337  
   338  	// Compute unsigned radix-16 digits:
   339  	for i := 0; i < 32; i++ {
   340  		digits[2*i] = int8(b[i] & 15)
   341  		digits[2*i+1] = int8((b[i] >> 4) & 15)
   342  	}
   343  
   344  	// Recenter coefficients:
   345  	for i := 0; i < 63; i++ {
   346  		carry := (digits[i] + 8) >> 4
   347  		digits[i] -= carry << 4
   348  		digits[i+1] += carry
   349  	}
   350  
   351  	return digits
   352  }
   353
View as plain text