vendor/github.com/btcsuite/btcd/btcec/pubkey.go

   1 // Copyright (c) 2013-2014 The btcsuite developers
   2 // Use of this source code is governed by an ISC
   3 // license that can be found in the LICENSE file.
   4
   5 package btcec
   6
   7 import (
   8         "crypto/ecdsa"
   9         "errors"
  10         "fmt"
  11         "math/big"
  12 )
  13
  14 // These constants define the lengths of serialized public keys.
  15 const (
  16         PubKeyBytesLenCompressed   = 33
  17         PubKeyBytesLenUncompressed = 65
  18         PubKeyBytesLenHybrid       = 65
  19 )
  20
  21 func isOdd(a *big.Int) bool {
  22         return a.Bit(0) == 1
  23 }
  24
  25 // decompressPoint decompresses a point on the given curve given the X point and
  26 // the solution to use.
  27 func decompressPoint(curve *KoblitzCurve, x *big.Int, ybit bool) (*big.Int, error) {
  28         // TODO: This will probably only work for secp256k1 due to
  29         // optimizations.
  30
  31         // Y = +-sqrt(x^3 + B)
  32         x3 := new(big.Int).Mul(x, x)
  33         x3.Mul(x3, x)
  34         x3.Add(x3, curve.Params().B)
  35
  36         // now calculate sqrt mod p of x2 + B
  37         // This code used to do a full sqrt based on tonelli/shanks,
  38         // but this was replaced by the algorithms referenced in
  39         // https://bitcointalk.org/index.php?topic=162805.msg1712294#msg1712294
  40         y := new(big.Int).Exp(x3, curve.QPlus1Div4(), curve.Params().P)
  41
  42         if ybit != isOdd(y) {
  43                 y.Sub(curve.Params().P, y)
  44         }
  45         if ybit != isOdd(y) {
  46                 return nil, fmt.Errorf("ybit doesn't match oddness")
  47         }
  48         return y, nil
  49 }
  50
  51 const (
  52         pubkeyCompressed   byte = 0x2 // y_bit + x coord
  53         pubkeyUncompressed byte = 0x4 // x coord + y coord
  54         pubkeyHybrid       byte = 0x6 // y_bit + x coord + y coord
  55 )
  56
  57 // IsCompressedPubKey returns true the the passed serialized public key has
  58 // been encoded in compressed format, and false otherwise.
  59 func IsCompressedPubKey(pubKey []byte) bool {
  60         // The public key is only compressed if it is the correct length and
  61         // the format (first byte) is one of the compressed pubkey values.
  62         return len(pubKey) == PubKeyBytesLenCompressed &&
  63                 (pubKey[0]&^byte(0x1) == pubkeyCompressed)
  64 }
  65
  66 // ParsePubKey parses a public key for a koblitz curve from a bytestring into a
  67 // ecdsa.Publickey, verifying that it is valid. It supports compressed,
  68 // uncompressed and hybrid signature formats.
  69 func ParsePubKey(pubKeyStr []byte, curve *KoblitzCurve) (key *PublicKey, err error) {
  70         pubkey := PublicKey{}
  71         pubkey.Curve = curve
  72
  73         if len(pubKeyStr) == 0 {
  74                 return nil, errors.New("pubkey string is empty")
  75         }
  76
  77         format := pubKeyStr[0]
  78         ybit := (format & 0x1) == 0x1
  79         format &= ^byte(0x1)
  80
  81         switch len(pubKeyStr) {
  82         case PubKeyBytesLenUncompressed:
  83                 if format != pubkeyUncompressed && format != pubkeyHybrid {
  84                         return nil, fmt.Errorf("invalid magic in pubkey str: "+
  85                                 "%d", pubKeyStr[0])
  86                 }
  87
  88                 pubkey.X = new(big.Int).SetBytes(pubKeyStr[1:33])
  89                 pubkey.Y = new(big.Int).SetBytes(pubKeyStr[33:])
  90                 // hybrid keys have extra information, make use of it.
  91                 if format == pubkeyHybrid && ybit != isOdd(pubkey.Y) {
  92                         return nil, fmt.Errorf("ybit doesn't match oddness")
  93                 }
  94         case PubKeyBytesLenCompressed:
  95                 // format is 0x2 | solution, <X coordinate>
  96                 // solution determines which solution of the curve we use.
  97                 /// y^2 = x^3 + Curve.B
  98                 if format != pubkeyCompressed {
  99                         return nil, fmt.Errorf("invalid magic in compressed "+
 100                                 "pubkey string: %d", pubKeyStr[0])
 101                 }
 102                 pubkey.X = new(big.Int).SetBytes(pubKeyStr[1:33])
 103                 pubkey.Y, err = decompressPoint(curve, pubkey.X, ybit)
 104                 if err != nil {
 105                         return nil, err
 106                 }
 107         default: // wrong!
 108                 return nil, fmt.Errorf("invalid pub key length %d",
 109                         len(pubKeyStr))
 110         }
 111
 112         if pubkey.X.Cmp(pubkey.Curve.Params().P) >= 0 {
 113                 return nil, fmt.Errorf("pubkey X parameter is >= to P")
 114         }
 115         if pubkey.Y.Cmp(pubkey.Curve.Params().P) >= 0 {
 116                 return nil, fmt.Errorf("pubkey Y parameter is >= to P")
 117         }
 118         if !pubkey.Curve.IsOnCurve(pubkey.X, pubkey.Y) {
 119                 return nil, fmt.Errorf("pubkey isn't on secp256k1 curve")
 120         }
 121         return &pubkey, nil
 122 }
 123
 124 // PublicKey is an ecdsa.PublicKey with additional functions to
 125 // serialize in uncompressed, compressed, and hybrid formats.
 126 type PublicKey ecdsa.PublicKey
 127
 128 // ToECDSA returns the public key as a *ecdsa.PublicKey.
 129 func (p *PublicKey) ToECDSA() *ecdsa.PublicKey {
 130         return (*ecdsa.PublicKey)(p)
 131 }
 132
 133 // SerializeUncompressed serializes a public key in a 65-byte uncompressed
 134 // format.
 135 func (p *PublicKey) SerializeUncompressed() []byte {
 136         b := make([]byte, 0, PubKeyBytesLenUncompressed)
 137         b = append(b, pubkeyUncompressed)
 138         b = paddedAppend(32, b, p.X.Bytes())
 139         return paddedAppend(32, b, p.Y.Bytes())
 140 }
 141
 142 // SerializeCompressed serializes a public key in a 33-byte compressed format.
 143 func (p *PublicKey) SerializeCompressed() []byte {
 144         b := make([]byte, 0, PubKeyBytesLenCompressed)
 145         format := pubkeyCompressed
 146         if isOdd(p.Y) {
 147                 format |= 0x1
 148         }
 149         b = append(b, format)
 150         return paddedAppend(32, b, p.X.Bytes())
 151 }
 152
 153 // SerializeHybrid serializes a public key in a 65-byte hybrid format.
 154 func (p *PublicKey) SerializeHybrid() []byte {
 155         b := make([]byte, 0, PubKeyBytesLenHybrid)
 156         format := pubkeyHybrid
 157         if isOdd(p.Y) {
 158                 format |= 0x1
 159         }
 160         b = append(b, format)
 161         b = paddedAppend(32, b, p.X.Bytes())
 162         return paddedAppend(32, b, p.Y.Bytes())
 163 }
 164
 165 // IsEqual compares this PublicKey instance to the one passed, returning true if
 166 // both PublicKeys are equivalent. A PublicKey is equivalent to another, if they
 167 // both have the same X and Y coordinate.
 168 func (p *PublicKey) IsEqual(otherPubKey *PublicKey) bool {
 169         return p.X.Cmp(otherPubKey.X) == 0 &&
 170                 p.Y.Cmp(otherPubKey.Y) == 0
 171 }
 172
 173 // paddedAppend appends the src byte slice to dst, returning the new slice.
 174 // If the length of the source is smaller than the passed size, leading zero
 175 // bytes are appended to the dst slice before appending src.
 176 func paddedAppend(size uint, dst, src []byte) []byte {
 177         for i := 0; i < int(size)-len(src); i++ {
 178                 dst = append(dst, 0)
 179         }
 180         return append(dst, src...)
 181 }