edwards25519.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 edwards25519
     6  
     7  import (
     8  	_ "crypto/internal/fips140/check"
     9  	"crypto/internal/fips140/edwards25519/field"
    10  	"errors"
    11  )
    12  
    13  // Point types.
    14  
    15  type projP1xP1 struct {
    16  	X, Y, Z, T field.Element
    17  }
    18  
    19  type projP2 struct {
    20  	X, Y, Z field.Element
    21  }
    22  
    23  // Point represents a point on the edwards25519 curve.
    24  //
    25  // This type works similarly to math/big.Int, and all arguments and receivers
    26  // are allowed to alias.
    27  //
    28  // The zero value is NOT valid, and it may be used only as a receiver.
    29  type Point struct {
    30  	// Make the type not comparable (i.e. used with == or as a map key), as
    31  	// equivalent points can be represented by different Go values.
    32  	_ incomparable
    33  
    34  	// The point is internally represented in extended coordinates (X, Y, Z, T)
    35  	// where x = X/Z, y = Y/Z, and xy = T/Z per https://eprint.iacr.org/2008/522.
    36  	x, y, z, t field.Element
    37  }
    38  
    39  type incomparable [0]func()
    40  
    41  func checkInitialized(points ...*Point) {
    42  	for _, p := range points {
    43  		if p.x == (field.Element{}) && p.y == (field.Element{}) {
    44  			panic("edwards25519: use of uninitialized Point")
    45  		}
    46  	}
    47  }
    48  
    49  type projCached struct {
    50  	YplusX, YminusX, Z, T2d field.Element
    51  }
    52  
    53  type affineCached struct {
    54  	YplusX, YminusX, T2d field.Element
    55  }
    56  
    57  // Constructors.
    58  
    59  func (v *projP2) Zero() *projP2 {
    60  	v.X.Zero()
    61  	v.Y.One()
    62  	v.Z.One()
    63  	return v
    64  }
    65  
    66  // identity is the point at infinity.
    67  var identity, _ = new(Point).SetBytes([]byte{
    68  	1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    69  	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0})
    70  
    71  // NewIdentityPoint returns a new Point set to the identity.
    72  func NewIdentityPoint() *Point {
    73  	return new(Point).Set(identity)
    74  }
    75  
    76  // generator is the canonical curve basepoint. See TestGenerator for the
    77  // correspondence of this encoding with the values in RFC 8032.
    78  var generator, _ = new(Point).SetBytes([]byte{
    79  	0x58, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66,
    80  	0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66,
    81  	0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66,
    82  	0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66})
    83  
    84  // NewGeneratorPoint returns a new Point set to the canonical generator.
    85  func NewGeneratorPoint() *Point {
    86  	return new(Point).Set(generator)
    87  }
    88  
    89  func (v *projCached) Zero() *projCached {
    90  	v.YplusX.One()
    91  	v.YminusX.One()
    92  	v.Z.One()
    93  	v.T2d.Zero()
    94  	return v
    95  }
    96  
    97  func (v *affineCached) Zero() *affineCached {
    98  	v.YplusX.One()
    99  	v.YminusX.One()
   100  	v.T2d.Zero()
   101  	return v
   102  }
   103  
   104  // Assignments.
   105  
   106  // Set sets v = u, and returns v.
   107  func (v *Point) Set(u *Point) *Point {
   108  	*v = *u
   109  	return v
   110  }
   111  
   112  // Encoding.
   113  
   114  // Bytes returns the canonical 32-byte encoding of v, according to RFC 8032,
   115  // Section 5.1.2.
   116  func (v *Point) Bytes() []byte {
   117  	// This function is outlined to make the allocations inline in the caller
   118  	// rather than happen on the heap.
   119  	var buf [32]byte
   120  	return v.bytes(&buf)
   121  }
   122  
   123  func (v *Point) bytes(buf *[32]byte) []byte {
   124  	checkInitialized(v)
   125  
   126  	var zInv, x, y field.Element
   127  	zInv.Invert(&v.z)       // zInv = 1 / Z
   128  	x.Multiply(&v.x, &zInv) // x = X / Z
   129  	y.Multiply(&v.y, &zInv) // y = Y / Z
   130  
   131  	out := copyFieldElement(buf, &y)
   132  	out[31] |= byte(x.IsNegative() << 7)
   133  	return out
   134  }
   135  
   136  var feOne = new(field.Element).One()
   137  
   138  // SetBytes sets v = x, where x is a 32-byte encoding of v. If x does not
   139  // represent a valid point on the curve, SetBytes returns nil and an error and
   140  // the receiver is unchanged. Otherwise, SetBytes returns v.
   141  //
   142  // Note that SetBytes accepts all non-canonical encodings of valid points.
   143  // That is, it follows decoding rules that match most implementations in
   144  // the ecosystem rather than RFC 8032.
   145  func (v *Point) SetBytes(x []byte) (*Point, error) {
   146  	// Specifically, the non-canonical encodings that are accepted are
   147  	//   1) the ones where the field element is not reduced (see the
   148  	//      (*field.Element).SetBytes docs) and
   149  	//   2) the ones where the x-coordinate is zero and the sign bit is set.
   150  	//
   151  	// Read more at https://hdevalence.ca/blog/2020-10-04-its-25519am,
   152  	// specifically the "Canonical A, R" section.
   153  
   154  	y, err := new(field.Element).SetBytes(x)
   155  	if err != nil {
   156  		return nil, errors.New("edwards25519: invalid point encoding length")
   157  	}
   158  
   159  	// -x² + y² = 1 + dx²y²
   160  	// x² + dx²y² = x²(dy² + 1) = y² - 1
   161  	// x² = (y² - 1) / (dy² + 1)
   162  
   163  	// u = y² - 1
   164  	y2 := new(field.Element).Square(y)
   165  	u := new(field.Element).Subtract(y2, feOne)
   166  
   167  	// v = dy² + 1
   168  	vv := new(field.Element).Multiply(y2, d)
   169  	vv = vv.Add(vv, feOne)
   170  
   171  	// x = +√(u/v)
   172  	xx, wasSquare := new(field.Element).SqrtRatio(u, vv)
   173  	if wasSquare == 0 {
   174  		return nil, errors.New("edwards25519: invalid point encoding")
   175  	}
   176  
   177  	// Select the negative square root if the sign bit is set.
   178  	xxNeg := new(field.Element).Negate(xx)
   179  	xx = xx.Select(xxNeg, xx, int(x[31]>>7))
   180  
   181  	v.x.Set(xx)
   182  	v.y.Set(y)
   183  	v.z.One()
   184  	v.t.Multiply(xx, y) // xy = T / Z
   185  
   186  	return v, nil
   187  }
   188  
   189  // BytesMontgomery converts v to a point on the birationally-equivalent
   190  // Curve25519 Montgomery curve, and returns its canonical 32 bytes encoding
   191  // according to RFC 7748.
   192  //
   193  // Note that BytesMontgomery only encodes the u-coordinate, so v and -v encode
   194  // to the same value. If v is the identity point, BytesMontgomery returns 32
   195  // zero bytes, analogously to the X25519 function.
   196  //
   197  // The lack of an inverse operation (such as SetMontgomeryBytes) is deliberate:
   198  // while every valid edwards25519 point has a unique u-coordinate Montgomery
   199  // encoding, X25519 accepts inputs on the quadratic twist, which don't correspond
   200  // to any edwards25519 point, and every other X25519 input corresponds to two
   201  // edwards25519 points.
   202  func (v *Point) BytesMontgomery() []byte {
   203  	// This function is outlined to make the allocations inline in the caller
   204  	// rather than happen on the heap.
   205  	var buf [32]byte
   206  	return v.bytesMontgomery(&buf)
   207  }
   208  
   209  func (v *Point) bytesMontgomery(buf *[32]byte) []byte {
   210  	checkInitialized(v)
   211  
   212  	// RFC 7748, Section 4.1 provides the bilinear map to calculate the
   213  	// Montgomery u-coordinate
   214  	//
   215  	//              u = (1 + y) / (1 - y)
   216  	//
   217  	// where y = Y / Z and therefore
   218  	//
   219  	//              u = (Z + Y) / (Z - Y)
   220  
   221  	var n, r, u field.Element
   222  
   223  	n.Add(&v.z, &v.y)                // n = Z + Y
   224  	r.Invert(r.Subtract(&v.z, &v.y)) // r = 1 / (Z - Y)
   225  	u.Multiply(&n, &r)               // u = n * r
   226  
   227  	return copyFieldElement(buf, &u)
   228  }
   229  
   230  func copyFieldElement(buf *[32]byte, v *field.Element) []byte {
   231  	copy(buf[:], v.Bytes())
   232  	return buf[:]
   233  }
   234  
   235  // Conversions.
   236  
   237  func (v *projP2) FromP1xP1(p *projP1xP1) *projP2 {
   238  	v.X.Multiply(&p.X, &p.T)
   239  	v.Y.Multiply(&p.Y, &p.Z)
   240  	v.Z.Multiply(&p.Z, &p.T)
   241  	return v
   242  }
   243  
   244  func (v *projP2) FromP3(p *Point) *projP2 {
   245  	v.X.Set(&p.x)
   246  	v.Y.Set(&p.y)
   247  	v.Z.Set(&p.z)
   248  	return v
   249  }
   250  
   251  func (v *Point) fromP1xP1(p *projP1xP1) *Point {
   252  	v.x.Multiply(&p.X, &p.T)
   253  	v.y.Multiply(&p.Y, &p.Z)
   254  	v.z.Multiply(&p.Z, &p.T)
   255  	v.t.Multiply(&p.X, &p.Y)
   256  	return v
   257  }
   258  
   259  func (v *Point) fromP2(p *projP2) *Point {
   260  	v.x.Multiply(&p.X, &p.Z)
   261  	v.y.Multiply(&p.Y, &p.Z)
   262  	v.z.Square(&p.Z)
   263  	v.t.Multiply(&p.X, &p.Y)
   264  	return v
   265  }
   266  
   267  // d is a constant in the curve equation.
   268  var d, _ = new(field.Element).SetBytes([]byte{
   269  	0xa3, 0x78, 0x59, 0x13, 0xca, 0x4d, 0xeb, 0x75,
   270  	0xab, 0xd8, 0x41, 0x41, 0x4d, 0x0a, 0x70, 0x00,
   271  	0x98, 0xe8, 0x79, 0x77, 0x79, 0x40, 0xc7, 0x8c,
   272  	0x73, 0xfe, 0x6f, 0x2b, 0xee, 0x6c, 0x03, 0x52})
   273  var d2 = new(field.Element).Add(d, d)
   274  
   275  func (v *projCached) FromP3(p *Point) *projCached {
   276  	v.YplusX.Add(&p.y, &p.x)
   277  	v.YminusX.Subtract(&p.y, &p.x)
   278  	v.Z.Set(&p.z)
   279  	v.T2d.Multiply(&p.t, d2)
   280  	return v
   281  }
   282  
   283  func (v *affineCached) FromP3(p *Point) *affineCached {
   284  	v.YplusX.Add(&p.y, &p.x)
   285  	v.YminusX.Subtract(&p.y, &p.x)
   286  	v.T2d.Multiply(&p.t, d2)
   287  
   288  	var invZ field.Element
   289  	invZ.Invert(&p.z)
   290  	v.YplusX.Multiply(&v.YplusX, &invZ)
   291  	v.YminusX.Multiply(&v.YminusX, &invZ)
   292  	v.T2d.Multiply(&v.T2d, &invZ)
   293  	return v
   294  }
   295  
   296  // (Re)addition and subtraction.
   297  
   298  // Add sets v = p + q, and returns v.
   299  func (v *Point) Add(p, q *Point) *Point {
   300  	checkInitialized(p, q)
   301  	qCached := new(projCached).FromP3(q)
   302  	result := new(projP1xP1).Add(p, qCached)
   303  	return v.fromP1xP1(result)
   304  }
   305  
   306  // Subtract sets v = p - q, and returns v.
   307  func (v *Point) Subtract(p, q *Point) *Point {
   308  	checkInitialized(p, q)
   309  	qCached := new(projCached).FromP3(q)
   310  	result := new(projP1xP1).Sub(p, qCached)
   311  	return v.fromP1xP1(result)
   312  }
   313  
   314  func (v *projP1xP1) Add(p *Point, q *projCached) *projP1xP1 {
   315  	var YplusX, YminusX, PP, MM, TT2d, ZZ2 field.Element
   316  
   317  	YplusX.Add(&p.y, &p.x)
   318  	YminusX.Subtract(&p.y, &p.x)
   319  
   320  	PP.Multiply(&YplusX, &q.YplusX)
   321  	MM.Multiply(&YminusX, &q.YminusX)
   322  	TT2d.Multiply(&p.t, &q.T2d)
   323  	ZZ2.Multiply(&p.z, &q.Z)
   324  
   325  	ZZ2.Add(&ZZ2, &ZZ2)
   326  
   327  	v.X.Subtract(&PP, &MM)
   328  	v.Y.Add(&PP, &MM)
   329  	v.Z.Add(&ZZ2, &TT2d)
   330  	v.T.Subtract(&ZZ2, &TT2d)
   331  	return v
   332  }
   333  
   334  func (v *projP1xP1) Sub(p *Point, q *projCached) *projP1xP1 {
   335  	var YplusX, YminusX, PP, MM, TT2d, ZZ2 field.Element
   336  
   337  	YplusX.Add(&p.y, &p.x)
   338  	YminusX.Subtract(&p.y, &p.x)
   339  
   340  	PP.Multiply(&YplusX, &q.YminusX) // flipped sign
   341  	MM.Multiply(&YminusX, &q.YplusX) // flipped sign
   342  	TT2d.Multiply(&p.t, &q.T2d)
   343  	ZZ2.Multiply(&p.z, &q.Z)
   344  
   345  	ZZ2.Add(&ZZ2, &ZZ2)
   346  
   347  	v.X.Subtract(&PP, &MM)
   348  	v.Y.Add(&PP, &MM)
   349  	v.Z.Subtract(&ZZ2, &TT2d) // flipped sign
   350  	v.T.Add(&ZZ2, &TT2d)      // flipped sign
   351  	return v
   352  }
   353  
   354  func (v *projP1xP1) AddAffine(p *Point, q *affineCached) *projP1xP1 {
   355  	var YplusX, YminusX, PP, MM, TT2d, Z2 field.Element
   356  
   357  	YplusX.Add(&p.y, &p.x)
   358  	YminusX.Subtract(&p.y, &p.x)
   359  
   360  	PP.Multiply(&YplusX, &q.YplusX)
   361  	MM.Multiply(&YminusX, &q.YminusX)
   362  	TT2d.Multiply(&p.t, &q.T2d)
   363  
   364  	Z2.Add(&p.z, &p.z)
   365  
   366  	v.X.Subtract(&PP, &MM)
   367  	v.Y.Add(&PP, &MM)
   368  	v.Z.Add(&Z2, &TT2d)
   369  	v.T.Subtract(&Z2, &TT2d)
   370  	return v
   371  }
   372  
   373  func (v *projP1xP1) SubAffine(p *Point, q *affineCached) *projP1xP1 {
   374  	var YplusX, YminusX, PP, MM, TT2d, Z2 field.Element
   375  
   376  	YplusX.Add(&p.y, &p.x)
   377  	YminusX.Subtract(&p.y, &p.x)
   378  
   379  	PP.Multiply(&YplusX, &q.YminusX) // flipped sign
   380  	MM.Multiply(&YminusX, &q.YplusX) // flipped sign
   381  	TT2d.Multiply(&p.t, &q.T2d)
   382  
   383  	Z2.Add(&p.z, &p.z)
   384  
   385  	v.X.Subtract(&PP, &MM)
   386  	v.Y.Add(&PP, &MM)
   387  	v.Z.Subtract(&Z2, &TT2d) // flipped sign
   388  	v.T.Add(&Z2, &TT2d)      // flipped sign
   389  	return v
   390  }
   391  
   392  // Doubling.
   393  
   394  func (v *projP1xP1) Double(p *projP2) *projP1xP1 {
   395  	var XX, YY, ZZ2, XplusYsq field.Element
   396  
   397  	XX.Square(&p.X)
   398  	YY.Square(&p.Y)
   399  	ZZ2.Square(&p.Z)
   400  	ZZ2.Add(&ZZ2, &ZZ2)
   401  	XplusYsq.Add(&p.X, &p.Y)
   402  	XplusYsq.Square(&XplusYsq)
   403  
   404  	v.Y.Add(&YY, &XX)
   405  	v.Z.Subtract(&YY, &XX)
   406  
   407  	v.X.Subtract(&XplusYsq, &v.Y)
   408  	v.T.Subtract(&ZZ2, &v.Z)
   409  	return v
   410  }
   411  
   412  // Negation.
   413  
   414  // Negate sets v = -p, and returns v.
   415  func (v *Point) Negate(p *Point) *Point {
   416  	checkInitialized(p)
   417  	v.x.Negate(&p.x)
   418  	v.y.Set(&p.y)
   419  	v.z.Set(&p.z)
   420  	v.t.Negate(&p.t)
   421  	return v
   422  }
   423  
   424  // Equal returns 1 if v is equivalent to u, and 0 otherwise.
   425  func (v *Point) Equal(u *Point) int {
   426  	checkInitialized(v, u)
   427  
   428  	var t1, t2, t3, t4 field.Element
   429  	t1.Multiply(&v.x, &u.z)
   430  	t2.Multiply(&u.x, &v.z)
   431  	t3.Multiply(&v.y, &u.z)
   432  	t4.Multiply(&u.y, &v.z)
   433  
   434  	return t1.Equal(&t2) & t3.Equal(&t4)
   435  }
   436  
   437  // Constant-time operations
   438  
   439  // Select sets v to a if cond == 1 and to b if cond == 0.
   440  func (v *projCached) Select(a, b *projCached, cond int) *projCached {
   441  	v.YplusX.Select(&a.YplusX, &b.YplusX, cond)
   442  	v.YminusX.Select(&a.YminusX, &b.YminusX, cond)
   443  	v.Z.Select(&a.Z, &b.Z, cond)
   444  	v.T2d.Select(&a.T2d, &b.T2d, cond)
   445  	return v
   446  }
   447  
   448  // Select sets v to a if cond == 1 and to b if cond == 0.
   449  func (v *affineCached) Select(a, b *affineCached, cond int) *affineCached {
   450  	v.YplusX.Select(&a.YplusX, &b.YplusX, cond)
   451  	v.YminusX.Select(&a.YminusX, &b.YminusX, cond)
   452  	v.T2d.Select(&a.T2d, &b.T2d, cond)
   453  	return v
   454  }
   455  
   456  // CondNeg negates v if cond == 1 and leaves it unchanged if cond == 0.
   457  func (v *projCached) CondNeg(cond int) *projCached {
   458  	v.YplusX.Swap(&v.YminusX, cond)
   459  	v.T2d.Select(new(field.Element).Negate(&v.T2d), &v.T2d, cond)
   460  	return v
   461  }
   462  
   463  // CondNeg negates v if cond == 1 and leaves it unchanged if cond == 0.
   464  func (v *affineCached) CondNeg(cond int) *affineCached {
   465  	v.YplusX.Swap(&v.YminusX, cond)
   466  	v.T2d.Select(new(field.Element).Negate(&v.T2d), &v.T2d, cond)
   467  	return v
   468  }
   469
View as plain text