1 // Copyright 2011 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
4 5 // Package dsa implements the Digital Signature Algorithm, as defined in FIPS 186-3.
6 //
7 // The DSA operations in this package are not implemented using constant-time algorithms.
8 //
9 // Deprecated: DSA is a legacy algorithm, and modern alternatives such as
10 // Ed25519 (implemented by package crypto/ed25519) should be used instead. Keys
11 // with 1024-bit moduli (L1024N160 parameters) are cryptographically weak, while
12 // bigger keys are not widely supported. Note that FIPS 186-5 no longer approves
13 // DSA for signature generation.
14 package dsa
15 16 import (
17 "errors"
18 "io"
19 "math/big"
20 21 "crypto/internal/fips140only"
22 "crypto/internal/randutil"
23 )
24 25 // Parameters represents the domain parameters for a key. These parameters can
26 // be shared across many keys. The bit length of Q must be a multiple of 8.
27 type Parameters struct {
28 P, Q, G *big.Int
29 }
30 31 // PublicKey represents a DSA public key.
32 type PublicKey struct {
33 Parameters
34 Y *big.Int
35 }
36 37 // PrivateKey represents a DSA private key.
38 type PrivateKey struct {
39 PublicKey
40 X *big.Int
41 }
42 43 // ErrInvalidPublicKey results when a public key is not usable by this code.
44 // FIPS is quite strict about the format of DSA keys, but other code may be
45 // less so. Thus, when using keys which may have been generated by other code,
46 // this error must be handled.
47 var ErrInvalidPublicKey = errors.New("crypto/dsa: invalid public key")
48 49 // ParameterSizes is an enumeration of the acceptable bit lengths of the primes
50 // in a set of DSA parameters. See FIPS 186-3, section 4.2.
51 type ParameterSizes int
52 53 const (
54 L1024N160 ParameterSizes = iota
55 L2048N224
56 L2048N256
57 L3072N256
58 )
59 60 // numMRTests is the number of Miller-Rabin primality tests that we perform. We
61 // pick the largest recommended number from table C.1 of FIPS 186-3.
62 const numMRTests = 64
63 64 // GenerateParameters puts a random, valid set of DSA parameters into params.
65 // This function can take many seconds, even on fast machines.
66 func GenerateParameters(params *Parameters, rand io.Reader, sizes ParameterSizes) error {
67 if fips140only.Enabled {
68 return errors.New("crypto/dsa: use of DSA is not allowed in FIPS 140-only mode")
69 }
70 71 // This function doesn't follow FIPS 186-3 exactly in that it doesn't
72 // use a verification seed to generate the primes. The verification
73 // seed doesn't appear to be exported or used by other code and
74 // omitting it makes the code cleaner.
75 76 var L, N int
77 switch sizes {
78 case L1024N160:
79 L = 1024
80 N = 160
81 case L2048N224:
82 L = 2048
83 N = 224
84 case L2048N256:
85 L = 2048
86 N = 256
87 case L3072N256:
88 L = 3072
89 N = 256
90 default:
91 return errors.New("crypto/dsa: invalid ParameterSizes")
92 }
93 94 qBytes := []byte{:N/8}
95 pBytes := []byte{:L/8}
96 97 q := &big.Int{}
98 p := &big.Int{}
99 rem := &big.Int{}
100 one := &big.Int{}
101 one.SetInt64(1)
102 103 GeneratePrimes:
104 for {
105 if _, err := io.ReadFull(rand, qBytes); err != nil {
106 return err
107 }
108 109 qBytes[len(qBytes)-1] |= 1
110 qBytes[0] |= 0x80
111 q.SetBytes(qBytes)
112 113 if !q.ProbablyPrime(numMRTests) {
114 continue
115 }
116 117 for i := 0; i < 4*L; i++ {
118 if _, err := io.ReadFull(rand, pBytes); err != nil {
119 return err
120 }
121 122 pBytes[len(pBytes)-1] |= 1
123 pBytes[0] |= 0x80
124 125 p.SetBytes(pBytes)
126 rem.Mod(p, q)
127 rem.Sub(rem, one)
128 p.Sub(p, rem)
129 if p.BitLen() < L {
130 continue
131 }
132 133 if !p.ProbablyPrime(numMRTests) {
134 continue
135 }
136 137 params.P = p
138 params.Q = q
139 break GeneratePrimes
140 }
141 }
142 143 h := &big.Int{}
144 h.SetInt64(2)
145 g := &big.Int{}
146 147 pm1 := (&big.Int{}).Sub(p, one)
148 e := (&big.Int{}).Div(pm1, q)
149 150 for {
151 g.Exp(h, e, p)
152 if g.Cmp(one) == 0 {
153 h.Add(h, one)
154 continue
155 }
156 157 params.G = g
158 return nil
159 }
160 }
161 162 // GenerateKey generates a public&private key pair. The Parameters of the
163 // [PrivateKey] must already be valid (see [GenerateParameters]).
164 func GenerateKey(priv *PrivateKey, rand io.Reader) error {
165 if fips140only.Enabled {
166 return errors.New("crypto/dsa: use of DSA is not allowed in FIPS 140-only mode")
167 }
168 169 if priv.P == nil || priv.Q == nil || priv.G == nil {
170 return errors.New("crypto/dsa: parameters not set up before generating key")
171 }
172 173 x := &big.Int{}
174 xBytes := []byte{:priv.Q.BitLen()/8}
175 176 for {
177 _, err := io.ReadFull(rand, xBytes)
178 if err != nil {
179 return err
180 }
181 x.SetBytes(xBytes)
182 if x.Sign() != 0 && x.Cmp(priv.Q) < 0 {
183 break
184 }
185 }
186 187 priv.X = x
188 priv.Y = &big.Int{}
189 priv.Y.Exp(priv.G, x, priv.P)
190 return nil
191 }
192 193 // fermatInverse calculates the inverse of k in GF(P) using Fermat's method.
194 // This has better constant-time properties than Euclid's method (implemented
195 // in math/big.Int.ModInverse) although math/big itself isn't strictly
196 // constant-time so it's not perfect.
197 func fermatInverse(k, P *big.Int) *big.Int {
198 two := big.NewInt(2)
199 pMinus2 := (&big.Int{}).Sub(P, two)
200 return (&big.Int{}).Exp(k, pMinus2, P)
201 }
202 203 // Sign signs an arbitrary length hash (which should be the result of hashing a
204 // larger message) using the private key, priv. It returns the signature as a
205 // pair of integers. The security of the private key depends on the entropy of
206 // rand.
207 //
208 // Note that FIPS 186-3 section 4.6 specifies that the hash should be truncated
209 // to the byte-length of the subgroup. This function does not perform that
210 // truncation itself.
211 //
212 // Be aware that calling Sign with an attacker-controlled [PrivateKey] may
213 // require an arbitrary amount of CPU.
214 func Sign(rand io.Reader, priv *PrivateKey, hash []byte) (r, s *big.Int, err error) {
215 if fips140only.Enabled {
216 return nil, nil, errors.New("crypto/dsa: use of DSA is not allowed in FIPS 140-only mode")
217 }
218 219 randutil.MaybeReadByte(rand)
220 221 // FIPS 186-3, section 4.6
222 223 n := priv.Q.BitLen()
224 if priv.Q.Sign() <= 0 || priv.P.Sign() <= 0 || priv.G.Sign() <= 0 || priv.X.Sign() <= 0 || n%8 != 0 {
225 err = ErrInvalidPublicKey
226 return
227 }
228 n >>= 3
229 230 var attempts int
231 for attempts = 10; attempts > 0; attempts-- {
232 k := &big.Int{}
233 buf := []byte{:n}
234 for {
235 _, err = io.ReadFull(rand, buf)
236 if err != nil {
237 return
238 }
239 k.SetBytes(buf)
240 // priv.Q must be >= 128 because the test above
241 // requires it to be > 0 and that
242 // ceil(log_2(Q)) mod 8 = 0
243 // Thus this loop will quickly terminate.
244 if k.Sign() > 0 && k.Cmp(priv.Q) < 0 {
245 break
246 }
247 }
248 249 kInv := fermatInverse(k, priv.Q)
250 251 r = (&big.Int{}).Exp(priv.G, k, priv.P)
252 r.Mod(r, priv.Q)
253 254 if r.Sign() == 0 {
255 continue
256 }
257 258 z := k.SetBytes(hash)
259 260 s = (&big.Int{}).Mul(priv.X, r)
261 s.Add(s, z)
262 s.Mod(s, priv.Q)
263 s.Mul(s, kInv)
264 s.Mod(s, priv.Q)
265 266 if s.Sign() != 0 {
267 break
268 }
269 }
270 271 // Only degenerate private keys will require more than a handful of
272 // attempts.
273 if attempts == 0 {
274 return nil, nil, ErrInvalidPublicKey
275 }
276 277 return
278 }
279 280 // Verify verifies the signature in r, s of hash using the public key, pub. It
281 // reports whether the signature is valid.
282 //
283 // Note that FIPS 186-3 section 4.6 specifies that the hash should be truncated
284 // to the byte-length of the subgroup. This function does not perform that
285 // truncation itself.
286 func Verify(pub *PublicKey, hash []byte, r, s *big.Int) bool {
287 if fips140only.Enabled {
288 panic("crypto/dsa: use of DSA is not allowed in FIPS 140-only mode")
289 }
290 291 // FIPS 186-3, section 4.7
292 293 if pub.P.Sign() == 0 {
294 return false
295 }
296 297 if r.Sign() < 1 || r.Cmp(pub.Q) >= 0 {
298 return false
299 }
300 if s.Sign() < 1 || s.Cmp(pub.Q) >= 0 {
301 return false
302 }
303 304 w := (&big.Int{}).ModInverse(s, pub.Q)
305 if w == nil {
306 return false
307 }
308 309 n := pub.Q.BitLen()
310 if n%8 != 0 {
311 return false
312 }
313 z := (&big.Int{}).SetBytes(hash)
314 315 u1 := (&big.Int{}).Mul(z, w)
316 u1.Mod(u1, pub.Q)
317 u2 := w.Mul(r, w)
318 u2.Mod(u2, pub.Q)
319 v := u1.Exp(pub.G, u1, pub.P)
320 u2.Exp(pub.Y, u2, pub.P)
321 v.Mul(v, u2)
322 v.Mod(v, pub.P)
323 v.Mod(v, pub.Q)
324 325 return v.Cmp(r) == 0
326 }
327