1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
|
// Copyright 2021 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
// Package fiat implements prime order fields using formally verified algorithms
// from the Fiat Cryptography project.
package fiat
import (
"crypto/subtle"
"errors"
)
// P521Element is an integer modulo 2^521 - 1.
//
// The zero value is a valid zero element.
type P521Element struct {
// This element has the following bounds, which are tighter than
// the output bounds of some operations. Those operations must be
// followed by a carry.
//
// [0x0 ~> 0x400000000000000], [0x0 ~> 0x400000000000000], [0x0 ~> 0x400000000000000],
// [0x0 ~> 0x400000000000000], [0x0 ~> 0x400000000000000], [0x0 ~> 0x400000000000000],
// [0x0 ~> 0x400000000000000], [0x0 ~> 0x400000000000000], [0x0 ~> 0x200000000000000]
x [9]uint64
}
// One sets e = 1, and returns e.
func (e *P521Element) One() *P521Element {
*e = P521Element{}
e.x[0] = 1
return e
}
// Equal returns 1 if e == t, and zero otherwise.
func (e *P521Element) Equal(t *P521Element) int {
eBytes := e.Bytes()
tBytes := t.Bytes()
return subtle.ConstantTimeCompare(eBytes, tBytes)
}
var p521ZeroEncoding = new(P521Element).Bytes()
// IsZero returns 1 if e == 0, and zero otherwise.
func (e *P521Element) IsZero() int {
eBytes := e.Bytes()
return subtle.ConstantTimeCompare(eBytes, p521ZeroEncoding)
}
// Set sets e = t, and returns e.
func (e *P521Element) Set(t *P521Element) *P521Element {
e.x = t.x
return e
}
// Bytes returns the 66-byte little-endian encoding of e.
func (e *P521Element) Bytes() []byte {
// This function must be inlined to move the allocation to the parent and
// save it from escaping to the heap.
var out [66]byte
p521ToBytes(&out, &e.x)
return out[:]
}
// SetBytes sets e = v, where v is a little-endian 66-byte encoding, and returns
// e. If v is not 66 bytes or it encodes a value higher than 2^521 - 1, SetBytes
// returns nil and an error, and e is unchanged.
func (e *P521Element) SetBytes(v []byte) (*P521Element, error) {
if len(v) != 66 || v[65] > 1 {
return nil, errors.New("invalid P-521 field encoding")
}
var in [66]byte
copy(in[:], v)
p521FromBytes(&e.x, &in)
return e, nil
}
// Add sets e = t1 + t2, and returns e.
func (e *P521Element) Add(t1, t2 *P521Element) *P521Element {
p521Add(&e.x, &t1.x, &t2.x)
p521Carry(&e.x, &e.x)
return e
}
// Sub sets e = t1 - t2, and returns e.
func (e *P521Element) Sub(t1, t2 *P521Element) *P521Element {
p521Sub(&e.x, &t1.x, &t2.x)
p521Carry(&e.x, &e.x)
return e
}
// Mul sets e = t1 * t2, and returns e.
func (e *P521Element) Mul(t1, t2 *P521Element) *P521Element {
p521CarryMul(&e.x, &t1.x, &t2.x)
return e
}
// Square sets e = t * t, and returns e.
func (e *P521Element) Square(t *P521Element) *P521Element {
p521CarrySquare(&e.x, &t.x)
return e
}
// Select sets e to a if cond == 1, and to b if cond == 0.
func (v *P521Element) Select(a, b *P521Element, cond int) *P521Element {
p521Selectznz(&v.x, p521Uint1(cond), &b.x, &a.x)
return v
}
// Invert sets e = 1/t, and returns e.
//
// If t == 0, Invert returns e = 0.
func (e *P521Element) Invert(t *P521Element) *P521Element {
// Inversion is implemented as exponentiation with exponent p − 2.
// The sequence of multiplications and squarings was generated with
// github.com/mmcloughlin/addchain v0.2.0.
var t1, t2 = new(P521Element), new(P521Element)
// _10 = 2 * 1
t1.Square(t)
// _11 = 1 + _10
t1.Mul(t, t1)
// _1100 = _11 << 2
t2.Square(t1)
t2.Square(t2)
// _1111 = _11 + _1100
t1.Mul(t1, t2)
// _11110000 = _1111 << 4
t2.Square(t1)
for i := 0; i < 3; i++ {
t2.Square(t2)
}
// _11111111 = _1111 + _11110000
t1.Mul(t1, t2)
// x16 = _11111111<<8 + _11111111
t2.Square(t1)
for i := 0; i < 7; i++ {
t2.Square(t2)
}
t1.Mul(t1, t2)
// x32 = x16<<16 + x16
t2.Square(t1)
for i := 0; i < 15; i++ {
t2.Square(t2)
}
t1.Mul(t1, t2)
// x64 = x32<<32 + x32
t2.Square(t1)
for i := 0; i < 31; i++ {
t2.Square(t2)
}
t1.Mul(t1, t2)
// x65 = 2*x64 + 1
t2.Square(t1)
t2.Mul(t2, t)
// x129 = x65<<64 + x64
for i := 0; i < 64; i++ {
t2.Square(t2)
}
t1.Mul(t1, t2)
// x130 = 2*x129 + 1
t2.Square(t1)
t2.Mul(t2, t)
// x259 = x130<<129 + x129
for i := 0; i < 129; i++ {
t2.Square(t2)
}
t1.Mul(t1, t2)
// x260 = 2*x259 + 1
t2.Square(t1)
t2.Mul(t2, t)
// x519 = x260<<259 + x259
for i := 0; i < 259; i++ {
t2.Square(t2)
}
t1.Mul(t1, t2)
// return x519<<2 + 1
t1.Square(t1)
t1.Square(t1)
return e.Mul(t1, t)
}
|
