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/ed25519/internal/edwards25519/field"
     9  	"errors"
    10  )
    11  
    12  // Point types.
    13  
    14  type projP1xP1 struct {
    15  	X, Y, Z, T field.Element
    16  }
    17  
    18  type projP2 struct {
    19  	X, Y, Z field.Element
    20  }
    21  
    22  // Point represents a point on the edwards25519 curve.
    23  //
    24  // This type works similarly to math/big.Int, and all arguments and receivers
    25  // are allowed to alias.
    26  //
    27  // The zero value is NOT valid, and it may be used only as a receiver.
    28  type Point struct {
    29  	// The point is internally represented in extended coordinates (X, Y, Z, T)
    30  	// where x = X/Z, y = Y/Z, and xy = T/Z per https://eprint.iacr.org/2008/522.
    31  	x, y, z, t field.Element
    32  
    33  	// Make the type not comparable (i.e. used with == or as a map key), as
    34  	// equivalent points can be represented by different Go values.
    35  	_ incomparable
    36  }
    37  
    38  type incomparable [0]func()
    39  
    40  func checkInitialized(points ...*Point) {
    41  	for _, p := range points {
    42  		if p.x == (field.Element{}) && p.y == (field.Element{}) {
    43  			panic("edwards25519: use of uninitialized Point")
    44  		}
    45  	}
    46  }
    47  
    48  type projCached struct {
    49  	YplusX, YminusX, Z, T2d field.Element
    50  }
    51  
    52  type affineCached struct {
    53  	YplusX, YminusX, T2d field.Element
    54  }
    55  
    56  // Constructors.
    57  
    58  func (v *projP2) Zero() *projP2 {
    59  	v.X.Zero()
    60  	v.Y.One()
    61  	v.Z.One()
    62  	return v
    63  }
    64  
    65  // identity is the point at infinity.
    66  var identity, _ = new(Point).SetBytes([]byte{
    67  	1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    68  	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0})
    69  
    70  // NewIdentityPoint returns a new Point set to the identity.
    71  func NewIdentityPoint() *Point {
    72  	return new(Point).Set(identity)
    73  }
    74  
    75  // generator is the canonical curve basepoint. See TestGenerator for the
    76  // correspondence of this encoding with the values in RFC 8032.
    77  var generator, _ = new(Point).SetBytes([]byte{
    78  	0x58, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66,
    79  	0x66, 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  
    83  // NewGeneratorPoint returns a new Point set to the canonical generator.
    84  func NewGeneratorPoint() *Point {
    85  	return new(Point).Set(generator)
    86  }
    87  
    88  func (v *projCached) Zero() *projCached {
    89  	v.YplusX.One()
    90  	v.YminusX.One()
    91  	v.Z.One()
    92  	v.T2d.Zero()
    93  	return v
    94  }
    95  
    96  func (v *affineCached) Zero() *affineCached {
    97  	v.YplusX.One()
    98  	v.YminusX.One()
    99  	v.T2d.Zero()
   100  	return v
   101  }
   102  
   103  // Assignments.
   104  
   105  // Set sets v = u, and returns v.
   106  func (v *Point) Set(u *Point) *Point {
   107  	*v = *u
   108  	return v
   109  }
   110  
   111  // Encoding.
   112  
   113  // Bytes returns the canonical 32-byte encoding of v, according to RFC 8032,
   114  // Section 5.1.2.
   115  func (v *Point) Bytes() []byte {
   116  	// This function is outlined to make the allocations inline in the caller
   117  	// rather than happen on the heap.
   118  	var buf [32]byte
   119  	return v.bytes(&buf)
   120  }
   121  
   122  func (v *Point) bytes(buf *[32]byte) []byte {
   123  	checkInitialized(v)
   124  
   125  	var zInv, x, y field.Element
   126  	zInv.Invert(&v.z)       // zInv = 1 / Z
   127  	x.Multiply(&v.x, &zInv) // x = X / Z
   128  	y.Multiply(&v.y, &zInv) // y = Y / Z
   129  
   130  	out := copyFieldElement(buf, &y)
   131  	out[31] |= byte(x.IsNegative() << 7)
   132  	return out
   133  }
   134  
   135  var feOne = new(field.Element).One()
   136  
   137  // SetBytes sets v = x, where x is a 32-byte encoding of v. If x does not
   138  // represent a valid point on the curve, SetBytes returns nil and an error and
   139  // the receiver is unchanged. Otherwise, SetBytes returns v.
   140  //
   141  // Note that SetBytes accepts all non-canonical encodings of valid points.
   142  // That is, it follows decoding rules that match most implementations in
   143  // the ecosystem rather than RFC 8032.
   144  func (v *Point) SetBytes(x []byte) (*Point, error) {
   145  	// Specifically, the non-canonical encodings that are accepted are
   146  	//   1) the ones where the field element is not reduced (see the
   147  	//      (*field.Element).SetBytes docs) and
   148  	//   2) the ones where the x-coordinate is zero and the sign bit is set.
   149  	//
   150  	// This is consistent with crypto/ed25519/internal/edwards25519. Read more
   151  	// at https://hdevalence.ca/blog/2020-10-04-its-25519am, specifically the
   152  	// "Canonical A, R" section.
   153  
   154  	if len(x) != 32 {
   155  		return nil, errors.New("edwards25519: invalid point encoding length")
   156  	}
   157  	y := new(field.Element).SetBytes(x)
   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