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/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  	// Make the type not comparable (i.e. used with == or as a map key), as
    30  	// equivalent points can be represented by different Go values.
    31  	_ incomparable
    32  
    33  	// The point is internally represented in extended coordinates (X, Y, Z, T)
    34  	// where x = X/Z, y = Y/Z, and xy = T/Z per https://eprint.iacr.org/2008/522.
    35  	x, y, z, t field.Element
    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  	// Read more at https://hdevalence.ca/blog/2020-10-04-its-25519am,
   151  	// specifically the "Canonical A, R" section.
   152  
   153  	y, err := new(field.Element).SetBytes(x)
   154  	if err != nil {
   155  		return nil, errors.New("edwards25519: invalid point encoding length")
   156  	}
   157  
   158  	// -x² + y² = 1 + dx²y²
   159  	// x² + dx²y² = x²(dy² + 1) = y² - 1
   160  	// x² = (y² - 1) / (dy² + 1)
   161  
   162  	// u = y² - 1
   163  	y2 := new(field.Element).Square(y)
   164  	u := new(field.Element).Subtract(y2, feOne)
   165  
   166  	// v = dy² + 1
   167  	vv := new(field.Element).Multiply(y2, d)
   168  	vv = vv.Add(vv, feOne)
   169  
   170  	// x = +√(u/v)
   171  	xx, wasSquare := new(field.Element).SqrtRatio(u, vv)
   172  	if wasSquare == 0 {
   173  		return nil, errors.New("edwards25519: invalid point encoding")
   174  	}
   175  
   176  	// Select the negative square root if the sign bit is set.
   177  	xxNeg := new(field.Element).Negate(xx)
   178  	xx = xx.Select(xxNeg, xx, int(x[31]>>7))
   179  
   180  	v.x.Set(xx)
   181  	v.y.Set(y)
   182  	v.z.One()
   183  	v.t.Multiply(xx, y) // xy = T / Z
   184  
   185  	return v, nil
   186  }
   187  
   188  func copyFieldElement(buf *[32]byte, v *field.Element) []byte {
   189  	copy(buf[:], v.Bytes())
   190  	return buf[:]
   191  }
   192  
   193  // Conversions.
   194  
   195  func (v *projP2) FromP1xP1(p *projP1xP1) *projP2 {
   196  	v.X.Multiply(&p.X, &p.T)
   197  	v.Y.Multiply(&p.Y, &p.Z)
   198  	v.Z.Multiply(&p.Z, &p.T)
   199  	return v
   200  }
   201  
   202  func (v *projP2) FromP3(p *Point) *projP2 {
   203  	v.X.Set(&p.x)
   204  	v.Y.Set(&p.y)
   205  	v.Z.Set(&p.z)
   206  	return v
   207  }
   208  
   209  func (v *Point) fromP1xP1(p *projP1xP1) *Point {
   210  	v.x.Multiply(&p.X, &p.T)
   211  	v.y.Multiply(&p.Y, &p.Z)
   212  	v.z.Multiply(&p.Z, &p.T)
   213  	v.t.Multiply(&p.X, &p.Y)
   214  	return v
   215  }
   216  
   217  func (v *Point) fromP2(p *projP2) *Point {
   218  	v.x.Multiply(&p.X, &p.Z)
   219  	v.y.Multiply(&p.Y, &p.Z)
   220  	v.z.Square(&p.Z)
   221  	v.t.Multiply(&p.X, &p.Y)
   222  	return v
   223  }
   224  
   225  // d is a constant in the curve equation.
   226  var d, _ = new(field.Element).SetBytes([]byte{
   227  	0xa3, 0x78, 0x59, 0x13, 0xca, 0x4d, 0xeb, 0x75,
   228  	0xab, 0xd8, 0x41, 0x41, 0x4d, 0x0a, 0x70, 0x00,
   229  	0x98, 0xe8, 0x79, 0x77, 0x79, 0x40, 0xc7, 0x8c,
   230  	0x73, 0xfe, 0x6f, 0x2b, 0xee, 0x6c, 0x03, 0x52})
   231  var d2 = new(field.Element).Add(d, d)
   232  
   233  func (v *projCached) FromP3(p *Point) *projCached {
   234  	v.YplusX.Add(&p.y, &p.x)
   235  	v.YminusX.Subtract(&p.y, &p.x)
   236  	v.Z.Set(&p.z)
   237  	v.T2d.Multiply(&p.t, d2)
   238  	return v
   239  }
   240  
   241  func (v *affineCached) FromP3(p *Point) *affineCached {
   242  	v.YplusX.Add(&p.y, &p.x)
   243  	v.YminusX.Subtract(&p.y, &p.x)
   244  	v.T2d.Multiply(&p.t, d2)
   245  
   246  	var invZ field.Element
   247  	invZ.Invert(&p.z)
   248  	v.YplusX.Multiply(&v.YplusX, &invZ)
   249  	v.YminusX.Multiply(&v.YminusX, &invZ)
   250  	v.T2d.Multiply(&v.T2d, &invZ)
   251  	return v
   252  }
   253  
   254  // (Re)addition and subtraction.
   255  
   256  // Add sets v = p + q, and returns v.
   257  func (v *Point) Add(p, q *Point) *Point {
   258  	checkInitialized(p, q)
   259  	qCached := new(projCached).FromP3(q)
   260  	result := new(projP1xP1).Add(p, qCached)
   261  	return v.fromP1xP1(result)
   262  }
   263  
   264  // Subtract sets v = p - q, and returns v.
   265  func (v *Point) Subtract(p, q *Point) *Point {
   266  	checkInitialized(p, q)
   267  	qCached := new(projCached).FromP3(q)
   268  	result := new(projP1xP1).Sub(p, qCached)
   269  	return v.fromP1xP1(result)
   270  }
   271  
   272  func (v *projP1xP1) Add(p *Point, q *projCached) *projP1xP1 {
   273  	var YplusX, YminusX, PP, MM, TT2d, ZZ2 field.Element
   274  
   275  	YplusX.Add(&p.y, &p.x)
   276  	YminusX.Subtract(&p.y, &p.x)
   277  
   278  	PP.Multiply(&YplusX, &q.YplusX)
   279  	MM.Multiply(&YminusX, &q.YminusX)
   280  	TT2d.Multiply(&p.t, &q.T2d)
   281  	ZZ2.Multiply(&p.z, &q.Z)
   282  
   283  	ZZ2.Add(&ZZ2, &ZZ2)
   284  
   285  	v.X.Subtract(&PP, &MM)
   286  	v.Y.Add(&PP, &MM)
   287  	v.Z.Add(&ZZ2, &TT2d)
   288  	v.T.Subtract(&ZZ2, &TT2d)
   289  	return v
   290  }
   291  
   292  func (v *projP1xP1) Sub(p *Point, q *projCached) *projP1xP1 {
   293  	var YplusX, YminusX, PP, MM, TT2d, ZZ2 field.Element
   294  
   295  	YplusX.Add(&p.y, &p.x)
   296  	YminusX.Subtract(&p.y, &p.x)
   297  
   298  	PP.Multiply(&YplusX, &q.YminusX) // flipped sign
   299  	MM.Multiply(&YminusX, &q.YplusX) // flipped sign
   300  	TT2d.Multiply(&p.t, &q.T2d)
   301  	ZZ2.Multiply(&p.z, &q.Z)
   302  
   303  	ZZ2.Add(&ZZ2, &ZZ2)
   304  
   305  	v.X.Subtract(&PP, &MM)
   306  	v.Y.Add(&PP, &MM)
   307  	v.Z.Subtract(&ZZ2, &TT2d) // flipped sign
   308  	v.T.Add(&ZZ2, &TT2d)      // flipped sign
   309  	return v
   310  }
   311  
   312  func (v *projP1xP1) AddAffine(p *Point, q *affineCached) *projP1xP1 {
   313  	var YplusX, YminusX, PP, MM, TT2d, Z2 field.Element
   314  
   315  	YplusX.Add(&p.y, &p.x)
   316  	YminusX.Subtract(&p.y, &p.x)
   317  
   318  	PP.Multiply(&YplusX, &q.YplusX)
   319  	MM.Multiply(&YminusX, &q.YminusX)
   320  	TT2d.Multiply(&p.t, &q.T2d)
   321  
   322  	Z2.Add(&p.z, &p.z)
   323  
   324  	v.X.Subtract(&PP, &MM)
   325  	v.Y.Add(&PP, &MM)
   326  	v.Z.Add(&Z2, &TT2d)
   327  	v.T.Subtract(&Z2, &TT2d)
   328  	return v
   329  }
   330  
   331  func (v *projP1xP1) SubAffine(p *Point, q *affineCached) *projP1xP1 {
   332  	var YplusX, YminusX, PP, MM, TT2d, Z2 field.Element
   333  
   334  	YplusX.Add(&p.y, &p.x)
   335  	YminusX.Subtract(&p.y, &p.x)
   336  
   337  	PP.Multiply(&YplusX, &q.YminusX) // flipped sign
   338  	MM.Multiply(&YminusX, &q.YplusX) // flipped sign
   339  	TT2d.Multiply(&p.t, &q.T2d)
   340  
   341  	Z2.Add(&p.z, &p.z)
   342  
   343  	v.X.Subtract(&PP, &MM)
   344  	v.Y.Add(&PP, &MM)
   345  	v.Z.Subtract(&Z2, &TT2d) // flipped sign
   346  	v.T.Add(&Z2, &TT2d)      // flipped sign
   347  	return v
   348  }
   349  
   350  // Doubling.
   351  
   352  func (v *projP1xP1) Double(p *projP2) *projP1xP1 {
   353  	var XX, YY, ZZ2, XplusYsq field.Element
   354  
   355  	XX.Square(&p.X)
   356  	YY.Square(&p.Y)
   357  	ZZ2.Square(&p.Z)
   358  	ZZ2.Add(&ZZ2, &ZZ2)
   359  	XplusYsq.Add(&p.X, &p.Y)
   360  	XplusYsq.Square(&XplusYsq)
   361  
   362  	v.Y.Add(&YY, &XX)
   363  	v.Z.Subtract(&YY, &XX)
   364  
   365  	v.X.Subtract(&XplusYsq, &v.Y)
   366  	v.T.Subtract(&ZZ2, &v.Z)
   367  	return v
   368  }
   369  
   370  // Negation.
   371  
   372  // Negate sets v = -p, and returns v.
   373  func (v *Point) Negate(p *Point) *Point {
   374  	checkInitialized(p)
   375  	v.x.Negate(&p.x)
   376  	v.y.Set(&p.y)
   377  	v.z.Set(&p.z)
   378  	v.t.Negate(&p.t)
   379  	return v
   380  }
   381  
   382  // Equal returns 1 if v is equivalent to u, and 0 otherwise.
   383  func (v *Point) Equal(u *Point) int {
   384  	checkInitialized(v, u)
   385  
   386  	var t1, t2, t3, t4 field.Element
   387  	t1.Multiply(&v.x, &u.z)
   388  	t2.Multiply(&u.x, &v.z)
   389  	t3.Multiply(&v.y, &u.z)
   390  	t4.Multiply(&u.y, &v.z)
   391  
   392  	return t1.Equal(&t2) & t3.Equal(&t4)
   393  }
   394  
   395  // Constant-time operations
   396  
   397  // Select sets v to a if cond == 1 and to b if cond == 0.
   398  func (v *projCached) Select(a, b *projCached, cond int) *projCached {
   399  	v.YplusX.Select(&a.YplusX, &b.YplusX, cond)
   400  	v.YminusX.Select(&a.YminusX, &b.YminusX, cond)
   401  	v.Z.Select(&a.Z, &b.Z, cond)
   402  	v.T2d.Select(&a.T2d, &b.T2d, cond)
   403  	return v
   404  }
   405  
   406  // Select sets v to a if cond == 1 and to b if cond == 0.
   407  func (v *affineCached) Select(a, b *affineCached, cond int) *affineCached {
   408  	v.YplusX.Select(&a.YplusX, &b.YplusX, cond)
   409  	v.YminusX.Select(&a.YminusX, &b.YminusX, cond)
   410  	v.T2d.Select(&a.T2d, &b.T2d, cond)
   411  	return v
   412  }
   413  
   414  // CondNeg negates v if cond == 1 and leaves it unchanged if cond == 0.
   415  func (v *projCached) CondNeg(cond int) *projCached {
   416  	v.YplusX.Swap(&v.YminusX, cond)
   417  	v.T2d.Select(new(field.Element).Negate(&v.T2d), &v.T2d, cond)
   418  	return v
   419  }
   420  
   421  // CondNeg negates v if cond == 1 and leaves it unchanged if cond == 0.
   422  func (v *affineCached) CondNeg(cond int) *affineCached {
   423  	v.YplusX.Swap(&v.YminusX, cond)
   424  	v.T2d.Select(new(field.Element).Negate(&v.T2d), &v.T2d, cond)
   425  	return v
   426  }
   427
View as plain text