1 package group
2
3 import (
4 "crypto"
5 "crypto/elliptic"
6 _ "crypto/sha256"
7 _ "crypto/sha512"
8 "crypto/subtle"
9 "fmt"
10 "io"
11 "math/big"
12
13 "github.com/cloudflare/circl/ecc/p384"
14 "github.com/cloudflare/circl/expander"
15 )
16
17 var (
18
19 P256 Group = wG{elliptic.P256()}
20
21 P384 Group = wG{p384.P384()}
22
23 P521 Group = wG{elliptic.P521()}
24 )
25
26 type wG struct {
27 c elliptic.Curve
28 }
29
30 func (g wG) String() string { return g.c.Params().Name }
31 func (g wG) NewElement() Element { return g.zeroElement() }
32 func (g wG) NewScalar() Scalar { return g.zeroScalar() }
33 func (g wG) Identity() Element { return g.zeroElement() }
34 func (g wG) zeroScalar() *wScl { return &wScl{g, make([]byte, (g.c.Params().BitSize+7)/8)} }
35 func (g wG) zeroElement() *wElt { return &wElt{g, new(big.Int), new(big.Int)} }
36 func (g wG) Generator() Element { return &wElt{g, g.c.Params().Gx, g.c.Params().Gy} }
37 func (g wG) Order() Scalar { s := &wScl{g, nil}; s.fromBig(g.c.Params().N); return s }
38 func (g wG) RandomElement(rd io.Reader) Element {
39 b := make([]byte, (g.c.Params().BitSize+7)/8)
40 if n, err := io.ReadFull(rd, b); err != nil || n != len(b) {
41 panic(err)
42 }
43 return g.HashToElement(b, nil)
44 }
45
46 func (g wG) RandomScalar(rd io.Reader) Scalar {
47 b := make([]byte, (g.c.Params().BitSize+7)/8)
48 if n, err := io.ReadFull(rd, b); err != nil || n != len(b) {
49 panic(err)
50 }
51 return g.HashToScalar(b, nil)
52 }
53
54 func (g wG) RandomNonZeroScalar(rd io.Reader) Scalar {
55 zero := g.zeroScalar()
56 for {
57 s := g.RandomScalar(rd)
58 if !s.IsEqual(zero) {
59 return s
60 }
61 }
62 }
63
64 func (g wG) cvtElt(e Element) *wElt {
65 if e == nil {
66 return g.zeroElement()
67 }
68 ee, ok := e.(*wElt)
69 if !ok || g.c.Params().BitSize != ee.c.Params().BitSize {
70 panic(ErrType)
71 }
72 return ee
73 }
74
75 func (g wG) cvtScl(s Scalar) *wScl {
76 if s == nil {
77 return g.zeroScalar()
78 }
79 ss, ok := s.(*wScl)
80 if !ok || g.c.Params().BitSize != ss.c.Params().BitSize {
81 panic(ErrType)
82 }
83 return ss
84 }
85
86 func (g wG) Params() *Params {
87 fieldLen := uint((g.c.Params().BitSize + 7) / 8)
88 return &Params{
89 ElementLength: 1 + 2*fieldLen,
90 CompressedElementLength: 1 + fieldLen,
91 ScalarLength: fieldLen,
92 }
93 }
94
95 func (g wG) HashToElementNonUniform(b, dst []byte) Element {
96 var u [1]big.Int
97 mapping, h, L := g.mapToCurveParams()
98 xmd := expander.NewExpanderMD(h, dst)
99 HashToField(u[:], b, xmd, g.c.Params().P, L)
100 return mapping(&u[0])
101 }
102
103 func (g wG) HashToElement(b, dst []byte) Element {
104 var u [2]big.Int
105 mapping, h, L := g.mapToCurveParams()
106 xmd := expander.NewExpanderMD(h, dst)
107 HashToField(u[:], b, xmd, g.c.Params().P, L)
108 Q0 := mapping(&u[0])
109 Q1 := mapping(&u[1])
110 return Q0.Add(Q0, Q1)
111 }
112
113 func (g wG) HashToScalar(b, dst []byte) Scalar {
114 var u [1]big.Int
115 _, h, L := g.mapToCurveParams()
116 xmd := expander.NewExpanderMD(h, dst)
117 HashToField(u[:], b, xmd, g.c.Params().N, L)
118 s := g.NewScalar().(*wScl)
119 s.fromBig(&u[0])
120 return s
121 }
122
123 type wElt struct {
124 wG
125 x, y *big.Int
126 }
127
128 func (e *wElt) Group() Group { return e.wG }
129 func (e *wElt) String() string { return fmt.Sprintf("x: 0x%v\ny: 0x%v", e.x.Text(16), e.y.Text(16)) }
130 func (e *wElt) IsIdentity() bool { return e.x.Sign() == 0 && e.y.Sign() == 0 }
131 func (e *wElt) IsEqual(o Element) bool {
132 oo := e.cvtElt(o)
133 return e.x.Cmp(oo.x) == 0 && e.y.Cmp(oo.y) == 0
134 }
135
136 func (e *wElt) Set(a Element) Element {
137 aa := e.cvtElt(a)
138 e.x.Set(aa.x)
139 e.y.Set(aa.y)
140 return e
141 }
142
143 func (e *wElt) Copy() Element { return e.wG.zeroElement().Set(e) }
144
145 func (e *wElt) CMov(v int, a Element) Element {
146 if !(v == 0 || v == 1) {
147 panic(ErrSelector)
148 }
149 aa := e.cvtElt(a)
150 l := (e.wG.c.Params().BitSize + 7) / 8
151 bufE := make([]byte, l)
152 bufA := make([]byte, l)
153 e.x.FillBytes(bufE)
154 aa.x.FillBytes(bufA)
155 subtle.ConstantTimeCopy(v, bufE, bufA)
156 e.x.SetBytes(bufE)
157
158 e.y.FillBytes(bufE)
159 aa.y.FillBytes(bufA)
160 subtle.ConstantTimeCopy(v, bufE, bufA)
161 e.y.SetBytes(bufE)
162
163 return e
164 }
165
166 func (e *wElt) CSelect(v int, a Element, b Element) Element {
167 if !(v == 0 || v == 1) {
168 panic(ErrSelector)
169 }
170 aa, bb := e.cvtElt(a), e.cvtElt(b)
171 l := (e.wG.c.Params().BitSize + 7) / 8
172 bufE := make([]byte, l)
173 bufA := make([]byte, l)
174 bufB := make([]byte, l)
175
176 e.x.FillBytes(bufE)
177 aa.x.FillBytes(bufA)
178 bb.x.FillBytes(bufB)
179 for i := range bufE {
180 bufE[i] = byte(subtle.ConstantTimeSelect(v, int(bufA[i]), int(bufB[i])))
181 }
182 e.x.SetBytes(bufE)
183
184 e.y.FillBytes(bufE)
185 aa.y.FillBytes(bufA)
186 bb.y.FillBytes(bufB)
187 for i := range bufE {
188 bufE[i] = byte(subtle.ConstantTimeSelect(v, int(bufA[i]), int(bufB[i])))
189 }
190 e.y.SetBytes(bufE)
191
192 return e
193 }
194
195 func (e *wElt) Add(a, b Element) Element {
196 aa, bb := e.cvtElt(a), e.cvtElt(b)
197 e.x, e.y = e.c.Add(aa.x, aa.y, bb.x, bb.y)
198 return e
199 }
200
201 func (e *wElt) Dbl(a Element) Element {
202 aa := e.cvtElt(a)
203 e.x, e.y = e.c.Double(aa.x, aa.y)
204 return e
205 }
206
207 func (e *wElt) Neg(a Element) Element {
208 aa := e.cvtElt(a)
209 e.x.Set(aa.x)
210 e.y.Neg(aa.y).Mod(e.y, e.c.Params().P)
211 return e
212 }
213
214 func (e *wElt) Mul(a Element, s Scalar) Element {
215 aa, ss := e.cvtElt(a), e.cvtScl(s)
216 e.x, e.y = e.c.ScalarMult(aa.x, aa.y, ss.k)
217 return e
218 }
219
220 func (e *wElt) MulGen(s Scalar) Element {
221 ss := e.cvtScl(s)
222 e.x, e.y = e.c.ScalarBaseMult(ss.k)
223 return e
224 }
225
226 func (e *wElt) MarshalBinary() ([]byte, error) {
227 if e.IsIdentity() {
228 return []byte{0x0}, nil
229 }
230 e.x.Mod(e.x, e.c.Params().P)
231 e.y.Mod(e.y, e.c.Params().P)
232 return elliptic.Marshal(e.wG.c, e.x, e.y), nil
233 }
234
235 func (e *wElt) MarshalBinaryCompress() ([]byte, error) {
236 if e.IsIdentity() {
237 return []byte{0x0}, nil
238 }
239 e.x.Mod(e.x, e.c.Params().P)
240 e.y.Mod(e.y, e.c.Params().P)
241 return elliptic.MarshalCompressed(e.wG.c, e.x, e.y), nil
242 }
243
244 func (e *wElt) UnmarshalBinary(b []byte) error {
245 byteLen := (e.c.Params().BitSize + 7) / 8
246 l := len(b)
247 switch {
248 case l == 1 && b[0] == 0x00:
249 e.x.SetInt64(0)
250 e.y.SetInt64(0)
251 case l == 1+byteLen && (b[0] == 0x02 || b[0] == 0x03):
252 x, y := elliptic.UnmarshalCompressed(e.wG.c, b)
253 if x == nil {
254 return ErrUnmarshal
255 }
256 e.x, e.y = x, y
257 case l == 1+2*byteLen && b[0] == 0x04:
258 x, y := elliptic.Unmarshal(e.wG.c, b)
259 if x == nil {
260 return ErrUnmarshal
261 }
262 e.x, e.y = x, y
263 default:
264 return ErrUnmarshal
265 }
266 return nil
267 }
268
269 type wScl struct {
270 wG
271 k []byte
272 }
273
274 func (s *wScl) Group() Group { return s.wG }
275 func (s *wScl) String() string { return fmt.Sprintf("0x%x", s.k) }
276 func (s *wScl) SetUint64(n uint64) Scalar { s.fromBig(new(big.Int).SetUint64(n)); return s }
277 func (s *wScl) SetBigInt(x *big.Int) Scalar { s.fromBig(x); return s }
278 func (s *wScl) IsZero() bool {
279 return subtle.ConstantTimeCompare(s.k, make([]byte, (s.wG.c.Params().BitSize+7)/8)) == 1
280 }
281
282 func (s *wScl) IsEqual(a Scalar) bool {
283 aa := s.cvtScl(a)
284 return subtle.ConstantTimeCompare(s.k, aa.k) == 1
285 }
286
287 func (s *wScl) fromBig(b *big.Int) {
288 k := new(big.Int).Mod(b, s.c.Params().N)
289 if err := s.UnmarshalBinary(k.Bytes()); err != nil {
290 panic(err)
291 }
292 }
293
294 func (s *wScl) Set(a Scalar) Scalar {
295 aa := s.cvtScl(a)
296 if err := s.UnmarshalBinary(aa.k); err != nil {
297 panic(err)
298 }
299 return s
300 }
301
302 func (s *wScl) Copy() Scalar { return s.wG.zeroScalar().Set(s) }
303
304 func (s *wScl) CMov(v int, a Scalar) Scalar {
305 if !(v == 0 || v == 1) {
306 panic(ErrSelector)
307 }
308 aa := s.cvtScl(a)
309 subtle.ConstantTimeCopy(v, s.k, aa.k)
310 return s
311 }
312
313 func (s *wScl) CSelect(v int, a Scalar, b Scalar) Scalar {
314 if !(v == 0 || v == 1) {
315 panic(ErrSelector)
316 }
317 aa, bb := s.cvtScl(a), s.cvtScl(b)
318 for i := range s.k {
319 s.k[i] = byte(subtle.ConstantTimeSelect(v, int(aa.k[i]), int(bb.k[i])))
320 }
321 return s
322 }
323
324 func (s *wScl) Add(a, b Scalar) Scalar {
325 aa, bb := s.cvtScl(a), s.cvtScl(b)
326 r := new(big.Int)
327 r.SetBytes(aa.k).Add(r, new(big.Int).SetBytes(bb.k))
328 s.fromBig(r)
329 return s
330 }
331
332 func (s *wScl) Sub(a, b Scalar) Scalar {
333 aa, bb := s.cvtScl(a), s.cvtScl(b)
334 r := new(big.Int)
335 r.SetBytes(aa.k).Sub(r, new(big.Int).SetBytes(bb.k))
336 s.fromBig(r)
337 return s
338 }
339
340 func (s *wScl) Mul(a, b Scalar) Scalar {
341 aa, bb := s.cvtScl(a), s.cvtScl(b)
342 r := new(big.Int)
343 r.SetBytes(aa.k).Mul(r, new(big.Int).SetBytes(bb.k))
344 s.fromBig(r)
345 return s
346 }
347
348 func (s *wScl) Neg(a Scalar) Scalar {
349 aa := s.cvtScl(a)
350 r := new(big.Int)
351 r.SetBytes(aa.k).Neg(r)
352 s.fromBig(r)
353 return s
354 }
355
356 func (s *wScl) Inv(a Scalar) Scalar {
357 aa := s.cvtScl(a)
358 r := new(big.Int)
359 r.SetBytes(aa.k).ModInverse(r, s.c.Params().N)
360 s.fromBig(r)
361 return s
362 }
363
364 func (s *wScl) MarshalBinary() (data []byte, err error) {
365 data = make([]byte, (s.c.Params().BitSize+7)/8)
366 copy(data, s.k)
367 return data, nil
368 }
369
370 func (s *wScl) UnmarshalBinary(b []byte) error {
371 l := (s.c.Params().BitSize + 7) / 8
372 s.k = make([]byte, l)
373 copy(s.k[l-len(b):l], b)
374 return nil
375 }
376
377 func (g wG) mapToCurveParams() (mapping func(u *big.Int) *wElt, h crypto.Hash, L uint) {
378 var Z, C2 big.Int
379 switch g.c.Params().BitSize {
380 case 256:
381 Z.SetInt64(-10)
382 C2.SetString("0x78bc71a02d89ec07214623f6d0f955072c7cc05604a5a6e23ffbf67115fa5301", 0)
383 h = crypto.SHA256
384 L = 48
385 case 384:
386 Z.SetInt64(-12)
387 C2.SetString("0x19877cc1041b7555743c0ae2e3a3e61fb2aaa2e0e87ea557a563d8b598a0940d0a697a9e0b9e92cfaa314f583c9d066", 0)
388 h = crypto.SHA384
389 L = 72
390 case 521:
391 Z.SetInt64(-4)
392 C2.SetInt64(8)
393 h = crypto.SHA512
394 L = 98
395 default:
396 panic("curve not supported")
397 }
398 return func(u *big.Int) *wElt { return g.sswu3mod4Map(u, &Z, &C2) }, h, L
399 }
400
401 func (g wG) sswu3mod4Map(u *big.Int, Z, C2 *big.Int) *wElt {
402 tv1 := new(big.Int)
403 tv2 := new(big.Int)
404 tv3 := new(big.Int)
405 tv4 := new(big.Int)
406 xn := new(big.Int)
407 xd := new(big.Int)
408 x1n := new(big.Int)
409 x2n := new(big.Int)
410 gx1 := new(big.Int)
411 gxd := new(big.Int)
412 y1 := new(big.Int)
413 y2 := new(big.Int)
414 x := new(big.Int)
415 y := new(big.Int)
416
417 A := big.NewInt(-3)
418 B := g.c.Params().B
419 p := g.c.Params().P
420 c1 := new(big.Int)
421 c1.Sub(p, big.NewInt(3)).Rsh(c1, 2)
422
423 add := func(c, a, b *big.Int) { c.Add(a, b).Mod(c, p) }
424 mul := func(c, a, b *big.Int) { c.Mul(a, b).Mod(c, p) }
425 sqr := func(c, a *big.Int) { c.Mul(a, a).Mod(c, p) }
426 exp := func(c, a, b *big.Int) { c.Exp(a, b, p) }
427 sgn := func(a *big.Int) uint { a.Mod(a, p); return a.Bit(0) }
428 cmv := func(c, a, b *big.Int, k bool) {
429 if k {
430 c.Set(b)
431 } else {
432 c.Set(a)
433 }
434 }
435
436 sqr(tv1, u)
437 mul(tv3, Z, tv1)
438 sqr(tv2, tv3)
439 add(xd, tv2, tv3)
440 add(x1n, xd, big.NewInt(1))
441 mul(x1n, x1n, B)
442 tv4.Neg(A)
443 mul(xd, tv4, xd)
444 e1 := xd.Sign() == 0
445 mul(tv4, Z, A)
446 cmv(xd, xd, tv4, e1)
447 sqr(tv2, xd)
448 mul(gxd, tv2, xd)
449 mul(tv2, A, tv2)
450 sqr(gx1, x1n)
451 add(gx1, gx1, tv2)
452 mul(gx1, gx1, x1n)
453 mul(tv2, B, gxd)
454 add(gx1, gx1, tv2)
455 sqr(tv4, gxd)
456 mul(tv2, gx1, gxd)
457 mul(tv4, tv4, tv2)
458 exp(y1, tv4, c1)
459 mul(y1, y1, tv2)
460 mul(x2n, tv3, x1n)
461 mul(y2, y1, C2)
462 mul(y2, y2, tv1)
463 mul(y2, y2, u)
464 sqr(tv2, y1)
465 mul(tv2, tv2, gxd)
466 e2 := tv2.Cmp(gx1) == 0
467 cmv(xn, x2n, x1n, e2)
468 cmv(y, y2, y1, e2)
469 e3 := sgn(u) == sgn(y)
470 tv1.Neg(y)
471 cmv(y, tv1, y, e3)
472 tv1.ModInverse(xd, p)
473 mul(x, xn, tv1)
474 y.Mod(y, p)
475 return &wElt{g, x, y}
476 }
477
View as plain text