| 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 |
|
| 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 |
// The 32-bit pure Go P-256 in crypto/elliptic is still faster than the |
| 34 |
// autogenerated code here, regrettably. |
| 35 |
// { |
| 36 |
// Element: "P256Element", |
| 37 |
// Prime: "2^256 - 2^224 + 2^192 + 2^96 - 1", |
| 38 |
// Prefix: "p256", |
| 39 |
// FiatType: "[4]uint64", |
| 40 |
// BytesLen: 32, |
| 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 |
// Note that unsaturated_solinas would be about 2x faster than |
| 50 |
// word_by_word_montgomery for P-521, but this curve is used rarely enough |
| 51 |
// that it's not worth carrying unsaturated_solinas support for it. |
| 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 |
` |