p521.go

Documentation: crypto/elliptic

		 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/fiat"
		 9  	"math/big"
		10  )
		11  
		12  type p521Curve struct {
		13  	*CurveParams
		14  }
		15  
		16  var p521 p521Curve
		17  var p521Params *CurveParams
		18  
		19  func initP521() {
		20  	// See FIPS 186-3, section D.2.5
		21  	p521.CurveParams = &CurveParams{Name: "P-521"}
		22  	p521.P, _ = new(big.Int).SetString("6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151", 10)
		23  	p521.N, _ = new(big.Int).SetString("6864797660130609714981900799081393217269435300143305409394463459185543183397655394245057746333217197532963996371363321113864768612440380340372808892707005449", 10)
		24  	p521.B, _ = new(big.Int).SetString("051953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00", 16)
		25  	p521.Gx, _ = new(big.Int).SetString("c6858e06b70404e9cd9e3ecb662395b4429c648139053fb521f828af606b4d3dbaa14b5e77efe75928fe1dc127a2ffa8de3348b3c1856a429bf97e7e31c2e5bd66", 16)
		26  	p521.Gy, _ = new(big.Int).SetString("11839296a789a3bc0045c8a5fb42c7d1bd998f54449579b446817afbd17273e662c97ee72995ef42640c550b9013fad0761353c7086a272c24088be94769fd16650", 16)
		27  	p521.BitSize = 521
		28  }
		29  
		30  func (curve p521Curve) Params() *CurveParams {
		31  	return curve.CurveParams
		32  }
		33  
		34  func (curve p521Curve) IsOnCurve(x, y *big.Int) bool {
		35  	if x.Sign() < 0 || x.Cmp(curve.P) >= 0 ||
		36  		y.Sign() < 0 || y.Cmp(curve.P) >= 0 {
		37  		return false
		38  	}
		39  
		40  	x1 := bigIntToFiatP521(x)
		41  	y1 := bigIntToFiatP521(y)
		42  	b := bigIntToFiatP521(curve.B) // TODO: precompute this value.
		43  
		44  	// x³ - 3x + b.
		45  	x3 := new(fiat.P521Element).Square(x1)
		46  	x3.Mul(x3, x1)
		47  
		48  	threeX := new(fiat.P521Element).Add(x1, x1)
		49  	threeX.Add(threeX, x1)
		50  
		51  	x3.Sub(x3, threeX)
		52  	x3.Add(x3, b)
		53  
		54  	// y² = x³ - 3x + b
		55  	y2 := new(fiat.P521Element).Square(y1)
		56  
		57  	return x3.Equal(y2) == 1
		58  }
		59  
		60  type p521Point struct {
		61  	x, y, z *fiat.P521Element
		62  }
		63  
		64  func fiatP521ToBigInt(x *fiat.P521Element) *big.Int {
		65  	xBytes := x.Bytes()
		66  	for i := range xBytes[:len(xBytes)/2] {
		67  		xBytes[i], xBytes[len(xBytes)-i-1] = xBytes[len(xBytes)-i-1], xBytes[i]
		68  	}
		69  	return new(big.Int).SetBytes(xBytes)
		70  }
		71  
		72  // affineFromJacobian brings a point in Jacobian coordinates back to affine
		73  // coordinates, with (0, 0) representing infinity by convention. It also goes
		74  // back to big.Int values to match the exposed API.
		75  func (curve p521Curve) affineFromJacobian(p *p521Point) (x, y *big.Int) {
		76  	if p.z.IsZero() == 1 {
		77  		return new(big.Int), new(big.Int)
		78  	}
		79  
		80  	zinv := new(fiat.P521Element).Invert(p.z)
		81  	zinvsq := new(fiat.P521Element).Mul(zinv, zinv)
		82  
		83  	xx := new(fiat.P521Element).Mul(p.x, zinvsq)
		84  	zinvsq.Mul(zinvsq, zinv)
		85  	yy := new(fiat.P521Element).Mul(p.y, zinvsq)
		86  
		87  	return fiatP521ToBigInt(xx), fiatP521ToBigInt(yy)
		88  }
		89  
		90  func bigIntToFiatP521(x *big.Int) *fiat.P521Element {
		91  	xBytes := new(big.Int).Mod(x, p521.P).FillBytes(make([]byte, 66))
		92  	for i := range xBytes[:len(xBytes)/2] {
		93  		xBytes[i], xBytes[len(xBytes)-i-1] = xBytes[len(xBytes)-i-1], xBytes[i]
		94  	}
		95  	x1, err := new(fiat.P521Element).SetBytes(xBytes)
		96  	if err != nil {
		97  		// The input is reduced modulo P and encoded in a fixed size bytes
		98  		// slice, this should be impossible.
		99  		panic("internal error: bigIntToFiatP521")
	 100  	}
	 101  	return x1
	 102  }
	 103  
	 104  // jacobianFromAffine converts (x, y) affine coordinates into (x, y, z) Jacobian
	 105  // coordinates. It also converts from big.Int to fiat, which is necessarily a
	 106  // messy and variable-time operation, which we can't avoid due to the exposed API.
	 107  func (curve p521Curve) jacobianFromAffine(x, y *big.Int) *p521Point {
	 108  	// (0, 0) is by convention the point at infinity, which can't be represented
	 109  	// in affine coordinates, but is (0, 0, 0) in Jacobian.
	 110  	if x.Sign() == 0 && y.Sign() == 0 {
	 111  		return &p521Point{
	 112  			x: new(fiat.P521Element),
	 113  			y: new(fiat.P521Element),
	 114  			z: new(fiat.P521Element),
	 115  		}
	 116  	}
	 117  	return &p521Point{
	 118  		x: bigIntToFiatP521(x),
	 119  		y: bigIntToFiatP521(y),
	 120  		z: new(fiat.P521Element).One(),
	 121  	}
	 122  }
	 123  
	 124  func (curve p521Curve) Add(x1, y1, x2, y2 *big.Int) (*big.Int, *big.Int) {
	 125  	p1 := curve.jacobianFromAffine(x1, y1)
	 126  	p2 := curve.jacobianFromAffine(x2, y2)
	 127  	return curve.affineFromJacobian(p1.addJacobian(p1, p2))
	 128  }
	 129  
	 130  // addJacobian sets q = p1 + p2, and returns q. The points may overlap.
	 131  func (q *p521Point) addJacobian(p1, p2 *p521Point) *p521Point {
	 132  	// https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#addition-add-2007-bl
	 133  	z1IsZero := p1.z.IsZero()
	 134  	z2IsZero := p2.z.IsZero()
	 135  
	 136  	z1z1 := new(fiat.P521Element).Square(p1.z)
	 137  	z2z2 := new(fiat.P521Element).Square(p2.z)
	 138  
	 139  	u1 := new(fiat.P521Element).Mul(p1.x, z2z2)
	 140  	u2 := new(fiat.P521Element).Mul(p2.x, z1z1)
	 141  	h := new(fiat.P521Element).Sub(u2, u1)
	 142  	xEqual := h.IsZero() == 1
	 143  	i := new(fiat.P521Element).Add(h, h)
	 144  	i.Square(i)
	 145  	j := new(fiat.P521Element).Mul(h, i)
	 146  
	 147  	s1 := new(fiat.P521Element).Mul(p1.y, p2.z)
	 148  	s1.Mul(s1, z2z2)
	 149  	s2 := new(fiat.P521Element).Mul(p2.y, p1.z)
	 150  	s2.Mul(s2, z1z1)
	 151  	r := new(fiat.P521Element).Sub(s2, s1)
	 152  	yEqual := r.IsZero() == 1
	 153  	if xEqual && yEqual && z1IsZero == 0 && z2IsZero == 0 {
	 154  		return q.doubleJacobian(p1)
	 155  	}
	 156  	r.Add(r, r)
	 157  	v := new(fiat.P521Element).Mul(u1, i)
	 158  
	 159  	x := new(fiat.P521Element).Set(r)
	 160  	x.Square(x)
	 161  	x.Sub(x, j)
	 162  	x.Sub(x, v)
	 163  	x.Sub(x, v)
	 164  
	 165  	y := new(fiat.P521Element).Set(r)
	 166  	v.Sub(v, x)
	 167  	y.Mul(y, v)
	 168  	s1.Mul(s1, j)
	 169  	s1.Add(s1, s1)
	 170  	y.Sub(y, s1)
	 171  
	 172  	z := new(fiat.P521Element).Add(p1.z, p2.z)
	 173  	z.Square(z)
	 174  	z.Sub(z, z1z1)
	 175  	z.Sub(z, z2z2)
	 176  	z.Mul(z, h)
	 177  
	 178  	x.Select(p2.x, x, z1IsZero)
	 179  	x.Select(p1.x, x, z2IsZero)
	 180  	y.Select(p2.y, y, z1IsZero)
	 181  	y.Select(p1.y, y, z2IsZero)
	 182  	z.Select(p2.z, z, z1IsZero)
	 183  	z.Select(p1.z, z, z2IsZero)
	 184  
	 185  	q.x.Set(x)
	 186  	q.y.Set(y)
	 187  	q.z.Set(z)
	 188  	return q
	 189  }
	 190  
	 191  func (curve p521Curve) Double(x1, y1 *big.Int) (*big.Int, *big.Int) {
	 192  	p := curve.jacobianFromAffine(x1, y1)
	 193  	return curve.affineFromJacobian(p.doubleJacobian(p))
	 194  }
	 195  
	 196  // doubleJacobian sets q = p + p, and returns q. The points may overlap.
	 197  func (q *p521Point) doubleJacobian(p *p521Point) *p521Point {
	 198  	// https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#doubling-dbl-2001-b
	 199  	delta := new(fiat.P521Element).Square(p.z)
	 200  	gamma := new(fiat.P521Element).Square(p.y)
	 201  	alpha := new(fiat.P521Element).Sub(p.x, delta)
	 202  	alpha2 := new(fiat.P521Element).Add(p.x, delta)
	 203  	alpha.Mul(alpha, alpha2)
	 204  	alpha2.Set(alpha)
	 205  	alpha.Add(alpha, alpha)
	 206  	alpha.Add(alpha, alpha2)
	 207  
	 208  	beta := alpha2.Mul(p.x, gamma)
	 209  
	 210  	q.x.Square(alpha)
	 211  	beta8 := new(fiat.P521Element).Add(beta, beta)
	 212  	beta8.Add(beta8, beta8)
	 213  	beta8.Add(beta8, beta8)
	 214  	q.x.Sub(q.x, beta8)
	 215  
	 216  	q.z.Add(p.y, p.z)
	 217  	q.z.Square(q.z)
	 218  	q.z.Sub(q.z, gamma)
	 219  	q.z.Sub(q.z, delta)
	 220  
	 221  	beta.Add(beta, beta)
	 222  	beta.Add(beta, beta)
	 223  	beta.Sub(beta, q.x)
	 224  	q.y.Mul(alpha, beta)
	 225  
	 226  	gamma.Square(gamma)
	 227  	gamma.Add(gamma, gamma)
	 228  	gamma.Add(gamma, gamma)
	 229  	gamma.Add(gamma, gamma)
	 230  
	 231  	q.y.Sub(q.y, gamma)
	 232  
	 233  	return q
	 234  }
	 235  
	 236  func (curve p521Curve) ScalarMult(Bx, By *big.Int, scalar []byte) (*big.Int, *big.Int) {
	 237  	B := curve.jacobianFromAffine(Bx, By)
	 238  	p, t := &p521Point{
	 239  		x: new(fiat.P521Element),
	 240  		y: new(fiat.P521Element),
	 241  		z: new(fiat.P521Element),
	 242  	}, &p521Point{
	 243  		x: new(fiat.P521Element),
	 244  		y: new(fiat.P521Element),
	 245  		z: new(fiat.P521Element),
	 246  	}
	 247  
	 248  	for _, byte := range scalar {
	 249  		for bitNum := 0; bitNum < 8; bitNum++ {
	 250  			p.doubleJacobian(p)
	 251  			bit := (byte >> (7 - bitNum)) & 1
	 252  			t.addJacobian(p, B)
	 253  			p.x.Select(t.x, p.x, int(bit))
	 254  			p.y.Select(t.y, p.y, int(bit))
	 255  			p.z.Select(t.z, p.z, int(bit))
	 256  		}
	 257  	}
	 258  
	 259  	return curve.affineFromJacobian(p)
	 260  }
	 261  
	 262  func (curve p521Curve) ScalarBaseMult(k []byte) (*big.Int, *big.Int) {
	 263  	return curve.ScalarMult(curve.Gx, curve.Gy, k)
	 264  }
	 265
View as plain text