1
2
3
4
5
6
7 package nistec
8
9 import (
10 "crypto/internal/fips140/nistec/fiat"
11 "crypto/internal/fips140/subtle"
12 "errors"
13 "sync"
14 )
15
16
17
18 const p384ElementLength = 48
19
20
21 type P384Point struct {
22
23
24 x, y, z *fiat.P384Element
25 }
26
27
28 func NewP384Point() *P384Point {
29 return &P384Point{
30 x: new(fiat.P384Element),
31 y: new(fiat.P384Element).One(),
32 z: new(fiat.P384Element),
33 }
34 }
35
36
37 func (p *P384Point) SetGenerator() *P384Point {
38 p.x.SetBytes([]byte{0xaa, 0x87, 0xca, 0x22, 0xbe, 0x8b, 0x5, 0x37, 0x8e, 0xb1, 0xc7, 0x1e, 0xf3, 0x20, 0xad, 0x74, 0x6e, 0x1d, 0x3b, 0x62, 0x8b, 0xa7, 0x9b, 0x98, 0x59, 0xf7, 0x41, 0xe0, 0x82, 0x54, 0x2a, 0x38, 0x55, 0x2, 0xf2, 0x5d, 0xbf, 0x55, 0x29, 0x6c, 0x3a, 0x54, 0x5e, 0x38, 0x72, 0x76, 0xa, 0xb7})
39 p.y.SetBytes([]byte{0x36, 0x17, 0xde, 0x4a, 0x96, 0x26, 0x2c, 0x6f, 0x5d, 0x9e, 0x98, 0xbf, 0x92, 0x92, 0xdc, 0x29, 0xf8, 0xf4, 0x1d, 0xbd, 0x28, 0x9a, 0x14, 0x7c, 0xe9, 0xda, 0x31, 0x13, 0xb5, 0xf0, 0xb8, 0xc0, 0xa, 0x60, 0xb1, 0xce, 0x1d, 0x7e, 0x81, 0x9d, 0x7a, 0x43, 0x1d, 0x7c, 0x90, 0xea, 0xe, 0x5f})
40 p.z.One()
41 return p
42 }
43
44
45 func (p *P384Point) Set(q *P384Point) *P384Point {
46 p.x.Set(q.x)
47 p.y.Set(q.y)
48 p.z.Set(q.z)
49 return p
50 }
51
52
53
54
55
56 func (p *P384Point) SetBytes(b []byte) (*P384Point, error) {
57 switch {
58
59 case len(b) == 1 && b[0] == 0:
60 return p.Set(NewP384Point()), nil
61
62
63 case len(b) == 1+2*p384ElementLength && b[0] == 4:
64 x, err := new(fiat.P384Element).SetBytes(b[1 : 1+p384ElementLength])
65 if err != nil {
66 return nil, err
67 }
68 y, err := new(fiat.P384Element).SetBytes(b[1+p384ElementLength:])
69 if err != nil {
70 return nil, err
71 }
72 if err := p384CheckOnCurve(x, y); err != nil {
73 return nil, err
74 }
75 p.x.Set(x)
76 p.y.Set(y)
77 p.z.One()
78 return p, nil
79
80
81 case len(b) == 1+p384ElementLength && (b[0] == 2 || b[0] == 3):
82 x, err := new(fiat.P384Element).SetBytes(b[1:])
83 if err != nil {
84 return nil, err
85 }
86
87
88 y := p384Polynomial(new(fiat.P384Element), x)
89 if !p384Sqrt(y, y) {
90 return nil, errors.New("invalid P384 compressed point encoding")
91 }
92
93
94
95 otherRoot := new(fiat.P384Element)
96 otherRoot.Sub(otherRoot, y)
97 cond := y.Bytes()[p384ElementLength-1]&1 ^ b[0]&1
98 y.Select(otherRoot, y, int(cond))
99
100 p.x.Set(x)
101 p.y.Set(y)
102 p.z.One()
103 return p, nil
104
105 default:
106 return nil, errors.New("invalid P384 point encoding")
107 }
108 }
109
110 var _p384B *fiat.P384Element
111 var _p384BOnce sync.Once
112
113 func p384B() *fiat.P384Element {
114 _p384BOnce.Do(func() {
115 _p384B, _ = new(fiat.P384Element).SetBytes([]byte{0xb3, 0x31, 0x2f, 0xa7, 0xe2, 0x3e, 0xe7, 0xe4, 0x98, 0x8e, 0x5, 0x6b, 0xe3, 0xf8, 0x2d, 0x19, 0x18, 0x1d, 0x9c, 0x6e, 0xfe, 0x81, 0x41, 0x12, 0x3, 0x14, 0x8, 0x8f, 0x50, 0x13, 0x87, 0x5a, 0xc6, 0x56, 0x39, 0x8d, 0x8a, 0x2e, 0xd1, 0x9d, 0x2a, 0x85, 0xc8, 0xed, 0xd3, 0xec, 0x2a, 0xef})
116 })
117 return _p384B
118 }
119
120
121 func p384Polynomial(y2, x *fiat.P384Element) *fiat.P384Element {
122 y2.Square(x)
123 y2.Mul(y2, x)
124
125 threeX := new(fiat.P384Element).Add(x, x)
126 threeX.Add(threeX, x)
127 y2.Sub(y2, threeX)
128
129 return y2.Add(y2, p384B())
130 }
131
132 func p384CheckOnCurve(x, y *fiat.P384Element) error {
133
134 rhs := p384Polynomial(new(fiat.P384Element), x)
135 lhs := new(fiat.P384Element).Square(y)
136 if rhs.Equal(lhs) != 1 {
137 return errors.New("P384 point not on curve")
138 }
139 return nil
140 }
141
142
143
144
145 func (p *P384Point) Bytes() []byte {
146
147
148 var out [1 + 2*p384ElementLength]byte
149 return p.bytes(&out)
150 }
151
152 func (p *P384Point) bytes(out *[1 + 2*p384ElementLength]byte) []byte {
153 if p.z.IsZero() == 1 {
154 return append(out[:0], 0)
155 }
156
157 zinv := new(fiat.P384Element).Invert(p.z)
158 x := new(fiat.P384Element).Mul(p.x, zinv)
159 y := new(fiat.P384Element).Mul(p.y, zinv)
160
161 buf := append(out[:0], 4)
162 buf = append(buf, x.Bytes()...)
163 buf = append(buf, y.Bytes()...)
164 return buf
165 }
166
167
168
169 func (p *P384Point) BytesX() ([]byte, error) {
170
171
172 var out [p384ElementLength]byte
173 return p.bytesX(&out)
174 }
175
176 func (p *P384Point) bytesX(out *[p384ElementLength]byte) ([]byte, error) {
177 if p.z.IsZero() == 1 {
178 return nil, errors.New("P384 point is the point at infinity")
179 }
180
181 zinv := new(fiat.P384Element).Invert(p.z)
182 x := new(fiat.P384Element).Mul(p.x, zinv)
183
184 return append(out[:0], x.Bytes()...), nil
185 }
186
187
188
189
190 func (p *P384Point) BytesCompressed() []byte {
191
192
193 var out [1 + p384ElementLength]byte
194 return p.bytesCompressed(&out)
195 }
196
197 func (p *P384Point) bytesCompressed(out *[1 + p384ElementLength]byte) []byte {
198 if p.z.IsZero() == 1 {
199 return append(out[:0], 0)
200 }
201
202 zinv := new(fiat.P384Element).Invert(p.z)
203 x := new(fiat.P384Element).Mul(p.x, zinv)
204 y := new(fiat.P384Element).Mul(p.y, zinv)
205
206
207
208 buf := append(out[:0], 2)
209 buf[0] |= y.Bytes()[p384ElementLength-1] & 1
210 buf = append(buf, x.Bytes()...)
211 return buf
212 }
213
214
215 func (q *P384Point) Add(p1, p2 *P384Point) *P384Point {
216
217
218
219 t0 := new(fiat.P384Element).Mul(p1.x, p2.x)
220 t1 := new(fiat.P384Element).Mul(p1.y, p2.y)
221 t2 := new(fiat.P384Element).Mul(p1.z, p2.z)
222 t3 := new(fiat.P384Element).Add(p1.x, p1.y)
223 t4 := new(fiat.P384Element).Add(p2.x, p2.y)
224 t3.Mul(t3, t4)
225 t4.Add(t0, t1)
226 t3.Sub(t3, t4)
227 t4.Add(p1.y, p1.z)
228 x3 := new(fiat.P384Element).Add(p2.y, p2.z)
229 t4.Mul(t4, x3)
230 x3.Add(t1, t2)
231 t4.Sub(t4, x3)
232 x3.Add(p1.x, p1.z)
233 y3 := new(fiat.P384Element).Add(p2.x, p2.z)
234 x3.Mul(x3, y3)
235 y3.Add(t0, t2)
236 y3.Sub(x3, y3)
237 z3 := new(fiat.P384Element).Mul(p384B(), t2)
238 x3.Sub(y3, z3)
239 z3.Add(x3, x3)
240 x3.Add(x3, z3)
241 z3.Sub(t1, x3)
242 x3.Add(t1, x3)
243 y3.Mul(p384B(), y3)
244 t1.Add(t2, t2)
245 t2.Add(t1, t2)
246 y3.Sub(y3, t2)
247 y3.Sub(y3, t0)
248 t1.Add(y3, y3)
249 y3.Add(t1, y3)
250 t1.Add(t0, t0)
251 t0.Add(t1, t0)
252 t0.Sub(t0, t2)
253 t1.Mul(t4, y3)
254 t2.Mul(t0, y3)
255 y3.Mul(x3, z3)
256 y3.Add(y3, t2)
257 x3.Mul(t3, x3)
258 x3.Sub(x3, t1)
259 z3.Mul(t4, z3)
260 t1.Mul(t3, t0)
261 z3.Add(z3, t1)
262
263 q.x.Set(x3)
264 q.y.Set(y3)
265 q.z.Set(z3)
266 return q
267 }
268
269
270 func (q *P384Point) Double(p *P384Point) *P384Point {
271
272
273
274 t0 := new(fiat.P384Element).Square(p.x)
275 t1 := new(fiat.P384Element).Square(p.y)
276 t2 := new(fiat.P384Element).Square(p.z)
277 t3 := new(fiat.P384Element).Mul(p.x, p.y)
278 t3.Add(t3, t3)
279 z3 := new(fiat.P384Element).Mul(p.x, p.z)
280 z3.Add(z3, z3)
281 y3 := new(fiat.P384Element).Mul(p384B(), t2)
282 y3.Sub(y3, z3)
283 x3 := new(fiat.P384Element).Add(y3, y3)
284 y3.Add(x3, y3)
285 x3.Sub(t1, y3)
286 y3.Add(t1, y3)
287 y3.Mul(x3, y3)
288 x3.Mul(x3, t3)
289 t3.Add(t2, t2)
290 t2.Add(t2, t3)
291 z3.Mul(p384B(), z3)
292 z3.Sub(z3, t2)
293 z3.Sub(z3, t0)
294 t3.Add(z3, z3)
295 z3.Add(z3, t3)
296 t3.Add(t0, t0)
297 t0.Add(t3, t0)
298 t0.Sub(t0, t2)
299 t0.Mul(t0, z3)
300 y3.Add(y3, t0)
301 t0.Mul(p.y, p.z)
302 t0.Add(t0, t0)
303 z3.Mul(t0, z3)
304 x3.Sub(x3, z3)
305 z3.Mul(t0, t1)
306 z3.Add(z3, z3)
307 z3.Add(z3, z3)
308
309 q.x.Set(x3)
310 q.y.Set(y3)
311 q.z.Set(z3)
312 return q
313 }
314
315
316 func (q *P384Point) Select(p1, p2 *P384Point, cond int) *P384Point {
317 q.x.Select(p1.x, p2.x, cond)
318 q.y.Select(p1.y, p2.y, cond)
319 q.z.Select(p1.z, p2.z, cond)
320 return q
321 }
322
323
324
325
326 type p384Table [15]*P384Point
327
328
329
330 func (table *p384Table) Select(p *P384Point, n uint8) {
331 if n >= 16 {
332 panic("nistec: internal error: p384Table called with out-of-bounds value")
333 }
334 p.Set(NewP384Point())
335 for i := uint8(1); i < 16; i++ {
336 cond := subtle.ConstantTimeByteEq(i, n)
337 p.Select(table[i-1], p, cond)
338 }
339 }
340
341
342 func (p *P384Point) ScalarMult(q *P384Point, scalar []byte) (*P384Point, error) {
343
344
345 var table = p384Table{NewP384Point(), NewP384Point(), NewP384Point(),
346 NewP384Point(), NewP384Point(), NewP384Point(), NewP384Point(),
347 NewP384Point(), NewP384Point(), NewP384Point(), NewP384Point(),
348 NewP384Point(), NewP384Point(), NewP384Point(), NewP384Point()}
349 table[0].Set(q)
350 for i := 1; i < 15; i += 2 {
351 table[i].Double(table[i/2])
352 table[i+1].Add(table[i], q)
353 }
354
355
356
357 t := NewP384Point()
358 p.Set(NewP384Point())
359 for i, byte := range scalar {
360
361
362 if i != 0 {
363 p.Double(p)
364 p.Double(p)
365 p.Double(p)
366 p.Double(p)
367 }
368
369 windowValue := byte >> 4
370 table.Select(t, windowValue)
371 p.Add(p, t)
372
373 p.Double(p)
374 p.Double(p)
375 p.Double(p)
376 p.Double(p)
377
378 windowValue = byte & 0b1111
379 table.Select(t, windowValue)
380 p.Add(p, t)
381 }
382
383 return p, nil
384 }
385
386 var p384GeneratorTable *[p384ElementLength * 2]p384Table
387 var p384GeneratorTableOnce sync.Once
388
389
390
391
392 func (p *P384Point) generatorTable() *[p384ElementLength * 2]p384Table {
393 p384GeneratorTableOnce.Do(func() {
394 p384GeneratorTable = new([p384ElementLength * 2]p384Table)
395 base := NewP384Point().SetGenerator()
396 for i := 0; i < p384ElementLength*2; i++ {
397 p384GeneratorTable[i][0] = NewP384Point().Set(base)
398 for j := 1; j < 15; j++ {
399 p384GeneratorTable[i][j] = NewP384Point().Add(p384GeneratorTable[i][j-1], base)
400 }
401 base.Double(base)
402 base.Double(base)
403 base.Double(base)
404 base.Double(base)
405 }
406 })
407 return p384GeneratorTable
408 }
409
410
411
412 func (p *P384Point) ScalarBaseMult(scalar []byte) (*P384Point, error) {
413 if len(scalar) != p384ElementLength {
414 return nil, errors.New("invalid scalar length")
415 }
416 tables := p.generatorTable()
417
418
419
420
421
422
423
424 t := NewP384Point()
425 p.Set(NewP384Point())
426 tableIndex := len(tables) - 1
427 for _, byte := range scalar {
428 windowValue := byte >> 4
429 tables[tableIndex].Select(t, windowValue)
430 p.Add(p, t)
431 tableIndex--
432
433 windowValue = byte & 0b1111
434 tables[tableIndex].Select(t, windowValue)
435 p.Add(p, t)
436 tableIndex--
437 }
438
439 return p, nil
440 }
441
442
443
444 func p384Sqrt(e, x *fiat.P384Element) (isSquare bool) {
445 candidate := new(fiat.P384Element)
446 p384SqrtCandidate(candidate, x)
447 square := new(fiat.P384Element).Square(candidate)
448 if square.Equal(x) != 1 {
449 return false
450 }
451 e.Set(candidate)
452 return true
453 }
454
455
456 func p384SqrtCandidate(z, x *fiat.P384Element) {
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480 var t0 = new(fiat.P384Element)
481 var t1 = new(fiat.P384Element)
482 var t2 = new(fiat.P384Element)
483
484 z.Square(x)
485 z.Mul(x, z)
486 z.Square(z)
487 t0.Mul(x, z)
488 z.Square(t0)
489 for s := 1; s < 3; s++ {
490 z.Square(z)
491 }
492 t1.Mul(t0, z)
493 t2.Square(t1)
494 z.Mul(x, t2)
495 for s := 0; s < 5; s++ {
496 t2.Square(t2)
497 }
498 t1.Mul(t1, t2)
499 t2.Square(t1)
500 for s := 1; s < 12; s++ {
501 t2.Square(t2)
502 }
503 t1.Mul(t1, t2)
504 for s := 0; s < 7; s++ {
505 t1.Square(t1)
506 }
507 t1.Mul(z, t1)
508 z.Square(t1)
509 z.Mul(x, z)
510 t2.Square(z)
511 for s := 1; s < 31; s++ {
512 t2.Square(t2)
513 }
514 t1.Mul(t1, t2)
515 t2.Square(t1)
516 for s := 1; s < 63; s++ {
517 t2.Square(t2)
518 }
519 t1.Mul(t1, t2)
520 t2.Square(t1)
521 for s := 1; s < 126; s++ {
522 t2.Square(t2)
523 }
524 t1.Mul(t1, t2)
525 for s := 0; s < 3; s++ {
526 t1.Square(t1)
527 }
528 t0.Mul(t0, t1)
529 for s := 0; s < 33; s++ {
530 t0.Square(t0)
531 }
532 z.Mul(z, t0)
533 for s := 0; s < 64; s++ {
534 z.Square(z)
535 }
536 z.Mul(x, z)
537 for s := 0; s < 30; s++ {
538 z.Square(z)
539 }
540 }
541
View as plain text