1
2
3
4
5
6
7
8 package dsa
9
10 import (
11 "errors"
12 "io"
13 "math/big"
14 )
15
16
17
18 type Parameters struct {
19 P, Q, G *big.Int
20 }
21
22
23 type PublicKey struct {
24 Parameters
25 Y *big.Int
26 }
27
28
29 type PrivateKey struct {
30 PublicKey
31 X *big.Int
32 }
33
34
35
36
37
38 var ErrInvalidPublicKey = errors.New("crypto/dsa: invalid public key")
39
40
41
42 type ParameterSizes int
43
44 const (
45 L1024N160 ParameterSizes = iota
46 L2048N224
47 L2048N256
48 L3072N256
49 )
50
51
52
53 const numMRTests = 64
54
55
56
57 func GenerateParameters(params *Parameters, rand io.Reader, sizes ParameterSizes) error {
58
59
60
61
62
63 var L, N int
64 switch sizes {
65 case L1024N160:
66 L = 1024
67 N = 160
68 case L2048N224:
69 L = 2048
70 N = 224
71 case L2048N256:
72 L = 2048
73 N = 256
74 case L3072N256:
75 L = 3072
76 N = 256
77 default:
78 return errors.New("crypto/dsa: invalid ParameterSizes")
79 }
80
81 qBytes := make([]byte, N/8)
82 pBytes := make([]byte, L/8)
83
84 q := new(big.Int)
85 p := new(big.Int)
86 rem := new(big.Int)
87 one := new(big.Int)
88 one.SetInt64(1)
89
90 GeneratePrimes:
91 for {
92 if _, err := io.ReadFull(rand, qBytes); err != nil {
93 return err
94 }
95
96 qBytes[len(qBytes)-1] |= 1
97 qBytes[0] |= 0x80
98 q.SetBytes(qBytes)
99
100 if !q.ProbablyPrime(numMRTests) {
101 continue
102 }
103
104 for i := 0; i < 4*L; i++ {
105 if _, err := io.ReadFull(rand, pBytes); err != nil {
106 return err
107 }
108
109 pBytes[len(pBytes)-1] |= 1
110 pBytes[0] |= 0x80
111
112 p.SetBytes(pBytes)
113 rem.Mod(p, q)
114 rem.Sub(rem, one)
115 p.Sub(p, rem)
116 if p.BitLen() < L {
117 continue
118 }
119
120 if !p.ProbablyPrime(numMRTests) {
121 continue
122 }
123
124 params.P = p
125 params.Q = q
126 break GeneratePrimes
127 }
128 }
129
130 h := new(big.Int)
131 h.SetInt64(2)
132 g := new(big.Int)
133
134 pm1 := new(big.Int).Sub(p, one)
135 e := new(big.Int).Div(pm1, q)
136
137 for {
138 g.Exp(h, e, p)
139 if g.Cmp(one) == 0 {
140 h.Add(h, one)
141 continue
142 }
143
144 params.G = g
145 return nil
146 }
147 }
148
149
150
151 func GenerateKey(priv *PrivateKey, rand io.Reader) error {
152 if priv.P == nil || priv.Q == nil || priv.G == nil {
153 return errors.New("crypto/dsa: parameters not set up before generating key")
154 }
155
156 x := new(big.Int)
157 xBytes := make([]byte, priv.Q.BitLen()/8)
158
159 for {
160 _, err := io.ReadFull(rand, xBytes)
161 if err != nil {
162 return err
163 }
164 x.SetBytes(xBytes)
165 if x.Sign() != 0 && x.Cmp(priv.Q) < 0 {
166 break
167 }
168 }
169
170 priv.X = x
171 priv.Y = new(big.Int)
172 priv.Y.Exp(priv.G, x, priv.P)
173 return nil
174 }
175
176
177
178
179
180 func fermatInverse(k, P *big.Int) *big.Int {
181 two := big.NewInt(2)
182 pMinus2 := new(big.Int).Sub(P, two)
183 return new(big.Int).Exp(k, pMinus2, P)
184 }
185
186
187
188
189
190
191
192
193
194
195
196
197 func Sign(rand io.Reader, priv *PrivateKey, hash []byte) (r, s *big.Int, err error) {
198
199
200 n := priv.Q.BitLen()
201 if priv.Q.Sign() <= 0 || priv.P.Sign() <= 0 || priv.G.Sign() <= 0 || priv.X.Sign() <= 0 || n&7 != 0 {
202 err = ErrInvalidPublicKey
203 return
204 }
205 n >>= 3
206
207 var attempts int
208 for attempts = 10; attempts > 0; attempts-- {
209 k := new(big.Int)
210 buf := make([]byte, n)
211 for {
212 _, err = io.ReadFull(rand, buf)
213 if err != nil {
214 return
215 }
216 k.SetBytes(buf)
217
218
219
220
221 if k.Sign() > 0 && k.Cmp(priv.Q) < 0 {
222 break
223 }
224 }
225
226 kInv := fermatInverse(k, priv.Q)
227
228 r = new(big.Int).Exp(priv.G, k, priv.P)
229 r.Mod(r, priv.Q)
230
231 if r.Sign() == 0 {
232 continue
233 }
234
235 z := k.SetBytes(hash)
236
237 s = new(big.Int).Mul(priv.X, r)
238 s.Add(s, z)
239 s.Mod(s, priv.Q)
240 s.Mul(s, kInv)
241 s.Mod(s, priv.Q)
242
243 if s.Sign() != 0 {
244 break
245 }
246 }
247
248
249
250 if attempts == 0 {
251 return nil, nil, ErrInvalidPublicKey
252 }
253
254 return
255 }
256
257
258
259
260
261
262
263 func Verify(pub *PublicKey, hash []byte, r, s *big.Int) bool {
264
265
266 if pub.P.Sign() == 0 {
267 return false
268 }
269
270 if r.Sign() < 1 || r.Cmp(pub.Q) >= 0 {
271 return false
272 }
273 if s.Sign() < 1 || s.Cmp(pub.Q) >= 0 {
274 return false
275 }
276
277 w := new(big.Int).ModInverse(s, pub.Q)
278
279 n := pub.Q.BitLen()
280 if n&7 != 0 {
281 return false
282 }
283 z := new(big.Int).SetBytes(hash)
284
285 u1 := new(big.Int).Mul(z, w)
286 u1.Mod(u1, pub.Q)
287 u2 := w.Mul(r, w)
288 u2.Mod(u2, pub.Q)
289 v := u1.Exp(pub.G, u1, pub.P)
290 u2.Exp(pub.Y, u2, pub.P)
291 v.Mul(v, u2)
292 v.Mod(v, pub.P)
293 v.Mod(v, pub.Q)
294
295 return v.Cmp(r) == 0
296 }
297
View as plain text