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