1
2
3
4
5 package elliptic
6
7
8
9
10
11
12 import (
13 "math/big"
14 )
15
16 var p224 p224Curve
17
18 type p224Curve struct {
19 *CurveParams
20 gx, gy, b p224FieldElement
21 }
22
23 func initP224() {
24
25 p224.CurveParams = &CurveParams{Name: "P-224"}
26 p224.P, _ = new(big.Int).SetString("26959946667150639794667015087019630673557916260026308143510066298881", 10)
27 p224.N, _ = new(big.Int).SetString("26959946667150639794667015087019625940457807714424391721682722368061", 10)
28 p224.B, _ = new(big.Int).SetString("b4050a850c04b3abf54132565044b0b7d7bfd8ba270b39432355ffb4", 16)
29 p224.Gx, _ = new(big.Int).SetString("b70e0cbd6bb4bf7f321390b94a03c1d356c21122343280d6115c1d21", 16)
30 p224.Gy, _ = new(big.Int).SetString("bd376388b5f723fb4c22dfe6cd4375a05a07476444d5819985007e34", 16)
31 p224.BitSize = 224
32
33 p224FromBig(&p224.gx, p224.Gx)
34 p224FromBig(&p224.gy, p224.Gy)
35 p224FromBig(&p224.b, p224.B)
36 }
37
38
39
40
41 func P224() Curve {
42 initonce.Do(initAll)
43 return p224
44 }
45
46 func (curve p224Curve) Params() *CurveParams {
47 return curve.CurveParams
48 }
49
50 func (curve p224Curve) IsOnCurve(bigX, bigY *big.Int) bool {
51 var x, y p224FieldElement
52 p224FromBig(&x, bigX)
53 p224FromBig(&y, bigY)
54
55
56 var tmp p224LargeFieldElement
57 var x3 p224FieldElement
58 p224Square(&x3, &x, &tmp)
59 p224Mul(&x3, &x3, &x, &tmp)
60
61 for i := 0; i < 8; i++ {
62 x[i] *= 3
63 }
64 p224Sub(&x3, &x3, &x)
65 p224Reduce(&x3)
66 p224Add(&x3, &x3, &curve.b)
67 p224Contract(&x3, &x3)
68
69 p224Square(&y, &y, &tmp)
70 p224Contract(&y, &y)
71
72 for i := 0; i < 8; i++ {
73 if y[i] != x3[i] {
74 return false
75 }
76 }
77 return true
78 }
79
80 func (p224Curve) Add(bigX1, bigY1, bigX2, bigY2 *big.Int) (x, y *big.Int) {
81 var x1, y1, z1, x2, y2, z2, x3, y3, z3 p224FieldElement
82
83 p224FromBig(&x1, bigX1)
84 p224FromBig(&y1, bigY1)
85 if bigX1.Sign() != 0 || bigY1.Sign() != 0 {
86 z1[0] = 1
87 }
88 p224FromBig(&x2, bigX2)
89 p224FromBig(&y2, bigY2)
90 if bigX2.Sign() != 0 || bigY2.Sign() != 0 {
91 z2[0] = 1
92 }
93
94 p224AddJacobian(&x3, &y3, &z3, &x1, &y1, &z1, &x2, &y2, &z2)
95 return p224ToAffine(&x3, &y3, &z3)
96 }
97
98 func (p224Curve) Double(bigX1, bigY1 *big.Int) (x, y *big.Int) {
99 var x1, y1, z1, x2, y2, z2 p224FieldElement
100
101 p224FromBig(&x1, bigX1)
102 p224FromBig(&y1, bigY1)
103 z1[0] = 1
104
105 p224DoubleJacobian(&x2, &y2, &z2, &x1, &y1, &z1)
106 return p224ToAffine(&x2, &y2, &z2)
107 }
108
109 func (p224Curve) ScalarMult(bigX1, bigY1 *big.Int, scalar []byte) (x, y *big.Int) {
110 var x1, y1, z1, x2, y2, z2 p224FieldElement
111
112 p224FromBig(&x1, bigX1)
113 p224FromBig(&y1, bigY1)
114 z1[0] = 1
115
116 p224ScalarMult(&x2, &y2, &z2, &x1, &y1, &z1, scalar)
117 return p224ToAffine(&x2, &y2, &z2)
118 }
119
120 func (curve p224Curve) ScalarBaseMult(scalar []byte) (x, y *big.Int) {
121 var z1, x2, y2, z2 p224FieldElement
122
123 z1[0] = 1
124 p224ScalarMult(&x2, &y2, &z2, &curve.gx, &curve.gy, &z1, scalar)
125 return p224ToAffine(&x2, &y2, &z2)
126 }
127
128
129
130
131
132
133
134
135
136
137
138
139 type p224FieldElement [8]uint32
140
141
142 var p224P = [8]uint32{1, 0, 0, 0xffff000, 0xfffffff, 0xfffffff, 0xfffffff, 0xfffffff}
143
144
145
146
147 func p224IsZero(a *p224FieldElement) uint32 {
148
149
150 var minimal p224FieldElement
151 p224Contract(&minimal, a)
152
153 var isZero, isP uint32
154 for i, v := range minimal {
155 isZero |= v
156 isP |= v - p224P[i]
157 }
158
159
160 isZero |= isZero >> 16
161 isZero |= isZero >> 8
162 isZero |= isZero >> 4
163 isZero |= isZero >> 2
164 isZero |= isZero >> 1
165
166 isP |= isP >> 16
167 isP |= isP >> 8
168 isP |= isP >> 4
169 isP |= isP >> 2
170 isP |= isP >> 1
171
172
173 result := isZero & isP
174 result = (^result) & 1
175
176 return result
177 }
178
179
180
181
182 func p224Add(out, a, b *p224FieldElement) {
183 for i := 0; i < 8; i++ {
184 out[i] = a[i] + b[i]
185 }
186 }
187
188 const two31p3 = 1<<31 + 1<<3
189 const two31m3 = 1<<31 - 1<<3
190 const two31m15m3 = 1<<31 - 1<<15 - 1<<3
191
192
193
194
195 var p224ZeroModP31 = []uint32{two31p3, two31m3, two31m3, two31m15m3, two31m3, two31m3, two31m3, two31m3}
196
197
198
199
200
201 func p224Sub(out, a, b *p224FieldElement) {
202 for i := 0; i < 8; i++ {
203 out[i] = a[i] + p224ZeroModP31[i] - b[i]
204 }
205 }
206
207
208
209
210 type p224LargeFieldElement [15]uint64
211
212 const two63p35 = 1<<63 + 1<<35
213 const two63m35 = 1<<63 - 1<<35
214 const two63m35m19 = 1<<63 - 1<<35 - 1<<19
215
216
217
218 var p224ZeroModP63 = [8]uint64{two63p35, two63m35, two63m35, two63m35, two63m35m19, two63m35, two63m35, two63m35}
219
220 const bottom12Bits = 0xfff
221 const bottom28Bits = 0xfffffff
222
223
224
225
226
227 func p224Mul(out, a, b *p224FieldElement, tmp *p224LargeFieldElement) {
228 for i := 0; i < 15; i++ {
229 tmp[i] = 0
230 }
231
232 for i := 0; i < 8; i++ {
233 for j := 0; j < 8; j++ {
234 tmp[i+j] += uint64(a[i]) * uint64(b[j])
235 }
236 }
237
238 p224ReduceLarge(out, tmp)
239 }
240
241
242
243
244
245 func p224Square(out, a *p224FieldElement, tmp *p224LargeFieldElement) {
246 for i := 0; i < 15; i++ {
247 tmp[i] = 0
248 }
249
250 for i := 0; i < 8; i++ {
251 for j := 0; j <= i; j++ {
252 r := uint64(a[i]) * uint64(a[j])
253 if i == j {
254 tmp[i+j] += r
255 } else {
256 tmp[i+j] += r << 1
257 }
258 }
259 }
260
261 p224ReduceLarge(out, tmp)
262 }
263
264
265
266
267 func p224ReduceLarge(out *p224FieldElement, in *p224LargeFieldElement) {
268 for i := 0; i < 8; i++ {
269 in[i] += p224ZeroModP63[i]
270 }
271
272
273 for i := 14; i >= 8; i-- {
274 in[i-8] -= in[i]
275 in[i-5] += (in[i] & 0xffff) << 12
276 in[i-4] += in[i] >> 16
277 }
278 in[8] = 0
279
280
281
282
283 for i := 1; i < 8; i++ {
284 in[i+1] += in[i] >> 28
285 out[i] = uint32(in[i] & bottom28Bits)
286 }
287 in[0] -= in[8]
288 out[3] += uint32(in[8]&0xffff) << 12
289 out[4] += uint32(in[8] >> 16)
290
291
292
293
294
295 out[0] = uint32(in[0] & bottom28Bits)
296 out[1] += uint32((in[0] >> 28) & bottom28Bits)
297 out[2] += uint32(in[0] >> 56)
298
299
300
301 }
302
303
304
305
306
307 func p224Reduce(a *p224FieldElement) {
308 for i := 0; i < 7; i++ {
309 a[i+1] += a[i] >> 28
310 a[i] &= bottom28Bits
311 }
312 top := a[7] >> 28
313 a[7] &= bottom28Bits
314
315
316 mask := top
317 mask |= mask >> 2
318 mask |= mask >> 1
319 mask <<= 31
320 mask = uint32(int32(mask) >> 31)
321
322
323 a[0] -= top
324 a[3] += top << 12
325
326
327
328
329 a[3] -= 1 & mask
330 a[2] += mask & (1<<28 - 1)
331 a[1] += mask & (1<<28 - 1)
332 a[0] += mask & (1 << 28)
333 }
334
335
336
337 func p224Invert(out, in *p224FieldElement) {
338 var f1, f2, f3, f4 p224FieldElement
339 var c p224LargeFieldElement
340
341 p224Square(&f1, in, &c)
342 p224Mul(&f1, &f1, in, &c)
343 p224Square(&f1, &f1, &c)
344 p224Mul(&f1, &f1, in, &c)
345 p224Square(&f2, &f1, &c)
346 p224Square(&f2, &f2, &c)
347 p224Square(&f2, &f2, &c)
348 p224Mul(&f1, &f1, &f2, &c)
349 p224Square(&f2, &f1, &c)
350 for i := 0; i < 5; i++ {
351 p224Square(&f2, &f2, &c)
352 }
353 p224Mul(&f2, &f2, &f1, &c)
354 p224Square(&f3, &f2, &c)
355 for i := 0; i < 11; i++ {
356 p224Square(&f3, &f3, &c)
357 }
358 p224Mul(&f2, &f3, &f2, &c)
359 p224Square(&f3, &f2, &c)
360 for i := 0; i < 23; i++ {
361 p224Square(&f3, &f3, &c)
362 }
363 p224Mul(&f3, &f3, &f2, &c)
364 p224Square(&f4, &f3, &c)
365 for i := 0; i < 47; i++ {
366 p224Square(&f4, &f4, &c)
367 }
368 p224Mul(&f3, &f3, &f4, &c)
369 p224Square(&f4, &f3, &c)
370 for i := 0; i < 23; i++ {
371 p224Square(&f4, &f4, &c)
372 }
373 p224Mul(&f2, &f4, &f2, &c)
374 for i := 0; i < 6; i++ {
375 p224Square(&f2, &f2, &c)
376 }
377 p224Mul(&f1, &f1, &f2, &c)
378 p224Square(&f1, &f1, &c)
379 p224Mul(&f1, &f1, in, &c)
380 for i := 0; i < 97; i++ {
381 p224Square(&f1, &f1, &c)
382 }
383 p224Mul(out, &f1, &f3, &c)
384 }
385
386
387
388
389
390 func p224Contract(out, in *p224FieldElement) {
391 copy(out[:], in[:])
392
393
394 for i := 0; i < 7; i++ {
395 out[i+1] += out[i] >> 28
396 out[i] &= bottom28Bits
397 }
398 top := out[7] >> 28
399 out[7] &= bottom28Bits
400
401
402
403
404 out[0] -= top
405 out[3] += top << 12
406
407
408
409
410 for i := 0; i < 3; i++ {
411 mask := uint32(int32(out[i]) >> 31)
412 out[i] += (1 << 28) & mask
413 out[i+1] -= 1 & mask
414 }
415
416
417
418 for i := 3; i < 7; i++ {
419 out[i+1] += out[i] >> 28
420 out[i] &= bottom28Bits
421 }
422 top = out[7] >> 28
423 out[7] &= bottom28Bits
424
425
426 out[0] -= top
427 out[3] += top << 12
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442 for i := 0; i < 3; i++ {
443 mask := uint32(int32(out[i]) >> 31)
444 out[i] += (1 << 28) & mask
445 out[i+1] -= 1 & mask
446 }
447
448
449
450
451
452
453
454 top4AllOnes := uint32(0xffffffff)
455 for i := 4; i < 8; i++ {
456 top4AllOnes &= out[i]
457 }
458 top4AllOnes |= 0xf0000000
459
460 top4AllOnes &= top4AllOnes >> 16
461 top4AllOnes &= top4AllOnes >> 8
462 top4AllOnes &= top4AllOnes >> 4
463 top4AllOnes &= top4AllOnes >> 2
464 top4AllOnes &= top4AllOnes >> 1
465 top4AllOnes = uint32(int32(top4AllOnes<<31) >> 31)
466
467
468 bottom3NonZero := out[0] | out[1] | out[2]
469 bottom3NonZero |= bottom3NonZero >> 16
470 bottom3NonZero |= bottom3NonZero >> 8
471 bottom3NonZero |= bottom3NonZero >> 4
472 bottom3NonZero |= bottom3NonZero >> 2
473 bottom3NonZero |= bottom3NonZero >> 1
474 bottom3NonZero = uint32(int32(bottom3NonZero<<31) >> 31)
475
476
477
478
479
480 n := 0xffff000 - out[3]
481 out3Equal := n
482 out3Equal |= out3Equal >> 16
483 out3Equal |= out3Equal >> 8
484 out3Equal |= out3Equal >> 4
485 out3Equal |= out3Equal >> 2
486 out3Equal |= out3Equal >> 1
487 out3Equal = ^uint32(int32(out3Equal<<31) >> 31)
488
489
490 out3GT := uint32(int32(n) >> 31)
491
492 mask := top4AllOnes & ((out3Equal & bottom3NonZero) | out3GT)
493 out[0] -= 1 & mask
494 out[3] -= 0xffff000 & mask
495 out[4] -= 0xfffffff & mask
496 out[5] -= 0xfffffff & mask
497 out[6] -= 0xfffffff & mask
498 out[7] -= 0xfffffff & mask
499
500
501
502
503 for i := 0; i < 3; i++ {
504 mask := uint32(int32(out[i]) >> 31)
505 out[i] += (1 << 28) & mask
506 out[i+1] -= 1 & mask
507 }
508 }
509
510
511
512
513
514
515
516 func p224AddJacobian(x3, y3, z3, x1, y1, z1, x2, y2, z2 *p224FieldElement) {
517
518 var z1z1, z2z2, u1, u2, s1, s2, h, i, j, r, v p224FieldElement
519 var c p224LargeFieldElement
520
521 z1IsZero := p224IsZero(z1)
522 z2IsZero := p224IsZero(z2)
523
524
525 p224Square(&z1z1, z1, &c)
526
527 p224Square(&z2z2, z2, &c)
528
529 p224Mul(&u1, x1, &z2z2, &c)
530
531 p224Mul(&u2, x2, &z1z1, &c)
532
533 p224Mul(&s1, z2, &z2z2, &c)
534 p224Mul(&s1, y1, &s1, &c)
535
536 p224Mul(&s2, z1, &z1z1, &c)
537 p224Mul(&s2, y2, &s2, &c)
538
539 p224Sub(&h, &u2, &u1)
540 p224Reduce(&h)
541 xEqual := p224IsZero(&h)
542
543 for j := 0; j < 8; j++ {
544 i[j] = h[j] << 1
545 }
546 p224Reduce(&i)
547 p224Square(&i, &i, &c)
548
549 p224Mul(&j, &h, &i, &c)
550
551 p224Sub(&r, &s2, &s1)
552 p224Reduce(&r)
553 yEqual := p224IsZero(&r)
554 if xEqual == 1 && yEqual == 1 && z1IsZero == 0 && z2IsZero == 0 {
555 p224DoubleJacobian(x3, y3, z3, x1, y1, z1)
556 return
557 }
558 for i := 0; i < 8; i++ {
559 r[i] <<= 1
560 }
561 p224Reduce(&r)
562
563 p224Mul(&v, &u1, &i, &c)
564
565 p224Add(&z1z1, &z1z1, &z2z2)
566 p224Add(&z2z2, z1, z2)
567 p224Reduce(&z2z2)
568 p224Square(&z2z2, &z2z2, &c)
569 p224Sub(z3, &z2z2, &z1z1)
570 p224Reduce(z3)
571 p224Mul(z3, z3, &h, &c)
572
573 for i := 0; i < 8; i++ {
574 z1z1[i] = v[i] << 1
575 }
576 p224Add(&z1z1, &j, &z1z1)
577 p224Reduce(&z1z1)
578 p224Square(x3, &r, &c)
579 p224Sub(x3, x3, &z1z1)
580 p224Reduce(x3)
581
582 for i := 0; i < 8; i++ {
583 s1[i] <<= 1
584 }
585 p224Mul(&s1, &s1, &j, &c)
586 p224Sub(&z1z1, &v, x3)
587 p224Reduce(&z1z1)
588 p224Mul(&z1z1, &z1z1, &r, &c)
589 p224Sub(y3, &z1z1, &s1)
590 p224Reduce(y3)
591
592 p224CopyConditional(x3, x2, z1IsZero)
593 p224CopyConditional(x3, x1, z2IsZero)
594 p224CopyConditional(y3, y2, z1IsZero)
595 p224CopyConditional(y3, y1, z2IsZero)
596 p224CopyConditional(z3, z2, z1IsZero)
597 p224CopyConditional(z3, z1, z2IsZero)
598 }
599
600
601 func p224DoubleJacobian(x3, y3, z3, x1, y1, z1 *p224FieldElement) {
602 var delta, gamma, beta, alpha, t p224FieldElement
603 var c p224LargeFieldElement
604
605 p224Square(&delta, z1, &c)
606 p224Square(&gamma, y1, &c)
607 p224Mul(&beta, x1, &gamma, &c)
608
609
610 p224Add(&t, x1, &delta)
611 for i := 0; i < 8; i++ {
612 t[i] += t[i] << 1
613 }
614 p224Reduce(&t)
615 p224Sub(&alpha, x1, &delta)
616 p224Reduce(&alpha)
617 p224Mul(&alpha, &alpha, &t, &c)
618
619
620 p224Add(z3, y1, z1)
621 p224Reduce(z3)
622 p224Square(z3, z3, &c)
623 p224Sub(z3, z3, &gamma)
624 p224Reduce(z3)
625 p224Sub(z3, z3, &delta)
626 p224Reduce(z3)
627
628
629 for i := 0; i < 8; i++ {
630 delta[i] = beta[i] << 3
631 }
632 p224Reduce(&delta)
633 p224Square(x3, &alpha, &c)
634 p224Sub(x3, x3, &delta)
635 p224Reduce(x3)
636
637
638 for i := 0; i < 8; i++ {
639 beta[i] <<= 2
640 }
641 p224Sub(&beta, &beta, x3)
642 p224Reduce(&beta)
643 p224Square(&gamma, &gamma, &c)
644 for i := 0; i < 8; i++ {
645 gamma[i] <<= 3
646 }
647 p224Reduce(&gamma)
648 p224Mul(y3, &alpha, &beta, &c)
649 p224Sub(y3, y3, &gamma)
650 p224Reduce(y3)
651 }
652
653
654
655 func p224CopyConditional(out, in *p224FieldElement, control uint32) {
656 control <<= 31
657 control = uint32(int32(control) >> 31)
658
659 for i := 0; i < 8; i++ {
660 out[i] ^= (out[i] ^ in[i]) & control
661 }
662 }
663
664 func p224ScalarMult(outX, outY, outZ, inX, inY, inZ *p224FieldElement, scalar []byte) {
665 var xx, yy, zz p224FieldElement
666 for i := 0; i < 8; i++ {
667 outX[i] = 0
668 outY[i] = 0
669 outZ[i] = 0
670 }
671
672 for _, byte := range scalar {
673 for bitNum := uint(0); bitNum < 8; bitNum++ {
674 p224DoubleJacobian(outX, outY, outZ, outX, outY, outZ)
675 bit := uint32((byte >> (7 - bitNum)) & 1)
676 p224AddJacobian(&xx, &yy, &zz, inX, inY, inZ, outX, outY, outZ)
677 p224CopyConditional(outX, &xx, bit)
678 p224CopyConditional(outY, &yy, bit)
679 p224CopyConditional(outZ, &zz, bit)
680 }
681 }
682 }
683
684
685 func p224ToAffine(x, y, z *p224FieldElement) (*big.Int, *big.Int) {
686 var zinv, zinvsq, outx, outy p224FieldElement
687 var tmp p224LargeFieldElement
688
689 if isPointAtInfinity := p224IsZero(z); isPointAtInfinity == 1 {
690 return new(big.Int), new(big.Int)
691 }
692
693 p224Invert(&zinv, z)
694 p224Square(&zinvsq, &zinv, &tmp)
695 p224Mul(x, x, &zinvsq, &tmp)
696 p224Mul(&zinvsq, &zinvsq, &zinv, &tmp)
697 p224Mul(y, y, &zinvsq, &tmp)
698
699 p224Contract(&outx, x)
700 p224Contract(&outy, y)
701 return p224ToBig(&outx), p224ToBig(&outy)
702 }
703
704
705
706 func get28BitsFromEnd(buf []byte, shift uint) (uint32, []byte) {
707 var ret uint32
708
709 for i := uint(0); i < 4; i++ {
710 var b byte
711 if l := len(buf); l > 0 {
712 b = buf[l-1]
713
714
715 if i != 3 || shift == 4 {
716 buf = buf[:l-1]
717 }
718 }
719 ret |= uint32(b) << (8 * i) >> shift
720 }
721 ret &= bottom28Bits
722 return ret, buf
723 }
724
725
726 func p224FromBig(out *p224FieldElement, in *big.Int) {
727 bytes := in.Bytes()
728 out[0], bytes = get28BitsFromEnd(bytes, 0)
729 out[1], bytes = get28BitsFromEnd(bytes, 4)
730 out[2], bytes = get28BitsFromEnd(bytes, 0)
731 out[3], bytes = get28BitsFromEnd(bytes, 4)
732 out[4], bytes = get28BitsFromEnd(bytes, 0)
733 out[5], bytes = get28BitsFromEnd(bytes, 4)
734 out[6], bytes = get28BitsFromEnd(bytes, 0)
735 out[7], bytes = get28BitsFromEnd(bytes, 4)
736 }
737
738
739 func p224ToBig(in *p224FieldElement) *big.Int {
740 var buf [28]byte
741 buf[27] = byte(in[0])
742 buf[26] = byte(in[0] >> 8)
743 buf[25] = byte(in[0] >> 16)
744 buf[24] = byte(((in[0] >> 24) & 0x0f) | (in[1]<<4)&0xf0)
745
746 buf[23] = byte(in[1] >> 4)
747 buf[22] = byte(in[1] >> 12)
748 buf[21] = byte(in[1] >> 20)
749
750 buf[20] = byte(in[2])
751 buf[19] = byte(in[2] >> 8)
752 buf[18] = byte(in[2] >> 16)
753 buf[17] = byte(((in[2] >> 24) & 0x0f) | (in[3]<<4)&0xf0)
754
755 buf[16] = byte(in[3] >> 4)
756 buf[15] = byte(in[3] >> 12)
757 buf[14] = byte(in[3] >> 20)
758
759 buf[13] = byte(in[4])
760 buf[12] = byte(in[4] >> 8)
761 buf[11] = byte(in[4] >> 16)
762 buf[10] = byte(((in[4] >> 24) & 0x0f) | (in[5]<<4)&0xf0)
763
764 buf[9] = byte(in[5] >> 4)
765 buf[8] = byte(in[5] >> 12)
766 buf[7] = byte(in[5] >> 20)
767
768 buf[6] = byte(in[6])
769 buf[5] = byte(in[6] >> 8)
770 buf[4] = byte(in[6] >> 16)
771 buf[3] = byte(((in[6] >> 24) & 0x0f) | (in[7]<<4)&0xf0)
772
773 buf[2] = byte(in[7] >> 4)
774 buf[1] = byte(in[7] >> 12)
775 buf[0] = byte(in[7] >> 20)
776
777 return new(big.Int).SetBytes(buf[:])
778 }
779
View as plain text