1
2
3
4
5
6
7 package main
8
9
10
11
12
13
14 import (
15 "bytes"
16 "crypto/elliptic"
17 "fmt"
18 "go/format"
19 "io"
20 "log"
21 "math/big"
22 "os"
23 "os/exec"
24 "strings"
25 "text/template"
26 )
27
28 var curves = []struct {
29 P string
30 Element string
31 Params *elliptic.CurveParams
32 }{
33 {
34 P: "P224",
35 Element: "fiat.P224Element",
36 Params: elliptic.P224().Params(),
37 },
38 {
39 P: "P384",
40 Element: "fiat.P384Element",
41 Params: elliptic.P384().Params(),
42 },
43 {
44 P: "P521",
45 Element: "fiat.P521Element",
46 Params: elliptic.P521().Params(),
47 },
48 }
49
50 func main() {
51 t := template.Must(template.New("tmplNISTEC").Parse(tmplNISTEC))
52
53 tmplAddchainFile, err := os.CreateTemp("", "addchain-template")
54 if err != nil {
55 log.Fatal(err)
56 }
57 defer os.Remove(tmplAddchainFile.Name())
58 if _, err := io.WriteString(tmplAddchainFile, tmplAddchain); err != nil {
59 log.Fatal(err)
60 }
61 if err := tmplAddchainFile.Close(); err != nil {
62 log.Fatal(err)
63 }
64
65 for _, c := range curves {
66 p := strings.ToLower(c.P)
67 elementLen := (c.Params.BitSize + 7) / 8
68 B := fmt.Sprintf("%#v", c.Params.B.FillBytes(make([]byte, elementLen)))
69 Gx := fmt.Sprintf("%#v", c.Params.Gx.FillBytes(make([]byte, elementLen)))
70 Gy := fmt.Sprintf("%#v", c.Params.Gy.FillBytes(make([]byte, elementLen)))
71
72 log.Printf("Generating %s.go...", p)
73 f, err := os.Create(p + ".go")
74 if err != nil {
75 log.Fatal(err)
76 }
77 defer f.Close()
78 buf := &bytes.Buffer{}
79 if err := t.Execute(buf, map[string]interface{}{
80 "P": c.P, "p": p, "B": B, "Gx": Gx, "Gy": Gy,
81 "Element": c.Element, "ElementLen": elementLen,
82 }); err != nil {
83 log.Fatal(err)
84 }
85 out, err := format.Source(buf.Bytes())
86 if err != nil {
87 log.Fatal(err)
88 }
89 if _, err := f.Write(out); err != nil {
90 log.Fatal(err)
91 }
92
93
94 mod4 := new(big.Int).Mod(c.Params.P, big.NewInt(4))
95 if mod4.Cmp(big.NewInt(3)) != 0 {
96 continue
97 }
98
99 exp := new(big.Int).Add(c.Params.P, big.NewInt(1))
100 exp.Div(exp, big.NewInt(4))
101
102 tmp, err := os.CreateTemp("", "addchain-"+p)
103 if err != nil {
104 log.Fatal(err)
105 }
106 defer os.Remove(tmp.Name())
107 cmd := exec.Command("addchain", "search", fmt.Sprintf("%d", exp))
108 cmd.Stderr = os.Stderr
109 cmd.Stdout = tmp
110 if err := cmd.Run(); err != nil {
111 log.Fatal(err)
112 }
113 if err := tmp.Close(); err != nil {
114 log.Fatal(err)
115 }
116 cmd = exec.Command("addchain", "gen", "-tmpl", tmplAddchainFile.Name(), tmp.Name())
117 cmd.Stderr = os.Stderr
118 out, err = cmd.Output()
119 if err != nil {
120 log.Fatal(err)
121 }
122 out = bytes.Replace(out, []byte("Element"), []byte(c.Element), -1)
123 out = bytes.Replace(out, []byte("sqrtCandidate"), []byte(p+"SqrtCandidate"), -1)
124 out, err = format.Source(out)
125 if err != nil {
126 log.Fatal(err)
127 }
128 if _, err := f.Write(out); err != nil {
129 log.Fatal(err)
130 }
131 }
132 }
133
134 const tmplNISTEC = `// Copyright 2022 The Go Authors. All rights reserved.
135 // Use of this source code is governed by a BSD-style
136 // license that can be found in the LICENSE file.
137
138 // Code generated by generate.go. DO NOT EDIT.
139
140 package nistec
141
142 import (
143 "crypto/internal/fips140/nistec/fiat"
144 "crypto/internal/fips140/subtle"
145 "errors"
146 "sync"
147 )
148
149 // {{.p}}ElementLength is the length of an element of the base or scalar field,
150 // which have the same bytes length for all NIST P curves.
151 const {{.p}}ElementLength = {{ .ElementLen }}
152
153 // {{.P}}Point is a {{.P}} point. The zero value is NOT valid.
154 type {{.P}}Point struct {
155 // The point is represented in projective coordinates (X:Y:Z),
156 // where x = X/Z and y = Y/Z.
157 x, y, z *{{.Element}}
158 }
159
160 // New{{.P}}Point returns a new {{.P}}Point representing the point at infinity point.
161 func New{{.P}}Point() *{{.P}}Point {
162 return &{{.P}}Point{
163 x: new({{.Element}}),
164 y: new({{.Element}}).One(),
165 z: new({{.Element}}),
166 }
167 }
168
169 // SetGenerator sets p to the canonical generator and returns p.
170 func (p *{{.P}}Point) SetGenerator() *{{.P}}Point {
171 p.x.SetBytes({{.Gx}})
172 p.y.SetBytes({{.Gy}})
173 p.z.One()
174 return p
175 }
176
177 // Set sets p = q and returns p.
178 func (p *{{.P}}Point) Set(q *{{.P}}Point) *{{.P}}Point {
179 p.x.Set(q.x)
180 p.y.Set(q.y)
181 p.z.Set(q.z)
182 return p
183 }
184
185 // SetBytes sets p to the compressed, uncompressed, or infinity value encoded in
186 // b, as specified in SEC 1, Version 2.0, Section 2.3.4. If the point is not on
187 // the curve, it returns nil and an error, and the receiver is unchanged.
188 // Otherwise, it returns p.
189 func (p *{{.P}}Point) SetBytes(b []byte) (*{{.P}}Point, error) {
190 switch {
191 // Point at infinity.
192 case len(b) == 1 && b[0] == 0:
193 return p.Set(New{{.P}}Point()), nil
194
195 // Uncompressed form.
196 case len(b) == 1+2*{{.p}}ElementLength && b[0] == 4:
197 x, err := new({{.Element}}).SetBytes(b[1 : 1+{{.p}}ElementLength])
198 if err != nil {
199 return nil, err
200 }
201 y, err := new({{.Element}}).SetBytes(b[1+{{.p}}ElementLength:])
202 if err != nil {
203 return nil, err
204 }
205 if err := {{.p}}CheckOnCurve(x, y); err != nil {
206 return nil, err
207 }
208 p.x.Set(x)
209 p.y.Set(y)
210 p.z.One()
211 return p, nil
212
213 // Compressed form.
214 case len(b) == 1+{{.p}}ElementLength && (b[0] == 2 || b[0] == 3):
215 x, err := new({{.Element}}).SetBytes(b[1:])
216 if err != nil {
217 return nil, err
218 }
219
220 // y² = x³ - 3x + b
221 y := {{.p}}Polynomial(new({{.Element}}), x)
222 if !{{.p}}Sqrt(y, y) {
223 return nil, errors.New("invalid {{.P}} compressed point encoding")
224 }
225
226 // Select the positive or negative root, as indicated by the least
227 // significant bit, based on the encoding type byte.
228 otherRoot := new({{.Element}})
229 otherRoot.Sub(otherRoot, y)
230 cond := y.Bytes()[{{.p}}ElementLength-1]&1 ^ b[0]&1
231 y.Select(otherRoot, y, int(cond))
232
233 p.x.Set(x)
234 p.y.Set(y)
235 p.z.One()
236 return p, nil
237
238 default:
239 return nil, errors.New("invalid {{.P}} point encoding")
240 }
241 }
242
243
244 var _{{.p}}B *{{.Element}}
245 var _{{.p}}BOnce sync.Once
246
247 func {{.p}}B() *{{.Element}} {
248 _{{.p}}BOnce.Do(func() {
249 _{{.p}}B, _ = new({{.Element}}).SetBytes({{.B}})
250 })
251 return _{{.p}}B
252 }
253
254 // {{.p}}Polynomial sets y2 to x³ - 3x + b, and returns y2.
255 func {{.p}}Polynomial(y2, x *{{.Element}}) *{{.Element}} {
256 y2.Square(x)
257 y2.Mul(y2, x)
258
259 threeX := new({{.Element}}).Add(x, x)
260 threeX.Add(threeX, x)
261 y2.Sub(y2, threeX)
262
263 return y2.Add(y2, {{.p}}B())
264 }
265
266 func {{.p}}CheckOnCurve(x, y *{{.Element}}) error {
267 // y² = x³ - 3x + b
268 rhs := {{.p}}Polynomial(new({{.Element}}), x)
269 lhs := new({{.Element}}).Square(y)
270 if rhs.Equal(lhs) != 1 {
271 return errors.New("{{.P}} point not on curve")
272 }
273 return nil
274 }
275
276 // Bytes returns the uncompressed or infinity encoding of p, as specified in
277 // SEC 1, Version 2.0, Section 2.3.3. Note that the encoding of the point at
278 // infinity is shorter than all other encodings.
279 func (p *{{.P}}Point) Bytes() []byte {
280 // This function is outlined to make the allocations inline in the caller
281 // rather than happen on the heap.
282 var out [1+2*{{.p}}ElementLength]byte
283 return p.bytes(&out)
284 }
285
286 func (p *{{.P}}Point) bytes(out *[1+2*{{.p}}ElementLength]byte) []byte {
287 if p.z.IsZero() == 1 {
288 return append(out[:0], 0)
289 }
290
291 zinv := new({{.Element}}).Invert(p.z)
292 x := new({{.Element}}).Mul(p.x, zinv)
293 y := new({{.Element}}).Mul(p.y, zinv)
294
295 buf := append(out[:0], 4)
296 buf = append(buf, x.Bytes()...)
297 buf = append(buf, y.Bytes()...)
298 return buf
299 }
300
301 // BytesX returns the encoding of the x-coordinate of p, as specified in SEC 1,
302 // Version 2.0, Section 2.3.5, or an error if p is the point at infinity.
303 func (p *{{.P}}Point) BytesX() ([]byte, error) {
304 // This function is outlined to make the allocations inline in the caller
305 // rather than happen on the heap.
306 var out [{{.p}}ElementLength]byte
307 return p.bytesX(&out)
308 }
309
310 func (p *{{.P}}Point) bytesX(out *[{{.p}}ElementLength]byte) ([]byte, error) {
311 if p.z.IsZero() == 1 {
312 return nil, errors.New("{{.P}} point is the point at infinity")
313 }
314
315 zinv := new({{.Element}}).Invert(p.z)
316 x := new({{.Element}}).Mul(p.x, zinv)
317
318 return append(out[:0], x.Bytes()...), nil
319 }
320
321 // BytesCompressed returns the compressed or infinity encoding of p, as
322 // specified in SEC 1, Version 2.0, Section 2.3.3. Note that the encoding of the
323 // point at infinity is shorter than all other encodings.
324 func (p *{{.P}}Point) BytesCompressed() []byte {
325 // This function is outlined to make the allocations inline in the caller
326 // rather than happen on the heap.
327 var out [1 + {{.p}}ElementLength]byte
328 return p.bytesCompressed(&out)
329 }
330
331 func (p *{{.P}}Point) bytesCompressed(out *[1 + {{.p}}ElementLength]byte) []byte {
332 if p.z.IsZero() == 1 {
333 return append(out[:0], 0)
334 }
335
336 zinv := new({{.Element}}).Invert(p.z)
337 x := new({{.Element}}).Mul(p.x, zinv)
338 y := new({{.Element}}).Mul(p.y, zinv)
339
340 // Encode the sign of the y coordinate (indicated by the least significant
341 // bit) as the encoding type (2 or 3).
342 buf := append(out[:0], 2)
343 buf[0] |= y.Bytes()[{{.p}}ElementLength-1] & 1
344 buf = append(buf, x.Bytes()...)
345 return buf
346 }
347
348 // Add sets q = p1 + p2, and returns q. The points may overlap.
349 func (q *{{.P}}Point) Add(p1, p2 *{{.P}}Point) *{{.P}}Point {
350 // Complete addition formula for a = -3 from "Complete addition formulas for
351 // prime order elliptic curves" (https://eprint.iacr.org/2015/1060), §A.2.
352
353 t0 := new({{.Element}}).Mul(p1.x, p2.x) // t0 := X1 * X2
354 t1 := new({{.Element}}).Mul(p1.y, p2.y) // t1 := Y1 * Y2
355 t2 := new({{.Element}}).Mul(p1.z, p2.z) // t2 := Z1 * Z2
356 t3 := new({{.Element}}).Add(p1.x, p1.y) // t3 := X1 + Y1
357 t4 := new({{.Element}}).Add(p2.x, p2.y) // t4 := X2 + Y2
358 t3.Mul(t3, t4) // t3 := t3 * t4
359 t4.Add(t0, t1) // t4 := t0 + t1
360 t3.Sub(t3, t4) // t3 := t3 - t4
361 t4.Add(p1.y, p1.z) // t4 := Y1 + Z1
362 x3 := new({{.Element}}).Add(p2.y, p2.z) // X3 := Y2 + Z2
363 t4.Mul(t4, x3) // t4 := t4 * X3
364 x3.Add(t1, t2) // X3 := t1 + t2
365 t4.Sub(t4, x3) // t4 := t4 - X3
366 x3.Add(p1.x, p1.z) // X3 := X1 + Z1
367 y3 := new({{.Element}}).Add(p2.x, p2.z) // Y3 := X2 + Z2
368 x3.Mul(x3, y3) // X3 := X3 * Y3
369 y3.Add(t0, t2) // Y3 := t0 + t2
370 y3.Sub(x3, y3) // Y3 := X3 - Y3
371 z3 := new({{.Element}}).Mul({{.p}}B(), t2) // Z3 := b * t2
372 x3.Sub(y3, z3) // X3 := Y3 - Z3
373 z3.Add(x3, x3) // Z3 := X3 + X3
374 x3.Add(x3, z3) // X3 := X3 + Z3
375 z3.Sub(t1, x3) // Z3 := t1 - X3
376 x3.Add(t1, x3) // X3 := t1 + X3
377 y3.Mul({{.p}}B(), y3) // Y3 := b * Y3
378 t1.Add(t2, t2) // t1 := t2 + t2
379 t2.Add(t1, t2) // t2 := t1 + t2
380 y3.Sub(y3, t2) // Y3 := Y3 - t2
381 y3.Sub(y3, t0) // Y3 := Y3 - t0
382 t1.Add(y3, y3) // t1 := Y3 + Y3
383 y3.Add(t1, y3) // Y3 := t1 + Y3
384 t1.Add(t0, t0) // t1 := t0 + t0
385 t0.Add(t1, t0) // t0 := t1 + t0
386 t0.Sub(t0, t2) // t0 := t0 - t2
387 t1.Mul(t4, y3) // t1 := t4 * Y3
388 t2.Mul(t0, y3) // t2 := t0 * Y3
389 y3.Mul(x3, z3) // Y3 := X3 * Z3
390 y3.Add(y3, t2) // Y3 := Y3 + t2
391 x3.Mul(t3, x3) // X3 := t3 * X3
392 x3.Sub(x3, t1) // X3 := X3 - t1
393 z3.Mul(t4, z3) // Z3 := t4 * Z3
394 t1.Mul(t3, t0) // t1 := t3 * t0
395 z3.Add(z3, t1) // Z3 := Z3 + t1
396
397 q.x.Set(x3)
398 q.y.Set(y3)
399 q.z.Set(z3)
400 return q
401 }
402
403 // Double sets q = p + p, and returns q. The points may overlap.
404 func (q *{{.P}}Point) Double(p *{{.P}}Point) *{{.P}}Point {
405 // Complete addition formula for a = -3 from "Complete addition formulas for
406 // prime order elliptic curves" (https://eprint.iacr.org/2015/1060), §A.2.
407
408 t0 := new({{.Element}}).Square(p.x) // t0 := X ^ 2
409 t1 := new({{.Element}}).Square(p.y) // t1 := Y ^ 2
410 t2 := new({{.Element}}).Square(p.z) // t2 := Z ^ 2
411 t3 := new({{.Element}}).Mul(p.x, p.y) // t3 := X * Y
412 t3.Add(t3, t3) // t3 := t3 + t3
413 z3 := new({{.Element}}).Mul(p.x, p.z) // Z3 := X * Z
414 z3.Add(z3, z3) // Z3 := Z3 + Z3
415 y3 := new({{.Element}}).Mul({{.p}}B(), t2) // Y3 := b * t2
416 y3.Sub(y3, z3) // Y3 := Y3 - Z3
417 x3 := new({{.Element}}).Add(y3, y3) // X3 := Y3 + Y3
418 y3.Add(x3, y3) // Y3 := X3 + Y3
419 x3.Sub(t1, y3) // X3 := t1 - Y3
420 y3.Add(t1, y3) // Y3 := t1 + Y3
421 y3.Mul(x3, y3) // Y3 := X3 * Y3
422 x3.Mul(x3, t3) // X3 := X3 * t3
423 t3.Add(t2, t2) // t3 := t2 + t2
424 t2.Add(t2, t3) // t2 := t2 + t3
425 z3.Mul({{.p}}B(), z3) // Z3 := b * Z3
426 z3.Sub(z3, t2) // Z3 := Z3 - t2
427 z3.Sub(z3, t0) // Z3 := Z3 - t0
428 t3.Add(z3, z3) // t3 := Z3 + Z3
429 z3.Add(z3, t3) // Z3 := Z3 + t3
430 t3.Add(t0, t0) // t3 := t0 + t0
431 t0.Add(t3, t0) // t0 := t3 + t0
432 t0.Sub(t0, t2) // t0 := t0 - t2
433 t0.Mul(t0, z3) // t0 := t0 * Z3
434 y3.Add(y3, t0) // Y3 := Y3 + t0
435 t0.Mul(p.y, p.z) // t0 := Y * Z
436 t0.Add(t0, t0) // t0 := t0 + t0
437 z3.Mul(t0, z3) // Z3 := t0 * Z3
438 x3.Sub(x3, z3) // X3 := X3 - Z3
439 z3.Mul(t0, t1) // Z3 := t0 * t1
440 z3.Add(z3, z3) // Z3 := Z3 + Z3
441 z3.Add(z3, z3) // Z3 := Z3 + Z3
442
443 q.x.Set(x3)
444 q.y.Set(y3)
445 q.z.Set(z3)
446 return q
447 }
448
449 // Select sets q to p1 if cond == 1, and to p2 if cond == 0.
450 func (q *{{.P}}Point) Select(p1, p2 *{{.P}}Point, cond int) *{{.P}}Point {
451 q.x.Select(p1.x, p2.x, cond)
452 q.y.Select(p1.y, p2.y, cond)
453 q.z.Select(p1.z, p2.z, cond)
454 return q
455 }
456
457 // A {{.p}}Table holds the first 15 multiples of a point at offset -1, so [1]P
458 // is at table[0], [15]P is at table[14], and [0]P is implicitly the identity
459 // point.
460 type {{.p}}Table [15]*{{.P}}Point
461
462 // Select selects the n-th multiple of the table base point into p. It works in
463 // constant time by iterating over every entry of the table. n must be in [0, 15].
464 func (table *{{.p}}Table) Select(p *{{.P}}Point, n uint8) {
465 if n >= 16 {
466 panic("nistec: internal error: {{.p}}Table called with out-of-bounds value")
467 }
468 p.Set(New{{.P}}Point())
469 for i := uint8(1); i < 16; i++ {
470 cond := subtle.ConstantTimeByteEq(i, n)
471 p.Select(table[i-1], p, cond)
472 }
473 }
474
475 // ScalarMult sets p = scalar * q, and returns p.
476 func (p *{{.P}}Point) ScalarMult(q *{{.P}}Point, scalar []byte) (*{{.P}}Point, error) {
477 // Compute a {{.p}}Table for the base point q. The explicit New{{.P}}Point
478 // calls get inlined, letting the allocations live on the stack.
479 var table = {{.p}}Table{New{{.P}}Point(), New{{.P}}Point(), New{{.P}}Point(),
480 New{{.P}}Point(), New{{.P}}Point(), New{{.P}}Point(), New{{.P}}Point(),
481 New{{.P}}Point(), New{{.P}}Point(), New{{.P}}Point(), New{{.P}}Point(),
482 New{{.P}}Point(), New{{.P}}Point(), New{{.P}}Point(), New{{.P}}Point()}
483 table[0].Set(q)
484 for i := 1; i < 15; i += 2 {
485 table[i].Double(table[i/2])
486 table[i+1].Add(table[i], q)
487 }
488
489 // Instead of doing the classic double-and-add chain, we do it with a
490 // four-bit window: we double four times, and then add [0-15]P.
491 t := New{{.P}}Point()
492 p.Set(New{{.P}}Point())
493 for i, byte := range scalar {
494 // No need to double on the first iteration, as p is the identity at
495 // this point, and [N]∞ = ∞.
496 if i != 0 {
497 p.Double(p)
498 p.Double(p)
499 p.Double(p)
500 p.Double(p)
501 }
502
503 windowValue := byte >> 4
504 table.Select(t, windowValue)
505 p.Add(p, t)
506
507 p.Double(p)
508 p.Double(p)
509 p.Double(p)
510 p.Double(p)
511
512 windowValue = byte & 0b1111
513 table.Select(t, windowValue)
514 p.Add(p, t)
515 }
516
517 return p, nil
518 }
519
520 var {{.p}}GeneratorTable *[{{.p}}ElementLength * 2]{{.p}}Table
521 var {{.p}}GeneratorTableOnce sync.Once
522
523 // generatorTable returns a sequence of {{.p}}Tables. The first table contains
524 // multiples of G. Each successive table is the previous table doubled four
525 // times.
526 func (p *{{.P}}Point) generatorTable() *[{{.p}}ElementLength * 2]{{.p}}Table {
527 {{.p}}GeneratorTableOnce.Do(func() {
528 {{.p}}GeneratorTable = new([{{.p}}ElementLength * 2]{{.p}}Table)
529 base := New{{.P}}Point().SetGenerator()
530 for i := 0; i < {{.p}}ElementLength*2; i++ {
531 {{.p}}GeneratorTable[i][0] = New{{.P}}Point().Set(base)
532 for j := 1; j < 15; j++ {
533 {{.p}}GeneratorTable[i][j] = New{{.P}}Point().Add({{.p}}GeneratorTable[i][j-1], base)
534 }
535 base.Double(base)
536 base.Double(base)
537 base.Double(base)
538 base.Double(base)
539 }
540 })
541 return {{.p}}GeneratorTable
542 }
543
544 // ScalarBaseMult sets p = scalar * B, where B is the canonical generator, and
545 // returns p.
546 func (p *{{.P}}Point) ScalarBaseMult(scalar []byte) (*{{.P}}Point, error) {
547 if len(scalar) != {{.p}}ElementLength {
548 return nil, errors.New("invalid scalar length")
549 }
550 tables := p.generatorTable()
551
552 // This is also a scalar multiplication with a four-bit window like in
553 // ScalarMult, but in this case the doublings are precomputed. The value
554 // [windowValue]G added at iteration k would normally get doubled
555 // (totIterations-k)×4 times, but with a larger precomputation we can
556 // instead add [2^((totIterations-k)×4)][windowValue]G and avoid the
557 // doublings between iterations.
558 t := New{{.P}}Point()
559 p.Set(New{{.P}}Point())
560 tableIndex := len(tables) - 1
561 for _, byte := range scalar {
562 windowValue := byte >> 4
563 tables[tableIndex].Select(t, windowValue)
564 p.Add(p, t)
565 tableIndex--
566
567 windowValue = byte & 0b1111
568 tables[tableIndex].Select(t, windowValue)
569 p.Add(p, t)
570 tableIndex--
571 }
572
573 return p, nil
574 }
575
576 // {{.p}}Sqrt sets e to a square root of x. If x is not a square, {{.p}}Sqrt returns
577 // false and e is unchanged. e and x can overlap.
578 func {{.p}}Sqrt(e, x *{{ .Element }}) (isSquare bool) {
579 candidate := new({{ .Element }})
580 {{.p}}SqrtCandidate(candidate, x)
581 square := new({{ .Element }}).Square(candidate)
582 if square.Equal(x) != 1 {
583 return false
584 }
585 e.Set(candidate)
586 return true
587 }
588 `
589
590 const tmplAddchain = `
591 // sqrtCandidate sets z to a square root candidate for x. z and x must not overlap.
592 func sqrtCandidate(z, x *Element) {
593 // Since p = 3 mod 4, exponentiation by (p + 1) / 4 yields a square root candidate.
594 //
595 // The sequence of {{ .Ops.Adds }} multiplications and {{ .Ops.Doubles }} squarings is derived from the
596 // following addition chain generated with {{ .Meta.Module }} {{ .Meta.ReleaseTag }}.
597 //
598 {{- range lines (format .Script) }}
599 // {{ . }}
600 {{- end }}
601 //
602
603 {{- range .Program.Temporaries }}
604 var {{ . }} = new(Element)
605 {{- end }}
606 {{ range $i := .Program.Instructions -}}
607 {{- with add $i.Op }}
608 {{ $i.Output }}.Mul({{ .X }}, {{ .Y }})
609 {{- end -}}
610
611 {{- with double $i.Op }}
612 {{ $i.Output }}.Square({{ .X }})
613 {{- end -}}
614
615 {{- with shift $i.Op -}}
616 {{- $first := 0 -}}
617 {{- if ne $i.Output.Identifier .X.Identifier }}
618 {{ $i.Output }}.Square({{ .X }})
619 {{- $first = 1 -}}
620 {{- end }}
621 for s := {{ $first }}; s < {{ .S }}; s++ {
622 {{ $i.Output }}.Square({{ $i.Output }})
623 }
624 {{- end -}}
625 {{- end }}
626 }
627 `
628
View as plain text