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 }