1package org.bouncycastle.math.ec; 2 3import java.math.BigInteger; 4 5/** 6 * Class holding methods for point multiplication based on the window 7 * τ-adic nonadjacent form (WTNAF). The algorithms are based on the 8 * paper "Improved Algorithms for Arithmetic on Anomalous Binary Curves" 9 * by Jerome A. Solinas. The paper first appeared in the Proceedings of 10 * Crypto 1997. 11 */ 12class Tnaf 13{ 14 private static final BigInteger MINUS_ONE = ECConstants.ONE.negate(); 15 private static final BigInteger MINUS_TWO = ECConstants.TWO.negate(); 16 private static final BigInteger MINUS_THREE = ECConstants.THREE.negate(); 17 18 /** 19 * The window width of WTNAF. The standard value of 4 is slightly less 20 * than optimal for running time, but keeps space requirements for 21 * precomputation low. For typical curves, a value of 5 or 6 results in 22 * a better running time. When changing this value, the 23 * <code>α<sub>u</sub></code>'s must be computed differently, see 24 * e.g. "Guide to Elliptic Curve Cryptography", Darrel Hankerson, 25 * Alfred Menezes, Scott Vanstone, Springer-Verlag New York Inc., 2004, 26 * p. 121-122 27 */ 28 public static final byte WIDTH = 4; 29 30 /** 31 * 2<sup>4</sup> 32 */ 33 public static final byte POW_2_WIDTH = 16; 34 35 /** 36 * The <code>α<sub>u</sub></code>'s for <code>a=0</code> as an array 37 * of <code>ZTauElement</code>s. 38 */ 39 public static final ZTauElement[] alpha0 = { 40 null, 41 new ZTauElement(ECConstants.ONE, ECConstants.ZERO), null, 42 new ZTauElement(MINUS_THREE, MINUS_ONE), null, 43 new ZTauElement(MINUS_ONE, MINUS_ONE), null, 44 new ZTauElement(ECConstants.ONE, MINUS_ONE), null 45 }; 46 47 /** 48 * The <code>α<sub>u</sub></code>'s for <code>a=0</code> as an array 49 * of TNAFs. 50 */ 51 public static final byte[][] alpha0Tnaf = { 52 null, {1}, null, {-1, 0, 1}, null, {1, 0, 1}, null, {-1, 0, 0, 1} 53 }; 54 55 /** 56 * The <code>α<sub>u</sub></code>'s for <code>a=1</code> as an array 57 * of <code>ZTauElement</code>s. 58 */ 59 public static final ZTauElement[] alpha1 = {null, 60 new ZTauElement(ECConstants.ONE, ECConstants.ZERO), null, 61 new ZTauElement(MINUS_THREE, ECConstants.ONE), null, 62 new ZTauElement(MINUS_ONE, ECConstants.ONE), null, 63 new ZTauElement(ECConstants.ONE, ECConstants.ONE), null 64 }; 65 66 /** 67 * The <code>α<sub>u</sub></code>'s for <code>a=1</code> as an array 68 * of TNAFs. 69 */ 70 public static final byte[][] alpha1Tnaf = { 71 null, {1}, null, {-1, 0, 1}, null, {1, 0, 1}, null, {-1, 0, 0, -1} 72 }; 73 74 /** 75 * Computes the norm of an element <code>λ</code> of 76 * <code><b>Z</b>[τ]</code>. 77 * @param mu The parameter <code>μ</code> of the elliptic curve. 78 * @param lambda The element <code>λ</code> of 79 * <code><b>Z</b>[τ]</code>. 80 * @return The norm of <code>λ</code>. 81 */ 82 public static BigInteger norm(final byte mu, ZTauElement lambda) 83 { 84 BigInteger norm; 85 86 // s1 = u^2 87 BigInteger s1 = lambda.u.multiply(lambda.u); 88 89 // s2 = u * v 90 BigInteger s2 = lambda.u.multiply(lambda.v); 91 92 // s3 = 2 * v^2 93 BigInteger s3 = lambda.v.multiply(lambda.v).shiftLeft(1); 94 95 if (mu == 1) 96 { 97 norm = s1.add(s2).add(s3); 98 } 99 else if (mu == -1) 100 { 101 norm = s1.subtract(s2).add(s3); 102 } 103 else 104 { 105 throw new IllegalArgumentException("mu must be 1 or -1"); 106 } 107 108 return norm; 109 } 110 111 /** 112 * Computes the norm of an element <code>λ</code> of 113 * <code><b>R</b>[τ]</code>, where <code>λ = u + vτ</code> 114 * and <code>u</code> and <code>u</code> are real numbers (elements of 115 * <code><b>R</b></code>). 116 * @param mu The parameter <code>μ</code> of the elliptic curve. 117 * @param u The real part of the element <code>λ</code> of 118 * <code><b>R</b>[τ]</code>. 119 * @param v The <code>τ</code>-adic part of the element 120 * <code>λ</code> of <code><b>R</b>[τ]</code>. 121 * @return The norm of <code>λ</code>. 122 */ 123 public static SimpleBigDecimal norm(final byte mu, SimpleBigDecimal u, 124 SimpleBigDecimal v) 125 { 126 SimpleBigDecimal norm; 127 128 // s1 = u^2 129 SimpleBigDecimal s1 = u.multiply(u); 130 131 // s2 = u * v 132 SimpleBigDecimal s2 = u.multiply(v); 133 134 // s3 = 2 * v^2 135 SimpleBigDecimal s3 = v.multiply(v).shiftLeft(1); 136 137 if (mu == 1) 138 { 139 norm = s1.add(s2).add(s3); 140 } 141 else if (mu == -1) 142 { 143 norm = s1.subtract(s2).add(s3); 144 } 145 else 146 { 147 throw new IllegalArgumentException("mu must be 1 or -1"); 148 } 149 150 return norm; 151 } 152 153 /** 154 * Rounds an element <code>λ</code> of <code><b>R</b>[τ]</code> 155 * to an element of <code><b>Z</b>[τ]</code>, such that their difference 156 * has minimal norm. <code>λ</code> is given as 157 * <code>λ = λ<sub>0</sub> + λ<sub>1</sub>τ</code>. 158 * @param lambda0 The component <code>λ<sub>0</sub></code>. 159 * @param lambda1 The component <code>λ<sub>1</sub></code>. 160 * @param mu The parameter <code>μ</code> of the elliptic curve. Must 161 * equal 1 or -1. 162 * @return The rounded element of <code><b>Z</b>[τ]</code>. 163 * @throws IllegalArgumentException if <code>lambda0</code> and 164 * <code>lambda1</code> do not have same scale. 165 */ 166 public static ZTauElement round(SimpleBigDecimal lambda0, 167 SimpleBigDecimal lambda1, byte mu) 168 { 169 int scale = lambda0.getScale(); 170 if (lambda1.getScale() != scale) 171 { 172 throw new IllegalArgumentException("lambda0 and lambda1 do not " + 173 "have same scale"); 174 } 175 176 if (!((mu == 1) || (mu == -1))) 177 { 178 throw new IllegalArgumentException("mu must be 1 or -1"); 179 } 180 181 BigInteger f0 = lambda0.round(); 182 BigInteger f1 = lambda1.round(); 183 184 SimpleBigDecimal eta0 = lambda0.subtract(f0); 185 SimpleBigDecimal eta1 = lambda1.subtract(f1); 186 187 // eta = 2*eta0 + mu*eta1 188 SimpleBigDecimal eta = eta0.add(eta0); 189 if (mu == 1) 190 { 191 eta = eta.add(eta1); 192 } 193 else 194 { 195 // mu == -1 196 eta = eta.subtract(eta1); 197 } 198 199 // check1 = eta0 - 3*mu*eta1 200 // check2 = eta0 + 4*mu*eta1 201 SimpleBigDecimal threeEta1 = eta1.add(eta1).add(eta1); 202 SimpleBigDecimal fourEta1 = threeEta1.add(eta1); 203 SimpleBigDecimal check1; 204 SimpleBigDecimal check2; 205 if (mu == 1) 206 { 207 check1 = eta0.subtract(threeEta1); 208 check2 = eta0.add(fourEta1); 209 } 210 else 211 { 212 // mu == -1 213 check1 = eta0.add(threeEta1); 214 check2 = eta0.subtract(fourEta1); 215 } 216 217 byte h0 = 0; 218 byte h1 = 0; 219 220 // if eta >= 1 221 if (eta.compareTo(ECConstants.ONE) >= 0) 222 { 223 if (check1.compareTo(MINUS_ONE) < 0) 224 { 225 h1 = mu; 226 } 227 else 228 { 229 h0 = 1; 230 } 231 } 232 else 233 { 234 // eta < 1 235 if (check2.compareTo(ECConstants.TWO) >= 0) 236 { 237 h1 = mu; 238 } 239 } 240 241 // if eta < -1 242 if (eta.compareTo(MINUS_ONE) < 0) 243 { 244 if (check1.compareTo(ECConstants.ONE) >= 0) 245 { 246 h1 = (byte)-mu; 247 } 248 else 249 { 250 h0 = -1; 251 } 252 } 253 else 254 { 255 // eta >= -1 256 if (check2.compareTo(MINUS_TWO) < 0) 257 { 258 h1 = (byte)-mu; 259 } 260 } 261 262 BigInteger q0 = f0.add(BigInteger.valueOf(h0)); 263 BigInteger q1 = f1.add(BigInteger.valueOf(h1)); 264 return new ZTauElement(q0, q1); 265 } 266 267 /** 268 * Approximate division by <code>n</code>. For an integer 269 * <code>k</code>, the value <code>λ = s k / n</code> is 270 * computed to <code>c</code> bits of accuracy. 271 * @param k The parameter <code>k</code>. 272 * @param s The curve parameter <code>s<sub>0</sub></code> or 273 * <code>s<sub>1</sub></code>. 274 * @param vm The Lucas Sequence element <code>V<sub>m</sub></code>. 275 * @param a The parameter <code>a</code> of the elliptic curve. 276 * @param m The bit length of the finite field 277 * <code><b>F</b><sub>m</sub></code>. 278 * @param c The number of bits of accuracy, i.e. the scale of the returned 279 * <code>SimpleBigDecimal</code>. 280 * @return The value <code>λ = s k / n</code> computed to 281 * <code>c</code> bits of accuracy. 282 */ 283 public static SimpleBigDecimal approximateDivisionByN(BigInteger k, 284 BigInteger s, BigInteger vm, byte a, int m, int c) 285 { 286 int _k = (m + 5)/2 + c; 287 BigInteger ns = k.shiftRight(m - _k - 2 + a); 288 289 BigInteger gs = s.multiply(ns); 290 291 BigInteger hs = gs.shiftRight(m); 292 293 BigInteger js = vm.multiply(hs); 294 295 BigInteger gsPlusJs = gs.add(js); 296 BigInteger ls = gsPlusJs.shiftRight(_k-c); 297 if (gsPlusJs.testBit(_k-c-1)) 298 { 299 // round up 300 ls = ls.add(ECConstants.ONE); 301 } 302 303 return new SimpleBigDecimal(ls, c); 304 } 305 306 /** 307 * Computes the <code>τ</code>-adic NAF (non-adjacent form) of an 308 * element <code>λ</code> of <code><b>Z</b>[τ]</code>. 309 * @param mu The parameter <code>μ</code> of the elliptic curve. 310 * @param lambda The element <code>λ</code> of 311 * <code><b>Z</b>[τ]</code>. 312 * @return The <code>τ</code>-adic NAF of <code>λ</code>. 313 */ 314 public static byte[] tauAdicNaf(byte mu, ZTauElement lambda) 315 { 316 if (!((mu == 1) || (mu == -1))) 317 { 318 throw new IllegalArgumentException("mu must be 1 or -1"); 319 } 320 321 BigInteger norm = norm(mu, lambda); 322 323 // Ceiling of log2 of the norm 324 int log2Norm = norm.bitLength(); 325 326 // If length(TNAF) > 30, then length(TNAF) < log2Norm + 3.52 327 int maxLength = log2Norm > 30 ? log2Norm + 4 : 34; 328 329 // The array holding the TNAF 330 byte[] u = new byte[maxLength]; 331 int i = 0; 332 333 // The actual length of the TNAF 334 int length = 0; 335 336 BigInteger r0 = lambda.u; 337 BigInteger r1 = lambda.v; 338 339 while(!((r0.equals(ECConstants.ZERO)) && (r1.equals(ECConstants.ZERO)))) 340 { 341 // If r0 is odd 342 if (r0.testBit(0)) 343 { 344 u[i] = (byte) ECConstants.TWO.subtract((r0.subtract(r1.shiftLeft(1))).mod(ECConstants.FOUR)).intValue(); 345 346 // r0 = r0 - u[i] 347 if (u[i] == 1) 348 { 349 r0 = r0.clearBit(0); 350 } 351 else 352 { 353 // u[i] == -1 354 r0 = r0.add(ECConstants.ONE); 355 } 356 length = i; 357 } 358 else 359 { 360 u[i] = 0; 361 } 362 363 BigInteger t = r0; 364 BigInteger s = r0.shiftRight(1); 365 if (mu == 1) 366 { 367 r0 = r1.add(s); 368 } 369 else 370 { 371 // mu == -1 372 r0 = r1.subtract(s); 373 } 374 375 r1 = t.shiftRight(1).negate(); 376 i++; 377 } 378 379 length++; 380 381 // Reduce the TNAF array to its actual length 382 byte[] tnaf = new byte[length]; 383 System.arraycopy(u, 0, tnaf, 0, length); 384 return tnaf; 385 } 386 387 /** 388 * Applies the operation <code>τ()</code> to an 389 * <code>ECPoint.AbstractF2m</code>. 390 * @param p The ECPoint.AbstractF2m to which <code>τ()</code> is applied. 391 * @return <code>τ(p)</code> 392 */ 393 public static ECPoint.AbstractF2m tau(ECPoint.AbstractF2m p) 394 { 395 return p.tau(); 396 } 397 398 /** 399 * Returns the parameter <code>μ</code> of the elliptic curve. 400 * @param curve The elliptic curve from which to obtain <code>μ</code>. 401 * The curve must be a Koblitz curve, i.e. <code>a</code> equals 402 * <code>0</code> or <code>1</code> and <code>b</code> equals 403 * <code>1</code>. 404 * @return <code>μ</code> of the elliptic curve. 405 * @throws IllegalArgumentException if the given ECCurve is not a Koblitz 406 * curve. 407 */ 408 public static byte getMu(ECCurve.AbstractF2m curve) 409 { 410 if (!curve.isKoblitz()) 411 { 412 throw new IllegalArgumentException("No Koblitz curve (ABC), TNAF multiplication not possible"); 413 } 414 415 if (curve.getA().isZero()) 416 { 417 return -1; 418 } 419 420 return 1; 421 } 422 423 public static byte getMu(ECFieldElement curveA) 424 { 425 return (byte)(curveA.isZero() ? -1 : 1); 426 } 427 428 public static byte getMu(int curveA) 429 { 430 return (byte)(curveA == 0 ? -1 : 1); 431 } 432 433 /** 434 * Calculates the Lucas Sequence elements <code>U<sub>k-1</sub></code> and 435 * <code>U<sub>k</sub></code> or <code>V<sub>k-1</sub></code> and 436 * <code>V<sub>k</sub></code>. 437 * @param mu The parameter <code>μ</code> of the elliptic curve. 438 * @param k The index of the second element of the Lucas Sequence to be 439 * returned. 440 * @param doV If set to true, computes <code>V<sub>k-1</sub></code> and 441 * <code>V<sub>k</sub></code>, otherwise <code>U<sub>k-1</sub></code> and 442 * <code>U<sub>k</sub></code>. 443 * @return An array with 2 elements, containing <code>U<sub>k-1</sub></code> 444 * and <code>U<sub>k</sub></code> or <code>V<sub>k-1</sub></code> 445 * and <code>V<sub>k</sub></code>. 446 */ 447 public static BigInteger[] getLucas(byte mu, int k, boolean doV) 448 { 449 if (!((mu == 1) || (mu == -1))) 450 { 451 throw new IllegalArgumentException("mu must be 1 or -1"); 452 } 453 454 BigInteger u0; 455 BigInteger u1; 456 BigInteger u2; 457 458 if (doV) 459 { 460 u0 = ECConstants.TWO; 461 u1 = BigInteger.valueOf(mu); 462 } 463 else 464 { 465 u0 = ECConstants.ZERO; 466 u1 = ECConstants.ONE; 467 } 468 469 for (int i = 1; i < k; i++) 470 { 471 // u2 = mu*u1 - 2*u0; 472 BigInteger s = null; 473 if (mu == 1) 474 { 475 s = u1; 476 } 477 else 478 { 479 // mu == -1 480 s = u1.negate(); 481 } 482 483 u2 = s.subtract(u0.shiftLeft(1)); 484 u0 = u1; 485 u1 = u2; 486// System.out.println(i + ": " + u2); 487// System.out.println(); 488 } 489 490 BigInteger[] retVal = {u0, u1}; 491 return retVal; 492 } 493 494 /** 495 * Computes the auxiliary value <code>t<sub>w</sub></code>. If the width is 496 * 4, then for <code>mu = 1</code>, <code>t<sub>w</sub> = 6</code> and for 497 * <code>mu = -1</code>, <code>t<sub>w</sub> = 10</code> 498 * @param mu The parameter <code>μ</code> of the elliptic curve. 499 * @param w The window width of the WTNAF. 500 * @return the auxiliary value <code>t<sub>w</sub></code> 501 */ 502 public static BigInteger getTw(byte mu, int w) 503 { 504 if (w == 4) 505 { 506 if (mu == 1) 507 { 508 return BigInteger.valueOf(6); 509 } 510 else 511 { 512 // mu == -1 513 return BigInteger.valueOf(10); 514 } 515 } 516 else 517 { 518 // For w <> 4, the values must be computed 519 BigInteger[] us = getLucas(mu, w, false); 520 BigInteger twoToW = ECConstants.ZERO.setBit(w); 521 BigInteger u1invert = us[1].modInverse(twoToW); 522 BigInteger tw; 523 tw = ECConstants.TWO.multiply(us[0]).multiply(u1invert).mod(twoToW); 524// System.out.println("mu = " + mu); 525// System.out.println("tw = " + tw); 526 return tw; 527 } 528 } 529 530 /** 531 * Computes the auxiliary values <code>s<sub>0</sub></code> and 532 * <code>s<sub>1</sub></code> used for partial modular reduction. 533 * @param curve The elliptic curve for which to compute 534 * <code>s<sub>0</sub></code> and <code>s<sub>1</sub></code>. 535 * @throws IllegalArgumentException if <code>curve</code> is not a 536 * Koblitz curve (Anomalous Binary Curve, ABC). 537 */ 538 public static BigInteger[] getSi(ECCurve.AbstractF2m curve) 539 { 540 if (!curve.isKoblitz()) 541 { 542 throw new IllegalArgumentException("si is defined for Koblitz curves only"); 543 } 544 545 int m = curve.getFieldSize(); 546 int a = curve.getA().toBigInteger().intValue(); 547 byte mu = getMu(a); 548 int shifts = getShiftsForCofactor(curve.getCofactor()); 549 int index = m + 3 - a; 550 BigInteger[] ui = getLucas(mu, index, false); 551 if (mu == 1) 552 { 553 ui[0] = ui[0].negate(); 554 ui[1] = ui[1].negate(); 555 } 556 557 BigInteger dividend0 = ECConstants.ONE.add(ui[1]).shiftRight(shifts); 558 BigInteger dividend1 = ECConstants.ONE.add(ui[0]).shiftRight(shifts).negate(); 559 560 return new BigInteger[] { dividend0, dividend1 }; 561 } 562 563 public static BigInteger[] getSi(int fieldSize, int curveA, BigInteger cofactor) 564 { 565 byte mu = getMu(curveA); 566 int shifts = getShiftsForCofactor(cofactor); 567 int index = fieldSize + 3 - curveA; 568 BigInteger[] ui = getLucas(mu, index, false); 569 if (mu == 1) 570 { 571 ui[0] = ui[0].negate(); 572 ui[1] = ui[1].negate(); 573 } 574 575 BigInteger dividend0 = ECConstants.ONE.add(ui[1]).shiftRight(shifts); 576 BigInteger dividend1 = ECConstants.ONE.add(ui[0]).shiftRight(shifts).negate(); 577 578 return new BigInteger[] { dividend0, dividend1 }; 579 } 580 581 protected static int getShiftsForCofactor(BigInteger h) 582 { 583 if (h != null) 584 { 585 if (h.equals(ECConstants.TWO)) 586 { 587 return 1; 588 } 589 if (h.equals(ECConstants.FOUR)) 590 { 591 return 2; 592 } 593 } 594 595 throw new IllegalArgumentException("h (Cofactor) must be 2 or 4"); 596 } 597 598 /** 599 * Partial modular reduction modulo 600 * <code>(τ<sup>m</sup> - 1)/(τ - 1)</code>. 601 * @param k The integer to be reduced. 602 * @param m The bitlength of the underlying finite field. 603 * @param a The parameter <code>a</code> of the elliptic curve. 604 * @param s The auxiliary values <code>s<sub>0</sub></code> and 605 * <code>s<sub>1</sub></code>. 606 * @param mu The parameter μ of the elliptic curve. 607 * @param c The precision (number of bits of accuracy) of the partial 608 * modular reduction. 609 * @return <code>ρ := k partmod (τ<sup>m</sup> - 1)/(τ - 1)</code> 610 */ 611 public static ZTauElement partModReduction(BigInteger k, int m, byte a, 612 BigInteger[] s, byte mu, byte c) 613 { 614 // d0 = s[0] + mu*s[1]; mu is either 1 or -1 615 BigInteger d0; 616 if (mu == 1) 617 { 618 d0 = s[0].add(s[1]); 619 } 620 else 621 { 622 d0 = s[0].subtract(s[1]); 623 } 624 625 BigInteger[] v = getLucas(mu, m, true); 626 BigInteger vm = v[1]; 627 628 SimpleBigDecimal lambda0 = approximateDivisionByN( 629 k, s[0], vm, a, m, c); 630 631 SimpleBigDecimal lambda1 = approximateDivisionByN( 632 k, s[1], vm, a, m, c); 633 634 ZTauElement q = round(lambda0, lambda1, mu); 635 636 // r0 = n - d0*q0 - 2*s1*q1 637 BigInteger r0 = k.subtract(d0.multiply(q.u)).subtract( 638 BigInteger.valueOf(2).multiply(s[1]).multiply(q.v)); 639 640 // r1 = s1*q0 - s0*q1 641 BigInteger r1 = s[1].multiply(q.u).subtract(s[0].multiply(q.v)); 642 643 return new ZTauElement(r0, r1); 644 } 645 646 /** 647 * Multiplies a {@link org.bouncycastle.math.ec.ECPoint.AbstractF2m ECPoint.AbstractF2m} 648 * by a <code>BigInteger</code> using the reduced <code>τ</code>-adic 649 * NAF (RTNAF) method. 650 * @param p The ECPoint.AbstractF2m to multiply. 651 * @param k The <code>BigInteger</code> by which to multiply <code>p</code>. 652 * @return <code>k * p</code> 653 */ 654 public static ECPoint.AbstractF2m multiplyRTnaf(ECPoint.AbstractF2m p, BigInteger k) 655 { 656 ECCurve.AbstractF2m curve = (ECCurve.AbstractF2m) p.getCurve(); 657 int m = curve.getFieldSize(); 658 int a = curve.getA().toBigInteger().intValue(); 659 byte mu = getMu(a); 660 BigInteger[] s = curve.getSi(); 661 ZTauElement rho = partModReduction(k, m, (byte)a, s, mu, (byte)10); 662 663 return multiplyTnaf(p, rho); 664 } 665 666 /** 667 * Multiplies a {@link org.bouncycastle.math.ec.ECPoint.AbstractF2m ECPoint.AbstractF2m} 668 * by an element <code>λ</code> of <code><b>Z</b>[τ]</code> 669 * using the <code>τ</code>-adic NAF (TNAF) method. 670 * @param p The ECPoint.AbstractF2m to multiply. 671 * @param lambda The element <code>λ</code> of 672 * <code><b>Z</b>[τ]</code>. 673 * @return <code>λ * p</code> 674 */ 675 public static ECPoint.AbstractF2m multiplyTnaf(ECPoint.AbstractF2m p, ZTauElement lambda) 676 { 677 ECCurve.AbstractF2m curve = (ECCurve.AbstractF2m)p.getCurve(); 678 byte mu = getMu(curve.getA()); 679 byte[] u = tauAdicNaf(mu, lambda); 680 681 ECPoint.AbstractF2m q = multiplyFromTnaf(p, u); 682 683 return q; 684 } 685 686 /** 687 * Multiplies a {@link org.bouncycastle.math.ec.ECPoint.AbstractF2m ECPoint.AbstractF2m} 688 * by an element <code>λ</code> of <code><b>Z</b>[τ]</code> 689 * using the <code>τ</code>-adic NAF (TNAF) method, given the TNAF 690 * of <code>λ</code>. 691 * @param p The ECPoint.AbstractF2m to multiply. 692 * @param u The the TNAF of <code>λ</code>.. 693 * @return <code>λ * p</code> 694 */ 695 public static ECPoint.AbstractF2m multiplyFromTnaf(ECPoint.AbstractF2m p, byte[] u) 696 { 697 ECCurve curve = p.getCurve(); 698 ECPoint.AbstractF2m q = (ECPoint.AbstractF2m)curve.getInfinity(); 699 ECPoint.AbstractF2m pNeg = (ECPoint.AbstractF2m)p.negate(); 700 int tauCount = 0; 701 for (int i = u.length - 1; i >= 0; i--) 702 { 703 ++tauCount; 704 byte ui = u[i]; 705 if (ui != 0) 706 { 707 q = q.tauPow(tauCount); 708 tauCount = 0; 709 710 ECPoint x = ui > 0 ? p : pNeg; 711 q = (ECPoint.AbstractF2m)q.add(x); 712 } 713 } 714 if (tauCount > 0) 715 { 716 q = q.tauPow(tauCount); 717 } 718 return q; 719 } 720 721 /** 722 * Computes the <code>[τ]</code>-adic window NAF of an element 723 * <code>λ</code> of <code><b>Z</b>[τ]</code>. 724 * @param mu The parameter μ of the elliptic curve. 725 * @param lambda The element <code>λ</code> of 726 * <code><b>Z</b>[τ]</code> of which to compute the 727 * <code>[τ]</code>-adic NAF. 728 * @param width The window width of the resulting WNAF. 729 * @param pow2w 2<sup>width</sup>. 730 * @param tw The auxiliary value <code>t<sub>w</sub></code>. 731 * @param alpha The <code>α<sub>u</sub></code>'s for the window width. 732 * @return The <code>[τ]</code>-adic window NAF of 733 * <code>λ</code>. 734 */ 735 public static byte[] tauAdicWNaf(byte mu, ZTauElement lambda, 736 byte width, BigInteger pow2w, BigInteger tw, ZTauElement[] alpha) 737 { 738 if (!((mu == 1) || (mu == -1))) 739 { 740 throw new IllegalArgumentException("mu must be 1 or -1"); 741 } 742 743 BigInteger norm = norm(mu, lambda); 744 745 // Ceiling of log2 of the norm 746 int log2Norm = norm.bitLength(); 747 748 // If length(TNAF) > 30, then length(TNAF) < log2Norm + 3.52 749 int maxLength = log2Norm > 30 ? log2Norm + 4 + width : 34 + width; 750 751 // The array holding the TNAF 752 byte[] u = new byte[maxLength]; 753 754 // 2^(width - 1) 755 BigInteger pow2wMin1 = pow2w.shiftRight(1); 756 757 // Split lambda into two BigIntegers to simplify calculations 758 BigInteger r0 = lambda.u; 759 BigInteger r1 = lambda.v; 760 int i = 0; 761 762 // while lambda <> (0, 0) 763 while (!((r0.equals(ECConstants.ZERO))&&(r1.equals(ECConstants.ZERO)))) 764 { 765 // if r0 is odd 766 if (r0.testBit(0)) 767 { 768 // uUnMod = r0 + r1*tw mod 2^width 769 BigInteger uUnMod 770 = r0.add(r1.multiply(tw)).mod(pow2w); 771 772 byte uLocal; 773 // if uUnMod >= 2^(width - 1) 774 if (uUnMod.compareTo(pow2wMin1) >= 0) 775 { 776 uLocal = (byte) uUnMod.subtract(pow2w).intValue(); 777 } 778 else 779 { 780 uLocal = (byte) uUnMod.intValue(); 781 } 782 // uLocal is now in [-2^(width-1), 2^(width-1)-1] 783 784 u[i] = uLocal; 785 boolean s = true; 786 if (uLocal < 0) 787 { 788 s = false; 789 uLocal = (byte)-uLocal; 790 } 791 // uLocal is now >= 0 792 793 if (s) 794 { 795 r0 = r0.subtract(alpha[uLocal].u); 796 r1 = r1.subtract(alpha[uLocal].v); 797 } 798 else 799 { 800 r0 = r0.add(alpha[uLocal].u); 801 r1 = r1.add(alpha[uLocal].v); 802 } 803 } 804 else 805 { 806 u[i] = 0; 807 } 808 809 BigInteger t = r0; 810 811 if (mu == 1) 812 { 813 r0 = r1.add(r0.shiftRight(1)); 814 } 815 else 816 { 817 // mu == -1 818 r0 = r1.subtract(r0.shiftRight(1)); 819 } 820 r1 = t.shiftRight(1).negate(); 821 i++; 822 } 823 return u; 824 } 825 826 /** 827 * Does the precomputation for WTNAF multiplication. 828 * @param p The <code>ECPoint</code> for which to do the precomputation. 829 * @param a The parameter <code>a</code> of the elliptic curve. 830 * @return The precomputation array for <code>p</code>. 831 */ 832 public static ECPoint.AbstractF2m[] getPreComp(ECPoint.AbstractF2m p, byte a) 833 { 834 byte[][] alphaTnaf = (a == 0) ? Tnaf.alpha0Tnaf : Tnaf.alpha1Tnaf; 835 836 ECPoint.AbstractF2m[] pu = new ECPoint.AbstractF2m[(alphaTnaf.length + 1) >>> 1]; 837 pu[0] = p; 838 839 int precompLen = alphaTnaf.length; 840 for (int i = 3; i < precompLen; i += 2) 841 { 842 pu[i >>> 1] = Tnaf.multiplyFromTnaf(p, alphaTnaf[i]); 843 } 844 845 p.getCurve().normalizeAll(pu); 846 847 return pu; 848 } 849} 850