diff options
Diffstat (limited to 'bcprov/src/main/java/org/bouncycastle/math/ec')
4 files changed, 153 insertions, 44 deletions
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 3b334d2..7165bab 100644 --- a/bcprov/src/main/java/org/bouncycastle/math/ec/ECAlgorithms.java +++ b/bcprov/src/main/java/org/bouncycastle/math/ec/ECAlgorithms.java @@ -124,6 +124,11 @@ public class ECAlgorithms public static void montgomeryTrick(ECFieldElement[] zs, int off, int len) { + montgomeryTrick(zs, off, len, null); + } + + public static void montgomeryTrick(ECFieldElement[] zs, int off, int len, ECFieldElement scale) + { /* * Uses the "Montgomery Trick" to invert many field elements, with only a single actual * field inversion. See e.g. the paper: @@ -140,7 +145,14 @@ public class ECAlgorithms c[i] = c[i - 1].multiply(zs[off + i]); } - ECFieldElement u = c[--i].invert(); + --i; + + if (scale != null) + { + c[i] = c[i].multiply(scale); + } + + ECFieldElement u = c[i].invert(); while (i > 0) { 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 4c658f2..0dc6853 100644 --- a/bcprov/src/main/java/org/bouncycastle/math/ec/ECCurve.java +++ b/bcprov/src/main/java/org/bouncycastle/math/ec/ECCurve.java @@ -229,26 +229,57 @@ public abstract class ECCurve */ public void normalizeAll(ECPoint[] points) { - checkPoints(points); + normalizeAll(points, 0, points.length, null); + } - if (this.getCoordinateSystem() == ECCurve.COORD_AFFINE) + /** + * Normalization ensures that any projective coordinate is 1, and therefore that the x, y + * coordinates reflect those of the equivalent point in an affine coordinate system. Where more + * than one point is to be normalized, this method will generally be more efficient than + * normalizing each point separately. An (optional) z-scaling factor can be applied; effectively + * each z coordinate is scaled by this value prior to normalization (but only one + * actual multiplication is needed). + * + * @param points + * An array of points that will be updated in place with their normalized versions, + * where necessary + * @param off + * The start of the range of points to normalize + * @param len + * The length of the range of points to normalize + * @param iso + * The (optional) z-scaling factor - can be null + */ + public void normalizeAll(ECPoint[] points, int off, int len, ECFieldElement iso) + { + checkPoints(points, off, len); + + switch (this.getCoordinateSystem()) + { + case ECCurve.COORD_AFFINE: + case ECCurve.COORD_LAMBDA_AFFINE: { + if (iso != null) + { + throw new IllegalArgumentException("'iso' not valid for affine coordinates"); + } return; } + } /* * Figure out which of the points actually need to be normalized */ - ECFieldElement[] zs = new ECFieldElement[points.length]; - int[] indices = new int[points.length]; + ECFieldElement[] zs = new ECFieldElement[len]; + int[] indices = new int[len]; int count = 0; - for (int i = 0; i < points.length; ++i) + for (int i = 0; i < len; ++i) { - ECPoint p = points[i]; - if (null != p && !p.isNormalized()) + ECPoint p = points[off + i]; + if (null != p && (iso != null || !p.isNormalized())) { zs[count] = p.getZCoord(0); - indices[count++] = i; + indices[count++] = off + i; } } @@ -257,7 +288,7 @@ public abstract class ECCurve return; } - ECAlgorithms.montgomeryTrick(zs, 0, count); + ECAlgorithms.montgomeryTrick(zs, 0, count, iso); for (int j = 0; j < count; ++j) { @@ -414,14 +445,23 @@ public abstract class ECCurve protected void checkPoints(ECPoint[] points) { + checkPoints(points, 0, points.length); + } + + protected void checkPoints(ECPoint[] points, int off, int len) + { if (points == null) { throw new IllegalArgumentException("'points' cannot be null"); } + if (off < 0 || len < 0 || (off > (points.length - len))) + { + throw new IllegalArgumentException("invalid range specified for 'points'"); + } - for (int i = 0; i < points.length; ++i) + for (int i = 0; i < len; ++i) { - ECPoint point = points[i]; + ECPoint point = points[off + i]; if (null != point && this != point.getCurve()) { throw new IllegalArgumentException("'points' entries must be null or on this curve"); 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 7cd04e4..4db27e0 100644 --- a/bcprov/src/main/java/org/bouncycastle/math/ec/ECPoint.java +++ b/bcprov/src/main/java/org/bouncycastle/math/ec/ECPoint.java @@ -287,6 +287,9 @@ public abstract class ECPoint return x == null || y == null || (zs.length > 0 && zs[0].isZero()); } + /** + * @deprecated per-point compression property will be removed, refer {@link #getEncoded(boolean)} + */ public boolean isCompressed() { return this.withCompression; @@ -435,13 +438,19 @@ public abstract class ECPoint return sb.toString(); } + /** + * @deprecated per-point compression property will be removed, refer {@link #getEncoded(boolean)} + */ public byte[] getEncoded() { return getEncoded(this.withCompression); } /** - * return the field element encoded with point compression. (S 4.3.6) + * Get an encoding of the point value, optionally in compressed format. + * + * @param compressed whether to generate a compressed point encoding. + * @return the point encoding */ public byte[] getEncoded(boolean compressed) { @@ -771,14 +780,7 @@ public abstract class ECPoint Y3 = W1.subtract(X3).multiply(dy).subtract(A1); Z3 = dx; - if (Z1IsOne) - { - Z3Squared = C; - } - else - { - Z3 = Z3.multiply(Z1); - } + Z3 = Z3.multiply(Z1); } else { @@ -967,7 +969,7 @@ public abstract class ECPoint } else if (!a4.isZero()) { - ECFieldElement Z1Squared = Z1IsOne ? Z1 : Z1.square(); + ECFieldElement Z1Squared = Z1.square(); ECFieldElement Z1Pow4 = Z1Squared.square(); if (a4Neg.bitLength() < a4.bitLength()) { 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 7ac3160..339689e 100644 --- a/bcprov/src/main/java/org/bouncycastle/math/ec/WNafUtil.java +++ b/bcprov/src/main/java/org/bouncycastle/math/ec/WNafUtil.java @@ -10,6 +10,7 @@ public abstract class WNafUtil private static final byte[] EMPTY_BYTES = new byte[0]; private static final int[] EMPTY_INTS = new int[0]; + private static final ECPoint[] EMPTY_POINTS = new ECPoint[0]; public static int[] generateCompactNaf(BigInteger k) { @@ -386,45 +387,99 @@ public abstract class WNafUtil ECCurve c = p.getCurve(); WNafPreCompInfo wnafPreCompInfo = getWNafPreCompInfo(c.getPreCompInfo(p, PRECOMP_NAME)); + int iniPreCompLen = 0, reqPreCompLen = 1 << Math.max(0, width - 2); + ECPoint[] preComp = wnafPreCompInfo.getPreComp(); if (preComp == null) { - preComp = new ECPoint[]{ p }; + preComp = EMPTY_POINTS; + } + else + { + iniPreCompLen = preComp.length; } - int preCompLen = preComp.length; - int reqPreCompLen = 1 << Math.max(0, width - 2); - - if (preCompLen < reqPreCompLen) + if (iniPreCompLen < reqPreCompLen) { preComp = resizeTable(preComp, reqPreCompLen); - if (reqPreCompLen == 2) + + if (reqPreCompLen == 1) { - preComp[1] = preComp[0].threeTimes(); + preComp[0] = p.normalize(); } else { - ECPoint twiceP = wnafPreCompInfo.getTwice(); - if (twiceP == null) + int curPreCompLen = iniPreCompLen; + if (curPreCompLen == 0) { - twiceP = preComp[0].twice(); - wnafPreCompInfo.setTwice(twiceP); + preComp[0] = p; + curPreCompLen = 1; } - for (int i = preCompLen; i < reqPreCompLen; i++) + ECFieldElement iso = null; + + if (reqPreCompLen == 2) { - /* - * Compute the new ECPoints for the precomputation array. The values 1, 3, 5, ..., - * 2^(width-1)-1 times p are computed - */ - preComp[i] = twiceP.add(preComp[i - 1]); + preComp[1] = p.threeTimes(); + } + else + { + ECPoint twiceP = wnafPreCompInfo.getTwice(), last = preComp[curPreCompLen - 1]; + if (twiceP == null) + { + twiceP = preComp[0].twice(); + wnafPreCompInfo.setTwice(twiceP); + + /* + * 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 (ECAlgorithms.isFpCurve(c) && c.getFieldSize() >= 64) + { + 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()); + + ECFieldElement iso2 = iso.square(), iso3 = iso2.multiply(iso); + last = last.scaleX(iso2).scaleY(iso3); + + if (iniPreCompLen == 0) + { + preComp[0] = last; + } + 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(twiceP); + } } - } - /* - * Having oft-used operands in affine form makes operations faster. - */ - c.normalizeAll(preComp); + /* + * Having oft-used operands in affine form makes operations faster. + */ + c.normalizeAll(preComp, iniPreCompLen, reqPreCompLen - iniPreCompLen, iso); + } } wnafPreCompInfo.setPreComp(preComp); |