Source file src/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	//
     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		if w == nil {
   283			return false
   284		}
   285	
   286		n := pub.Q.BitLen()
   287		if n&7 != 0 {
   288			return false
   289		}
   290		z := new(big.Int).SetBytes(hash)
   291	
   292		u1 := new(big.Int).Mul(z, w)
   293		u1.Mod(u1, pub.Q)
   294		u2 := w.Mul(r, w)
   295		u2.Mod(u2, pub.Q)
   296		v := u1.Exp(pub.G, u1, pub.P)
   297		u2.Exp(pub.Y, u2, pub.P)
   298		v.Mul(v, u2)
   299		v.Mod(v, pub.P)
   300		v.Mod(v, pub.Q)
   301	
   302		return v.Cmp(r) == 0
   303	}
   304	

View as plain text