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 Element: "P256Element",
38 Prime: "2^256 - 2^224 + 2^192 + 2^96 - 1",
39 Prefix: "p256",
40 FiatType: "[4]uint64",
41 BytesLen: 32,
42 },
43 {
44 Element: "P384Element",
45 Prime: "2^384 - 2^128 - 2^96 + 2^32 - 1",
46 Prefix: "p384",
47 FiatType: "[6]uint64",
48 BytesLen: 48,
49 },
50
51
52
53 {
54 Element: "P521Element",
55 Prime: "2^521 - 1",
56 Prefix: "p521",
57 FiatType: "[9]uint64",
58 BytesLen: 66,
59 },
60 }
61
62 func main() {
63 t := template.Must(template.New("montgomery").Parse(tmplWrapper))
64
65 tmplAddchainFile, err := os.CreateTemp("", "addchain-template")
66 if err != nil {
67 log.Fatal(err)
68 }
69 defer os.Remove(tmplAddchainFile.Name())
70 if _, err := io.WriteString(tmplAddchainFile, tmplAddchain); err != nil {
71 log.Fatal(err)
72 }
73 if err := tmplAddchainFile.Close(); err != nil {
74 log.Fatal(err)
75 }
76
77 for _, c := range curves {
78 log.Printf("Generating %s.go...", c.Prefix)
79 f, err := os.Create(c.Prefix + ".go")
80 if err != nil {
81 log.Fatal(err)
82 }
83 if err := t.Execute(f, c); err != nil {
84 log.Fatal(err)
85 }
86 if err := f.Close(); err != nil {
87 log.Fatal(err)
88 }
89
90 log.Printf("Generating %s_fiat64.go...", c.Prefix)
91 cmd := exec.Command("docker", "run", "--rm", "--entrypoint", "word_by_word_montgomery",
92 "fiat-crypto:v0.0.9", "--lang", "Go", "--no-wide-int", "--cmovznz-by-mul",
93 "--relax-primitive-carry-to-bitwidth", "32,64", "--internal-static",
94 "--public-function-case", "camelCase", "--public-type-case", "camelCase",
95 "--private-function-case", "camelCase", "--private-type-case", "camelCase",
96 "--doc-text-before-function-name", "", "--doc-newline-before-package-declaration",
97 "--doc-prepend-header", "Code generated by Fiat Cryptography. DO NOT EDIT.",
98 "--package-name", "fiat", "--no-prefix-fiat", c.Prefix, "64", c.Prime,
99 "mul", "square", "add", "sub", "one", "from_montgomery", "to_montgomery",
100 "selectznz", "to_bytes", "from_bytes")
101 cmd.Stderr = os.Stderr
102 out, err := cmd.Output()
103 if err != nil {
104 log.Fatal(err)
105 }
106 out, err = format.Source(out)
107 if err != nil {
108 log.Fatal(err)
109 }
110 if err := os.WriteFile(c.Prefix+"_fiat64.go", out, 0644); err != nil {
111 log.Fatal(err)
112 }
113
114 log.Printf("Generating %s_invert.go...", c.Prefix)
115 f, err = os.CreateTemp("", "addchain-"+c.Prefix)
116 if err != nil {
117 log.Fatal(err)
118 }
119 defer os.Remove(f.Name())
120 cmd = exec.Command("addchain", "search", c.Prime+" - 2")
121 cmd.Stderr = os.Stderr
122 cmd.Stdout = f
123 if err := cmd.Run(); err != nil {
124 log.Fatal(err)
125 }
126 if err := f.Close(); err != nil {
127 log.Fatal(err)
128 }
129 cmd = exec.Command("addchain", "gen", "-tmpl", tmplAddchainFile.Name(), f.Name())
130 cmd.Stderr = os.Stderr
131 out, err = cmd.Output()
132 if err != nil {
133 log.Fatal(err)
134 }
135 out = bytes.Replace(out, []byte("Element"), []byte(c.Element), -1)
136 out, err = format.Source(out)
137 if err != nil {
138 log.Fatal(err)
139 }
140 if err := os.WriteFile(c.Prefix+"_invert.go", out, 0644); err != nil {
141 log.Fatal(err)
142 }
143 }
144 }
145
146 const tmplWrapper = `// Copyright 2021 The Go Authors. All rights reserved.
147 // Use of this source code is governed by a BSD-style
148 // license that can be found in the LICENSE file.
149
150 // Code generated by generate.go. DO NOT EDIT.
151
152 package fiat
153
154 import (
155 "crypto/internal/fips140/subtle"
156 "errors"
157 )
158
159 // {{ .Element }} is an integer modulo {{ .Prime }}.
160 //
161 // The zero value is a valid zero element.
162 type {{ .Element }} struct {
163 // Values are represented internally always in the Montgomery domain, and
164 // converted in Bytes and SetBytes.
165 x {{ .Prefix }}MontgomeryDomainFieldElement
166 }
167
168 const {{ .Prefix }}ElementLen = {{ .BytesLen }}
169
170 type {{ .Prefix }}UntypedFieldElement = {{ .FiatType }}
171
172 // One sets e = 1, and returns e.
173 func (e *{{ .Element }}) One() *{{ .Element }} {
174 {{ .Prefix }}SetOne(&e.x)
175 return e
176 }
177
178 // Equal returns 1 if e == t, and zero otherwise.
179 func (e *{{ .Element }}) Equal(t *{{ .Element }}) int {
180 eBytes := e.Bytes()
181 tBytes := t.Bytes()
182 return subtle.ConstantTimeCompare(eBytes, tBytes)
183 }
184
185 // IsZero returns 1 if e == 0, and zero otherwise.
186 func (e *{{ .Element }}) IsZero() int {
187 zero := make([]byte, {{ .Prefix }}ElementLen)
188 eBytes := e.Bytes()
189 return subtle.ConstantTimeCompare(eBytes, zero)
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 // SetBytes sets e = v, where v is a big-endian {{ .BytesLen }}-byte encoding, and returns e.
215 // If v is not {{ .BytesLen }} bytes or it encodes a value higher than {{ .Prime }},
216 // SetBytes returns nil and an error, and e is unchanged.
217 func (e *{{ .Element }}) SetBytes(v []byte) (*{{ .Element }}, error) {
218 if len(v) != {{ .Prefix }}ElementLen {
219 return nil, errors.New("invalid {{ .Element }} encoding")
220 }
221
222 // Check for non-canonical encodings (p + k, 2p + k, etc.) by comparing to
223 // the encoding of -1 mod p, so p - 1, the highest canonical encoding.
224 var minusOneEncoding = new({{ .Element }}).Sub(
225 new({{ .Element }}), new({{ .Element }}).One()).Bytes()
226 for i := range v {
227 if v[i] < minusOneEncoding[i] {
228 break
229 }
230 if v[i] > minusOneEncoding[i] {
231 return nil, errors.New("invalid {{ .Element }} encoding")
232 }
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