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 //
   9 // Deprecated: DSA is a legacy algorithm, and modern alternatives such as
  10 // Ed25519 (implemented by package crypto/ed25519) should be used instead. Keys
  11 // with 1024-bit moduli (L1024N160 parameters) are cryptographically weak, while
  12 // bigger keys are not widely supported. Note that FIPS 186-5 no longer approves
  13 // DSA for signature generation.
  14 package dsa
  15
  16 import (
  17         "errors"
  18         "io"
  19         "math/big"
  20
  21         "crypto/internal/randutil"
  22 )
  23
  24 // Parameters represents the domain parameters for a key. These parameters can
  25 // be shared across many keys. The bit length of Q must be a multiple of 8.
  26 type Parameters struct {
  27         P, Q, G *big.Int
  28 }
  29
  30 // PublicKey represents a DSA public key.
  31 type PublicKey struct {
  32         Parameters
  33         Y *big.Int
  34 }
  35
  36 // PrivateKey represents a DSA private key.
  37 type PrivateKey struct {
  38         PublicKey
  39         X *big.Int
  40 }
  41
  42 // ErrInvalidPublicKey results when a public key is not usable by this code.
  43 // FIPS is quite strict about the format of DSA keys, but other code may be
  44 // less so. Thus, when using keys which may have been generated by other code,
  45 // this error must be handled.
  46 var ErrInvalidPublicKey = errors.New("crypto/dsa: invalid public key")
  47
  48 // ParameterSizes is an enumeration of the acceptable bit lengths of the primes
  49 // in a set of DSA parameters. See FIPS 186-3, section 4.2.
  50 type ParameterSizes int
  51
  52 const (
  53         L1024N160 ParameterSizes = iota
  54         L2048N224
  55         L2048N256
  56         L3072N256
  57 )
  58
  59 // numMRTests is the number of Miller-Rabin primality tests that we perform. We
  60 // pick the largest recommended number from table C.1 of FIPS 186-3.
  61 const numMRTests = 64
  62
  63 // GenerateParameters puts a random, valid set of DSA parameters into params.
  64 // This function can take many seconds, even on fast machines.
  65 func GenerateParameters(params *Parameters, rand io.Reader, sizes ParameterSizes) error {
  66         // This function doesn't follow FIPS 186-3 exactly in that it doesn't
  67         // use a verification seed to generate the primes. The verification
  68         // seed doesn't appear to be exported or used by other code and
  69         // omitting it makes the code cleaner.
  70
  71         var L, N int
  72         switch sizes {
  73         case L1024N160:
  74                 L = 1024
  75                 N = 160
  76         case L2048N224:
  77                 L = 2048
  78                 N = 224
  79         case L2048N256:
  80                 L = 2048
  81                 N = 256
  82         case L3072N256:
  83                 L = 3072
  84                 N = 256
  85         default:
  86                 return errors.New("crypto/dsa: invalid ParameterSizes")
  87         }
  88
  89         qBytes := make([]byte, N/8)
  90         pBytes := make([]byte, L/8)
  91
  92         q := new(big.Int)
  93         p := new(big.Int)
  94         rem := new(big.Int)
  95         one := new(big.Int)
  96         one.SetInt64(1)
  97
  98 GeneratePrimes:
  99         for {
 100                 if _, err := io.ReadFull(rand, qBytes); err != nil {
 101                         return err
 102                 }
 103
 104                 qBytes[len(qBytes)-1] |= 1
 105                 qBytes[0] |= 0x80
 106                 q.SetBytes(qBytes)
 107
 108                 if !q.ProbablyPrime(numMRTests) {
 109                         continue
 110                 }
 111
 112                 for i := 0; i < 4*L; i++ {
 113                         if _, err := io.ReadFull(rand, pBytes); err != nil {
 114                                 return err
 115                         }
 116
 117                         pBytes[len(pBytes)-1] |= 1
 118                         pBytes[0] |= 0x80
 119
 120                         p.SetBytes(pBytes)
 121                         rem.Mod(p, q)
 122                         rem.Sub(rem, one)
 123                         p.Sub(p, rem)
 124                         if p.BitLen() < L {
 125                                 continue
 126                         }
 127
 128                         if !p.ProbablyPrime(numMRTests) {
 129                                 continue
 130                         }
 131
 132                         params.P = p
 133                         params.Q = q
 134                         break GeneratePrimes
 135                 }
 136         }
 137
 138         h := new(big.Int)
 139         h.SetInt64(2)
 140         g := new(big.Int)
 141
 142         pm1 := new(big.Int).Sub(p, one)
 143         e := new(big.Int).Div(pm1, q)
 144
 145         for {
 146                 g.Exp(h, e, p)
 147                 if g.Cmp(one) == 0 {
 148                         h.Add(h, one)
 149                         continue
 150                 }
 151
 152                 params.G = g
 153                 return nil
 154         }
 155 }
 156
 157 // GenerateKey generates a public&private key pair. The Parameters of the
 158 // PrivateKey must already be valid (see GenerateParameters).
 159 func GenerateKey(priv *PrivateKey, rand io.Reader) error {
 160         if priv.P == nil || priv.Q == nil || priv.G == nil {
 161                 return errors.New("crypto/dsa: parameters not set up before generating key")
 162         }
 163
 164         x := new(big.Int)
 165         xBytes := make([]byte, priv.Q.BitLen()/8)
 166
 167         for {
 168                 _, err := io.ReadFull(rand, xBytes)
 169                 if err != nil {
 170                         return err
 171                 }
 172                 x.SetBytes(xBytes)
 173                 if x.Sign() != 0 && x.Cmp(priv.Q) < 0 {
 174                         break
 175                 }
 176         }
 177
 178         priv.X = x
 179         priv.Y = new(big.Int)
 180         priv.Y.Exp(priv.G, x, priv.P)
 181         return nil
 182 }
 183
 184 // fermatInverse calculates the inverse of k in GF(P) using Fermat's method.
 185 // This has better constant-time properties than Euclid's method (implemented
 186 // in math/big.Int.ModInverse) although math/big itself isn't strictly
 187 // constant-time so it's not perfect.
 188 func fermatInverse(k, P *big.Int) *big.Int {
 189         two := big.NewInt(2)
 190         pMinus2 := new(big.Int).Sub(P, two)
 191         return new(big.Int).Exp(k, pMinus2, P)
 192 }
 193
 194 // Sign signs an arbitrary length hash (which should be the result of hashing a
 195 // larger message) using the private key, priv. It returns the signature as a
 196 // pair of integers. The security of the private key depends on the entropy of
 197 // rand.
 198 //
 199 // Note that FIPS 186-3 section 4.6 specifies that the hash should be truncated
 200 // to the byte-length of the subgroup. This function does not perform that
 201 // truncation itself.
 202 //
 203 // Be aware that calling Sign with an attacker-controlled PrivateKey may
 204 // require an arbitrary amount of CPU.
 205 func Sign(rand io.Reader, priv *PrivateKey, hash []byte) (r, s *big.Int, err error) {
 206         randutil.MaybeReadByte(rand)
 207
 208         // FIPS 186-3, section 4.6
 209
 210         n := priv.Q.BitLen()
 211         if priv.Q.Sign() <= 0 || priv.P.Sign() <= 0 || priv.G.Sign() <= 0 || priv.X.Sign() <= 0 || n%8 != 0 {
 212                 err = ErrInvalidPublicKey
 213                 return
 214         }
 215         n >>= 3
 216
 217         var attempts int
 218         for attempts = 10; attempts > 0; attempts-- {
 219                 k := new(big.Int)
 220                 buf := make([]byte, n)
 221                 for {
 222                         _, err = io.ReadFull(rand, buf)
 223                         if err != nil {
 224                                 return
 225                         }
 226                         k.SetBytes(buf)
 227                         // priv.Q must be >= 128 because the test above
 228                         // requires it to be > 0 and that
 229                         //    ceil(log_2(Q)) mod 8 = 0
 230                         // Thus this loop will quickly terminate.
 231                         if k.Sign() > 0 && k.Cmp(priv.Q) < 0 {
 232                                 break
 233                         }
 234                 }
 235
 236                 kInv := fermatInverse(k, priv.Q)
 237
 238                 r = new(big.Int).Exp(priv.G, k, priv.P)
 239                 r.Mod(r, priv.Q)
 240
 241                 if r.Sign() == 0 {
 242                         continue
 243                 }
 244
 245                 z := k.SetBytes(hash)
 246
 247                 s = new(big.Int).Mul(priv.X, r)
 248                 s.Add(s, z)
 249                 s.Mod(s, priv.Q)
 250                 s.Mul(s, kInv)
 251                 s.Mod(s, priv.Q)
 252
 253                 if s.Sign() != 0 {
 254                         break
 255                 }
 256         }
 257
 258         // Only degenerate private keys will require more than a handful of
 259         // attempts.
 260         if attempts == 0 {
 261                 return nil, nil, ErrInvalidPublicKey
 262         }
 263
 264         return
 265 }
 266
 267 // Verify verifies the signature in r, s of hash using the public key, pub. It
 268 // reports whether the signature is valid.
 269 //
 270 // Note that FIPS 186-3 section 4.6 specifies that the hash should be truncated
 271 // to the byte-length of the subgroup. This function does not perform that
 272 // truncation itself.
 273 func Verify(pub *PublicKey, hash []byte, r, s *big.Int) bool {
 274         // FIPS 186-3, section 4.7
 275
 276         if pub.P.Sign() == 0 {
 277                 return false
 278         }
 279
 280         if r.Sign() < 1 || r.Cmp(pub.Q) >= 0 {
 281                 return false
 282         }
 283         if s.Sign() < 1 || s.Cmp(pub.Q) >= 0 {
 284                 return false
 285         }
 286
 287         w := new(big.Int).ModInverse(s, pub.Q)
 288         if w == nil {
 289                 return false
 290         }
 291
 292         n := pub.Q.BitLen()
 293         if n%8 != 0 {
 294                 return false
 295         }
 296         z := new(big.Int).SetBytes(hash)
 297
 298         u1 := new(big.Int).Mul(z, w)
 299         u1.Mod(u1, pub.Q)
 300         u2 := w.Mul(r, w)
 301         u2.Mod(u2, pub.Q)
 302         v := u1.Exp(pub.G, u1, pub.P)
 303         u2.Exp(pub.Y, u2, pub.P)
 304         v.Mul(v, u2)
 305         v.Mod(v, pub.P)
 306         v.Mod(v, pub.Q)
 307
 308         return v.Cmp(r) == 0
 309 }