| 1 |
// +build ignore |
| 2 |
// The previous line (and this one up to the warning below) is removed by the |
| 3 |
// template generator. |
| 4 |
|
| 5 |
// Code generated from ./templates/field.go.tmpl. DO NOT EDIT. |
| 6 |
|
| 7 |
package {{.Name | ToLower}} |
| 8 |
|
| 9 |
import ( |
| 10 |
"bytes" |
| 11 |
"crypto/subtle" |
| 12 |
"encoding/binary" |
| 13 |
"errors" |
| 14 |
"io" |
| 15 |
|
| 16 |
"github.com/cloudflare/circl/internal/conv" |
| 17 |
"github.com/cloudflare/circl/internal/sha3" |
| 18 |
"golang.org/x/crypto/cryptobyte" |
| 19 |
) |
| 20 |
|
| 21 |
// Size is the length in bytes of an {{.Name}} element. |
| 22 |
const Size = {{.NumUint8}} |
| 23 |
|
| 24 |
// Fp represents a prime field element as a positive integer less than Order. |
| 25 |
type Fp [{{.NumUint64}}]uint64 |
| 26 |
|
| 27 |
func (z Fp) String() string { x := z.fromMont(); return conv.Uint64Le2Hex(x[:]) } |
| 28 |
func (z Fp) Size() uint { return Size } |
| 29 |
func (z Fp) OrderRootUnity() uint { return numRootsUnity } |
| 30 |
func (z *Fp) AddAssign(x *Fp) { fiatFpAdd(z, z, x) } |
| 31 |
func (z *Fp) SubAssign(x *Fp) { fiatFpSub(z, z, x) } |
| 32 |
func (z *Fp) MulAssign(x *Fp) { fiatFpMul(z, z, x) } |
| 33 |
func (z *Fp) Add(x, y *Fp) { fiatFpAdd(z, x, y) } |
| 34 |
func (z *Fp) Sub(x, y *Fp) { fiatFpSub(z, x, y) } |
| 35 |
func (z *Fp) Mul(x, y *Fp) { fiatFpMul(z, x, y) } |
| 36 |
func (z *Fp) Sqr(x *Fp) { fiatFpSquare(z, x) } |
| 37 |
func (z *Fp) IsZero() bool { return ctEqual(z, &Fp{}) } |
| 38 |
func (z *Fp) IsOne() bool { return ctEqual(z, &rootOfUnityTwoN[0]) } |
| 39 |
func (z *Fp) IsEqual(x *Fp) bool { return ctEqual(z, x) } |
| 40 |
func (z *Fp) SetOne() { *z = rootOfUnityTwoN[0] } |
| 41 |
func (z *Fp) toMont() { fiatFpMul(z, z, &rSquare) } |
| 42 |
func (z *Fp) fromMont() (out Fp) { fiatFpMul(&out, z, &Fp{1}); return } |
| 43 |
func (z *Fp) MarshalBinary() ([]byte, error) { return conv.MarshalBinaryLen(z, Size) } |
| 44 |
func (z *Fp) UnmarshalBinary(b []byte) error { return conv.UnmarshalBinary(z, b) } |
| 45 |
func (z *Fp) Marshal(b *cryptobyte.Builder) error { |
| 46 |
var x [Size]byte |
| 47 |
for i, zi := range z.fromMont() { |
| 48 |
binary.LittleEndian.PutUint64(x[8*i:], zi) |
| 49 |
} |
| 50 |
b.AddBytes(x[:]) |
| 51 |
return nil |
| 52 |
} |
| 53 |
|
| 54 |
func (z* Fp) Unmarshal(s *cryptobyte.String) bool{ |
| 55 |
var b [Size]byte |
| 56 |
if s.CopyBytes(b[:]) { |
| 57 |
n, ok := isInRange(&b) |
| 58 |
if ok { |
| 59 |
*z = n |
| 60 |
z.toMont() |
| 61 |
return true |
| 62 |
} |
| 63 |
} |
| 64 |
return false |
| 65 |
} |
| 66 |
|
| 67 |
func (z* Fp) Random(r io.Reader) error { |
| 68 |
var b [Size]byte |
| 69 |
var ok bool |
| 70 |
for range maxNumTries { |
| 71 |
_, err := r.Read(b[:]) |
| 72 |
if err != nil { |
| 73 |
return err |
| 74 |
} |
| 75 |
|
| 76 |
*z, ok = isInRange(&b) |
| 77 |
if ok { |
| 78 |
z.toMont() |
| 79 |
return nil |
| 80 |
} |
| 81 |
} |
| 82 |
|
| 83 |
return ErrMaxNumTries |
| 84 |
} |
| 85 |
|
| 86 |
func (z* Fp) RandomSHA3(s *sha3.State) error { |
| 87 |
var b [Size]byte |
| 88 |
var ok bool |
| 89 |
for range maxNumTries { |
| 90 |
_, err := s.Read(b[:]) |
| 91 |
if err != nil { |
| 92 |
return err |
| 93 |
} |
| 94 |
|
| 95 |
*z, ok = isInRange(&b) |
| 96 |
if ok { |
| 97 |
z.toMont() |
| 98 |
return nil |
| 99 |
} |
| 100 |
} |
| 101 |
|
| 102 |
return ErrMaxNumTries |
| 103 |
} |
| 104 |
|
| 105 |
func (z* Fp) InvUint64(x uint64) { |
| 106 |
if 0 < x && x <= numInverseInt { |
| 107 |
*z = inverseInt[x-1] |
| 108 |
} else { |
| 109 |
err := z.SetUint64(x) |
| 110 |
if err != nil { |
| 111 |
panic(ErrFieldEltDecode) |
| 112 |
} |
| 113 |
z.Inv(z) |
| 114 |
} |
| 115 |
} |
| 116 |
|
| 117 |
func (z* Fp) InvTwoN(n uint) { |
| 118 |
z.SetOne() |
| 119 |
for range n { |
| 120 |
z.Mul(z, &half) |
| 121 |
} |
| 122 |
} |
| 123 |
|
| 124 |
func (z* Fp) SetUint64(n uint64) error { |
| 125 |
{{- if eq .Bits 64 }} |
| 126 |
if n >= {{.OrderVar}} { |
| 127 |
return ErrFieldEltDecode |
| 128 |
} |
| 129 |
{{- end }} |
| 130 |
*z = Fp{n} |
| 131 |
z.toMont() |
| 132 |
return nil |
| 133 |
} |
| 134 |
|
| 135 |
func (z* Fp) GetUint64() (uint64, error) { |
| 136 |
x := z.fromMont(); |
| 137 |
{{- if eq .Bits 128 }} |
| 138 |
if x[1] != 0 { |
| 139 |
return 0, ErrNumberTooLarge |
| 140 |
} |
| 141 |
{{- end }} |
| 142 |
return x[0], nil |
| 143 |
} |
| 144 |
|
| 145 |
func (z* Fp) SetRootOfUnityTwoN(n uint) { |
| 146 |
if n > numRootsUnity { |
| 147 |
panic(ErrRootsOfUnity) |
| 148 |
} |
| 149 |
*z = rootOfUnityTwoN[n] |
| 150 |
} |
| 151 |
|
| 152 |
|
| 153 |
func (z Fp) Order() []byte { |
| 154 |
var x [Size]byte |
| 155 |
binary.Write(bytes.NewBuffer(x[:0]), binary.BigEndian, []uint64{ {{.OrderVar}} }) |
| 156 |
return x[:] |
| 157 |
} |
| 158 |
|
| 159 |
func (z* Fp) sqri(x *Fp, n uint) { |
| 160 |
z.Sqr(x) |
| 161 |
for range n - 1 { |
| 162 |
z.Sqr(z) |
| 163 |
} |
| 164 |
} |
| 165 |
|
| 166 |
func fiatFpCmovznzU64(z *uint64, b, x, y uint64) { *z = (x &^ (-b)) | (y & (-b)) } |
| 167 |
|
| 168 |
func ctEqual(x, y *Fp) bool { |
| 169 |
var v uint64 |
| 170 |
for i := 0; i < len(*x); i++ { |
| 171 |
v |= (*x)[i] ^ (*y)[i] |
| 172 |
} |
| 173 |
v32 := uint32(v>>32) | uint32(v) |
| 174 |
return subtle.ConstantTimeEq(int32(v32), 0) == 1 |
| 175 |
} |
| 176 |
|
| 177 |
|
| 178 |
const ( |
| 179 |
// order is the order of the {{.Name}} field. |
| 180 |
{{.OrderConst -}} |
| 181 |
// numRootsUnity is .. |
| 182 |
numRootsUnity = {{.NumRootsUnity}} |
| 183 |
// numInverseInt{{.Name}} is the number of precomputed inverses. |
| 184 |
numInverseInt = {{.NumInverseInt}} |
| 185 |
// maxNumTries is the maximum tries for rejection sampling. |
| 186 |
maxNumTries = 10 |
| 187 |
) |
| 188 |
|
| 189 |
var ( |
| 190 |
// rSquare is R^2 mod {{.Name}}Order, where R=2^{{.Bits}} (little-endian). |
| 191 |
rSquare = Fp{ {{.RSquare}} } |
| 192 |
// half is 1/2 mod Order. |
| 193 |
half = Fp{ {{.Half}} } |
| 194 |
// rootOfUnityTwoN are the (principal) roots of unity that generate |
| 195 |
// a multiplicative group of order 2^n. |
| 196 |
// i.e., rootOfUnityTwoN[i] generates a group of order 2^i. |
| 197 |
// Thus, by definition, |
| 198 |
// - rootOfUnityTwoN[0] = One |
| 199 |
// - rootOfUnityTwoN[numRoots] = Generator |
| 200 |
// Constants are encoded in Montgomery domain (little-endian). |
| 201 |
rootOfUnityTwoN = [numRootsUnity + 1]Fp{ |
| 202 |
{{.RootsOfUnity}} |
| 203 |
} |
| 204 |
// inverseInt has the inverse of the first `numInverseInt` integers. |
| 205 |
inverseInt = [numInverseInt]Fp{ |
| 206 |
{{.InverseInt}} |
| 207 |
} |
| 208 |
) |
| 209 |
|
| 210 |
|
| 211 |
var ( |
| 212 |
ErrMatchLen = errors.New("inputs mismatched length") |
| 213 |
ErrFieldEltDecode = errors.New("incorrect field element value") |
| 214 |
ErrNumberTooLarge = errors.New("number of bits is not enough to represent the number") |
| 215 |
ErrMaxNumTries = errors.New("random rejection sampling reached maximum number of tries") |
| 216 |
ErrRootsOfUnity = errors.New("Fp has no roots of unity of order larger than 2^{{.NumRootsUnity}}") |
| 217 |
) |