1
2
3
4
5
6
7 package elliptic
8
9
10
11
12
13
14
15
16 import (
17 "io"
18 "math/big"
19 "sync"
20 )
21
22
23
24
25
26
27 type Curve interface {
28
29 Params() *CurveParams
30
31 IsOnCurve(x, y *big.Int) bool
32
33 Add(x1, y1, x2, y2 *big.Int) (x, y *big.Int)
34
35 Double(x1, y1 *big.Int) (x, y *big.Int)
36
37 ScalarMult(x1, y1 *big.Int, k []byte) (x, y *big.Int)
38
39
40 ScalarBaseMult(k []byte) (x, y *big.Int)
41 }
42
43 func matchesSpecificCurve(params *CurveParams, available ...Curve) (Curve, bool) {
44 for _, c := range available {
45 if params == c.Params() {
46 return c, true
47 }
48 }
49 return nil, false
50 }
51
52
53
54 type CurveParams struct {
55 P *big.Int
56 N *big.Int
57 B *big.Int
58 Gx, Gy *big.Int
59 BitSize int
60 Name string
61 }
62
63 func (curve *CurveParams) Params() *CurveParams {
64 return curve
65 }
66
67
68 func (curve *CurveParams) polynomial(x *big.Int) *big.Int {
69 x3 := new(big.Int).Mul(x, x)
70 x3.Mul(x3, x)
71
72 threeX := new(big.Int).Lsh(x, 1)
73 threeX.Add(threeX, x)
74
75 x3.Sub(x3, threeX)
76 x3.Add(x3, curve.B)
77 x3.Mod(x3, curve.P)
78
79 return x3
80 }
81
82 func (curve *CurveParams) IsOnCurve(x, y *big.Int) bool {
83
84
85 if specific, ok := matchesSpecificCurve(curve, p224, p521); ok {
86 return specific.IsOnCurve(x, y)
87 }
88
89
90 y2 := new(big.Int).Mul(y, y)
91 y2.Mod(y2, curve.P)
92
93 return curve.polynomial(x).Cmp(y2) == 0
94 }
95
96
97
98
99 func zForAffine(x, y *big.Int) *big.Int {
100 z := new(big.Int)
101 if x.Sign() != 0 || y.Sign() != 0 {
102 z.SetInt64(1)
103 }
104 return z
105 }
106
107
108
109 func (curve *CurveParams) affineFromJacobian(x, y, z *big.Int) (xOut, yOut *big.Int) {
110 if z.Sign() == 0 {
111 return new(big.Int), new(big.Int)
112 }
113
114 zinv := new(big.Int).ModInverse(z, curve.P)
115 zinvsq := new(big.Int).Mul(zinv, zinv)
116
117 xOut = new(big.Int).Mul(x, zinvsq)
118 xOut.Mod(xOut, curve.P)
119 zinvsq.Mul(zinvsq, zinv)
120 yOut = new(big.Int).Mul(y, zinvsq)
121 yOut.Mod(yOut, curve.P)
122 return
123 }
124
125 func (curve *CurveParams) Add(x1, y1, x2, y2 *big.Int) (*big.Int, *big.Int) {
126
127
128 if specific, ok := matchesSpecificCurve(curve, p224, p521); ok {
129 return specific.Add(x1, y1, x2, y2)
130 }
131
132 z1 := zForAffine(x1, y1)
133 z2 := zForAffine(x2, y2)
134 return curve.affineFromJacobian(curve.addJacobian(x1, y1, z1, x2, y2, z2))
135 }
136
137
138
139 func (curve *CurveParams) addJacobian(x1, y1, z1, x2, y2, z2 *big.Int) (*big.Int, *big.Int, *big.Int) {
140
141 x3, y3, z3 := new(big.Int), new(big.Int), new(big.Int)
142 if z1.Sign() == 0 {
143 x3.Set(x2)
144 y3.Set(y2)
145 z3.Set(z2)
146 return x3, y3, z3
147 }
148 if z2.Sign() == 0 {
149 x3.Set(x1)
150 y3.Set(y1)
151 z3.Set(z1)
152 return x3, y3, z3
153 }
154
155 z1z1 := new(big.Int).Mul(z1, z1)
156 z1z1.Mod(z1z1, curve.P)
157 z2z2 := new(big.Int).Mul(z2, z2)
158 z2z2.Mod(z2z2, curve.P)
159
160 u1 := new(big.Int).Mul(x1, z2z2)
161 u1.Mod(u1, curve.P)
162 u2 := new(big.Int).Mul(x2, z1z1)
163 u2.Mod(u2, curve.P)
164 h := new(big.Int).Sub(u2, u1)
165 xEqual := h.Sign() == 0
166 if h.Sign() == -1 {
167 h.Add(h, curve.P)
168 }
169 i := new(big.Int).Lsh(h, 1)
170 i.Mul(i, i)
171 j := new(big.Int).Mul(h, i)
172
173 s1 := new(big.Int).Mul(y1, z2)
174 s1.Mul(s1, z2z2)
175 s1.Mod(s1, curve.P)
176 s2 := new(big.Int).Mul(y2, z1)
177 s2.Mul(s2, z1z1)
178 s2.Mod(s2, curve.P)
179 r := new(big.Int).Sub(s2, s1)
180 if r.Sign() == -1 {
181 r.Add(r, curve.P)
182 }
183 yEqual := r.Sign() == 0
184 if xEqual && yEqual {
185 return curve.doubleJacobian(x1, y1, z1)
186 }
187 r.Lsh(r, 1)
188 v := new(big.Int).Mul(u1, i)
189
190 x3.Set(r)
191 x3.Mul(x3, x3)
192 x3.Sub(x3, j)
193 x3.Sub(x3, v)
194 x3.Sub(x3, v)
195 x3.Mod(x3, curve.P)
196
197 y3.Set(r)
198 v.Sub(v, x3)
199 y3.Mul(y3, v)
200 s1.Mul(s1, j)
201 s1.Lsh(s1, 1)
202 y3.Sub(y3, s1)
203 y3.Mod(y3, curve.P)
204
205 z3.Add(z1, z2)
206 z3.Mul(z3, z3)
207 z3.Sub(z3, z1z1)
208 z3.Sub(z3, z2z2)
209 z3.Mul(z3, h)
210 z3.Mod(z3, curve.P)
211
212 return x3, y3, z3
213 }
214
215 func (curve *CurveParams) Double(x1, y1 *big.Int) (*big.Int, *big.Int) {
216
217
218 if specific, ok := matchesSpecificCurve(curve, p224, p521); ok {
219 return specific.Double(x1, y1)
220 }
221
222 z1 := zForAffine(x1, y1)
223 return curve.affineFromJacobian(curve.doubleJacobian(x1, y1, z1))
224 }
225
226
227
228 func (curve *CurveParams) doubleJacobian(x, y, z *big.Int) (*big.Int, *big.Int, *big.Int) {
229
230 delta := new(big.Int).Mul(z, z)
231 delta.Mod(delta, curve.P)
232 gamma := new(big.Int).Mul(y, y)
233 gamma.Mod(gamma, curve.P)
234 alpha := new(big.Int).Sub(x, delta)
235 if alpha.Sign() == -1 {
236 alpha.Add(alpha, curve.P)
237 }
238 alpha2 := new(big.Int).Add(x, delta)
239 alpha.Mul(alpha, alpha2)
240 alpha2.Set(alpha)
241 alpha.Lsh(alpha, 1)
242 alpha.Add(alpha, alpha2)
243
244 beta := alpha2.Mul(x, gamma)
245
246 x3 := new(big.Int).Mul(alpha, alpha)
247 beta8 := new(big.Int).Lsh(beta, 3)
248 beta8.Mod(beta8, curve.P)
249 x3.Sub(x3, beta8)
250 if x3.Sign() == -1 {
251 x3.Add(x3, curve.P)
252 }
253 x3.Mod(x3, curve.P)
254
255 z3 := new(big.Int).Add(y, z)
256 z3.Mul(z3, z3)
257 z3.Sub(z3, gamma)
258 if z3.Sign() == -1 {
259 z3.Add(z3, curve.P)
260 }
261 z3.Sub(z3, delta)
262 if z3.Sign() == -1 {
263 z3.Add(z3, curve.P)
264 }
265 z3.Mod(z3, curve.P)
266
267 beta.Lsh(beta, 2)
268 beta.Sub(beta, x3)
269 if beta.Sign() == -1 {
270 beta.Add(beta, curve.P)
271 }
272 y3 := alpha.Mul(alpha, beta)
273
274 gamma.Mul(gamma, gamma)
275 gamma.Lsh(gamma, 3)
276 gamma.Mod(gamma, curve.P)
277
278 y3.Sub(y3, gamma)
279 if y3.Sign() == -1 {
280 y3.Add(y3, curve.P)
281 }
282 y3.Mod(y3, curve.P)
283
284 return x3, y3, z3
285 }
286
287 func (curve *CurveParams) ScalarMult(Bx, By *big.Int, k []byte) (*big.Int, *big.Int) {
288
289
290 if specific, ok := matchesSpecificCurve(curve, p224, p256, p521); ok {
291 return specific.ScalarMult(Bx, By, k)
292 }
293
294 Bz := new(big.Int).SetInt64(1)
295 x, y, z := new(big.Int), new(big.Int), new(big.Int)
296
297 for _, byte := range k {
298 for bitNum := 0; bitNum < 8; bitNum++ {
299 x, y, z = curve.doubleJacobian(x, y, z)
300 if byte&0x80 == 0x80 {
301 x, y, z = curve.addJacobian(Bx, By, Bz, x, y, z)
302 }
303 byte <<= 1
304 }
305 }
306
307 return curve.affineFromJacobian(x, y, z)
308 }
309
310 func (curve *CurveParams) ScalarBaseMult(k []byte) (*big.Int, *big.Int) {
311
312
313 if specific, ok := matchesSpecificCurve(curve, p224, p256, p521); ok {
314 return specific.ScalarBaseMult(k)
315 }
316
317 return curve.ScalarMult(curve.Gx, curve.Gy, k)
318 }
319
320 var mask = []byte{0xff, 0x1, 0x3, 0x7, 0xf, 0x1f, 0x3f, 0x7f}
321
322
323
324 func GenerateKey(curve Curve, rand io.Reader) (priv []byte, x, y *big.Int, err error) {
325 N := curve.Params().N
326 bitSize := N.BitLen()
327 byteLen := (bitSize + 7) / 8
328 priv = make([]byte, byteLen)
329
330 for x == nil {
331 _, err = io.ReadFull(rand, priv)
332 if err != nil {
333 return
334 }
335
336
337 priv[0] &= mask[bitSize%8]
338
339
340 priv[1] ^= 0x42
341
342
343 if new(big.Int).SetBytes(priv).Cmp(N) >= 0 {
344 continue
345 }
346
347 x, y = curve.ScalarBaseMult(priv)
348 }
349 return
350 }
351
352
353
354 func Marshal(curve Curve, x, y *big.Int) []byte {
355 byteLen := (curve.Params().BitSize + 7) / 8
356
357 ret := make([]byte, 1+2*byteLen)
358 ret[0] = 4
359
360 x.FillBytes(ret[1 : 1+byteLen])
361 y.FillBytes(ret[1+byteLen : 1+2*byteLen])
362
363 return ret
364 }
365
366
367
368 func MarshalCompressed(curve Curve, x, y *big.Int) []byte {
369 byteLen := (curve.Params().BitSize + 7) / 8
370 compressed := make([]byte, 1+byteLen)
371 compressed[0] = byte(y.Bit(0)) | 2
372 x.FillBytes(compressed[1:])
373 return compressed
374 }
375
376
377
378
379 func Unmarshal(curve Curve, data []byte) (x, y *big.Int) {
380 byteLen := (curve.Params().BitSize + 7) / 8
381 if len(data) != 1+2*byteLen {
382 return nil, nil
383 }
384 if data[0] != 4 {
385 return nil, nil
386 }
387 p := curve.Params().P
388 x = new(big.Int).SetBytes(data[1 : 1+byteLen])
389 y = new(big.Int).SetBytes(data[1+byteLen:])
390 if x.Cmp(p) >= 0 || y.Cmp(p) >= 0 {
391 return nil, nil
392 }
393 if !curve.IsOnCurve(x, y) {
394 return nil, nil
395 }
396 return
397 }
398
399
400
401
402 func UnmarshalCompressed(curve Curve, data []byte) (x, y *big.Int) {
403 byteLen := (curve.Params().BitSize + 7) / 8
404 if len(data) != 1+byteLen {
405 return nil, nil
406 }
407 if data[0] != 2 && data[0] != 3 {
408 return nil, nil
409 }
410 p := curve.Params().P
411 x = new(big.Int).SetBytes(data[1:])
412 if x.Cmp(p) >= 0 {
413 return nil, nil
414 }
415
416 y = curve.Params().polynomial(x)
417 y = y.ModSqrt(y, p)
418 if y == nil {
419 return nil, nil
420 }
421 if byte(y.Bit(0)) != data[0]&1 {
422 y.Neg(y).Mod(y, p)
423 }
424 if !curve.IsOnCurve(x, y) {
425 return nil, nil
426 }
427 return
428 }
429
430 var initonce sync.Once
431 var p384 *CurveParams
432
433 func initAll() {
434 initP224()
435 initP256()
436 initP384()
437 initP521()
438 }
439
440 func initP384() {
441
442 p384 = &CurveParams{Name: "P-384"}
443 p384.P, _ = new(big.Int).SetString("39402006196394479212279040100143613805079739270465446667948293404245721771496870329047266088258938001861606973112319", 10)
444 p384.N, _ = new(big.Int).SetString("39402006196394479212279040100143613805079739270465446667946905279627659399113263569398956308152294913554433653942643", 10)
445 p384.B, _ = new(big.Int).SetString("b3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5013875ac656398d8a2ed19d2a85c8edd3ec2aef", 16)
446 p384.Gx, _ = new(big.Int).SetString("aa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741e082542a385502f25dbf55296c3a545e3872760ab7", 16)
447 p384.Gy, _ = new(big.Int).SetString("3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da3113b5f0b8c00a60b1ce1d7e819d7a431d7c90ea0e5f", 16)
448 p384.BitSize = 384
449 }
450
451
452
453
454
455
456
457
458
459 func P256() Curve {
460 initonce.Do(initAll)
461 return p256
462 }
463
464
465
466
467
468
469
470
471 func P384() Curve {
472 initonce.Do(initAll)
473 return p384
474 }
475
476
477
478
479
480
481
482
483 func P521() Curve {
484 initonce.Do(initAll)
485 return p521
486 }
487
View as plain text