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

View as plain text