1
2
3
4
5 package elliptic
6
7 import (
8 "crypto/elliptic/internal/fiat"
9 "math/big"
10 )
11
12 type p521Curve struct {
13 *CurveParams
14 }
15
16 var p521 p521Curve
17 var p521Params *CurveParams
18
19 func initP521() {
20
21 p521.CurveParams = &CurveParams{Name: "P-521"}
22 p521.P, _ = new(big.Int).SetString("6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151", 10)
23 p521.N, _ = new(big.Int).SetString("6864797660130609714981900799081393217269435300143305409394463459185543183397655394245057746333217197532963996371363321113864768612440380340372808892707005449", 10)
24 p521.B, _ = new(big.Int).SetString("051953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00", 16)
25 p521.Gx, _ = new(big.Int).SetString("c6858e06b70404e9cd9e3ecb662395b4429c648139053fb521f828af606b4d3dbaa14b5e77efe75928fe1dc127a2ffa8de3348b3c1856a429bf97e7e31c2e5bd66", 16)
26 p521.Gy, _ = new(big.Int).SetString("11839296a789a3bc0045c8a5fb42c7d1bd998f54449579b446817afbd17273e662c97ee72995ef42640c550b9013fad0761353c7086a272c24088be94769fd16650", 16)
27 p521.BitSize = 521
28 }
29
30 func (curve p521Curve) Params() *CurveParams {
31 return curve.CurveParams
32 }
33
34 func (curve p521Curve) IsOnCurve(x, y *big.Int) bool {
35 x1 := bigIntToFiatP521(x)
36 y1 := bigIntToFiatP521(y)
37 b := bigIntToFiatP521(curve.B)
38
39
40 x3 := new(fiat.P521Element).Square(x1)
41 x3.Mul(x3, x1)
42
43 threeX := new(fiat.P521Element).Add(x1, x1)
44 threeX.Add(threeX, x1)
45
46 x3.Sub(x3, threeX)
47 x3.Add(x3, b)
48
49
50 y2 := new(fiat.P521Element).Square(y1)
51
52 return x3.Equal(y2) == 1
53 }
54
55 type p521Point struct {
56 x, y, z *fiat.P521Element
57 }
58
59 func fiatP521ToBigInt(x *fiat.P521Element) *big.Int {
60 xBytes := x.Bytes()
61 for i := range xBytes[:len(xBytes)/2] {
62 xBytes[i], xBytes[len(xBytes)-i-1] = xBytes[len(xBytes)-i-1], xBytes[i]
63 }
64 return new(big.Int).SetBytes(xBytes)
65 }
66
67
68
69
70 func (curve p521Curve) affineFromJacobian(p *p521Point) (x, y *big.Int) {
71 if p.z.IsZero() == 1 {
72 return new(big.Int), new(big.Int)
73 }
74
75 zinv := new(fiat.P521Element).Invert(p.z)
76 zinvsq := new(fiat.P521Element).Mul(zinv, zinv)
77
78 xx := new(fiat.P521Element).Mul(p.x, zinvsq)
79 zinvsq.Mul(zinvsq, zinv)
80 yy := new(fiat.P521Element).Mul(p.y, zinvsq)
81
82 return fiatP521ToBigInt(xx), fiatP521ToBigInt(yy)
83 }
84
85 func bigIntToFiatP521(x *big.Int) *fiat.P521Element {
86 xBytes := new(big.Int).Mod(x, p521.P).FillBytes(make([]byte, 66))
87 for i := range xBytes[:len(xBytes)/2] {
88 xBytes[i], xBytes[len(xBytes)-i-1] = xBytes[len(xBytes)-i-1], xBytes[i]
89 }
90 x1, err := new(fiat.P521Element).SetBytes(xBytes)
91 if err != nil {
92
93
94 panic("internal error: bigIntToFiatP521")
95 }
96 return x1
97 }
98
99
100
101
102 func (curve p521Curve) jacobianFromAffine(x, y *big.Int) *p521Point {
103
104
105 if x.Sign() == 0 && y.Sign() == 0 {
106 return &p521Point{
107 x: new(fiat.P521Element),
108 y: new(fiat.P521Element),
109 z: new(fiat.P521Element),
110 }
111 }
112 return &p521Point{
113 x: bigIntToFiatP521(x),
114 y: bigIntToFiatP521(y),
115 z: new(fiat.P521Element).One(),
116 }
117 }
118
119 func (curve p521Curve) Add(x1, y1, x2, y2 *big.Int) (*big.Int, *big.Int) {
120 p1 := curve.jacobianFromAffine(x1, y1)
121 p2 := curve.jacobianFromAffine(x2, y2)
122 return curve.affineFromJacobian(p1.addJacobian(p1, p2))
123 }
124
125
126 func (q *p521Point) addJacobian(p1, p2 *p521Point) *p521Point {
127
128 z1IsZero := p1.z.IsZero()
129 z2IsZero := p2.z.IsZero()
130
131 z1z1 := new(fiat.P521Element).Square(p1.z)
132 z2z2 := new(fiat.P521Element).Square(p2.z)
133
134 u1 := new(fiat.P521Element).Mul(p1.x, z2z2)
135 u2 := new(fiat.P521Element).Mul(p2.x, z1z1)
136 h := new(fiat.P521Element).Sub(u2, u1)
137 xEqual := h.IsZero() == 1
138 i := new(fiat.P521Element).Add(h, h)
139 i.Square(i)
140 j := new(fiat.P521Element).Mul(h, i)
141
142 s1 := new(fiat.P521Element).Mul(p1.y, p2.z)
143 s1.Mul(s1, z2z2)
144 s2 := new(fiat.P521Element).Mul(p2.y, p1.z)
145 s2.Mul(s2, z1z1)
146 r := new(fiat.P521Element).Sub(s2, s1)
147 yEqual := r.IsZero() == 1
148 if xEqual && yEqual && z1IsZero == 0 && z2IsZero == 0 {
149 return q.doubleJacobian(p1)
150 }
151 r.Add(r, r)
152 v := new(fiat.P521Element).Mul(u1, i)
153
154 x := new(fiat.P521Element).Set(r)
155 x.Square(x)
156 x.Sub(x, j)
157 x.Sub(x, v)
158 x.Sub(x, v)
159
160 y := new(fiat.P521Element).Set(r)
161 v.Sub(v, x)
162 y.Mul(y, v)
163 s1.Mul(s1, j)
164 s1.Add(s1, s1)
165 y.Sub(y, s1)
166
167 z := new(fiat.P521Element).Add(p1.z, p2.z)
168 z.Square(z)
169 z.Sub(z, z1z1)
170 z.Sub(z, z2z2)
171 z.Mul(z, h)
172
173 x.Select(p2.x, x, z1IsZero)
174 x.Select(p1.x, x, z2IsZero)
175 y.Select(p2.y, y, z1IsZero)
176 y.Select(p1.y, y, z2IsZero)
177 z.Select(p2.z, z, z1IsZero)
178 z.Select(p1.z, z, z2IsZero)
179
180 q.x.Set(x)
181 q.y.Set(y)
182 q.z.Set(z)
183 return q
184 }
185
186 func (curve p521Curve) Double(x1, y1 *big.Int) (*big.Int, *big.Int) {
187 p := curve.jacobianFromAffine(x1, y1)
188 return curve.affineFromJacobian(p.doubleJacobian(p))
189 }
190
191
192 func (q *p521Point) doubleJacobian(p *p521Point) *p521Point {
193
194 delta := new(fiat.P521Element).Square(p.z)
195 gamma := new(fiat.P521Element).Square(p.y)
196 alpha := new(fiat.P521Element).Sub(p.x, delta)
197 alpha2 := new(fiat.P521Element).Add(p.x, delta)
198 alpha.Mul(alpha, alpha2)
199 alpha2.Set(alpha)
200 alpha.Add(alpha, alpha)
201 alpha.Add(alpha, alpha2)
202
203 beta := alpha2.Mul(p.x, gamma)
204
205 q.x.Square(alpha)
206 beta8 := new(fiat.P521Element).Add(beta, beta)
207 beta8.Add(beta8, beta8)
208 beta8.Add(beta8, beta8)
209 q.x.Sub(q.x, beta8)
210
211 q.z.Add(p.y, p.z)
212 q.z.Square(q.z)
213 q.z.Sub(q.z, gamma)
214 q.z.Sub(q.z, delta)
215
216 beta.Add(beta, beta)
217 beta.Add(beta, beta)
218 beta.Sub(beta, q.x)
219 q.y.Mul(alpha, beta)
220
221 gamma.Square(gamma)
222 gamma.Add(gamma, gamma)
223 gamma.Add(gamma, gamma)
224 gamma.Add(gamma, gamma)
225
226 q.y.Sub(q.y, gamma)
227
228 return q
229 }
230
231 func (curve p521Curve) ScalarMult(Bx, By *big.Int, scalar []byte) (*big.Int, *big.Int) {
232 B := curve.jacobianFromAffine(Bx, By)
233 p, t := &p521Point{
234 x: new(fiat.P521Element),
235 y: new(fiat.P521Element),
236 z: new(fiat.P521Element),
237 }, &p521Point{
238 x: new(fiat.P521Element),
239 y: new(fiat.P521Element),
240 z: new(fiat.P521Element),
241 }
242
243 for _, byte := range scalar {
244 for bitNum := 0; bitNum < 8; bitNum++ {
245 p.doubleJacobian(p)
246 bit := (byte >> (7 - bitNum)) & 1
247 t.addJacobian(p, B)
248 p.x.Select(t.x, p.x, int(bit))
249 p.y.Select(t.y, p.y, int(bit))
250 p.z.Select(t.z, p.z, int(bit))
251 }
252 }
253
254 return curve.affineFromJacobian(p)
255 }
256
257 func (curve p521Curve) ScalarBaseMult(k []byte) (*big.Int, *big.Int) {
258 return curve.ScalarMult(curve.Gx, curve.Gy, k)
259 }
260
View as plain text