scalar.go

Documentation: crypto/ed25519/internal/edwards25519

     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/subtle"
     9  	"encoding/binary"
    10  	"errors"
    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 value in little-endian. The value is always reduced
    25  	// between operations.
    26  	s [32]byte
    27  }
    28  
    29  var (
    30  	scZero = Scalar{[32]byte{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}}
    31  
    32  	scOne = Scalar{[32]byte{1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}}
    33  
    34  	scMinusOne = Scalar{[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}}
    35  )
    36  
    37  // NewScalar returns a new zero Scalar.
    38  func NewScalar() *Scalar {
    39  	return &Scalar{}
    40  }
    41  
    42  // MultiplyAdd sets s = x * y + z mod l, and returns s.
    43  func (s *Scalar) MultiplyAdd(x, y, z *Scalar) *Scalar {
    44  	scMulAdd(&s.s, &x.s, &y.s, &z.s)
    45  	return s
    46  }
    47  
    48  // Add sets s = x + y mod l, and returns s.
    49  func (s *Scalar) Add(x, y *Scalar) *Scalar {
    50  	// s = 1 * x + y mod l
    51  	scMulAdd(&s.s, &scOne.s, &x.s, &y.s)
    52  	return s
    53  }
    54  
    55  // Subtract sets s = x - y mod l, and returns s.
    56  func (s *Scalar) Subtract(x, y *Scalar) *Scalar {
    57  	// s = -1 * y + x mod l
    58  	scMulAdd(&s.s, &scMinusOne.s, &y.s, &x.s)
    59  	return s
    60  }
    61  
    62  // Negate sets s = -x mod l, and returns s.
    63  func (s *Scalar) Negate(x *Scalar) *Scalar {
    64  	// s = -1 * x + 0 mod l
    65  	scMulAdd(&s.s, &scMinusOne.s, &x.s, &scZero.s)
    66  	return s
    67  }
    68  
    69  // Multiply sets s = x * y mod l, and returns s.
    70  func (s *Scalar) Multiply(x, y *Scalar) *Scalar {
    71  	// s = x * y + 0 mod l
    72  	scMulAdd(&s.s, &x.s, &y.s, &scZero.s)
    73  	return s
    74  }
    75  
    76  // Set sets s = x, and returns s.
    77  func (s *Scalar) Set(x *Scalar) *Scalar {
    78  	*s = *x
    79  	return s
    80  }
    81  
    82  // SetUniformBytes sets s to an uniformly distributed value given 64 uniformly
    83  // distributed random bytes.
    84  func (s *Scalar) SetUniformBytes(x []byte) *Scalar {
    85  	if len(x) != 64 {
    86  		panic("edwards25519: invalid SetUniformBytes input length")
    87  	}
    88  	var wideBytes [64]byte
    89  	copy(wideBytes[:], x[:])
    90  	scReduce(&s.s, &wideBytes)
    91  	return s
    92  }
    93  
    94  // SetCanonicalBytes sets s = x, where x is a 32-byte little-endian encoding of
    95  // s, and returns s. If x is not a canonical encoding of s, SetCanonicalBytes
    96  // returns nil and an error, and the receiver is unchanged.
    97  func (s *Scalar) SetCanonicalBytes(x []byte) (*Scalar, error) {
    98  	if len(x) != 32 {
    99  		return nil, errors.New("invalid scalar length")
   100  	}
   101  	ss := &Scalar{}
   102  	copy(ss.s[:], x)
   103  	if !isReduced(ss) {
   104  		return nil, errors.New("invalid scalar encoding")
   105  	}
   106  	s.s = ss.s
   107  	return s, nil
   108  }
   109  
   110  // isReduced returns whether the given scalar is reduced modulo l.
   111  func isReduced(s *Scalar) bool {
   112  	for i := len(s.s) - 1; i >= 0; i-- {
   113  		switch {
   114  		case s.s[i] > scMinusOne.s[i]:
   115  			return false
   116  		case s.s[i] < scMinusOne.s[i]:
   117  			return true
   118  		}
   119  	}
   120  	return true
   121  }
   122  
   123  // SetBytesWithClamping applies the buffer pruning described in RFC 8032,
   124  // Section 5.1.5 (also known as clamping) and sets s to the result. The input
   125  // must be 32 bytes, and it is not modified.
   126  //
   127  // Note that since Scalar values are always reduced modulo the prime order of
   128  // the curve, the resulting value will not preserve any of the cofactor-clearing
   129  // properties that clamping is meant to provide. It will however work as
   130  // expected as long as it is applied to points on the prime order subgroup, like
   131  // in Ed25519. In fact, it is lost to history why RFC 8032 adopted the
   132  // irrelevant RFC 7748 clamping, but it is now required for compatibility.
   133  func (s *Scalar) SetBytesWithClamping(x []byte) *Scalar {
   134  	// The description above omits the purpose of the high bits of the clamping
   135  	// for brevity, but those are also lost to reductions, and are also
   136  	// irrelevant to edwards25519 as they protect against a specific
   137  	// implementation bug that was once observed in a generic Montgomery ladder.
   138  	if len(x) != 32 {
   139  		panic("edwards25519: invalid SetBytesWithClamping input length")
   140  	}
   141  	var wideBytes [64]byte
   142  	copy(wideBytes[:], x[:])
   143  	wideBytes[0] &= 248
   144  	wideBytes[31] &= 63
   145  	wideBytes[31] |= 64
   146  	scReduce(&s.s, &wideBytes)
   147  	return s
   148  }
   149  
   150  // Bytes returns the canonical 32-byte little-endian encoding of s.
   151  func (s *Scalar) Bytes() []byte {
   152  	buf := make([]byte, 32)
   153  	copy(buf, s.s[:])
   154  	return buf
   155  }
   156  
   157  // Equal returns 1 if s and t are equal, and 0 otherwise.
   158  func (s *Scalar) Equal(t *Scalar) int {
   159  	return subtle.ConstantTimeCompare(s.s[:], t.s[:])
   160  }
   161  
   162  // scMulAdd and scReduce are ported from the public domain, “ref10”
   163  // implementation of ed25519 from SUPERCOP.
   164  
   165  func load3(in []byte) int64 {
   166  	r := int64(in[0])
   167  	r |= int64(in[1]) << 8
   168  	r |= int64(in[2]) << 16
   169  	return r
   170  }
   171  
   172  func load4(in []byte) int64 {
   173  	r := int64(in[0])
   174  	r |= int64(in[1]) << 8
   175  	r |= int64(in[2]) << 16
   176  	r |= int64(in[3]) << 24
   177  	return r
   178  }
   179  
   180  // Input:
   181  //   a[0]+256*a[1]+...+256^31*a[31] = a
   182  //   b[0]+256*b[1]+...+256^31*b[31] = b
   183  //   c[0]+256*c[1]+...+256^31*c[31] = c
   184  //
   185  // Output:
   186  //   s[0]+256*s[1]+...+256^31*s[31] = (ab+c) mod l
   187  //   where l = 2^252 + 27742317777372353535851937790883648493.
   188  func scMulAdd(s, a, b, c *[32]byte) {
   189  	a0 := 2097151 & load3(a[:])
   190  	a1 := 2097151 & (load4(a[2:]) >> 5)
   191  	a2 := 2097151 & (load3(a[5:]) >> 2)
   192  	a3 := 2097151 & (load4(a[7:]) >> 7)
   193  	a4 := 2097151 & (load4(a[10:]) >> 4)
   194  	a5 := 2097151 & (load3(a[13:]) >> 1)
   195  	a6 := 2097151 & (load4(a[15:]) >> 6)
   196  	a7 := 2097151 & (load3(a[18:]) >> 3)
   197  	a8 := 2097151 & load3(a[21:])
   198  	a9 := 2097151 & (load4(a[23:]) >> 5)
   199  	a10 := 2097151 & (load3(a[26:]) >> 2)
   200  	a11 := (load4(a[28:]) >> 7)
   201  	b0 := 2097151 & load3(b[:])
   202  	b1 := 2097151 & (load4(b[2:]) >> 5)
   203  	b2 := 2097151 & (load3(b[5:]) >> 2)
   204  	b3 := 2097151 & (load4(b[7:]) >> 7)
   205  	b4 := 2097151 & (load4(b[10:]) >> 4)
   206  	b5 := 2097151 & (load3(b[13:]) >> 1)
   207  	b6 := 2097151 & (load4(b[15:]) >> 6)
   208  	b7 := 2097151 & (load3(b[18:]) >> 3)
   209  	b8 := 2097151 & load3(b[21:])
   210  	b9 := 2097151 & (load4(b[23:]) >> 5)
   211  	b10 := 2097151 & (load3(b[26:]) >> 2)
   212  	b11 := (load4(b[28:]) >> 7)
   213  	c0 := 2097151 & load3(c[:])
   214  	c1 := 2097151 & (load4(c[2:]) >> 5)
   215  	c2 := 2097151 & (load3(c[5:]) >> 2)
   216  	c3 := 2097151 & (load4(c[7:]) >> 7)
   217  	c4 := 2097151 & (load4(c[10:]) >> 4)
   218  	c5 := 2097151 & (load3(c[13:]) >> 1)
   219  	c6 := 2097151 & (load4(c[15:]) >> 6)
   220  	c7 := 2097151 & (load3(c[18:]) >> 3)
   221  	c8 := 2097151 & load3(c[21:])
   222  	c9 := 2097151 & (load4(c[23:]) >> 5)
   223  	c10 := 2097151 & (load3(c[26:]) >> 2)
   224  	c11 := (load4(c[28:]) >> 7)
   225  	var carry [23]int64
   226  
   227  	s0 := c0 + a0*b0
   228  	s1 := c1 + a0*b1 + a1*b0
   229  	s2 := c2 + a0*b2 + a1*b1 + a2*b0
   230  	s3 := c3 + a0*b3 + a1*b2 + a2*b1 + a3*b0
   231  	s4 := c4 + a0*b4 + a1*b3 + a2*b2 + a3*b1 + a4*b0
   232  	s5 := c5 + a0*b5 + a1*b4 + a2*b3 + a3*b2 + a4*b1 + a5*b0
   233  	s6 := c6 + a0*b6 + a1*b5 + a2*b4 + a3*b3 + a4*b2 + a5*b1 + a6*b0
   234  	s7 := c7 + a0*b7 + a1*b6 + a2*b5 + a3*b4 + a4*b3 + a5*b2 + a6*b1 + a7*b0
   235  	s8 := c8 + a0*b8 + a1*b7 + a2*b6 + a3*b5 + a4*b4 + a5*b3 + a6*b2 + a7*b1 + a8*b0
   236  	s9 := c9 + a0*b9 + a1*b8 + a2*b7 + a3*b6 + a4*b5 + a5*b4 + a6*b3 + a7*b2 + a8*b1 + a9*b0
   237  	s10 := c10 + a0*b10 + a1*b9 + a2*b8 + a3*b7 + a4*b6 + a5*b5 + a6*b4 + a7*b3 + a8*b2 + a9*b1 + a10*b0
   238  	s11 := c11 + a0*b11 + a1*b10 + a2*b9 + a3*b8 + a4*b7 + a5*b6 + a6*b5 + a7*b4 + a8*b3 + a9*b2 + a10*b1 + a11*b0
   239  	s12 := a1*b11 + a2*b10 + a3*b9 + a4*b8 + a5*b7 + a6*b6 + a7*b5 + a8*b4 + a9*b3 + a10*b2 + a11*b1
   240  	s13 := a2*b11 + a3*b10 + a4*b9 + a5*b8 + a6*b7 + a7*b6 + a8*b5 + a9*b4 + a10*b3 + a11*b2
   241  	s14 := a3*b11 + a4*b10 + a5*b9 + a6*b8 + a7*b7 + a8*b6 + a9*b5 + a10*b4 + a11*b3
   242  	s15 := a4*b11 + a5*b10 + a6*b9 + a7*b8 + a8*b7 + a9*b6 + a10*b5 + a11*b4
   243  	s16 := a5*b11 + a6*b10 + a7*b9 + a8*b8 + a9*b7 + a10*b6 + a11*b5
   244  	s17 := a6*b11 + a7*b10 + a8*b9 + a9*b8 + a10*b7 + a11*b6
   245  	s18 := a7*b11 + a8*b10 + a9*b9 + a10*b8 + a11*b7
   246  	s19 := a8*b11 + a9*b10 + a10*b9 + a11*b8
   247  	s20 := a9*b11 + a10*b10 + a11*b9
   248  	s21 := a10*b11 + a11*b10
   249  	s22 := a11 * b11
   250  	s23 := int64(0)
   251  
   252  	carry[0] = (s0 + (1 << 20)) >> 21
   253  	s1 += carry[0]
   254  	s0 -= carry[0] << 21
   255  	carry[2] = (s2 + (1 << 20)) >> 21
   256  	s3 += carry[2]
   257  	s2 -= carry[2] << 21
   258  	carry[4] = (s4 + (1 << 20)) >> 21
   259  	s5 += carry[4]
   260  	s4 -= carry[4] << 21
   261  	carry[6] = (s6 + (1 << 20)) >> 21
   262  	s7 += carry[6]
   263  	s6 -= carry[6] << 21
   264  	carry[8] = (s8 + (1 << 20)) >> 21
   265  	s9 += carry[8]
   266  	s8 -= carry[8] << 21
   267  	carry[10] = (s10 + (1 << 20)) >> 21
   268  	s11 += carry[10]
   269  	s10 -= carry[10] << 21
   270  	carry[12] = (s12 + (1 << 20)) >> 21
   271  	s13 += carry[12]
   272  	s12 -= carry[12] << 21
   273  	carry[14] = (s14 + (1 << 20)) >> 21
   274  	s15 += carry[14]
   275  	s14 -= carry[14] << 21
   276  	carry[16] = (s16 + (1 << 20)) >> 21
   277  	s17 += carry[16]
   278  	s16 -= carry[16] << 21
   279  	carry[18] = (s18 + (1 << 20)) >> 21
   280  	s19 += carry[18]
   281  	s18 -= carry[18] << 21
   282  	carry[20] = (s20 + (1 << 20)) >> 21
   283  	s21 += carry[20]
   284  	s20 -= carry[20] << 21
   285  	carry[22] = (s22 + (1 << 20)) >> 21
   286  	s23 += carry[22]
   287  	s22 -= carry[22] << 21
   288  
   289  	carry[1] = (s1 + (1 << 20)) >> 21
   290  	s2 += carry[1]
   291  	s1 -= carry[1] << 21
   292  	carry[3] = (s3 + (1 << 20)) >> 21
   293  	s4 += carry[3]
   294  	s3 -= carry[3] << 21
   295  	carry[5] = (s5 + (1 << 20)) >> 21
   296  	s6 += carry[5]
   297  	s5 -= carry[5] << 21
   298  	carry[7] = (s7 + (1 << 20)) >> 21
   299  	s8 += carry[7]
   300  	s7 -= carry[7] << 21
   301  	carry[9] = (s9 + (1 << 20)) >> 21
   302  	s10 += carry[9]
   303  	s9 -= carry[9] << 21
   304  	carry[11] = (s11 + (1 << 20)) >> 21
   305  	s12 += carry[11]
   306  	s11 -= carry[11] << 21
   307  	carry[13] = (s13 + (1 << 20)) >> 21
   308  	s14 += carry[13]
   309  	s13 -= carry[13] << 21
   310  	carry[15] = (s15 + (1 << 20)) >> 21
   311  	s16 += carry[15]
   312  	s15 -= carry[15] << 21
   313  	carry[17] = (s17 + (1 << 20)) >> 21
   314  	s18 += carry[17]
   315  	s17 -= carry[17] << 21
   316  	carry[19] = (s19 + (1 << 20)) >> 21
   317  	s20 += carry[19]
   318  	s19 -= carry[19] << 21
   319  	carry[21] = (s21 + (1 << 20)) >> 21
   320  	s22 += carry[21]
   321  	s21 -= carry[21] << 21
   322  
   323  	s11 += s23 * 666643
   324  	s12 += s23 * 470296
   325  	s13 += s23 * 654183
   326  	s14 -= s23 * 997805
   327  	s15 += s23 * 136657
   328  	s16 -= s23 * 683901
   329  	s23 = 0
   330  
   331  	s10 += s22 * 666643
   332  	s11 += s22 * 470296
   333  	s12 += s22 * 654183
   334  	s13 -= s22 * 997805
   335  	s14 += s22 * 136657
   336  	s15 -= s22 * 683901
   337  	s22 = 0
   338  
   339  	s9 += s21 * 666643
   340  	s10 += s21 * 470296
   341  	s11 += s21 * 654183
   342  	s12 -= s21 * 997805
   343  	s13 += s21 * 136657
   344  	s14 -= s21 * 683901
   345  	s21 = 0
   346  
   347  	s8 += s20 * 666643
   348  	s9 += s20 * 470296
   349  	s10 += s20 * 654183
   350  	s11 -= s20 * 997805
   351  	s12 += s20 * 136657
   352  	s13 -= s20 * 683901
   353  	s20 = 0
   354  
   355  	s7 += s19 * 666643
   356  	s8 += s19 * 470296
   357  	s9 += s19 * 654183
   358  	s10 -= s19 * 997805
   359  	s11 += s19 * 136657
   360  	s12 -= s19 * 683901
   361  	s19 = 0
   362  
   363  	s6 += s18 * 666643
   364  	s7 += s18 * 470296
   365  	s8 += s18 * 654183
   366  	s9 -= s18 * 997805
   367  	s10 += s18 * 136657
   368  	s11 -= s18 * 683901
   369  	s18 = 0
   370  
   371  	carry[6] = (s6 + (1 << 20)) >> 21
   372  	s7 += carry[6]
   373  	s6 -= carry[6] << 21
   374  	carry[8] = (s8 + (1 << 20)) >> 21
   375  	s9 += carry[8]
   376  	s8 -= carry[8] << 21
   377  	carry[10] = (s10 + (1 << 20)) >> 21
   378  	s11 += carry[10]
   379  	s10 -= carry[10] << 21
   380  	carry[12] = (s12 + (1 << 20)) >> 21
   381  	s13 += carry[12]
   382  	s12 -= carry[12] << 21
   383  	carry[14] = (s14 + (1 << 20)) >> 21
   384  	s15 += carry[14]
   385  	s14 -= carry[14] << 21
   386  	carry[16] = (s16 + (1 << 20)) >> 21
   387  	s17 += carry[16]
   388  	s16 -= carry[16] << 21
   389  
   390  	carry[7] = (s7 + (1 << 20)) >> 21
   391  	s8 += carry[7]
   392  	s7 -= carry[7] << 21
   393  	carry[9] = (s9 + (1 << 20)) >> 21
   394  	s10 += carry[9]
   395  	s9 -= carry[9] << 21
   396  	carry[11] = (s11 + (1 << 20)) >> 21
   397  	s12 += carry[11]
   398  	s11 -= carry[11] << 21
   399  	carry[13] = (s13 + (1 << 20)) >> 21
   400  	s14 += carry[13]
   401  	s13 -= carry[13] << 21
   402  	carry[15] = (s15 + (1 << 20)) >> 21
   403  	s16 += carry[15]
   404  	s15 -= carry[15] << 21
   405  
   406  	s5 += s17 * 666643
   407  	s6 += s17 * 470296
   408  	s7 += s17 * 654183
   409  	s8 -= s17 * 997805
   410  	s9 += s17 * 136657
   411  	s10 -= s17 * 683901
   412  	s17 = 0
   413  
   414  	s4 += s16 * 666643
   415  	s5 += s16 * 470296
   416  	s6 += s16 * 654183
   417  	s7 -= s16 * 997805
   418  	s8 += s16 * 136657
   419  	s9 -= s16 * 683901
   420  	s16 = 0
   421  
   422  	s3 += s15 * 666643
   423  	s4 += s15 * 470296
   424  	s5 += s15 * 654183
   425  	s6 -= s15 * 997805
   426  	s7 += s15 * 136657
   427  	s8 -= s15 * 683901
   428  	s15 = 0
   429  
   430  	s2 += s14 * 666643
   431  	s3 += s14 * 470296
   432  	s4 += s14 * 654183
   433  	s5 -= s14 * 997805
   434  	s6 += s14 * 136657
   435  	s7 -= s14 * 683901
   436  	s14 = 0
   437  
   438  	s1 += s13 * 666643
   439  	s2 += s13 * 470296
   440  	s3 += s13 * 654183
   441  	s4 -= s13 * 997805
   442  	s5 += s13 * 136657
   443  	s6 -= s13 * 683901
   444  	s13 = 0
   445  
   446  	s0 += s12 * 666643
   447  	s1 += s12 * 470296
   448  	s2 += s12 * 654183
   449  	s3 -= s12 * 997805
   450  	s4 += s12 * 136657
   451  	s5 -= s12 * 683901
   452  	s12 = 0
   453  
   454  	carry[0] = (s0 + (1 << 20)) >> 21
   455  	s1 += carry[0]
   456  	s0 -= carry[0] << 21
   457  	carry[2] = (s2 + (1 << 20)) >> 21
   458  	s3 += carry[2]
   459  	s2 -= carry[2] << 21
   460  	carry[4] = (s4 + (1 << 20)) >> 21
   461  	s5 += carry[4]
   462  	s4 -= carry[4] << 21
   463  	carry[6] = (s6 + (1 << 20)) >> 21
   464  	s7 += carry[6]
   465  	s6 -= carry[6] << 21
   466  	carry[8] = (s8 + (1 << 20)) >> 21
   467  	s9 += carry[8]
   468  	s8 -= carry[8] << 21
   469  	carry[10] = (s10 + (1 << 20)) >> 21
   470  	s11 += carry[10]
   471  	s10 -= carry[10] << 21
   472  
   473  	carry[1] = (s1 + (1 << 20)) >> 21
   474  	s2 += carry[1]
   475  	s1 -= carry[1] << 21
   476  	carry[3] = (s3 + (1 << 20)) >> 21
   477  	s4 += carry[3]
   478  	s3 -= carry[3] << 21
   479  	carry[5] = (s5 + (1 << 20)) >> 21
   480  	s6 += carry[5]
   481  	s5 -= carry[5] << 21
   482  	carry[7] = (s7 + (1 << 20)) >> 21
   483  	s8 += carry[7]
   484  	s7 -= carry[7] << 21
   485  	carry[9] = (s9 + (1 << 20)) >> 21
   486  	s10 += carry[9]
   487  	s9 -= carry[9] << 21
   488  	carry[11] = (s11 + (1 << 20)) >> 21
   489  	s12 += carry[11]
   490  	s11 -= carry[11] << 21
   491  
   492  	s0 += s12 * 666643
   493  	s1 += s12 * 470296
   494  	s2 += s12 * 654183
   495  	s3 -= s12 * 997805
   496  	s4 += s12 * 136657
   497  	s5 -= s12 * 683901
   498  	s12 = 0
   499  
   500  	carry[0] = s0 >> 21
   501  	s1 += carry[0]
   502  	s0 -= carry[0] << 21
   503  	carry[1] = s1 >> 21
   504  	s2 += carry[1]
   505  	s1 -= carry[1] << 21
   506  	carry[2] = s2 >> 21
   507  	s3 += carry[2]
   508  	s2 -= carry[2] << 21
   509  	carry[3] = s3 >> 21
   510  	s4 += carry[3]
   511  	s3 -= carry[3] << 21
   512  	carry[4] = s4 >> 21
   513  	s5 += carry[4]
   514  	s4 -= carry[4] << 21
   515  	carry[5] = s5 >> 21
   516  	s6 += carry[5]
   517  	s5 -= carry[5] << 21
   518  	carry[6] = s6 >> 21
   519  	s7 += carry[6]
   520  	s6 -= carry[6] << 21
   521  	carry[7] = s7 >> 21
   522  	s8 += carry[7]
   523  	s7 -= carry[7] << 21
   524  	carry[8] = s8 >> 21
   525  	s9 += carry[8]
   526  	s8 -= carry[8] << 21
   527  	carry[9] = s9 >> 21
   528  	s10 += carry[9]
   529  	s9 -= carry[9] << 21
   530  	carry[10] = s10 >> 21
   531  	s11 += carry[10]
   532  	s10 -= carry[10] << 21
   533  	carry[11] = s11 >> 21
   534  	s12 += carry[11]
   535  	s11 -= carry[11] << 21
   536  
   537  	s0 += s12 * 666643
   538  	s1 += s12 * 470296
   539  	s2 += s12 * 654183
   540  	s3 -= s12 * 997805
   541  	s4 += s12 * 136657
   542  	s5 -= s12 * 683901
   543  	s12 = 0
   544  
   545  	carry[0] = s0 >> 21
   546  	s1 += carry[0]
   547  	s0 -= carry[0] << 21
   548  	carry[1] = s1 >> 21
   549  	s2 += carry[1]
   550  	s1 -= carry[1] << 21
   551  	carry[2] = s2 >> 21
   552  	s3 += carry[2]
   553  	s2 -= carry[2] << 21
   554  	carry[3] = s3 >> 21
   555  	s4 += carry[3]
   556  	s3 -= carry[3] << 21
   557  	carry[4] = s4 >> 21
   558  	s5 += carry[4]
   559  	s4 -= carry[4] << 21
   560  	carry[5] = s5 >> 21
   561  	s6 += carry[5]
   562  	s5 -= carry[5] << 21
   563  	carry[6] = s6 >> 21
   564  	s7 += carry[6]
   565  	s6 -= carry[6] << 21
   566  	carry[7] = s7 >> 21
   567  	s8 += carry[7]
   568  	s7 -= carry[7] << 21
   569  	carry[8] = s8 >> 21
   570  	s9 += carry[8]
   571  	s8 -= carry[8] << 21
   572  	carry[9] = s9 >> 21
   573  	s10 += carry[9]
   574  	s9 -= carry[9] << 21
   575  	carry[10] = s10 >> 21
   576  	s11 += carry[10]
   577  	s10 -= carry[10] << 21
   578  
   579  	s[0] = byte(s0 >> 0)
   580  	s[1] = byte(s0 >> 8)
   581  	s[2] = byte((s0 >> 16) | (s1 << 5))
   582  	s[3] = byte(s1 >> 3)
   583  	s[4] = byte(s1 >> 11)
   584  	s[5] = byte((s1 >> 19) | (s2 << 2))
   585  	s[6] = byte(s2 >> 6)
   586  	s[7] = byte((s2 >> 14) | (s3 << 7))
   587  	s[8] = byte(s3 >> 1)
   588  	s[9] = byte(s3 >> 9)
   589  	s[10] = byte((s3 >> 17) | (s4 << 4))
   590  	s[11] = byte(s4 >> 4)
   591  	s[12] = byte(s4 >> 12)
   592  	s[13] = byte((s4 >> 20) | (s5 << 1))
   593  	s[14] = byte(s5 >> 7)
   594  	s[15] = byte((s5 >> 15) | (s6 << 6))
   595  	s[16] = byte(s6 >> 2)
   596  	s[17] = byte(s6 >> 10)
   597  	s[18] = byte((s6 >> 18) | (s7 << 3))
   598  	s[19] = byte(s7 >> 5)
   599  	s[20] = byte(s7 >> 13)
   600  	s[21] = byte(s8 >> 0)
   601  	s[22] = byte(s8 >> 8)
   602  	s[23] = byte((s8 >> 16) | (s9 << 5))
   603  	s[24] = byte(s9 >> 3)
   604  	s[25] = byte(s9 >> 11)
   605  	s[26] = byte((s9 >> 19) | (s10 << 2))
   606  	s[27] = byte(s10 >> 6)
   607  	s[28] = byte((s10 >> 14) | (s11 << 7))
   608  	s[29] = byte(s11 >> 1)
   609  	s[30] = byte(s11 >> 9)
   610  	s[31] = byte(s11 >> 17)
   611  }
   612  
   613  // Input:
   614  //   s[0]+256*s[1]+...+256^63*s[63] = s
   615  //
   616  // Output:
   617  //   s[0]+256*s[1]+...+256^31*s[31] = s mod l
   618  //   where l = 2^252 + 27742317777372353535851937790883648493.
   619  func scReduce(out *[32]byte, s *[64]byte) {
   620  	s0 := 2097151 & load3(s[:])
   621  	s1 := 2097151 & (load4(s[2:]) >> 5)
   622  	s2 := 2097151 & (load3(s[5:]) >> 2)
   623  	s3 := 2097151 & (load4(s[7:]) >> 7)
   624  	s4 := 2097151 & (load4(s[10:]) >> 4)
   625  	s5 := 2097151 & (load3(s[13:]) >> 1)
   626  	s6 := 2097151 & (load4(s[15:]) >> 6)
   627  	s7 := 2097151 & (load3(s[18:]) >> 3)
   628  	s8 := 2097151 & load3(s[21:])
   629  	s9 := 2097151 & (load4(s[23:]) >> 5)
   630  	s10 := 2097151 & (load3(s[26:]) >> 2)
   631  	s11 := 2097151 & (load4(s[28:]) >> 7)
   632  	s12 := 2097151 & (load4(s[31:]) >> 4)
   633  	s13 := 2097151 & (load3(s[34:]) >> 1)
   634  	s14 := 2097151 & (load4(s[36:]) >> 6)
   635  	s15 := 2097151 & (load3(s[39:]) >> 3)
   636  	s16 := 2097151 & load3(s[42:])
   637  	s17 := 2097151 & (load4(s[44:]) >> 5)
   638  	s18 := 2097151 & (load3(s[47:]) >> 2)
   639  	s19 := 2097151 & (load4(s[49:]) >> 7)
   640  	s20 := 2097151 & (load4(s[52:]) >> 4)
   641  	s21 := 2097151 & (load3(s[55:]) >> 1)
   642  	s22 := 2097151 & (load4(s[57:]) >> 6)
   643  	s23 := (load4(s[60:]) >> 3)
   644  
   645  	s11 += s23 * 666643
   646  	s12 += s23 * 470296
   647  	s13 += s23 * 654183
   648  	s14 -= s23 * 997805
   649  	s15 += s23 * 136657
   650  	s16 -= s23 * 683901
   651  	s23 = 0
   652  
   653  	s10 += s22 * 666643
   654  	s11 += s22 * 470296
   655  	s12 += s22 * 654183
   656  	s13 -= s22 * 997805
   657  	s14 += s22 * 136657
   658  	s15 -= s22 * 683901
   659  	s22 = 0
   660  
   661  	s9 += s21 * 666643
   662  	s10 += s21 * 470296
   663  	s11 += s21 * 654183
   664  	s12 -= s21 * 997805
   665  	s13 += s21 * 136657
   666  	s14 -= s21 * 683901
   667  	s21 = 0
   668  
   669  	s8 += s20 * 666643
   670  	s9 += s20 * 470296
   671  	s10 += s20 * 654183
   672  	s11 -= s20 * 997805
   673  	s12 += s20 * 136657
   674  	s13 -= s20 * 683901
   675  	s20 = 0
   676  
   677  	s7 += s19 * 666643
   678  	s8 += s19 * 470296
   679  	s9 += s19 * 654183
   680  	s10 -= s19 * 997805
   681  	s11 += s19 * 136657
   682  	s12 -= s19 * 683901
   683  	s19 = 0
   684  
   685  	s6 += s18 * 666643
   686  	s7 += s18 * 470296
   687  	s8 += s18 * 654183
   688  	s9 -= s18 * 997805
   689  	s10 += s18 * 136657
   690  	s11 -= s18 * 683901
   691  	s18 = 0
   692  
   693  	var carry [17]int64
   694  
   695  	carry[6] = (s6 + (1 << 20)) >> 21
   696  	s7 += carry[6]
   697  	s6 -= carry[6] << 21
   698  	carry[8] = (s8 + (1 << 20)) >> 21
   699  	s9 += carry[8]
   700  	s8 -= carry[8] << 21
   701  	carry[10] = (s10 + (1 << 20)) >> 21
   702  	s11 += carry[10]
   703  	s10 -= carry[10] << 21
   704  	carry[12] = (s12 + (1 << 20)) >> 21
   705  	s13 += carry[12]
   706  	s12 -= carry[12] << 21
   707  	carry[14] = (s14 + (1 << 20)) >> 21
   708  	s15 += carry[14]
   709  	s14 -= carry[14] << 21
   710  	carry[16] = (s16 + (1 << 20)) >> 21
   711  	s17 += carry[16]
   712  	s16 -= carry[16] << 21
   713  
   714  	carry[7] = (s7 + (1 << 20)) >> 21
   715  	s8 += carry[7]
   716  	s7 -= carry[7] << 21
   717  	carry[9] = (s9 + (1 << 20)) >> 21
   718  	s10 += carry[9]
   719  	s9 -= carry[9] << 21
   720  	carry[11] = (s11 + (1 << 20)) >> 21
   721  	s12 += carry[11]
   722  	s11 -= carry[11] << 21
   723  	carry[13] = (s13 + (1 << 20)) >> 21
   724  	s14 += carry[13]
   725  	s13 -= carry[13] << 21
   726  	carry[15] = (s15 + (1 << 20)) >> 21
   727  	s16 += carry[15]
   728  	s15 -= carry[15] << 21
   729  
   730  	s5 += s17 * 666643
   731  	s6 += s17 * 470296
   732  	s7 += s17 * 654183
   733  	s8 -= s17 * 997805
   734  	s9 += s17 * 136657
   735  	s10 -= s17 * 683901
   736  	s17 = 0
   737  
   738  	s4 += s16 * 666643
   739  	s5 += s16 * 470296
   740  	s6 += s16 * 654183
   741  	s7 -= s16 * 997805
   742  	s8 += s16 * 136657
   743  	s9 -= s16 * 683901
   744  	s16 = 0
   745  
   746  	s3 += s15 * 666643
   747  	s4 += s15 * 470296
   748  	s5 += s15 * 654183
   749  	s6 -= s15 * 997805
   750  	s7 += s15 * 136657
   751  	s8 -= s15 * 683901
   752  	s15 = 0
   753  
   754  	s2 += s14 * 666643
   755  	s3 += s14 * 470296
   756  	s4 += s14 * 654183
   757  	s5 -= s14 * 997805
   758  	s6 += s14 * 136657
   759  	s7 -= s14 * 683901
   760  	s14 = 0
   761  
   762  	s1 += s13 * 666643
   763  	s2 += s13 * 470296
   764  	s3 += s13 * 654183
   765  	s4 -= s13 * 997805
   766  	s5 += s13 * 136657
   767  	s6 -= s13 * 683901
   768  	s13 = 0
   769  
   770  	s0 += s12 * 666643
   771  	s1 += s12 * 470296
   772  	s2 += s12 * 654183
   773  	s3 -= s12 * 997805
   774  	s4 += s12 * 136657
   775  	s5 -= s12 * 683901
   776  	s12 = 0
   777  
   778  	carry[0] = (s0 + (1 << 20)) >> 21
   779  	s1 += carry[0]
   780  	s0 -= carry[0] << 21
   781  	carry[2] = (s2 + (1 << 20)) >> 21
   782  	s3 += carry[2]
   783  	s2 -= carry[2] << 21
   784  	carry[4] = (s4 + (1 << 20)) >> 21
   785  	s5 += carry[4]
   786  	s4 -= carry[4] << 21
   787  	carry[6] = (s6 + (1 << 20)) >> 21
   788  	s7 += carry[6]
   789  	s6 -= carry[6] << 21
   790  	carry[8] = (s8 + (1 << 20)) >> 21
   791  	s9 += carry[8]
   792  	s8 -= carry[8] << 21
   793  	carry[10] = (s10 + (1 << 20)) >> 21
   794  	s11 += carry[10]
   795  	s10 -= carry[10] << 21
   796  
   797  	carry[1] = (s1 + (1 << 20)) >> 21
   798  	s2 += carry[1]
   799  	s1 -= carry[1] << 21
   800  	carry[3] = (s3 + (1 << 20)) >> 21
   801  	s4 += carry[3]
   802  	s3 -= carry[3] << 21
   803  	carry[5] = (s5 + (1 << 20)) >> 21
   804  	s6 += carry[5]
   805  	s5 -= carry[5] << 21
   806  	carry[7] = (s7 + (1 << 20)) >> 21
   807  	s8 += carry[7]
   808  	s7 -= carry[7] << 21
   809  	carry[9] = (s9 + (1 << 20)) >> 21
   810  	s10 += carry[9]
   811  	s9 -= carry[9] << 21
   812  	carry[11] = (s11 + (1 << 20)) >> 21
   813  	s12 += carry[11]
   814  	s11 -= carry[11] << 21
   815  
   816  	s0 += s12 * 666643
   817  	s1 += s12 * 470296
   818  	s2 += s12 * 654183
   819  	s3 -= s12 * 997805
   820  	s4 += s12 * 136657
   821  	s5 -= s12 * 683901
   822  	s12 = 0
   823  
   824  	carry[0] = s0 >> 21
   825  	s1 += carry[0]
   826  	s0 -= carry[0] << 21
   827  	carry[1] = s1 >> 21
   828  	s2 += carry[1]
   829  	s1 -= carry[1] << 21
   830  	carry[2] = s2 >> 21
   831  	s3 += carry[2]
   832  	s2 -= carry[2] << 21
   833  	carry[3] = s3 >> 21
   834  	s4 += carry[3]
   835  	s3 -= carry[3] << 21
   836  	carry[4] = s4 >> 21
   837  	s5 += carry[4]
   838  	s4 -= carry[4] << 21
   839  	carry[5] = s5 >> 21
   840  	s6 += carry[5]
   841  	s5 -= carry[5] << 21
   842  	carry[6] = s6 >> 21
   843  	s7 += carry[6]
   844  	s6 -= carry[6] << 21
   845  	carry[7] = s7 >> 21
   846  	s8 += carry[7]
   847  	s7 -= carry[7] << 21
   848  	carry[8] = s8 >> 21
   849  	s9 += carry[8]
   850  	s8 -= carry[8] << 21
   851  	carry[9] = s9 >> 21
   852  	s10 += carry[9]
   853  	s9 -= carry[9] << 21
   854  	carry[10] = s10 >> 21
   855  	s11 += carry[10]
   856  	s10 -= carry[10] << 21
   857  	carry[11] = s11 >> 21
   858  	s12 += carry[11]
   859  	s11 -= carry[11] << 21
   860  
   861  	s0 += s12 * 666643
   862  	s1 += s12 * 470296
   863  	s2 += s12 * 654183
   864  	s3 -= s12 * 997805
   865  	s4 += s12 * 136657
   866  	s5 -= s12 * 683901
   867  	s12 = 0
   868  
   869  	carry[0] = s0 >> 21
   870  	s1 += carry[0]
   871  	s0 -= carry[0] << 21
   872  	carry[1] = s1 >> 21
   873  	s2 += carry[1]
   874  	s1 -= carry[1] << 21
   875  	carry[2] = s2 >> 21
   876  	s3 += carry[2]
   877  	s2 -= carry[2] << 21
   878  	carry[3] = s3 >> 21
   879  	s4 += carry[3]
   880  	s3 -= carry[3] << 21
   881  	carry[4] = s4 >> 21
   882  	s5 += carry[4]
   883  	s4 -= carry[4] << 21
   884  	carry[5] = s5 >> 21
   885  	s6 += carry[5]
   886  	s5 -= carry[5] << 21
   887  	carry[6] = s6 >> 21
   888  	s7 += carry[6]
   889  	s6 -= carry[6] << 21
   890  	carry[7] = s7 >> 21
   891  	s8 += carry[7]
   892  	s7 -= carry[7] << 21
   893  	carry[8] = s8 >> 21
   894  	s9 += carry[8]
   895  	s8 -= carry[8] << 21
   896  	carry[9] = s9 >> 21
   897  	s10 += carry[9]
   898  	s9 -= carry[9] << 21
   899  	carry[10] = s10 >> 21
   900  	s11 += carry[10]
   901  	s10 -= carry[10] << 21
   902  
   903  	out[0] = byte(s0 >> 0)
   904  	out[1] = byte(s0 >> 8)
   905  	out[2] = byte((s0 >> 16) | (s1 << 5))
   906  	out[3] = byte(s1 >> 3)
   907  	out[4] = byte(s1 >> 11)
   908  	out[5] = byte((s1 >> 19) | (s2 << 2))
   909  	out[6] = byte(s2 >> 6)
   910  	out[7] = byte((s2 >> 14) | (s3 << 7))
   911  	out[8] = byte(s3 >> 1)
   912  	out[9] = byte(s3 >> 9)
   913  	out[10] = byte((s3 >> 17) | (s4 << 4))
   914  	out[11] = byte(s4 >> 4)
   915  	out[12] = byte(s4 >> 12)
   916  	out[13] = byte((s4 >> 20) | (s5 << 1))
   917  	out[14] = byte(s5 >> 7)
   918  	out[15] = byte((s5 >> 15) | (s6 << 6))
   919  	out[16] = byte(s6 >> 2)
   920  	out[17] = byte(s6 >> 10)
   921  	out[18] = byte((s6 >> 18) | (s7 << 3))
   922  	out[19] = byte(s7 >> 5)
   923  	out[20] = byte(s7 >> 13)
   924  	out[21] = byte(s8 >> 0)
   925  	out[22] = byte(s8 >> 8)
   926  	out[23] = byte((s8 >> 16) | (s9 << 5))
   927  	out[24] = byte(s9 >> 3)
   928  	out[25] = byte(s9 >> 11)
   929  	out[26] = byte((s9 >> 19) | (s10 << 2))
   930  	out[27] = byte(s10 >> 6)
   931  	out[28] = byte((s10 >> 14) | (s11 << 7))
   932  	out[29] = byte(s11 >> 1)
   933  	out[30] = byte(s11 >> 9)
   934  	out[31] = byte(s11 >> 17)
   935  }
   936  
   937  // nonAdjacentForm computes a width-w non-adjacent form for this scalar.
   938  //
   939  // w must be between 2 and 8, or nonAdjacentForm will panic.
   940  func (s *Scalar) nonAdjacentForm(w uint) [256]int8 {
   941  	// This implementation is adapted from the one
   942  	// in curve25519-dalek and is documented there:
   943  	// https://github.com/dalek-cryptography/curve25519-dalek/blob/f630041af28e9a405255f98a8a93adca18e4315b/src/scalar.rs#L800-L871
   944  	if s.s[31] > 127 {
   945  		panic("scalar has high bit set illegally")
   946  	}
   947  	if w < 2 {
   948  		panic("w must be at least 2 by the definition of NAF")
   949  	} else if w > 8 {
   950  		panic("NAF digits must fit in int8")
   951  	}
   952  
   953  	var naf [256]int8
   954  	var digits [5]uint64
   955  
   956  	for i := 0; i < 4; i++ {
   957  		digits[i] = binary.LittleEndian.Uint64(s.s[i*8:])
   958  	}
   959  
   960  	width := uint64(1 << w)
   961  	windowMask := uint64(width - 1)
   962  
   963  	pos := uint(0)
   964  	carry := uint64(0)
   965  	for pos < 256 {
   966  		indexU64 := pos / 64
   967  		indexBit := pos % 64
   968  		var bitBuf uint64
   969  		if indexBit < 64-w {
   970  			// This window's bits are contained in a single u64
   971  			bitBuf = digits[indexU64] >> indexBit
   972  		} else {
   973  			// Combine the current 64 bits with bits from the next 64
   974  			bitBuf = (digits[indexU64] >> indexBit) | (digits[1+indexU64] << (64 - indexBit))
   975  		}
   976  
   977  		// Add carry into the current window
   978  		window := carry + (bitBuf & windowMask)
   979  
   980  		if window&1 == 0 {
   981  			// If the window value is even, preserve the carry and continue.
   982  			// Why is the carry preserved?
   983  			// If carry == 0 and window & 1 == 0,
   984  			//    then the next carry should be 0
   985  			// If carry == 1 and window & 1 == 0,
   986  			//    then bit_buf & 1 == 1 so the next carry should be 1
   987  			pos += 1
   988  			continue
   989  		}
   990  
   991  		if window < width/2 {
   992  			carry = 0
   993  			naf[pos] = int8(window)
   994  		} else {
   995  			carry = 1
   996  			naf[pos] = int8(window) - int8(width)
   997  		}
   998  
   999  		pos += w
  1000  	}
  1001  	return naf
  1002  }
  1003  
  1004  func (s *Scalar) signedRadix16() [64]int8 {
  1005  	if s.s[31] > 127 {
  1006  		panic("scalar has high bit set illegally")
  1007  	}
  1008  
  1009  	var digits [64]int8
  1010  
  1011  	// Compute unsigned radix-16 digits:
  1012  	for i := 0; i < 32; i++ {
  1013  		digits[2*i] = int8(s.s[i] & 15)
  1014  		digits[2*i+1] = int8((s.s[i] >> 4) & 15)
  1015  	}
  1016  
  1017  	// Recenter coefficients:
  1018  	for i := 0; i < 63; i++ {
  1019  		carry := (digits[i] + 8) >> 4
  1020  		digits[i] -= carry << 4
  1021  		digits[i+1] += carry
  1022  	}
  1023  
  1024  	return digits
  1025  }
  1026
View as plain text