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