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

View as plain text