1// Copyright 2022 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
5package nistec
6
7import (
8	"crypto/internal/nistec/fiat"
9	"sync"
10)
11
12var p224GG *[96]fiat.P224Element
13var p224GGOnce sync.Once
14
15// p224SqrtCandidate sets r to a square root candidate for x. r and x must not overlap.
16func p224SqrtCandidate(r, x *fiat.P224Element) {
17	// Since p = 1 mod 4, we can't use the exponentiation by (p + 1) / 4 like
18	// for the other primes. Instead, implement a variation of Tonelli–Shanks.
19	// The constant-time implementation is adapted from Thomas Pornin's ecGFp5.
20	//
21	// https://github.com/pornin/ecgfp5/blob/82325b965/rust/src/field.rs#L337-L385
22
23	// p = q*2^n + 1 with q odd -> q = 2^128 - 1 and n = 96
24	// g^(2^n) = 1 -> g = 11 ^ q (where 11 is the smallest non-square)
25	// GG[j] = g^(2^j) for j = 0 to n-1
26
27	p224GGOnce.Do(func() {
28		p224GG = new([96]fiat.P224Element)
29		for i := range p224GG {
30			if i == 0 {
31				p224GG[i].SetBytes([]byte{0x6a, 0x0f, 0xec, 0x67,
32					0x85, 0x98, 0xa7, 0x92, 0x0c, 0x55, 0xb2, 0xd4,
33					0x0b, 0x2d, 0x6f, 0xfb, 0xbe, 0xa3, 0xd8, 0xce,
34					0xf3, 0xfb, 0x36, 0x32, 0xdc, 0x69, 0x1b, 0x74})
35			} else {
36				p224GG[i].Square(&p224GG[i-1])
37			}
38		}
39	})
40
41	// r <- x^((q+1)/2) = x^(2^127)
42	// v <- x^q = x^(2^128-1)
43
44	// Compute x^(2^127-1) first.
45	//
46	// The sequence of 10 multiplications and 126 squarings is derived from the
47	// following addition chain generated with github.com/mmcloughlin/addchain v0.4.0.
48	//
49	//	_10      = 2*1
50	//	_11      = 1 + _10
51	//	_110     = 2*_11
52	//	_111     = 1 + _110
53	//	_111000  = _111 << 3
54	//	_111111  = _111 + _111000
55	//	_1111110 = 2*_111111
56	//	_1111111 = 1 + _1111110
57	//	x12      = _1111110 << 5 + _111111
58	//	x24      = x12 << 12 + x12
59	//	i36      = x24 << 7
60	//	x31      = _1111111 + i36
61	//	x48      = i36 << 17 + x24
62	//	x96      = x48 << 48 + x48
63	//	return     x96 << 31 + x31
64	//
65	var t0 = new(fiat.P224Element)
66	var t1 = new(fiat.P224Element)
67
68	r.Square(x)
69	r.Mul(x, r)
70	r.Square(r)
71	r.Mul(x, r)
72	t0.Square(r)
73	for s := 1; s < 3; s++ {
74		t0.Square(t0)
75	}
76	t0.Mul(r, t0)
77	t1.Square(t0)
78	r.Mul(x, t1)
79	for s := 0; s < 5; s++ {
80		t1.Square(t1)
81	}
82	t0.Mul(t0, t1)
83	t1.Square(t0)
84	for s := 1; s < 12; s++ {
85		t1.Square(t1)
86	}
87	t0.Mul(t0, t1)
88	t1.Square(t0)
89	for s := 1; s < 7; s++ {
90		t1.Square(t1)
91	}
92	r.Mul(r, t1)
93	for s := 0; s < 17; s++ {
94		t1.Square(t1)
95	}
96	t0.Mul(t0, t1)
97	t1.Square(t0)
98	for s := 1; s < 48; s++ {
99		t1.Square(t1)
100	}
101	t0.Mul(t0, t1)
102	for s := 0; s < 31; s++ {
103		t0.Square(t0)
104	}
105	r.Mul(r, t0)
106
107	// v = x^(2^127-1)^2 * x
108	v := new(fiat.P224Element).Square(r)
109	v.Mul(v, x)
110
111	// r = x^(2^127-1) * x
112	r.Mul(r, x)
113
114	// for i = n-1 down to 1:
115	//     w = v^(2^(i-1))
116	//     if w == -1 then:
117	//         v <- v*GG[n-i]
118	//         r <- r*GG[n-i-1]
119
120	var p224MinusOne = new(fiat.P224Element).Sub(
121		new(fiat.P224Element), new(fiat.P224Element).One())
122
123	for i := 96 - 1; i >= 1; i-- {
124		w := new(fiat.P224Element).Set(v)
125		for j := 0; j < i-1; j++ {
126			w.Square(w)
127		}
128		cond := w.Equal(p224MinusOne)
129		v.Select(t0.Mul(v, &p224GG[96-i]), v, cond)
130		r.Select(t0.Mul(r, &p224GG[96-i-1]), r, cond)
131	}
132}
133