p521.go

     1  // Copyright 2013 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 elliptic
     6  
     7  import (
     8  	"crypto/elliptic/internal/nistec"
     9  	"crypto/rand"
    10  	"math/big"
    11  )
    12  
    13  // p521Curve is a Curve implementation based on nistec.P521Point.
    14  //
    15  // It's a wrapper that exposes the big.Int-based Curve interface and encodes the
    16  // legacy idiosyncrasies it requires, such as invalid and infinity point
    17  // handling.
    18  //
    19  // To interact with the nistec package, points are encoded into and decoded from
    20  // properly formatted byte slices. All big.Int use is limited to this package.
    21  // Encoding and decoding is 1/1000th of the runtime of a scalar multiplication,
    22  // so the overhead is acceptable.
    23  type p521Curve struct {
    24  	params *CurveParams
    25  }
    26  
    27  var p521 p521Curve
    28  var _ Curve = p521
    29  
    30  func initP521() {
    31  	p521.params = &CurveParams{
    32  		Name:    "P-521",
    33  		BitSize: 521,
    34  		// FIPS 186-4, section D.1.2.5
    35  		P: bigFromDecimal("68647976601306097149819007990813932172694353001433" +
    36  			"0540939446345918554318339765605212255964066145455497729631139148" +
    37  			"0858037121987999716643812574028291115057151"),
    38  		N: bigFromDecimal("68647976601306097149819007990813932172694353001433" +
    39  			"0540939446345918554318339765539424505774633321719753296399637136" +
    40  			"3321113864768612440380340372808892707005449"),
    41  		B: bigFromHex("0051953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8" +
    42  			"b489918ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef" +
    43  			"451fd46b503f00"),
    44  		Gx: bigFromHex("00c6858e06b70404e9cd9e3ecb662395b4429c648139053fb521f8" +
    45  			"28af606b4d3dbaa14b5e77efe75928fe1dc127a2ffa8de3348b3c1856a429bf9" +
    46  			"7e7e31c2e5bd66"),
    47  		Gy: bigFromHex("011839296a789a3bc0045c8a5fb42c7d1bd998f54449579b446817" +
    48  			"afbd17273e662c97ee72995ef42640c550b9013fad0761353c7086a272c24088" +
    49  			"be94769fd16650"),
    50  	}
    51  }
    52  
    53  func (curve p521Curve) Params() *CurveParams {
    54  	return curve.params
    55  }
    56  
    57  func (curve p521Curve) IsOnCurve(x, y *big.Int) bool {
    58  	// IsOnCurve is documented to reject (0, 0), the conventional point at
    59  	// infinity, which however is accepted by p521PointFromAffine.
    60  	if x.Sign() == 0 && y.Sign() == 0 {
    61  		return false
    62  	}
    63  	_, ok := p521PointFromAffine(x, y)
    64  	return ok
    65  }
    66  
    67  func p521PointFromAffine(x, y *big.Int) (p *nistec.P521Point, ok bool) {
    68  	// (0, 0) is by convention the point at infinity, which can't be represented
    69  	// in affine coordinates. Marshal incorrectly encodes it as an uncompressed
    70  	// point, which SetBytes would correctly reject. See Issue 37294.
    71  	if x.Sign() == 0 && y.Sign() == 0 {
    72  		return nistec.NewP521Point(), true
    73  	}
    74  	if x.Sign() < 0 || y.Sign() < 0 {
    75  		return nil, false
    76  	}
    77  	if x.BitLen() > 521 || y.BitLen() > 521 {
    78  		return nil, false
    79  	}
    80  	p, err := nistec.NewP521Point().SetBytes(Marshal(P521(), x, y))
    81  	if err != nil {
    82  		return nil, false
    83  	}
    84  	return p, true
    85  }
    86  
    87  func p521PointToAffine(p *nistec.P521Point) (x, y *big.Int) {
    88  	out := p.Bytes()
    89  	if len(out) == 1 && out[0] == 0 {
    90  		// This is the correct encoding of the point at infinity, which
    91  		// Unmarshal does not support. See Issue 37294.
    92  		return new(big.Int), new(big.Int)
    93  	}
    94  	x, y = Unmarshal(P521(), out)
    95  	if x == nil {
    96  		panic("crypto/elliptic: internal error: Unmarshal rejected a valid point encoding")
    97  	}
    98  	return x, y
    99  }
   100  
   101  // p521RandomPoint returns a random point on the curve. It's used when Add,
   102  // Double, or ScalarMult are fed a point not on the curve, which is undefined
   103  // behavior. Originally, we used to do the math on it anyway (which allows
   104  // invalid curve attacks) and relied on the caller and Unmarshal to avoid this
   105  // happening in the first place. Now, we just can't construct a nistec.P521Point
   106  // for an invalid pair of coordinates, because that API is safer. If we panic,
   107  // we risk introducing a DoS. If we return nil, we risk a panic. If we return
   108  // the input, ecdsa.Verify might fail open. The safest course seems to be to
   109  // return a valid, random point, which hopefully won't help the attacker.
   110  func p521RandomPoint() (x, y *big.Int) {
   111  	_, x, y, err := GenerateKey(P521(), rand.Reader)
   112  	if err != nil {
   113  		panic("crypto/elliptic: failed to generate random point")
   114  	}
   115  	return x, y
   116  }
   117  
   118  func (p521Curve) Add(x1, y1, x2, y2 *big.Int) (*big.Int, *big.Int) {
   119  	p1, ok := p521PointFromAffine(x1, y1)
   120  	if !ok {
   121  		return p521RandomPoint()
   122  	}
   123  	p2, ok := p521PointFromAffine(x2, y2)
   124  	if !ok {
   125  		return p521RandomPoint()
   126  	}
   127  	return p521PointToAffine(p1.Add(p1, p2))
   128  }
   129  
   130  func (p521Curve) Double(x1, y1 *big.Int) (*big.Int, *big.Int) {
   131  	p, ok := p521PointFromAffine(x1, y1)
   132  	if !ok {
   133  		return p521RandomPoint()
   134  	}
   135  	return p521PointToAffine(p.Double(p))
   136  }
   137  
   138  func (p521Curve) ScalarMult(Bx, By *big.Int, scalar []byte) (*big.Int, *big.Int) {
   139  	p, ok := p521PointFromAffine(Bx, By)
   140  	if !ok {
   141  		return p521RandomPoint()
   142  	}
   143  	return p521PointToAffine(p.ScalarMult(p, scalar))
   144  }
   145  
   146  func (p521Curve) ScalarBaseMult(scalar []byte) (*big.Int, *big.Int) {
   147  	p := nistec.NewP521Generator()
   148  	return p521PointToAffine(p.ScalarMult(p, scalar))
   149  }
   150  
   151  func bigFromDecimal(s string) *big.Int {
   152  	b, ok := new(big.Int).SetString(s, 10)
   153  	if !ok {
   154  		panic("invalid encoding")
   155  	}
   156  	return b
   157  }
   158  
   159  func bigFromHex(s string) *big.Int {
   160  	b, ok := new(big.Int).SetString(s, 16)
   161  	if !ok {
   162  		panic("invalid encoding")
   163  	}
   164  	return b
   165  }
   166
View as plain text