Class ECConstantTimeMultiplier

java.lang.Object
org.bouncycastle.math.ec.AbstractECMultiplier
org.bouncycastle.math.ec.ECConstantTimeMultiplier
All Implemented Interfaces:
ECMultiplier
public class ECConstantTimeMultiplier extends AbstractECMultiplier
Scalar multiplication of a variable point by a secret scalar, without leaking the scalar through control flow or memory-access pattern.

WNafL2RMultiplier - the default multiplier for most curves - is not suitable for a secret scalar: it selects between two precomputed tables on the sign of a wNAF digit, indexes those tables directly with the digit's magnitude, and performs a run of doublings whose length is the number of zeros in the recoding. All three depend on the scalar. FixedPointCombMultiplier is constant-time but fixed-base only, and its precomputation is far too expensive to pay per call on the varying point of a key agreement.

This multiplier uses a fixed window instead:

  • the scalar is forced odd (by adding the group order, which is odd, under a mask) and recoded into a fixed number of odd signed digits, so no digit is zero, and both the iteration count and the number of doublings are independent of the scalar;
  • the precomputed table holds the odd multiples and their negations, so a digit's sign is folded into its table index and no conditional point negation is needed;
  • table entries are fetched with ECLookupTable.lookup(int), which ECCurve.createCacheSafeLookupTable(ECPoint[], int, int) implements as a masked scan over the whole table, so the index does not steer a memory access.
The result is identical to the other multipliers; only the timing profile differs. Expect it to be somewhat slower, and markedly slower on a curve with a GLV endomorphism (secp256k1), whose speedup is deliberately given up here - splitting the scalar for GLV is itself a BigInteger computation on the secret.

The point must lie in the subgroup of the given order: forcing the scalar odd computes (k + n)P in place of an even kP, and the two agree exactly when the order of P divides n. Points validated against domain parameters satisfy this (ECPoint.isValid() includes the order check); a point decoded straight off the wire on a cofactor curve need not, and for such a point the result differs from ECPoint.multiply(BigInteger) by nP on even scalars. For the same reason the order must be odd - true of every standard EC group order, and enforced here, since an even one would break the recoding silently.

NOTE: every step below is written to avoid branching on, or indexing with, the scalar. Do not "simplify" the masked selections into conditionals. This class addresses the point arithmetic only; a caller whose scalar arrives as a BigInteger still exposes that value's magnitude through the length of its internal representation, and reduction of the scalar before it reaches here (for example a cofactor adjustment) is outside the guarantee. The guarantee also stops at the field layer: on the custom curves the field arithmetic is fixed-length limb arithmetic, but on a generic ECCurve.Fp or F2m curve - brainpool, the GOST curves, or a caller-built curve - the field operations under the point arithmetic are BigInteger-based and their timing can vary with operand values.

See Also:

  • Constructor Details

    • ECConstantTimeMultiplier

      public ECConstantTimeMultiplier()
      Take the group order from the curve. Every curve in ECNamedCurveTable and CustomNamedCurves carries one, but a caller-built ECCurve need not - see ECConstantTimeMultiplier(BigInteger).

    • ECConstantTimeMultiplier

      public ECConstantTimeMultiplier(BigInteger order)
      Parameters:
      order - the group order, or null to take it from the curve; must be odd. The recoding needs the order to force the scalar odd, and ECCurve.getOrder() is null for a curve built without one - domain parameters always carry it separately, so a caller that has ECDomainParameters should pass its getN().

  • Method Details

    • multiplyPositive

      protected ECPoint multiplyPositive(ECPoint p, BigInteger k)
      Specified by:
      multiplyPositive in class AbstractECMultiplier

    • getWidth

      protected int getWidth(int size)
      Window width. The table costs 2^(width-1) point additions to build and the main loop runs ceil(size / width) iterations, so the useful range is narrow; these follow the same shape as the widths WNafUtil picks for comparable scalar sizes.