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 class WNafMultiplier implements ECMultiplier 10 { 11 /** 12 * Computes the Window NAF (non-adjacent Form) of an integer. 13 * @param width The width <code>w</code> of the Window NAF. The width is 14 * defined as the minimal number <code>w</code>, such that for any 15 * <code>w</code> consecutive digits in the resulting representation, at 16 * most one is non-zero. 17 * @param k The integer of which the Window NAF is computed. 18 * @return The Window NAF of the given width, such that the following holds: 19 * <code>k = ∑<sub>i=0</sub><sup>l-1</sup> k<sub>i</sub>2<sup>i</sup> 20 * </code>, where the <code>k<sub>i</sub></code> denote the elements of the 21 * returned <code>byte[]</code>. 22 */ 23 public byte[] windowNaf(byte width, BigInteger k) 24 { 25 // The window NAF is at most 1 element longer than the binary 26 // representation of the integer k. byte can be used instead of short or 27 // int unless the window width is larger than 8. For larger width use 28 // short or int. However, a width of more than 8 is not efficient for 29 // m = log2(q) smaller than 2305 Bits. Note: Values for m larger than 30 // 1000 Bits are currently not used in practice. 31 byte[] wnaf = new byte[k.bitLength() + 1]; 32 33 // 2^width as short and BigInteger 34 short pow2wB = (short)(1 << width); 35 BigInteger pow2wBI = BigInteger.valueOf(pow2wB); 36 37 int i = 0; 38 39 // The actual length of the WNAF 40 int length = 0; 41 42 // while k >= 1 43 while (k.signum() > 0) 44 { 45 // if k is odd 46 if (k.testBit(0)) 47 { 48 // k mod 2^width 49 BigInteger remainder = k.mod(pow2wBI); 50 51 // if remainder > 2^(width - 1) - 1 52 if (remainder.testBit(width - 1)) 53 { 54 wnaf[i] = (byte)(remainder.intValue() - pow2wB); 55 } 56 else 57 { 58 wnaf[i] = (byte)remainder.intValue(); 59 } 60 // wnaf[i] is now in [-2^(width-1), 2^(width-1)-1] 61 62 k = k.subtract(BigInteger.valueOf(wnaf[i])); 63 length = i; 64 } 65 else 66 { 67 wnaf[i] = 0; 68 } 69 70 // k = k/2 71 k = k.shiftRight(1); 72 i++; 73 } 74 75 length++; 76 77 // Reduce the WNAF array to its actual length 78 byte[] wnafShort = new byte[length]; 79 System.arraycopy(wnaf, 0, wnafShort, 0, length); 80 return wnafShort; 81 } 82 83 /** 84 * Multiplies <code>this</code> by an integer <code>k</code> using the 85 * Window NAF method. 86 * @param k The integer by which <code>this</code> is multiplied. 87 * @return A new <code>ECPoint</code> which equals <code>this</code> 88 * multiplied by <code>k</code>. 89 */ 90 public ECPoint multiply(ECPoint p, BigInteger k, PreCompInfo preCompInfo) 91 { 92 WNafPreCompInfo wnafPreCompInfo; 93 94 if ((preCompInfo != null) && (preCompInfo instanceof WNafPreCompInfo)) 95 { 96 wnafPreCompInfo = (WNafPreCompInfo)preCompInfo; 97 } 98 else 99 { 100 // Ignore empty PreCompInfo or PreCompInfo of incorrect type 101 wnafPreCompInfo = new WNafPreCompInfo(); 102 } 103 104 // floor(log2(k)) 105 int m = k.bitLength(); 106 107 // width of the Window NAF 108 byte width; 109 110 // Required length of precomputation array 111 int reqPreCompLen; 112 113 // Determine optimal width and corresponding length of precomputation 114 // array based on literature values 115 if (m < 13) 116 { 117 width = 2; 118 reqPreCompLen = 1; 119 } 120 else 121 { 122 if (m < 41) 123 { 124 width = 3; 125 reqPreCompLen = 2; 126 } 127 else 128 { 129 if (m < 121) 130 { 131 width = 4; 132 reqPreCompLen = 4; 133 } 134 else 135 { 136 if (m < 337) 137 { 138 width = 5; 139 reqPreCompLen = 8; 140 } 141 else 142 { 143 if (m < 897) 144 { 145 width = 6; 146 reqPreCompLen = 16; 147 } 148 else 149 { 150 if (m < 2305) 151 { 152 width = 7; 153 reqPreCompLen = 32; 154 } 155 else 156 { 157 width = 8; 158 reqPreCompLen = 127; 159 } 160 } 161 } 162 } 163 } 164 } 165 166 // The length of the precomputation array 167 int preCompLen = 1; 168 169 ECPoint[] preComp = wnafPreCompInfo.getPreComp(); 170 ECPoint twiceP = wnafPreCompInfo.getTwiceP(); 171 172 // Check if the precomputed ECPoints already exist 173 if (preComp == null) 174 { 175 // Precomputation must be performed from scratch, create an empty 176 // precomputation array of desired length 177 preComp = new ECPoint[]{ p }; 178 } 179 else 180 { 181 // Take the already precomputed ECPoints to start with 182 preCompLen = preComp.length; 183 } 184 185 if (twiceP == null) 186 { 187 // Compute twice(p) 188 twiceP = p.twice(); 189 } 190 191 if (preCompLen < reqPreCompLen) 192 { 193 // Precomputation array must be made bigger, copy existing preComp 194 // array into the larger new preComp array 195 ECPoint[] oldPreComp = preComp; 196 preComp = new ECPoint[reqPreCompLen]; 197 System.arraycopy(oldPreComp, 0, preComp, 0, preCompLen); 198 199 for (int i = preCompLen; i < reqPreCompLen; i++) 200 { 201 // Compute the new ECPoints for the precomputation array. 202 // The values 1, 3, 5, ..., 2^(width-1)-1 times p are 203 // computed 204 preComp[i] = twiceP.add(preComp[i - 1]); 205 } 206 } 207 208 // Compute the Window NAF of the desired width 209 byte[] wnaf = windowNaf(width, k); 210 int l = wnaf.length; 211 212 // Apply the Window NAF to p using the precomputed ECPoint values. 213 ECPoint q = p.getCurve().getInfinity(); 214 for (int i = l - 1; i >= 0; i--) 215 { 216 q = q.twice(); 217 218 if (wnaf[i] != 0) 219 { 220 if (wnaf[i] > 0) 221 { 222 q = q.add(preComp[(wnaf[i] - 1)/2]); 223 } 224 else 225 { 226 // wnaf[i] < 0 227 q = q.subtract(preComp[(-wnaf[i] - 1)/2]); 228 } 229 } 230 } 231 232 // Set PreCompInfo in ECPoint, such that it is available for next 233 // multiplication. 234 wnafPreCompInfo.setPreComp(preComp); 235 wnafPreCompInfo.setTwiceP(twiceP); 236 p.setPreCompInfo(wnafPreCompInfo); 237 return q; 238 } 239 240 } 241
