Source file src/crypto/elliptic/p224.go

Documentation: crypto/elliptic

		 1  // Copyright 2012 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  // This is a constant-time, 32-bit implementation of P224. See FIPS 186-3,
		 8  // section D.2.2.
		 9  //
		10  // See https://www.imperialviolet.org/2010/12/04/ecc.html ([1]) for background.
		11  
		12  import (
		13  	"math/big"
		14  )
		15  
		16  var p224 p224Curve
		17  
		18  type p224Curve struct {
		19  	*CurveParams
		20  	gx, gy, b p224FieldElement
		21  }
		22  
		23  func initP224() {
		24  	// See FIPS 186-3, section D.2.2
		25  	p224.CurveParams = &CurveParams{Name: "P-224"}
		26  	p224.P, _ = new(big.Int).SetString("26959946667150639794667015087019630673557916260026308143510066298881", 10)
		27  	p224.N, _ = new(big.Int).SetString("26959946667150639794667015087019625940457807714424391721682722368061", 10)
		28  	p224.B, _ = new(big.Int).SetString("b4050a850c04b3abf54132565044b0b7d7bfd8ba270b39432355ffb4", 16)
		29  	p224.Gx, _ = new(big.Int).SetString("b70e0cbd6bb4bf7f321390b94a03c1d356c21122343280d6115c1d21", 16)
		30  	p224.Gy, _ = new(big.Int).SetString("bd376388b5f723fb4c22dfe6cd4375a05a07476444d5819985007e34", 16)
		31  	p224.BitSize = 224
		32  
		33  	p224FromBig(&p224.gx, p224.Gx)
		34  	p224FromBig(&p224.gy, p224.Gy)
		35  	p224FromBig(&p224.b, p224.B)
		36  }
		37  
		38  // P224 returns a Curve which implements P-224 (see FIPS 186-3, section D.2.2).
		39  //
		40  // The cryptographic operations are implemented using constant-time algorithms.
		41  func P224() Curve {
		42  	initonce.Do(initAll)
		43  	return p224
		44  }
		45  
		46  func (curve p224Curve) Params() *CurveParams {
		47  	return curve.CurveParams
		48  }
		49  
		50  func (curve p224Curve) IsOnCurve(bigX, bigY *big.Int) bool {
		51  	if bigX.Sign() < 0 || bigX.Cmp(curve.P) >= 0 ||
		52  		bigY.Sign() < 0 || bigY.Cmp(curve.P) >= 0 {
		53  		return false
		54  	}
		55  
		56  	var x, y p224FieldElement
		57  	p224FromBig(&x, bigX)
		58  	p224FromBig(&y, bigY)
		59  
		60  	// y² = x³ - 3x + b
		61  	var tmp p224LargeFieldElement
		62  	var x3 p224FieldElement
		63  	p224Square(&x3, &x, &tmp)
		64  	p224Mul(&x3, &x3, &x, &tmp)
		65  
		66  	for i := 0; i < 8; i++ {
		67  		x[i] *= 3
		68  	}
		69  	p224Sub(&x3, &x3, &x)
		70  	p224Reduce(&x3)
		71  	p224Add(&x3, &x3, &curve.b)
		72  	p224Contract(&x3, &x3)
		73  
		74  	p224Square(&y, &y, &tmp)
		75  	p224Contract(&y, &y)
		76  
		77  	for i := 0; i < 8; i++ {
		78  		if y[i] != x3[i] {
		79  			return false
		80  		}
		81  	}
		82  	return true
		83  }
		84  
		85  func (p224Curve) Add(bigX1, bigY1, bigX2, bigY2 *big.Int) (x, y *big.Int) {
		86  	var x1, y1, z1, x2, y2, z2, x3, y3, z3 p224FieldElement
		87  
		88  	p224FromBig(&x1, bigX1)
		89  	p224FromBig(&y1, bigY1)
		90  	if bigX1.Sign() != 0 || bigY1.Sign() != 0 {
		91  		z1[0] = 1
		92  	}
		93  	p224FromBig(&x2, bigX2)
		94  	p224FromBig(&y2, bigY2)
		95  	if bigX2.Sign() != 0 || bigY2.Sign() != 0 {
		96  		z2[0] = 1
		97  	}
		98  
		99  	p224AddJacobian(&x3, &y3, &z3, &x1, &y1, &z1, &x2, &y2, &z2)
	 100  	return p224ToAffine(&x3, &y3, &z3)
	 101  }
	 102  
	 103  func (p224Curve) Double(bigX1, bigY1 *big.Int) (x, y *big.Int) {
	 104  	var x1, y1, z1, x2, y2, z2 p224FieldElement
	 105  
	 106  	p224FromBig(&x1, bigX1)
	 107  	p224FromBig(&y1, bigY1)
	 108  	z1[0] = 1
	 109  
	 110  	p224DoubleJacobian(&x2, &y2, &z2, &x1, &y1, &z1)
	 111  	return p224ToAffine(&x2, &y2, &z2)
	 112  }
	 113  
	 114  func (p224Curve) ScalarMult(bigX1, bigY1 *big.Int, scalar []byte) (x, y *big.Int) {
	 115  	var x1, y1, z1, x2, y2, z2 p224FieldElement
	 116  
	 117  	p224FromBig(&x1, bigX1)
	 118  	p224FromBig(&y1, bigY1)
	 119  	z1[0] = 1
	 120  
	 121  	p224ScalarMult(&x2, &y2, &z2, &x1, &y1, &z1, scalar)
	 122  	return p224ToAffine(&x2, &y2, &z2)
	 123  }
	 124  
	 125  func (curve p224Curve) ScalarBaseMult(scalar []byte) (x, y *big.Int) {
	 126  	var z1, x2, y2, z2 p224FieldElement
	 127  
	 128  	z1[0] = 1
	 129  	p224ScalarMult(&x2, &y2, &z2, &curve.gx, &curve.gy, &z1, scalar)
	 130  	return p224ToAffine(&x2, &y2, &z2)
	 131  }
	 132  
	 133  // Field element functions.
	 134  //
	 135  // The field that we're dealing with is ℤ/pℤ where p = 2**224 - 2**96 + 1.
	 136  //
	 137  // Field elements are represented by a FieldElement, which is a typedef to an
	 138  // array of 8 uint32's. The value of a FieldElement, a, is:
	 139  //	 a[0] + 2**28·a[1] + 2**56·a[1] + ... + 2**196·a[7]
	 140  //
	 141  // Using 28-bit limbs means that there's only 4 bits of headroom, which is less
	 142  // than we would really like. But it has the useful feature that we hit 2**224
	 143  // exactly, making the reflections during a reduce much nicer.
	 144  type p224FieldElement [8]uint32
	 145  
	 146  // p224P is the order of the field, represented as a p224FieldElement.
	 147  var p224P = [8]uint32{1, 0, 0, 0xffff000, 0xfffffff, 0xfffffff, 0xfffffff, 0xfffffff}
	 148  
	 149  // p224IsZero returns 1 if a == 0 mod p and 0 otherwise.
	 150  //
	 151  // a[i] < 2**29
	 152  func p224IsZero(a *p224FieldElement) uint32 {
	 153  	// Since a p224FieldElement contains 224 bits there are two possible
	 154  	// representations of 0: 0 and p.
	 155  	var minimal p224FieldElement
	 156  	p224Contract(&minimal, a)
	 157  
	 158  	var isZero, isP uint32
	 159  	for i, v := range minimal {
	 160  		isZero |= v
	 161  		isP |= v - p224P[i]
	 162  	}
	 163  
	 164  	// If either isZero or isP is 0, then we should return 1.
	 165  	isZero |= isZero >> 16
	 166  	isZero |= isZero >> 8
	 167  	isZero |= isZero >> 4
	 168  	isZero |= isZero >> 2
	 169  	isZero |= isZero >> 1
	 170  
	 171  	isP |= isP >> 16
	 172  	isP |= isP >> 8
	 173  	isP |= isP >> 4
	 174  	isP |= isP >> 2
	 175  	isP |= isP >> 1
	 176  
	 177  	// For isZero and isP, the LSB is 0 iff all the bits are zero.
	 178  	result := isZero & isP
	 179  	result = (^result) & 1
	 180  
	 181  	return result
	 182  }
	 183  
	 184  // p224Add computes *out = a+b
	 185  //
	 186  // a[i] + b[i] < 2**32
	 187  func p224Add(out, a, b *p224FieldElement) {
	 188  	for i := 0; i < 8; i++ {
	 189  		out[i] = a[i] + b[i]
	 190  	}
	 191  }
	 192  
	 193  const two31p3 = 1<<31 + 1<<3
	 194  const two31m3 = 1<<31 - 1<<3
	 195  const two31m15m3 = 1<<31 - 1<<15 - 1<<3
	 196  
	 197  // p224ZeroModP31 is 0 mod p where bit 31 is set in all limbs so that we can
	 198  // subtract smaller amounts without underflow. See the section "Subtraction" in
	 199  // [1] for reasoning.
	 200  var p224ZeroModP31 = []uint32{two31p3, two31m3, two31m3, two31m15m3, two31m3, two31m3, two31m3, two31m3}
	 201  
	 202  // p224Sub computes *out = a-b
	 203  //
	 204  // a[i], b[i] < 2**30
	 205  // out[i] < 2**32
	 206  func p224Sub(out, a, b *p224FieldElement) {
	 207  	for i := 0; i < 8; i++ {
	 208  		out[i] = a[i] + p224ZeroModP31[i] - b[i]
	 209  	}
	 210  }
	 211  
	 212  // LargeFieldElement also represents an element of the field. The limbs are
	 213  // still spaced 28-bits apart and in little-endian order. So the limbs are at
	 214  // 0, 28, 56, ..., 392 bits, each 64-bits wide.
	 215  type p224LargeFieldElement [15]uint64
	 216  
	 217  const two63p35 = 1<<63 + 1<<35
	 218  const two63m35 = 1<<63 - 1<<35
	 219  const two63m35m19 = 1<<63 - 1<<35 - 1<<19
	 220  
	 221  // p224ZeroModP63 is 0 mod p where bit 63 is set in all limbs. See the section
	 222  // "Subtraction" in [1] for why.
	 223  var p224ZeroModP63 = [8]uint64{two63p35, two63m35, two63m35, two63m35, two63m35m19, two63m35, two63m35, two63m35}
	 224  
	 225  const bottom12Bits = 0xfff
	 226  const bottom28Bits = 0xfffffff
	 227  
	 228  // p224Mul computes *out = a*b
	 229  //
	 230  // a[i] < 2**29, b[i] < 2**30 (or vice versa)
	 231  // out[i] < 2**29
	 232  func p224Mul(out, a, b *p224FieldElement, tmp *p224LargeFieldElement) {
	 233  	for i := 0; i < 15; i++ {
	 234  		tmp[i] = 0
	 235  	}
	 236  
	 237  	for i := 0; i < 8; i++ {
	 238  		for j := 0; j < 8; j++ {
	 239  			tmp[i+j] += uint64(a[i]) * uint64(b[j])
	 240  		}
	 241  	}
	 242  
	 243  	p224ReduceLarge(out, tmp)
	 244  }
	 245  
	 246  // Square computes *out = a*a
	 247  //
	 248  // a[i] < 2**29
	 249  // out[i] < 2**29
	 250  func p224Square(out, a *p224FieldElement, tmp *p224LargeFieldElement) {
	 251  	for i := 0; i < 15; i++ {
	 252  		tmp[i] = 0
	 253  	}
	 254  
	 255  	for i := 0; i < 8; i++ {
	 256  		for j := 0; j <= i; j++ {
	 257  			r := uint64(a[i]) * uint64(a[j])
	 258  			if i == j {
	 259  				tmp[i+j] += r
	 260  			} else {
	 261  				tmp[i+j] += r << 1
	 262  			}
	 263  		}
	 264  	}
	 265  
	 266  	p224ReduceLarge(out, tmp)
	 267  }
	 268  
	 269  // ReduceLarge converts a p224LargeFieldElement to a p224FieldElement.
	 270  //
	 271  // in[i] < 2**62
	 272  func p224ReduceLarge(out *p224FieldElement, in *p224LargeFieldElement) {
	 273  	for i := 0; i < 8; i++ {
	 274  		in[i] += p224ZeroModP63[i]
	 275  	}
	 276  
	 277  	// Eliminate the coefficients at 2**224 and greater.
	 278  	for i := 14; i >= 8; i-- {
	 279  		in[i-8] -= in[i]
	 280  		in[i-5] += (in[i] & 0xffff) << 12
	 281  		in[i-4] += in[i] >> 16
	 282  	}
	 283  	in[8] = 0
	 284  	// in[0..8] < 2**64
	 285  
	 286  	// As the values become small enough, we start to store them in |out|
	 287  	// and use 32-bit operations.
	 288  	for i := 1; i < 8; i++ {
	 289  		in[i+1] += in[i] >> 28
	 290  		out[i] = uint32(in[i] & bottom28Bits)
	 291  	}
	 292  	in[0] -= in[8]
	 293  	out[3] += uint32(in[8]&0xffff) << 12
	 294  	out[4] += uint32(in[8] >> 16)
	 295  	// in[0] < 2**64
	 296  	// out[3] < 2**29
	 297  	// out[4] < 2**29
	 298  	// out[1,2,5..7] < 2**28
	 299  
	 300  	out[0] = uint32(in[0] & bottom28Bits)
	 301  	out[1] += uint32((in[0] >> 28) & bottom28Bits)
	 302  	out[2] += uint32(in[0] >> 56)
	 303  	// out[0] < 2**28
	 304  	// out[1..4] < 2**29
	 305  	// out[5..7] < 2**28
	 306  }
	 307  
	 308  // Reduce reduces the coefficients of a to smaller bounds.
	 309  //
	 310  // On entry: a[i] < 2**31 + 2**30
	 311  // On exit: a[i] < 2**29
	 312  func p224Reduce(a *p224FieldElement) {
	 313  	for i := 0; i < 7; i++ {
	 314  		a[i+1] += a[i] >> 28
	 315  		a[i] &= bottom28Bits
	 316  	}
	 317  	top := a[7] >> 28
	 318  	a[7] &= bottom28Bits
	 319  
	 320  	// top < 2**4
	 321  	mask := top
	 322  	mask |= mask >> 2
	 323  	mask |= mask >> 1
	 324  	mask <<= 31
	 325  	mask = uint32(int32(mask) >> 31)
	 326  	// Mask is all ones if top != 0, all zero otherwise
	 327  
	 328  	a[0] -= top
	 329  	a[3] += top << 12
	 330  
	 331  	// We may have just made a[0] negative but, if we did, then we must
	 332  	// have added something to a[3], this it's > 2**12. Therefore we can
	 333  	// carry down to a[0].
	 334  	a[3] -= 1 & mask
	 335  	a[2] += mask & (1<<28 - 1)
	 336  	a[1] += mask & (1<<28 - 1)
	 337  	a[0] += mask & (1 << 28)
	 338  }
	 339  
	 340  // p224Invert calculates *out = in**-1 by computing in**(2**224 - 2**96 - 1),
	 341  // i.e. Fermat's little theorem.
	 342  func p224Invert(out, in *p224FieldElement) {
	 343  	var f1, f2, f3, f4 p224FieldElement
	 344  	var c p224LargeFieldElement
	 345  
	 346  	p224Square(&f1, in, &c)		// 2
	 347  	p224Mul(&f1, &f1, in, &c)	// 2**2 - 1
	 348  	p224Square(&f1, &f1, &c)	 // 2**3 - 2
	 349  	p224Mul(&f1, &f1, in, &c)	// 2**3 - 1
	 350  	p224Square(&f2, &f1, &c)	 // 2**4 - 2
	 351  	p224Square(&f2, &f2, &c)	 // 2**5 - 4
	 352  	p224Square(&f2, &f2, &c)	 // 2**6 - 8
	 353  	p224Mul(&f1, &f1, &f2, &c) // 2**6 - 1
	 354  	p224Square(&f2, &f1, &c)	 // 2**7 - 2
	 355  	for i := 0; i < 5; i++ {	 // 2**12 - 2**6
	 356  		p224Square(&f2, &f2, &c)
	 357  	}
	 358  	p224Mul(&f2, &f2, &f1, &c) // 2**12 - 1
	 359  	p224Square(&f3, &f2, &c)	 // 2**13 - 2
	 360  	for i := 0; i < 11; i++ {	// 2**24 - 2**12
	 361  		p224Square(&f3, &f3, &c)
	 362  	}
	 363  	p224Mul(&f2, &f3, &f2, &c) // 2**24 - 1
	 364  	p224Square(&f3, &f2, &c)	 // 2**25 - 2
	 365  	for i := 0; i < 23; i++ {	// 2**48 - 2**24
	 366  		p224Square(&f3, &f3, &c)
	 367  	}
	 368  	p224Mul(&f3, &f3, &f2, &c) // 2**48 - 1
	 369  	p224Square(&f4, &f3, &c)	 // 2**49 - 2
	 370  	for i := 0; i < 47; i++ {	// 2**96 - 2**48
	 371  		p224Square(&f4, &f4, &c)
	 372  	}
	 373  	p224Mul(&f3, &f3, &f4, &c) // 2**96 - 1
	 374  	p224Square(&f4, &f3, &c)	 // 2**97 - 2
	 375  	for i := 0; i < 23; i++ {	// 2**120 - 2**24
	 376  		p224Square(&f4, &f4, &c)
	 377  	}
	 378  	p224Mul(&f2, &f4, &f2, &c) // 2**120 - 1
	 379  	for i := 0; i < 6; i++ {	 // 2**126 - 2**6
	 380  		p224Square(&f2, &f2, &c)
	 381  	}
	 382  	p224Mul(&f1, &f1, &f2, &c) // 2**126 - 1
	 383  	p224Square(&f1, &f1, &c)	 // 2**127 - 2
	 384  	p224Mul(&f1, &f1, in, &c)	// 2**127 - 1
	 385  	for i := 0; i < 97; i++ {	// 2**224 - 2**97
	 386  		p224Square(&f1, &f1, &c)
	 387  	}
	 388  	p224Mul(out, &f1, &f3, &c) // 2**224 - 2**96 - 1
	 389  }
	 390  
	 391  // p224Contract converts a FieldElement to its unique, minimal form.
	 392  //
	 393  // On entry, in[i] < 2**29
	 394  // On exit, out[i] < 2**28 and out < p
	 395  func p224Contract(out, in *p224FieldElement) {
	 396  	copy(out[:], in[:])
	 397  
	 398  	// First, carry the bits above 28 to the higher limb.
	 399  	for i := 0; i < 7; i++ {
	 400  		out[i+1] += out[i] >> 28
	 401  		out[i] &= bottom28Bits
	 402  	}
	 403  	top := out[7] >> 28
	 404  	out[7] &= bottom28Bits
	 405  
	 406  	// Use the reduction identity to carry the overflow.
	 407  	//
	 408  	//	 a + top * 2²²⁴ = a + top * 2⁹⁶ - top
	 409  	out[0] -= top
	 410  	out[3] += top << 12
	 411  
	 412  	// We may just have made out[0] negative. So we carry down. If we made
	 413  	// out[0] negative then we know that out[3] is sufficiently positive
	 414  	// because we just added to it.
	 415  	for i := 0; i < 3; i++ {
	 416  		mask := uint32(int32(out[i]) >> 31)
	 417  		out[i] += (1 << 28) & mask
	 418  		out[i+1] -= 1 & mask
	 419  	}
	 420  
	 421  	// We might have pushed out[3] over 2**28 so we perform another, partial,
	 422  	// carry chain.
	 423  	for i := 3; i < 7; i++ {
	 424  		out[i+1] += out[i] >> 28
	 425  		out[i] &= bottom28Bits
	 426  	}
	 427  	top = out[7] >> 28
	 428  	out[7] &= bottom28Bits
	 429  
	 430  	// Eliminate top while maintaining the same value mod p.
	 431  	out[0] -= top
	 432  	out[3] += top << 12
	 433  
	 434  	// There are two cases to consider for out[3]:
	 435  	//	 1) The first time that we eliminated top, we didn't push out[3] over
	 436  	//			2**28. In this case, the partial carry chain didn't change any values
	 437  	//			and top is now zero.
	 438  	//	 2) We did push out[3] over 2**28 the first time that we eliminated top.
	 439  	//			The first value of top was in [0..2], therefore, after overflowing
	 440  	//			and being reduced by the second carry chain, out[3] <= 2<<12 - 1.
	 441  	// In both cases, out[3] cannot have overflowed when we eliminated top for
	 442  	// the second time.
	 443  
	 444  	// Again, we may just have made out[0] negative, so do the same carry down.
	 445  	// As before, if we made out[0] negative then we know that out[3] is
	 446  	// sufficiently positive.
	 447  	for i := 0; i < 3; i++ {
	 448  		mask := uint32(int32(out[i]) >> 31)
	 449  		out[i] += (1 << 28) & mask
	 450  		out[i+1] -= 1 & mask
	 451  	}
	 452  
	 453  	// Now we see if the value is >= p and, if so, subtract p.
	 454  
	 455  	// First we build a mask from the top four limbs, which must all be
	 456  	// equal to bottom28Bits if the whole value is >= p. If top4AllOnes
	 457  	// ends up with any zero bits in the bottom 28 bits, then this wasn't
	 458  	// true.
	 459  	top4AllOnes := uint32(0xffffffff)
	 460  	for i := 4; i < 8; i++ {
	 461  		top4AllOnes &= out[i]
	 462  	}
	 463  	top4AllOnes |= 0xf0000000
	 464  	// Now we replicate any zero bits to all the bits in top4AllOnes.
	 465  	top4AllOnes &= top4AllOnes >> 16
	 466  	top4AllOnes &= top4AllOnes >> 8
	 467  	top4AllOnes &= top4AllOnes >> 4
	 468  	top4AllOnes &= top4AllOnes >> 2
	 469  	top4AllOnes &= top4AllOnes >> 1
	 470  	top4AllOnes = uint32(int32(top4AllOnes<<31) >> 31)
	 471  
	 472  	// Now we test whether the bottom three limbs are non-zero.
	 473  	bottom3NonZero := out[0] | out[1] | out[2]
	 474  	bottom3NonZero |= bottom3NonZero >> 16
	 475  	bottom3NonZero |= bottom3NonZero >> 8
	 476  	bottom3NonZero |= bottom3NonZero >> 4
	 477  	bottom3NonZero |= bottom3NonZero >> 2
	 478  	bottom3NonZero |= bottom3NonZero >> 1
	 479  	bottom3NonZero = uint32(int32(bottom3NonZero<<31) >> 31)
	 480  
	 481  	// Assuming top4AllOnes != 0, everything depends on the value of out[3].
	 482  	//		If it's > 0xffff000 then the whole value is > p
	 483  	//		If it's = 0xffff000 and bottom3NonZero != 0, then the whole value is >= p
	 484  	//		If it's < 0xffff000, then the whole value is < p
	 485  	n := 0xffff000 - out[3]
	 486  	out3Equal := n
	 487  	out3Equal |= out3Equal >> 16
	 488  	out3Equal |= out3Equal >> 8
	 489  	out3Equal |= out3Equal >> 4
	 490  	out3Equal |= out3Equal >> 2
	 491  	out3Equal |= out3Equal >> 1
	 492  	out3Equal = ^uint32(int32(out3Equal<<31) >> 31)
	 493  
	 494  	// If out[3] > 0xffff000 then n's MSB will be one.
	 495  	out3GT := uint32(int32(n) >> 31)
	 496  
	 497  	mask := top4AllOnes & ((out3Equal & bottom3NonZero) | out3GT)
	 498  	out[0] -= 1 & mask
	 499  	out[3] -= 0xffff000 & mask
	 500  	out[4] -= 0xfffffff & mask
	 501  	out[5] -= 0xfffffff & mask
	 502  	out[6] -= 0xfffffff & mask
	 503  	out[7] -= 0xfffffff & mask
	 504  
	 505  	// Do one final carry down, in case we made out[0] negative. One of
	 506  	// out[0..3] needs to be positive and able to absorb the -1 or the value
	 507  	// would have been < p, and the subtraction wouldn't have happened.
	 508  	for i := 0; i < 3; i++ {
	 509  		mask := uint32(int32(out[i]) >> 31)
	 510  		out[i] += (1 << 28) & mask
	 511  		out[i+1] -= 1 & mask
	 512  	}
	 513  }
	 514  
	 515  // Group element functions.
	 516  //
	 517  // These functions deal with group elements. The group is an elliptic curve
	 518  // group with a = -3 defined in FIPS 186-3, section D.2.2.
	 519  
	 520  // p224AddJacobian computes *out = a+b where a != b.
	 521  func p224AddJacobian(x3, y3, z3, x1, y1, z1, x2, y2, z2 *p224FieldElement) {
	 522  	// See https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#addition-p224Add-2007-bl
	 523  	var z1z1, z2z2, u1, u2, s1, s2, h, i, j, r, v p224FieldElement
	 524  	var c p224LargeFieldElement
	 525  
	 526  	z1IsZero := p224IsZero(z1)
	 527  	z2IsZero := p224IsZero(z2)
	 528  
	 529  	// Z1Z1 = Z1²
	 530  	p224Square(&z1z1, z1, &c)
	 531  	// Z2Z2 = Z2²
	 532  	p224Square(&z2z2, z2, &c)
	 533  	// U1 = X1*Z2Z2
	 534  	p224Mul(&u1, x1, &z2z2, &c)
	 535  	// U2 = X2*Z1Z1
	 536  	p224Mul(&u2, x2, &z1z1, &c)
	 537  	// S1 = Y1*Z2*Z2Z2
	 538  	p224Mul(&s1, z2, &z2z2, &c)
	 539  	p224Mul(&s1, y1, &s1, &c)
	 540  	// S2 = Y2*Z1*Z1Z1
	 541  	p224Mul(&s2, z1, &z1z1, &c)
	 542  	p224Mul(&s2, y2, &s2, &c)
	 543  	// H = U2-U1
	 544  	p224Sub(&h, &u2, &u1)
	 545  	p224Reduce(&h)
	 546  	xEqual := p224IsZero(&h)
	 547  	// I = (2*H)²
	 548  	for j := 0; j < 8; j++ {
	 549  		i[j] = h[j] << 1
	 550  	}
	 551  	p224Reduce(&i)
	 552  	p224Square(&i, &i, &c)
	 553  	// J = H*I
	 554  	p224Mul(&j, &h, &i, &c)
	 555  	// r = 2*(S2-S1)
	 556  	p224Sub(&r, &s2, &s1)
	 557  	p224Reduce(&r)
	 558  	yEqual := p224IsZero(&r)
	 559  	if xEqual == 1 && yEqual == 1 && z1IsZero == 0 && z2IsZero == 0 {
	 560  		p224DoubleJacobian(x3, y3, z3, x1, y1, z1)
	 561  		return
	 562  	}
	 563  	for i := 0; i < 8; i++ {
	 564  		r[i] <<= 1
	 565  	}
	 566  	p224Reduce(&r)
	 567  	// V = U1*I
	 568  	p224Mul(&v, &u1, &i, &c)
	 569  	// Z3 = ((Z1+Z2)²-Z1Z1-Z2Z2)*H
	 570  	p224Add(&z1z1, &z1z1, &z2z2)
	 571  	p224Add(&z2z2, z1, z2)
	 572  	p224Reduce(&z2z2)
	 573  	p224Square(&z2z2, &z2z2, &c)
	 574  	p224Sub(z3, &z2z2, &z1z1)
	 575  	p224Reduce(z3)
	 576  	p224Mul(z3, z3, &h, &c)
	 577  	// X3 = r²-J-2*V
	 578  	for i := 0; i < 8; i++ {
	 579  		z1z1[i] = v[i] << 1
	 580  	}
	 581  	p224Add(&z1z1, &j, &z1z1)
	 582  	p224Reduce(&z1z1)
	 583  	p224Square(x3, &r, &c)
	 584  	p224Sub(x3, x3, &z1z1)
	 585  	p224Reduce(x3)
	 586  	// Y3 = r*(V-X3)-2*S1*J
	 587  	for i := 0; i < 8; i++ {
	 588  		s1[i] <<= 1
	 589  	}
	 590  	p224Mul(&s1, &s1, &j, &c)
	 591  	p224Sub(&z1z1, &v, x3)
	 592  	p224Reduce(&z1z1)
	 593  	p224Mul(&z1z1, &z1z1, &r, &c)
	 594  	p224Sub(y3, &z1z1, &s1)
	 595  	p224Reduce(y3)
	 596  
	 597  	p224CopyConditional(x3, x2, z1IsZero)
	 598  	p224CopyConditional(x3, x1, z2IsZero)
	 599  	p224CopyConditional(y3, y2, z1IsZero)
	 600  	p224CopyConditional(y3, y1, z2IsZero)
	 601  	p224CopyConditional(z3, z2, z1IsZero)
	 602  	p224CopyConditional(z3, z1, z2IsZero)
	 603  }
	 604  
	 605  // p224DoubleJacobian computes *out = a+a.
	 606  func p224DoubleJacobian(x3, y3, z3, x1, y1, z1 *p224FieldElement) {
	 607  	var delta, gamma, beta, alpha, t p224FieldElement
	 608  	var c p224LargeFieldElement
	 609  
	 610  	p224Square(&delta, z1, &c)
	 611  	p224Square(&gamma, y1, &c)
	 612  	p224Mul(&beta, x1, &gamma, &c)
	 613  
	 614  	// alpha = 3*(X1-delta)*(X1+delta)
	 615  	p224Add(&t, x1, &delta)
	 616  	for i := 0; i < 8; i++ {
	 617  		t[i] += t[i] << 1
	 618  	}
	 619  	p224Reduce(&t)
	 620  	p224Sub(&alpha, x1, &delta)
	 621  	p224Reduce(&alpha)
	 622  	p224Mul(&alpha, &alpha, &t, &c)
	 623  
	 624  	// Z3 = (Y1+Z1)²-gamma-delta
	 625  	p224Add(z3, y1, z1)
	 626  	p224Reduce(z3)
	 627  	p224Square(z3, z3, &c)
	 628  	p224Sub(z3, z3, &gamma)
	 629  	p224Reduce(z3)
	 630  	p224Sub(z3, z3, &delta)
	 631  	p224Reduce(z3)
	 632  
	 633  	// X3 = alpha²-8*beta
	 634  	for i := 0; i < 8; i++ {
	 635  		delta[i] = beta[i] << 3
	 636  	}
	 637  	p224Reduce(&delta)
	 638  	p224Square(x3, &alpha, &c)
	 639  	p224Sub(x3, x3, &delta)
	 640  	p224Reduce(x3)
	 641  
	 642  	// Y3 = alpha*(4*beta-X3)-8*gamma²
	 643  	for i := 0; i < 8; i++ {
	 644  		beta[i] <<= 2
	 645  	}
	 646  	p224Sub(&beta, &beta, x3)
	 647  	p224Reduce(&beta)
	 648  	p224Square(&gamma, &gamma, &c)
	 649  	for i := 0; i < 8; i++ {
	 650  		gamma[i] <<= 3
	 651  	}
	 652  	p224Reduce(&gamma)
	 653  	p224Mul(y3, &alpha, &beta, &c)
	 654  	p224Sub(y3, y3, &gamma)
	 655  	p224Reduce(y3)
	 656  }
	 657  
	 658  // p224CopyConditional sets *out = *in iff the least-significant-bit of control
	 659  // is true, and it runs in constant time.
	 660  func p224CopyConditional(out, in *p224FieldElement, control uint32) {
	 661  	control <<= 31
	 662  	control = uint32(int32(control) >> 31)
	 663  
	 664  	for i := 0; i < 8; i++ {
	 665  		out[i] ^= (out[i] ^ in[i]) & control
	 666  	}
	 667  }
	 668  
	 669  func p224ScalarMult(outX, outY, outZ, inX, inY, inZ *p224FieldElement, scalar []byte) {
	 670  	var xx, yy, zz p224FieldElement
	 671  	for i := 0; i < 8; i++ {
	 672  		outX[i] = 0
	 673  		outY[i] = 0
	 674  		outZ[i] = 0
	 675  	}
	 676  
	 677  	for _, byte := range scalar {
	 678  		for bitNum := uint(0); bitNum < 8; bitNum++ {
	 679  			p224DoubleJacobian(outX, outY, outZ, outX, outY, outZ)
	 680  			bit := uint32((byte >> (7 - bitNum)) & 1)
	 681  			p224AddJacobian(&xx, &yy, &zz, inX, inY, inZ, outX, outY, outZ)
	 682  			p224CopyConditional(outX, &xx, bit)
	 683  			p224CopyConditional(outY, &yy, bit)
	 684  			p224CopyConditional(outZ, &zz, bit)
	 685  		}
	 686  	}
	 687  }
	 688  
	 689  // p224ToAffine converts from Jacobian to affine form.
	 690  func p224ToAffine(x, y, z *p224FieldElement) (*big.Int, *big.Int) {
	 691  	var zinv, zinvsq, outx, outy p224FieldElement
	 692  	var tmp p224LargeFieldElement
	 693  
	 694  	if isPointAtInfinity := p224IsZero(z); isPointAtInfinity == 1 {
	 695  		return new(big.Int), new(big.Int)
	 696  	}
	 697  
	 698  	p224Invert(&zinv, z)
	 699  	p224Square(&zinvsq, &zinv, &tmp)
	 700  	p224Mul(x, x, &zinvsq, &tmp)
	 701  	p224Mul(&zinvsq, &zinvsq, &zinv, &tmp)
	 702  	p224Mul(y, y, &zinvsq, &tmp)
	 703  
	 704  	p224Contract(&outx, x)
	 705  	p224Contract(&outy, y)
	 706  	return p224ToBig(&outx), p224ToBig(&outy)
	 707  }
	 708  
	 709  // get28BitsFromEnd returns the least-significant 28 bits from buf>>shift,
	 710  // where buf is interpreted as a big-endian number.
	 711  func get28BitsFromEnd(buf []byte, shift uint) (uint32, []byte) {
	 712  	var ret uint32
	 713  
	 714  	for i := uint(0); i < 4; i++ {
	 715  		var b byte
	 716  		if l := len(buf); l > 0 {
	 717  			b = buf[l-1]
	 718  			// We don't remove the byte if we're about to return and we're not
	 719  			// reading all of it.
	 720  			if i != 3 || shift == 4 {
	 721  				buf = buf[:l-1]
	 722  			}
	 723  		}
	 724  		ret |= uint32(b) << (8 * i) >> shift
	 725  	}
	 726  	ret &= bottom28Bits
	 727  	return ret, buf
	 728  }
	 729  
	 730  // p224FromBig sets *out = *in.
	 731  func p224FromBig(out *p224FieldElement, in *big.Int) {
	 732  	bytes := in.Bytes()
	 733  	out[0], bytes = get28BitsFromEnd(bytes, 0)
	 734  	out[1], bytes = get28BitsFromEnd(bytes, 4)
	 735  	out[2], bytes = get28BitsFromEnd(bytes, 0)
	 736  	out[3], bytes = get28BitsFromEnd(bytes, 4)
	 737  	out[4], bytes = get28BitsFromEnd(bytes, 0)
	 738  	out[5], bytes = get28BitsFromEnd(bytes, 4)
	 739  	out[6], bytes = get28BitsFromEnd(bytes, 0)
	 740  	out[7], bytes = get28BitsFromEnd(bytes, 4)
	 741  }
	 742  
	 743  // p224ToBig returns in as a big.Int.
	 744  func p224ToBig(in *p224FieldElement) *big.Int {
	 745  	var buf [28]byte
	 746  	buf[27] = byte(in[0])
	 747  	buf[26] = byte(in[0] >> 8)
	 748  	buf[25] = byte(in[0] >> 16)
	 749  	buf[24] = byte(((in[0] >> 24) & 0x0f) | (in[1]<<4)&0xf0)
	 750  
	 751  	buf[23] = byte(in[1] >> 4)
	 752  	buf[22] = byte(in[1] >> 12)
	 753  	buf[21] = byte(in[1] >> 20)
	 754  
	 755  	buf[20] = byte(in[2])
	 756  	buf[19] = byte(in[2] >> 8)
	 757  	buf[18] = byte(in[2] >> 16)
	 758  	buf[17] = byte(((in[2] >> 24) & 0x0f) | (in[3]<<4)&0xf0)
	 759  
	 760  	buf[16] = byte(in[3] >> 4)
	 761  	buf[15] = byte(in[3] >> 12)
	 762  	buf[14] = byte(in[3] >> 20)
	 763  
	 764  	buf[13] = byte(in[4])
	 765  	buf[12] = byte(in[4] >> 8)
	 766  	buf[11] = byte(in[4] >> 16)
	 767  	buf[10] = byte(((in[4] >> 24) & 0x0f) | (in[5]<<4)&0xf0)
	 768  
	 769  	buf[9] = byte(in[5] >> 4)
	 770  	buf[8] = byte(in[5] >> 12)
	 771  	buf[7] = byte(in[5] >> 20)
	 772  
	 773  	buf[6] = byte(in[6])
	 774  	buf[5] = byte(in[6] >> 8)
	 775  	buf[4] = byte(in[6] >> 16)
	 776  	buf[3] = byte(((in[6] >> 24) & 0x0f) | (in[7]<<4)&0xf0)
	 777  
	 778  	buf[2] = byte(in[7] >> 4)
	 779  	buf[1] = byte(in[7] >> 12)
	 780  	buf[0] = byte(in[7] >> 20)
	 781  
	 782  	return new(big.Int).SetBytes(buf[:])
	 783  }
	 784  

View as plain text