dsa.go

     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/rand"
    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.Enforced() {
    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 := make([]byte, N/8)
    95  	pBytes := make([]byte, L/8)
    96  
    97  	q := new(big.Int)
    98  	p := new(big.Int)
    99  	rem := new(big.Int)
   100  	one := new(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 := new(big.Int)
   144  	h.SetInt64(2)
   145  	g := new(big.Int)
   146  
   147  	pm1 := new(big.Int).Sub(p, one)
   148  	e := new(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.Enforced() {
   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 := new(big.Int)
   174  	xBytes := make([]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 = new(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 := new(big.Int).Sub(P, two)
   200  	return new(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  // Since Go 1.26, a secure source of random bytes is always used, and the Reader is
   213  // ignored unless GODEBUG=cryptocustomrand=1 is set. This setting will be removed
   214  // in a future Go release. Instead, use [testing/cryptotest.SetGlobalRandom].
   215  //
   216  // Be aware that calling Sign with an attacker-controlled [PrivateKey] may
   217  // require an arbitrary amount of CPU.
   218  func Sign(random io.Reader, priv *PrivateKey, hash []byte) (r, s *big.Int, err error) {
   219  	if fips140only.Enforced() {
   220  		return nil, nil, errors.New("crypto/dsa: use of DSA is not allowed in FIPS 140-only mode")
   221  	}
   222  
   223  	random = rand.CustomReader(random)
   224  
   225  	// FIPS 186-3, section 4.6
   226  
   227  	n := priv.Q.BitLen()
   228  	if priv.Q.Sign() <= 0 || priv.P.Sign() <= 0 || priv.G.Sign() <= 0 || priv.X.Sign() <= 0 || n%8 != 0 {
   229  		err = ErrInvalidPublicKey
   230  		return
   231  	}
   232  	n >>= 3
   233  
   234  	var attempts int
   235  	for attempts = 10; attempts > 0; attempts-- {
   236  		k := new(big.Int)
   237  		buf := make([]byte, n)
   238  		for {
   239  			_, err = io.ReadFull(random, buf)
   240  			if err != nil {
   241  				return
   242  			}
   243  			k.SetBytes(buf)
   244  			// priv.Q must be >= 128 because the test above
   245  			// requires it to be > 0 and that
   246  			//    ceil(log_2(Q)) mod 8 = 0
   247  			// Thus this loop will quickly terminate.
   248  			if k.Sign() > 0 && k.Cmp(priv.Q) < 0 {
   249  				break
   250  			}
   251  		}
   252  
   253  		kInv := fermatInverse(k, priv.Q)
   254  
   255  		r = new(big.Int).Exp(priv.G, k, priv.P)
   256  		r.Mod(r, priv.Q)
   257  
   258  		if r.Sign() == 0 {
   259  			continue
   260  		}
   261  
   262  		z := k.SetBytes(hash)
   263  
   264  		s = new(big.Int).Mul(priv.X, r)
   265  		s.Add(s, z)
   266  		s.Mod(s, priv.Q)
   267  		s.Mul(s, kInv)
   268  		s.Mod(s, priv.Q)
   269  
   270  		if s.Sign() != 0 {
   271  			break
   272  		}
   273  	}
   274  
   275  	// Only degenerate private keys will require more than a handful of
   276  	// attempts.
   277  	if attempts == 0 {
   278  		return nil, nil, ErrInvalidPublicKey
   279  	}
   280  
   281  	return
   282  }
   283  
   284  // Verify verifies the signature in r, s of hash using the public key, pub. It
   285  // reports whether the signature is valid.
   286  //
   287  // Note that FIPS 186-3 section 4.6 specifies that the hash should be truncated
   288  // to the byte-length of the subgroup. This function does not perform that
   289  // truncation itself.
   290  func Verify(pub *PublicKey, hash []byte, r, s *big.Int) bool {
   291  	if fips140only.Enforced() {
   292  		panic("crypto/dsa: use of DSA is not allowed in FIPS 140-only mode")
   293  	}
   294  
   295  	// FIPS 186-3, section 4.7
   296  
   297  	if pub.P.Sign() == 0 {
   298  		return false
   299  	}
   300  
   301  	if r.Sign() < 1 || r.Cmp(pub.Q) >= 0 {
   302  		return false
   303  	}
   304  	if s.Sign() < 1 || s.Cmp(pub.Q) >= 0 {
   305  		return false
   306  	}
   307  
   308  	w := new(big.Int).ModInverse(s, pub.Q)
   309  	if w == nil {
   310  		return false
   311  	}
   312  
   313  	n := pub.Q.BitLen()
   314  	if n%8 != 0 {
   315  		return false
   316  	}
   317  	z := new(big.Int).SetBytes(hash)
   318  
   319  	u1 := new(big.Int).Mul(z, w)
   320  	u1.Mod(u1, pub.Q)
   321  	u2 := w.Mul(r, w)
   322  	u2.Mod(u2, pub.Q)
   323  	v := u1.Exp(pub.G, u1, pub.P)
   324  	u2.Exp(pub.Y, u2, pub.P)
   325  	v.Mul(v, u2)
   326  	v.Mod(v, pub.P)
   327  	v.Mod(v, pub.Q)
   328  
   329  	return v.Cmp(r) == 0
   330  }
   331
View as plain text