dsa.go

Documentation: crypto/dsa

		 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