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 ecdsa implements the Elliptic Curve Digital Signature Algorithm, as 6// defined in FIPS 186-3. 7// 8// This implementation derives the nonce from an AES-CTR CSPRNG keyed by 9// ChopMD(256, SHA2-512(priv.D || entropy || hash)). The CSPRNG key is IRO by 10// a result of Coron; the AES-CTR stream is IRO under standard assumptions. 11package ecdsa 12 13// References: 14// [NSA]: Suite B implementer's guide to FIPS 186-3, 15// http://www.nsa.gov/ia/_files/ecdsa.pdf 16// [SECG]: SECG, SEC1 17// http://www.secg.org/sec1-v2.pdf 18 19import ( 20 "crypto" 21 "crypto/aes" 22 "crypto/cipher" 23 "crypto/elliptic" 24 "crypto/sha512" 25 "encoding/asn1" 26 "errors" 27 "io" 28 "math/big" 29) 30 31// A invertible implements fast inverse mod Curve.Params().N 32type invertible interface { 33 // Inverse returns the inverse of k in GF(P) 34 Inverse(k *big.Int) *big.Int 35} 36 37// combinedMult implements fast multiplication S1*g + S2*p (g - generator, p - arbitrary point) 38type combinedMult interface { 39 CombinedMult(bigX, bigY *big.Int, baseScalar, scalar []byte) (x, y *big.Int) 40} 41 42const ( 43 aesIV = "IV for ECDSA CTR" 44) 45 46// PublicKey represents an ECDSA public key. 47type PublicKey struct { 48 elliptic.Curve 49 X, Y *big.Int 50} 51 52// PrivateKey represents a ECDSA private key. 53type PrivateKey struct { 54 PublicKey 55 D *big.Int 56} 57 58type ecdsaSignature struct { 59 R, S *big.Int 60} 61 62// Public returns the public key corresponding to priv. 63func (priv *PrivateKey) Public() crypto.PublicKey { 64 return &priv.PublicKey 65} 66 67// Sign signs msg with priv, reading randomness from rand. This method is 68// intended to support keys where the private part is kept in, for example, a 69// hardware module. Common uses should use the Sign function in this package 70// directly. 71func (priv *PrivateKey) Sign(rand io.Reader, msg []byte, opts crypto.SignerOpts) ([]byte, error) { 72 r, s, err := Sign(rand, priv, msg) 73 if err != nil { 74 return nil, err 75 } 76 77 return asn1.Marshal(ecdsaSignature{r, s}) 78} 79 80var one = new(big.Int).SetInt64(1) 81 82// randFieldElement returns a random element of the field underlying the given 83// curve using the procedure given in [NSA] A.2.1. 84func randFieldElement(c elliptic.Curve, rand io.Reader) (k *big.Int, err error) { 85 params := c.Params() 86 b := make([]byte, params.BitSize/8+8) 87 _, err = io.ReadFull(rand, b) 88 if err != nil { 89 return 90 } 91 92 k = new(big.Int).SetBytes(b) 93 n := new(big.Int).Sub(params.N, one) 94 k.Mod(k, n) 95 k.Add(k, one) 96 return 97} 98 99// GenerateKey generates a public and private key pair. 100func GenerateKey(c elliptic.Curve, rand io.Reader) (priv *PrivateKey, err error) { 101 k, err := randFieldElement(c, rand) 102 if err != nil { 103 return 104 } 105 106 priv = new(PrivateKey) 107 priv.PublicKey.Curve = c 108 priv.D = k 109 priv.PublicKey.X, priv.PublicKey.Y = c.ScalarBaseMult(k.Bytes()) 110 return 111} 112 113// hashToInt converts a hash value to an integer. There is some disagreement 114// about how this is done. [NSA] suggests that this is done in the obvious 115// manner, but [SECG] truncates the hash to the bit-length of the curve order 116// first. We follow [SECG] because that's what OpenSSL does. Additionally, 117// OpenSSL right shifts excess bits from the number if the hash is too large 118// and we mirror that too. 119func hashToInt(hash []byte, c elliptic.Curve) *big.Int { 120 orderBits := c.Params().N.BitLen() 121 orderBytes := (orderBits + 7) / 8 122 if len(hash) > orderBytes { 123 hash = hash[:orderBytes] 124 } 125 126 ret := new(big.Int).SetBytes(hash) 127 excess := len(hash)*8 - orderBits 128 if excess > 0 { 129 ret.Rsh(ret, uint(excess)) 130 } 131 return ret 132} 133 134// fermatInverse calculates the inverse of k in GF(P) using Fermat's method. 135// This has better constant-time properties than Euclid's method (implemented 136// in math/big.Int.ModInverse) although math/big itself isn't strictly 137// constant-time so it's not perfect. 138func fermatInverse(k, N *big.Int) *big.Int { 139 two := big.NewInt(2) 140 nMinus2 := new(big.Int).Sub(N, two) 141 return new(big.Int).Exp(k, nMinus2, N) 142} 143 144var errZeroParam = errors.New("zero parameter") 145 146// Sign signs an arbitrary length hash (which should be the result of hashing a 147// larger message) using the private key, priv. It returns the signature as a 148// pair of integers. The security of the private key depends on the entropy of 149// rand. 150func Sign(rand io.Reader, priv *PrivateKey, hash []byte) (r, s *big.Int, err error) { 151 // Get max(log2(q) / 2, 256) bits of entropy from rand. 152 entropylen := (priv.Curve.Params().BitSize + 7) / 16 153 if entropylen > 32 { 154 entropylen = 32 155 } 156 entropy := make([]byte, entropylen) 157 _, err = io.ReadFull(rand, entropy) 158 if err != nil { 159 return 160 } 161 162 // Initialize an SHA-512 hash context; digest ... 163 md := sha512.New() 164 md.Write(priv.D.Bytes()) // the private key, 165 md.Write(entropy) // the entropy, 166 md.Write(hash) // and the input hash; 167 key := md.Sum(nil)[:32] // and compute ChopMD-256(SHA-512), 168 // which is an indifferentiable MAC. 169 170 // Create an AES-CTR instance to use as a CSPRNG. 171 block, err := aes.NewCipher(key) 172 if err != nil { 173 return nil, nil, err 174 } 175 176 // Create a CSPRNG that xors a stream of zeros with 177 // the output of the AES-CTR instance. 178 csprng := cipher.StreamReader{ 179 R: zeroReader, 180 S: cipher.NewCTR(block, []byte(aesIV)), 181 } 182 183 // See [NSA] 3.4.1 184 c := priv.PublicKey.Curve 185 N := c.Params().N 186 if N.Sign() == 0 { 187 return nil, nil, errZeroParam 188 } 189 var k, kInv *big.Int 190 for { 191 for { 192 k, err = randFieldElement(c, csprng) 193 if err != nil { 194 r = nil 195 return 196 } 197 198 if in, ok := priv.Curve.(invertible); ok { 199 kInv = in.Inverse(k) 200 } else { 201 kInv = fermatInverse(k, N) // N != 0 202 } 203 204 r, _ = priv.Curve.ScalarBaseMult(k.Bytes()) 205 r.Mod(r, N) 206 if r.Sign() != 0 { 207 break 208 } 209 } 210 211 e := hashToInt(hash, c) 212 s = new(big.Int).Mul(priv.D, r) 213 s.Add(s, e) 214 s.Mul(s, kInv) 215 s.Mod(s, N) // N != 0 216 if s.Sign() != 0 { 217 break 218 } 219 } 220 221 return 222} 223 224// Verify verifies the signature in r, s of hash using the public key, pub. Its 225// return value records whether the signature is valid. 226func Verify(pub *PublicKey, hash []byte, r, s *big.Int) bool { 227 // See [NSA] 3.4.2 228 c := pub.Curve 229 N := c.Params().N 230 231 if r.Sign() == 0 || s.Sign() == 0 { 232 return false 233 } 234 if r.Cmp(N) >= 0 || s.Cmp(N) >= 0 { 235 return false 236 } 237 e := hashToInt(hash, c) 238 239 var w *big.Int 240 if in, ok := c.(invertible); ok { 241 w = in.Inverse(s) 242 } else { 243 w = new(big.Int).ModInverse(s, N) 244 } 245 246 u1 := e.Mul(e, w) 247 u1.Mod(u1, N) 248 u2 := w.Mul(r, w) 249 u2.Mod(u2, N) 250 251 // Check if implements S1*g + S2*p 252 var x, y *big.Int 253 if opt, ok := c.(combinedMult); ok { 254 x, y = opt.CombinedMult(pub.X, pub.Y, u1.Bytes(), u2.Bytes()) 255 } else { 256 x1, y1 := c.ScalarBaseMult(u1.Bytes()) 257 x2, y2 := c.ScalarMult(pub.X, pub.Y, u2.Bytes()) 258 x, y = c.Add(x1, y1, x2, y2) 259 } 260 261 if x.Sign() == 0 && y.Sign() == 0 { 262 return false 263 } 264 x.Mod(x, N) 265 return x.Cmp(r) == 0 266} 267 268type zr struct { 269 io.Reader 270} 271 272// Read replaces the contents of dst with zeros. 273func (z *zr) Read(dst []byte) (n int, err error) { 274 for i := range dst { 275 dst[i] = 0 276 } 277 return len(dst), nil 278} 279 280var zeroReader = &zr{} 281