1 package org.bouncycastle.math.ec; 2 3 import java.math.BigInteger; 4 5 /** 6 * Class implementing the WNAF (Window Non-Adjacent Form) multiplication 7 * algorithm. 8 */ 9 public class WNafL2RMultiplier extends AbstractECMultiplier 10 { 11 /** 12 * Multiplies <code>this</code> by an integer <code>k</code> using the 13 * Window NAF method. 14 * @param k The integer by which <code>this</code> is multiplied. 15 * @return A new <code>ECPoint</code> which equals <code>this</code> 16 * multiplied by <code>k</code>. 17 */ multiplyPositive(ECPoint p, BigInteger k)18 protected ECPoint multiplyPositive(ECPoint p, BigInteger k) 19 { 20 // Clamp the window width in the range [2, 16] 21 int width = Math.max(2, Math.min(16, getWindowSize(k.bitLength()))); 22 23 WNafPreCompInfo wnafPreCompInfo = WNafUtil.precompute(p, width, true); 24 ECPoint[] preComp = wnafPreCompInfo.getPreComp(); 25 ECPoint[] preCompNeg = wnafPreCompInfo.getPreCompNeg(); 26 27 int[] wnaf = WNafUtil.generateCompactWindowNaf(width, k); 28 29 ECPoint R = p.getCurve().getInfinity(); 30 31 int i = wnaf.length; 32 33 /* 34 * NOTE This code optimizes the first window using the precomputed points to substitute an 35 * addition for 2 or more doublings. 36 */ 37 if (i > 1) 38 { 39 int wi = wnaf[--i]; 40 int digit = wi >> 16, zeroes = wi & 0xFFFF; 41 42 int n = Math.abs(digit); 43 ECPoint[] table = digit < 0 ? preCompNeg : preComp; 44 45 /* 46 * NOTE: We use this optimization conservatively, since some coordinate systems have 47 * significantly cheaper doubling relative to addition. 48 * 49 * (n << 2) selects precomputed values in the lower half of the table 50 * (n << 3) selects precomputed values in the lower quarter of the table 51 */ 52 //if ((n << 2) < (1 << width)) 53 if ((n << 3) < (1 << width)) 54 { 55 int highest = LongArray.bitLengths[n]; 56 int lowBits = n ^ (1 << (highest - 1)); 57 int scale = width - highest; 58 59 int i1 = ((1 << (width - 1)) - 1); 60 int i2 = (lowBits << scale) + 1; 61 R = table[i1 >>> 1].add(table[i2 >>> 1]); 62 63 zeroes -= scale; 64 65 // System.out.println("Optimized: 2^" + scale + " * " + n + " = " + i1 + " + " + i2); 66 } 67 else 68 { 69 R = table[n >>> 1]; 70 } 71 72 R = R.timesPow2(zeroes); 73 } 74 75 while (i > 0) 76 { 77 int wi = wnaf[--i]; 78 int digit = wi >> 16, zeroes = wi & 0xFFFF; 79 80 int n = Math.abs(digit); 81 ECPoint[] table = digit < 0 ? preCompNeg : preComp; 82 ECPoint r = table[n >>> 1]; 83 84 R = R.twicePlus(r); 85 R = R.timesPow2(zeroes); 86 } 87 88 return R; 89 } 90 91 /** 92 * Determine window width to use for a scalar multiplication of the given size. 93 * 94 * @param bits the bit-length of the scalar to multiply by 95 * @return the window size to use 96 */ getWindowSize(int bits)97 protected int getWindowSize(int bits) 98 { 99 return WNafUtil.getWindowSize(bits); 100 } 101 } 102