p224.go

     1  // Copyright 2021 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 nistec
     6  
     7  import (
     8  	"crypto/elliptic/internal/fiat"
     9  	"crypto/subtle"
    10  	"errors"
    11  )
    12  
    13  var p224B, _ = new(fiat.P224Element).SetBytes([]byte{0xb4, 0x05, 0x0a, 0x85,
    14  	0x0c, 0x04, 0xb3, 0xab, 0xf5, 0x41, 0x32, 0x56, 0x50, 0x44, 0xb0, 0xb7,
    15  	0xd7, 0xbf, 0xd8, 0xba, 0x27, 0x0b, 0x39, 0x43, 0x23, 0x55, 0xff, 0xb4})
    16  
    17  var p224G, _ = NewP224Point().SetBytes([]byte{0x04,
    18  	0xb7, 0x0e, 0x0c, 0xbd, 0x6b, 0xb4, 0xbf, 0x7f, 0x32, 0x13, 0x90, 0xb9,
    19  	0x4a, 0x03, 0xc1, 0xd3, 0x56, 0xc2, 0x11, 0x22, 0x34, 0x32, 0x80, 0xd6,
    20  	0x11, 0x5c, 0x1d, 0x21, 0xbd, 0x37, 0x63, 0x88, 0xb5, 0xf7, 0x23, 0xfb,
    21  	0x4c, 0x22, 0xdf, 0xe6, 0xcd, 0x43, 0x75, 0xa0, 0x5a, 0x07, 0x47, 0x64,
    22  	0x44, 0xd5, 0x81, 0x99, 0x85, 0x0, 0x7e, 0x34})
    23  
    24  const p224ElementLength = 28
    25  
    26  // P224Point is a P-224 point. The zero value is NOT valid.
    27  type P224Point struct {
    28  	// The point is represented in projective coordinates (X:Y:Z),
    29  	// where x = X/Z and y = Y/Z.
    30  	x, y, z *fiat.P224Element
    31  }
    32  
    33  // NewP224Point returns a new P224Point representing the point at infinity point.
    34  func NewP224Point() *P224Point {
    35  	return &P224Point{
    36  		x: new(fiat.P224Element),
    37  		y: new(fiat.P224Element).One(),
    38  		z: new(fiat.P224Element),
    39  	}
    40  }
    41  
    42  // NewP224Generator returns a new P224Point set to the canonical generator.
    43  func NewP224Generator() *P224Point {
    44  	return (&P224Point{
    45  		x: new(fiat.P224Element),
    46  		y: new(fiat.P224Element),
    47  		z: new(fiat.P224Element),
    48  	}).Set(p224G)
    49  }
    50  
    51  // Set sets p = q and returns p.
    52  func (p *P224Point) Set(q *P224Point) *P224Point {
    53  	p.x.Set(q.x)
    54  	p.y.Set(q.y)
    55  	p.z.Set(q.z)
    56  	return p
    57  }
    58  
    59  // SetBytes sets p to the compressed, uncompressed, or infinity value encoded in
    60  // b, as specified in SEC 1, Version 2.0, Section 2.3.4. If the point is not on
    61  // the curve, it returns nil and an error, and the receiver is unchanged.
    62  // Otherwise, it returns p.
    63  func (p *P224Point) SetBytes(b []byte) (*P224Point, error) {
    64  	switch {
    65  	// Point at infinity.
    66  	case len(b) == 1 && b[0] == 0:
    67  		return p.Set(NewP224Point()), nil
    68  
    69  	// Uncompressed form.
    70  	case len(b) == 1+2*p224ElementLength && b[0] == 4:
    71  		x, err := new(fiat.P224Element).SetBytes(b[1 : 1+p224ElementLength])
    72  		if err != nil {
    73  			return nil, err
    74  		}
    75  		y, err := new(fiat.P224Element).SetBytes(b[1+p224ElementLength:])
    76  		if err != nil {
    77  			return nil, err
    78  		}
    79  		if err := p224CheckOnCurve(x, y); err != nil {
    80  			return nil, err
    81  		}
    82  		p.x.Set(x)
    83  		p.y.Set(y)
    84  		p.z.One()
    85  		return p, nil
    86  
    87  	// Compressed form
    88  	case len(b) == 1+p224ElementLength && b[0] == 0:
    89  		return nil, errors.New("unimplemented") // TODO(filippo)
    90  
    91  	default:
    92  		return nil, errors.New("invalid P224 point encoding")
    93  	}
    94  }
    95  
    96  func p224CheckOnCurve(x, y *fiat.P224Element) error {
    97  	// x³ - 3x + b.
    98  	x3 := new(fiat.P224Element).Square(x)
    99  	x3.Mul(x3, x)
   100  
   101  	threeX := new(fiat.P224Element).Add(x, x)
   102  	threeX.Add(threeX, x)
   103  
   104  	x3.Sub(x3, threeX)
   105  	x3.Add(x3, p224B)
   106  
   107  	// y² = x³ - 3x + b
   108  	y2 := new(fiat.P224Element).Square(y)
   109  
   110  	if x3.Equal(y2) != 1 {
   111  		return errors.New("P224 point not on curve")
   112  	}
   113  	return nil
   114  }
   115  
   116  // Bytes returns the uncompressed or infinity encoding of p, as specified in
   117  // SEC 1, Version 2.0, Section 2.3.3. Note that the encoding of the point at
   118  // infinity is shorter than all other encodings.
   119  func (p *P224Point) Bytes() []byte {
   120  	// This function is outlined to make the allocations inline in the caller
   121  	// rather than happen on the heap.
   122  	var out [133]byte
   123  	return p.bytes(&out)
   124  }
   125  
   126  func (p *P224Point) bytes(out *[133]byte) []byte {
   127  	if p.z.IsZero() == 1 {
   128  		return append(out[:0], 0)
   129  	}
   130  
   131  	zinv := new(fiat.P224Element).Invert(p.z)
   132  	xx := new(fiat.P224Element).Mul(p.x, zinv)
   133  	yy := new(fiat.P224Element).Mul(p.y, zinv)
   134  
   135  	buf := append(out[:0], 4)
   136  	buf = append(buf, xx.Bytes()...)
   137  	buf = append(buf, yy.Bytes()...)
   138  	return buf
   139  }
   140  
   141  // Add sets q = p1 + p2, and returns q. The points may overlap.
   142  func (q *P224Point) Add(p1, p2 *P224Point) *P224Point {
   143  	// Complete addition formula for a = -3 from "Complete addition formulas for
   144  	// prime order elliptic curves" (https://eprint.iacr.org/2015/1060), §A.2.
   145  
   146  	t0 := new(fiat.P224Element).Mul(p1.x, p2.x) // t0 := X1 * X2
   147  	t1 := new(fiat.P224Element).Mul(p1.y, p2.y) // t1 := Y1 * Y2
   148  	t2 := new(fiat.P224Element).Mul(p1.z, p2.z) // t2 := Z1 * Z2
   149  	t3 := new(fiat.P224Element).Add(p1.x, p1.y) // t3 := X1 + Y1
   150  	t4 := new(fiat.P224Element).Add(p2.x, p2.y) // t4 := X2 + Y2
   151  	t3.Mul(t3, t4)                              // t3 := t3 * t4
   152  	t4.Add(t0, t1)                              // t4 := t0 + t1
   153  	t3.Sub(t3, t4)                              // t3 := t3 - t4
   154  	t4.Add(p1.y, p1.z)                          // t4 := Y1 + Z1
   155  	x3 := new(fiat.P224Element).Add(p2.y, p2.z) // X3 := Y2 + Z2
   156  	t4.Mul(t4, x3)                              // t4 := t4 * X3
   157  	x3.Add(t1, t2)                              // X3 := t1 + t2
   158  	t4.Sub(t4, x3)                              // t4 := t4 - X3
   159  	x3.Add(p1.x, p1.z)                          // X3 := X1 + Z1
   160  	y3 := new(fiat.P224Element).Add(p2.x, p2.z) // Y3 := X2 + Z2
   161  	x3.Mul(x3, y3)                              // X3 := X3 * Y3
   162  	y3.Add(t0, t2)                              // Y3 := t0 + t2
   163  	y3.Sub(x3, y3)                              // Y3 := X3 - Y3
   164  	z3 := new(fiat.P224Element).Mul(p224B, t2)  // Z3 := b * t2
   165  	x3.Sub(y3, z3)                              // X3 := Y3 - Z3
   166  	z3.Add(x3, x3)                              // Z3 := X3 + X3
   167  	x3.Add(x3, z3)                              // X3 := X3 + Z3
   168  	z3.Sub(t1, x3)                              // Z3 := t1 - X3
   169  	x3.Add(t1, x3)                              // X3 := t1 + X3
   170  	y3.Mul(p224B, y3)                           // Y3 := b * Y3
   171  	t1.Add(t2, t2)                              // t1 := t2 + t2
   172  	t2.Add(t1, t2)                              // t2 := t1 + t2
   173  	y3.Sub(y3, t2)                              // Y3 := Y3 - t2
   174  	y3.Sub(y3, t0)                              // Y3 := Y3 - t0
   175  	t1.Add(y3, y3)                              // t1 := Y3 + Y3
   176  	y3.Add(t1, y3)                              // Y3 := t1 + Y3
   177  	t1.Add(t0, t0)                              // t1 := t0 + t0
   178  	t0.Add(t1, t0)                              // t0 := t1 + t0
   179  	t0.Sub(t0, t2)                              // t0 := t0 - t2
   180  	t1.Mul(t4, y3)                              // t1 := t4 * Y3
   181  	t2.Mul(t0, y3)                              // t2 := t0 * Y3
   182  	y3.Mul(x3, z3)                              // Y3 := X3 * Z3
   183  	y3.Add(y3, t2)                              // Y3 := Y3 + t2
   184  	x3.Mul(t3, x3)                              // X3 := t3 * X3
   185  	x3.Sub(x3, t1)                              // X3 := X3 - t1
   186  	z3.Mul(t4, z3)                              // Z3 := t4 * Z3
   187  	t1.Mul(t3, t0)                              // t1 := t3 * t0
   188  	z3.Add(z3, t1)                              // Z3 := Z3 + t1
   189  
   190  	q.x.Set(x3)
   191  	q.y.Set(y3)
   192  	q.z.Set(z3)
   193  	return q
   194  }
   195  
   196  // Double sets q = p + p, and returns q. The points may overlap.
   197  func (q *P224Point) Double(p *P224Point) *P224Point {
   198  	// Complete addition formula for a = -3 from "Complete addition formulas for
   199  	// prime order elliptic curves" (https://eprint.iacr.org/2015/1060), §A.2.
   200  
   201  	t0 := new(fiat.P224Element).Square(p.x)    // t0 := X ^ 2
   202  	t1 := new(fiat.P224Element).Square(p.y)    // t1 := Y ^ 2
   203  	t2 := new(fiat.P224Element).Square(p.z)    // t2 := Z ^ 2
   204  	t3 := new(fiat.P224Element).Mul(p.x, p.y)  // t3 := X * Y
   205  	t3.Add(t3, t3)                             // t3 := t3 + t3
   206  	z3 := new(fiat.P224Element).Mul(p.x, p.z)  // Z3 := X * Z
   207  	z3.Add(z3, z3)                             // Z3 := Z3 + Z3
   208  	y3 := new(fiat.P224Element).Mul(p224B, t2) // Y3 := b * t2
   209  	y3.Sub(y3, z3)                             // Y3 := Y3 - Z3
   210  	x3 := new(fiat.P224Element).Add(y3, y3)    // X3 := Y3 + Y3
   211  	y3.Add(x3, y3)                             // Y3 := X3 + Y3
   212  	x3.Sub(t1, y3)                             // X3 := t1 - Y3
   213  	y3.Add(t1, y3)                             // Y3 := t1 + Y3
   214  	y3.Mul(x3, y3)                             // Y3 := X3 * Y3
   215  	x3.Mul(x3, t3)                             // X3 := X3 * t3
   216  	t3.Add(t2, t2)                             // t3 := t2 + t2
   217  	t2.Add(t2, t3)                             // t2 := t2 + t3
   218  	z3.Mul(p224B, z3)                          // Z3 := b * Z3
   219  	z3.Sub(z3, t2)                             // Z3 := Z3 - t2
   220  	z3.Sub(z3, t0)                             // Z3 := Z3 - t0
   221  	t3.Add(z3, z3)                             // t3 := Z3 + Z3
   222  	z3.Add(z3, t3)                             // Z3 := Z3 + t3
   223  	t3.Add(t0, t0)                             // t3 := t0 + t0
   224  	t0.Add(t3, t0)                             // t0 := t3 + t0
   225  	t0.Sub(t0, t2)                             // t0 := t0 - t2
   226  	t0.Mul(t0, z3)                             // t0 := t0 * Z3
   227  	y3.Add(y3, t0)                             // Y3 := Y3 + t0
   228  	t0.Mul(p.y, p.z)                           // t0 := Y * Z
   229  	t0.Add(t0, t0)                             // t0 := t0 + t0
   230  	z3.Mul(t0, z3)                             // Z3 := t0 * Z3
   231  	x3.Sub(x3, z3)                             // X3 := X3 - Z3
   232  	z3.Mul(t0, t1)                             // Z3 := t0 * t1
   233  	z3.Add(z3, z3)                             // Z3 := Z3 + Z3
   234  	z3.Add(z3, z3)                             // Z3 := Z3 + Z3
   235  
   236  	q.x.Set(x3)
   237  	q.y.Set(y3)
   238  	q.z.Set(z3)
   239  	return q
   240  }
   241  
   242  // Select sets q to p1 if cond == 1, and to p2 if cond == 0.
   243  func (q *P224Point) Select(p1, p2 *P224Point, cond int) *P224Point {
   244  	q.x.Select(p1.x, p2.x, cond)
   245  	q.y.Select(p1.y, p2.y, cond)
   246  	q.z.Select(p1.z, p2.z, cond)
   247  	return q
   248  }
   249  
   250  // ScalarMult sets p = scalar * q, and returns p.
   251  func (p *P224Point) ScalarMult(q *P224Point, scalar []byte) *P224Point {
   252  	// table holds the first 16 multiples of q. The explicit newP224Point calls
   253  	// get inlined, letting the allocations live on the stack.
   254  	var table = [16]*P224Point{
   255  		NewP224Point(), NewP224Point(), NewP224Point(), NewP224Point(),
   256  		NewP224Point(), NewP224Point(), NewP224Point(), NewP224Point(),
   257  		NewP224Point(), NewP224Point(), NewP224Point(), NewP224Point(),
   258  		NewP224Point(), NewP224Point(), NewP224Point(), NewP224Point(),
   259  	}
   260  	for i := 1; i < 16; i++ {
   261  		table[i].Add(table[i-1], q)
   262  	}
   263  
   264  	// Instead of doing the classic double-and-add chain, we do it with a
   265  	// four-bit window: we double four times, and then add [0-15]P.
   266  	t := NewP224Point()
   267  	p.Set(NewP224Point())
   268  	for _, byte := range scalar {
   269  		p.Double(p)
   270  		p.Double(p)
   271  		p.Double(p)
   272  		p.Double(p)
   273  
   274  		for i := uint8(0); i < 16; i++ {
   275  			cond := subtle.ConstantTimeByteEq(byte>>4, i)
   276  			t.Select(table[i], t, cond)
   277  		}
   278  		p.Add(p, t)
   279  
   280  		p.Double(p)
   281  		p.Double(p)
   282  		p.Double(p)
   283  		p.Double(p)
   284  
   285  		for i := uint8(0); i < 16; i++ {
   286  			cond := subtle.ConstantTimeByteEq(byte&0b1111, i)
   287  			t.Select(table[i], t, cond)
   288  		}
   289  		p.Add(p, t)
   290  	}
   291  
   292  	return p
   293  }
   294
View as plain text