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: We try to optimize 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             // Optimization can only be used for values in the lower half of the table
46             if ((n << 2) < (1 << width))
47             {
48                 int highest = LongArray.bitLengths[n];
49 
50                 // TODO Get addition/doubling cost ratio from curve and compare to 'scale' to see if worth substituting?
51                 int scale = width - highest;
52                 int lowBits =  n ^ (1 << (highest - 1));
53 
54                 int i1 = ((1 << (width - 1)) - 1);
55                 int i2 = (lowBits << scale) + 1;
56                 R = table[i1 >>> 1].add(table[i2 >>> 1]);
57 
58                 zeroes -= scale;
59 
60 //              System.out.println("Optimized: 2^" + scale + " * " + n + " = " + i1 + " + " + i2);
61             }
62             else
63             {
64                 R = table[n >>> 1];
65             }
66 
67             R = R.timesPow2(zeroes);
68         }
69 
70         while (i > 0)
71         {
72             int wi = wnaf[--i];
73             int digit = wi >> 16, zeroes = wi & 0xFFFF;
74 
75             int n = Math.abs(digit);
76             ECPoint[] table = digit < 0 ? preCompNeg : preComp;
77             ECPoint r = table[n >>> 1];
78 
79             R = R.twicePlus(r);
80             R = R.timesPow2(zeroes);
81         }
82 
83         return R;
84     }
85 
86     /**
87      * Determine window width to use for a scalar multiplication of the given size.
88      *
89      * @param bits the bit-length of the scalar to multiply by
90      * @return the window size to use
91      */
getWindowSize(int bits)92     protected int getWindowSize(int bits)
93     {
94         return WNafUtil.getWindowSize(bits);
95     }
96 }
97