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.
5 // Package dsa implements the Digital Signature Algorithm, as defined in FIPS 186-3.
14 // Parameters represents the domain parameters for a key. These parameters can
15 // be shared across many keys. The bit length of Q must be a multiple of 8.
16 type Parameters
struct {
20 // PublicKey represents a DSA public key.
21 type PublicKey
struct {
26 // PrivateKey represents a DSA private key.
27 type PrivateKey
struct {
32 // ErrInvalidPublicKey results when a public key is not usable by this code.
33 // FIPS is quite strict about the format of DSA keys, but other code may be
34 // less so. Thus, when using keys which may have been generated by other code,
35 // this error must be handled.
36 var ErrInvalidPublicKey
= errors
.New("crypto/dsa: invalid public key")
38 // ParameterSizes is a enumeration of the acceptable bit lengths of the primes
39 // in a set of DSA parameters. See FIPS 186-3, section 4.2.
40 type ParameterSizes
int
43 L1024N160 ParameterSizes
= iota
49 // numMRTests is the number of Miller-Rabin primality tests that we perform. We
50 // pick the largest recommended number from table C.1 of FIPS 186-3.
53 // GenerateParameters puts a random, valid set of DSA parameters into params.
54 // This function takes many seconds, even on fast machines.
55 func GenerateParameters(params
*Parameters
, rand io
.Reader
, sizes ParameterSizes
) (err error
) {
56 // This function doesn't follow FIPS 186-3 exactly in that it doesn't
57 // use a verification seed to generate the primes. The verification
58 // seed doesn't appear to be exported or used by other code and
59 // omitting it makes the code cleaner.
76 return errors
.New("crypto/dsa: invalid ParameterSizes")
79 qBytes
:= make([]byte, N
/8)
80 pBytes
:= make([]byte, L
/8)
90 _
, err
= io
.ReadFull(rand
, qBytes
)
95 qBytes
[len(qBytes
)-1] |
= 1
99 if !q
.ProbablyPrime(numMRTests
) {
103 for i
:= 0; i
< 4*L
; i
++ {
104 _
, err
= io
.ReadFull(rand
, pBytes
)
109 pBytes
[len(pBytes
)-1] |
= 1
120 if !p
.ProbablyPrime(numMRTests
) {
134 pm1
:= new(big
.Int
).Sub(p
, one
)
135 e
:= new(big
.Int
).Div(pm1
, q
)
149 // GenerateKey generates a public&private key pair. The Parameters of the
150 // PrivateKey must already be valid (see GenerateParameters).
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")
157 xBytes
:= make([]byte, priv
.Q
.BitLen()/8)
160 _
, err
:= io
.ReadFull(rand
, xBytes
)
165 if x
.Sign() != 0 && x
.Cmp(priv
.Q
) < 0 {
171 priv
.Y
= new(big
.Int
)
172 priv
.Y
.Exp(priv
.G
, x
, priv
.P
)
176 // fermatInverse calculates the inverse of k in GF(P) using Fermat's method.
177 // This has better constant-time properties than Euclid's method (implemented
178 // in math/big.Int.ModInverse) although math/big itself isn't strictly
179 // constant-time so it's not perfect.
180 func fermatInverse(k
, P
*big
.Int
) *big
.Int
{
182 pMinus2
:= new(big
.Int
).Sub(P
, two
)
183 return new(big
.Int
).Exp(k
, pMinus2
, P
)
186 // Sign signs an arbitrary length hash (which should be the result of hashing a
187 // larger message) using the private key, priv. It returns the signature as a
188 // pair of integers. The security of the private key depends on the entropy of
191 // Note that FIPS 186-3 section 4.6 specifies that the hash should be truncated
192 // to the byte-length of the subgroup. This function does not perform that
193 // truncation itself.
194 func Sign(rand io
.Reader
, priv
*PrivateKey
, hash
[]byte) (r
, s
*big
.Int
, err error
) {
195 // FIPS 186-3, section 4.6
199 err
= ErrInvalidPublicKey
206 buf
:= make([]byte, n
)
208 _
, err
= io
.ReadFull(rand
, buf
)
213 if k
.Sign() > 0 && k
.Cmp(priv
.Q
) < 0 {
218 kInv
:= fermatInverse(k
, priv
.Q
)
220 r
= new(big
.Int
).Exp(priv
.G
, k
, priv
.P
)
227 z
:= k
.SetBytes(hash
)
229 s
= new(big
.Int
).Mul(priv
.X
, r
)
243 // Verify verifies the signature in r, s of hash using the public key, pub. It
244 // reports whether the signature is valid.
246 // Note that FIPS 186-3 section 4.6 specifies that the hash should be truncated
247 // to the byte-length of the subgroup. This function does not perform that
248 // truncation itself.
249 func Verify(pub
*PublicKey
, hash
[]byte, r
, s
*big
.Int
) bool {
250 // FIPS 186-3, section 4.7
252 if r
.Sign() < 1 || r
.Cmp(pub
.Q
) >= 0 {
255 if s
.Sign() < 1 || s
.Cmp(pub
.Q
) >= 0 {
259 w
:= new(big
.Int
).ModInverse(s
, pub
.Q
)
265 z
:= new(big
.Int
).SetBytes(hash
)
267 u1
:= new(big
.Int
).Mul(z
, w
)
271 v
:= u1
.Exp(pub
.G
, u1
, pub
.P
)
272 u2
.Exp(pub
.Y
, u2
, pub
.P
)