15db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Rootpackage org.bouncycastle.math.ec; 25db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 35db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Rootimport java.math.BigInteger; 45db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 55db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root/** 65db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * Class implementing the WNAF (Window Non-Adjacent Form) multiplication 75db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * algorithm. 85db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root */ 95db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Rootpublic class WNafL2RMultiplier extends AbstractECMultiplier 105db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root{ 115db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root /** 125db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * Multiplies <code>this</code> by an integer <code>k</code> using the 135db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * Window NAF method. 145db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * @param k The integer by which <code>this</code> is multiplied. 155db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * @return A new <code>ECPoint</code> which equals <code>this</code> 165db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * multiplied by <code>k</code>. 175db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root */ 185db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root protected ECPoint multiplyPositive(ECPoint p, BigInteger k) 195db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 205db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root // Clamp the window width in the range [2, 16] 215db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int width = Math.max(2, Math.min(16, getWindowSize(k.bitLength()))); 225db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 235db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root WNafPreCompInfo wnafPreCompInfo = WNafUtil.precompute(p, width, true); 245db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root ECPoint[] preComp = wnafPreCompInfo.getPreComp(); 255db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root ECPoint[] preCompNeg = wnafPreCompInfo.getPreCompNeg(); 265db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 275db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int[] wnaf = WNafUtil.generateCompactWindowNaf(width, k); 285db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 295db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root ECPoint R = p.getCurve().getInfinity(); 305db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 315db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int i = wnaf.length; 325db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 335db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root /* 34d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root * NOTE: We try to optimize the first window using the precomputed points to substitute an 355db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * addition for 2 or more doublings. 365db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root */ 375db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root if (i > 1) 385db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 395db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int wi = wnaf[--i]; 405db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int digit = wi >> 16, zeroes = wi & 0xFFFF; 415db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 425db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int n = Math.abs(digit); 435db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root ECPoint[] table = digit < 0 ? preCompNeg : preComp; 445db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 45d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root // Optimization can only be used for values in the lower half of the table 46d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root if ((n << 2) < (1 << width)) 475db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 485db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int highest = LongArray.bitLengths[n]; 49d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root 50d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root // TODO Get addition/doubling cost ratio from curve and compare to 'scale' to see if worth substituting? 515db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int scale = width - highest; 52d001700a15b8bd733ae344c1fc315b97c43c6590Kenny Root int lowBits = n ^ (1 << (highest - 1)); 535db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 545db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int i1 = ((1 << (width - 1)) - 1); 555db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int i2 = (lowBits << scale) + 1; 565db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root R = table[i1 >>> 1].add(table[i2 >>> 1]); 575db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 585db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root zeroes -= scale; 595db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 605db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root// System.out.println("Optimized: 2^" + scale + " * " + n + " = " + i1 + " + " + i2); 615db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 625db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root else 635db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 645db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root R = table[n >>> 1]; 655db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 665db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 675db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root R = R.timesPow2(zeroes); 685db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 695db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 705db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root while (i > 0) 715db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 725db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int wi = wnaf[--i]; 735db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int digit = wi >> 16, zeroes = wi & 0xFFFF; 745db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 755db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root int n = Math.abs(digit); 765db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root ECPoint[] table = digit < 0 ? preCompNeg : preComp; 775db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root ECPoint r = table[n >>> 1]; 785db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 795db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root R = R.twicePlus(r); 805db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root R = R.timesPow2(zeroes); 815db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 825db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 835db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return R; 845db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 855db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root 865db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root /** 875db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * Determine window width to use for a scalar multiplication of the given size. 885db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * 895db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * @param bits the bit-length of the scalar to multiply by 905db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root * @return the window size to use 915db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root */ 925db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root protected int getWindowSize(int bits) 935db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root { 945db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root return WNafUtil.getWindowSize(bits); 955db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root } 965db505e1f6a68c8d5dfdb0fed0b8607dea7bed96Kenny Root} 97