...
Run Format

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

View as plain text