Source file src/pkg/crypto/dsa/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	package dsa
     7	
     8	import (
     9		"errors"
    10		"io"
    11		"math/big"
    12	)
    13	
    14	// Parameters represents the domain parameters for a key. These parameters can
    15	// be shared across many keys. The bit length of Q must be a multiple of 8.
    16	type Parameters struct {
    17		P, Q, G *big.Int
    18	}
    19	
    20	// PublicKey represents a DSA public key.
    21	type PublicKey struct {
    22		Parameters
    23		Y *big.Int
    24	}
    25	
    26	// PrivateKey represents a DSA private key.
    27	type PrivateKey struct {
    28		PublicKey
    29		X *big.Int
    30	}
    31	
    32	// ErrInvalidPublicKey results when a public key is not usable by this code.
    33	// FIPS is quite strict about the format of DSA keys, but other code may be
    34	// less so. Thus, when using keys which may have been generated by other code,
    35	// this error must be handled.
    36	var ErrInvalidPublicKey = errors.New("crypto/dsa: invalid public key")
    37	
    38	// ParameterSizes is a enumeration of the acceptable bit lengths of the primes
    39	// in a set of DSA parameters. See FIPS 186-3, section 4.2.
    40	type ParameterSizes int
    41	
    42	const (
    43		L1024N160 ParameterSizes = iota
    44		L2048N224
    45		L2048N256
    46		L3072N256
    47	)
    48	
    49	// numMRTests is the number of Miller-Rabin primality tests that we perform. We
    50	// pick the largest recommended number from table C.1 of FIPS 186-3.
    51	const numMRTests = 64
    52	
    53	// GenerateParameters puts a random, valid set of DSA parameters into params.
    54	// This function takes many seconds, even on fast machines.
    55	func GenerateParameters(params *Parameters, rand io.Reader, sizes ParameterSizes) (err error) {
    56		// This function doesn't follow FIPS 186-3 exactly in that it doesn't
    57		// use a verification seed to generate the primes. The verification
    58		// seed doesn't appear to be exported or used by other code and
    59		// omitting it makes the code cleaner.
    60	
    61		var L, N int
    62		switch sizes {
    63		case L1024N160:
    64			L = 1024
    65			N = 160
    66		case L2048N224:
    67			L = 2048
    68			N = 224
    69		case L2048N256:
    70			L = 2048
    71			N = 256
    72		case L3072N256:
    73			L = 3072
    74			N = 256
    75		default:
    76			return errors.New("crypto/dsa: invalid ParameterSizes")
    77		}
    78	
    79		qBytes := make([]byte, N/8)
    80		pBytes := make([]byte, L/8)
    81	
    82		q := new(big.Int)
    83		p := new(big.Int)
    84		rem := new(big.Int)
    85		one := new(big.Int)
    86		one.SetInt64(1)
    87	
    88	GeneratePrimes:
    89		for {
    90			_, err = io.ReadFull(rand, qBytes)
    91			if err != nil {
    92				return
    93			}
    94	
    95			qBytes[len(qBytes)-1] |= 1
    96			qBytes[0] |= 0x80
    97			q.SetBytes(qBytes)
    98	
    99			if !q.ProbablyPrime(numMRTests) {
   100				continue
   101			}
   102	
   103			for i := 0; i < 4*L; i++ {
   104				_, err = io.ReadFull(rand, pBytes)
   105				if err != nil {
   106					return
   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
   146		}
   147	
   148		panic("unreachable")
   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	// Sign signs an arbitrary length hash (which should be the result of hashing a
   179	// larger message) using the private key, priv. It returns the signature as a
   180	// pair of integers. The security of the private key depends on the entropy of
   181	// rand.
   182	//
   183	// Note that FIPS 186-3 section 4.6 specifies that the hash should be truncated
   184	// to the byte-length of the subgroup. This function does not perform that
   185	// truncation itself.
   186	func Sign(rand io.Reader, priv *PrivateKey, hash []byte) (r, s *big.Int, err error) {
   187		// FIPS 186-3, section 4.6
   188	
   189		n := priv.Q.BitLen()
   190		if n&7 != 0 {
   191			err = ErrInvalidPublicKey
   192			return
   193		}
   194		n >>= 3
   195	
   196		for {
   197			k := new(big.Int)
   198			buf := make([]byte, n)
   199			for {
   200				_, err = io.ReadFull(rand, buf)
   201				if err != nil {
   202					return
   203				}
   204				k.SetBytes(buf)
   205				if k.Sign() > 0 && k.Cmp(priv.Q) < 0 {
   206					break
   207				}
   208			}
   209	
   210			kInv := new(big.Int).ModInverse(k, priv.Q)
   211	
   212			r = new(big.Int).Exp(priv.G, k, priv.P)
   213			r.Mod(r, priv.Q)
   214	
   215			if r.Sign() == 0 {
   216				continue
   217			}
   218	
   219			z := k.SetBytes(hash)
   220	
   221			s = new(big.Int).Mul(priv.X, r)
   222			s.Add(s, z)
   223			s.Mod(s, priv.Q)
   224			s.Mul(s, kInv)
   225			s.Mod(s, priv.Q)
   226	
   227			if s.Sign() != 0 {
   228				break
   229			}
   230		}
   231	
   232		return
   233	}
   234	
   235	// Verify verifies the signature in r, s of hash using the public key, pub. It
   236	// reports whether the signature is valid.
   237	//
   238	// Note that FIPS 186-3 section 4.6 specifies that the hash should be truncated
   239	// to the byte-length of the subgroup. This function does not perform that
   240	// truncation itself.
   241	func Verify(pub *PublicKey, hash []byte, r, s *big.Int) bool {
   242		// FIPS 186-3, section 4.7
   243	
   244		if r.Sign() < 1 || r.Cmp(pub.Q) >= 0 {
   245			return false
   246		}
   247		if s.Sign() < 1 || s.Cmp(pub.Q) >= 0 {
   248			return false
   249		}
   250	
   251		w := new(big.Int).ModInverse(s, pub.Q)
   252	
   253		n := pub.Q.BitLen()
   254		if n&7 != 0 {
   255			return false
   256		}
   257		z := new(big.Int).SetBytes(hash)
   258	
   259		u1 := new(big.Int).Mul(z, w)
   260		u1.Mod(u1, pub.Q)
   261		u2 := w.Mul(r, w)
   262		u2.Mod(u2, pub.Q)
   263		v := u1.Exp(pub.G, u1, pub.P)
   264		u2.Exp(pub.Y, u2, pub.P)
   265		v.Mul(v, u2)
   266		v.Mod(v, pub.P)
   267		v.Mod(v, pub.Q)
   268	
   269		return v.Cmp(r) == 0
   270	}