Package org.bouncycastle.math.ec

Class 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:
    ECAlgorithms.multiplySecret(ECPoint, BigInteger)

    • Constructor Detail

      • 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​(java.math.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 Detail

      • 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.