1
2
3
4
5
6
7
8
9
10
11 package ecdsa
12
13
14
15
16
17
18
19 import (
20 "crypto"
21 "crypto/aes"
22 "crypto/cipher"
23 "crypto/elliptic"
24 "crypto/sha512"
25 "encoding/asn1"
26 "errors"
27 "io"
28 "math/big"
29 )
30
31
32 type invertible interface {
33
34 Inverse(k *big.Int) *big.Int
35 }
36
37
38 type combinedMult interface {
39 CombinedMult(bigX, bigY *big.Int, baseScalar, scalar []byte) (x, y *big.Int)
40 }
41
42 const (
43 aesIV = "IV for ECDSA CTR"
44 )
45
46
47 type PublicKey struct {
48 elliptic.Curve
49 X, Y *big.Int
50 }
51
52
53 type PrivateKey struct {
54 PublicKey
55 D *big.Int
56 }
57
58 type ecdsaSignature struct {
59 R, S *big.Int
60 }
61
62
63 func (priv *PrivateKey) Public() crypto.PublicKey {
64 return &priv.PublicKey
65 }
66
67
68
69
70
71
72
73
74 func (priv *PrivateKey) Sign(rand io.Reader, digest []byte, opts crypto.SignerOpts) ([]byte, error) {
75 r, s, err := Sign(rand, priv, digest)
76 if err != nil {
77 return nil, err
78 }
79
80 return asn1.Marshal(ecdsaSignature{r, s})
81 }
82
83 var one = new(big.Int).SetInt64(1)
84
85
86
87 func randFieldElement(c elliptic.Curve, rand io.Reader) (k *big.Int, err error) {
88 params := c.Params()
89 b := make([]byte, params.BitSize/8+8)
90 _, err = io.ReadFull(rand, b)
91 if err != nil {
92 return
93 }
94
95 k = new(big.Int).SetBytes(b)
96 n := new(big.Int).Sub(params.N, one)
97 k.Mod(k, n)
98 k.Add(k, one)
99 return
100 }
101
102
103 func GenerateKey(c elliptic.Curve, rand io.Reader) (*PrivateKey, error) {
104 k, err := randFieldElement(c, rand)
105 if err != nil {
106 return nil, err
107 }
108
109 priv := new(PrivateKey)
110 priv.PublicKey.Curve = c
111 priv.D = k
112 priv.PublicKey.X, priv.PublicKey.Y = c.ScalarBaseMult(k.Bytes())
113 return priv, nil
114 }
115
116
117
118
119
120
121
122 func hashToInt(hash []byte, c elliptic.Curve) *big.Int {
123 orderBits := c.Params().N.BitLen()
124 orderBytes := (orderBits + 7) / 8
125 if len(hash) > orderBytes {
126 hash = hash[:orderBytes]
127 }
128
129 ret := new(big.Int).SetBytes(hash)
130 excess := len(hash)*8 - orderBits
131 if excess > 0 {
132 ret.Rsh(ret, uint(excess))
133 }
134 return ret
135 }
136
137
138
139
140
141 func fermatInverse(k, N *big.Int) *big.Int {
142 two := big.NewInt(2)
143 nMinus2 := new(big.Int).Sub(N, two)
144 return new(big.Int).Exp(k, nMinus2, N)
145 }
146
147 var errZeroParam = errors.New("zero parameter")
148
149
150
151
152
153
154 func Sign(rand io.Reader, priv *PrivateKey, hash []byte) (r, s *big.Int, err error) {
155
156 entropylen := (priv.Curve.Params().BitSize + 7) / 16
157 if entropylen > 32 {
158 entropylen = 32
159 }
160 entropy := make([]byte, entropylen)
161 _, err = io.ReadFull(rand, entropy)
162 if err != nil {
163 return
164 }
165
166
167 md := sha512.New()
168 md.Write(priv.D.Bytes())
169 md.Write(entropy)
170 md.Write(hash)
171 key := md.Sum(nil)[:32]
172
173
174
175 block, err := aes.NewCipher(key)
176 if err != nil {
177 return nil, nil, err
178 }
179
180
181
182 csprng := cipher.StreamReader{
183 R: zeroReader,
184 S: cipher.NewCTR(block, []byte(aesIV)),
185 }
186
187
188 c := priv.PublicKey.Curve
189 N := c.Params().N
190 if N.Sign() == 0 {
191 return nil, nil, errZeroParam
192 }
193 var k, kInv *big.Int
194 for {
195 for {
196 k, err = randFieldElement(c, csprng)
197 if err != nil {
198 r = nil
199 return
200 }
201
202 if in, ok := priv.Curve.(invertible); ok {
203 kInv = in.Inverse(k)
204 } else {
205 kInv = fermatInverse(k, N)
206 }
207
208 r, _ = priv.Curve.ScalarBaseMult(k.Bytes())
209 r.Mod(r, N)
210 if r.Sign() != 0 {
211 break
212 }
213 }
214
215 e := hashToInt(hash, c)
216 s = new(big.Int).Mul(priv.D, r)
217 s.Add(s, e)
218 s.Mul(s, kInv)
219 s.Mod(s, N)
220 if s.Sign() != 0 {
221 break
222 }
223 }
224
225 return
226 }
227
228
229
230 func Verify(pub *PublicKey, hash []byte, r, s *big.Int) bool {
231
232 c := pub.Curve
233 N := c.Params().N
234
235 if r.Sign() <= 0 || s.Sign() <= 0 {
236 return false
237 }
238 if r.Cmp(N) >= 0 || s.Cmp(N) >= 0 {
239 return false
240 }
241 e := hashToInt(hash, c)
242
243 var w *big.Int
244 if in, ok := c.(invertible); ok {
245 w = in.Inverse(s)
246 } else {
247 w = new(big.Int).ModInverse(s, N)
248 }
249
250 u1 := e.Mul(e, w)
251 u1.Mod(u1, N)
252 u2 := w.Mul(r, w)
253 u2.Mod(u2, N)
254
255
256 var x, y *big.Int
257 if opt, ok := c.(combinedMult); ok {
258 x, y = opt.CombinedMult(pub.X, pub.Y, u1.Bytes(), u2.Bytes())
259 } else {
260 x1, y1 := c.ScalarBaseMult(u1.Bytes())
261 x2, y2 := c.ScalarMult(pub.X, pub.Y, u2.Bytes())
262 x, y = c.Add(x1, y1, x2, y2)
263 }
264
265 if x.Sign() == 0 && y.Sign() == 0 {
266 return false
267 }
268 x.Mod(x, N)
269 return x.Cmp(r) == 0
270 }
271
272 type zr struct {
273 io.Reader
274 }
275
276
277 func (z *zr) Read(dst []byte) (n int, err error) {
278 for i := range dst {
279 dst[i] = 0
280 }
281 return len(dst), nil
282 }
283
284 var zeroReader = &zr{}
285
View as plain text