Subversion Repositories openrisc

// 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
package dsa

import (
        "errors"
        "io"
        "math/big"
)

// 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
}

type invalidPublicKeyError int

func (invalidPublicKeyError) Error() string {
        return "crypto/dsa: invalid public key"
}

// 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 error = invalidPublicKeyError(0)

// ParameterSizes is a 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 takes many seconds, even on fast machines.
func GenerateParameters(params *Parameters, rand io.Reader, sizes ParameterSizes) (err 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 {
                _, err = io.ReadFull(rand, qBytes)
                if err != nil {
                        return
                }

                qBytes[len(qBytes)-1] |= 1
                qBytes[0] |= 0x80
                q.SetBytes(qBytes)

                if !q.ProbablyPrime(numMRTests) {
                        continue
                }

                for i := 0; i < 4*L; i++ {
                        _, err = io.ReadFull(rand, pBytes)
                        if err != nil {
                                return
                        }

                        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
        }

        panic("unreachable")
}

// 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
}

// 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.
func Sign(rand io.Reader, priv *PrivateKey, hash []byte) (r, s *big.Int, err error) {
        // FIPS 186-3, section 4.6

        n := priv.Q.BitLen()
        if n&7 != 0 {
                err = ErrInvalidPublicKey
                return
        }
        n >>= 3

        for {
                k := new(big.Int)
                buf := make([]byte, n)
                for {
                        _, err = io.ReadFull(rand, buf)
                        if err != nil {
                                return
                        }
                        k.SetBytes(buf)
                        if k.Sign() > 0 && k.Cmp(priv.Q) < 0 {
                                break
                        }
                }

                kInv := new(big.Int).ModInverse(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
                }
        }

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