fe.go

     1  // Copyright (c) 2017 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 field implements fast arithmetic modulo 2^255-19.
     6  package field
     7  
     8  import (
     9  	_ "crypto/internal/fips140/check"
    10  	"crypto/internal/fips140/subtle"
    11  	"crypto/internal/fips140deps/byteorder"
    12  	"errors"
    13  	"math/bits"
    14  )
    15  
    16  // Element represents an element of the field GF(2^255-19). Note that this
    17  // is not a cryptographically secure group, and should only be used to interact
    18  // with edwards25519.Point coordinates.
    19  //
    20  // This type works similarly to math/big.Int, and all arguments and receivers
    21  // are allowed to alias.
    22  //
    23  // The zero value is a valid zero element.
    24  type Element struct {
    25  	// An element t represents the integer
    26  	//     t.l0 + t.l1*2^51 + t.l2*2^102 + t.l3*2^153 + t.l4*2^204
    27  	//
    28  	// Between operations, all limbs are expected to be lower than 2^52.
    29  	l0 uint64
    30  	l1 uint64
    31  	l2 uint64
    32  	l3 uint64
    33  	l4 uint64
    34  }
    35  
    36  const maskLow51Bits uint64 = (1 << 51) - 1
    37  
    38  var feZero = &Element{0, 0, 0, 0, 0}
    39  
    40  // Zero sets v = 0, and returns v.
    41  func (v *Element) Zero() *Element {
    42  	*v = *feZero
    43  	return v
    44  }
    45  
    46  var feOne = &Element{1, 0, 0, 0, 0}
    47  
    48  // One sets v = 1, and returns v.
    49  func (v *Element) One() *Element {
    50  	*v = *feOne
    51  	return v
    52  }
    53  
    54  // reduce reduces v modulo 2^255 - 19 and returns it.
    55  func (v *Element) reduce() *Element {
    56  	v.carryPropagate()
    57  
    58  	// After the light reduction we now have a field element representation
    59  	// v < 2^255 + 2^13 * 19, but need v < 2^255 - 19.
    60  
    61  	// If v >= 2^255 - 19, then v + 19 >= 2^255, which would overflow 2^255 - 1,
    62  	// generating a carry. That is, c will be 0 if v < 2^255 - 19, and 1 otherwise.
    63  	c := (v.l0 + 19) >> 51
    64  	c = (v.l1 + c) >> 51
    65  	c = (v.l2 + c) >> 51
    66  	c = (v.l3 + c) >> 51
    67  	c = (v.l4 + c) >> 51
    68  
    69  	// If v < 2^255 - 19 and c = 0, this will be a no-op. Otherwise, it's
    70  	// effectively applying the reduction identity to the carry.
    71  	v.l0 += 19 * c
    72  
    73  	v.l1 += v.l0 >> 51
    74  	v.l0 = v.l0 & maskLow51Bits
    75  	v.l2 += v.l1 >> 51
    76  	v.l1 = v.l1 & maskLow51Bits
    77  	v.l3 += v.l2 >> 51
    78  	v.l2 = v.l2 & maskLow51Bits
    79  	v.l4 += v.l3 >> 51
    80  	v.l3 = v.l3 & maskLow51Bits
    81  	// no additional carry
    82  	v.l4 = v.l4 & maskLow51Bits
    83  
    84  	return v
    85  }
    86  
    87  // Add sets v = a + b, and returns v.
    88  func (v *Element) Add(a, b *Element) *Element {
    89  	v.l0 = a.l0 + b.l0
    90  	v.l1 = a.l1 + b.l1
    91  	v.l2 = a.l2 + b.l2
    92  	v.l3 = a.l3 + b.l3
    93  	v.l4 = a.l4 + b.l4
    94  	return v.carryPropagate()
    95  }
    96  
    97  // Subtract sets v = a - b, and returns v.
    98  func (v *Element) Subtract(a, b *Element) *Element {
    99  	// We first add 2 * p, to guarantee the subtraction won't underflow, and
   100  	// then subtract b (which can be up to 2^255 + 2^13 * 19).
   101  	v.l0 = (a.l0 + 0xFFFFFFFFFFFDA) - b.l0
   102  	v.l1 = (a.l1 + 0xFFFFFFFFFFFFE) - b.l1
   103  	v.l2 = (a.l2 + 0xFFFFFFFFFFFFE) - b.l2
   104  	v.l3 = (a.l3 + 0xFFFFFFFFFFFFE) - b.l3
   105  	v.l4 = (a.l4 + 0xFFFFFFFFFFFFE) - b.l4
   106  	return v.carryPropagate()
   107  }
   108  
   109  // Negate sets v = -a, and returns v.
   110  func (v *Element) Negate(a *Element) *Element {
   111  	return v.Subtract(feZero, a)
   112  }
   113  
   114  // Invert sets v = 1/z mod p, and returns v.
   115  //
   116  // If z == 0, Invert returns v = 0.
   117  func (v *Element) Invert(z *Element) *Element {
   118  	// Inversion is implemented as exponentiation with exponent p − 2.
   119  	// It uses 254 squarings and 11 multiplications, grouping squarings to use SquareN.
   120  	var z11, t0, t1, t2, t Element
   121  
   122  	t1.Square(z)           // 2
   123  	t.Square(&t1)          // 4
   124  	t.Square(&t)           // 8
   125  	t2.Multiply(&t, z)     // 9
   126  	z11.Multiply(&t2, &t1) // 11
   127  	t.Square(&z11)         // 22
   128  	t0.Multiply(&t, &t2)   // 31 = 2^5 - 2^0
   129  
   130  	t.SquareN(&t0, 5)    // 2^10 - 2^5
   131  	t2.Multiply(&t, &t0) // 2^10 - 1
   132  
   133  	t.SquareN(&t2, 5)    // 2^15 - 2^5
   134  	t0.Multiply(&t, &t0) // 2^15 - 1
   135  
   136  	t.SquareN(&t0, 15)   // 2^30 - 2^15
   137  	t1.Multiply(&t, &t0) // 2^30 - 1
   138  
   139  	t.SquareN(&t1, 30)   // 2^60 - 2^30
   140  	t0.Multiply(&t, &t1) // 2^60 - 1
   141  
   142  	t.SquareN(&t0, 60)   // 2^120 - 2^60
   143  	t1.Multiply(&t, &t0) // 2^120 - 1
   144  
   145  	t.SquareN(&t1, 120) // 2^240 - 2^120
   146  	t.Multiply(&t, &t1) // 2^240 - 1
   147  
   148  	t.SquareN(&t, 10)   // 2^250 - 2^10
   149  	t.Multiply(&t, &t2) // 2^250 - 1
   150  
   151  	t.SquareN(&t, 5) // 2^255 - 2^5
   152  
   153  	return v.Multiply(&t, &z11) // 2^255 - 21
   154  }
   155  
   156  // Set sets v = a, and returns v.
   157  func (v *Element) Set(a *Element) *Element {
   158  	*v = *a
   159  	return v
   160  }
   161  
   162  // SetBytes sets v to x, where x is a 32-byte little-endian encoding. If x is
   163  // not of the right length, SetBytes returns nil and an error, and the
   164  // receiver is unchanged.
   165  //
   166  // Consistent with RFC 7748, the most significant bit (the high bit of the
   167  // last byte) is ignored, and non-canonical values (2^255-19 through 2^255-1)
   168  // are accepted. Note that this is laxer than specified by RFC 8032, but
   169  // consistent with most Ed25519 implementations.
   170  func (v *Element) SetBytes(x []byte) (*Element, error) {
   171  	if len(x) != 32 {
   172  		return nil, errors.New("edwards25519: invalid field element input size")
   173  	}
   174  
   175  	// Bits 0:51 (bytes 0:8, bits 0:64, shift 0, mask 51).
   176  	v.l0 = byteorder.LEUint64(x[0:8])
   177  	v.l0 &= maskLow51Bits
   178  	// Bits 51:102 (bytes 6:14, bits 48:112, shift 3, mask 51).
   179  	v.l1 = byteorder.LEUint64(x[6:14]) >> 3
   180  	v.l1 &= maskLow51Bits
   181  	// Bits 102:153 (bytes 12:20, bits 96:160, shift 6, mask 51).
   182  	v.l2 = byteorder.LEUint64(x[12:20]) >> 6
   183  	v.l2 &= maskLow51Bits
   184  	// Bits 153:204 (bytes 19:27, bits 152:216, shift 1, mask 51).
   185  	v.l3 = byteorder.LEUint64(x[19:27]) >> 1
   186  	v.l3 &= maskLow51Bits
   187  	// Bits 204:255 (bytes 24:32, bits 192:256, shift 12, mask 51).
   188  	// Note: not bytes 25:33, shift 4, to avoid overread.
   189  	v.l4 = byteorder.LEUint64(x[24:32]) >> 12
   190  	v.l4 &= maskLow51Bits
   191  
   192  	return v, nil
   193  }
   194  
   195  // Bytes returns the canonical 32-byte little-endian encoding of v.
   196  func (v *Element) Bytes() []byte {
   197  	// This function is outlined to make the allocations inline in the caller
   198  	// rather than happen on the heap.
   199  	var out [32]byte
   200  	return v.bytes(&out)
   201  }
   202  
   203  func (v *Element) bytes(out *[32]byte) []byte {
   204  	t := *v
   205  	t.reduce()
   206  
   207  	// Pack five 51-bit limbs into four 64-bit words:
   208  	//
   209  	//  255    204    153    102     51      0
   210  	//    ├──l4──┼──l3──┼──l2──┼──l1──┼──l0──┤
   211  	//   ├───u3───┼───u2───┼───u1───┼───u0───┤
   212  	// 256      192      128       64        0
   213  
   214  	u0 := t.l1<<51 | t.l0
   215  	u1 := t.l2<<(102-64) | t.l1>>(64-51)
   216  	u2 := t.l3<<(153-128) | t.l2>>(128-102)
   217  	u3 := t.l4<<(204-192) | t.l3>>(192-153)
   218  
   219  	byteorder.LEPutUint64(out[0*8:], u0)
   220  	byteorder.LEPutUint64(out[1*8:], u1)
   221  	byteorder.LEPutUint64(out[2*8:], u2)
   222  	byteorder.LEPutUint64(out[3*8:], u3)
   223  
   224  	return out[:]
   225  }
   226  
   227  // Equal returns 1 if v and u are equal, and 0 otherwise.
   228  func (v *Element) Equal(u *Element) int {
   229  	sa, sv := u.Bytes(), v.Bytes()
   230  	return subtle.ConstantTimeCompare(sa, sv)
   231  }
   232  
   233  // mask64Bits returns 0xffffffff if cond is 1, and 0 otherwise.
   234  func mask64Bits(cond int) uint64 { return ^(uint64(cond) - 1) }
   235  
   236  // Select sets v to a if cond == 1, and to b if cond == 0.
   237  func (v *Element) Select(a, b *Element, cond int) *Element {
   238  	m := mask64Bits(cond)
   239  	v.l0 = (m & a.l0) | (^m & b.l0)
   240  	v.l1 = (m & a.l1) | (^m & b.l1)
   241  	v.l2 = (m & a.l2) | (^m & b.l2)
   242  	v.l3 = (m & a.l3) | (^m & b.l3)
   243  	v.l4 = (m & a.l4) | (^m & b.l4)
   244  	return v
   245  }
   246  
   247  // Swap swaps v and u if cond == 1 or leaves them unchanged if cond == 0, and returns v.
   248  func (v *Element) Swap(u *Element, cond int) {
   249  	m := mask64Bits(cond)
   250  	t := m & (v.l0 ^ u.l0)
   251  	v.l0 ^= t
   252  	u.l0 ^= t
   253  	t = m & (v.l1 ^ u.l1)
   254  	v.l1 ^= t
   255  	u.l1 ^= t
   256  	t = m & (v.l2 ^ u.l2)
   257  	v.l2 ^= t
   258  	u.l2 ^= t
   259  	t = m & (v.l3 ^ u.l3)
   260  	v.l3 ^= t
   261  	u.l3 ^= t
   262  	t = m & (v.l4 ^ u.l4)
   263  	v.l4 ^= t
   264  	u.l4 ^= t
   265  }
   266  
   267  // IsNegative returns 1 if v is negative, and 0 otherwise.
   268  func (v *Element) IsNegative() int {
   269  	return int(v.Bytes()[0] & 1)
   270  }
   271  
   272  // Absolute sets v to |u|, and returns v.
   273  func (v *Element) Absolute(u *Element) *Element {
   274  	return v.Select(new(Element).Negate(u), u, u.IsNegative())
   275  }
   276  
   277  // Multiply sets v = x * y, and returns v.
   278  func (v *Element) Multiply(x, y *Element) *Element {
   279  	feMul(v, x, y)
   280  	return v
   281  }
   282  
   283  // Square sets v = x * x, and returns v.
   284  func (v *Element) Square(x *Element) *Element {
   285  	feSquare(v, x)
   286  	return v
   287  }
   288  
   289  // SquareN sets v = x^(2^n), and returns v. n must be positive.
   290  func (v *Element) SquareN(x *Element, n int) *Element {
   291  	feSquareN(v, x, n)
   292  	return v
   293  }
   294  
   295  // Mult32 sets v = x * y, and returns v.
   296  func (v *Element) Mult32(x *Element, y uint32) *Element {
   297  	x0lo, x0hi := mul51(x.l0, y)
   298  	x1lo, x1hi := mul51(x.l1, y)
   299  	x2lo, x2hi := mul51(x.l2, y)
   300  	x3lo, x3hi := mul51(x.l3, y)
   301  	x4lo, x4hi := mul51(x.l4, y)
   302  	v.l0 = x0lo + 19*x4hi // carried over per the reduction identity
   303  	v.l1 = x1lo + x0hi
   304  	v.l2 = x2lo + x1hi
   305  	v.l3 = x3lo + x2hi
   306  	v.l4 = x4lo + x3hi
   307  	// The hi portions are going to be only 32 bits, plus any previous excess,
   308  	// so we can skip the carry propagation.
   309  	return v
   310  }
   311  
   312  // mul51 returns lo + hi * 2⁵¹ = a * b.
   313  func mul51(a uint64, b uint32) (lo uint64, hi uint64) {
   314  	mh, ml := bits.Mul64(a, uint64(b))
   315  	lo = ml & maskLow51Bits
   316  	hi = (mh << 13) | (ml >> 51)
   317  	return
   318  }
   319  
   320  // Pow22523 set v = x^((p-5)/8), and returns v. (p-5)/8 is 2^252-3.
   321  func (v *Element) Pow22523(x *Element) *Element {
   322  	var t0, t1, t2 Element
   323  
   324  	t0.Square(x)          // x^2
   325  	t1.Multiply(x, &t0)   // x^3
   326  	t0.Square(&t1)        // x^6
   327  	t0.Square(&t0)        // x^12
   328  	t0.Multiply(&t1, &t0) // x^15
   329  	t0.Square(&t0)        // x^30
   330  	t0.Multiply(x, &t0)   // x^31 = 2^5 - 1
   331  
   332  	t1.SquareN(&t0, 5)    // 2^10 - 2^5
   333  	t1.Multiply(&t1, &t0) // 2^10 - 1
   334  
   335  	t2.SquareN(&t1, 5)    // 2^15 - 2^5
   336  	t0.Multiply(&t2, &t0) // 2^15 - 1
   337  
   338  	t2.SquareN(&t0, 15)   // 2^30 - 2^15
   339  	t2.Multiply(&t2, &t0) // 2^30 - 1
   340  
   341  	t0.SquareN(&t2, 30)   // 2^60 - 2^30
   342  	t0.Multiply(&t0, &t2) // 2^60 - 1
   343  
   344  	t2.SquareN(&t0, 60)   // 2^120 - 2^60
   345  	t2.Multiply(&t2, &t0) // 2^120 - 1
   346  
   347  	t0.SquareN(&t2, 120)  // 2^240 - 2^120
   348  	t0.Multiply(&t0, &t2) // 2^240 - 1
   349  
   350  	t0.SquareN(&t0, 10)   // 2^250 - 2^10
   351  	t0.Multiply(&t0, &t1) // 2^250 - 1
   352  
   353  	t0.SquareN(&t0, 2)        // 2^252 - 4
   354  	return v.Multiply(&t0, x) // 2^252 - 3
   355  }
   356  
   357  // sqrtM1 is 2^((p-1)/4), which squared is equal to -1 by Euler's Criterion.
   358  var sqrtM1 = &Element{1718705420411056, 234908883556509,
   359  	2233514472574048, 2117202627021982, 765476049583133}
   360  
   361  // SqrtRatio sets r to the non-negative square root of the ratio of u and v.
   362  //
   363  // If u/v is square, SqrtRatio returns r and 1. If u/v is not square, SqrtRatio
   364  // sets r according to Section 4.3 of draft-irtf-cfrg-ristretto255-decaf448-00,
   365  // and returns r and 0.
   366  func (r *Element) SqrtRatio(u, v *Element) (R *Element, wasSquare int) {
   367  	t0 := new(Element)
   368  
   369  	// r = (u * v3) * (u * v7)^((p-5)/8)
   370  	v2 := new(Element).Square(v)
   371  	uv3 := new(Element).Multiply(u, t0.Multiply(v2, v))
   372  	uv7 := new(Element).Multiply(uv3, t0.Square(v2))
   373  	rr := new(Element).Multiply(uv3, t0.Pow22523(uv7))
   374  
   375  	check := new(Element).Multiply(v, t0.Square(rr)) // check = v * r^2
   376  
   377  	uNeg := new(Element).Negate(u)
   378  	correctSignSqrt := check.Equal(u)
   379  	flippedSignSqrt := check.Equal(uNeg)
   380  	flippedSignSqrtI := check.Equal(t0.Multiply(uNeg, sqrtM1))
   381  
   382  	rPrime := new(Element).Multiply(rr, sqrtM1) // r_prime = SQRT_M1 * r
   383  	// r = CT_SELECT(r_prime IF flipped_sign_sqrt | flipped_sign_sqrt_i ELSE r)
   384  	rr.Select(rPrime, rr, flippedSignSqrt|flippedSignSqrtI)
   385  
   386  	r.Absolute(rr) // Choose the nonnegative square root.
   387  	return r, correctSignSqrt | flippedSignSqrt
   388  }
   389
View as plain text