blob: 575314b1b468908c3bb197ac656e368cb1f5e701 [file] [log] [blame]
// Copyright 2011 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
// Package dsa implements the Digital Signature Algorithm, as defined in FIPS 186-3.
//
// The DSA operations in this package are not implemented using constant-time algorithms.
package dsa
import (
"errors"
"io"
"math/big"
"crypto/internal/randutil"
)
// Parameters represents the domain parameters for a key. These parameters can
// be shared across many keys. The bit length of Q must be a multiple of 8.
type Parameters struct {
P, Q, G *big.Int
}
// PublicKey represents a DSA public key.
type PublicKey struct {
Parameters
Y *big.Int
}
// PrivateKey represents a DSA private key.
type PrivateKey struct {
PublicKey
X *big.Int
}
// ErrInvalidPublicKey results when a public key is not usable by this code.
// FIPS is quite strict about the format of DSA keys, but other code may be
// less so. Thus, when using keys which may have been generated by other code,
// this error must be handled.
var ErrInvalidPublicKey = errors.New("crypto/dsa: invalid public key")
// ParameterSizes is an enumeration of the acceptable bit lengths of the primes
// in a set of DSA parameters. See FIPS 186-3, section 4.2.
type ParameterSizes int
const (
L1024N160 ParameterSizes = iota
L2048N224
L2048N256
L3072N256
)
// numMRTests is the number of Miller-Rabin primality tests that we perform. We
// pick the largest recommended number from table C.1 of FIPS 186-3.
const numMRTests = 64
// GenerateParameters puts a random, valid set of DSA parameters into params.
// This function can take many seconds, even on fast machines.
func GenerateParameters(params *Parameters, rand io.Reader, sizes ParameterSizes) error {
// This function doesn't follow FIPS 186-3 exactly in that it doesn't
// use a verification seed to generate the primes. The verification
// seed doesn't appear to be exported or used by other code and
// omitting it makes the code cleaner.
var L, N int
switch sizes {
case L1024N160:
L = 1024
N = 160
case L2048N224:
L = 2048
N = 224
case L2048N256:
L = 2048
N = 256
case L3072N256:
L = 3072
N = 256
default:
return errors.New("crypto/dsa: invalid ParameterSizes")
}
qBytes := make([]byte, N/8)
pBytes := make([]byte, L/8)
q := new(big.Int)
p := new(big.Int)
rem := new(big.Int)
one := new(big.Int)
one.SetInt64(1)
GeneratePrimes:
for {
if _, err := io.ReadFull(rand, qBytes); err != nil {
return err
}
qBytes[len(qBytes)-1] |= 1
qBytes[0] |= 0x80
q.SetBytes(qBytes)
if !q.ProbablyPrime(numMRTests) {
continue
}
for i := 0; i < 4*L; i++ {
if _, err := io.ReadFull(rand, pBytes); err != nil {
return err
}
pBytes[len(pBytes)-1] |= 1
pBytes[0] |= 0x80
p.SetBytes(pBytes)
rem.Mod(p, q)
rem.Sub(rem, one)
p.Sub(p, rem)
if p.BitLen() < L {
continue
}
if !p.ProbablyPrime(numMRTests) {
continue
}
params.P = p
params.Q = q
break GeneratePrimes
}
}
h := new(big.Int)
h.SetInt64(2)
g := new(big.Int)
pm1 := new(big.Int).Sub(p, one)
e := new(big.Int).Div(pm1, q)
for {
g.Exp(h, e, p)
if g.Cmp(one) == 0 {
h.Add(h, one)
continue
}
params.G = g
return nil
}
}
// GenerateKey generates a public&private key pair. The Parameters of the
// PrivateKey must already be valid (see GenerateParameters).
func GenerateKey(priv *PrivateKey, rand io.Reader) error {
if priv.P == nil || priv.Q == nil || priv.G == nil {
return errors.New("crypto/dsa: parameters not set up before generating key")
}
x := new(big.Int)
xBytes := make([]byte, priv.Q.BitLen()/8)
for {
_, err := io.ReadFull(rand, xBytes)
if err != nil {
return err
}
x.SetBytes(xBytes)
if x.Sign() != 0 && x.Cmp(priv.Q) < 0 {
break
}
}
priv.X = x
priv.Y = new(big.Int)
priv.Y.Exp(priv.G, x, priv.P)
return nil
}
// fermatInverse calculates the inverse of k in GF(P) using Fermat's method.
// This has better constant-time properties than Euclid's method (implemented
// in math/big.Int.ModInverse) although math/big itself isn't strictly
// constant-time so it's not perfect.
func fermatInverse(k, P *big.Int) *big.Int {
two := big.NewInt(2)
pMinus2 := new(big.Int).Sub(P, two)
return new(big.Int).Exp(k, pMinus2, P)
}
// Sign signs an arbitrary length hash (which should be the result of hashing a
// larger message) using the private key, priv. It returns the signature as a
// pair of integers. The security of the private key depends on the entropy of
// rand.
//
// Note that FIPS 186-3 section 4.6 specifies that the hash should be truncated
// to the byte-length of the subgroup. This function does not perform that
// truncation itself.
//
// Be aware that calling Sign with an attacker-controlled PrivateKey may
// require an arbitrary amount of CPU.
func Sign(rand io.Reader, priv *PrivateKey, hash []byte) (r, s *big.Int, err error) {
randutil.MaybeReadByte(rand)
// FIPS 186-3, section 4.6
n := priv.Q.BitLen()
if priv.Q.Sign() <= 0 || priv.P.Sign() <= 0 || priv.G.Sign() <= 0 || priv.X.Sign() <= 0 || n&7 != 0 {
err = ErrInvalidPublicKey
return
}
n >>= 3
var attempts int
for attempts = 10; attempts > 0; attempts-- {
k := new(big.Int)
buf := make([]byte, n)
for {
_, err = io.ReadFull(rand, buf)
if err != nil {
return
}
k.SetBytes(buf)
// priv.Q must be >= 128 because the test above
// requires it to be > 0 and that
// ceil(log_2(Q)) mod 8 = 0
// Thus this loop will quickly terminate.
if k.Sign() > 0 && k.Cmp(priv.Q) < 0 {
break
}
}
kInv := fermatInverse(k, priv.Q)
r = new(big.Int).Exp(priv.G, k, priv.P)
r.Mod(r, priv.Q)
if r.Sign() == 0 {
continue
}
z := k.SetBytes(hash)
s = new(big.Int).Mul(priv.X, r)
s.Add(s, z)
s.Mod(s, priv.Q)
s.Mul(s, kInv)
s.Mod(s, priv.Q)
if s.Sign() != 0 {
break
}
}
// Only degenerate private keys will require more than a handful of
// attempts.
if attempts == 0 {
return nil, nil, ErrInvalidPublicKey
}
return
}
// Verify verifies the signature in r, s of hash using the public key, pub. It
// reports whether the signature is valid.
//
// Note that FIPS 186-3 section 4.6 specifies that the hash should be truncated
// to the byte-length of the subgroup. This function does not perform that
// truncation itself.
func Verify(pub *PublicKey, hash []byte, r, s *big.Int) bool {
// FIPS 186-3, section 4.7
if pub.P.Sign() == 0 {
return false
}
if r.Sign() < 1 || r.Cmp(pub.Q) >= 0 {
return false
}
if s.Sign() < 1 || s.Cmp(pub.Q) >= 0 {
return false
}
w := new(big.Int).ModInverse(s, pub.Q)
n := pub.Q.BitLen()
if n&7 != 0 {
return false
}
z := new(big.Int).SetBytes(hash)
u1 := new(big.Int).Mul(z, w)
u1.Mod(u1, pub.Q)
u2 := w.Mul(r, w)
u2.Mod(u2, pub.Q)
v := u1.Exp(pub.G, u1, pub.P)
u2.Exp(pub.Y, u2, pub.P)
v.Mul(v, u2)
v.Mod(v, pub.P)
v.Mod(v, pub.Q)
return v.Cmp(r) == 0
}