Debian Codegraph @

vdaf/prio3/arith/templates/fp.go.tmpl

raw
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 )