| | | 1 | | using System; |
| | | 2 | | |
| | | 3 | | using Renci.SshNet.Security.Org.BouncyCastle.Math.EC.Endo; |
| | | 4 | | using Renci.SshNet.Security.Org.BouncyCastle.Math.EC.Multiplier; |
| | | 5 | | using Renci.SshNet.Security.Org.BouncyCastle.Math.Field; |
| | | 6 | | |
| | | 7 | | namespace Renci.SshNet.Security.Org.BouncyCastle.Math.EC |
| | | 8 | | { |
| | | 9 | | internal class ECAlgorithms |
| | | 10 | | { |
| | | 11 | | public static bool IsF2mCurve(ECCurve c) |
| | 0 | 12 | | { |
| | 0 | 13 | | return IsF2mField(c.Field); |
| | 0 | 14 | | } |
| | | 15 | | |
| | | 16 | | public static bool IsF2mField(IFiniteField field) |
| | 0 | 17 | | { |
| | 0 | 18 | | return field.Dimension > 1 && field.Characteristic.Equals(BigInteger.Two) |
| | 0 | 19 | | && field is IPolynomialExtensionField; |
| | 0 | 20 | | } |
| | | 21 | | |
| | | 22 | | public static bool IsFpCurve(ECCurve c) |
| | 9 | 23 | | { |
| | 9 | 24 | | return IsFpField(c.Field); |
| | 9 | 25 | | } |
| | | 26 | | |
| | | 27 | | public static bool IsFpField(IFiniteField field) |
| | 9 | 28 | | { |
| | 9 | 29 | | return field.Dimension == 1; |
| | 9 | 30 | | } |
| | | 31 | | |
| | | 32 | | public static ECPoint SumOfMultiplies(ECPoint[] ps, BigInteger[] ks) |
| | 0 | 33 | | { |
| | 0 | 34 | | if (ps == null || ks == null || ps.Length != ks.Length || ps.Length < 1) |
| | 0 | 35 | | throw new ArgumentException("point and scalar arrays should be non-null, and of equal, non-zero, length" |
| | | 36 | | |
| | 0 | 37 | | int count = ps.Length; |
| | 0 | 38 | | switch (count) |
| | | 39 | | { |
| | | 40 | | case 1: |
| | 0 | 41 | | return ps[0].Multiply(ks[0]); |
| | | 42 | | case 2: |
| | 0 | 43 | | return SumOfTwoMultiplies(ps[0], ks[0], ps[1], ks[1]); |
| | | 44 | | default: |
| | 0 | 45 | | break; |
| | | 46 | | } |
| | | 47 | | |
| | 0 | 48 | | ECPoint p = ps[0]; |
| | 0 | 49 | | ECCurve c = p.Curve; |
| | | 50 | | |
| | 0 | 51 | | ECPoint[] imported = new ECPoint[count]; |
| | 0 | 52 | | imported[0] = p; |
| | 0 | 53 | | for (int i = 1; i < count; ++i) |
| | 0 | 54 | | { |
| | 0 | 55 | | imported[i] = ImportPoint(c, ps[i]); |
| | 0 | 56 | | } |
| | | 57 | | |
| | 0 | 58 | | GlvEndomorphism glvEndomorphism = c.GetEndomorphism() as GlvEndomorphism; |
| | 0 | 59 | | if (glvEndomorphism != null) |
| | 0 | 60 | | { |
| | 0 | 61 | | return ImplCheckResult(ImplSumOfMultipliesGlv(imported, ks, glvEndomorphism)); |
| | | 62 | | } |
| | | 63 | | |
| | 0 | 64 | | return ImplCheckResult(ImplSumOfMultiplies(imported, ks)); |
| | 0 | 65 | | } |
| | | 66 | | |
| | | 67 | | public static ECPoint SumOfTwoMultiplies(ECPoint P, BigInteger a, ECPoint Q, BigInteger b) |
| | 0 | 68 | | { |
| | 0 | 69 | | ECCurve cp = P.Curve; |
| | 0 | 70 | | Q = ImportPoint(cp, Q); |
| | | 71 | | |
| | | 72 | | // Point multiplication for Koblitz curves (using WTNAF) beats Shamir's trick |
| | 0 | 73 | | { |
| | 0 | 74 | | AbstractF2mCurve f2mCurve = cp as AbstractF2mCurve; |
| | 0 | 75 | | if (f2mCurve != null && f2mCurve.IsKoblitz) |
| | 0 | 76 | | { |
| | 0 | 77 | | return ImplCheckResult(P.Multiply(a).Add(Q.Multiply(b))); |
| | | 78 | | } |
| | 0 | 79 | | } |
| | | 80 | | |
| | 0 | 81 | | GlvEndomorphism glvEndomorphism = cp.GetEndomorphism() as GlvEndomorphism; |
| | 0 | 82 | | if (glvEndomorphism != null) |
| | 0 | 83 | | { |
| | 0 | 84 | | return ImplCheckResult( |
| | 0 | 85 | | ImplSumOfMultipliesGlv(new ECPoint[] { P, Q }, new BigInteger[] { a, b }, glvEndomorphism)); |
| | | 86 | | } |
| | | 87 | | |
| | 0 | 88 | | return ImplCheckResult(ImplShamirsTrickWNaf(P, a, Q, b)); |
| | 0 | 89 | | } |
| | | 90 | | |
| | | 91 | | /* |
| | | 92 | | * "Shamir's Trick", originally due to E. G. Straus |
| | | 93 | | * (Addition chains of vectors. American Mathematical Monthly, |
| | | 94 | | * 71(7):806-808, Aug./Sept. 1964) |
| | | 95 | | * |
| | | 96 | | * Input: The points P, Q, scalar k = (km?, ... , k1, k0) |
| | | 97 | | * and scalar l = (lm?, ... , l1, l0). |
| | | 98 | | * Output: R = k * P + l * Q. |
| | | 99 | | * 1: Z <- P + Q |
| | | 100 | | * 2: R <- O |
| | | 101 | | * 3: for i from m-1 down to 0 do |
| | | 102 | | * 4: R <- R + R {point doubling} |
| | | 103 | | * 5: if (ki = 1) and (li = 0) then R <- R + P end if |
| | | 104 | | * 6: if (ki = 0) and (li = 1) then R <- R + Q end if |
| | | 105 | | * 7: if (ki = 1) and (li = 1) then R <- R + Z end if |
| | | 106 | | * 8: end for |
| | | 107 | | * 9: return R |
| | | 108 | | */ |
| | | 109 | | public static ECPoint ShamirsTrick(ECPoint P, BigInteger k, ECPoint Q, BigInteger l) |
| | 0 | 110 | | { |
| | 0 | 111 | | ECCurve cp = P.Curve; |
| | 0 | 112 | | Q = ImportPoint(cp, Q); |
| | | 113 | | |
| | 0 | 114 | | return ImplCheckResult(ImplShamirsTrickJsf(P, k, Q, l)); |
| | 0 | 115 | | } |
| | | 116 | | |
| | | 117 | | public static ECPoint ImportPoint(ECCurve c, ECPoint p) |
| | 27 | 118 | | { |
| | 27 | 119 | | ECCurve cp = p.Curve; |
| | 27 | 120 | | if (!c.Equals(cp)) |
| | 0 | 121 | | throw new ArgumentException("Point must be on the same curve"); |
| | | 122 | | |
| | 27 | 123 | | return c.ImportPoint(p); |
| | 27 | 124 | | } |
| | | 125 | | |
| | | 126 | | public static void MontgomeryTrick(ECFieldElement[] zs, int off, int len) |
| | 0 | 127 | | { |
| | 0 | 128 | | MontgomeryTrick(zs, off, len, null); |
| | 0 | 129 | | } |
| | | 130 | | |
| | | 131 | | public static void MontgomeryTrick(ECFieldElement[] zs, int off, int len, ECFieldElement scale) |
| | 15 | 132 | | { |
| | | 133 | | /* |
| | | 134 | | * Uses the "Montgomery Trick" to invert many field elements, with only a single actual |
| | | 135 | | * field inversion. See e.g. the paper: |
| | | 136 | | * "Fast Multi-scalar Multiplication Methods on Elliptic Curves with Precomputation Strategy Using Montgomer |
| | | 137 | | * by Katsuyuki Okeya, Kouichi Sakurai. |
| | | 138 | | */ |
| | | 139 | | |
| | 15 | 140 | | ECFieldElement[] c = new ECFieldElement[len]; |
| | 15 | 141 | | c[0] = zs[off]; |
| | | 142 | | |
| | 15 | 143 | | int i = 0; |
| | 327 | 144 | | while (++i < len) |
| | 312 | 145 | | { |
| | 312 | 146 | | c[i] = c[i - 1].Multiply(zs[off + i]); |
| | 312 | 147 | | } |
| | | 148 | | |
| | 15 | 149 | | --i; |
| | | 150 | | |
| | 15 | 151 | | if (scale != null) |
| | 9 | 152 | | { |
| | 9 | 153 | | c[i] = c[i].Multiply(scale); |
| | 9 | 154 | | } |
| | | 155 | | |
| | 15 | 156 | | ECFieldElement u = c[i].Invert(); |
| | | 157 | | |
| | 327 | 158 | | while (i > 0) |
| | 312 | 159 | | { |
| | 312 | 160 | | int j = off + i--; |
| | 312 | 161 | | ECFieldElement tmp = zs[j]; |
| | 312 | 162 | | zs[j] = c[i].Multiply(u); |
| | 312 | 163 | | u = u.Multiply(tmp); |
| | 312 | 164 | | } |
| | | 165 | | |
| | 15 | 166 | | zs[off] = u; |
| | 15 | 167 | | } |
| | | 168 | | |
| | | 169 | | /** |
| | | 170 | | * Simple shift-and-add multiplication. Serves as reference implementation |
| | | 171 | | * to verify (possibly faster) implementations, and for very small scalars. |
| | | 172 | | * |
| | | 173 | | * @param p |
| | | 174 | | * The point to multiply. |
| | | 175 | | * @param k |
| | | 176 | | * The multiplier. |
| | | 177 | | * @return The result of the point multiplication <code>kP</code>. |
| | | 178 | | */ |
| | | 179 | | public static ECPoint ReferenceMultiply(ECPoint p, BigInteger k) |
| | 0 | 180 | | { |
| | 0 | 181 | | BigInteger x = k.Abs(); |
| | 0 | 182 | | ECPoint q = p.Curve.Infinity; |
| | 0 | 183 | | int t = x.BitLength; |
| | 0 | 184 | | if (t > 0) |
| | 0 | 185 | | { |
| | 0 | 186 | | if (x.TestBit(0)) |
| | 0 | 187 | | { |
| | 0 | 188 | | q = p; |
| | 0 | 189 | | } |
| | 0 | 190 | | for (int i = 1; i < t; i++) |
| | 0 | 191 | | { |
| | 0 | 192 | | p = p.Twice(); |
| | 0 | 193 | | if (x.TestBit(i)) |
| | 0 | 194 | | { |
| | 0 | 195 | | q = q.Add(p); |
| | 0 | 196 | | } |
| | 0 | 197 | | } |
| | 0 | 198 | | } |
| | 0 | 199 | | return k.SignValue < 0 ? q.Negate() : q; |
| | 0 | 200 | | } |
| | | 201 | | |
| | | 202 | | public static ECPoint ValidatePoint(ECPoint p) |
| | 0 | 203 | | { |
| | 0 | 204 | | if (!p.IsValid()) |
| | 0 | 205 | | throw new InvalidOperationException("Invalid point"); |
| | | 206 | | |
| | 0 | 207 | | return p; |
| | 0 | 208 | | } |
| | | 209 | | |
| | | 210 | | public static ECPoint CleanPoint(ECCurve c, ECPoint p) |
| | 9 | 211 | | { |
| | 9 | 212 | | ECCurve cp = p.Curve; |
| | 9 | 213 | | if (!c.Equals(cp)) |
| | 0 | 214 | | throw new ArgumentException("Point must be on the same curve", "p"); |
| | | 215 | | |
| | 9 | 216 | | return c.DecodePoint(p.GetEncoded(false)); |
| | 9 | 217 | | } |
| | | 218 | | |
| | | 219 | | internal static ECPoint ImplCheckResult(ECPoint p) |
| | 18 | 220 | | { |
| | 18 | 221 | | if (!p.IsValidPartial()) |
| | 0 | 222 | | throw new InvalidOperationException("Invalid result"); |
| | | 223 | | |
| | 18 | 224 | | return p; |
| | 18 | 225 | | } |
| | | 226 | | |
| | | 227 | | internal static ECPoint ImplShamirsTrickJsf(ECPoint P, BigInteger k, ECPoint Q, BigInteger l) |
| | 0 | 228 | | { |
| | 0 | 229 | | ECCurve curve = P.Curve; |
| | 0 | 230 | | ECPoint infinity = curve.Infinity; |
| | | 231 | | |
| | | 232 | | // TODO conjugate co-Z addition (ZADDC) can return both of these |
| | 0 | 233 | | ECPoint PaddQ = P.Add(Q); |
| | 0 | 234 | | ECPoint PsubQ = P.Subtract(Q); |
| | | 235 | | |
| | 0 | 236 | | ECPoint[] points = new ECPoint[] { Q, PsubQ, P, PaddQ }; |
| | 0 | 237 | | curve.NormalizeAll(points); |
| | | 238 | | |
| | 0 | 239 | | ECPoint[] table = new ECPoint[] { |
| | 0 | 240 | | points[3].Negate(), points[2].Negate(), points[1].Negate(), |
| | 0 | 241 | | points[0].Negate(), infinity, points[0], |
| | 0 | 242 | | points[1], points[2], points[3] }; |
| | | 243 | | |
| | 0 | 244 | | byte[] jsf = WNafUtilities.GenerateJsf(k, l); |
| | | 245 | | |
| | 0 | 246 | | ECPoint R = infinity; |
| | | 247 | | |
| | 0 | 248 | | int i = jsf.Length; |
| | 0 | 249 | | while (--i >= 0) |
| | 0 | 250 | | { |
| | 0 | 251 | | int jsfi = jsf[i]; |
| | | 252 | | |
| | | 253 | | // NOTE: The shifting ensures the sign is extended correctly |
| | 0 | 254 | | int kDigit = ((jsfi << 24) >> 28), lDigit = ((jsfi << 28) >> 28); |
| | | 255 | | |
| | 0 | 256 | | int index = 4 + (kDigit * 3) + lDigit; |
| | 0 | 257 | | R = R.TwicePlus(table[index]); |
| | 0 | 258 | | } |
| | | 259 | | |
| | 0 | 260 | | return R; |
| | 0 | 261 | | } |
| | | 262 | | |
| | | 263 | | internal static ECPoint ImplShamirsTrickWNaf(ECPoint P, BigInteger k, |
| | | 264 | | ECPoint Q, BigInteger l) |
| | 0 | 265 | | { |
| | 0 | 266 | | bool negK = k.SignValue < 0, negL = l.SignValue < 0; |
| | | 267 | | |
| | 0 | 268 | | k = k.Abs(); |
| | 0 | 269 | | l = l.Abs(); |
| | | 270 | | |
| | 0 | 271 | | int widthP = System.Math.Max(2, System.Math.Min(16, WNafUtilities.GetWindowSize(k.BitLength))); |
| | 0 | 272 | | int widthQ = System.Math.Max(2, System.Math.Min(16, WNafUtilities.GetWindowSize(l.BitLength))); |
| | | 273 | | |
| | 0 | 274 | | WNafPreCompInfo infoP = WNafUtilities.Precompute(P, widthP, true); |
| | 0 | 275 | | WNafPreCompInfo infoQ = WNafUtilities.Precompute(Q, widthQ, true); |
| | | 276 | | |
| | 0 | 277 | | ECPoint[] preCompP = negK ? infoP.PreCompNeg : infoP.PreComp; |
| | 0 | 278 | | ECPoint[] preCompQ = negL ? infoQ.PreCompNeg : infoQ.PreComp; |
| | 0 | 279 | | ECPoint[] preCompNegP = negK ? infoP.PreComp : infoP.PreCompNeg; |
| | 0 | 280 | | ECPoint[] preCompNegQ = negL ? infoQ.PreComp : infoQ.PreCompNeg; |
| | | 281 | | |
| | 0 | 282 | | byte[] wnafP = WNafUtilities.GenerateWindowNaf(widthP, k); |
| | 0 | 283 | | byte[] wnafQ = WNafUtilities.GenerateWindowNaf(widthQ, l); |
| | | 284 | | |
| | 0 | 285 | | return ImplShamirsTrickWNaf(preCompP, preCompNegP, wnafP, preCompQ, preCompNegQ, wnafQ); |
| | 0 | 286 | | } |
| | | 287 | | |
| | | 288 | | internal static ECPoint ImplShamirsTrickWNaf(ECPoint P, BigInteger k, ECPointMap pointMapQ, BigInteger l) |
| | 0 | 289 | | { |
| | 0 | 290 | | bool negK = k.SignValue < 0, negL = l.SignValue < 0; |
| | | 291 | | |
| | 0 | 292 | | k = k.Abs(); |
| | 0 | 293 | | l = l.Abs(); |
| | | 294 | | |
| | 0 | 295 | | int width = System.Math.Max(2, System.Math.Min(16, WNafUtilities.GetWindowSize(System.Math.Max(k.BitLength, |
| | | 296 | | |
| | 0 | 297 | | ECPoint Q = WNafUtilities.MapPointWithPrecomp(P, width, true, pointMapQ); |
| | 0 | 298 | | WNafPreCompInfo infoP = WNafUtilities.GetWNafPreCompInfo(P); |
| | 0 | 299 | | WNafPreCompInfo infoQ = WNafUtilities.GetWNafPreCompInfo(Q); |
| | | 300 | | |
| | 0 | 301 | | ECPoint[] preCompP = negK ? infoP.PreCompNeg : infoP.PreComp; |
| | 0 | 302 | | ECPoint[] preCompQ = negL ? infoQ.PreCompNeg : infoQ.PreComp; |
| | 0 | 303 | | ECPoint[] preCompNegP = negK ? infoP.PreComp : infoP.PreCompNeg; |
| | 0 | 304 | | ECPoint[] preCompNegQ = negL ? infoQ.PreComp : infoQ.PreCompNeg; |
| | | 305 | | |
| | 0 | 306 | | byte[] wnafP = WNafUtilities.GenerateWindowNaf(width, k); |
| | 0 | 307 | | byte[] wnafQ = WNafUtilities.GenerateWindowNaf(width, l); |
| | | 308 | | |
| | 0 | 309 | | return ImplShamirsTrickWNaf(preCompP, preCompNegP, wnafP, preCompQ, preCompNegQ, wnafQ); |
| | 0 | 310 | | } |
| | | 311 | | |
| | | 312 | | private static ECPoint ImplShamirsTrickWNaf(ECPoint[] preCompP, ECPoint[] preCompNegP, byte[] wnafP, |
| | | 313 | | ECPoint[] preCompQ, ECPoint[] preCompNegQ, byte[] wnafQ) |
| | 0 | 314 | | { |
| | 0 | 315 | | int len = System.Math.Max(wnafP.Length, wnafQ.Length); |
| | | 316 | | |
| | 0 | 317 | | ECCurve curve = preCompP[0].Curve; |
| | 0 | 318 | | ECPoint infinity = curve.Infinity; |
| | | 319 | | |
| | 0 | 320 | | ECPoint R = infinity; |
| | 0 | 321 | | int zeroes = 0; |
| | | 322 | | |
| | 0 | 323 | | for (int i = len - 1; i >= 0; --i) |
| | 0 | 324 | | { |
| | 0 | 325 | | int wiP = i < wnafP.Length ? (int)(sbyte)wnafP[i] : 0; |
| | 0 | 326 | | int wiQ = i < wnafQ.Length ? (int)(sbyte)wnafQ[i] : 0; |
| | | 327 | | |
| | 0 | 328 | | if ((wiP | wiQ) == 0) |
| | 0 | 329 | | { |
| | 0 | 330 | | ++zeroes; |
| | 0 | 331 | | continue; |
| | | 332 | | } |
| | | 333 | | |
| | 0 | 334 | | ECPoint r = infinity; |
| | 0 | 335 | | if (wiP != 0) |
| | 0 | 336 | | { |
| | 0 | 337 | | int nP = System.Math.Abs(wiP); |
| | 0 | 338 | | ECPoint[] tableP = wiP < 0 ? preCompNegP : preCompP; |
| | 0 | 339 | | r = r.Add(tableP[nP >> 1]); |
| | 0 | 340 | | } |
| | 0 | 341 | | if (wiQ != 0) |
| | 0 | 342 | | { |
| | 0 | 343 | | int nQ = System.Math.Abs(wiQ); |
| | 0 | 344 | | ECPoint[] tableQ = wiQ < 0 ? preCompNegQ : preCompQ; |
| | 0 | 345 | | r = r.Add(tableQ[nQ >> 1]); |
| | 0 | 346 | | } |
| | | 347 | | |
| | 0 | 348 | | if (zeroes > 0) |
| | 0 | 349 | | { |
| | 0 | 350 | | R = R.TimesPow2(zeroes); |
| | 0 | 351 | | zeroes = 0; |
| | 0 | 352 | | } |
| | | 353 | | |
| | 0 | 354 | | R = R.TwicePlus(r); |
| | 0 | 355 | | } |
| | | 356 | | |
| | 0 | 357 | | if (zeroes > 0) |
| | 0 | 358 | | { |
| | 0 | 359 | | R = R.TimesPow2(zeroes); |
| | 0 | 360 | | } |
| | | 361 | | |
| | 0 | 362 | | return R; |
| | 0 | 363 | | } |
| | | 364 | | |
| | | 365 | | internal static ECPoint ImplSumOfMultiplies(ECPoint[] ps, BigInteger[] ks) |
| | 0 | 366 | | { |
| | 0 | 367 | | int count = ps.Length; |
| | 0 | 368 | | bool[] negs = new bool[count]; |
| | 0 | 369 | | WNafPreCompInfo[] infos = new WNafPreCompInfo[count]; |
| | 0 | 370 | | byte[][] wnafs = new byte[count][]; |
| | | 371 | | |
| | 0 | 372 | | for (int i = 0; i < count; ++i) |
| | 0 | 373 | | { |
| | 0 | 374 | | BigInteger ki = ks[i]; negs[i] = ki.SignValue < 0; ki = ki.Abs(); |
| | | 375 | | |
| | 0 | 376 | | int width = System.Math.Max(2, System.Math.Min(16, WNafUtilities.GetWindowSize(ki.BitLength))); |
| | 0 | 377 | | infos[i] = WNafUtilities.Precompute(ps[i], width, true); |
| | 0 | 378 | | wnafs[i] = WNafUtilities.GenerateWindowNaf(width, ki); |
| | 0 | 379 | | } |
| | | 380 | | |
| | 0 | 381 | | return ImplSumOfMultiplies(negs, infos, wnafs); |
| | 0 | 382 | | } |
| | | 383 | | |
| | | 384 | | internal static ECPoint ImplSumOfMultipliesGlv(ECPoint[] ps, BigInteger[] ks, GlvEndomorphism glvEndomorphism) |
| | 0 | 385 | | { |
| | 0 | 386 | | BigInteger n = ps[0].Curve.Order; |
| | | 387 | | |
| | 0 | 388 | | int len = ps.Length; |
| | | 389 | | |
| | 0 | 390 | | BigInteger[] abs = new BigInteger[len << 1]; |
| | 0 | 391 | | for (int i = 0, j = 0; i < len; ++i) |
| | 0 | 392 | | { |
| | 0 | 393 | | BigInteger[] ab = glvEndomorphism.DecomposeScalar(ks[i].Mod(n)); |
| | 0 | 394 | | abs[j++] = ab[0]; |
| | 0 | 395 | | abs[j++] = ab[1]; |
| | 0 | 396 | | } |
| | | 397 | | |
| | 0 | 398 | | ECPointMap pointMap = glvEndomorphism.PointMap; |
| | 0 | 399 | | if (glvEndomorphism.HasEfficientPointMap) |
| | 0 | 400 | | { |
| | 0 | 401 | | return ECAlgorithms.ImplSumOfMultiplies(ps, pointMap, abs); |
| | | 402 | | } |
| | | 403 | | |
| | 0 | 404 | | ECPoint[] pqs = new ECPoint[len << 1]; |
| | 0 | 405 | | for (int i = 0, j = 0; i < len; ++i) |
| | 0 | 406 | | { |
| | 0 | 407 | | ECPoint p = ps[i], q = pointMap.Map(p); |
| | 0 | 408 | | pqs[j++] = p; |
| | 0 | 409 | | pqs[j++] = q; |
| | 0 | 410 | | } |
| | | 411 | | |
| | 0 | 412 | | return ECAlgorithms.ImplSumOfMultiplies(pqs, abs); |
| | 0 | 413 | | } |
| | | 414 | | |
| | | 415 | | internal static ECPoint ImplSumOfMultiplies(ECPoint[] ps, ECPointMap pointMap, BigInteger[] ks) |
| | 0 | 416 | | { |
| | 0 | 417 | | int halfCount = ps.Length, fullCount = halfCount << 1; |
| | | 418 | | |
| | 0 | 419 | | bool[] negs = new bool[fullCount]; |
| | 0 | 420 | | WNafPreCompInfo[] infos = new WNafPreCompInfo[fullCount]; |
| | 0 | 421 | | byte[][] wnafs = new byte[fullCount][]; |
| | | 422 | | |
| | 0 | 423 | | for (int i = 0; i < halfCount; ++i) |
| | 0 | 424 | | { |
| | 0 | 425 | | int j0 = i << 1, j1 = j0 + 1; |
| | | 426 | | |
| | 0 | 427 | | BigInteger kj0 = ks[j0]; negs[j0] = kj0.SignValue < 0; kj0 = kj0.Abs(); |
| | 0 | 428 | | BigInteger kj1 = ks[j1]; negs[j1] = kj1.SignValue < 0; kj1 = kj1.Abs(); |
| | | 429 | | |
| | 0 | 430 | | int width = System.Math.Max(2, System.Math.Min(16, WNafUtilities.GetWindowSize(System.Math.Max(kj0.BitLe |
| | | 431 | | |
| | 0 | 432 | | ECPoint P = ps[i], Q = WNafUtilities.MapPointWithPrecomp(P, width, true, pointMap); |
| | 0 | 433 | | infos[j0] = WNafUtilities.GetWNafPreCompInfo(P); |
| | 0 | 434 | | infos[j1] = WNafUtilities.GetWNafPreCompInfo(Q); |
| | 0 | 435 | | wnafs[j0] = WNafUtilities.GenerateWindowNaf(width, kj0); |
| | 0 | 436 | | wnafs[j1] = WNafUtilities.GenerateWindowNaf(width, kj1); |
| | 0 | 437 | | } |
| | | 438 | | |
| | 0 | 439 | | return ImplSumOfMultiplies(negs, infos, wnafs); |
| | 0 | 440 | | } |
| | | 441 | | |
| | | 442 | | private static ECPoint ImplSumOfMultiplies(bool[] negs, WNafPreCompInfo[] infos, byte[][] wnafs) |
| | 0 | 443 | | { |
| | 0 | 444 | | int len = 0, count = wnafs.Length; |
| | 0 | 445 | | for (int i = 0; i < count; ++i) |
| | 0 | 446 | | { |
| | 0 | 447 | | len = System.Math.Max(len, wnafs[i].Length); |
| | 0 | 448 | | } |
| | | 449 | | |
| | 0 | 450 | | ECCurve curve = infos[0].PreComp[0].Curve; |
| | 0 | 451 | | ECPoint infinity = curve.Infinity; |
| | | 452 | | |
| | 0 | 453 | | ECPoint R = infinity; |
| | 0 | 454 | | int zeroes = 0; |
| | | 455 | | |
| | 0 | 456 | | for (int i = len - 1; i >= 0; --i) |
| | 0 | 457 | | { |
| | 0 | 458 | | ECPoint r = infinity; |
| | | 459 | | |
| | 0 | 460 | | for (int j = 0; j < count; ++j) |
| | 0 | 461 | | { |
| | 0 | 462 | | byte[] wnaf = wnafs[j]; |
| | 0 | 463 | | int wi = i < wnaf.Length ? (int)(sbyte)wnaf[i] : 0; |
| | 0 | 464 | | if (wi != 0) |
| | 0 | 465 | | { |
| | 0 | 466 | | int n = System.Math.Abs(wi); |
| | 0 | 467 | | WNafPreCompInfo info = infos[j]; |
| | 0 | 468 | | ECPoint[] table = (wi < 0 == negs[j]) ? info.PreComp : info.PreCompNeg; |
| | 0 | 469 | | r = r.Add(table[n >> 1]); |
| | 0 | 470 | | } |
| | 0 | 471 | | } |
| | | 472 | | |
| | 0 | 473 | | if (r == infinity) |
| | 0 | 474 | | { |
| | 0 | 475 | | ++zeroes; |
| | 0 | 476 | | continue; |
| | | 477 | | } |
| | | 478 | | |
| | 0 | 479 | | if (zeroes > 0) |
| | 0 | 480 | | { |
| | 0 | 481 | | R = R.TimesPow2(zeroes); |
| | 0 | 482 | | zeroes = 0; |
| | 0 | 483 | | } |
| | | 484 | | |
| | 0 | 485 | | R = R.TwicePlus(r); |
| | 0 | 486 | | } |
| | | 487 | | |
| | 0 | 488 | | if (zeroes > 0) |
| | 0 | 489 | | { |
| | 0 | 490 | | R = R.TimesPow2(zeroes); |
| | 0 | 491 | | } |
| | | 492 | | |
| | 0 | 493 | | return R; |
| | 0 | 494 | | } |
| | | 495 | | } |
| | | 496 | | } |