Source file src/pkg/crypto/elliptic/p224.go

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