...
Run Format

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	
    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 a 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