1
2
3
4
5
6
7 package main
8
9 import (
10 "bytes"
11 "go/format"
12 "io"
13 "log"
14 "os"
15 "os/exec"
16 "text/template"
17 )
18
19 var curves = []struct {
20 Element string
21 Prime string
22 Prefix string
23 FiatType string
24 BytesLen int
25 }{
26 {
27 Element: "P224Element",
28 Prime: "2^224 - 2^96 + 1",
29 Prefix: "p224",
30 FiatType: "[4]uint64",
31 BytesLen: 28,
32 },
33
34
35
36
37
38
39
40
41
42 {
43 Element: "P384Element",
44 Prime: "2^384 - 2^128 - 2^96 + 2^32 - 1",
45 Prefix: "p384",
46 FiatType: "[6]uint64",
47 BytesLen: 48,
48 },
49
50
51
52 {
53 Element: "P521Element",
54 Prime: "2^521 - 1",
55 Prefix: "p521",
56 FiatType: "[9]uint64",
57 BytesLen: 66,
58 },
59 }
60
61 func main() {
62 t := template.Must(template.New("montgomery").Parse(tmplWrapper))
63
64 tmplAddchainFile, err := os.CreateTemp("", "addchain-template")
65 if err != nil {
66 log.Fatal(err)
67 }
68 defer os.Remove(tmplAddchainFile.Name())
69 if _, err := io.WriteString(tmplAddchainFile, tmplAddchain); err != nil {
70 log.Fatal(err)
71 }
72 if err := tmplAddchainFile.Close(); err != nil {
73 log.Fatal(err)
74 }
75
76 for _, c := range curves {
77 log.Printf("Generating %s.go...", c.Prefix)
78 f, err := os.Create(c.Prefix + ".go")
79 if err != nil {
80 log.Fatal(err)
81 }
82 if err := t.Execute(f, c); err != nil {
83 log.Fatal(err)
84 }
85 if err := f.Close(); err != nil {
86 log.Fatal(err)
87 }
88
89 log.Printf("Generating %s_fiat64.go...", c.Prefix)
90 cmd := exec.Command("docker", "run", "--rm", "--entrypoint", "word_by_word_montgomery",
91 "fiat-crypto:v0.0.9", "--lang", "Go", "--no-wide-int", "--cmovznz-by-mul",
92 "--relax-primitive-carry-to-bitwidth", "32,64", "--internal-static",
93 "--public-function-case", "camelCase", "--public-type-case", "camelCase",
94 "--private-function-case", "camelCase", "--private-type-case", "camelCase",
95 "--doc-text-before-function-name", "", "--doc-newline-before-package-declaration",
96 "--doc-prepend-header", "Code generated by Fiat Cryptography. DO NOT EDIT.",
97 "--package-name", "fiat", "--no-prefix-fiat", c.Prefix, "64", c.Prime,
98 "mul", "square", "add", "sub", "one", "from_montgomery", "to_montgomery",
99 "selectznz", "to_bytes", "from_bytes")
100 cmd.Stderr = os.Stderr
101 out, err := cmd.Output()
102 if err != nil {
103 log.Fatal(err)
104 }
105 out, err = format.Source(out)
106 if err != nil {
107 log.Fatal(err)
108 }
109 if err := os.WriteFile(c.Prefix+"_fiat64.go", out, 0644); err != nil {
110 log.Fatal(err)
111 }
112
113 log.Printf("Generating %s_invert.go...", c.Prefix)
114 f, err = os.CreateTemp("", "addchain-"+c.Prefix)
115 if err != nil {
116 log.Fatal(err)
117 }
118 defer os.Remove(f.Name())
119 cmd = exec.Command("addchain", "search", c.Prime+" - 2")
120 cmd.Stderr = os.Stderr
121 cmd.Stdout = f
122 if err := cmd.Run(); err != nil {
123 log.Fatal(err)
124 }
125 if err := f.Close(); err != nil {
126 log.Fatal(err)
127 }
128 cmd = exec.Command("addchain", "gen", "-tmpl", tmplAddchainFile.Name(), f.Name())
129 cmd.Stderr = os.Stderr
130 out, err = cmd.Output()
131 if err != nil {
132 log.Fatal(err)
133 }
134 out = bytes.Replace(out, []byte("Element"), []byte(c.Element), -1)
135 out, err = format.Source(out)
136 if err != nil {
137 log.Fatal(err)
138 }
139 if err := os.WriteFile(c.Prefix+"_invert.go", out, 0644); err != nil {
140 log.Fatal(err)
141 }
142 }
143 }
144
145 const tmplWrapper = `// Copyright 2021 The Go Authors. All rights reserved.
146 // Use of this source code is governed by a BSD-style
147 // license that can be found in the LICENSE file.
148
149 // Code generated by generate.go. DO NOT EDIT.
150
151 package fiat
152
153 import (
154 "crypto/subtle"
155 "errors"
156 )
157
158 // {{ .Element }} is an integer modulo {{ .Prime }}.
159 //
160 // The zero value is a valid zero element.
161 type {{ .Element }} struct {
162 // Values are represented internally always in the Montgomery domain, and
163 // converted in Bytes and SetBytes.
164 x {{ .Prefix }}MontgomeryDomainFieldElement
165 }
166
167 const {{ .Prefix }}ElementLen = {{ .BytesLen }}
168
169 type {{ .Prefix }}UntypedFieldElement = {{ .FiatType }}
170
171 // One sets e = 1, and returns e.
172 func (e *{{ .Element }}) One() *{{ .Element }} {
173 {{ .Prefix }}SetOne(&e.x)
174 return e
175 }
176
177 // Equal returns 1 if e == t, and zero otherwise.
178 func (e *{{ .Element }}) Equal(t *{{ .Element }}) int {
179 eBytes := e.Bytes()
180 tBytes := t.Bytes()
181 return subtle.ConstantTimeCompare(eBytes, tBytes)
182 }
183
184 var {{ .Prefix }}ZeroEncoding = new({{ .Element }}).Bytes()
185
186 // IsZero returns 1 if e == 0, and zero otherwise.
187 func (e *{{ .Element }}) IsZero() int {
188 eBytes := e.Bytes()
189 return subtle.ConstantTimeCompare(eBytes, {{ .Prefix }}ZeroEncoding)
190 }
191
192 // Set sets e = t, and returns e.
193 func (e *{{ .Element }}) Set(t *{{ .Element }}) *{{ .Element }} {
194 e.x = t.x
195 return e
196 }
197
198 // Bytes returns the {{ .BytesLen }}-byte big-endian encoding of e.
199 func (e *{{ .Element }}) Bytes() []byte {
200 // This function is outlined to make the allocations inline in the caller
201 // rather than happen on the heap.
202 var out [{{ .Prefix }}ElementLen]byte
203 return e.bytes(&out)
204 }
205
206 func (e *{{ .Element }}) bytes(out *[{{ .Prefix }}ElementLen]byte) []byte {
207 var tmp {{ .Prefix }}NonMontgomeryDomainFieldElement
208 {{ .Prefix }}FromMontgomery(&tmp, &e.x)
209 {{ .Prefix }}ToBytes(out, (*{{ .Prefix }}UntypedFieldElement)(&tmp))
210 {{ .Prefix }}InvertEndianness(out[:])
211 return out[:]
212 }
213
214 // {{ .Prefix }}MinusOneEncoding is the encoding of -1 mod p, so p - 1, the
215 // highest canonical encoding. It is used by SetBytes to check for non-canonical
216 // encodings such as p + k, 2p + k, etc.
217 var {{ .Prefix }}MinusOneEncoding = new({{ .Element }}).Sub(
218 new({{ .Element }}), new({{ .Element }}).One()).Bytes()
219
220 // SetBytes sets e = v, where v is a big-endian {{ .BytesLen }}-byte encoding, and returns e.
221 // If v is not {{ .BytesLen }} bytes or it encodes a value higher than {{ .Prime }},
222 // SetBytes returns nil and an error, and e is unchanged.
223 func (e *{{ .Element }}) SetBytes(v []byte) (*{{ .Element }}, error) {
224 if len(v) != {{ .Prefix }}ElementLen {
225 return nil, errors.New("invalid {{ .Element }} encoding")
226 }
227 for i := range v {
228 if v[i] < {{ .Prefix }}MinusOneEncoding[i] {
229 break
230 }
231 if v[i] > {{ .Prefix }}MinusOneEncoding[i] {
232 return nil, errors.New("invalid {{ .Element }} encoding")
233 }
234 }
235 var in [{{ .Prefix }}ElementLen]byte
236 copy(in[:], v)
237 {{ .Prefix }}InvertEndianness(in[:])
238 var tmp {{ .Prefix }}NonMontgomeryDomainFieldElement
239 {{ .Prefix }}FromBytes((*{{ .Prefix }}UntypedFieldElement)(&tmp), &in)
240 {{ .Prefix }}ToMontgomery(&e.x, &tmp)
241 return e, nil
242 }
243
244 // Add sets e = t1 + t2, and returns e.
245 func (e *{{ .Element }}) Add(t1, t2 *{{ .Element }}) *{{ .Element }} {
246 {{ .Prefix }}Add(&e.x, &t1.x, &t2.x)
247 return e
248 }
249
250 // Sub sets e = t1 - t2, and returns e.
251 func (e *{{ .Element }}) Sub(t1, t2 *{{ .Element }}) *{{ .Element }} {
252 {{ .Prefix }}Sub(&e.x, &t1.x, &t2.x)
253 return e
254 }
255
256 // Mul sets e = t1 * t2, and returns e.
257 func (e *{{ .Element }}) Mul(t1, t2 *{{ .Element }}) *{{ .Element }} {
258 {{ .Prefix }}Mul(&e.x, &t1.x, &t2.x)
259 return e
260 }
261
262 // Square sets e = t * t, and returns e.
263 func (e *{{ .Element }}) Square(t *{{ .Element }}) *{{ .Element }} {
264 {{ .Prefix }}Square(&e.x, &t.x)
265 return e
266 }
267
268 // Select sets v to a if cond == 1, and to b if cond == 0.
269 func (v *{{ .Element }}) Select(a, b *{{ .Element }}, cond int) *{{ .Element }} {
270 {{ .Prefix }}Selectznz((*{{ .Prefix }}UntypedFieldElement)(&v.x), {{ .Prefix }}Uint1(cond),
271 (*{{ .Prefix }}UntypedFieldElement)(&b.x), (*{{ .Prefix }}UntypedFieldElement)(&a.x))
272 return v
273 }
274
275 func {{ .Prefix }}InvertEndianness(v []byte) {
276 for i := 0; i < len(v)/2; i++ {
277 v[i], v[len(v)-1-i] = v[len(v)-1-i], v[i]
278 }
279 }
280 `
281
282 const tmplAddchain = `// Copyright 2021 The Go Authors. All rights reserved.
283 // Use of this source code is governed by a BSD-style
284 // license that can be found in the LICENSE file.
285
286 // Code generated by {{ .Meta.Name }}. DO NOT EDIT.
287
288 package fiat
289
290 // Invert sets e = 1/x, and returns e.
291 //
292 // If x == 0, Invert returns e = 0.
293 func (e *Element) Invert(x *Element) *Element {
294 // Inversion is implemented as exponentiation with exponent p − 2.
295 // The sequence of {{ .Ops.Adds }} multiplications and {{ .Ops.Doubles }} squarings is derived from the
296 // following addition chain generated with {{ .Meta.Module }} {{ .Meta.ReleaseTag }}.
297 //
298 {{- range lines (format .Script) }}
299 // {{ . }}
300 {{- end }}
301 //
302
303 var z = new(Element).Set(e)
304 {{- range .Program.Temporaries }}
305 var {{ . }} = new(Element)
306 {{- end }}
307 {{ range $i := .Program.Instructions -}}
308 {{- with add $i.Op }}
309 {{ $i.Output }}.Mul({{ .X }}, {{ .Y }})
310 {{- end -}}
311
312 {{- with double $i.Op }}
313 {{ $i.Output }}.Square({{ .X }})
314 {{- end -}}
315
316 {{- with shift $i.Op -}}
317 {{- $first := 0 -}}
318 {{- if ne $i.Output.Identifier .X.Identifier }}
319 {{ $i.Output }}.Square({{ .X }})
320 {{- $first = 1 -}}
321 {{- end }}
322 for s := {{ $first }}; s < {{ .S }}; s++ {
323 {{ $i.Output }}.Square({{ $i.Output }})
324 }
325 {{- end -}}
326 {{- end }}
327
328 return e.Set(z)
329 }
330 `
331
View as plain text