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  func copyFieldElement(buf *[32]byte, v *field.Element) []byte {
   190  	copy(buf[:], v.Bytes())
   191  	return buf[:]
   192  }
   193  
   194  // Conversions.
   195  
   196  func (v *projP2) FromP1xP1(p *projP1xP1) *projP2 {
   197  	v.X.Multiply(&p.X, &p.T)
   198  	v.Y.Multiply(&p.Y, &p.Z)
   199  	v.Z.Multiply(&p.Z, &p.T)
   200  	return v
   201  }
   202  
   203  func (v *projP2) FromP3(p *Point) *projP2 {
   204  	v.X.Set(&p.x)
   205  	v.Y.Set(&p.y)
   206  	v.Z.Set(&p.z)
   207  	return v
   208  }
   209  
   210  func (v *Point) fromP1xP1(p *projP1xP1) *Point {
   211  	v.x.Multiply(&p.X, &p.T)
   212  	v.y.Multiply(&p.Y, &p.Z)
   213  	v.z.Multiply(&p.Z, &p.T)
   214  	v.t.Multiply(&p.X, &p.Y)
   215  	return v
   216  }
   217  
   218  func (v *Point) fromP2(p *projP2) *Point {
   219  	v.x.Multiply(&p.X, &p.Z)
   220  	v.y.Multiply(&p.Y, &p.Z)
   221  	v.z.Square(&p.Z)
   222  	v.t.Multiply(&p.X, &p.Y)
   223  	return v
   224  }
   225  
   226  // d is a constant in the curve equation.
   227  var d, _ = new(field.Element).SetBytes([]byte{
   228  	0xa3, 0x78, 0x59, 0x13, 0xca, 0x4d, 0xeb, 0x75,
   229  	0xab, 0xd8, 0x41, 0x41, 0x4d, 0x0a, 0x70, 0x00,
   230  	0x98, 0xe8, 0x79, 0x77, 0x79, 0x40, 0xc7, 0x8c,
   231  	0x73, 0xfe, 0x6f, 0x2b, 0xee, 0x6c, 0x03, 0x52})
   232  var d2 = new(field.Element).Add(d, d)
   233  
   234  func (v *projCached) FromP3(p *Point) *projCached {
   235  	v.YplusX.Add(&p.y, &p.x)
   236  	v.YminusX.Subtract(&p.y, &p.x)
   237  	v.Z.Set(&p.z)
   238  	v.T2d.Multiply(&p.t, d2)
   239  	return v
   240  }
   241  
   242  func (v *affineCached) FromP3(p *Point) *affineCached {
   243  	v.YplusX.Add(&p.y, &p.x)
   244  	v.YminusX.Subtract(&p.y, &p.x)
   245  	v.T2d.Multiply(&p.t, d2)
   246  
   247  	var invZ field.Element
   248  	invZ.Invert(&p.z)
   249  	v.YplusX.Multiply(&v.YplusX, &invZ)
   250  	v.YminusX.Multiply(&v.YminusX, &invZ)
   251  	v.T2d.Multiply(&v.T2d, &invZ)
   252  	return v
   253  }
   254  
   255  // (Re)addition and subtraction.
   256  
   257  // Add sets v = p + q, and returns v.
   258  func (v *Point) Add(p, q *Point) *Point {
   259  	checkInitialized(p, q)
   260  	qCached := new(projCached).FromP3(q)
   261  	result := new(projP1xP1).Add(p, qCached)
   262  	return v.fromP1xP1(result)
   263  }
   264  
   265  // Subtract sets v = p - q, and returns v.
   266  func (v *Point) Subtract(p, q *Point) *Point {
   267  	checkInitialized(p, q)
   268  	qCached := new(projCached).FromP3(q)
   269  	result := new(projP1xP1).Sub(p, qCached)
   270  	return v.fromP1xP1(result)
   271  }
   272  
   273  func (v *projP1xP1) Add(p *Point, q *projCached) *projP1xP1 {
   274  	var YplusX, YminusX, PP, MM, TT2d, ZZ2 field.Element
   275  
   276  	YplusX.Add(&p.y, &p.x)
   277  	YminusX.Subtract(&p.y, &p.x)
   278  
   279  	PP.Multiply(&YplusX, &q.YplusX)
   280  	MM.Multiply(&YminusX, &q.YminusX)
   281  	TT2d.Multiply(&p.t, &q.T2d)
   282  	ZZ2.Multiply(&p.z, &q.Z)
   283  
   284  	ZZ2.Add(&ZZ2, &ZZ2)
   285  
   286  	v.X.Subtract(&PP, &MM)
   287  	v.Y.Add(&PP, &MM)
   288  	v.Z.Add(&ZZ2, &TT2d)
   289  	v.T.Subtract(&ZZ2, &TT2d)
   290  	return v
   291  }
   292  
   293  func (v *projP1xP1) Sub(p *Point, q *projCached) *projP1xP1 {
   294  	var YplusX, YminusX, PP, MM, TT2d, ZZ2 field.Element
   295  
   296  	YplusX.Add(&p.y, &p.x)
   297  	YminusX.Subtract(&p.y, &p.x)
   298  
   299  	PP.Multiply(&YplusX, &q.YminusX) // flipped sign
   300  	MM.Multiply(&YminusX, &q.YplusX) // flipped sign
   301  	TT2d.Multiply(&p.t, &q.T2d)
   302  	ZZ2.Multiply(&p.z, &q.Z)
   303  
   304  	ZZ2.Add(&ZZ2, &ZZ2)
   305  
   306  	v.X.Subtract(&PP, &MM)
   307  	v.Y.Add(&PP, &MM)
   308  	v.Z.Subtract(&ZZ2, &TT2d) // flipped sign
   309  	v.T.Add(&ZZ2, &TT2d)      // flipped sign
   310  	return v
   311  }
   312  
   313  func (v *projP1xP1) AddAffine(p *Point, q *affineCached) *projP1xP1 {
   314  	var YplusX, YminusX, PP, MM, TT2d, Z2 field.Element
   315  
   316  	YplusX.Add(&p.y, &p.x)
   317  	YminusX.Subtract(&p.y, &p.x)
   318  
   319  	PP.Multiply(&YplusX, &q.YplusX)
   320  	MM.Multiply(&YminusX, &q.YminusX)
   321  	TT2d.Multiply(&p.t, &q.T2d)
   322  
   323  	Z2.Add(&p.z, &p.z)
   324  
   325  	v.X.Subtract(&PP, &MM)
   326  	v.Y.Add(&PP, &MM)
   327  	v.Z.Add(&Z2, &TT2d)
   328  	v.T.Subtract(&Z2, &TT2d)
   329  	return v
   330  }
   331  
   332  func (v *projP1xP1) SubAffine(p *Point, q *affineCached) *projP1xP1 {
   333  	var YplusX, YminusX, PP, MM, TT2d, Z2 field.Element
   334  
   335  	YplusX.Add(&p.y, &p.x)
   336  	YminusX.Subtract(&p.y, &p.x)
   337  
   338  	PP.Multiply(&YplusX, &q.YminusX) // flipped sign
   339  	MM.Multiply(&YminusX, &q.YplusX) // flipped sign
   340  	TT2d.Multiply(&p.t, &q.T2d)
   341  
   342  	Z2.Add(&p.z, &p.z)
   343  
   344  	v.X.Subtract(&PP, &MM)
   345  	v.Y.Add(&PP, &MM)
   346  	v.Z.Subtract(&Z2, &TT2d) // flipped sign
   347  	v.T.Add(&Z2, &TT2d)      // flipped sign
   348  	return v
   349  }
   350  
   351  // Doubling.
   352  
   353  func (v *projP1xP1) Double(p *projP2) *projP1xP1 {
   354  	var XX, YY, ZZ2, XplusYsq field.Element
   355  
   356  	XX.Square(&p.X)
   357  	YY.Square(&p.Y)
   358  	ZZ2.Square(&p.Z)
   359  	ZZ2.Add(&ZZ2, &ZZ2)
   360  	XplusYsq.Add(&p.X, &p.Y)
   361  	XplusYsq.Square(&XplusYsq)
   362  
   363  	v.Y.Add(&YY, &XX)
   364  	v.Z.Subtract(&YY, &XX)
   365  
   366  	v.X.Subtract(&XplusYsq, &v.Y)
   367  	v.T.Subtract(&ZZ2, &v.Z)
   368  	return v
   369  }
   370  
   371  // Negation.
   372  
   373  // Negate sets v = -p, and returns v.
   374  func (v *Point) Negate(p *Point) *Point {
   375  	checkInitialized(p)
   376  	v.x.Negate(&p.x)
   377  	v.y.Set(&p.y)
   378  	v.z.Set(&p.z)
   379  	v.t.Negate(&p.t)
   380  	return v
   381  }
   382  
   383  // Equal returns 1 if v is equivalent to u, and 0 otherwise.
   384  func (v *Point) Equal(u *Point) int {
   385  	checkInitialized(v, u)
   386  
   387  	var t1, t2, t3, t4 field.Element
   388  	t1.Multiply(&v.x, &u.z)
   389  	t2.Multiply(&u.x, &v.z)
   390  	t3.Multiply(&v.y, &u.z)
   391  	t4.Multiply(&u.y, &v.z)
   392  
   393  	return t1.Equal(&t2) & t3.Equal(&t4)
   394  }
   395  
   396  // Constant-time operations
   397  
   398  // Select sets v to a if cond == 1 and to b if cond == 0.
   399  func (v *projCached) Select(a, b *projCached, cond int) *projCached {
   400  	v.YplusX.Select(&a.YplusX, &b.YplusX, cond)
   401  	v.YminusX.Select(&a.YminusX, &b.YminusX, cond)
   402  	v.Z.Select(&a.Z, &b.Z, cond)
   403  	v.T2d.Select(&a.T2d, &b.T2d, cond)
   404  	return v
   405  }
   406  
   407  // Select sets v to a if cond == 1 and to b if cond == 0.
   408  func (v *affineCached) Select(a, b *affineCached, cond int) *affineCached {
   409  	v.YplusX.Select(&a.YplusX, &b.YplusX, cond)
   410  	v.YminusX.Select(&a.YminusX, &b.YminusX, cond)
   411  	v.T2d.Select(&a.T2d, &b.T2d, cond)
   412  	return v
   413  }
   414  
   415  // CondNeg negates v if cond == 1 and leaves it unchanged if cond == 0.
   416  func (v *projCached) CondNeg(cond int) *projCached {
   417  	v.YplusX.Swap(&v.YminusX, cond)
   418  	v.T2d.Select(new(field.Element).Negate(&v.T2d), &v.T2d, cond)
   419  	return v
   420  }
   421  
   422  // CondNeg negates v if cond == 1 and leaves it unchanged if cond == 0.
   423  func (v *affineCached) CondNeg(cond int) *affineCached {
   424  	v.YplusX.Swap(&v.YminusX, cond)
   425  	v.T2d.Select(new(field.Element).Negate(&v.T2d), &v.T2d, cond)
   426  	return v
   427  }
   428
View as plain text