Source file src/pkg/crypto/ecdsa/ecdsa.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 ecdsa implements the Elliptic Curve Digital Signature Algorithm, as 6 // defined in FIPS 186-3. 7 package ecdsa 8 9 // References: 10 // [NSA]: Suite B implementer's guide to FIPS 186-3, 11 // http://www.nsa.gov/ia/_files/ecdsa.pdf 12 // [SECG]: SECG, SEC1 13 // http://www.secg.org/download/aid-780/sec1-v2.pdf 14 15 import ( 16 "crypto/elliptic" 17 "io" 18 "math/big" 19 ) 20 21 // PublicKey represents an ECDSA public key. 22 type PublicKey struct { 23 elliptic.Curve 24 X, Y *big.Int 25 } 26 27 // PrivateKey represents a ECDSA private key. 28 type PrivateKey struct { 29 PublicKey 30 D *big.Int 31 } 32 33 var one = new(big.Int).SetInt64(1) 34 35 // randFieldElement returns a random element of the field underlying the given 36 // curve using the procedure given in [NSA] A.2.1. 37 func randFieldElement(c elliptic.Curve, rand io.Reader) (k *big.Int, err error) { 38 params := c.Params() 39 b := make([]byte, params.BitSize/8+8) 40 _, err = io.ReadFull(rand, b) 41 if err != nil { 42 return 43 } 44 45 k = new(big.Int).SetBytes(b) 46 n := new(big.Int).Sub(params.N, one) 47 k.Mod(k, n) 48 k.Add(k, one) 49 return 50 } 51 52 // GenerateKey generates a public&private key pair. 53 func GenerateKey(c elliptic.Curve, rand io.Reader) (priv *PrivateKey, err error) { 54 k, err := randFieldElement(c, rand) 55 if err != nil { 56 return 57 } 58 59 priv = new(PrivateKey) 60 priv.PublicKey.Curve = c 61 priv.D = k 62 priv.PublicKey.X, priv.PublicKey.Y = c.ScalarBaseMult(k.Bytes()) 63 return 64 } 65 66 // hashToInt converts a hash value to an integer. There is some disagreement 67 // about how this is done. [NSA] suggests that this is done in the obvious 68 // manner, but [SECG] truncates the hash to the bit-length of the curve order 69 // first. We follow [SECG] because that's what OpenSSL does. 70 func hashToInt(hash []byte, c elliptic.Curve) *big.Int { 71 orderBits := c.Params().N.BitLen() 72 orderBytes := (orderBits + 7) / 8 73 if len(hash) > orderBytes { 74 hash = hash[:orderBytes] 75 } 76 77 ret := new(big.Int).SetBytes(hash) 78 excess := orderBytes*8 - orderBits 79 if excess > 0 { 80 ret.Rsh(ret, uint(excess)) 81 } 82 return ret 83 } 84 85 // Sign signs an arbitrary length hash (which should be the result of hashing a 86 // larger message) using the private key, priv. It returns the signature as a 87 // pair of integers. The security of the private key depends on the entropy of 88 // rand. 89 func Sign(rand io.Reader, priv *PrivateKey, hash []byte) (r, s *big.Int, err error) { 90 // See [NSA] 3.4.1 91 c := priv.PublicKey.Curve 92 N := c.Params().N 93 94 var k, kInv *big.Int 95 for { 96 for { 97 k, err = randFieldElement(c, rand) 98 if err != nil { 99 r = nil 100 return 101 } 102 103 kInv = new(big.Int).ModInverse(k, N) 104 r, _ = priv.Curve.ScalarBaseMult(k.Bytes()) 105 r.Mod(r, N) 106 if r.Sign() != 0 { 107 break 108 } 109 } 110 111 e := hashToInt(hash, c) 112 s = new(big.Int).Mul(priv.D, r) 113 s.Add(s, e) 114 s.Mul(s, kInv) 115 s.Mod(s, N) 116 if s.Sign() != 0 { 117 break 118 } 119 } 120 121 return 122 } 123 124 // Verify verifies the signature in r, s of hash using the public key, pub. It 125 // returns true iff the signature is valid. 126 func Verify(pub *PublicKey, hash []byte, r, s *big.Int) bool { 127 // See [NSA] 3.4.2 128 c := pub.Curve 129 N := c.Params().N 130 131 if r.Sign() == 0 || s.Sign() == 0 { 132 return false 133 } 134 if r.Cmp(N) >= 0 || s.Cmp(N) >= 0 { 135 return false 136 } 137 e := hashToInt(hash, c) 138 w := new(big.Int).ModInverse(s, N) 139 140 u1 := e.Mul(e, w) 141 u2 := w.Mul(r, w) 142 143 x1, y1 := c.ScalarBaseMult(u1.Bytes()) 144 x2, y2 := c.ScalarMult(pub.X, pub.Y, u2.Bytes()) 145 if x1.Cmp(x2) == 0 { 146 return false 147 } 148 x, _ := c.Add(x1, y1, x2, y2) 149 x.Mod(x, N) 150 return x.Cmp(r) == 0 151 }