// Copyright 2011 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// Package dsa implements the Digital Signature Algorithm, as defined in FIPS 186-3. // // The DSA operations in this package are not implemented using constant-time algorithms. // // Deprecated: DSA is a legacy algorithm, and modern alternatives such as // Ed25519 (implemented by package crypto/ed25519) should be used instead. Keys // with 1024-bit moduli (L1024N160 parameters) are cryptographically weak, while // bigger keys are not widely supported. Note that FIPS 186-5 no longer approves // DSA for signature generation.
package dsa import ( ) // Parameters represents the domain parameters for a key. These parameters can // be shared across many keys. The bit length of Q must be a multiple of 8. type Parameters struct { P, Q, G *big.Int } // PublicKey represents a DSA public key. type PublicKey struct { Parameters Y *big.Int } // PrivateKey represents a DSA private key. type PrivateKey struct { PublicKey X *big.Int } // ErrInvalidPublicKey results when a public key is not usable by this code. // FIPS is quite strict about the format of DSA keys, but other code may be // less so. Thus, when using keys which may have been generated by other code, // this error must be handled. var ErrInvalidPublicKey = errors.New("crypto/dsa: invalid public key") // ParameterSizes is an enumeration of the acceptable bit lengths of the primes // in a set of DSA parameters. See FIPS 186-3, section 4.2. type ParameterSizes int const ( L1024N160 ParameterSizes = iota L2048N224 L2048N256 L3072N256 ) // numMRTests is the number of Miller-Rabin primality tests that we perform. We // pick the largest recommended number from table C.1 of FIPS 186-3. const numMRTests = 64 // GenerateParameters puts a random, valid set of DSA parameters into params. // This function can take many seconds, even on fast machines. func ( *Parameters, io.Reader, ParameterSizes) error { // This function doesn't follow FIPS 186-3 exactly in that it doesn't // use a verification seed to generate the primes. The verification // seed doesn't appear to be exported or used by other code and // omitting it makes the code cleaner. var , int switch { case L1024N160: = 1024 = 160 case L2048N224: = 2048 = 224 case L2048N256: = 2048 = 256 case L3072N256: = 3072 = 256 default: return errors.New("crypto/dsa: invalid ParameterSizes") } := make([]byte, /8) := make([]byte, /8) := new(big.Int) := new(big.Int) := new(big.Int) := new(big.Int) .SetInt64(1) : for { if , := io.ReadFull(, ); != nil { return } [len()-1] |= 1 [0] |= 0x80 .SetBytes() if !.ProbablyPrime(numMRTests) { continue } for := 0; < 4*; ++ { if , := io.ReadFull(, ); != nil { return } [len()-1] |= 1 [0] |= 0x80 .SetBytes() .Mod(, ) .Sub(, ) .Sub(, ) if .BitLen() < { continue } if !.ProbablyPrime(numMRTests) { continue } .P = .Q = break } } := new(big.Int) .SetInt64(2) := new(big.Int) := new(big.Int).Sub(, ) := new(big.Int).Div(, ) for { .Exp(, , ) if .Cmp() == 0 { .Add(, ) continue } .G = return nil } } // GenerateKey generates a public&private key pair. The Parameters of the // [PrivateKey] must already be valid (see [GenerateParameters]). func ( *PrivateKey, io.Reader) error { if .P == nil || .Q == nil || .G == nil { return errors.New("crypto/dsa: parameters not set up before generating key") } := new(big.Int) := make([]byte, .Q.BitLen()/8) for { , := io.ReadFull(, ) if != nil { return } .SetBytes() if .Sign() != 0 && .Cmp(.Q) < 0 { break } } .X = .Y = new(big.Int) .Y.Exp(.G, , .P) return nil } // fermatInverse calculates the inverse of k in GF(P) using Fermat's method. // This has better constant-time properties than Euclid's method (implemented // in math/big.Int.ModInverse) although math/big itself isn't strictly // constant-time so it's not perfect. func fermatInverse(, *big.Int) *big.Int { := big.NewInt(2) := new(big.Int).Sub(, ) return new(big.Int).Exp(, , ) } // Sign signs an arbitrary length hash (which should be the result of hashing a // larger message) using the private key, priv. It returns the signature as a // pair of integers. The security of the private key depends on the entropy of // rand. // // Note that FIPS 186-3 section 4.6 specifies that the hash should be truncated // to the byte-length of the subgroup. This function does not perform that // truncation itself. // // Be aware that calling Sign with an attacker-controlled [PrivateKey] may // require an arbitrary amount of CPU. func ( io.Reader, *PrivateKey, []byte) (, *big.Int, error) { randutil.MaybeReadByte() // FIPS 186-3, section 4.6 := .Q.BitLen() if .Q.Sign() <= 0 || .P.Sign() <= 0 || .G.Sign() <= 0 || .X.Sign() <= 0 || %8 != 0 { = ErrInvalidPublicKey return } >>= 3 var int for = 10; > 0; -- { := new(big.Int) := make([]byte, ) for { _, = io.ReadFull(, ) if != nil { return } .SetBytes() // priv.Q must be >= 128 because the test above // requires it to be > 0 and that // ceil(log_2(Q)) mod 8 = 0 // Thus this loop will quickly terminate. if .Sign() > 0 && .Cmp(.Q) < 0 { break } } := fermatInverse(, .Q) = new(big.Int).Exp(.G, , .P) .Mod(, .Q) if .Sign() == 0 { continue } := .SetBytes() = new(big.Int).Mul(.X, ) .Add(, ) .Mod(, .Q) .Mul(, ) .Mod(, .Q) if .Sign() != 0 { break } } // Only degenerate private keys will require more than a handful of // attempts. if == 0 { return nil, nil, ErrInvalidPublicKey } return } // Verify verifies the signature in r, s of hash using the public key, pub. It // reports whether the signature is valid. // // Note that FIPS 186-3 section 4.6 specifies that the hash should be truncated // to the byte-length of the subgroup. This function does not perform that // truncation itself. func ( *PublicKey, []byte, , *big.Int) bool { // FIPS 186-3, section 4.7 if .P.Sign() == 0 { return false } if .Sign() < 1 || .Cmp(.Q) >= 0 { return false } if .Sign() < 1 || .Cmp(.Q) >= 0 { return false } := new(big.Int).ModInverse(, .Q) if == nil { return false } := .Q.BitLen() if %8 != 0 { return false } := new(big.Int).SetBytes() := new(big.Int).Mul(, ) .Mod(, .Q) := .Mul(, ) .Mod(, .Q) := .Exp(.G, , .P) .Exp(.Y, , .P) .Mul(, ) .Mod(, .P) .Mod(, .Q) return .Cmp() == 0 }