180261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giropackage org.bouncycastle.math.ec; 280261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 380261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giroimport java.math.BigInteger; 480261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 580261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giropublic abstract class WNafUtil 680261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro{ 753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro public static final String PRECOMP_NAME = "bc_wnaf"; 853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro private static final int[] DEFAULT_WINDOW_SIZE_CUTOFFS = new int[]{ 13, 41, 121, 337, 897, 2305 }; 1053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 1153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro private static final byte[] EMPTY_BYTES = new byte[0]; 1253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro private static final int[] EMPTY_INTS = new int[0]; 1353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro private static final ECPoint[] EMPTY_POINTS = new ECPoint[0]; 1480261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 1580261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro public static int[] generateCompactNaf(BigInteger k) 1680261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 1780261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro if ((k.bitLength() >>> 16) != 0) 1880261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 1980261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro throw new IllegalArgumentException("'k' must have bitlength < 2^16"); 2080261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 2153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro if (k.signum() == 0) 2253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 2353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro return EMPTY_INTS; 2453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 2580261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 2680261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro BigInteger _3k = k.shiftLeft(1).add(k); 2780261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 2853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro int bits = _3k.bitLength(); 2953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro int[] naf = new int[bits >> 1]; 3080261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 3153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro BigInteger diff = _3k.xor(k); 3280261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 3353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro int highBit = bits - 1, length = 0, zeroes = 0; 3453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro for (int i = 1; i < highBit; ++i) 3553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 3653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro if (!diff.testBit(i)) 3780261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 3880261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro ++zeroes; 3953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro continue; 4080261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 4153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 4253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro int digit = k.testBit(i) ? -1 : 1; 4353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro naf[length++] = (digit << 16) | zeroes; 4453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro zeroes = 1; 4553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro ++i; 4680261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 4780261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 4853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro naf[length++] = (1 << 16) | zeroes; 4953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 5080261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro if (naf.length > length) 5180261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 5280261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro naf = trim(naf, length); 5380261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 5480261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 5580261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro return naf; 5680261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 5780261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 5880261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro public static int[] generateCompactWindowNaf(int width, BigInteger k) 5980261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 6080261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro if (width == 2) 6180261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 6280261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro return generateCompactNaf(k); 6380261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 6480261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 6580261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro if (width < 2 || width > 16) 6680261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 6780261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro throw new IllegalArgumentException("'width' must be in the range [2, 16]"); 6880261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 6980261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro if ((k.bitLength() >>> 16) != 0) 7080261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 7180261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro throw new IllegalArgumentException("'k' must have bitlength < 2^16"); 7280261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 7353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro if (k.signum() == 0) 7453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 7553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro return EMPTY_INTS; 7653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 7780261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 7880261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro int[] wnaf = new int[k.bitLength() / width + 1]; 7980261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 8080261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro // 2^width and a mask and sign bit set accordingly 8180261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro int pow2 = 1 << width; 8280261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro int mask = pow2 - 1; 8380261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro int sign = pow2 >>> 1; 8480261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 8580261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro boolean carry = false; 8680261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro int length = 0, pos = 0; 8780261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 8880261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro while (pos <= k.bitLength()) 8980261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 9080261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro if (k.testBit(pos) == carry) 9180261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 9280261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro ++pos; 9380261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro continue; 9480261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 9580261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 9680261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro k = k.shiftRight(pos); 9780261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 9880261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro int digit = k.intValue() & mask; 9980261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro if (carry) 10080261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 10180261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro ++digit; 10280261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 10380261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 10480261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro carry = (digit & sign) != 0; 10580261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro if (carry) 10680261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 10780261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro digit -= pow2; 10880261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 10980261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 11080261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro int zeroes = length > 0 ? pos - 1 : pos; 11180261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro wnaf[length++] = (digit << 16) | zeroes; 11280261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro pos = width; 11380261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 11480261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 11580261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro // Reduce the WNAF array to its actual length 11680261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro if (wnaf.length > length) 11780261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 11880261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro wnaf = trim(wnaf, length); 11980261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 12080261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 12180261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro return wnaf; 12280261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 12380261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 12480261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro public static byte[] generateJSF(BigInteger g, BigInteger h) 12580261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 12680261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro int digits = Math.max(g.bitLength(), h.bitLength()) + 1; 12780261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro byte[] jsf = new byte[digits]; 12880261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 12980261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro BigInteger k0 = g, k1 = h; 13080261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro int j = 0, d0 = 0, d1 = 0; 13180261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 13253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro int offset = 0; 13353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro while ((d0 | d1) != 0 || k0.bitLength() > offset || k1.bitLength() > offset) 13480261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 13553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro int n0 = ((k0.intValue() >>> offset) + d0) & 7, n1 = ((k1.intValue() >>> offset) + d1) & 7; 13680261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 13780261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro int u0 = n0 & 1; 13880261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro if (u0 != 0) 13980261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 14080261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro u0 -= (n0 & 2); 14180261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro if ((n0 + u0) == 4 && (n1 & 3) == 2) 14280261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 14380261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro u0 = -u0; 14480261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 14580261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 14680261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 14780261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro int u1 = n1 & 1; 14880261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro if (u1 != 0) 14980261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 15080261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro u1 -= (n1 & 2); 15180261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro if ((n1 + u1) == 4 && (n0 & 3) == 2) 15280261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 15380261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro u1 = -u1; 15480261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 15580261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 15680261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 15780261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro if ((d0 << 1) == 1 + u0) 15880261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 15953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro d0 ^= 1; 16080261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 16180261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro if ((d1 << 1) == 1 + u1) 16280261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 16353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro d1 ^= 1; 16480261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 16580261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 16653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro if (++offset == 30) 16753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 16853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro offset = 0; 16953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro k0 = k0.shiftRight(30); 17053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro k1 = k1.shiftRight(30); 17153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 17280261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 17380261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro jsf[j++] = (byte)((u0 << 4) | (u1 & 0xF)); 17480261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 17580261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 17680261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro // Reduce the JSF array to its actual length 17780261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro if (jsf.length > j) 17880261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 17980261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro jsf = trim(jsf, j); 18080261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 18180261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 18280261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro return jsf; 18380261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 18480261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 18580261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro public static byte[] generateNaf(BigInteger k) 18680261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 18753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro if (k.signum() == 0) 18853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 18953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro return EMPTY_BYTES; 19053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 19153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 19280261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro BigInteger _3k = k.shiftLeft(1).add(k); 19380261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 19480261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro int digits = _3k.bitLength() - 1; 19580261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro byte[] naf = new byte[digits]; 19680261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 19753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro BigInteger diff = _3k.xor(k); 19880261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 19953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro for (int i = 1; i < digits; ++i) 20053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 20153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro if (diff.testBit(i)) 20253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 20353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro naf[i - 1] = (byte)(k.testBit(i) ? -1 : 1); 20453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro ++i; 20553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 20680261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 20780261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 20853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro naf[digits - 1] = 1; 20953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 21080261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro return naf; 21180261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 21280261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 21380261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro /** 21480261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro * Computes the Window NAF (non-adjacent Form) of an integer. 21580261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro * @param width The width <code>w</code> of the Window NAF. The width is 21680261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro * defined as the minimal number <code>w</code>, such that for any 21780261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro * <code>w</code> consecutive digits in the resulting representation, at 21880261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro * most one is non-zero. 21980261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro * @param k The integer of which the Window NAF is computed. 22080261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro * @return The Window NAF of the given width, such that the following holds: 22180261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro * <code>k = ∑<sub>i=0</sub><sup>l-1</sup> k<sub>i</sub>2<sup>i</sup> 22280261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro * </code>, where the <code>k<sub>i</sub></code> denote the elements of the 22380261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro * returned <code>byte[]</code>. 22480261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro */ 22580261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro public static byte[] generateWindowNaf(int width, BigInteger k) 22680261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 22780261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro if (width == 2) 22880261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 22980261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro return generateNaf(k); 23080261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 23180261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 23280261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro if (width < 2 || width > 8) 23380261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 23480261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro throw new IllegalArgumentException("'width' must be in the range [2, 8]"); 23580261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 23653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro if (k.signum() == 0) 23753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 23853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro return EMPTY_BYTES; 23953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 24080261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 24180261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro byte[] wnaf = new byte[k.bitLength() + 1]; 24280261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 24380261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro // 2^width and a mask and sign bit set accordingly 24480261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro int pow2 = 1 << width; 24580261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro int mask = pow2 - 1; 24680261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro int sign = pow2 >>> 1; 24780261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 24880261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro boolean carry = false; 24980261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro int length = 0, pos = 0; 25080261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 25180261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro while (pos <= k.bitLength()) 25280261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 25380261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro if (k.testBit(pos) == carry) 25480261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 25580261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro ++pos; 25680261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro continue; 25780261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 25880261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 25980261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro k = k.shiftRight(pos); 26080261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 26180261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro int digit = k.intValue() & mask; 26280261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro if (carry) 26380261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 26480261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro ++digit; 26580261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 26680261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 26780261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro carry = (digit & sign) != 0; 26880261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro if (carry) 26980261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 27080261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro digit -= pow2; 27180261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 27280261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 27380261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro length += (length > 0) ? pos - 1 : pos; 27480261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro wnaf[length++] = (byte)digit; 27580261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro pos = width; 27680261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 27780261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 27880261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro // Reduce the WNAF array to its actual length 27980261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro if (wnaf.length > length) 28080261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 28180261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro wnaf = trim(wnaf, length); 28280261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 28380261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 28480261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro return wnaf; 28580261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 28680261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 28753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro public static int getNafWeight(BigInteger k) 28853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 28953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro if (k.signum() == 0) 29053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 29153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro return 0; 29253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 29353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 29453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro BigInteger _3k = k.shiftLeft(1).add(k); 29553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro BigInteger diff = _3k.xor(k); 29653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 29753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro return diff.bitCount(); 29853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 29953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 30053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro public static WNafPreCompInfo getWNafPreCompInfo(ECPoint p) 30153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 30253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro return getWNafPreCompInfo(p.getCurve().getPreCompInfo(p, PRECOMP_NAME)); 30353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 30453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 30580261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro public static WNafPreCompInfo getWNafPreCompInfo(PreCompInfo preCompInfo) 30680261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 30780261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro if ((preCompInfo != null) && (preCompInfo instanceof WNafPreCompInfo)) 30880261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 30980261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro return (WNafPreCompInfo)preCompInfo; 31080261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 31180261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 31280261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro return new WNafPreCompInfo(); 31380261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 31480261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 31580261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro /** 31680261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro * Determine window width to use for a scalar multiplication of the given size. 31780261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro * 31880261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro * @param bits the bit-length of the scalar to multiply by 31980261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro * @return the window size to use 32080261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro */ 32180261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro public static int getWindowSize(int bits) 32280261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 32380261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro return getWindowSize(bits, DEFAULT_WINDOW_SIZE_CUTOFFS); 32480261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 32580261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 32680261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro /** 32780261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro * Determine window width to use for a scalar multiplication of the given size. 32880261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro * 32980261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro * @param bits the bit-length of the scalar to multiply by 33080261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro * @param windowSizeCutoffs a monotonically increasing list of bit sizes at which to increment the window width 33180261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro * @return the window size to use 33280261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro */ 33380261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro public static int getWindowSize(int bits, int[] windowSizeCutoffs) 33480261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 33580261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro int w = 0; 33680261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro for (; w < windowSizeCutoffs.length; ++w) 33780261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 33880261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro if (bits < windowSizeCutoffs[w]) 33980261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 34080261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro break; 34180261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 34280261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 34380261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro return w + 2; 34480261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 34580261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 34653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro public static ECPoint mapPointWithPrecomp(ECPoint p, int width, boolean includeNegated, 34753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro ECPointMap pointMap) 34880261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 34980261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro ECCurve c = p.getCurve(); 35053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro WNafPreCompInfo wnafPreCompP = precompute(p, width, includeNegated); 35180261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 35253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro ECPoint q = pointMap.map(p); 35353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro WNafPreCompInfo wnafPreCompQ = getWNafPreCompInfo(c.getPreCompInfo(q, PRECOMP_NAME)); 35453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 35553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro ECPoint twiceP = wnafPreCompP.getTwice(); 35653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro if (twiceP != null) 35780261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 35853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro ECPoint twiceQ = pointMap.map(twiceP); 35953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro wnafPreCompQ.setTwice(twiceQ); 36080261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 36180261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 36253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro ECPoint[] preCompP = wnafPreCompP.getPreComp(); 36353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro ECPoint[] preCompQ = new ECPoint[preCompP.length]; 36453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro for (int i = 0; i < preCompP.length; ++i) 36553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 36653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro preCompQ[i] = pointMap.map(preCompP[i]); 36753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 36853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro wnafPreCompQ.setPreComp(preCompQ); 36980261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 37053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro if (includeNegated) 37180261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 37253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro ECPoint[] preCompNegQ = new ECPoint[preCompQ.length]; 37353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro for (int i = 0; i < preCompNegQ.length; ++i) 37480261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 37553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro preCompNegQ[i] = preCompQ[i].negate(); 37680261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 37753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro wnafPreCompQ.setPreCompNeg(preCompNegQ); 37853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 37980261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 38053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro c.setPreCompInfo(q, PRECOMP_NAME, wnafPreCompQ); 38153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 38253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro return q; 38353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 38453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 38553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro public static WNafPreCompInfo precompute(ECPoint p, int width, boolean includeNegated) 38653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 38753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro ECCurve c = p.getCurve(); 38853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro WNafPreCompInfo wnafPreCompInfo = getWNafPreCompInfo(c.getPreCompInfo(p, PRECOMP_NAME)); 38953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 39053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro int iniPreCompLen = 0, reqPreCompLen = 1 << Math.max(0, width - 2); 39153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 39253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro ECPoint[] preComp = wnafPreCompInfo.getPreComp(); 39353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro if (preComp == null) 39453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 39553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro preComp = EMPTY_POINTS; 39653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 39753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro else 39853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 39953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro iniPreCompLen = preComp.length; 40053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 40153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 40253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro if (iniPreCompLen < reqPreCompLen) 40353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 40480261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro preComp = resizeTable(preComp, reqPreCompLen); 40580261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 40653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro if (reqPreCompLen == 1) 40780261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 40853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro preComp[0] = p.normalize(); 40953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 41053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro else 41153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 41253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro int curPreCompLen = iniPreCompLen; 41353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro if (curPreCompLen == 0) 41453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 41553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro preComp[0] = p; 41653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro curPreCompLen = 1; 41753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 41853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 41953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro ECFieldElement iso = null; 42053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 42153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro if (reqPreCompLen == 2) 42253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 42353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro preComp[1] = p.threeTimes(); 42453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 42553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro else 42653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 42753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro ECPoint twiceP = wnafPreCompInfo.getTwice(), last = preComp[curPreCompLen - 1]; 42853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro if (twiceP == null) 42953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 43053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro twiceP = preComp[0].twice(); 43153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro wnafPreCompInfo.setTwice(twiceP); 43253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 43353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro /* 43453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro * For Fp curves with Jacobian projective coordinates, use a (quasi-)isomorphism 43553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro * where 'twiceP' is "affine", so that the subsequent additions are cheaper. This 43653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro * also requires scaling the initial point's X, Y coordinates, and reversing the 43753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro * isomorphism as part of the subsequent normalization. 43853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro * 43953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro * NOTE: The correctness of this optimization depends on: 44053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro * 1) additions do not use the curve's A, B coefficients. 44153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro * 2) no special cases (i.e. Q +/- Q) when calculating 1P, 3P, 5P, ... 44253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro */ 4434caba4cfca3316673ae4e330e8a47932bed8a53aSergio Giro if (!twiceP.isInfinity() && ECAlgorithms.isFpCurve(c) && c.getFieldSize() >= 64) 44453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 44553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro switch (c.getCoordinateSystem()) 44653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 44753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro case ECCurve.COORD_JACOBIAN: 44853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro case ECCurve.COORD_JACOBIAN_CHUDNOVSKY: 44953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro case ECCurve.COORD_JACOBIAN_MODIFIED: 45053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 45153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro iso = twiceP.getZCoord(0); 45253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro twiceP = c.createPoint(twiceP.getXCoord().toBigInteger(), twiceP.getYCoord() 45353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro .toBigInteger()); 45453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 45553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro ECFieldElement iso2 = iso.square(), iso3 = iso2.multiply(iso); 45653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro last = last.scaleX(iso2).scaleY(iso3); 45753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 45853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro if (iniPreCompLen == 0) 45953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 46053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro preComp[0] = last; 46153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 46253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro break; 46353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 46453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 46553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 46653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 46753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 46853b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro while (curPreCompLen < reqPreCompLen) 46953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro { 47053b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro /* 47153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro * Compute the new ECPoints for the precomputation array. The values 1, 3, 47253b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro * 5, ..., 2^(width-1)-1 times p are computed 47353b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro */ 47453b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro preComp[curPreCompLen++] = last = last.add(twiceP); 47553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 47653b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro } 47753b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro 47880261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro /* 47953b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro * Having oft-used operands in affine form makes operations faster. 48080261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro */ 48153b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro c.normalizeAll(preComp, iniPreCompLen, reqPreCompLen - iniPreCompLen, iso); 48280261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 48380261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 48480261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 48580261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro wnafPreCompInfo.setPreComp(preComp); 48680261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 48780261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro if (includeNegated) 48880261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 48980261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro ECPoint[] preCompNeg = wnafPreCompInfo.getPreCompNeg(); 49080261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 49180261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro int pos; 49280261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro if (preCompNeg == null) 49380261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 49480261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro pos = 0; 49580261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro preCompNeg = new ECPoint[reqPreCompLen]; 49680261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 49780261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro else 49880261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 49980261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro pos = preCompNeg.length; 50080261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro if (pos < reqPreCompLen) 50180261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 50280261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro preCompNeg = resizeTable(preCompNeg, reqPreCompLen); 50380261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 50480261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 50580261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 50680261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro while (pos < reqPreCompLen) 50780261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 50880261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro preCompNeg[pos] = preComp[pos].negate(); 50980261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro ++pos; 51080261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 51180261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 51280261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro wnafPreCompInfo.setPreCompNeg(preCompNeg); 51380261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 51480261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 51553b61f9fe9d58034fcc7021137e92460f91b70ceSergio Giro c.setPreCompInfo(p, PRECOMP_NAME, wnafPreCompInfo); 51680261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 51780261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro return wnafPreCompInfo; 51880261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 51980261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 52080261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro private static byte[] trim(byte[] a, int length) 52180261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 52280261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro byte[] result = new byte[length]; 52380261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro System.arraycopy(a, 0, result, 0, result.length); 52480261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro return result; 52580261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 52680261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 52780261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro private static int[] trim(int[] a, int length) 52880261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 52980261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro int[] result = new int[length]; 53080261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro System.arraycopy(a, 0, result, 0, result.length); 53180261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro return result; 53280261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 53380261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro 53480261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro private static ECPoint[] resizeTable(ECPoint[] a, int length) 53580261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro { 53680261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro ECPoint[] result = new ECPoint[length]; 53780261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro System.arraycopy(a, 0, result, 0, a.length); 53880261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro return result; 53980261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro } 54080261dd2d1824bb3862e90e77a5412d56ad88b1fSergio Giro} 541