libgo/go/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
 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 func Sign(rand io.Reader, priv *PrivateKey, hash []byte) (r, s *big.Int, err error) {
 195         // FIPS 186-3, section 4.6
 196
 197         n := priv.Q.BitLen()
 198         if n&7 != 0 {
 199                 err = ErrInvalidPublicKey
 200                 return
 201         }
 202         n >>= 3
 203
 204         for {
 205                 k := new(big.Int)
 206                 buf := make([]byte, n)
 207                 for {
 208                         _, err = io.ReadFull(rand, buf)
 209                         if err != nil {
 210                                 return
 211                         }
 212                         k.SetBytes(buf)
 213                         if k.Sign() > 0 && k.Cmp(priv.Q) < 0 {
 214                                 break
 215                         }
 216                 }
 217
 218                 kInv := fermatInverse(k, priv.Q)
 219
 220                 r = new(big.Int).Exp(priv.G, k, priv.P)
 221                 r.Mod(r, priv.Q)
 222
 223                 if r.Sign() == 0 {
 224                         continue
 225                 }
 226
 227                 z := k.SetBytes(hash)
 228
 229                 s = new(big.Int).Mul(priv.X, r)
 230                 s.Add(s, z)
 231                 s.Mod(s, priv.Q)
 232                 s.Mul(s, kInv)
 233                 s.Mod(s, priv.Q)
 234
 235                 if s.Sign() != 0 {
 236                         break
 237                 }
 238         }
 239
 240         return
 241 }
 242
 243 // Verify verifies the signature in r, s of hash using the public key, pub. It
 244 // reports whether the signature is valid.
 245 //
 246 // Note that FIPS 186-3 section 4.6 specifies that the hash should be truncated
 247 // to the byte-length of the subgroup. This function does not perform that
 248 // truncation itself.
 249 func Verify(pub *PublicKey, hash []byte, r, s *big.Int) bool {
 250         // FIPS 186-3, section 4.7
 251
 252         if r.Sign() < 1 || r.Cmp(pub.Q) >= 0 {
 253                 return false
 254         }
 255         if s.Sign() < 1 || s.Cmp(pub.Q) >= 0 {
 256                 return false
 257         }
 258
 259         w := new(big.Int).ModInverse(s, pub.Q)
 260
 261         n := pub.Q.BitLen()
 262         if n&7 != 0 {
 263                 return false
 264         }
 265         z := new(big.Int).SetBytes(hash)
 266
 267         u1 := new(big.Int).Mul(z, w)
 268         u1.Mod(u1, pub.Q)
 269         u2 := w.Mul(r, w)
 270         u2.Mod(u2, pub.Q)
 271         v := u1.Exp(pub.G, u1, pub.P)
 272         u2.Exp(pub.Y, u2, pub.P)
 273         v.Mul(v, u2)
 274         v.Mod(v, pub.P)
 275         v.Mod(v, pub.Q)
 276
 277         return v.Cmp(r) == 0
 278 }