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 type Curve interface {
25
26 Params() *CurveParams
27
28 IsOnCurve(x, y *big.Int) bool
29
30 Add(x1, y1, x2, y2 *big.Int) (x, y *big.Int)
31
32 Double(x1, y1 *big.Int) (x, y *big.Int)
33
34 ScalarMult(x1, y1 *big.Int, k []byte) (x, y *big.Int)
35
36
37 ScalarBaseMult(k []byte) (x, y *big.Int)
38 }
39
40
41
42 type CurveParams struct {
43 P *big.Int
44 N *big.Int
45 B *big.Int
46 Gx, Gy *big.Int
47 BitSize int
48 Name string
49 }
50
51 func (curve *CurveParams) Params() *CurveParams {
52 return curve
53 }
54
55 func (curve *CurveParams) IsOnCurve(x, y *big.Int) bool {
56
57 y2 := new(big.Int).Mul(y, y)
58 y2.Mod(y2, curve.P)
59
60 x3 := new(big.Int).Mul(x, x)
61 x3.Mul(x3, x)
62
63 threeX := new(big.Int).Lsh(x, 1)
64 threeX.Add(threeX, x)
65
66 x3.Sub(x3, threeX)
67 x3.Add(x3, curve.B)
68 x3.Mod(x3, curve.P)
69
70 return x3.Cmp(y2) == 0
71 }
72
73
74
75
76 func zForAffine(x, y *big.Int) *big.Int {
77 z := new(big.Int)
78 if x.Sign() != 0 || y.Sign() != 0 {
79 z.SetInt64(1)
80 }
81 return z
82 }
83
84
85
86 func (curve *CurveParams) affineFromJacobian(x, y, z *big.Int) (xOut, yOut *big.Int) {
87 if z.Sign() == 0 {
88 return new(big.Int), new(big.Int)
89 }
90
91 zinv := new(big.Int).ModInverse(z, curve.P)
92 zinvsq := new(big.Int).Mul(zinv, zinv)
93
94 xOut = new(big.Int).Mul(x, zinvsq)
95 xOut.Mod(xOut, curve.P)
96 zinvsq.Mul(zinvsq, zinv)
97 yOut = new(big.Int).Mul(y, zinvsq)
98 yOut.Mod(yOut, curve.P)
99 return
100 }
101
102 func (curve *CurveParams) Add(x1, y1, x2, y2 *big.Int) (*big.Int, *big.Int) {
103 z1 := zForAffine(x1, y1)
104 z2 := zForAffine(x2, y2)
105 return curve.affineFromJacobian(curve.addJacobian(x1, y1, z1, x2, y2, z2))
106 }
107
108
109
110 func (curve *CurveParams) addJacobian(x1, y1, z1, x2, y2, z2 *big.Int) (*big.Int, *big.Int, *big.Int) {
111
112 x3, y3, z3 := new(big.Int), new(big.Int), new(big.Int)
113 if z1.Sign() == 0 {
114 x3.Set(x2)
115 y3.Set(y2)
116 z3.Set(z2)
117 return x3, y3, z3
118 }
119 if z2.Sign() == 0 {
120 x3.Set(x1)
121 y3.Set(y1)
122 z3.Set(z1)
123 return x3, y3, z3
124 }
125
126 z1z1 := new(big.Int).Mul(z1, z1)
127 z1z1.Mod(z1z1, curve.P)
128 z2z2 := new(big.Int).Mul(z2, z2)
129 z2z2.Mod(z2z2, curve.P)
130
131 u1 := new(big.Int).Mul(x1, z2z2)
132 u1.Mod(u1, curve.P)
133 u2 := new(big.Int).Mul(x2, z1z1)
134 u2.Mod(u2, curve.P)
135 h := new(big.Int).Sub(u2, u1)
136 xEqual := h.Sign() == 0
137 if h.Sign() == -1 {
138 h.Add(h, curve.P)
139 }
140 i := new(big.Int).Lsh(h, 1)
141 i.Mul(i, i)
142 j := new(big.Int).Mul(h, i)
143
144 s1 := new(big.Int).Mul(y1, z2)
145 s1.Mul(s1, z2z2)
146 s1.Mod(s1, curve.P)
147 s2 := new(big.Int).Mul(y2, z1)
148 s2.Mul(s2, z1z1)
149 s2.Mod(s2, curve.P)
150 r := new(big.Int).Sub(s2, s1)
151 if r.Sign() == -1 {
152 r.Add(r, curve.P)
153 }
154 yEqual := r.Sign() == 0
155 if xEqual && yEqual {
156 return curve.doubleJacobian(x1, y1, z1)
157 }
158 r.Lsh(r, 1)
159 v := new(big.Int).Mul(u1, i)
160
161 x3.Set(r)
162 x3.Mul(x3, x3)
163 x3.Sub(x3, j)
164 x3.Sub(x3, v)
165 x3.Sub(x3, v)
166 x3.Mod(x3, curve.P)
167
168 y3.Set(r)
169 v.Sub(v, x3)
170 y3.Mul(y3, v)
171 s1.Mul(s1, j)
172 s1.Lsh(s1, 1)
173 y3.Sub(y3, s1)
174 y3.Mod(y3, curve.P)
175
176 z3.Add(z1, z2)
177 z3.Mul(z3, z3)
178 z3.Sub(z3, z1z1)
179 z3.Sub(z3, z2z2)
180 z3.Mul(z3, h)
181 z3.Mod(z3, curve.P)
182
183 return x3, y3, z3
184 }
185
186 func (curve *CurveParams) Double(x1, y1 *big.Int) (*big.Int, *big.Int) {
187 z1 := zForAffine(x1, y1)
188 return curve.affineFromJacobian(curve.doubleJacobian(x1, y1, z1))
189 }
190
191
192
193 func (curve *CurveParams) doubleJacobian(x, y, z *big.Int) (*big.Int, *big.Int, *big.Int) {
194
195 delta := new(big.Int).Mul(z, z)
196 delta.Mod(delta, curve.P)
197 gamma := new(big.Int).Mul(y, y)
198 gamma.Mod(gamma, curve.P)
199 alpha := new(big.Int).Sub(x, delta)
200 if alpha.Sign() == -1 {
201 alpha.Add(alpha, curve.P)
202 }
203 alpha2 := new(big.Int).Add(x, delta)
204 alpha.Mul(alpha, alpha2)
205 alpha2.Set(alpha)
206 alpha.Lsh(alpha, 1)
207 alpha.Add(alpha, alpha2)
208
209 beta := alpha2.Mul(x, gamma)
210
211 x3 := new(big.Int).Mul(alpha, alpha)
212 beta8 := new(big.Int).Lsh(beta, 3)
213 x3.Sub(x3, beta8)
214 for x3.Sign() == -1 {
215 x3.Add(x3, curve.P)
216 }
217 x3.Mod(x3, curve.P)
218
219 z3 := new(big.Int).Add(y, z)
220 z3.Mul(z3, z3)
221 z3.Sub(z3, gamma)
222 if z3.Sign() == -1 {
223 z3.Add(z3, curve.P)
224 }
225 z3.Sub(z3, delta)
226 if z3.Sign() == -1 {
227 z3.Add(z3, curve.P)
228 }
229 z3.Mod(z3, curve.P)
230
231 beta.Lsh(beta, 2)
232 beta.Sub(beta, x3)
233 if beta.Sign() == -1 {
234 beta.Add(beta, curve.P)
235 }
236 y3 := alpha.Mul(alpha, beta)
237
238 gamma.Mul(gamma, gamma)
239 gamma.Lsh(gamma, 3)
240 gamma.Mod(gamma, curve.P)
241
242 y3.Sub(y3, gamma)
243 if y3.Sign() == -1 {
244 y3.Add(y3, curve.P)
245 }
246 y3.Mod(y3, curve.P)
247
248 return x3, y3, z3
249 }
250
251 func (curve *CurveParams) ScalarMult(Bx, By *big.Int, k []byte) (*big.Int, *big.Int) {
252 Bz := new(big.Int).SetInt64(1)
253 x, y, z := new(big.Int), new(big.Int), new(big.Int)
254
255 for _, byte := range k {
256 for bitNum := 0; bitNum < 8; bitNum++ {
257 x, y, z = curve.doubleJacobian(x, y, z)
258 if byte&0x80 == 0x80 {
259 x, y, z = curve.addJacobian(Bx, By, Bz, x, y, z)
260 }
261 byte <<= 1
262 }
263 }
264
265 return curve.affineFromJacobian(x, y, z)
266 }
267
268 func (curve *CurveParams) ScalarBaseMult(k []byte) (*big.Int, *big.Int) {
269 return curve.ScalarMult(curve.Gx, curve.Gy, k)
270 }
271
272 var mask = []byte{0xff, 0x1, 0x3, 0x7, 0xf, 0x1f, 0x3f, 0x7f}
273
274
275
276 func GenerateKey(curve Curve, rand io.Reader) (priv []byte, x, y *big.Int, err error) {
277 N := curve.Params().N
278 bitSize := N.BitLen()
279 byteLen := (bitSize + 7) >> 3
280 priv = make([]byte, byteLen)
281
282 for x == nil {
283 _, err = io.ReadFull(rand, priv)
284 if err != nil {
285 return
286 }
287
288
289 priv[0] &= mask[bitSize%8]
290
291
292 priv[1] ^= 0x42
293
294
295 if new(big.Int).SetBytes(priv).Cmp(N) >= 0 {
296 continue
297 }
298
299 x, y = curve.ScalarBaseMult(priv)
300 }
301 return
302 }
303
304
305 func Marshal(curve Curve, x, y *big.Int) []byte {
306 byteLen := (curve.Params().BitSize + 7) >> 3
307
308 ret := make([]byte, 1+2*byteLen)
309 ret[0] = 4
310
311 xBytes := x.Bytes()
312 copy(ret[1+byteLen-len(xBytes):], xBytes)
313 yBytes := y.Bytes()
314 copy(ret[1+2*byteLen-len(yBytes):], yBytes)
315 return ret
316 }
317
318
319
320
321 func Unmarshal(curve Curve, data []byte) (x, y *big.Int) {
322 byteLen := (curve.Params().BitSize + 7) >> 3
323 if len(data) != 1+2*byteLen {
324 return
325 }
326 if data[0] != 4 {
327 return
328 }
329 p := curve.Params().P
330 x = new(big.Int).SetBytes(data[1 : 1+byteLen])
331 y = new(big.Int).SetBytes(data[1+byteLen:])
332 if x.Cmp(p) >= 0 || y.Cmp(p) >= 0 {
333 return nil, nil
334 }
335 if !curve.IsOnCurve(x, y) {
336 return nil, nil
337 }
338 return
339 }
340
341 var initonce sync.Once
342 var p384 *CurveParams
343 var p521 *CurveParams
344
345 func initAll() {
346 initP224()
347 initP256()
348 initP384()
349 initP521()
350 }
351
352 func initP384() {
353
354 p384 = &CurveParams{Name: "P-384"}
355 p384.P, _ = new(big.Int).SetString("39402006196394479212279040100143613805079739270465446667948293404245721771496870329047266088258938001861606973112319", 10)
356 p384.N, _ = new(big.Int).SetString("39402006196394479212279040100143613805079739270465446667946905279627659399113263569398956308152294913554433653942643", 10)
357 p384.B, _ = new(big.Int).SetString("b3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5013875ac656398d8a2ed19d2a85c8edd3ec2aef", 16)
358 p384.Gx, _ = new(big.Int).SetString("aa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741e082542a385502f25dbf55296c3a545e3872760ab7", 16)
359 p384.Gy, _ = new(big.Int).SetString("3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da3113b5f0b8c00a60b1ce1d7e819d7a431d7c90ea0e5f", 16)
360 p384.BitSize = 384
361 }
362
363 func initP521() {
364
365 p521 = &CurveParams{Name: "P-521"}
366 p521.P, _ = new(big.Int).SetString("6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151", 10)
367 p521.N, _ = new(big.Int).SetString("6864797660130609714981900799081393217269435300143305409394463459185543183397655394245057746333217197532963996371363321113864768612440380340372808892707005449", 10)
368 p521.B, _ = new(big.Int).SetString("051953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00", 16)
369 p521.Gx, _ = new(big.Int).SetString("c6858e06b70404e9cd9e3ecb662395b4429c648139053fb521f828af606b4d3dbaa14b5e77efe75928fe1dc127a2ffa8de3348b3c1856a429bf97e7e31c2e5bd66", 16)
370 p521.Gy, _ = new(big.Int).SetString("11839296a789a3bc0045c8a5fb42c7d1bd998f54449579b446817afbd17273e662c97ee72995ef42640c550b9013fad0761353c7086a272c24088be94769fd16650", 16)
371 p521.BitSize = 521
372 }
373
374
375
376
377 func P256() Curve {
378 initonce.Do(initAll)
379 return p256
380 }
381
382
383
384
385 func P384() Curve {
386 initonce.Do(initAll)
387 return p384
388 }
389
390
391
392
393 func P521() Curve {
394 initonce.Do(initAll)
395 return p521
396 }
397
View as plain text