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//go:build ignore
6
7package main
8
9import (
10	"bytes"
11	"go/format"
12	"io"
13	"log"
14	"os"
15	"os/exec"
16	"text/template"
17)
18
19var 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	// The P-256 fiat implementation is used only on 32-bit architectures, but
34	// the uint32 fiat code is for some reason slower than the uint64 one. That
35	// suggests there is a wide margin for improvement.
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	// Note that unsaturated_solinas would be about 2x faster than
51	// word_by_word_montgomery for P-521, but this curve is used rarely enough
52	// that it's not worth carrying unsaturated_solinas support for it.
53	{
54		Element:  "P521Element",
55		Prime:    "2^521 - 1",
56		Prefix:   "p521",
57		FiatType: "[9]uint64",
58		BytesLen: 66,
59	},
60}
61
62func 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
146const 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
152package fiat
153
154import (
155	"crypto/subtle"
156	"errors"
157)
158
159// {{ .Element }} is an integer modulo {{ .Prime }}.
160//
161// The zero value is a valid zero element.
162type {{ .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
168const {{ .Prefix }}ElementLen = {{ .BytesLen }}
169
170type {{ .Prefix }}UntypedFieldElement = {{ .FiatType }}
171
172// One sets e = 1, and returns e.
173func (e *{{ .Element }}) One() *{{ .Element }} {
174	{{ .Prefix }}SetOne(&e.x)
175	return e
176}
177
178// Equal returns 1 if e == t, and zero otherwise.
179func (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.
186func (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.
193func (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.
199func (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
206func (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.
217func (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.
245func (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.
251func (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.
257func (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.
263func (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.
269func (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
275func {{ .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
282const 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
288package fiat
289
290// Invert sets e = 1/x, and returns e.
291//
292// If x == 0, Invert returns e = 0.
293func (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