p521.go

Documentation: crypto/elliptic/internal/fiat

     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 fiat implements prime order fields using formally verified algorithms
     6  // from the Fiat Cryptography project.
     7  package fiat
     8  
     9  import (
    10  	"crypto/subtle"
    11  	"errors"
    12  )
    13  
    14  // P521Element is an integer modulo 2^521 - 1.
    15  //
    16  // The zero value is a valid zero element.
    17  type P521Element struct {
    18  	// This element has the following bounds, which are tighter than
    19  	// the output bounds of some operations. Those operations must be
    20  	// followed by a carry.
    21  	//
    22  	// [0x0 ~> 0x400000000000000], [0x0 ~> 0x400000000000000], [0x0 ~> 0x400000000000000],
    23  	// [0x0 ~> 0x400000000000000], [0x0 ~> 0x400000000000000], [0x0 ~> 0x400000000000000],
    24  	// [0x0 ~> 0x400000000000000], [0x0 ~> 0x400000000000000], [0x0 ~> 0x200000000000000]
    25  	x [9]uint64
    26  }
    27  
    28  // One sets e = 1, and returns e.
    29  func (e *P521Element) One() *P521Element {
    30  	*e = P521Element{}
    31  	e.x[0] = 1
    32  	return e
    33  }
    34  
    35  // Equal returns 1 if e == t, and zero otherwise.
    36  func (e *P521Element) Equal(t *P521Element) int {
    37  	eBytes := e.Bytes()
    38  	tBytes := t.Bytes()
    39  	return subtle.ConstantTimeCompare(eBytes, tBytes)
    40  }
    41  
    42  var p521ZeroEncoding = new(P521Element).Bytes()
    43  
    44  // IsZero returns 1 if e == 0, and zero otherwise.
    45  func (e *P521Element) IsZero() int {
    46  	eBytes := e.Bytes()
    47  	return subtle.ConstantTimeCompare(eBytes, p521ZeroEncoding)
    48  }
    49  
    50  // Set sets e = t, and returns e.
    51  func (e *P521Element) Set(t *P521Element) *P521Element {
    52  	e.x = t.x
    53  	return e
    54  }
    55  
    56  // Bytes returns the 66-byte little-endian encoding of e.
    57  func (e *P521Element) Bytes() []byte {
    58  	// This function must be inlined to move the allocation to the parent and
    59  	// save it from escaping to the heap.
    60  	var out [66]byte
    61  	p521ToBytes(&out, &e.x)
    62  	return out[:]
    63  }
    64  
    65  // SetBytes sets e = v, where v is a little-endian 66-byte encoding, and returns
    66  // e. If v is not 66 bytes or it encodes a value higher than 2^521 - 1, SetBytes
    67  // returns nil and an error, and e is unchanged.
    68  func (e *P521Element) SetBytes(v []byte) (*P521Element, error) {
    69  	if len(v) != 66 || v[65] > 1 {
    70  		return nil, errors.New("invalid P-521 field encoding")
    71  	}
    72  	var in [66]byte
    73  	copy(in[:], v)
    74  	p521FromBytes(&e.x, &in)
    75  	return e, nil
    76  }
    77  
    78  // Add sets e = t1 + t2, and returns e.
    79  func (e *P521Element) Add(t1, t2 *P521Element) *P521Element {
    80  	p521Add(&e.x, &t1.x, &t2.x)
    81  	p521Carry(&e.x, &e.x)
    82  	return e
    83  }
    84  
    85  // Sub sets e = t1 - t2, and returns e.
    86  func (e *P521Element) Sub(t1, t2 *P521Element) *P521Element {
    87  	p521Sub(&e.x, &t1.x, &t2.x)
    88  	p521Carry(&e.x, &e.x)
    89  	return e
    90  }
    91  
    92  // Mul sets e = t1 * t2, and returns e.
    93  func (e *P521Element) Mul(t1, t2 *P521Element) *P521Element {
    94  	p521CarryMul(&e.x, &t1.x, &t2.x)
    95  	return e
    96  }
    97  
    98  // Square sets e = t * t, and returns e.
    99  func (e *P521Element) Square(t *P521Element) *P521Element {
   100  	p521CarrySquare(&e.x, &t.x)
   101  	return e
   102  }
   103  
   104  // Select sets e to a if cond == 1, and to b if cond == 0.
   105  func (v *P521Element) Select(a, b *P521Element, cond int) *P521Element {
   106  	p521Selectznz(&v.x, p521Uint1(cond), &b.x, &a.x)
   107  	return v
   108  }
   109  
   110  // Invert sets e = 1/t, and returns e.
   111  //
   112  // If t == 0, Invert returns e = 0.
   113  func (e *P521Element) Invert(t *P521Element) *P521Element {
   114  	// Inversion is implemented as exponentiation with exponent p − 2.
   115  	// The sequence of multiplications and squarings was generated with
   116  	// github.com/mmcloughlin/addchain v0.2.0.
   117  
   118  	var t1, t2 = new(P521Element), new(P521Element)
   119  
   120  	// _10 = 2 * 1
   121  	t1.Square(t)
   122  
   123  	// _11 = 1 + _10
   124  	t1.Mul(t, t1)
   125  
   126  	// _1100 = _11 << 2
   127  	t2.Square(t1)
   128  	t2.Square(t2)
   129  
   130  	// _1111 = _11 + _1100
   131  	t1.Mul(t1, t2)
   132  
   133  	// _11110000 = _1111 << 4
   134  	t2.Square(t1)
   135  	for i := 0; i < 3; i++ {
   136  		t2.Square(t2)
   137  	}
   138  
   139  	// _11111111 = _1111 + _11110000
   140  	t1.Mul(t1, t2)
   141  
   142  	// x16 = _11111111<<8 + _11111111
   143  	t2.Square(t1)
   144  	for i := 0; i < 7; i++ {
   145  		t2.Square(t2)
   146  	}
   147  	t1.Mul(t1, t2)
   148  
   149  	// x32 = x16<<16 + x16
   150  	t2.Square(t1)
   151  	for i := 0; i < 15; i++ {
   152  		t2.Square(t2)
   153  	}
   154  	t1.Mul(t1, t2)
   155  
   156  	// x64 = x32<<32 + x32
   157  	t2.Square(t1)
   158  	for i := 0; i < 31; i++ {
   159  		t2.Square(t2)
   160  	}
   161  	t1.Mul(t1, t2)
   162  
   163  	// x65 = 2*x64 + 1
   164  	t2.Square(t1)
   165  	t2.Mul(t2, t)
   166  
   167  	// x129 = x65<<64 + x64
   168  	for i := 0; i < 64; i++ {
   169  		t2.Square(t2)
   170  	}
   171  	t1.Mul(t1, t2)
   172  
   173  	// x130 = 2*x129 + 1
   174  	t2.Square(t1)
   175  	t2.Mul(t2, t)
   176  
   177  	// x259 = x130<<129 + x129
   178  	for i := 0; i < 129; i++ {
   179  		t2.Square(t2)
   180  	}
   181  	t1.Mul(t1, t2)
   182  
   183  	// x260 = 2*x259 + 1
   184  	t2.Square(t1)
   185  	t2.Mul(t2, t)
   186  
   187  	// x519 = x260<<259 + x259
   188  	for i := 0; i < 259; i++ {
   189  		t2.Square(t2)
   190  	}
   191  	t1.Mul(t1, t2)
   192  
   193  	// return x519<<2 + 1
   194  	t1.Square(t1)
   195  	t1.Square(t1)
   196  	return e.Mul(t1, t)
   197  }
   198
View as plain text