diff options
Diffstat (limited to 'bcprov/src/main/java/org/bouncycastle/math')
37 files changed, 1332 insertions, 355 deletions
diff --git a/bcprov/src/main/java/org/bouncycastle/math/ec/AbstractECMultiplier.java b/bcprov/src/main/java/org/bouncycastle/math/ec/AbstractECMultiplier.java index d1f35c56..e0a55435 100644 --- a/bcprov/src/main/java/org/bouncycastle/math/ec/AbstractECMultiplier.java +++ b/bcprov/src/main/java/org/bouncycastle/math/ec/AbstractECMultiplier.java @@ -19,8 +19,13 @@ public abstract class AbstractECMultiplier implements ECMultiplier * Although the various multipliers ought not to produce invalid output under normal * circumstances, a final check here is advised to guard against fault attacks. */ - return ECAlgorithms.validatePoint(result); + return checkResult(result); } protected abstract ECPoint multiplyPositive(ECPoint p, BigInteger k); + + protected ECPoint checkResult(ECPoint p) + { + return ECAlgorithms.implCheckResult(p); + } } diff --git a/bcprov/src/main/java/org/bouncycastle/math/ec/ECAlgorithms.java b/bcprov/src/main/java/org/bouncycastle/math/ec/ECAlgorithms.java index f8bf1eb5..f0b1585d 100644 --- a/bcprov/src/main/java/org/bouncycastle/math/ec/ECAlgorithms.java +++ b/bcprov/src/main/java/org/bouncycastle/math/ec/ECAlgorithms.java @@ -61,10 +61,10 @@ public class ECAlgorithms ECEndomorphism endomorphism = c.getEndomorphism(); if (endomorphism instanceof GLVEndomorphism) { - return validatePoint(implSumOfMultipliesGLV(imported, ks, (GLVEndomorphism)endomorphism)); + return implCheckResult(implSumOfMultipliesGLV(imported, ks, (GLVEndomorphism)endomorphism)); } - return validatePoint(implSumOfMultiplies(imported, ks)); + return implCheckResult(implSumOfMultiplies(imported, ks)); } public static ECPoint sumOfTwoMultiplies(ECPoint P, BigInteger a, @@ -79,18 +79,18 @@ public class ECAlgorithms ECCurve.AbstractF2m f2mCurve = (ECCurve.AbstractF2m)cp; if (f2mCurve.isKoblitz()) { - return validatePoint(P.multiply(a).add(Q.multiply(b))); + return implCheckResult(P.multiply(a).add(Q.multiply(b))); } } ECEndomorphism endomorphism = cp.getEndomorphism(); if (endomorphism instanceof GLVEndomorphism) { - return validatePoint( + return implCheckResult( implSumOfMultipliesGLV(new ECPoint[]{ P, Q }, new BigInteger[]{ a, b }, (GLVEndomorphism)endomorphism)); } - return validatePoint(implShamirsTrickWNaf(P, a, Q, b)); + return implCheckResult(implShamirsTrickWNaf(P, a, Q, b)); } /* @@ -118,7 +118,7 @@ public class ECAlgorithms ECCurve cp = P.getCurve(); Q = importPoint(cp, Q); - return validatePoint(implShamirsTrickJsf(P, k, Q, l)); + return implCheckResult(implShamirsTrickJsf(P, k, Q, l)); } public static ECPoint importPoint(ECCurve c, ECPoint p) @@ -211,7 +211,28 @@ public class ECAlgorithms { if (!p.isValid()) { - throw new IllegalArgumentException("Invalid point"); + throw new IllegalStateException("Invalid point"); + } + + return p; + } + + public static ECPoint cleanPoint(ECCurve c, ECPoint p) + { + ECCurve cp = p.getCurve(); + if (!c.equals(cp)) + { + throw new IllegalArgumentException("Point must be on the same curve"); + } + + return c.decodePoint(p.getEncoded(false)); + } + + static ECPoint implCheckResult(ECPoint p) + { + if (!p.isValidPartial()) + { + throw new IllegalStateException("Invalid result"); } return p; diff --git a/bcprov/src/main/java/org/bouncycastle/math/ec/ECCurve.java b/bcprov/src/main/java/org/bouncycastle/math/ec/ECCurve.java index 7f3197bc..7c10c78b 100644 --- a/bcprov/src/main/java/org/bouncycastle/math/ec/ECCurve.java +++ b/bcprov/src/main/java/org/bouncycastle/math/ec/ECCurve.java @@ -8,6 +8,7 @@ import org.bouncycastle.math.ec.endo.ECEndomorphism; import org.bouncycastle.math.ec.endo.GLVEndomorphism; import org.bouncycastle.math.field.FiniteField; import org.bouncycastle.math.field.FiniteFields; +import org.bouncycastle.math.raw.Nat; import org.bouncycastle.util.BigIntegers; import org.bouncycastle.util.Integers; @@ -173,15 +174,26 @@ public abstract class ECCurve public PreCompInfo getPreCompInfo(ECPoint point, String name) { checkPoint(point); + + Hashtable table; synchronized (point) { - Hashtable table = point.preCompTable; - return table == null ? null : (PreCompInfo)table.get(name); + table = point.preCompTable; + } + + if (null == table) + { + return null; + } + + synchronized (table) + { + return (PreCompInfo)table.get(name); } } /** - * Adds <code>PreCompInfo</code> for a point on this curve, under a given name. Used by + * Compute a <code>PreCompInfo</code> for a point on this curve, under a given name. Used by * <code>ECMultiplier</code>s to save the precomputation for this <code>ECPoint</code> for use * by subsequent multiplication. * @@ -189,20 +201,34 @@ public abstract class ECCurve * The <code>ECPoint</code> to store precomputations for. * @param name * A <code>String</code> used to index precomputations of different types. - * @param preCompInfo - * The values precomputed by the <code>ECMultiplier</code>. + * @param callback + * Called to calculate the <code>PreCompInfo</code>. */ - public void setPreCompInfo(ECPoint point, String name, PreCompInfo preCompInfo) + public PreCompInfo precompute(ECPoint point, String name, PreCompCallback callback) { checkPoint(point); + + Hashtable table; synchronized (point) { - Hashtable table = point.preCompTable; + table = point.preCompTable; if (null == table) { point.preCompTable = table = new Hashtable(4); } - table.put(name, preCompInfo); + } + + synchronized (table) + { + PreCompInfo existing = (PreCompInfo)table.get(name); + PreCompInfo result = callback.precompute(existing); + + if (result != existing) + { + table.put(name, result); + } + + return result; } } @@ -220,7 +246,7 @@ public abstract class ECCurve // TODO Default behaviour could be improved if the two curves have the same coordinate system by copying any Z coordinates. p = p.normalize(); - return validatePoint(p.getXCoord().toBigInteger(), p.getYCoord().toBigInteger(), p.withCompression); + return createPoint(p.getXCoord().toBigInteger(), p.getYCoord().toBigInteger(), p.withCompression); } /** @@ -390,7 +416,7 @@ public abstract class ECCurve BigInteger X = BigIntegers.fromUnsignedByteArray(encoded, 1, expectedLength); p = decompressPoint(yTilde, X); - if (!p.satisfiesCofactor()) + if (!p.implIsValid(true, true)) { throw new IllegalArgumentException("Invalid point"); } @@ -441,6 +467,61 @@ public abstract class ECCurve return p; } + /** + * Create a cache-safe lookup table for the specified sequence of points. All the points MUST + * belong to this {@link ECCurve} instance, and MUST already be normalized. + */ + public ECLookupTable createCacheSafeLookupTable(final ECPoint[] points, int off, final int len) + { + final int FE_BYTES = (getFieldSize() + 7) >>> 3; + + final byte[] table = new byte[len * FE_BYTES * 2]; + { + int pos = 0; + for (int i = 0; i < len; ++i) + { + ECPoint p = points[off + i]; + byte[] px = p.getRawXCoord().toBigInteger().toByteArray(); + byte[] py = p.getRawYCoord().toBigInteger().toByteArray(); + + int pxStart = px.length > FE_BYTES ? 1 : 0, pxLen = px.length - pxStart; + int pyStart = py.length > FE_BYTES ? 1 : 0, pyLen = py.length - pyStart; + + System.arraycopy(px, pxStart, table, pos + FE_BYTES - pxLen, pxLen); pos += FE_BYTES; + System.arraycopy(py, pyStart, table, pos + FE_BYTES - pyLen, pyLen); pos += FE_BYTES; + } + } + + return new ECLookupTable() + { + public int getSize() + { + return len; + } + + public ECPoint lookup(int index) + { + byte[] x = new byte[FE_BYTES], y = new byte[FE_BYTES]; + int pos = 0; + + for (int i = 0; i < len; ++i) + { + int MASK = ((i ^ index) - 1) >> 31; + + for (int j = 0; j < FE_BYTES; ++j) + { + x[j] ^= table[pos + j] & MASK; + y[j] ^= table[pos + FE_BYTES + j] & MASK; + } + + pos += (FE_BYTES * 2); + } + + return createRawPoint(fromBigInteger(new BigInteger(1, x)), fromBigInteger(new BigInteger(1, y)), false); + } + }; + } + protected void checkPoint(ECPoint point) { if (null == point || (this != point.getCurve())) @@ -542,6 +623,9 @@ public abstract class ECCurve BigInteger q, r; ECPoint.Fp infinity; + /** + * @deprecated use constructor taking order/cofactor + */ public Fp(BigInteger q, BigInteger a, BigInteger b) { this(q, a, b, null, null); @@ -553,7 +637,7 @@ public abstract class ECCurve this.q = q; this.r = ECFieldElement.Fp.calculateResidue(q); - this.infinity = new ECPoint.Fp(this, null, null); + this.infinity = new ECPoint.Fp(this, null, null, false); this.a = fromBigInteger(a); this.b = fromBigInteger(b); @@ -562,6 +646,9 @@ public abstract class ECCurve this.coord = FP_DEFAULT_COORDS; } + /** + * @deprecated use constructor taking order/cofactor + */ protected Fp(BigInteger q, BigInteger r, ECFieldElement a, ECFieldElement b) { this(q, r, a, b, null, null); @@ -573,7 +660,7 @@ public abstract class ECCurve this.q = q; this.r = r; - this.infinity = new ECPoint.Fp(this, null, null); + this.infinity = new ECPoint.Fp(this, null, null, false); this.a = a; this.b = b; @@ -814,7 +901,7 @@ public abstract class ECCurve * @return the solution for <code>z<sup>2</sup> + z = beta</code> or * <code>null</code> if no solution exists. */ - private ECFieldElement solveQuadraticEquation(ECFieldElement beta) + protected ECFieldElement solveQuadraticEquation(ECFieldElement beta) { if (beta.isZero()) { @@ -928,6 +1015,7 @@ public abstract class ECCurve * @param b The coefficient <code>b</code> in the Weierstrass equation * for non-supersingular elliptic curves over * <code>F<sub>2<sup>m</sup></sub></code>. + * @deprecated use constructor taking order/cofactor */ public F2m( int m, @@ -985,6 +1073,7 @@ public abstract class ECCurve * @param b The coefficient <code>b</code> in the Weierstrass equation * for non-supersingular elliptic curves over * <code>F<sub>2<sup>m</sup></sub></code>. + * @deprecated use constructor taking order/cofactor */ public F2m( int m, @@ -1039,7 +1128,7 @@ public abstract class ECCurve this.order = order; this.cofactor = cofactor; - this.infinity = new ECPoint.F2m(this, null, null); + this.infinity = new ECPoint.F2m(this, null, null, false); this.a = fromBigInteger(a); this.b = fromBigInteger(b); this.coord = F2M_DEFAULT_COORDS; @@ -1056,7 +1145,7 @@ public abstract class ECCurve this.order = order; this.cofactor = cofactor; - this.infinity = new ECPoint.F2m(this, null, null); + this.infinity = new ECPoint.F2m(this, null, null, false); this.a = a; this.b = b; this.coord = F2M_DEFAULT_COORDS; @@ -1145,20 +1234,50 @@ public abstract class ECCurve return k3; } - /** - * @deprecated use {@link #getOrder()} instead - */ - public BigInteger getN() + public ECLookupTable createCacheSafeLookupTable(ECPoint[] points, int off, final int len) { - return this.order; - } + final int FE_LONGS = (m + 63) >>> 6; + final int[] ks = isTrinomial() ? new int[]{ k1 } : new int[]{ k1, k2, k3 }; - /** - * @deprecated use {@link #getCofactor()} instead - */ - public BigInteger getH() - { - return this.cofactor; + final long[] table = new long[len * FE_LONGS * 2]; + { + int pos = 0; + for (int i = 0; i < len; ++i) + { + ECPoint p = points[off + i]; + ((ECFieldElement.F2m)p.getRawXCoord()).x.copyTo(table, pos); pos += FE_LONGS; + ((ECFieldElement.F2m)p.getRawYCoord()).x.copyTo(table, pos); pos += FE_LONGS; + } + } + + return new ECLookupTable() + { + public int getSize() + { + return len; + } + + public ECPoint lookup(int index) + { + long[] x = Nat.create64(FE_LONGS), y = Nat.create64(FE_LONGS); + int pos = 0; + + for (int i = 0; i < len; ++i) + { + long MASK = ((i ^ index) - 1) >> 31; + + for (int j = 0; j < FE_LONGS; ++j) + { + x[j] ^= table[pos + j] & MASK; + y[j] ^= table[pos + FE_LONGS + j] & MASK; + } + + pos += (FE_LONGS * 2); + } + + return createRawPoint(new ECFieldElement.F2m(m, ks, new LongArray(x)), new ECFieldElement.F2m(m, ks, new LongArray(y)), false); + } + }; } } } diff --git a/bcprov/src/main/java/org/bouncycastle/math/ec/ECFieldElement.java b/bcprov/src/main/java/org/bouncycastle/math/ec/ECFieldElement.java index 18409c09..49d1c2f1 100644 --- a/bcprov/src/main/java/org/bouncycastle/math/ec/ECFieldElement.java +++ b/bcprov/src/main/java/org/bouncycastle/math/ec/ECFieldElement.java @@ -24,6 +24,11 @@ public abstract class ECFieldElement public abstract ECFieldElement invert(); public abstract ECFieldElement sqrt(); + public ECFieldElement() + { + + } + public int bitLength() { return toBigInteger().bitLength(); @@ -84,7 +89,11 @@ public abstract class ECFieldElement return BigIntegers.asUnsignedByteArray((getFieldSize() + 7) / 8, toBigInteger()); } - public static class Fp extends ECFieldElement + public static abstract class AbstractFp extends ECFieldElement + { + } + + public static class Fp extends AbstractFp { BigInteger q, r, x; @@ -491,6 +500,49 @@ public abstract class ECFieldElement } } + public static abstract class AbstractF2m extends ECFieldElement + { + public ECFieldElement halfTrace() + { + int m = this.getFieldSize(); + if ((m & 1) == 0) + { + throw new IllegalStateException("Half-trace only defined for odd m"); + } + + ECFieldElement fe = this; + ECFieldElement ht = fe; + for (int i = 2; i < m; i += 2) + { + fe = fe.squarePow(2); + ht = ht.add(fe); + } + + return ht; + } + + public int trace() + { + int m = this.getFieldSize(); + ECFieldElement fe = this; + ECFieldElement tr = fe; + for (int i = 1; i < m; ++i) + { + fe = fe.square(); + tr = tr.add(fe); + } + if (tr.isZero()) + { + return 0; + } + if (tr.isOne()) + { + return 1; + } + throw new IllegalStateException("Internal error in trace calculation"); + } + } + /** * Class representing the Elements of the finite field * <code>F<sub>2<sup>m</sup></sub></code> in polynomial basis (PB) @@ -498,7 +550,7 @@ public abstract class ECFieldElement * basis representations are supported. Gaussian normal basis (GNB) * representation is not supported. */ - public static class F2m extends ECFieldElement + public static class F2m extends AbstractF2m { /** * Indicates gaussian normal basis representation (GNB). Number chosen @@ -533,7 +585,7 @@ public abstract class ECFieldElement /** * The <code>LongArray</code> holding the bits. */ - private LongArray x; + LongArray x; /** * Constructor for PPB. @@ -588,23 +640,7 @@ public abstract class ECFieldElement this.x = new LongArray(x); } - /** - * Constructor for TPB. - * @param m The exponent <code>m</code> of - * <code>F<sub>2<sup>m</sup></sub></code>. - * @param k The integer <code>k</code> where <code>x<sup>m</sup> + - * x<sup>k</sup> + 1</code> represents the reduction - * polynomial <code>f(z)</code>. - * @param x The BigInteger representing the value of the field element. - * @deprecated Use ECCurve.fromBigInteger to construct field elements - */ - public F2m(int m, int k, BigInteger x) - { - // Set k1 to k, and set k2 and k3 to 0 - this(m, k, 0, 0, x); - } - - private F2m(int m, int[] ks, LongArray x) + F2m(int m, int[] ks, LongArray x) { this.m = m; this.representation = (ks.length == 1) ? TPB : PPB; diff --git a/bcprov/src/main/java/org/bouncycastle/math/ec/ECLookupTable.java b/bcprov/src/main/java/org/bouncycastle/math/ec/ECLookupTable.java new file mode 100644 index 00000000..7ff5c6a4 --- /dev/null +++ b/bcprov/src/main/java/org/bouncycastle/math/ec/ECLookupTable.java @@ -0,0 +1,7 @@ +package org.bouncycastle.math.ec; + +public interface ECLookupTable +{ + int getSize(); + ECPoint lookup(int index); +} diff --git a/bcprov/src/main/java/org/bouncycastle/math/ec/ECPoint.java b/bcprov/src/main/java/org/bouncycastle/math/ec/ECPoint.java index 0ea5026c..57dfa339 100644 --- a/bcprov/src/main/java/org/bouncycastle/math/ec/ECPoint.java +++ b/bcprov/src/main/java/org/bouncycastle/math/ec/ECPoint.java @@ -8,7 +8,7 @@ import java.util.Hashtable; */ public abstract class ECPoint { - protected static ECFieldElement[] EMPTY_ZS = new ECFieldElement[0]; + protected final static ECFieldElement[] EMPTY_ZS = new ECFieldElement[0]; protected static ECFieldElement[] getInitialZCoords(ECCurve curve) { @@ -64,13 +64,21 @@ public abstract class ECPoint this.zs = zs; } - protected boolean satisfiesCofactor() + protected abstract boolean satisfiesCurveEquation(); + + protected boolean satisfiesOrder() { - BigInteger h = curve.getCofactor(); - return h == null || h.equals(ECConstants.ONE) || !ECAlgorithms.referenceMultiply(this, h).isInfinity(); - } + if (ECConstants.ONE.equals(curve.getCofactor())) + { + return true; + } - protected abstract boolean satisfiesCurveEquation(); + BigInteger n = curve.getOrder(); + + // TODO Require order to be available for all curves + + return n == null || ECAlgorithms.referenceMultiply(this, n).isInfinity(); + } public final ECPoint getDetachedPoint() { @@ -91,33 +99,6 @@ public abstract class ECPoint } /** - * Normalizes this point, and then returns the affine x-coordinate. - * - * Note: normalization can be expensive, this method is deprecated in favour - * of caller-controlled normalization. - * - * @deprecated Use getAffineXCoord(), or normalize() and getXCoord(), instead - */ - public ECFieldElement getX() - { - return normalize().getXCoord(); - } - - - /** - * Normalizes this point, and then returns the affine y-coordinate. - * - * Note: normalization can be expensive, this method is deprecated in favour - * of caller-controlled normalization. - * - * @deprecated Use getAffineYCoord(), or normalize() and getYCoord(), instead - */ - public ECFieldElement getY() - { - return normalize().getYCoord(); - } - - /** * Returns the affine x-coordinate after checking that this point is normalized. * * @return The affine x-coordinate of this point @@ -297,28 +278,58 @@ public abstract class ECPoint public boolean isValid() { + return implIsValid(false, true); + } + + boolean isValidPartial() + { + return implIsValid(false, false); + } + + boolean implIsValid(final boolean decompressed, final boolean checkOrder) + { if (isInfinity()) { return true; } - // TODO Sanity-check the field elements - - ECCurve curve = getCurve(); - if (curve != null) + ValidityPrecompInfo validity = (ValidityPrecompInfo)getCurve().precompute(this, ValidityPrecompInfo.PRECOMP_NAME, new PreCompCallback() { - if (!satisfiesCurveEquation()) + public PreCompInfo precompute(PreCompInfo existing) { - return false; - } + ValidityPrecompInfo info = (existing instanceof ValidityPrecompInfo) ? (ValidityPrecompInfo)existing : null; + if (info == null) + { + info = new ValidityPrecompInfo(); + } - if (!satisfiesCofactor()) - { - return false; + if (info.hasFailed()) + { + return info; + } + if (!info.hasCurveEquationPassed()) + { + if (!decompressed && !satisfiesCurveEquation()) + { + info.reportFailed(); + return info; + } + info.reportCurveEquationPassed(); + } + if (checkOrder && !info.hasOrderPassed()) + { + if (!satisfiesOrder()) + { + info.reportFailed(); + return info; + } + info.reportOrderPassed(); + } + return info; } - } + }); - return true; + return !validity.hasFailed(); } public ECPoint scaleX(ECFieldElement scale) @@ -440,6 +451,7 @@ public abstract class ECPoint /** * @deprecated per-point compression property will be removed, refer {@link #getEncoded(boolean)} + * @return a byte encoding. */ public byte[] getEncoded() { @@ -602,20 +614,6 @@ public abstract class ECPoint public static class Fp extends AbstractFp { /** - * Create a point which encodes without point compression. - * - * @param curve the curve to use - * @param x affine x co-ordinate - * @param y affine y co-ordinate - * - * @deprecated Use ECCurve.createPoint to construct points - */ - public Fp(ECCurve curve, ECFieldElement x, ECFieldElement y) - { - this(curve, x, y, false); - } - - /** * Create a point that encodes with or without point compression. * * @param curve the curve to use @@ -646,7 +644,7 @@ public abstract class ECPoint protected ECPoint detach() { - return new ECPoint.Fp(null, this.getAffineXCoord(), this.getAffineYCoord()); + return new ECPoint.Fp(null, this.getAffineXCoord(), this.getAffineYCoord(), false); } public ECFieldElement getZCoord(int index) @@ -1423,6 +1421,46 @@ public abstract class ECPoint return lhs.equals(rhs); } + protected boolean satisfiesOrder() + { + BigInteger cofactor = curve.getCofactor(); + if (ECConstants.TWO.equals(cofactor)) + { + /* + * Check that the trace of (X + A) is 0, then there exists a solution to L^2 + L = X + A, + * and so a halving is possible, so this point is the double of another. + */ + ECPoint N = this.normalize(); + ECFieldElement X = N.getAffineXCoord(); + ECFieldElement rhs = X.add(curve.getA()); + return ((ECFieldElement.AbstractF2m)rhs).trace() == 0; + } + if (ECConstants.FOUR.equals(cofactor)) + { + /* + * Solve L^2 + L = X + A to find the half of this point, if it exists (fail if not). + * Generate both possibilities for the square of the half-point's x-coordinate (w), + * and check if Tr(w + A) == 0 for at least one; then a second halving is possible + * (see comments for cofactor 2 above), so this point is four times another. + * + * Note: Tr(x^2) == Tr(x). + */ + ECPoint N = this.normalize(); + ECFieldElement X = N.getAffineXCoord(); + ECFieldElement lambda = ((ECCurve.AbstractF2m)curve).solveQuadraticEquation(X.add(curve.getA())); + if (lambda == null) + { + return false; + } + ECFieldElement w = X.multiply(lambda).add(N.getAffineYCoord()); + ECFieldElement t = w.add(curve.getA()); + return ((ECFieldElement.AbstractF2m)t).trace() == 0 + || ((ECFieldElement.AbstractF2m)(t.add(X))).trace() == 0; + } + + return super.satisfiesOrder(); + } + public ECPoint scaleX(ECFieldElement scale) { if (this.isInfinity()) @@ -1580,18 +1618,6 @@ public abstract class ECPoint * @param curve base curve * @param x x point * @param y y point - * - * @deprecated Use ECCurve.createPoint to construct points - */ - public F2m(ECCurve curve, ECFieldElement x, ECFieldElement y) - { - this(curve, x, y, false); - } - - /** - * @param curve base curve - * @param x x point - * @param y y point * @param withCompression true if encode with point compression. * * @deprecated per-point compression property will be removed, refer {@link #getEncoded(boolean)} @@ -1633,7 +1659,7 @@ public abstract class ECPoint protected ECPoint detach() { - return new ECPoint.F2m(null, this.getAffineXCoord(), this.getAffineYCoord()); // earlier JDK + return new ECPoint.F2m(null, this.getAffineXCoord(), this.getAffineYCoord(), false); // earlier JDK } public ECFieldElement getYCoord() diff --git a/bcprov/src/main/java/org/bouncycastle/math/ec/FixedPointCombMultiplier.java b/bcprov/src/main/java/org/bouncycastle/math/ec/FixedPointCombMultiplier.java index c91de7b1..f3dad929 100644 --- a/bcprov/src/main/java/org/bouncycastle/math/ec/FixedPointCombMultiplier.java +++ b/bcprov/src/main/java/org/bouncycastle/math/ec/FixedPointCombMultiplier.java @@ -2,6 +2,8 @@ package org.bouncycastle.math.ec; import java.math.BigInteger; +import org.bouncycastle.math.raw.Nat; + public class FixedPointCombMultiplier extends AbstractECMultiplier { protected ECPoint multiplyPositive(ECPoint p, BigInteger k) @@ -20,38 +22,35 @@ public class FixedPointCombMultiplier extends AbstractECMultiplier throw new IllegalStateException("fixed-point comb doesn't support scalars larger than the curve order"); } - int minWidth = getWidthForCombSize(size); - - FixedPointPreCompInfo info = FixedPointUtil.precompute(p, minWidth); - ECPoint[] lookupTable = info.getPreComp(); + FixedPointPreCompInfo info = FixedPointUtil.precompute(p); + ECLookupTable lookupTable = info.getLookupTable(); int width = info.getWidth(); int d = (size + width - 1) / width; ECPoint R = c.getInfinity(); - int top = d * width - 1; + int fullComb = d * width; + int[] K = Nat.fromBigInteger(fullComb, k); + + int top = fullComb - 1; for (int i = 0; i < d; ++i) { - int index = 0; + int secretIndex = 0; for (int j = top - i; j >= 0; j -= d) { - index <<= 1; - if (k.testBit(j)) - { - index |= 1; - } + int secretBit = K[j >>> 5] >>> (j & 0x1F); + secretIndex ^= secretBit >>> 1; + secretIndex <<= 1; + secretIndex ^= secretBit; } - R = R.twicePlus(lookupTable[index]); + ECPoint add = lookupTable.lookup(secretIndex); + + R = R.twicePlus(add); } return R.add(info.getOffset()); } - - protected int getWidthForCombSize(int combSize) - { - return combSize > 257 ? 6 : 5; - } } diff --git a/bcprov/src/main/java/org/bouncycastle/math/ec/FixedPointPreCompInfo.java b/bcprov/src/main/java/org/bouncycastle/math/ec/FixedPointPreCompInfo.java index 31f5d101..93889e1f 100644 --- a/bcprov/src/main/java/org/bouncycastle/math/ec/FixedPointPreCompInfo.java +++ b/bcprov/src/main/java/org/bouncycastle/math/ec/FixedPointPreCompInfo.java @@ -8,10 +8,9 @@ public class FixedPointPreCompInfo implements PreCompInfo protected ECPoint offset = null; /** - * Array holding the precomputed <code>ECPoint</code>s used for a fixed - * point multiplication. + * Lookup table for the precomputed {@link ECPoint}s used for a fixed point multiplication. */ - protected ECPoint[] preComp = null; + protected ECLookupTable lookupTable = null; /** * The width used for the precomputation. If a larger width precomputation @@ -20,24 +19,24 @@ public class FixedPointPreCompInfo implements PreCompInfo */ protected int width = -1; - public ECPoint getOffset() + public ECLookupTable getLookupTable() { - return offset; + return lookupTable; } - public void setOffset(ECPoint offset) + public void setLookupTable(ECLookupTable lookupTable) { - this.offset = offset; + this.lookupTable = lookupTable; } - public ECPoint[] getPreComp() + public ECPoint getOffset() { - return preComp; + return offset; } - public void setPreComp(ECPoint[] preComp) + public void setOffset(ECPoint offset) { - this.preComp = preComp; + this.offset = offset; } public int getWidth() diff --git a/bcprov/src/main/java/org/bouncycastle/math/ec/FixedPointUtil.java b/bcprov/src/main/java/org/bouncycastle/math/ec/FixedPointUtil.java index 93b435c5..6b81d236 100644 --- a/bcprov/src/main/java/org/bouncycastle/math/ec/FixedPointUtil.java +++ b/bcprov/src/main/java/org/bouncycastle/math/ec/FixedPointUtil.java @@ -14,62 +14,74 @@ public class FixedPointUtil public static FixedPointPreCompInfo getFixedPointPreCompInfo(PreCompInfo preCompInfo) { - if ((preCompInfo != null) && (preCompInfo instanceof FixedPointPreCompInfo)) - { - return (FixedPointPreCompInfo)preCompInfo; - } - - return new FixedPointPreCompInfo(); + return (preCompInfo instanceof FixedPointPreCompInfo) ? (FixedPointPreCompInfo)preCompInfo : null; } - public static FixedPointPreCompInfo precompute(ECPoint p, int minWidth) + public static FixedPointPreCompInfo precompute(final ECPoint p) { - ECCurve c = p.getCurve(); - - int n = 1 << minWidth; - FixedPointPreCompInfo info = getFixedPointPreCompInfo(c.getPreCompInfo(p, PRECOMP_NAME)); - ECPoint[] lookupTable = info.getPreComp(); + final ECCurve c = p.getCurve(); - if (lookupTable == null || lookupTable.length < n) + return (FixedPointPreCompInfo)c.precompute(p, PRECOMP_NAME, new PreCompCallback() { - int bits = getCombSize(c); - int d = (bits + minWidth - 1) / minWidth; - - ECPoint[] pow2Table = new ECPoint[minWidth + 1]; - pow2Table[0] = p; - for (int i = 1; i < minWidth; ++i) + public PreCompInfo precompute(PreCompInfo existing) { - pow2Table[i] = pow2Table[i - 1].timesPow2(d); - } + FixedPointPreCompInfo existingFP = (existing instanceof FixedPointPreCompInfo) ? (FixedPointPreCompInfo)existing : null; - // This will be the 'offset' value - pow2Table[minWidth] = pow2Table[0].subtract(pow2Table[1]); + int bits = getCombSize(c); + int minWidth = bits > 250 ? 6 : 5; + int n = 1 << minWidth; - c.normalizeAll(pow2Table); + if (checkExisting(existingFP, n)) + { + return existingFP; + } - lookupTable = new ECPoint[n]; - lookupTable[0] = pow2Table[0]; + int d = (bits + minWidth - 1) / minWidth; - for (int bit = minWidth - 1; bit >= 0; --bit) - { - ECPoint pow2 = pow2Table[bit]; + ECPoint[] pow2Table = new ECPoint[minWidth + 1]; + pow2Table[0] = p; + for (int i = 1; i < minWidth; ++i) + { + pow2Table[i] = pow2Table[i - 1].timesPow2(d); + } - int step = 1 << bit; - for (int i = step; i < n; i += (step << 1)) + // This will be the 'offset' value + pow2Table[minWidth] = pow2Table[0].subtract(pow2Table[1]); + + c.normalizeAll(pow2Table); + + ECPoint[] lookupTable = new ECPoint[n]; + lookupTable[0] = pow2Table[0]; + + for (int bit = minWidth - 1; bit >= 0; --bit) { - lookupTable[i] = lookupTable[i - step].add(pow2); + ECPoint pow2 = pow2Table[bit]; + + int step = 1 << bit; + for (int i = step; i < n; i += (step << 1)) + { + lookupTable[i] = lookupTable[i - step].add(pow2); + } } - } - c.normalizeAll(lookupTable); + c.normalizeAll(lookupTable); - info.setOffset(pow2Table[minWidth]); - info.setPreComp(lookupTable); - info.setWidth(minWidth); + FixedPointPreCompInfo result = new FixedPointPreCompInfo(); + result.setLookupTable(c.createCacheSafeLookupTable(lookupTable, 0, lookupTable.length)); + result.setOffset(pow2Table[minWidth]); + result.setWidth(minWidth); + return result; + } - c.setPreCompInfo(p, PRECOMP_NAME, info); - } + private boolean checkExisting(FixedPointPreCompInfo existingFP, int n) + { + return existingFP != null && checkTable(existingFP.getLookupTable(), n); + } - return info; + private boolean checkTable(ECLookupTable table, int n) + { + return table != null && table.getSize() >= n; + } + }); } } diff --git a/bcprov/src/main/java/org/bouncycastle/math/ec/LongArray.java b/bcprov/src/main/java/org/bouncycastle/math/ec/LongArray.java index b963118a..b9a1535f 100644 --- a/bcprov/src/main/java/org/bouncycastle/math/ec/LongArray.java +++ b/bcprov/src/main/java/org/bouncycastle/math/ec/LongArray.java @@ -373,6 +373,11 @@ class LongArray implements Cloneable } } + void copyTo(long[] z, int zOff) + { + System.arraycopy(m_ints, 0, z, zOff, m_ints.length); + } + public boolean isOne() { long[] a = m_ints; diff --git a/bcprov/src/main/java/org/bouncycastle/math/ec/PreCompCallback.java b/bcprov/src/main/java/org/bouncycastle/math/ec/PreCompCallback.java new file mode 100644 index 00000000..5cbd8d02 --- /dev/null +++ b/bcprov/src/main/java/org/bouncycastle/math/ec/PreCompCallback.java @@ -0,0 +1,6 @@ +package org.bouncycastle.math.ec; + +public interface PreCompCallback +{ + PreCompInfo precompute(PreCompInfo existing); +} diff --git a/bcprov/src/main/java/org/bouncycastle/math/ec/ValidityPrecompInfo.java b/bcprov/src/main/java/org/bouncycastle/math/ec/ValidityPrecompInfo.java new file mode 100644 index 00000000..d3a3ce31 --- /dev/null +++ b/bcprov/src/main/java/org/bouncycastle/math/ec/ValidityPrecompInfo.java @@ -0,0 +1,40 @@ +package org.bouncycastle.math.ec; + +class ValidityPrecompInfo implements PreCompInfo +{ + static final String PRECOMP_NAME = "bc_validity"; + + private boolean failed = false; + private boolean curveEquationPassed = false; + private boolean orderPassed = false; + + boolean hasFailed() + { + return failed; + } + + void reportFailed() + { + failed = true; + } + + boolean hasCurveEquationPassed() + { + return curveEquationPassed; + } + + void reportCurveEquationPassed() + { + curveEquationPassed = true; + } + + boolean hasOrderPassed() + { + return orderPassed; + } + + void reportOrderPassed() + { + orderPassed = true; + } +} diff --git a/bcprov/src/main/java/org/bouncycastle/math/ec/WNafUtil.java b/bcprov/src/main/java/org/bouncycastle/math/ec/WNafUtil.java index 301b5aee..f383308a 100644 --- a/bcprov/src/main/java/org/bouncycastle/math/ec/WNafUtil.java +++ b/bcprov/src/main/java/org/bouncycastle/math/ec/WNafUtil.java @@ -304,12 +304,7 @@ public abstract class WNafUtil public static WNafPreCompInfo getWNafPreCompInfo(PreCompInfo preCompInfo) { - if ((preCompInfo != null) && (preCompInfo instanceof WNafPreCompInfo)) - { - return (WNafPreCompInfo)preCompInfo; - } - - return new WNafPreCompInfo(); + return (preCompInfo instanceof WNafPreCompInfo) ? (WNafPreCompInfo)preCompInfo : null; } /** @@ -343,178 +338,214 @@ public abstract class WNafUtil return w + 2; } - public static ECPoint mapPointWithPrecomp(ECPoint p, int width, boolean includeNegated, - ECPointMap pointMap) + public static ECPoint mapPointWithPrecomp(ECPoint p, final int width, final boolean includeNegated, + final ECPointMap pointMap) { - ECCurve c = p.getCurve(); - WNafPreCompInfo wnafPreCompP = precompute(p, width, includeNegated); + final ECCurve c = p.getCurve(); + final WNafPreCompInfo wnafPreCompP = precompute(p, width, includeNegated); ECPoint q = pointMap.map(p); - WNafPreCompInfo wnafPreCompQ = getWNafPreCompInfo(c.getPreCompInfo(q, PRECOMP_NAME)); - - ECPoint twiceP = wnafPreCompP.getTwice(); - if (twiceP != null) + c.precompute(q, PRECOMP_NAME, new PreCompCallback() { - ECPoint twiceQ = pointMap.map(twiceP); - wnafPreCompQ.setTwice(twiceQ); - } + public PreCompInfo precompute(PreCompInfo existing) + { + WNafPreCompInfo result = new WNafPreCompInfo(); - ECPoint[] preCompP = wnafPreCompP.getPreComp(); - ECPoint[] preCompQ = new ECPoint[preCompP.length]; - for (int i = 0; i < preCompP.length; ++i) - { - preCompQ[i] = pointMap.map(preCompP[i]); - } - wnafPreCompQ.setPreComp(preCompQ); + ECPoint twiceP = wnafPreCompP.getTwice(); + if (twiceP != null) + { + ECPoint twiceQ = pointMap.map(twiceP); + result.setTwice(twiceQ); + } - if (includeNegated) - { - ECPoint[] preCompNegQ = new ECPoint[preCompQ.length]; - for (int i = 0; i < preCompNegQ.length; ++i) - { - preCompNegQ[i] = preCompQ[i].negate(); - } - wnafPreCompQ.setPreCompNeg(preCompNegQ); - } + ECPoint[] preCompP = wnafPreCompP.getPreComp(); + ECPoint[] preCompQ = new ECPoint[preCompP.length]; + for (int i = 0; i < preCompP.length; ++i) + { + preCompQ[i] = pointMap.map(preCompP[i]); + } + result.setPreComp(preCompQ); + + if (includeNegated) + { + ECPoint[] preCompNegQ = new ECPoint[preCompQ.length]; + for (int i = 0; i < preCompNegQ.length; ++i) + { + preCompNegQ[i] = preCompQ[i].negate(); + } + result.setPreCompNeg(preCompNegQ); + } - c.setPreCompInfo(q, PRECOMP_NAME, wnafPreCompQ); + return result; + } + }); return q; } - public static WNafPreCompInfo precompute(ECPoint p, int width, boolean includeNegated) + public static WNafPreCompInfo precompute(final ECPoint p, final int width, final boolean includeNegated) { - ECCurve c = p.getCurve(); - WNafPreCompInfo wnafPreCompInfo = getWNafPreCompInfo(c.getPreCompInfo(p, PRECOMP_NAME)); + final ECCurve c = p.getCurve(); - int iniPreCompLen = 0, reqPreCompLen = 1 << Math.max(0, width - 2); - - ECPoint[] preComp = wnafPreCompInfo.getPreComp(); - if (preComp == null) - { - preComp = EMPTY_POINTS; - } - else + return (WNafPreCompInfo)c.precompute(p, PRECOMP_NAME, new PreCompCallback() { - iniPreCompLen = preComp.length; - } + public PreCompInfo precompute(PreCompInfo existing) + { + WNafPreCompInfo existingWNaf = (existing instanceof WNafPreCompInfo) ? (WNafPreCompInfo)existing : null; - if (iniPreCompLen < reqPreCompLen) - { - preComp = resizeTable(preComp, reqPreCompLen); + int reqPreCompLen = 1 << Math.max(0, width - 2); - if (reqPreCompLen == 1) - { - preComp[0] = p.normalize(); - } - else - { - int curPreCompLen = iniPreCompLen; - if (curPreCompLen == 0) + if (checkExisting(existingWNaf, reqPreCompLen, includeNegated)) { - preComp[0] = p; - curPreCompLen = 1; + return existingWNaf; } - ECFieldElement iso = null; + ECPoint[] preComp = null, preCompNeg = null; + ECPoint twiceP = null; + + if (existingWNaf != null) + { + preComp = existingWNaf.getPreComp(); + preCompNeg = existingWNaf.getPreCompNeg(); + twiceP = existingWNaf.getTwice(); + } - if (reqPreCompLen == 2) + int iniPreCompLen = 0; + if (preComp == null) { - preComp[1] = p.threeTimes(); + preComp = EMPTY_POINTS; } else { - ECPoint twiceP = wnafPreCompInfo.getTwice(), last = preComp[curPreCompLen - 1]; - if (twiceP == null) - { - twiceP = preComp[0].twice(); - wnafPreCompInfo.setTwice(twiceP); + iniPreCompLen = preComp.length; + } - /* - * For Fp curves with Jacobian projective coordinates, use a (quasi-)isomorphism - * where 'twiceP' is "affine", so that the subsequent additions are cheaper. This - * also requires scaling the initial point's X, Y coordinates, and reversing the - * isomorphism as part of the subsequent normalization. - * - * NOTE: The correctness of this optimization depends on: - * 1) additions do not use the curve's A, B coefficients. - * 2) no special cases (i.e. Q +/- Q) when calculating 1P, 3P, 5P, ... - */ - if (!twiceP.isInfinity() && ECAlgorithms.isFpCurve(c) && c.getFieldSize() >= 64) + if (iniPreCompLen < reqPreCompLen) + { + preComp = resizeTable(preComp, reqPreCompLen); + + if (reqPreCompLen == 1) + { + preComp[0] = p.normalize(); + } + else + { + int curPreCompLen = iniPreCompLen; + if (curPreCompLen == 0) { - switch (c.getCoordinateSystem()) - { - case ECCurve.COORD_JACOBIAN: - case ECCurve.COORD_JACOBIAN_CHUDNOVSKY: - case ECCurve.COORD_JACOBIAN_MODIFIED: - { - iso = twiceP.getZCoord(0); - twiceP = c.createPoint(twiceP.getXCoord().toBigInteger(), twiceP.getYCoord() - .toBigInteger()); + preComp[0] = p; + curPreCompLen = 1; + } - ECFieldElement iso2 = iso.square(), iso3 = iso2.multiply(iso); - last = last.scaleX(iso2).scaleY(iso3); + ECFieldElement iso = null; - if (iniPreCompLen == 0) + if (reqPreCompLen == 2) + { + preComp[1] = p.threeTimes(); + } + else + { + ECPoint isoTwiceP = twiceP, last = preComp[curPreCompLen - 1]; + if (isoTwiceP == null) + { + isoTwiceP = preComp[0].twice(); + twiceP = isoTwiceP; + + /* + * For Fp curves with Jacobian projective coordinates, use a (quasi-)isomorphism + * where 'twiceP' is "affine", so that the subsequent additions are cheaper. This + * also requires scaling the initial point's X, Y coordinates, and reversing the + * isomorphism as part of the subsequent normalization. + * + * NOTE: The correctness of this optimization depends on: + * 1) additions do not use the curve's A, B coefficients. + * 2) no special cases (i.e. Q +/- Q) when calculating 1P, 3P, 5P, ... + */ + if (!twiceP.isInfinity() && ECAlgorithms.isFpCurve(c) && c.getFieldSize() >= 64) { - preComp[0] = last; + switch (c.getCoordinateSystem()) + { + case ECCurve.COORD_JACOBIAN: + case ECCurve.COORD_JACOBIAN_CHUDNOVSKY: + case ECCurve.COORD_JACOBIAN_MODIFIED: + { + iso = twiceP.getZCoord(0); + isoTwiceP = c.createPoint(twiceP.getXCoord().toBigInteger(), twiceP.getYCoord() + .toBigInteger()); + + ECFieldElement iso2 = iso.square(), iso3 = iso2.multiply(iso); + last = last.scaleX(iso2).scaleY(iso3); + + if (iniPreCompLen == 0) + { + preComp[0] = last; + } + break; + } + } } - break; } + + while (curPreCompLen < reqPreCompLen) + { + /* + * Compute the new ECPoints for the precomputation array. The values 1, 3, + * 5, ..., 2^(width-1)-1 times p are computed + */ + preComp[curPreCompLen++] = last = last.add(isoTwiceP); } } - } - while (curPreCompLen < reqPreCompLen) - { /* - * Compute the new ECPoints for the precomputation array. The values 1, 3, - * 5, ..., 2^(width-1)-1 times p are computed + * Having oft-used operands in affine form makes operations faster. */ - preComp[curPreCompLen++] = last = last.add(twiceP); + c.normalizeAll(preComp, iniPreCompLen, reqPreCompLen - iniPreCompLen, iso); } } - /* - * Having oft-used operands in affine form makes operations faster. - */ - c.normalizeAll(preComp, iniPreCompLen, reqPreCompLen - iniPreCompLen, iso); - } - } + if (includeNegated) + { + int pos; + if (preCompNeg == null) + { + pos = 0; + preCompNeg = new ECPoint[reqPreCompLen]; + } + else + { + pos = preCompNeg.length; + if (pos < reqPreCompLen) + { + preCompNeg = resizeTable(preCompNeg, reqPreCompLen); + } + } - wnafPreCompInfo.setPreComp(preComp); + while (pos < reqPreCompLen) + { + preCompNeg[pos] = preComp[pos].negate(); + ++pos; + } + } - if (includeNegated) - { - ECPoint[] preCompNeg = wnafPreCompInfo.getPreCompNeg(); - - int pos; - if (preCompNeg == null) - { - pos = 0; - preCompNeg = new ECPoint[reqPreCompLen]; + WNafPreCompInfo result = new WNafPreCompInfo(); + result.setPreComp(preComp); + result.setPreCompNeg(preCompNeg); + result.setTwice(twiceP); + return result; } - else + + private boolean checkExisting(WNafPreCompInfo existingWNaf, int reqPreCompLen, boolean includeNegated) { - pos = preCompNeg.length; - if (pos < reqPreCompLen) - { - preCompNeg = resizeTable(preCompNeg, reqPreCompLen); - } + return existingWNaf != null + && checkTable(existingWNaf.getPreComp(), reqPreCompLen) + && (!includeNegated || checkTable(existingWNaf.getPreCompNeg(), reqPreCompLen)); } - while (pos < reqPreCompLen) + private boolean checkTable(ECPoint[] table, int reqLen) { - preCompNeg[pos] = preComp[pos].negate(); - ++pos; + return table != null && table.length >= reqLen; } - - wnafPreCompInfo.setPreCompNeg(preCompNeg); - } - - c.setPreCompInfo(p, PRECOMP_NAME, wnafPreCompInfo); - - return wnafPreCompInfo; + }); } private static byte[] trim(byte[] a, int length) diff --git a/bcprov/src/main/java/org/bouncycastle/math/ec/WTauNafMultiplier.java b/bcprov/src/main/java/org/bouncycastle/math/ec/WTauNafMultiplier.java index 7974e1d3..0438e1db 100644 --- a/bcprov/src/main/java/org/bouncycastle/math/ec/WTauNafMultiplier.java +++ b/bcprov/src/main/java/org/bouncycastle/math/ec/WTauNafMultiplier.java @@ -36,7 +36,7 @@ public class WTauNafMultiplier extends AbstractECMultiplier ZTauElement rho = Tnaf.partModReduction(k, m, a, s, mu, (byte)10); - return multiplyWTnaf(p, rho, curve.getPreCompInfo(p, PRECOMP_NAME), a, mu); + return multiplyWTnaf(p, rho, a, mu); } /** @@ -49,8 +49,7 @@ public class WTauNafMultiplier extends AbstractECMultiplier * <code>[τ]</code>-adic NAF. * @return <code>p</code> multiplied by <code>λ</code>. */ - private ECPoint.AbstractF2m multiplyWTnaf(ECPoint.AbstractF2m p, ZTauElement lambda, - PreCompInfo preCompInfo, byte a, byte mu) + private ECPoint.AbstractF2m multiplyWTnaf(ECPoint.AbstractF2m p, ZTauElement lambda, byte a, byte mu) { ZTauElement[] alpha = (a == 0) ? Tnaf.alpha0 : Tnaf.alpha1; @@ -59,7 +58,7 @@ public class WTauNafMultiplier extends AbstractECMultiplier byte[]u = Tnaf.tauAdicWNaf(mu, lambda, Tnaf.WIDTH, BigInteger.valueOf(Tnaf.POW_2_WIDTH), tw, alpha); - return multiplyFromWTnaf(p, u, preCompInfo); + return multiplyFromWTnaf(p, u); } /** @@ -71,24 +70,27 @@ public class WTauNafMultiplier extends AbstractECMultiplier * @param u The the WTNAF of <code>λ</code>.. * @return <code>λ * p</code> */ - private static ECPoint.AbstractF2m multiplyFromWTnaf(ECPoint.AbstractF2m p, byte[] u, PreCompInfo preCompInfo) + private static ECPoint.AbstractF2m multiplyFromWTnaf(final ECPoint.AbstractF2m p, byte[] u) { ECCurve.AbstractF2m curve = (ECCurve.AbstractF2m)p.getCurve(); - byte a = curve.getA().toBigInteger().byteValue(); + final byte a = curve.getA().toBigInteger().byteValue(); - ECPoint.AbstractF2m[] pu; - if ((preCompInfo == null) || !(preCompInfo instanceof WTauNafPreCompInfo)) + WTauNafPreCompInfo preCompInfo = (WTauNafPreCompInfo)curve.precompute(p, PRECOMP_NAME, new PreCompCallback() { - pu = Tnaf.getPreComp(p, a); + public PreCompInfo precompute(PreCompInfo existing) + { + if (existing instanceof WTauNafPreCompInfo) + { + return existing; + } + + WTauNafPreCompInfo result = new WTauNafPreCompInfo(); + result.setPreComp(Tnaf.getPreComp(p, a)); + return result; + } + }); - WTauNafPreCompInfo pre = new WTauNafPreCompInfo(); - pre.setPreComp(pu); - curve.setPreCompInfo(p, PRECOMP_NAME, pre); - } - else - { - pu = ((WTauNafPreCompInfo)preCompInfo).getPreComp(); - } + ECPoint.AbstractF2m[] pu = preCompInfo.getPreComp(); // TODO Include negations in precomp (optionally) and use from here ECPoint.AbstractF2m[] puNeg = new ECPoint.AbstractF2m[pu.length]; diff --git a/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP192K1Curve.java b/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP192K1Curve.java index b46cba6a..f160ab31 100644 --- a/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP192K1Curve.java +++ b/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP192K1Curve.java @@ -5,7 +5,9 @@ import java.math.BigInteger; import org.bouncycastle.math.ec.ECConstants; import org.bouncycastle.math.ec.ECCurve; import org.bouncycastle.math.ec.ECFieldElement; +import org.bouncycastle.math.ec.ECLookupTable; import org.bouncycastle.math.ec.ECPoint; +import org.bouncycastle.math.raw.Nat192; import org.bouncycastle.util.encoders.Hex; public class SecP192K1Curve extends ECCurve.AbstractFp @@ -76,4 +78,49 @@ public class SecP192K1Curve extends ECCurve.AbstractFp { return infinity; } + + public ECLookupTable createCacheSafeLookupTable(ECPoint[] points, int off, final int len) + { + final int FE_INTS = 6; + + final int[] table = new int[len * FE_INTS * 2]; + { + int pos = 0; + for (int i = 0; i < len; ++i) + { + ECPoint p = points[off + i]; + Nat192.copy(((SecP192K1FieldElement)p.getRawXCoord()).x, 0, table, pos); pos += FE_INTS; + Nat192.copy(((SecP192K1FieldElement)p.getRawYCoord()).x, 0, table, pos); pos += FE_INTS; + } + } + + return new ECLookupTable() + { + public int getSize() + { + return len; + } + + public ECPoint lookup(int index) + { + int[] x = Nat192.create(), y = Nat192.create(); + int pos = 0; + + for (int i = 0; i < len; ++i) + { + int MASK = ((i ^ index) - 1) >> 31; + + for (int j = 0; j < FE_INTS; ++j) + { + x[j] ^= table[pos + j] & MASK; + y[j] ^= table[pos + FE_INTS + j] & MASK; + } + + pos += (FE_INTS * 2); + } + + return createRawPoint(new SecP192K1FieldElement(x), new SecP192K1FieldElement(y), false); + } + }; + } } diff --git a/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP192K1FieldElement.java b/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP192K1FieldElement.java index 642c44cd..39e62afa 100644 --- a/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP192K1FieldElement.java +++ b/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP192K1FieldElement.java @@ -7,7 +7,7 @@ import org.bouncycastle.math.raw.Mod; import org.bouncycastle.math.raw.Nat192; import org.bouncycastle.util.Arrays; -public class SecP192K1FieldElement extends ECFieldElement +public class SecP192K1FieldElement extends ECFieldElement.AbstractFp { public static final BigInteger Q = SecP192K1Curve.q; diff --git a/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP192R1Curve.java b/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP192R1Curve.java index be67100a..a43a5966 100644 --- a/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP192R1Curve.java +++ b/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP192R1Curve.java @@ -4,7 +4,9 @@ import java.math.BigInteger; import org.bouncycastle.math.ec.ECCurve; import org.bouncycastle.math.ec.ECFieldElement; +import org.bouncycastle.math.ec.ECLookupTable; import org.bouncycastle.math.ec.ECPoint; +import org.bouncycastle.math.raw.Nat192; import org.bouncycastle.util.encoders.Hex; public class SecP192R1Curve extends ECCurve.AbstractFp @@ -77,4 +79,49 @@ public class SecP192R1Curve extends ECCurve.AbstractFp { return infinity; } + + public ECLookupTable createCacheSafeLookupTable(ECPoint[] points, int off, final int len) + { + final int FE_INTS = 6; + + final int[] table = new int[len * FE_INTS * 2]; + { + int pos = 0; + for (int i = 0; i < len; ++i) + { + ECPoint p = points[off + i]; + Nat192.copy(((SecP192R1FieldElement)p.getRawXCoord()).x, 0, table, pos); pos += FE_INTS; + Nat192.copy(((SecP192R1FieldElement)p.getRawYCoord()).x, 0, table, pos); pos += FE_INTS; + } + } + + return new ECLookupTable() + { + public int getSize() + { + return len; + } + + public ECPoint lookup(int index) + { + int[] x = Nat192.create(), y = Nat192.create(); + int pos = 0; + + for (int i = 0; i < len; ++i) + { + int MASK = ((i ^ index) - 1) >> 31; + + for (int j = 0; j < FE_INTS; ++j) + { + x[j] ^= table[pos + j] & MASK; + y[j] ^= table[pos + FE_INTS + j] & MASK; + } + + pos += (FE_INTS * 2); + } + + return createRawPoint(new SecP192R1FieldElement(x), new SecP192R1FieldElement(y), false); + } + }; + } } diff --git a/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP192R1FieldElement.java b/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP192R1FieldElement.java index 68c8080d..15fdcd63 100644 --- a/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP192R1FieldElement.java +++ b/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP192R1FieldElement.java @@ -7,7 +7,7 @@ import org.bouncycastle.math.raw.Mod; import org.bouncycastle.math.raw.Nat192; import org.bouncycastle.util.Arrays; -public class SecP192R1FieldElement extends ECFieldElement +public class SecP192R1FieldElement extends ECFieldElement.AbstractFp { public static final BigInteger Q = SecP192R1Curve.q; diff --git a/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP224K1Curve.java b/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP224K1Curve.java index ad733da6..6b28be79 100644 --- a/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP224K1Curve.java +++ b/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP224K1Curve.java @@ -5,7 +5,9 @@ import java.math.BigInteger; import org.bouncycastle.math.ec.ECConstants; import org.bouncycastle.math.ec.ECCurve; import org.bouncycastle.math.ec.ECFieldElement; +import org.bouncycastle.math.ec.ECLookupTable; import org.bouncycastle.math.ec.ECPoint; +import org.bouncycastle.math.raw.Nat224; import org.bouncycastle.util.encoders.Hex; public class SecP224K1Curve extends ECCurve.AbstractFp @@ -75,4 +77,49 @@ public class SecP224K1Curve extends ECCurve.AbstractFp { return infinity; } + + public ECLookupTable createCacheSafeLookupTable(ECPoint[] points, int off, final int len) + { + final int FE_INTS = 7; + + final int[] table = new int[len * FE_INTS * 2]; + { + int pos = 0; + for (int i = 0; i < len; ++i) + { + ECPoint p = points[off + i]; + Nat224.copy(((SecP224K1FieldElement)p.getRawXCoord()).x, 0, table, pos); pos += FE_INTS; + Nat224.copy(((SecP224K1FieldElement)p.getRawYCoord()).x, 0, table, pos); pos += FE_INTS; + } + } + + return new ECLookupTable() + { + public int getSize() + { + return len; + } + + public ECPoint lookup(int index) + { + int[] x = Nat224.create(), y = Nat224.create(); + int pos = 0; + + for (int i = 0; i < len; ++i) + { + int MASK = ((i ^ index) - 1) >> 31; + + for (int j = 0; j < FE_INTS; ++j) + { + x[j] ^= table[pos + j] & MASK; + y[j] ^= table[pos + FE_INTS + j] & MASK; + } + + pos += (FE_INTS * 2); + } + + return createRawPoint(new SecP224K1FieldElement(x), new SecP224K1FieldElement(y), false); + } + }; + } } diff --git a/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP224K1FieldElement.java b/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP224K1FieldElement.java index 8285a4e9..2093a061 100644 --- a/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP224K1FieldElement.java +++ b/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP224K1FieldElement.java @@ -7,7 +7,7 @@ import org.bouncycastle.math.raw.Mod; import org.bouncycastle.math.raw.Nat224; import org.bouncycastle.util.Arrays; -public class SecP224K1FieldElement extends ECFieldElement +public class SecP224K1FieldElement extends ECFieldElement.AbstractFp { public static final BigInteger Q = SecP224K1Curve.q; diff --git a/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP224R1Curve.java b/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP224R1Curve.java index c8443299..febb323c 100644 --- a/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP224R1Curve.java +++ b/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP224R1Curve.java @@ -4,7 +4,9 @@ import java.math.BigInteger; import org.bouncycastle.math.ec.ECCurve; import org.bouncycastle.math.ec.ECFieldElement; +import org.bouncycastle.math.ec.ECLookupTable; import org.bouncycastle.math.ec.ECPoint; +import org.bouncycastle.math.raw.Nat224; import org.bouncycastle.util.encoders.Hex; public class SecP224R1Curve extends ECCurve.AbstractFp @@ -77,4 +79,49 @@ public class SecP224R1Curve extends ECCurve.AbstractFp { return infinity; } + + public ECLookupTable createCacheSafeLookupTable(ECPoint[] points, int off, final int len) + { + final int FE_INTS = 7; + + final int[] table = new int[len * FE_INTS * 2]; + { + int pos = 0; + for (int i = 0; i < len; ++i) + { + ECPoint p = points[off + i]; + Nat224.copy(((SecP224R1FieldElement)p.getRawXCoord()).x, 0, table, pos); pos += FE_INTS; + Nat224.copy(((SecP224R1FieldElement)p.getRawYCoord()).x, 0, table, pos); pos += FE_INTS; + } + } + + return new ECLookupTable() + { + public int getSize() + { + return len; + } + + public ECPoint lookup(int index) + { + int[] x = Nat224.create(), y = Nat224.create(); + int pos = 0; + + for (int i = 0; i < len; ++i) + { + int MASK = ((i ^ index) - 1) >> 31; + + for (int j = 0; j < FE_INTS; ++j) + { + x[j] ^= table[pos + j] & MASK; + y[j] ^= table[pos + FE_INTS + j] & MASK; + } + + pos += (FE_INTS * 2); + } + + return createRawPoint(new SecP224R1FieldElement(x), new SecP224R1FieldElement(y), false); + } + }; + } } diff --git a/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP224R1FieldElement.java b/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP224R1FieldElement.java index 4a28f3d0..ed2334a7 100644 --- a/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP224R1FieldElement.java +++ b/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP224R1FieldElement.java @@ -8,7 +8,7 @@ import org.bouncycastle.math.raw.Nat; import org.bouncycastle.math.raw.Nat224; import org.bouncycastle.util.Arrays; -public class SecP224R1FieldElement extends ECFieldElement +public class SecP224R1FieldElement extends ECFieldElement.AbstractFp { public static final BigInteger Q = SecP224R1Curve.q; diff --git a/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256K1Curve.java b/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256K1Curve.java index 9b885764..6235381e 100644 --- a/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256K1Curve.java +++ b/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256K1Curve.java @@ -5,7 +5,9 @@ import java.math.BigInteger; import org.bouncycastle.math.ec.ECConstants; import org.bouncycastle.math.ec.ECCurve; import org.bouncycastle.math.ec.ECFieldElement; +import org.bouncycastle.math.ec.ECLookupTable; import org.bouncycastle.math.ec.ECPoint; +import org.bouncycastle.math.raw.Nat256; import org.bouncycastle.util.encoders.Hex; public class SecP256K1Curve extends ECCurve.AbstractFp @@ -75,4 +77,49 @@ public class SecP256K1Curve extends ECCurve.AbstractFp { return infinity; } + + public ECLookupTable createCacheSafeLookupTable(ECPoint[] points, int off, final int len) + { + final int FE_INTS = 8; + + final int[] table = new int[len * FE_INTS * 2]; + { + int pos = 0; + for (int i = 0; i < len; ++i) + { + ECPoint p = points[off + i]; + Nat256.copy(((SecP256K1FieldElement)p.getRawXCoord()).x, 0, table, pos); pos += FE_INTS; + Nat256.copy(((SecP256K1FieldElement)p.getRawYCoord()).x, 0, table, pos); pos += FE_INTS; + } + } + + return new ECLookupTable() + { + public int getSize() + { + return len; + } + + public ECPoint lookup(int index) + { + int[] x = Nat256.create(), y = Nat256.create(); + int pos = 0; + + for (int i = 0; i < len; ++i) + { + int MASK = ((i ^ index) - 1) >> 31; + + for (int j = 0; j < FE_INTS; ++j) + { + x[j] ^= table[pos + j] & MASK; + y[j] ^= table[pos + FE_INTS + j] & MASK; + } + + pos += (FE_INTS * 2); + } + + return createRawPoint(new SecP256K1FieldElement(x), new SecP256K1FieldElement(y), false); + } + }; + } } diff --git a/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256K1FieldElement.java b/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256K1FieldElement.java index 467b17f5..30bca2e3 100644 --- a/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256K1FieldElement.java +++ b/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256K1FieldElement.java @@ -7,7 +7,7 @@ import org.bouncycastle.math.raw.Mod; import org.bouncycastle.math.raw.Nat256; import org.bouncycastle.util.Arrays; -public class SecP256K1FieldElement extends ECFieldElement +public class SecP256K1FieldElement extends ECFieldElement.AbstractFp { public static final BigInteger Q = SecP256K1Curve.q; diff --git a/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256R1Curve.java b/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256R1Curve.java index 5ff6a38d..7d7b51d5 100644 --- a/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256R1Curve.java +++ b/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256R1Curve.java @@ -4,7 +4,9 @@ import java.math.BigInteger; import org.bouncycastle.math.ec.ECCurve; import org.bouncycastle.math.ec.ECFieldElement; +import org.bouncycastle.math.ec.ECLookupTable; import org.bouncycastle.math.ec.ECPoint; +import org.bouncycastle.math.raw.Nat256; import org.bouncycastle.util.encoders.Hex; public class SecP256R1Curve extends ECCurve.AbstractFp @@ -77,4 +79,49 @@ public class SecP256R1Curve extends ECCurve.AbstractFp { return infinity; } + + public ECLookupTable createCacheSafeLookupTable(ECPoint[] points, int off, final int len) + { + final int FE_INTS = 8; + + final int[] table = new int[len * FE_INTS * 2]; + { + int pos = 0; + for (int i = 0; i < len; ++i) + { + ECPoint p = points[off + i]; + Nat256.copy(((SecP256R1FieldElement)p.getRawXCoord()).x, 0, table, pos); pos += FE_INTS; + Nat256.copy(((SecP256R1FieldElement)p.getRawYCoord()).x, 0, table, pos); pos += FE_INTS; + } + } + + return new ECLookupTable() + { + public int getSize() + { + return len; + } + + public ECPoint lookup(int index) + { + int[] x = Nat256.create(), y = Nat256.create(); + int pos = 0; + + for (int i = 0; i < len; ++i) + { + int MASK = ((i ^ index) - 1) >> 31; + + for (int j = 0; j < FE_INTS; ++j) + { + x[j] ^= table[pos + j] & MASK; + y[j] ^= table[pos + FE_INTS + j] & MASK; + } + + pos += (FE_INTS * 2); + } + + return createRawPoint(new SecP256R1FieldElement(x), new SecP256R1FieldElement(y), false); + } + }; + } } diff --git a/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256R1Field.java b/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256R1Field.java index 1e04f4b9..cea1af78 100644 --- a/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256R1Field.java +++ b/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256R1Field.java @@ -16,7 +16,7 @@ public class SecP256R1Field 0xFFFFFFFF, 0xFFFFFFFE, 0x00000001, 0xFFFFFFFE, 0x00000001, 0xFFFFFFFE, 0x00000001, 0x00000001, 0xFFFFFFFE, 0x00000002, 0xFFFFFFFE }; private static final int P7 = 0xFFFFFFFF; - private static final int PExt15 = 0xFFFFFFFF; + private static final int PExt15s1 = 0xFFFFFFFE >>> 1; public static void add(int[] x, int[] y, int[] z) { @@ -30,7 +30,7 @@ public class SecP256R1Field public static void addExt(int[] xx, int[] yy, int[] zz) { int c = Nat.add(16, xx, yy, zz); - if (c != 0 || (zz[15] == PExt15 && Nat.gte(16, zz, PExt))) + if (c != 0 || ((zz[15] >>> 1) >= PExt15s1 && Nat.gte(16, zz, PExt))) { Nat.subFrom(16, PExt, zz); } @@ -78,7 +78,7 @@ public class SecP256R1Field public static void multiplyAddToExt(int[] x, int[] y, int[] zz) { int c = Nat256.mulAddTo(x, y, zz); - if (c != 0 || (zz[15] == PExt15 && Nat.gte(16, zz, PExt))) + if (c != 0 || ((zz[15] >>> 1) >= PExt15s1 && Nat.gte(16, zz, PExt))) { Nat.subFrom(16, PExt, zz); } diff --git a/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256R1FieldElement.java b/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256R1FieldElement.java index be250d10..6be46f24 100644 --- a/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256R1FieldElement.java +++ b/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP256R1FieldElement.java @@ -7,7 +7,7 @@ import org.bouncycastle.math.raw.Mod; import org.bouncycastle.math.raw.Nat256; import org.bouncycastle.util.Arrays; -public class SecP256R1FieldElement extends ECFieldElement +public class SecP256R1FieldElement extends ECFieldElement.AbstractFp { public static final BigInteger Q = SecP256R1Curve.q; diff --git a/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP384R1Curve.java b/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP384R1Curve.java index 27cbcdb2..7a5603d2 100644 --- a/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP384R1Curve.java +++ b/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP384R1Curve.java @@ -4,7 +4,9 @@ import java.math.BigInteger; import org.bouncycastle.math.ec.ECCurve; import org.bouncycastle.math.ec.ECFieldElement; +import org.bouncycastle.math.ec.ECLookupTable; import org.bouncycastle.math.ec.ECPoint; +import org.bouncycastle.math.raw.Nat; import org.bouncycastle.util.encoders.Hex; public class SecP384R1Curve extends ECCurve.AbstractFp @@ -77,4 +79,49 @@ public class SecP384R1Curve extends ECCurve.AbstractFp { return infinity; } + + public ECLookupTable createCacheSafeLookupTable(ECPoint[] points, int off, final int len) + { + final int FE_INTS = 12; + + final int[] table = new int[len * FE_INTS * 2]; + { + int pos = 0; + for (int i = 0; i < len; ++i) + { + ECPoint p = points[off + i]; + Nat.copy(FE_INTS, ((SecP384R1FieldElement)p.getRawXCoord()).x, 0, table, pos); pos += FE_INTS; + Nat.copy(FE_INTS, ((SecP384R1FieldElement)p.getRawYCoord()).x, 0, table, pos); pos += FE_INTS; + } + } + + return new ECLookupTable() + { + public int getSize() + { + return len; + } + + public ECPoint lookup(int index) + { + int[] x = Nat.create(FE_INTS), y = Nat.create(FE_INTS); + int pos = 0; + + for (int i = 0; i < len; ++i) + { + int MASK = ((i ^ index) - 1) >> 31; + + for (int j = 0; j < FE_INTS; ++j) + { + x[j] ^= table[pos + j] & MASK; + y[j] ^= table[pos + FE_INTS + j] & MASK; + } + + pos += (FE_INTS * 2); + } + + return createRawPoint(new SecP384R1FieldElement(x), new SecP384R1FieldElement(y), false); + } + }; + } } diff --git a/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP384R1FieldElement.java b/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP384R1FieldElement.java index 24e585d8..3116b443 100644 --- a/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP384R1FieldElement.java +++ b/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP384R1FieldElement.java @@ -7,7 +7,7 @@ import org.bouncycastle.math.raw.Mod; import org.bouncycastle.math.raw.Nat; import org.bouncycastle.util.Arrays; -public class SecP384R1FieldElement extends ECFieldElement +public class SecP384R1FieldElement extends ECFieldElement.AbstractFp { public static final BigInteger Q = SecP384R1Curve.q; diff --git a/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP521R1Curve.java b/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP521R1Curve.java index 16691b10..267defcf 100644 --- a/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP521R1Curve.java +++ b/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP521R1Curve.java @@ -4,7 +4,9 @@ import java.math.BigInteger; import org.bouncycastle.math.ec.ECCurve; import org.bouncycastle.math.ec.ECFieldElement; +import org.bouncycastle.math.ec.ECLookupTable; import org.bouncycastle.math.ec.ECPoint; +import org.bouncycastle.math.raw.Nat; import org.bouncycastle.util.encoders.Hex; public class SecP521R1Curve extends ECCurve.AbstractFp @@ -77,4 +79,49 @@ public class SecP521R1Curve extends ECCurve.AbstractFp { return infinity; } + + public ECLookupTable createCacheSafeLookupTable(ECPoint[] points, int off, final int len) + { + final int FE_INTS = 17; + + final int[] table = new int[len * FE_INTS * 2]; + { + int pos = 0; + for (int i = 0; i < len; ++i) + { + ECPoint p = points[off + i]; + Nat.copy(FE_INTS, ((SecP521R1FieldElement)p.getRawXCoord()).x, 0, table, pos); pos += FE_INTS; + Nat.copy(FE_INTS, ((SecP521R1FieldElement)p.getRawYCoord()).x, 0, table, pos); pos += FE_INTS; + } + } + + return new ECLookupTable() + { + public int getSize() + { + return len; + } + + public ECPoint lookup(int index) + { + int[] x = Nat.create(FE_INTS), y = Nat.create(FE_INTS); + int pos = 0; + + for (int i = 0; i < len; ++i) + { + int MASK = ((i ^ index) - 1) >> 31; + + for (int j = 0; j < FE_INTS; ++j) + { + x[j] ^= table[pos + j] & MASK; + y[j] ^= table[pos + FE_INTS + j] & MASK; + } + + pos += (FE_INTS * 2); + } + + return createRawPoint(new SecP521R1FieldElement(x), new SecP521R1FieldElement(y), false); + } + }; + } } diff --git a/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP521R1FieldElement.java b/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP521R1FieldElement.java index ce9b6392..5cf30fc0 100644 --- a/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP521R1FieldElement.java +++ b/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/SecP521R1FieldElement.java @@ -7,7 +7,7 @@ import org.bouncycastle.math.raw.Mod; import org.bouncycastle.math.raw.Nat; import org.bouncycastle.util.Arrays; -public class SecP521R1FieldElement extends ECFieldElement +public class SecP521R1FieldElement extends ECFieldElement.AbstractFp { public static final BigInteger Q = SecP521R1Curve.q; diff --git a/bcprov/src/main/java/org/bouncycastle/math/package.html b/bcprov/src/main/java/org/bouncycastle/math/package.html new file mode 100644 index 00000000..0e6088d8 --- /dev/null +++ b/bcprov/src/main/java/org/bouncycastle/math/package.html @@ -0,0 +1,5 @@ +<html> +<body bgcolor="#ffffff"> +The Bouncy Castle math package. +</body> +</html> diff --git a/bcprov/src/main/java/org/bouncycastle/math/raw/Interleave.java b/bcprov/src/main/java/org/bouncycastle/math/raw/Interleave.java new file mode 100644 index 00000000..85f4f6d6 --- /dev/null +++ b/bcprov/src/main/java/org/bouncycastle/math/raw/Interleave.java @@ -0,0 +1,177 @@ +package org.bouncycastle.math.raw; + +public class Interleave +{ + private static final long M32 = 0x55555555L; + private static final long M64 = 0x5555555555555555L; + private static final long M64R = 0xAAAAAAAAAAAAAAAAL; + + /* + * This expands 8 bit indices into 16 bit contents (high bit 14), by inserting 0s between bits. + * In a binary field, this operation is the same as squaring an 8 bit number. + * + * NOTE: All entries are positive so sign-extension is not an issue. + */ +// private static final short[] INTERLEAVE2_TABLE = new short[] +// { +// 0x0000, 0x0001, 0x0004, 0x0005, 0x0010, 0x0011, 0x0014, 0x0015, +// 0x0040, 0x0041, 0x0044, 0x0045, 0x0050, 0x0051, 0x0054, 0x0055, +// 0x0100, 0x0101, 0x0104, 0x0105, 0x0110, 0x0111, 0x0114, 0x0115, +// 0x0140, 0x0141, 0x0144, 0x0145, 0x0150, 0x0151, 0x0154, 0x0155, +// 0x0400, 0x0401, 0x0404, 0x0405, 0x0410, 0x0411, 0x0414, 0x0415, +// 0x0440, 0x0441, 0x0444, 0x0445, 0x0450, 0x0451, 0x0454, 0x0455, +// 0x0500, 0x0501, 0x0504, 0x0505, 0x0510, 0x0511, 0x0514, 0x0515, +// 0x0540, 0x0541, 0x0544, 0x0545, 0x0550, 0x0551, 0x0554, 0x0555, +// 0x1000, 0x1001, 0x1004, 0x1005, 0x1010, 0x1011, 0x1014, 0x1015, +// 0x1040, 0x1041, 0x1044, 0x1045, 0x1050, 0x1051, 0x1054, 0x1055, +// 0x1100, 0x1101, 0x1104, 0x1105, 0x1110, 0x1111, 0x1114, 0x1115, +// 0x1140, 0x1141, 0x1144, 0x1145, 0x1150, 0x1151, 0x1154, 0x1155, +// 0x1400, 0x1401, 0x1404, 0x1405, 0x1410, 0x1411, 0x1414, 0x1415, +// 0x1440, 0x1441, 0x1444, 0x1445, 0x1450, 0x1451, 0x1454, 0x1455, +// 0x1500, 0x1501, 0x1504, 0x1505, 0x1510, 0x1511, 0x1514, 0x1515, +// 0x1540, 0x1541, 0x1544, 0x1545, 0x1550, 0x1551, 0x1554, 0x1555, +// 0x4000, 0x4001, 0x4004, 0x4005, 0x4010, 0x4011, 0x4014, 0x4015, +// 0x4040, 0x4041, 0x4044, 0x4045, 0x4050, 0x4051, 0x4054, 0x4055, +// 0x4100, 0x4101, 0x4104, 0x4105, 0x4110, 0x4111, 0x4114, 0x4115, +// 0x4140, 0x4141, 0x4144, 0x4145, 0x4150, 0x4151, 0x4154, 0x4155, +// 0x4400, 0x4401, 0x4404, 0x4405, 0x4410, 0x4411, 0x4414, 0x4415, +// 0x4440, 0x4441, 0x4444, 0x4445, 0x4450, 0x4451, 0x4454, 0x4455, +// 0x4500, 0x4501, 0x4504, 0x4505, 0x4510, 0x4511, 0x4514, 0x4515, +// 0x4540, 0x4541, 0x4544, 0x4545, 0x4550, 0x4551, 0x4554, 0x4555, +// 0x5000, 0x5001, 0x5004, 0x5005, 0x5010, 0x5011, 0x5014, 0x5015, +// 0x5040, 0x5041, 0x5044, 0x5045, 0x5050, 0x5051, 0x5054, 0x5055, +// 0x5100, 0x5101, 0x5104, 0x5105, 0x5110, 0x5111, 0x5114, 0x5115, +// 0x5140, 0x5141, 0x5144, 0x5145, 0x5150, 0x5151, 0x5154, 0x5155, +// 0x5400, 0x5401, 0x5404, 0x5405, 0x5410, 0x5411, 0x5414, 0x5415, +// 0x5440, 0x5441, 0x5444, 0x5445, 0x5450, 0x5451, 0x5454, 0x5455, +// 0x5500, 0x5501, 0x5504, 0x5505, 0x5510, 0x5511, 0x5514, 0x5515, +// 0x5540, 0x5541, 0x5544, 0x5545, 0x5550, 0x5551, 0x5554, 0x5555 +// }; + + public static int expand8to16(int x) + { + x &= 0xFF; + x = (x | (x << 4)) & 0x0F0F; + x = (x | (x << 2)) & 0x3333; + x = (x | (x << 1)) & 0x5555; + return x; + } + + public static int expand16to32(int x) + { + x &= 0xFFFF; + x = (x | (x << 8)) & 0x00FF00FF; + x = (x | (x << 4)) & 0x0F0F0F0F; + x = (x | (x << 2)) & 0x33333333; + x = (x | (x << 1)) & 0x55555555; + return x; + } + + public static long expand32to64(int x) + { + // "shuffle" low half to even bits and high half to odd bits + int t; + t = (x ^ (x >>> 8)) & 0x0000FF00; x ^= (t ^ (t << 8)); + t = (x ^ (x >>> 4)) & 0x00F000F0; x ^= (t ^ (t << 4)); + t = (x ^ (x >>> 2)) & 0x0C0C0C0C; x ^= (t ^ (t << 2)); + t = (x ^ (x >>> 1)) & 0x22222222; x ^= (t ^ (t << 1)); + + return ((x >>> 1) & M32) << 32 | (x & M32); + } + + public static void expand64To128(long x, long[] z, int zOff) + { + // "shuffle" low half to even bits and high half to odd bits + long t; + t = (x ^ (x >>> 16)) & 0x00000000FFFF0000L; x ^= (t ^ (t << 16)); + t = (x ^ (x >>> 8)) & 0x0000FF000000FF00L; x ^= (t ^ (t << 8)); + t = (x ^ (x >>> 4)) & 0x00F000F000F000F0L; x ^= (t ^ (t << 4)); + t = (x ^ (x >>> 2)) & 0x0C0C0C0C0C0C0C0CL; x ^= (t ^ (t << 2)); + t = (x ^ (x >>> 1)) & 0x2222222222222222L; x ^= (t ^ (t << 1)); + + z[zOff ] = (x ) & M64; + z[zOff + 1] = (x >>> 1) & M64; + } + + public static void expand64To128Rev(long x, long[] z, int zOff) + { + // "shuffle" low half to even bits and high half to odd bits + long t; + t = (x ^ (x >>> 16)) & 0x00000000FFFF0000L; x ^= (t ^ (t << 16)); + t = (x ^ (x >>> 8)) & 0x0000FF000000FF00L; x ^= (t ^ (t << 8)); + t = (x ^ (x >>> 4)) & 0x00F000F000F000F0L; x ^= (t ^ (t << 4)); + t = (x ^ (x >>> 2)) & 0x0C0C0C0C0C0C0C0CL; x ^= (t ^ (t << 2)); + t = (x ^ (x >>> 1)) & 0x2222222222222222L; x ^= (t ^ (t << 1)); + + z[zOff ] = (x ) & M64R; + z[zOff + 1] = (x << 1) & M64R; + } + + public static int shuffle(int x) + { + // "shuffle" low half to even bits and high half to odd bits + int t; + t = (x ^ (x >>> 8)) & 0x0000FF00; x ^= (t ^ (t << 8)); + t = (x ^ (x >>> 4)) & 0x00F000F0; x ^= (t ^ (t << 4)); + t = (x ^ (x >>> 2)) & 0x0C0C0C0C; x ^= (t ^ (t << 2)); + t = (x ^ (x >>> 1)) & 0x22222222; x ^= (t ^ (t << 1)); + return x; + } + + public static long shuffle(long x) + { + // "shuffle" low half to even bits and high half to odd bits + long t; + t = (x ^ (x >>> 16)) & 0x00000000FFFF0000L; x ^= (t ^ (t << 16)); + t = (x ^ (x >>> 8)) & 0x0000FF000000FF00L; x ^= (t ^ (t << 8)); + t = (x ^ (x >>> 4)) & 0x00F000F000F000F0L; x ^= (t ^ (t << 4)); + t = (x ^ (x >>> 2)) & 0x0C0C0C0C0C0C0C0CL; x ^= (t ^ (t << 2)); + t = (x ^ (x >>> 1)) & 0x2222222222222222L; x ^= (t ^ (t << 1)); + return x; + } + + public static int shuffle2(int x) + { + // "shuffle" (twice) low half to even bits and high half to odd bits + int t; + t = (x ^ (x >>> 7)) & 0x00AA00AA; x ^= (t ^ (t << 7)); + t = (x ^ (x >>> 14)) & 0x0000CCCC; x ^= (t ^ (t << 14)); + t = (x ^ (x >>> 4)) & 0x00F000F0; x ^= (t ^ (t << 4)); + t = (x ^ (x >>> 8)) & 0x0000FF00; x ^= (t ^ (t << 8)); + return x; + } + + public static int unshuffle(int x) + { + // "unshuffle" even bits to low half and odd bits to high half + int t; + t = (x ^ (x >>> 1)) & 0x22222222; x ^= (t ^ (t << 1)); + t = (x ^ (x >>> 2)) & 0x0C0C0C0C; x ^= (t ^ (t << 2)); + t = (x ^ (x >>> 4)) & 0x00F000F0; x ^= (t ^ (t << 4)); + t = (x ^ (x >>> 8)) & 0x0000FF00; x ^= (t ^ (t << 8)); + return x; + } + + public static long unshuffle(long x) + { + // "unshuffle" even bits to low half and odd bits to high half + long t; + t = (x ^ (x >>> 1)) & 0x2222222222222222L; x ^= (t ^ (t << 1)); + t = (x ^ (x >>> 2)) & 0x0C0C0C0C0C0C0C0CL; x ^= (t ^ (t << 2)); + t = (x ^ (x >>> 4)) & 0x00F000F000F000F0L; x ^= (t ^ (t << 4)); + t = (x ^ (x >>> 8)) & 0x0000FF000000FF00L; x ^= (t ^ (t << 8)); + t = (x ^ (x >>> 16)) & 0x00000000FFFF0000L; x ^= (t ^ (t << 16)); + return x; + } + + public static int unshuffle2(int x) + { + // "unshuffle" (twice) even bits to low half and odd bits to high half + int t; + t = (x ^ (x >>> 8)) & 0x0000FF00; x ^= (t ^ (t << 8)); + t = (x ^ (x >>> 4)) & 0x00F000F0; x ^= (t ^ (t << 4)); + t = (x ^ (x >>> 14)) & 0x0000CCCC; x ^= (t ^ (t << 14)); + t = (x ^ (x >>> 7)) & 0x00AA00AA; x ^= (t ^ (t << 7)); + return x; + } +} diff --git a/bcprov/src/main/java/org/bouncycastle/math/raw/Nat.java b/bcprov/src/main/java/org/bouncycastle/math/raw/Nat.java index 6b77f8fa..d9482cf7 100644 --- a/bcprov/src/main/java/org/bouncycastle/math/raw/Nat.java +++ b/bcprov/src/main/java/org/bouncycastle/math/raw/Nat.java @@ -194,6 +194,41 @@ public abstract class Nat return c == 0 ? 0 : incAt(len, z, zOff, 1); } + public static int cadd(int len, int mask, int[] x, int[] y, int[] z) + { + long MASK = -(mask & 1) & M; + long c = 0; + for (int i = 0; i < len; ++i) + { + c += (x[i] & M) + (y[i] & MASK); + z[i] = (int)c; + c >>>= 32; + } + return (int)c; + } + + public static void cmov(int len, int mask, int[] x, int xOff, int[] z, int zOff) + { + mask = -(mask & 1); + + for (int i = 0; i < len; ++i) + { + int z_i = z[zOff + i], diff = z_i ^ x[xOff + i]; + z_i ^= (diff & mask); + z[zOff + i] = z_i; + } + +// final int half = 0x55555555, rest = half << (-mask); +// +// for (int i = 0; i < len; ++i) +// { +// int z_i = z[zOff + i], diff = z_i ^ x[xOff + i]; +// z_i ^= (diff & half); +// z_i ^= (diff & rest); +// z[zOff + i] = z_i; +// } + } + public static int[] copy(int len, int[] x) { int[] z = new int[len]; @@ -206,6 +241,11 @@ public abstract class Nat System.arraycopy(x, 0, z, 0, len); } + public static void copy(int len, int[] x, int xOff, int[] z, int zOff) + { + System.arraycopy(x, xOff, z, zOff, len); + } + public static int[] create(int len) { return new int[len]; @@ -216,6 +256,19 @@ public abstract class Nat return new long[len]; } + public static int csub(int len, int mask, int[] x, int[] y, int[] z) + { + long MASK = -(mask & 1) & M; + long c = 0; + for (int i = 0; i < len; ++i) + { + c += (x[i] & M) - (y[i] & MASK); + z[i] = (int)c; + c >>= 32; + } + return (int)c; + } + public static int dec(int len, int[] z) { for (int i = 0; i < len; ++i) @@ -441,6 +494,16 @@ public abstract class Nat } } + public static void mul(int[] x, int xOff, int xLen, int[] y, int yOff, int yLen, int[] zz, int zzOff) + { + zz[zzOff + yLen] = mulWord(yLen, x[xOff], y, yOff, zz, zzOff); + + for (int i = 1; i < xLen; ++i) + { + zz[zzOff + i + yLen] = mulWordAddTo(yLen, x[xOff + i], y, yOff, zz, zzOff + i); + } + } + public static int mulAddTo(int len, int[] x, int[] y, int[] zz) { long zc = 0; diff --git a/bcprov/src/main/java/org/bouncycastle/math/raw/Nat192.java b/bcprov/src/main/java/org/bouncycastle/math/raw/Nat192.java index 12db01bc..ffe74d70 100644 --- a/bcprov/src/main/java/org/bouncycastle/math/raw/Nat192.java +++ b/bcprov/src/main/java/org/bouncycastle/math/raw/Nat192.java @@ -144,6 +144,16 @@ public abstract class Nat192 z[5] = x[5]; } + public static void copy(int[] x, int xOff, int[] z, int zOff) + { + z[zOff + 0] = x[xOff + 0]; + z[zOff + 1] = x[xOff + 1]; + z[zOff + 2] = x[xOff + 2]; + z[zOff + 3] = x[xOff + 3]; + z[zOff + 4] = x[xOff + 4]; + z[zOff + 5] = x[xOff + 5]; + } + public static void copy64(long[] x, long[] z) { z[0] = x[0]; @@ -151,6 +161,13 @@ public abstract class Nat192 z[2] = x[2]; } + public static void copy64(long[] x, int xOff, long[] z, int zOff) + { + z[zOff + 0] = x[xOff + 0]; + z[zOff + 1] = x[xOff + 1]; + z[zOff + 2] = x[xOff + 2]; + } + public static int[] create() { return new int[6]; diff --git a/bcprov/src/main/java/org/bouncycastle/math/raw/Nat224.java b/bcprov/src/main/java/org/bouncycastle/math/raw/Nat224.java index 9ff107c1..59be1f51 100644 --- a/bcprov/src/main/java/org/bouncycastle/math/raw/Nat224.java +++ b/bcprov/src/main/java/org/bouncycastle/math/raw/Nat224.java @@ -215,6 +215,17 @@ public abstract class Nat224 z[6] = x[6]; } + public static void copy(int[] x, int xOff, int[] z, int zOff) + { + z[zOff + 0] = x[xOff + 0]; + z[zOff + 1] = x[xOff + 1]; + z[zOff + 2] = x[xOff + 2]; + z[zOff + 3] = x[xOff + 3]; + z[zOff + 4] = x[xOff + 4]; + z[zOff + 5] = x[xOff + 5]; + z[zOff + 6] = x[xOff + 6]; + } + public static int[] create() { return new int[7]; diff --git a/bcprov/src/main/java/org/bouncycastle/math/raw/Nat256.java b/bcprov/src/main/java/org/bouncycastle/math/raw/Nat256.java index 726bae35..f7d80b3a 100644 --- a/bcprov/src/main/java/org/bouncycastle/math/raw/Nat256.java +++ b/bcprov/src/main/java/org/bouncycastle/math/raw/Nat256.java @@ -238,6 +238,18 @@ public abstract class Nat256 z[7] = x[7]; } + public static void copy(int[] x, int xOff, int[] z, int zOff) + { + z[zOff + 0] = x[xOff + 0]; + z[zOff + 1] = x[xOff + 1]; + z[zOff + 2] = x[xOff + 2]; + z[zOff + 3] = x[xOff + 3]; + z[zOff + 4] = x[xOff + 4]; + z[zOff + 5] = x[xOff + 5]; + z[zOff + 6] = x[xOff + 6]; + z[zOff + 7] = x[xOff + 7]; + } + public static void copy64(long[] x, long[] z) { z[0] = x[0]; @@ -246,6 +258,14 @@ public abstract class Nat256 z[3] = x[3]; } + public static void copy64(long[] x, int xOff, long[] z, int zOff) + { + z[zOff + 0] = x[xOff + 0]; + z[zOff + 1] = x[xOff + 1]; + z[zOff + 2] = x[xOff + 2]; + z[zOff + 3] = x[xOff + 3]; + } + public static int[] create() { return new int[8]; |