generate.go

     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 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  
    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/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