| | | 1 | | using System; |
| | | 2 | | |
| | | 3 | | namespace Renci.SshNet.Security.Org.BouncyCastle.Math.EC.Multiplier |
| | | 4 | | { |
| | | 5 | | /** |
| | | 6 | | * Class implementing the WNAF (Window Non-Adjacent Form) multiplication |
| | | 7 | | * algorithm. |
| | | 8 | | */ |
| | | 9 | | internal class WNafL2RMultiplier |
| | | 10 | | : AbstractECMultiplier |
| | | 11 | | { |
| | | 12 | | /** |
| | | 13 | | * Multiplies <code>this</code> by an integer <code>k</code> using the |
| | | 14 | | * Window NAF method. |
| | | 15 | | * @param k The integer by which <code>this</code> is multiplied. |
| | | 16 | | * @return A new <code>ECPoint</code> which equals <code>this</code> |
| | | 17 | | * multiplied by <code>k</code>. |
| | | 18 | | */ |
| | | 19 | | protected override ECPoint MultiplyPositive(ECPoint p, BigInteger k) |
| | 9 | 20 | | { |
| | | 21 | | // Clamp the window width in the range [2, 16] |
| | 9 | 22 | | int width = System.Math.Max(2, System.Math.Min(16, GetWindowSize(k.BitLength))); |
| | | 23 | | |
| | 9 | 24 | | WNafPreCompInfo wnafPreCompInfo = WNafUtilities.Precompute(p, width, true); |
| | 9 | 25 | | ECPoint[] preComp = wnafPreCompInfo.PreComp; |
| | 9 | 26 | | ECPoint[] preCompNeg = wnafPreCompInfo.PreCompNeg; |
| | | 27 | | |
| | 9 | 28 | | int[] wnaf = WNafUtilities.GenerateCompactWindowNaf(width, k); |
| | | 29 | | |
| | 9 | 30 | | ECPoint R = p.Curve.Infinity; |
| | | 31 | | |
| | 9 | 32 | | int i = wnaf.Length; |
| | | 33 | | |
| | | 34 | | /* |
| | | 35 | | * NOTE: We try to optimize the first window using the precomputed points to substitute an |
| | | 36 | | * addition for 2 or more doublings. |
| | | 37 | | */ |
| | 9 | 38 | | if (i > 1) |
| | 9 | 39 | | { |
| | 9 | 40 | | int wi = wnaf[--i]; |
| | 18 | 41 | | int digit = wi >> 16, zeroes = wi & 0xFFFF; |
| | | 42 | | |
| | 9 | 43 | | int n = System.Math.Abs(digit); |
| | 9 | 44 | | ECPoint[] table = digit < 0 ? preCompNeg : preComp; |
| | | 45 | | |
| | | 46 | | // Optimization can only be used for values in the lower half of the table |
| | 9 | 47 | | if ((n << 2) < (1 << width)) |
| | 7 | 48 | | { |
| | 7 | 49 | | int highest = LongArray.BitLengths[n]; |
| | | 50 | | |
| | | 51 | | // TODO Get addition/doubling cost ratio from curve and compare to 'scale' to see if worth substitut |
| | 7 | 52 | | int scale = width - highest; |
| | 7 | 53 | | int lowBits = n ^ (1 << (highest - 1)); |
| | | 54 | | |
| | 7 | 55 | | int i1 = ((1 << (width - 1)) - 1); |
| | 7 | 56 | | int i2 = (lowBits << scale) + 1; |
| | 7 | 57 | | R = table[i1 >> 1].Add(table[i2 >> 1]); |
| | | 58 | | |
| | 7 | 59 | | zeroes -= scale; |
| | | 60 | | |
| | | 61 | | //Console.WriteLine("Optimized: 2^" + scale + " * " + n + " = " + i1 + " + " + i2); |
| | 7 | 62 | | } |
| | | 63 | | else |
| | 2 | 64 | | { |
| | 2 | 65 | | R = table[n >> 1]; |
| | 2 | 66 | | } |
| | | 67 | | |
| | 9 | 68 | | R = R.TimesPow2(zeroes); |
| | 9 | 69 | | } |
| | | 70 | | |
| | 521 | 71 | | while (i > 0) |
| | 512 | 72 | | { |
| | 512 | 73 | | int wi = wnaf[--i]; |
| | 1024 | 74 | | int digit = wi >> 16, zeroes = wi & 0xFFFF; |
| | | 75 | | |
| | 512 | 76 | | int n = System.Math.Abs(digit); |
| | 512 | 77 | | ECPoint[] table = digit < 0 ? preCompNeg : preComp; |
| | 512 | 78 | | ECPoint r = table[n >> 1]; |
| | | 79 | | |
| | 512 | 80 | | R = R.TwicePlus(r); |
| | 512 | 81 | | R = R.TimesPow2(zeroes); |
| | 512 | 82 | | } |
| | | 83 | | |
| | 9 | 84 | | return R; |
| | 9 | 85 | | } |
| | | 86 | | |
| | | 87 | | /** |
| | | 88 | | * Determine window width to use for a scalar multiplication of the given size. |
| | | 89 | | * |
| | | 90 | | * @param bits the bit-length of the scalar to multiply by |
| | | 91 | | * @return the window size to use |
| | | 92 | | */ |
| | | 93 | | protected virtual int GetWindowSize(int bits) |
| | 9 | 94 | | { |
| | 9 | 95 | | return WNafUtilities.GetWindowSize(bits); |
| | 9 | 96 | | } |
| | | 97 | | } |
| | | 98 | | } |