org.bouncycastle.math.ec

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:

ECAlgorithms.multiplySecret(ECPoint, BigInteger)

Constructor Summary

Constructors

Constructor and Description
ECConstantTimeMultiplier() Take the group order from the curve.
ECConstantTimeMultiplier(java.math.BigInteger order)

Method Summary

Modifier and Type	Method and Description
protected int	getWidth(int size) Window width.
protected ECPoint	multiplyPositive(ECPoint p, java.math.BigInteger k)

Methods inherited from class org.bouncycastle.math.ec.AbstractECMultiplier

checkResult, multiply

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

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

multiplyPositive

protected ECPoint multiplyPositive(ECPoint p,
                                   java.math.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.