1
2
3
4
5
6
7
8
9 package nistec
10
11 import (
12 "crypto/internal/nistec/fiat"
13 "crypto/subtle"
14 "errors"
15 "sync"
16 )
17
18
19
20 const p256ElementLength = 32
21
22
23 type P256Point struct {
24
25
26 x, y, z *fiat.P256Element
27 }
28
29
30 func NewP256Point() *P256Point {
31 return &P256Point{
32 x: new(fiat.P256Element),
33 y: new(fiat.P256Element).One(),
34 z: new(fiat.P256Element),
35 }
36 }
37
38
39 func (p *P256Point) SetGenerator() *P256Point {
40 p.x.SetBytes([]byte{0x6b, 0x17, 0xd1, 0xf2, 0xe1, 0x2c, 0x42, 0x47, 0xf8, 0xbc, 0xe6, 0xe5, 0x63, 0xa4, 0x40, 0xf2, 0x77, 0x3, 0x7d, 0x81, 0x2d, 0xeb, 0x33, 0xa0, 0xf4, 0xa1, 0x39, 0x45, 0xd8, 0x98, 0xc2, 0x96})
41 p.y.SetBytes([]byte{0x4f, 0xe3, 0x42, 0xe2, 0xfe, 0x1a, 0x7f, 0x9b, 0x8e, 0xe7, 0xeb, 0x4a, 0x7c, 0xf, 0x9e, 0x16, 0x2b, 0xce, 0x33, 0x57, 0x6b, 0x31, 0x5e, 0xce, 0xcb, 0xb6, 0x40, 0x68, 0x37, 0xbf, 0x51, 0xf5})
42 p.z.One()
43 return p
44 }
45
46
47 func (p *P256Point) Set(q *P256Point) *P256Point {
48 p.x.Set(q.x)
49 p.y.Set(q.y)
50 p.z.Set(q.z)
51 return p
52 }
53
54
55
56
57
58 func (p *P256Point) SetBytes(b []byte) (*P256Point, error) {
59 switch {
60
61 case len(b) == 1 && b[0] == 0:
62 return p.Set(NewP256Point()), nil
63
64
65 case len(b) == 1+2*p256ElementLength && b[0] == 4:
66 x, err := new(fiat.P256Element).SetBytes(b[1 : 1+p256ElementLength])
67 if err != nil {
68 return nil, err
69 }
70 y, err := new(fiat.P256Element).SetBytes(b[1+p256ElementLength:])
71 if err != nil {
72 return nil, err
73 }
74 if err := p256CheckOnCurve(x, y); err != nil {
75 return nil, err
76 }
77 p.x.Set(x)
78 p.y.Set(y)
79 p.z.One()
80 return p, nil
81
82
83 case len(b) == 1+p256ElementLength && (b[0] == 2 || b[0] == 3):
84 x, err := new(fiat.P256Element).SetBytes(b[1:])
85 if err != nil {
86 return nil, err
87 }
88
89
90 y := p256Polynomial(new(fiat.P256Element), x)
91 if !p256Sqrt(y, y) {
92 return nil, errors.New("invalid P256 compressed point encoding")
93 }
94
95
96
97 otherRoot := new(fiat.P256Element)
98 otherRoot.Sub(otherRoot, y)
99 cond := y.Bytes()[p256ElementLength-1]&1 ^ b[0]&1
100 y.Select(otherRoot, y, int(cond))
101
102 p.x.Set(x)
103 p.y.Set(y)
104 p.z.One()
105 return p, nil
106
107 default:
108 return nil, errors.New("invalid P256 point encoding")
109 }
110 }
111
112 var _p256B *fiat.P256Element
113 var _p256BOnce sync.Once
114
115 func p256B() *fiat.P256Element {
116 _p256BOnce.Do(func() {
117 _p256B, _ = new(fiat.P256Element).SetBytes([]byte{0x5a, 0xc6, 0x35, 0xd8, 0xaa, 0x3a, 0x93, 0xe7, 0xb3, 0xeb, 0xbd, 0x55, 0x76, 0x98, 0x86, 0xbc, 0x65, 0x1d, 0x6, 0xb0, 0xcc, 0x53, 0xb0, 0xf6, 0x3b, 0xce, 0x3c, 0x3e, 0x27, 0xd2, 0x60, 0x4b})
118 })
119 return _p256B
120 }
121
122
123 func p256Polynomial(y2, x *fiat.P256Element) *fiat.P256Element {
124 y2.Square(x)
125 y2.Mul(y2, x)
126
127 threeX := new(fiat.P256Element).Add(x, x)
128 threeX.Add(threeX, x)
129 y2.Sub(y2, threeX)
130
131 return y2.Add(y2, p256B())
132 }
133
134 func p256CheckOnCurve(x, y *fiat.P256Element) error {
135
136 rhs := p256Polynomial(new(fiat.P256Element), x)
137 lhs := new(fiat.P256Element).Square(y)
138 if rhs.Equal(lhs) != 1 {
139 return errors.New("P256 point not on curve")
140 }
141 return nil
142 }
143
144
145
146
147 func (p *P256Point) Bytes() []byte {
148
149
150 var out [1 + 2*p256ElementLength]byte
151 return p.bytes(&out)
152 }
153
154 func (p *P256Point) bytes(out *[1 + 2*p256ElementLength]byte) []byte {
155 if p.z.IsZero() == 1 {
156 return append(out[:0], 0)
157 }
158
159 zinv := new(fiat.P256Element).Invert(p.z)
160 x := new(fiat.P256Element).Mul(p.x, zinv)
161 y := new(fiat.P256Element).Mul(p.y, zinv)
162
163 buf := append(out[:0], 4)
164 buf = append(buf, x.Bytes()...)
165 buf = append(buf, y.Bytes()...)
166 return buf
167 }
168
169
170
171 func (p *P256Point) BytesX() ([]byte, error) {
172
173
174 var out [p256ElementLength]byte
175 return p.bytesX(&out)
176 }
177
178 func (p *P256Point) bytesX(out *[p256ElementLength]byte) ([]byte, error) {
179 if p.z.IsZero() == 1 {
180 return nil, errors.New("P256 point is the point at infinity")
181 }
182
183 zinv := new(fiat.P256Element).Invert(p.z)
184 x := new(fiat.P256Element).Mul(p.x, zinv)
185
186 return append(out[:0], x.Bytes()...), nil
187 }
188
189
190
191
192 func (p *P256Point) BytesCompressed() []byte {
193
194
195 var out [1 + p256ElementLength]byte
196 return p.bytesCompressed(&out)
197 }
198
199 func (p *P256Point) bytesCompressed(out *[1 + p256ElementLength]byte) []byte {
200 if p.z.IsZero() == 1 {
201 return append(out[:0], 0)
202 }
203
204 zinv := new(fiat.P256Element).Invert(p.z)
205 x := new(fiat.P256Element).Mul(p.x, zinv)
206 y := new(fiat.P256Element).Mul(p.y, zinv)
207
208
209
210 buf := append(out[:0], 2)
211 buf[0] |= y.Bytes()[p256ElementLength-1] & 1
212 buf = append(buf, x.Bytes()...)
213 return buf
214 }
215
216
217 func (q *P256Point) Add(p1, p2 *P256Point) *P256Point {
218
219
220
221 t0 := new(fiat.P256Element).Mul(p1.x, p2.x)
222 t1 := new(fiat.P256Element).Mul(p1.y, p2.y)
223 t2 := new(fiat.P256Element).Mul(p1.z, p2.z)
224 t3 := new(fiat.P256Element).Add(p1.x, p1.y)
225 t4 := new(fiat.P256Element).Add(p2.x, p2.y)
226 t3.Mul(t3, t4)
227 t4.Add(t0, t1)
228 t3.Sub(t3, t4)
229 t4.Add(p1.y, p1.z)
230 x3 := new(fiat.P256Element).Add(p2.y, p2.z)
231 t4.Mul(t4, x3)
232 x3.Add(t1, t2)
233 t4.Sub(t4, x3)
234 x3.Add(p1.x, p1.z)
235 y3 := new(fiat.P256Element).Add(p2.x, p2.z)
236 x3.Mul(x3, y3)
237 y3.Add(t0, t2)
238 y3.Sub(x3, y3)
239 z3 := new(fiat.P256Element).Mul(p256B(), t2)
240 x3.Sub(y3, z3)
241 z3.Add(x3, x3)
242 x3.Add(x3, z3)
243 z3.Sub(t1, x3)
244 x3.Add(t1, x3)
245 y3.Mul(p256B(), y3)
246 t1.Add(t2, t2)
247 t2.Add(t1, t2)
248 y3.Sub(y3, t2)
249 y3.Sub(y3, t0)
250 t1.Add(y3, y3)
251 y3.Add(t1, y3)
252 t1.Add(t0, t0)
253 t0.Add(t1, t0)
254 t0.Sub(t0, t2)
255 t1.Mul(t4, y3)
256 t2.Mul(t0, y3)
257 y3.Mul(x3, z3)
258 y3.Add(y3, t2)
259 x3.Mul(t3, x3)
260 x3.Sub(x3, t1)
261 z3.Mul(t4, z3)
262 t1.Mul(t3, t0)
263 z3.Add(z3, t1)
264
265 q.x.Set(x3)
266 q.y.Set(y3)
267 q.z.Set(z3)
268 return q
269 }
270
271
272 func (q *P256Point) Double(p *P256Point) *P256Point {
273
274
275
276 t0 := new(fiat.P256Element).Square(p.x)
277 t1 := new(fiat.P256Element).Square(p.y)
278 t2 := new(fiat.P256Element).Square(p.z)
279 t3 := new(fiat.P256Element).Mul(p.x, p.y)
280 t3.Add(t3, t3)
281 z3 := new(fiat.P256Element).Mul(p.x, p.z)
282 z3.Add(z3, z3)
283 y3 := new(fiat.P256Element).Mul(p256B(), t2)
284 y3.Sub(y3, z3)
285 x3 := new(fiat.P256Element).Add(y3, y3)
286 y3.Add(x3, y3)
287 x3.Sub(t1, y3)
288 y3.Add(t1, y3)
289 y3.Mul(x3, y3)
290 x3.Mul(x3, t3)
291 t3.Add(t2, t2)
292 t2.Add(t2, t3)
293 z3.Mul(p256B(), z3)
294 z3.Sub(z3, t2)
295 z3.Sub(z3, t0)
296 t3.Add(z3, z3)
297 z3.Add(z3, t3)
298 t3.Add(t0, t0)
299 t0.Add(t3, t0)
300 t0.Sub(t0, t2)
301 t0.Mul(t0, z3)
302 y3.Add(y3, t0)
303 t0.Mul(p.y, p.z)
304 t0.Add(t0, t0)
305 z3.Mul(t0, z3)
306 x3.Sub(x3, z3)
307 z3.Mul(t0, t1)
308 z3.Add(z3, z3)
309 z3.Add(z3, z3)
310
311 q.x.Set(x3)
312 q.y.Set(y3)
313 q.z.Set(z3)
314 return q
315 }
316
317
318 func (q *P256Point) Select(p1, p2 *P256Point, cond int) *P256Point {
319 q.x.Select(p1.x, p2.x, cond)
320 q.y.Select(p1.y, p2.y, cond)
321 q.z.Select(p1.z, p2.z, cond)
322 return q
323 }
324
325
326
327
328 type p256Table [15]*P256Point
329
330
331
332 func (table *p256Table) Select(p *P256Point, n uint8) {
333 if n >= 16 {
334 panic("nistec: internal error: p256Table called with out-of-bounds value")
335 }
336 p.Set(NewP256Point())
337 for i := uint8(1); i < 16; i++ {
338 cond := subtle.ConstantTimeByteEq(i, n)
339 p.Select(table[i-1], p, cond)
340 }
341 }
342
343
344 func (p *P256Point) ScalarMult(q *P256Point, scalar []byte) (*P256Point, error) {
345
346
347 var table = p256Table{NewP256Point(), NewP256Point(), NewP256Point(),
348 NewP256Point(), NewP256Point(), NewP256Point(), NewP256Point(),
349 NewP256Point(), NewP256Point(), NewP256Point(), NewP256Point(),
350 NewP256Point(), NewP256Point(), NewP256Point(), NewP256Point()}
351 table[0].Set(q)
352 for i := 1; i < 15; i += 2 {
353 table[i].Double(table[i/2])
354 table[i+1].Add(table[i], q)
355 }
356
357
358
359 t := NewP256Point()
360 p.Set(NewP256Point())
361 for i, byte := range scalar {
362
363
364 if i != 0 {
365 p.Double(p)
366 p.Double(p)
367 p.Double(p)
368 p.Double(p)
369 }
370
371 windowValue := byte >> 4
372 table.Select(t, windowValue)
373 p.Add(p, t)
374
375 p.Double(p)
376 p.Double(p)
377 p.Double(p)
378 p.Double(p)
379
380 windowValue = byte & 0b1111
381 table.Select(t, windowValue)
382 p.Add(p, t)
383 }
384
385 return p, nil
386 }
387
388 var p256GeneratorTable *[p256ElementLength * 2]p256Table
389 var p256GeneratorTableOnce sync.Once
390
391
392
393
394 func (p *P256Point) generatorTable() *[p256ElementLength * 2]p256Table {
395 p256GeneratorTableOnce.Do(func() {
396 p256GeneratorTable = new([p256ElementLength * 2]p256Table)
397 base := NewP256Point().SetGenerator()
398 for i := 0; i < p256ElementLength*2; i++ {
399 p256GeneratorTable[i][0] = NewP256Point().Set(base)
400 for j := 1; j < 15; j++ {
401 p256GeneratorTable[i][j] = NewP256Point().Add(p256GeneratorTable[i][j-1], base)
402 }
403 base.Double(base)
404 base.Double(base)
405 base.Double(base)
406 base.Double(base)
407 }
408 })
409 return p256GeneratorTable
410 }
411
412
413
414 func (p *P256Point) ScalarBaseMult(scalar []byte) (*P256Point, error) {
415 if len(scalar) != p256ElementLength {
416 return nil, errors.New("invalid scalar length")
417 }
418 tables := p.generatorTable()
419
420
421
422
423
424
425
426 t := NewP256Point()
427 p.Set(NewP256Point())
428 tableIndex := len(tables) - 1
429 for _, byte := range scalar {
430 windowValue := byte >> 4
431 tables[tableIndex].Select(t, windowValue)
432 p.Add(p, t)
433 tableIndex--
434
435 windowValue = byte & 0b1111
436 tables[tableIndex].Select(t, windowValue)
437 p.Add(p, t)
438 tableIndex--
439 }
440
441 return p, nil
442 }
443
444
445
446 func p256Sqrt(e, x *fiat.P256Element) (isSquare bool) {
447 candidate := new(fiat.P256Element)
448 p256SqrtCandidate(candidate, x)
449 square := new(fiat.P256Element).Square(candidate)
450 if square.Equal(x) != 1 {
451 return false
452 }
453 e.Set(candidate)
454 return true
455 }
456
457
458 func p256SqrtCandidate(z, x *fiat.P256Element) {
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474 var t0 = new(fiat.P256Element)
475
476 z.Square(x)
477 z.Mul(x, z)
478 t0.Square(z)
479 for s := 1; s < 2; s++ {
480 t0.Square(t0)
481 }
482 z.Mul(z, t0)
483 t0.Square(z)
484 for s := 1; s < 4; s++ {
485 t0.Square(t0)
486 }
487 z.Mul(z, t0)
488 t0.Square(z)
489 for s := 1; s < 8; s++ {
490 t0.Square(t0)
491 }
492 z.Mul(z, t0)
493 t0.Square(z)
494 for s := 1; s < 16; s++ {
495 t0.Square(t0)
496 }
497 z.Mul(z, t0)
498 for s := 0; s < 32; s++ {
499 z.Square(z)
500 }
501 z.Mul(x, z)
502 for s := 0; s < 96; s++ {
503 z.Square(z)
504 }
505 z.Mul(x, z)
506 for s := 0; s < 94; s++ {
507 z.Square(z)
508 }
509 }
510
View as plain text