1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 package nistec
16
17 import (
18 "crypto/internal/fips140deps/byteorder"
19 "errors"
20 "math/bits"
21 "runtime"
22 "unsafe"
23 )
24
25
26
27 type p256Element [4]uint64
28
29
30 var p256One = p256Element{0x0000000000000001, 0xffffffff00000000,
31 0xffffffffffffffff, 0x00000000fffffffe}
32
33 var p256Zero = p256Element{}
34
35
36 var p256P = p256Element{0xffffffffffffffff, 0x00000000ffffffff,
37 0x0000000000000000, 0xffffffff00000001}
38
39
40
41 type P256Point struct {
42
43
44 x, y, z p256Element
45 }
46
47
48 func NewP256Point() *P256Point {
49 return &P256Point{
50 x: p256One, y: p256One, z: p256Zero,
51 }
52 }
53
54
55 func (p *P256Point) SetGenerator() *P256Point {
56 p.x = p256Element{0x79e730d418a9143c, 0x75ba95fc5fedb601,
57 0x79fb732b77622510, 0x18905f76a53755c6}
58 p.y = p256Element{0xddf25357ce95560a, 0x8b4ab8e4ba19e45c,
59 0xd2e88688dd21f325, 0x8571ff1825885d85}
60 p.z = p256One
61 return p
62 }
63
64
65 func (p *P256Point) Set(q *P256Point) *P256Point {
66 p.x, p.y, p.z = q.x, q.y, q.z
67 return p
68 }
69
70 const p256ElementLength = 32
71 const p256UncompressedLength = 1 + 2*p256ElementLength
72 const p256CompressedLength = 1 + p256ElementLength
73
74
75
76
77
78 func (p *P256Point) SetBytes(b []byte) (*P256Point, error) {
79
80
81
82 rr := p256Element{0x0000000000000003, 0xfffffffbffffffff,
83 0xfffffffffffffffe, 0x00000004fffffffd}
84
85 switch {
86
87 case len(b) == 1 && b[0] == 0:
88 return p.Set(NewP256Point()), nil
89
90
91 case len(b) == p256UncompressedLength && b[0] == 4:
92 var r P256Point
93 p256BigToLittle(&r.x, (*[32]byte)(b[1:33]))
94 p256BigToLittle(&r.y, (*[32]byte)(b[33:65]))
95 if p256LessThanP(&r.x) == 0 || p256LessThanP(&r.y) == 0 {
96 return nil, errors.New("invalid P256 element encoding")
97 }
98 p256Mul(&r.x, &r.x, &rr)
99 p256Mul(&r.y, &r.y, &rr)
100 if err := p256CheckOnCurve(&r.x, &r.y); err != nil {
101 return nil, err
102 }
103 r.z = p256One
104 return p.Set(&r), nil
105
106
107 case len(b) == p256CompressedLength && (b[0] == 2 || b[0] == 3):
108 var r P256Point
109 p256BigToLittle(&r.x, (*[32]byte)(b[1:33]))
110 if p256LessThanP(&r.x) == 0 {
111 return nil, errors.New("invalid P256 element encoding")
112 }
113 p256Mul(&r.x, &r.x, &rr)
114
115
116 p256Polynomial(&r.y, &r.x)
117 if !p256Sqrt(&r.y, &r.y) {
118 return nil, errors.New("invalid P256 compressed point encoding")
119 }
120
121
122
123 yy := new(p256Element)
124 p256FromMont(yy, &r.y)
125 cond := int(yy[0]&1) ^ int(b[0]&1)
126 p256NegCond(&r.y, cond)
127
128 r.z = p256One
129 return p.Set(&r), nil
130
131 default:
132 return nil, errors.New("invalid P256 point encoding")
133 }
134 }
135
136
137 func p256Polynomial(y2, x *p256Element) *p256Element {
138 x3 := new(p256Element)
139 p256Sqr(x3, x, 1)
140 p256Mul(x3, x3, x)
141
142 threeX := new(p256Element)
143 p256Add(threeX, x, x)
144 p256Add(threeX, threeX, x)
145 p256NegCond(threeX, 1)
146
147 p256B := &p256Element{0xd89cdf6229c4bddf, 0xacf005cd78843090,
148 0xe5a220abf7212ed6, 0xdc30061d04874834}
149
150 p256Add(x3, x3, threeX)
151 p256Add(x3, x3, p256B)
152
153 *y2 = *x3
154 return y2
155 }
156
157 func p256CheckOnCurve(x, y *p256Element) error {
158
159 rhs := p256Polynomial(new(p256Element), x)
160 lhs := new(p256Element)
161 p256Sqr(lhs, y, 1)
162 if p256Equal(lhs, rhs) != 1 {
163 return errors.New("P256 point not on curve")
164 }
165 return nil
166 }
167
168
169
170
171 func p256LessThanP(x *p256Element) int {
172 var b uint64
173 _, b = bits.Sub64(x[0], p256P[0], b)
174 _, b = bits.Sub64(x[1], p256P[1], b)
175 _, b = bits.Sub64(x[2], p256P[2], b)
176 _, b = bits.Sub64(x[3], p256P[3], b)
177 return int(b)
178 }
179
180 func p256BigToLittle(l *p256Element, b *[32]byte) {
181 bytesToLimbs((*[4]uint64)(l), b)
182 }
183
184 func bytesToLimbs(l *[4]uint64, b *[32]byte) {
185 l[0] = byteorder.BEUint64(b[24:])
186 l[1] = byteorder.BEUint64(b[16:])
187 l[2] = byteorder.BEUint64(b[8:])
188 l[3] = byteorder.BEUint64(b[:])
189 }
190
191 func p256LittleToBig(b *[32]byte, l *p256Element) {
192 limbsToBytes(b, (*[4]uint64)(l))
193 }
194
195 func limbsToBytes(b *[32]byte, l *[4]uint64) {
196 byteorder.BEPutUint64(b[24:], l[0])
197 byteorder.BEPutUint64(b[16:], l[1])
198 byteorder.BEPutUint64(b[8:], l[2])
199 byteorder.BEPutUint64(b[:], l[3])
200 }
201
202
203 func p256Add(res, x, y *p256Element) {
204 var c, b uint64
205 t1 := make([]uint64, 4)
206 t1[0], c = bits.Add64(x[0], y[0], 0)
207 t1[1], c = bits.Add64(x[1], y[1], c)
208 t1[2], c = bits.Add64(x[2], y[2], c)
209 t1[3], c = bits.Add64(x[3], y[3], c)
210 t2 := make([]uint64, 4)
211 t2[0], b = bits.Sub64(t1[0], p256P[0], 0)
212 t2[1], b = bits.Sub64(t1[1], p256P[1], b)
213 t2[2], b = bits.Sub64(t1[2], p256P[2], b)
214 t2[3], b = bits.Sub64(t1[3], p256P[3], b)
215
216
217
218
219
220
221
222 t2Mask := (c ^ b) - 1
223 res[0] = (t1[0] & ^t2Mask) | (t2[0] & t2Mask)
224 res[1] = (t1[1] & ^t2Mask) | (t2[1] & t2Mask)
225 res[2] = (t1[2] & ^t2Mask) | (t2[2] & t2Mask)
226 res[3] = (t1[3] & ^t2Mask) | (t2[3] & t2Mask)
227 }
228
229
230
231 func p256Sqrt(e, x *p256Element) (isSquare bool) {
232 t0, t1 := new(p256Element), new(p256Element)
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249 p256Sqr(t0, x, 1)
250 p256Mul(t0, x, t0)
251 p256Sqr(t1, t0, 2)
252 p256Mul(t0, t0, t1)
253 p256Sqr(t1, t0, 4)
254 p256Mul(t0, t0, t1)
255 p256Sqr(t1, t0, 8)
256 p256Mul(t0, t0, t1)
257 p256Sqr(t1, t0, 16)
258 p256Mul(t0, t0, t1)
259 p256Sqr(t0, t0, 32)
260 p256Mul(t0, x, t0)
261 p256Sqr(t0, t0, 96)
262 p256Mul(t0, x, t0)
263 p256Sqr(t0, t0, 94)
264
265 p256Sqr(t1, t0, 1)
266 if p256Equal(t1, x) != 1 {
267 return false
268 }
269 *e = *t0
270 return true
271 }
272
273
274
275
276
277
278 func p256Mul(res, in1, in2 *p256Element)
279
280
281
282
283 func p256Sqr(res, in *p256Element, n int)
284
285
286
287
288
289 func p256FromMont(res, in *p256Element)
290
291
292
293
294 func p256NegCond(val *p256Element, cond int)
295
296
297
298
299 func p256MovCond(res, a, b *P256Point, cond int)
300
301
302
303
304 type p256Table [16]P256Point
305
306
307
308
309
310 func p256Select(res *P256Point, table *p256Table, idx int)
311
312
313
314 type p256AffinePoint struct {
315 x, y p256Element
316 }
317
318
319
320 type p256AffineTable [32]p256AffinePoint
321
322
323
324
325
326
327
328
329 var p256Precomputed *[43]p256AffineTable
330
331 func init() {
332 p256PrecomputedPtr := unsafe.Pointer(&p256PrecomputedEmbed)
333 if runtime.GOARCH == "s390x" {
334 var newTable [43 * 32 * 2 * 4]uint64
335 for i, x := range (*[43 * 32 * 2 * 4][8]byte)(p256PrecomputedPtr) {
336 newTable[i] = byteorder.LEUint64(x[:])
337 }
338 p256PrecomputedPtr = unsafe.Pointer(&newTable)
339 }
340 p256Precomputed = (*[43]p256AffineTable)(p256PrecomputedPtr)
341 }
342
343
344
345
346
347 func p256SelectAffine(res *p256AffinePoint, table *p256AffineTable, idx int)
348
349
350
351
352
353
354 func p256PointAddAffineAsm(res, in1 *P256Point, in2 *p256AffinePoint, sign, sel, zero int)
355
356
357
358
359
360
361 func p256PointAddAsm(res, in1, in2 *P256Point) int
362
363
364
365
366 func p256PointDoubleAsm(res, in *P256Point)
367
368
369
370 type p256OrdElement [4]uint64
371
372
373 func p256OrdReduce(s *p256OrdElement) {
374
375
376 t0, b := bits.Sub64(s[0], 0xf3b9cac2fc632551, 0)
377 t1, b := bits.Sub64(s[1], 0xbce6faada7179e84, b)
378 t2, b := bits.Sub64(s[2], 0xffffffffffffffff, b)
379 t3, b := bits.Sub64(s[3], 0xffffffff00000000, b)
380 tMask := b - 1
381 s[0] ^= (t0 ^ s[0]) & tMask
382 s[1] ^= (t1 ^ s[1]) & tMask
383 s[2] ^= (t2 ^ s[2]) & tMask
384 s[3] ^= (t3 ^ s[3]) & tMask
385 }
386
387 func p256OrdLittleToBig(b *[32]byte, l *p256OrdElement) {
388 limbsToBytes(b, (*[4]uint64)(l))
389 }
390
391 func p256OrdBigToLittle(l *p256OrdElement, b *[32]byte) {
392 bytesToLimbs((*[4]uint64)(l), b)
393 }
394
395
396 func (q *P256Point) Add(r1, r2 *P256Point) *P256Point {
397 var sum, double P256Point
398 r1IsInfinity := r1.isInfinity()
399 r2IsInfinity := r2.isInfinity()
400 pointsEqual := p256PointAddAsm(&sum, r1, r2)
401 p256PointDoubleAsm(&double, r1)
402 p256MovCond(&sum, &double, &sum, pointsEqual)
403 p256MovCond(&sum, r1, &sum, r2IsInfinity)
404 p256MovCond(&sum, r2, &sum, r1IsInfinity)
405 return q.Set(&sum)
406 }
407
408
409 func (q *P256Point) Double(p *P256Point) *P256Point {
410 var double P256Point
411 p256PointDoubleAsm(&double, p)
412 return q.Set(&double)
413 }
414
415
416
417
418 func (r *P256Point) ScalarBaseMult(scalar []byte) (*P256Point, error) {
419 if len(scalar) != 32 {
420 return nil, errors.New("invalid scalar length")
421 }
422 scalarReversed := new(p256OrdElement)
423 p256OrdBigToLittle(scalarReversed, (*[32]byte)(scalar))
424 p256OrdReduce(scalarReversed)
425
426 r.p256BaseMult(scalarReversed)
427 return r, nil
428 }
429
430
431
432
433 func (r *P256Point) ScalarMult(q *P256Point, scalar []byte) (*P256Point, error) {
434 if len(scalar) != 32 {
435 return nil, errors.New("invalid scalar length")
436 }
437 scalarReversed := new(p256OrdElement)
438 p256OrdBigToLittle(scalarReversed, (*[32]byte)(scalar))
439 p256OrdReduce(scalarReversed)
440
441 r.Set(q).p256ScalarMult(scalarReversed)
442 return r, nil
443 }
444
445
446 func uint64IsZero(x uint64) int {
447 x = ^x
448 x &= x >> 32
449 x &= x >> 16
450 x &= x >> 8
451 x &= x >> 4
452 x &= x >> 2
453 x &= x >> 1
454 return int(x & 1)
455 }
456
457
458 func p256Equal(a, b *p256Element) int {
459 var acc uint64
460 for i := range a {
461 acc |= a[i] ^ b[i]
462 }
463 return uint64IsZero(acc)
464 }
465
466
467 func (p *P256Point) isInfinity() int {
468 return p256Equal(&p.z, &p256Zero)
469 }
470
471
472
473
474 func (p *P256Point) Bytes() []byte {
475
476
477 var out [p256UncompressedLength]byte
478 return p.bytes(&out)
479 }
480
481 func (p *P256Point) bytes(out *[p256UncompressedLength]byte) []byte {
482
483 if p.isInfinity() == 1 {
484 return append(out[:0], 0)
485 }
486
487 x, y := new(p256Element), new(p256Element)
488 p.affineFromMont(x, y)
489
490 out[0] = 4
491 p256LittleToBig((*[32]byte)(out[1:33]), x)
492 p256LittleToBig((*[32]byte)(out[33:65]), y)
493
494 return out[:]
495 }
496
497
498
499 func (p *P256Point) affineFromMont(x, y *p256Element) {
500 p256Inverse(y, &p.z)
501 p256Sqr(x, y, 1)
502 p256Mul(y, y, x)
503
504 p256Mul(x, &p.x, x)
505 p256Mul(y, &p.y, y)
506
507 p256FromMont(x, x)
508 p256FromMont(y, y)
509 }
510
511
512
513 func (p *P256Point) BytesX() ([]byte, error) {
514
515
516 var out [p256ElementLength]byte
517 return p.bytesX(&out)
518 }
519
520 func (p *P256Point) bytesX(out *[p256ElementLength]byte) ([]byte, error) {
521 if p.isInfinity() == 1 {
522 return nil, errors.New("P256 point is the point at infinity")
523 }
524
525 x := new(p256Element)
526 p256Inverse(x, &p.z)
527 p256Sqr(x, x, 1)
528 p256Mul(x, &p.x, x)
529 p256FromMont(x, x)
530 p256LittleToBig((*[32]byte)(out[:]), x)
531
532 return out[:], nil
533 }
534
535
536
537
538 func (p *P256Point) BytesCompressed() []byte {
539
540
541 var out [p256CompressedLength]byte
542 return p.bytesCompressed(&out)
543 }
544
545 func (p *P256Point) bytesCompressed(out *[p256CompressedLength]byte) []byte {
546 if p.isInfinity() == 1 {
547 return append(out[:0], 0)
548 }
549
550 x, y := new(p256Element), new(p256Element)
551 p.affineFromMont(x, y)
552
553 out[0] = 2 | byte(y[0]&1)
554 p256LittleToBig((*[32]byte)(out[1:33]), x)
555
556 return out[:]
557 }
558
559
560 func (q *P256Point) Select(p1, p2 *P256Point, cond int) *P256Point {
561 p256MovCond(q, p1, p2, cond)
562 return q
563 }
564
565
566 func p256Inverse(out, in *p256Element) {
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589 var z = new(p256Element)
590 var t0 = new(p256Element)
591 var t1 = new(p256Element)
592
593 p256Sqr(z, in, 1)
594 p256Mul(z, in, z)
595 p256Sqr(z, z, 1)
596 p256Mul(z, in, z)
597 p256Sqr(t0, z, 3)
598 p256Mul(t0, z, t0)
599 p256Sqr(t1, t0, 6)
600 p256Mul(t0, t0, t1)
601 p256Sqr(t0, t0, 3)
602 p256Mul(z, z, t0)
603 p256Sqr(t0, z, 1)
604 p256Mul(t0, in, t0)
605 p256Sqr(t1, t0, 16)
606 p256Mul(t0, t0, t1)
607 p256Sqr(t0, t0, 15)
608 p256Mul(z, z, t0)
609 p256Sqr(t0, t0, 17)
610 p256Mul(t0, in, t0)
611 p256Sqr(t0, t0, 143)
612 p256Mul(t0, z, t0)
613 p256Sqr(t0, t0, 47)
614 p256Mul(z, z, t0)
615 p256Sqr(z, z, 2)
616 p256Mul(out, in, z)
617 }
618
619 func boothW5(in uint) (int, int) {
620 var s uint = ^((in >> 5) - 1)
621 var d uint = (1 << 6) - in - 1
622 d = (d & s) | (in & (^s))
623 d = (d >> 1) + (d & 1)
624 return int(d), int(s & 1)
625 }
626
627 func boothW6(in uint) (int, int) {
628 var s uint = ^((in >> 6) - 1)
629 var d uint = (1 << 7) - in - 1
630 d = (d & s) | (in & (^s))
631 d = (d >> 1) + (d & 1)
632 return int(d), int(s & 1)
633 }
634
635 func (p *P256Point) p256BaseMult(scalar *p256OrdElement) {
636 var t0 p256AffinePoint
637
638 wvalue := (scalar[0] << 1) & 0x7f
639 sel, sign := boothW6(uint(wvalue))
640 p256SelectAffine(&t0, &p256Precomputed[0], sel)
641 p.x, p.y, p.z = t0.x, t0.y, p256One
642 p256NegCond(&p.y, sign)
643
644 index := uint(5)
645 zero := sel
646
647 for i := 1; i < 43; i++ {
648 if index < 192 {
649 wvalue = ((scalar[index/64] >> (index % 64)) + (scalar[index/64+1] << (64 - (index % 64)))) & 0x7f
650 } else {
651 wvalue = (scalar[index/64] >> (index % 64)) & 0x7f
652 }
653 index += 6
654 sel, sign = boothW6(uint(wvalue))
655 p256SelectAffine(&t0, &p256Precomputed[i], sel)
656 p256PointAddAffineAsm(p, p, &t0, sign, sel, zero)
657 zero |= sel
658 }
659
660
661 p256MovCond(p, p, NewP256Point(), zero)
662 }
663
664 func (p *P256Point) p256ScalarMult(scalar *p256OrdElement) {
665
666
667 var precomp p256Table
668 var t0, t1, t2, t3 P256Point
669
670
671 precomp[0] = *p
672
673 p256PointDoubleAsm(&t0, p)
674 p256PointDoubleAsm(&t1, &t0)
675 p256PointDoubleAsm(&t2, &t1)
676 p256PointDoubleAsm(&t3, &t2)
677 precomp[1] = t0
678 precomp[3] = t1
679 precomp[7] = t2
680 precomp[15] = t3
681
682 p256PointAddAsm(&t0, &t0, p)
683 p256PointAddAsm(&t1, &t1, p)
684 p256PointAddAsm(&t2, &t2, p)
685 precomp[2] = t0
686 precomp[4] = t1
687 precomp[8] = t2
688
689 p256PointDoubleAsm(&t0, &t0)
690 p256PointDoubleAsm(&t1, &t1)
691 precomp[5] = t0
692 precomp[9] = t1
693
694 p256PointAddAsm(&t2, &t0, p)
695 p256PointAddAsm(&t1, &t1, p)
696 precomp[6] = t2
697 precomp[10] = t1
698
699 p256PointDoubleAsm(&t0, &t0)
700 p256PointDoubleAsm(&t2, &t2)
701 precomp[11] = t0
702 precomp[13] = t2
703
704 p256PointAddAsm(&t0, &t0, p)
705 p256PointAddAsm(&t2, &t2, p)
706 precomp[12] = t0
707 precomp[14] = t2
708
709
710 index := uint(254)
711 var sel, sign int
712
713 wvalue := (scalar[index/64] >> (index % 64)) & 0x3f
714 sel, _ = boothW5(uint(wvalue))
715
716 p256Select(p, &precomp, sel)
717 zero := sel
718
719 for index > 4 {
720 index -= 5
721 p256PointDoubleAsm(p, p)
722 p256PointDoubleAsm(p, p)
723 p256PointDoubleAsm(p, p)
724 p256PointDoubleAsm(p, p)
725 p256PointDoubleAsm(p, p)
726
727 if index < 192 {
728 wvalue = ((scalar[index/64] >> (index % 64)) + (scalar[index/64+1] << (64 - (index % 64)))) & 0x3f
729 } else {
730 wvalue = (scalar[index/64] >> (index % 64)) & 0x3f
731 }
732
733 sel, sign = boothW5(uint(wvalue))
734
735 p256Select(&t0, &precomp, sel)
736 p256NegCond(&t0.y, sign)
737 p256PointAddAsm(&t1, p, &t0)
738 p256MovCond(&t1, &t1, p, sel)
739 p256MovCond(p, &t1, &t0, zero)
740 zero |= sel
741 }
742
743 p256PointDoubleAsm(p, p)
744 p256PointDoubleAsm(p, p)
745 p256PointDoubleAsm(p, p)
746 p256PointDoubleAsm(p, p)
747 p256PointDoubleAsm(p, p)
748
749 wvalue = (scalar[0] << 1) & 0x3f
750 sel, sign = boothW5(uint(wvalue))
751
752 p256Select(&t0, &precomp, sel)
753 p256NegCond(&t0.y, sign)
754 p256PointAddAsm(&t1, p, &t0)
755 p256MovCond(&t1, &t1, p, sel)
756 p256MovCond(p, &t1, &t0, zero)
757 }
758
View as plain text