diff options
Diffstat (limited to 'core/src/main/java/org/spongycastle/math/ec/custom/sec')
32 files changed, 6681 insertions, 0 deletions
diff --git a/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP192K1Curve.java b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP192K1Curve.java new file mode 100644 index 00000000..3c5d9cb3 --- /dev/null +++ b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP192K1Curve.java @@ -0,0 +1,79 @@ +package org.spongycastle.math.ec.custom.sec; + +import java.math.BigInteger; + +import org.spongycastle.math.ec.ECConstants; +import org.spongycastle.math.ec.ECCurve; +import org.spongycastle.math.ec.ECFieldElement; +import org.spongycastle.math.ec.ECPoint; +import org.spongycastle.util.encoders.Hex; + +public class SecP192K1Curve extends ECCurve.AbstractFp +{ + public static final BigInteger q = new BigInteger(1, + Hex.decode("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFEE37")); + + private static final int SecP192K1_DEFAULT_COORDS = COORD_JACOBIAN; + + protected SecP192K1Point infinity; + + public SecP192K1Curve() + { + super(q); + + this.infinity = new SecP192K1Point(this, null, null); + + this.a = fromBigInteger(ECConstants.ZERO); + this.b = fromBigInteger(BigInteger.valueOf(3)); + this.order = new BigInteger(1, Hex.decode("FFFFFFFFFFFFFFFFFFFFFFFE26F2FC170F69466A74DEFD8D")); + this.cofactor = BigInteger.valueOf(1); + + this.coord = SecP192K1_DEFAULT_COORDS; + } + + protected ECCurve cloneCurve() + { + return new SecP192K1Curve(); + } + + public boolean supportsCoordinateSystem(int coord) + { + switch (coord) + { + case COORD_JACOBIAN: + return true; + default: + return false; + } + } + + public BigInteger getQ() + { + return q; + } + + public int getFieldSize() + { + return q.bitLength(); + } + + public ECFieldElement fromBigInteger(BigInteger x) + { + return new SecP192K1FieldElement(x); + } + + protected ECPoint createRawPoint(ECFieldElement x, ECFieldElement y, boolean withCompression) + { + return new SecP192K1Point(this, x, y, withCompression); + } + + protected ECPoint createRawPoint(ECFieldElement x, ECFieldElement y, ECFieldElement[] zs, boolean withCompression) + { + return new SecP192K1Point(this, x, y, zs, withCompression); + } + + public ECPoint getInfinity() + { + return infinity; + } +} diff --git a/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP192K1Field.java b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP192K1Field.java new file mode 100644 index 00000000..b7e87f27 --- /dev/null +++ b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP192K1Field.java @@ -0,0 +1,177 @@ +package org.spongycastle.math.ec.custom.sec; + +import java.math.BigInteger; + +import org.spongycastle.math.raw.Nat; +import org.spongycastle.math.raw.Nat192; + +public class SecP192K1Field +{ + // 2^192 - 2^32 - 2^12 - 2^8 - 2^7 - 2^6 - 2^3 - 1 + static final int[] P = new int[]{ 0xFFFFEE37, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF }; + static final int[] PExt = new int[]{ 0x013C4FD1, 0x00002392, 0x00000001, 0x00000000, 0x00000000, + 0x00000000, 0xFFFFDC6E, 0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF }; + private static final int[] PExtInv = new int[]{ 0xFEC3B02F, 0xFFFFDC6D, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, + 0xFFFFFFFF, 0x00002391, 0x00000002 }; + private static final int P5 = 0xFFFFFFFF; + private static final int PExt11 = 0xFFFFFFFF; + private static final int PInv33 = 0x11C9; + + public static void add(int[] x, int[] y, int[] z) + { + int c = Nat192.add(x, y, z); + if (c != 0 || (z[5] == P5 && Nat192.gte(z, P))) + { + Nat.add33To(6, PInv33, z); + } + } + + public static void addExt(int[] xx, int[] yy, int[] zz) + { + int c = Nat.add(12, xx, yy, zz); + if (c != 0 || (zz[11] == PExt11 && Nat.gte(12, zz, PExt))) + { + if (Nat.addTo(PExtInv.length, PExtInv, zz) != 0) + { + Nat.incAt(12, zz, PExtInv.length); + } + } + } + + public static void addOne(int[] x, int[] z) + { + int c = Nat.inc(6, x, z); + if (c != 0 || (z[5] == P5 && Nat192.gte(z, P))) + { + Nat.add33To(6, PInv33, z); + } + } + + public static int[] fromBigInteger(BigInteger x) + { + int[] z = Nat192.fromBigInteger(x); + if (z[5] == P5 && Nat192.gte(z, P)) + { + Nat192.subFrom(P, z); + } + return z; + } + + public static void half(int[] x, int[] z) + { + if ((x[0] & 1) == 0) + { + Nat.shiftDownBit(6, x, 0, z); + } + else + { + int c = Nat192.add(x, P, z); + Nat.shiftDownBit(6, z, c); + } + } + + public static void multiply(int[] x, int[] y, int[] z) + { + int[] tt = Nat192.createExt(); + Nat192.mul(x, y, tt); + reduce(tt, z); + } + + public static void multiplyAddToExt(int[] x, int[] y, int[] zz) + { + int c = Nat192.mulAddTo(x, y, zz); + if (c != 0 || (zz[11] == PExt11 && Nat.gte(12, zz, PExt))) + { + if (Nat.addTo(PExtInv.length, PExtInv, zz) != 0) + { + Nat.incAt(12, zz, PExtInv.length); + } + } + } + + public static void negate(int[] x, int[] z) + { + if (Nat192.isZero(x)) + { + Nat192.zero(z); + } + else + { + Nat192.sub(P, x, z); + } + } + + public static void reduce(int[] xx, int[] z) + { + long cc = Nat192.mul33Add(PInv33, xx, 6, xx, 0, z, 0); + int c = Nat192.mul33DWordAdd(PInv33, cc, z, 0); + + // assert c == 0L || c == 1L; + + if (c != 0 || (z[5] == P5 && Nat192.gte(z, P))) + { + Nat.add33To(6, PInv33, z); + } + } + + public static void reduce32(int x, int[] z) + { + if ((x != 0 && Nat192.mul33WordAdd(PInv33, x, z, 0) != 0) + || (z[5] == P5 && Nat192.gte(z, P))) + { + Nat.add33To(6, PInv33, z); + } + } + + public static void square(int[] x, int[] z) + { + int[] tt = Nat192.createExt(); + Nat192.square(x, tt); + reduce(tt, z); + } + + public static void squareN(int[] x, int n, int[] z) + { +// assert n > 0; + + int[] tt = Nat192.createExt(); + Nat192.square(x, tt); + reduce(tt, z); + + while (--n > 0) + { + Nat192.square(z, tt); + reduce(tt, z); + } + } + + public static void subtract(int[] x, int[] y, int[] z) + { + int c = Nat192.sub(x, y, z); + if (c != 0) + { + Nat.sub33From(6, PInv33, z); + } + } + + public static void subtractExt(int[] xx, int[] yy, int[] zz) + { + int c = Nat.sub(12, xx, yy, zz); + if (c != 0) + { + if (Nat.subFrom(PExtInv.length, PExtInv, zz) != 0) + { + Nat.decAt(12, zz, PExtInv.length); + } + } + } + + public static void twice(int[] x, int[] z) + { + int c = Nat.shiftUpBit(6, x, 0, z); + if (c != 0 || (z[5] == P5 && Nat192.gte(z, P))) + { + Nat.add33To(6, PInv33, z); + } + } +} diff --git a/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP192K1FieldElement.java b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP192K1FieldElement.java new file mode 100644 index 00000000..449c560c --- /dev/null +++ b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP192K1FieldElement.java @@ -0,0 +1,213 @@ +package org.spongycastle.math.ec.custom.sec; + +import java.math.BigInteger; + +import org.spongycastle.math.ec.ECFieldElement; +import org.spongycastle.math.raw.Mod; +import org.spongycastle.math.raw.Nat192; +import org.spongycastle.util.Arrays; + +public class SecP192K1FieldElement extends ECFieldElement +{ + public static final BigInteger Q = SecP192K1Curve.q; + + protected int[] x; + + public SecP192K1FieldElement(BigInteger x) + { + if (x == null || x.signum() < 0 || x.compareTo(Q) >= 0) + { + throw new IllegalArgumentException("x value invalid for SecP192K1FieldElement"); + } + + this.x = SecP192K1Field.fromBigInteger(x); + } + + public SecP192K1FieldElement() + { + this.x = Nat192.create(); + } + + protected SecP192K1FieldElement(int[] x) + { + this.x = x; + } + + public boolean isZero() + { + return Nat192.isZero(x); + } + + public boolean isOne() + { + return Nat192.isOne(x); + } + + public boolean testBitZero() + { + return Nat192.getBit(x, 0) == 1; + } + + public BigInteger toBigInteger() + { + return Nat192.toBigInteger(x); + } + + public String getFieldName() + { + return "SecP192K1Field"; + } + + public int getFieldSize() + { + return Q.bitLength(); + } + + public ECFieldElement add(ECFieldElement b) + { + int[] z = Nat192.create(); + SecP192K1Field.add(x, ((SecP192K1FieldElement)b).x, z); + return new SecP192K1FieldElement(z); + } + + public ECFieldElement addOne() + { + int[] z = Nat192.create(); + SecP192K1Field.addOne(x, z); + return new SecP192K1FieldElement(z); + } + + public ECFieldElement subtract(ECFieldElement b) + { + int[] z = Nat192.create(); + SecP192K1Field.subtract(x, ((SecP192K1FieldElement)b).x, z); + return new SecP192K1FieldElement(z); + } + + public ECFieldElement multiply(ECFieldElement b) + { + int[] z = Nat192.create(); + SecP192K1Field.multiply(x, ((SecP192K1FieldElement)b).x, z); + return new SecP192K1FieldElement(z); + } + + public ECFieldElement divide(ECFieldElement b) + { +// return multiply(b.invert()); + int[] z = Nat192.create(); + Mod.invert(SecP192K1Field.P, ((SecP192K1FieldElement)b).x, z); + SecP192K1Field.multiply(z, x, z); + return new SecP192K1FieldElement(z); + } + + public ECFieldElement negate() + { + int[] z = Nat192.create(); + SecP192K1Field.negate(x, z); + return new SecP192K1FieldElement(z); + } + + public ECFieldElement square() + { + int[] z = Nat192.create(); + SecP192K1Field.square(x, z); + return new SecP192K1FieldElement(z); + } + + public ECFieldElement invert() + { +// return new SecP192K1FieldElement(toBigInteger().modInverse(Q)); + int[] z = Nat192.create(); + Mod.invert(SecP192K1Field.P, x, z); + return new SecP192K1FieldElement(z); + } + + /** + * return a sqrt root - the routine verifies that the calculation returns the right value - if + * none exists it returns null. + */ + public ECFieldElement sqrt() + { + /* + * Raise this element to the exponent 2^190 - 2^30 - 2^10 - 2^6 - 2^5 - 2^4 - 2^1 + * + * Breaking up the exponent's binary representation into "repunits", we get: + * { 159 1s } { 1 0s } { 19 1s } { 1 0s } { 3 1s } { 3 0s} { 3 1s } { 1 0s } + * + * Therefore we need an addition chain containing 3, 19, 159 (the lengths of the repunits) + * We use: 1, 2, [3], 6, 8, 16, [19], 35, 70, 140, [159] + */ + + int[] x1 = this.x; + if (Nat192.isZero(x1) || Nat192.isOne(x1)) + { + return this; + } + + int[] x2 = Nat192.create(); + SecP192K1Field.square(x1, x2); + SecP192K1Field.multiply(x2, x1, x2); + int[] x3 = Nat192.create(); + SecP192K1Field.square(x2, x3); + SecP192K1Field.multiply(x3, x1, x3); + int[] x6 = Nat192.create(); + SecP192K1Field.squareN(x3, 3, x6); + SecP192K1Field.multiply(x6, x3, x6); + int[] x8 = x6; + SecP192K1Field.squareN(x6, 2, x8); + SecP192K1Field.multiply(x8, x2, x8); + int[] x16 = x2; + SecP192K1Field.squareN(x8, 8, x16); + SecP192K1Field.multiply(x16, x8, x16); + int[] x19 = x8; + SecP192K1Field.squareN(x16, 3, x19); + SecP192K1Field.multiply(x19, x3, x19); + int[] x35 = Nat192.create(); + SecP192K1Field.squareN(x19, 16, x35); + SecP192K1Field.multiply(x35, x16, x35); + int[] x70 = x16; + SecP192K1Field.squareN(x35, 35, x70); + SecP192K1Field.multiply(x70, x35, x70); + int[] x140 = x35; + SecP192K1Field.squareN(x70, 70, x140); + SecP192K1Field.multiply(x140, x70, x140); + int[] x159 = x70; + SecP192K1Field.squareN(x140, 19, x159); + SecP192K1Field.multiply(x159, x19, x159); + + int[] t1 = x159; + SecP192K1Field.squareN(t1, 20, t1); + SecP192K1Field.multiply(t1, x19, t1); + SecP192K1Field.squareN(t1, 4, t1); + SecP192K1Field.multiply(t1, x3, t1); + SecP192K1Field.squareN(t1, 6, t1); + SecP192K1Field.multiply(t1, x3, t1); + SecP192K1Field.square(t1, t1); + + int[] t2 = x3; + SecP192K1Field.square(t1, t2); + + return Nat192.eq(x1, t2) ? new SecP192K1FieldElement(t1) : null; + } + + public boolean equals(Object other) + { + if (other == this) + { + return true; + } + + if (!(other instanceof SecP192K1FieldElement)) + { + return false; + } + + SecP192K1FieldElement o = (SecP192K1FieldElement)other; + return Nat192.eq(x, o.x); + } + + public int hashCode() + { + return Q.hashCode() ^ Arrays.hashCode(x, 0, 6); + } +} diff --git a/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP192K1Point.java b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP192K1Point.java new file mode 100644 index 00000000..d2fc0ad2 --- /dev/null +++ b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP192K1Point.java @@ -0,0 +1,298 @@ +package org.spongycastle.math.ec.custom.sec; + +import org.spongycastle.math.ec.ECCurve; +import org.spongycastle.math.ec.ECFieldElement; +import org.spongycastle.math.ec.ECPoint; +import org.spongycastle.math.raw.Nat; +import org.spongycastle.math.raw.Nat192; + +public class SecP192K1Point extends ECPoint.AbstractFp +{ + /** + * Create a point which encodes with 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 SecP192K1Point(ECCurve curve, ECFieldElement x, ECFieldElement y) + { + this(curve, x, y, false); + } + + /** + * Create a point that encodes with or without point compresion. + * + * @param curve + * the curve to use + * @param x + * affine x co-ordinate + * @param y + * affine y co-ordinate + * @param withCompression + * if true encode with point compression + * + * @deprecated per-point compression property will be removed, refer + * {@link #getEncoded(boolean)} + */ + public SecP192K1Point(ECCurve curve, ECFieldElement x, ECFieldElement y, boolean withCompression) + { + super(curve, x, y); + + if ((x == null) != (y == null)) + { + throw new IllegalArgumentException("Exactly one of the field elements is null"); + } + + this.withCompression = withCompression; + } + + SecP192K1Point(ECCurve curve, ECFieldElement x, ECFieldElement y, ECFieldElement[] zs, + boolean withCompression) + { + super(curve, x, y, zs); + + this.withCompression = withCompression; + } + + protected ECPoint detach() + { + return new SecP192K1Point(null, getAffineXCoord(), getAffineYCoord()); + } + + // B.3 pg 62 + public ECPoint add(ECPoint b) + { + if (this.isInfinity()) + { + return b; + } + if (b.isInfinity()) + { + return this; + } + if (this == b) + { + return twice(); + } + + ECCurve curve = this.getCurve(); + + SecP192K1FieldElement X1 = (SecP192K1FieldElement)this.x, Y1 = (SecP192K1FieldElement)this.y; + SecP192K1FieldElement X2 = (SecP192K1FieldElement)b.getXCoord(), Y2 = (SecP192K1FieldElement)b.getYCoord(); + + SecP192K1FieldElement Z1 = (SecP192K1FieldElement)this.zs[0]; + SecP192K1FieldElement Z2 = (SecP192K1FieldElement)b.getZCoord(0); + + int c; + int[] tt1 = Nat192.createExt(); + int[] t2 = Nat192.create(); + int[] t3 = Nat192.create(); + int[] t4 = Nat192.create(); + + boolean Z1IsOne = Z1.isOne(); + int[] U2, S2; + if (Z1IsOne) + { + U2 = X2.x; + S2 = Y2.x; + } + else + { + S2 = t3; + SecP192K1Field.square(Z1.x, S2); + + U2 = t2; + SecP192K1Field.multiply(S2, X2.x, U2); + + SecP192K1Field.multiply(S2, Z1.x, S2); + SecP192K1Field.multiply(S2, Y2.x, S2); + } + + boolean Z2IsOne = Z2.isOne(); + int[] U1, S1; + if (Z2IsOne) + { + U1 = X1.x; + S1 = Y1.x; + } + else + { + S1 = t4; + SecP192K1Field.square(Z2.x, S1); + + U1 = tt1; + SecP192K1Field.multiply(S1, X1.x, U1); + + SecP192K1Field.multiply(S1, Z2.x, S1); + SecP192K1Field.multiply(S1, Y1.x, S1); + } + + int[] H = Nat192.create(); + SecP192K1Field.subtract(U1, U2, H); + + int[] R = t2; + SecP192K1Field.subtract(S1, S2, R); + + // Check if b == this or b == -this + if (Nat192.isZero(H)) + { + if (Nat192.isZero(R)) + { + // this == b, i.e. this must be doubled + return this.twice(); + } + + // this == -b, i.e. the result is the point at infinity + return curve.getInfinity(); + } + + int[] HSquared = t3; + SecP192K1Field.square(H, HSquared); + + int[] G = Nat192.create(); + SecP192K1Field.multiply(HSquared, H, G); + + int[] V = t3; + SecP192K1Field.multiply(HSquared, U1, V); + + SecP192K1Field.negate(G, G); + Nat192.mul(S1, G, tt1); + + c = Nat192.addBothTo(V, V, G); + SecP192K1Field.reduce32(c, G); + + SecP192K1FieldElement X3 = new SecP192K1FieldElement(t4); + SecP192K1Field.square(R, X3.x); + SecP192K1Field.subtract(X3.x, G, X3.x); + + SecP192K1FieldElement Y3 = new SecP192K1FieldElement(G); + SecP192K1Field.subtract(V, X3.x, Y3.x); + SecP192K1Field.multiplyAddToExt(Y3.x, R, tt1); + SecP192K1Field.reduce(tt1, Y3.x); + + SecP192K1FieldElement Z3 = new SecP192K1FieldElement(H); + if (!Z1IsOne) + { + SecP192K1Field.multiply(Z3.x, Z1.x, Z3.x); + } + if (!Z2IsOne) + { + SecP192K1Field.multiply(Z3.x, Z2.x, Z3.x); + } + + ECFieldElement[] zs = new ECFieldElement[] { Z3 }; + + return new SecP192K1Point(curve, X3, Y3, zs, this.withCompression); + } + + // B.3 pg 62 + public ECPoint twice() + { + if (this.isInfinity()) + { + return this; + } + + ECCurve curve = this.getCurve(); + + SecP192K1FieldElement Y1 = (SecP192K1FieldElement)this.y; + if (Y1.isZero()) + { + return curve.getInfinity(); + } + + SecP192K1FieldElement X1 = (SecP192K1FieldElement)this.x, Z1 = (SecP192K1FieldElement)this.zs[0]; + + int c; + + int[] Y1Squared = Nat192.create(); + SecP192K1Field.square(Y1.x, Y1Squared); + + int[] T = Nat192.create(); + SecP192K1Field.square(Y1Squared, T); + + int[] M = Nat192.create(); + SecP192K1Field.square(X1.x, M); + c = Nat192.addBothTo(M, M, M); + SecP192K1Field.reduce32(c, M); + + int[] S = Y1Squared; + SecP192K1Field.multiply(Y1Squared, X1.x, S); + c = Nat.shiftUpBits(6, S, 2, 0); + SecP192K1Field.reduce32(c, S); + + int[] t1 = Nat192.create(); + c = Nat.shiftUpBits(6, T, 3, 0, t1); + SecP192K1Field.reduce32(c, t1); + + SecP192K1FieldElement X3 = new SecP192K1FieldElement(T); + SecP192K1Field.square(M, X3.x); + SecP192K1Field.subtract(X3.x, S, X3.x); + SecP192K1Field.subtract(X3.x, S, X3.x); + + SecP192K1FieldElement Y3 = new SecP192K1FieldElement(S); + SecP192K1Field.subtract(S, X3.x, Y3.x); + SecP192K1Field.multiply(Y3.x, M, Y3.x); + SecP192K1Field.subtract(Y3.x, t1, Y3.x); + + SecP192K1FieldElement Z3 = new SecP192K1FieldElement(M); + SecP192K1Field.twice(Y1.x, Z3.x); + if (!Z1.isOne()) + { + SecP192K1Field.multiply(Z3.x, Z1.x, Z3.x); + } + + return new SecP192K1Point(curve, X3, Y3, new ECFieldElement[] { Z3 }, this.withCompression); + } + + public ECPoint twicePlus(ECPoint b) + { + if (this == b) + { + return threeTimes(); + } + if (this.isInfinity()) + { + return b; + } + if (b.isInfinity()) + { + return twice(); + } + + ECFieldElement Y1 = this.y; + if (Y1.isZero()) + { + return b; + } + + return twice().add(b); + } + + public ECPoint threeTimes() + { + if (this.isInfinity() || this.y.isZero()) + { + return this; + } + + // NOTE: Be careful about recursions between twicePlus and threeTimes + return twice().add(this); + } + + public ECPoint negate() + { + if (this.isInfinity()) + { + return this; + } + + return new SecP192K1Point(curve, this.x, this.y.negate(), this.zs, this.withCompression); + } +} diff --git a/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP192R1Curve.java b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP192R1Curve.java new file mode 100644 index 00000000..705069fc --- /dev/null +++ b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP192R1Curve.java @@ -0,0 +1,80 @@ +package org.spongycastle.math.ec.custom.sec; + +import java.math.BigInteger; + +import org.spongycastle.math.ec.ECCurve; +import org.spongycastle.math.ec.ECFieldElement; +import org.spongycastle.math.ec.ECPoint; +import org.spongycastle.util.encoders.Hex; + +public class SecP192R1Curve extends ECCurve.AbstractFp +{ + public static final BigInteger q = new BigInteger(1, + Hex.decode("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFF")); + + private static final int SecP192R1_DEFAULT_COORDS = COORD_JACOBIAN; + + protected SecP192R1Point infinity; + + public SecP192R1Curve() + { + super(q); + + this.infinity = new SecP192R1Point(this, null, null); + + this.a = fromBigInteger(new BigInteger(1, + Hex.decode("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFC"))); + this.b = fromBigInteger(new BigInteger(1, + Hex.decode("64210519E59C80E70FA7E9AB72243049FEB8DEECC146B9B1"))); + this.order = new BigInteger(1, Hex.decode("FFFFFFFFFFFFFFFFFFFFFFFF99DEF836146BC9B1B4D22831")); + this.cofactor = BigInteger.valueOf(1); + + this.coord = SecP192R1_DEFAULT_COORDS; + } + + protected ECCurve cloneCurve() + { + return new SecP192R1Curve(); + } + + public boolean supportsCoordinateSystem(int coord) + { + switch (coord) + { + case COORD_JACOBIAN: + return true; + default: + return false; + } + } + + public BigInteger getQ() + { + return q; + } + + public int getFieldSize() + { + return q.bitLength(); + } + + public ECFieldElement fromBigInteger(BigInteger x) + { + return new SecP192R1FieldElement(x); + } + + protected ECPoint createRawPoint(ECFieldElement x, ECFieldElement y, boolean withCompression) + { + return new SecP192R1Point(this, x, y, withCompression); + } + + protected ECPoint createRawPoint(ECFieldElement x, ECFieldElement y, ECFieldElement[] zs, boolean withCompression) + { + return new SecP192R1Point(this, x, y, zs, withCompression); + } + + public ECPoint getInfinity() + { + return infinity; + } +} diff --git a/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP192R1Field.java b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP192R1Field.java new file mode 100644 index 00000000..4188b8f8 --- /dev/null +++ b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP192R1Field.java @@ -0,0 +1,286 @@ +package org.spongycastle.math.ec.custom.sec; + +import java.math.BigInteger; + +import org.spongycastle.math.raw.Nat; +import org.spongycastle.math.raw.Nat192; + +public class SecP192R1Field +{ + private static final long M = 0xFFFFFFFFL; + + // 2^192 - 2^64 - 1 + static final int[] P = new int[]{ 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF }; + static final int[] PExt = new int[]{ 0x00000001, 0x00000000, 0x00000002, 0x00000000, 0x00000001, + 0x00000000, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF }; + private static final int[] PExtInv = new int[]{ 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFE, + 0xFFFFFFFF, 0x00000001, 0x00000000, 0x00000002 }; + private static final int P5 = 0xFFFFFFFF; + private static final int PExt11 = 0xFFFFFFFF; + + public static void add(int[] x, int[] y, int[] z) + { + int c = Nat192.add(x, y, z); + if (c != 0 || (z[5] == P5 && Nat192.gte(z, P))) + { + addPInvTo(z); + } + } + + public static void addExt(int[] xx, int[] yy, int[] zz) + { + int c = Nat.add(12, xx, yy, zz); + if (c != 0 || (zz[11] == PExt11 && Nat.gte(12, zz, PExt))) + { + if (Nat.addTo(PExtInv.length, PExtInv, zz) != 0) + { + Nat.incAt(12, zz, PExtInv.length); + } + } + } + + public static void addOne(int[] x, int[] z) + { + int c = Nat.inc(6, x, z); + if (c != 0 || (z[5] == P5 && Nat192.gte(z, P))) + { + addPInvTo(z); + } + } + + public static int[] fromBigInteger(BigInteger x) + { + int[] z = Nat192.fromBigInteger(x); + if (z[5] == P5 && Nat192.gte(z, P)) + { + Nat192.subFrom(P, z); + } + return z; + } + + public static void half(int[] x, int[] z) + { + if ((x[0] & 1) == 0) + { + Nat.shiftDownBit(6, x, 0, z); + } + else + { + int c = Nat192.add(x, P, z); + Nat.shiftDownBit(6, z, c); + } + } + + public static void multiply(int[] x, int[] y, int[] z) + { + int[] tt = Nat192.createExt(); + Nat192.mul(x, y, tt); + reduce(tt, z); + } + + public static void multiplyAddToExt(int[] x, int[] y, int[] zz) + { + int c = Nat192.mulAddTo(x, y, zz); + if (c != 0 || (zz[11] == PExt11 && Nat.gte(12, zz, PExt))) + { + if (Nat.addTo(PExtInv.length, PExtInv, zz) != 0) + { + Nat.incAt(12, zz, PExtInv.length); + } + } + } + + public static void negate(int[] x, int[] z) + { + if (Nat192.isZero(x)) + { + Nat192.zero(z); + } + else + { + Nat192.sub(P, x, z); + } + } + + public static void reduce(int[] xx, int[] z) + { + long xx06 = xx[6] & M, xx07 = xx[7] & M, xx08 = xx[8] & M; + long xx09 = xx[9] & M, xx10 = xx[10] & M, xx11 = xx[11] & M; + + long t0 = xx06 + xx10; + long t1 = xx07 + xx11; + + long cc = 0; + cc += (xx[0] & M) + t0; + int z0 = (int)cc; + cc >>= 32; + cc += (xx[1] & M) + t1; + z[1] = (int)cc; + cc >>= 32; + + t0 += xx08; + t1 += xx09; + + cc += (xx[2] & M) + t0; + long z2 = cc & M; + cc >>= 32; + cc += (xx[3] & M) + t1; + z[3] = (int)cc; + cc >>= 32; + + t0 -= xx06; + t1 -= xx07; + + cc += (xx[4] & M) + t0; + z[4] = (int)cc; + cc >>= 32; + cc += (xx[5] & M) + t1; + z[5] = (int)cc; + cc >>= 32; + + z2 += cc; + + cc += (z0 & M); + z[0] = (int)cc; + cc >>= 32; + if (cc != 0) + { + cc += (z[1] & M); + z[1] = (int)cc; + z2 += cc >> 32; + } + z[2] = (int)z2; + cc = z2 >> 32; + +// assert cc == 0 || cc == 1; + + if ((cc != 0 && Nat.incAt(6, z, 3) != 0) + || (z[5] == P5 && Nat192.gte(z, P))) + { + addPInvTo(z); + } + } + + public static void reduce32(int x, int[] z) + { + long cc = 0; + + if (x != 0) + { + long xx06 = x & M; + + cc += (z[0] & M) + xx06; + z[0] = (int)cc; + cc >>= 32; + if (cc != 0) + { + cc += (z[1] & M); + z[1] = (int)cc; + cc >>= 32; + } + cc += (z[2] & M) + xx06; + z[2] = (int)cc; + cc >>= 32; + +// assert cc == 0 || cc == 1; + } + + if ((cc != 0 && Nat.incAt(6, z, 3) != 0) + || (z[5] == P5 && Nat192.gte(z, P))) + { + addPInvTo(z); + } + } + + public static void square(int[] x, int[] z) + { + int[] tt = Nat192.createExt(); + Nat192.square(x, tt); + reduce(tt, z); + } + + public static void squareN(int[] x, int n, int[] z) + { +// assert n > 0; + + int[] tt = Nat192.createExt(); + Nat192.square(x, tt); + reduce(tt, z); + + while (--n > 0) + { + Nat192.square(z, tt); + reduce(tt, z); + } + } + + public static void subtract(int[] x, int[] y, int[] z) + { + int c = Nat192.sub(x, y, z); + if (c != 0) + { + subPInvFrom(z); + } + } + + public static void subtractExt(int[] xx, int[] yy, int[] zz) + { + int c = Nat.sub(12, xx, yy, zz); + if (c != 0) + { + if (Nat.subFrom(PExtInv.length, PExtInv, zz) != 0) + { + Nat.decAt(12, zz, PExtInv.length); + } + } + } + + public static void twice(int[] x, int[] z) + { + int c = Nat.shiftUpBit(6, x, 0, z); + if (c != 0 || (z[5] == P5 && Nat192.gte(z, P))) + { + addPInvTo(z); + } + } + + private static void addPInvTo(int[] z) + { + long c = (z[0] & M) + 1; + z[0] = (int)c; + c >>= 32; + if (c != 0) + { + c += (z[1] & M); + z[1] = (int)c; + c >>= 32; + } + c += (z[2] & M) + 1; + z[2] = (int)c; + c >>= 32; + if (c != 0) + { + Nat.incAt(6, z, 3); + } + } + + private static void subPInvFrom(int[] z) + { + long c = (z[0] & M) - 1; + z[0] = (int)c; + c >>= 32; + if (c != 0) + { + c += (z[1] & M); + z[1] = (int)c; + c >>= 32; + } + c += (z[2] & M) - 1; + z[2] = (int)c; + c >>= 32; + if (c != 0) + { + Nat.decAt(6, z, 3); + } + } +} diff --git a/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP192R1FieldElement.java b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP192R1FieldElement.java new file mode 100644 index 00000000..2ab5030c --- /dev/null +++ b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP192R1FieldElement.java @@ -0,0 +1,190 @@ +package org.spongycastle.math.ec.custom.sec; + +import java.math.BigInteger; + +import org.spongycastle.math.ec.ECFieldElement; +import org.spongycastle.math.raw.Mod; +import org.spongycastle.math.raw.Nat192; +import org.spongycastle.util.Arrays; + +public class SecP192R1FieldElement extends ECFieldElement +{ + public static final BigInteger Q = SecP192R1Curve.q; + + protected int[] x; + + public SecP192R1FieldElement(BigInteger x) + { + if (x == null || x.signum() < 0 || x.compareTo(Q) >= 0) + { + throw new IllegalArgumentException("x value invalid for SecP192R1FieldElement"); + } + + this.x = SecP192R1Field.fromBigInteger(x); + } + + public SecP192R1FieldElement() + { + this.x = Nat192.create(); + } + + protected SecP192R1FieldElement(int[] x) + { + this.x = x; + } + + public boolean isZero() + { + return Nat192.isZero(x); + } + + public boolean isOne() + { + return Nat192.isOne(x); + } + + public boolean testBitZero() + { + return Nat192.getBit(x, 0) == 1; + } + + public BigInteger toBigInteger() + { + return Nat192.toBigInteger(x); + } + + public String getFieldName() + { + return "SecP192R1Field"; + } + + public int getFieldSize() + { + return Q.bitLength(); + } + + public ECFieldElement add(ECFieldElement b) + { + int[] z = Nat192.create(); + SecP192R1Field.add(x, ((SecP192R1FieldElement)b).x, z); + return new SecP192R1FieldElement(z); + } + + public ECFieldElement addOne() + { + int[] z = Nat192.create(); + SecP192R1Field.addOne(x, z); + return new SecP192R1FieldElement(z); + } + + public ECFieldElement subtract(ECFieldElement b) + { + int[] z = Nat192.create(); + SecP192R1Field.subtract(x, ((SecP192R1FieldElement)b).x, z); + return new SecP192R1FieldElement(z); + } + + public ECFieldElement multiply(ECFieldElement b) + { + int[] z = Nat192.create(); + SecP192R1Field.multiply(x, ((SecP192R1FieldElement)b).x, z); + return new SecP192R1FieldElement(z); + } + + public ECFieldElement divide(ECFieldElement b) + { +// return multiply(b.invert()); + int[] z = Nat192.create(); + Mod.invert(SecP192R1Field.P, ((SecP192R1FieldElement)b).x, z); + SecP192R1Field.multiply(z, x, z); + return new SecP192R1FieldElement(z); + } + + public ECFieldElement negate() + { + int[] z = Nat192.create(); + SecP192R1Field.negate(x, z); + return new SecP192R1FieldElement(z); + } + + public ECFieldElement square() + { + int[] z = Nat192.create(); + SecP192R1Field.square(x, z); + return new SecP192R1FieldElement(z); + } + + public ECFieldElement invert() + { +// return new SecP192R1FieldElement(toBigInteger().modInverse(Q)); + int[] z = Nat192.create(); + Mod.invert(SecP192R1Field.P, x, z); + return new SecP192R1FieldElement(z); + } + + // D.1.4 91 + /** + * return a sqrt root - the routine verifies that the calculation returns the right value - if + * none exists it returns null. + */ + public ECFieldElement sqrt() + { + // Raise this element to the exponent 2^190 - 2^62 + + int[] x1 = this.x; + if (Nat192.isZero(x1) || Nat192.isOne(x1)) + { + return this; + } + + int[] t1 = Nat192.create(); + int[] t2 = Nat192.create(); + + SecP192R1Field.square(x1, t1); + SecP192R1Field.multiply(t1, x1, t1); + + SecP192R1Field.squareN(t1, 2, t2); + SecP192R1Field.multiply(t2, t1, t2); + + SecP192R1Field.squareN(t2, 4, t1); + SecP192R1Field.multiply(t1, t2, t1); + + SecP192R1Field.squareN(t1, 8, t2); + SecP192R1Field.multiply(t2, t1, t2); + + SecP192R1Field.squareN(t2, 16, t1); + SecP192R1Field.multiply(t1, t2, t1); + + SecP192R1Field.squareN(t1, 32, t2); + SecP192R1Field.multiply(t2, t1, t2); + + SecP192R1Field.squareN(t2, 64, t1); + SecP192R1Field.multiply(t1, t2, t1); + + SecP192R1Field.squareN(t1, 62, t1); + SecP192R1Field.square(t1, t2); + + return Nat192.eq(x1, t2) ? new SecP192R1FieldElement(t1) : null; + } + + public boolean equals(Object other) + { + if (other == this) + { + return true; + } + + if (!(other instanceof SecP192R1FieldElement)) + { + return false; + } + + SecP192R1FieldElement o = (SecP192R1FieldElement)other; + return Nat192.eq(x, o.x); + } + + public int hashCode() + { + return Q.hashCode() ^ Arrays.hashCode(x, 0, 6); + } +} diff --git a/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP192R1Point.java b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP192R1Point.java new file mode 100644 index 00000000..9d611267 --- /dev/null +++ b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP192R1Point.java @@ -0,0 +1,310 @@ +package org.spongycastle.math.ec.custom.sec; + +import org.spongycastle.math.ec.ECCurve; +import org.spongycastle.math.ec.ECFieldElement; +import org.spongycastle.math.ec.ECPoint; +import org.spongycastle.math.raw.Nat; +import org.spongycastle.math.raw.Nat192; + +public class SecP192R1Point extends ECPoint.AbstractFp +{ + /** + * Create a point which encodes with 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 SecP192R1Point(ECCurve curve, ECFieldElement x, ECFieldElement y) + { + this(curve, x, y, false); + } + + /** + * Create a point that encodes with or without point compresion. + * + * @param curve + * the curve to use + * @param x + * affine x co-ordinate + * @param y + * affine y co-ordinate + * @param withCompression + * if true encode with point compression + * + * @deprecated per-point compression property will be removed, refer + * {@link #getEncoded(boolean)} + */ + public SecP192R1Point(ECCurve curve, ECFieldElement x, ECFieldElement y, boolean withCompression) + { + super(curve, x, y); + + if ((x == null) != (y == null)) + { + throw new IllegalArgumentException("Exactly one of the field elements is null"); + } + + this.withCompression = withCompression; + } + + SecP192R1Point(ECCurve curve, ECFieldElement x, ECFieldElement y, ECFieldElement[] zs, boolean withCompression) + { + super(curve, x, y, zs); + + this.withCompression = withCompression; + } + + protected ECPoint detach() + { + return new SecP192R1Point(null, getAffineXCoord(), getAffineYCoord()); + } + + // B.3 pg 62 + public ECPoint add(ECPoint b) + { + if (this.isInfinity()) + { + return b; + } + if (b.isInfinity()) + { + return this; + } + if (this == b) + { + return twice(); + } + + ECCurve curve = this.getCurve(); + + SecP192R1FieldElement X1 = (SecP192R1FieldElement)this.x, Y1 = (SecP192R1FieldElement)this.y; + SecP192R1FieldElement X2 = (SecP192R1FieldElement)b.getXCoord(), Y2 = (SecP192R1FieldElement)b.getYCoord(); + + SecP192R1FieldElement Z1 = (SecP192R1FieldElement)this.zs[0]; + SecP192R1FieldElement Z2 = (SecP192R1FieldElement)b.getZCoord(0); + + int c; + int[] tt1 = Nat192.createExt(); + int[] t2 = Nat192.create(); + int[] t3 = Nat192.create(); + int[] t4 = Nat192.create(); + + boolean Z1IsOne = Z1.isOne(); + int[] U2, S2; + if (Z1IsOne) + { + U2 = X2.x; + S2 = Y2.x; + } + else + { + S2 = t3; + SecP192R1Field.square(Z1.x, S2); + + U2 = t2; + SecP192R1Field.multiply(S2, X2.x, U2); + + SecP192R1Field.multiply(S2, Z1.x, S2); + SecP192R1Field.multiply(S2, Y2.x, S2); + } + + boolean Z2IsOne = Z2.isOne(); + int[] U1, S1; + if (Z2IsOne) + { + U1 = X1.x; + S1 = Y1.x; + } + else + { + S1 = t4; + SecP192R1Field.square(Z2.x, S1); + + U1 = tt1; + SecP192R1Field.multiply(S1, X1.x, U1); + + SecP192R1Field.multiply(S1, Z2.x, S1); + SecP192R1Field.multiply(S1, Y1.x, S1); + } + + int[] H = Nat192.create(); + SecP192R1Field.subtract(U1, U2, H); + + int[] R = t2; + SecP192R1Field.subtract(S1, S2, R); + + // Check if b == this or b == -this + if (Nat192.isZero(H)) + { + if (Nat192.isZero(R)) + { + // this == b, i.e. this must be doubled + return this.twice(); + } + + // this == -b, i.e. the result is the point at infinity + return curve.getInfinity(); + } + + int[] HSquared = t3; + SecP192R1Field.square(H, HSquared); + + int[] G = Nat192.create(); + SecP192R1Field.multiply(HSquared, H, G); + + int[] V = t3; + SecP192R1Field.multiply(HSquared, U1, V); + + SecP192R1Field.negate(G, G); + Nat192.mul(S1, G, tt1); + + c = Nat192.addBothTo(V, V, G); + SecP192R1Field.reduce32(c, G); + + SecP192R1FieldElement X3 = new SecP192R1FieldElement(t4); + SecP192R1Field.square(R, X3.x); + SecP192R1Field.subtract(X3.x, G, X3.x); + + SecP192R1FieldElement Y3 = new SecP192R1FieldElement(G); + SecP192R1Field.subtract(V, X3.x, Y3.x); + SecP192R1Field.multiplyAddToExt(Y3.x, R, tt1); + SecP192R1Field.reduce(tt1, Y3.x); + + SecP192R1FieldElement Z3 = new SecP192R1FieldElement(H); + if (!Z1IsOne) + { + SecP192R1Field.multiply(Z3.x, Z1.x, Z3.x); + } + if (!Z2IsOne) + { + SecP192R1Field.multiply(Z3.x, Z2.x, Z3.x); + } + + ECFieldElement[] zs = new ECFieldElement[]{ Z3 }; + + return new SecP192R1Point(curve, X3, Y3, zs, this.withCompression); + } + + // B.3 pg 62 + public ECPoint twice() + { + if (this.isInfinity()) + { + return this; + } + + ECCurve curve = this.getCurve(); + + SecP192R1FieldElement Y1 = (SecP192R1FieldElement)this.y; + if (Y1.isZero()) + { + return curve.getInfinity(); + } + + SecP192R1FieldElement X1 = (SecP192R1FieldElement)this.x, Z1 = (SecP192R1FieldElement)this.zs[0]; + + int c; + int[] t1 = Nat192.create(); + int[] t2 = Nat192.create(); + + int[] Y1Squared = Nat192.create(); + SecP192R1Field.square(Y1.x, Y1Squared); + + int[] T = Nat192.create(); + SecP192R1Field.square(Y1Squared, T); + + boolean Z1IsOne = Z1.isOne(); + + int[] Z1Squared = Z1.x; + if (!Z1IsOne) + { + Z1Squared = t2; + SecP192R1Field.square(Z1.x, Z1Squared); + } + + SecP192R1Field.subtract(X1.x, Z1Squared, t1); + + int[] M = t2; + SecP192R1Field.add(X1.x, Z1Squared, M); + SecP192R1Field.multiply(M, t1, M); + c = Nat192.addBothTo(M, M, M); + SecP192R1Field.reduce32(c, M); + + int[] S = Y1Squared; + SecP192R1Field.multiply(Y1Squared, X1.x, S); + c = Nat.shiftUpBits(6, S, 2, 0); + SecP192R1Field.reduce32(c, S); + + c = Nat.shiftUpBits(6, T, 3, 0, t1); + SecP192R1Field.reduce32(c, t1); + + SecP192R1FieldElement X3 = new SecP192R1FieldElement(T); + SecP192R1Field.square(M, X3.x); + SecP192R1Field.subtract(X3.x, S, X3.x); + SecP192R1Field.subtract(X3.x, S, X3.x); + + SecP192R1FieldElement Y3 = new SecP192R1FieldElement(S); + SecP192R1Field.subtract(S, X3.x, Y3.x); + SecP192R1Field.multiply(Y3.x, M, Y3.x); + SecP192R1Field.subtract(Y3.x, t1, Y3.x); + + SecP192R1FieldElement Z3 = new SecP192R1FieldElement(M); + SecP192R1Field.twice(Y1.x, Z3.x); + if (!Z1IsOne) + { + SecP192R1Field.multiply(Z3.x, Z1.x, Z3.x); + } + + return new SecP192R1Point(curve, X3, Y3, new ECFieldElement[]{ Z3 }, this.withCompression); + } + + public ECPoint twicePlus(ECPoint b) + { + if (this == b) + { + return threeTimes(); + } + if (this.isInfinity()) + { + return b; + } + if (b.isInfinity()) + { + return twice(); + } + + ECFieldElement Y1 = this.y; + if (Y1.isZero()) + { + return b; + } + + return twice().add(b); + } + + public ECPoint threeTimes() + { + if (this.isInfinity() || this.y.isZero()) + { + return this; + } + + // NOTE: Be careful about recursions between twicePlus and threeTimes + return twice().add(this); + } + + public ECPoint negate() + { + if (this.isInfinity()) + { + return this; + } + + return new SecP192R1Point(curve, this.x, this.y.negate(), this.zs, this.withCompression); + } +} diff --git a/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP224K1Curve.java b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP224K1Curve.java new file mode 100644 index 00000000..9b26b6f8 --- /dev/null +++ b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP224K1Curve.java @@ -0,0 +1,78 @@ +package org.spongycastle.math.ec.custom.sec; + +import java.math.BigInteger; + +import org.spongycastle.math.ec.ECConstants; +import org.spongycastle.math.ec.ECCurve; +import org.spongycastle.math.ec.ECFieldElement; +import org.spongycastle.math.ec.ECPoint; +import org.spongycastle.util.encoders.Hex; + +public class SecP224K1Curve extends ECCurve.AbstractFp +{ + public static final BigInteger q = new BigInteger(1, + Hex.decode("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFE56D")); + + private static final int SECP224K1_DEFAULT_COORDS = COORD_JACOBIAN; + + protected SecP224K1Point infinity; + + public SecP224K1Curve() + { + super(q); + + this.infinity = new SecP224K1Point(this, null, null); + + this.a = fromBigInteger(ECConstants.ZERO); + this.b = fromBigInteger(BigInteger.valueOf(5)); + this.order = new BigInteger(1, Hex.decode("010000000000000000000000000001DCE8D2EC6184CAF0A971769FB1F7")); + this.cofactor = BigInteger.valueOf(1); + this.coord = SECP224K1_DEFAULT_COORDS; + } + + protected ECCurve cloneCurve() + { + return new SecP224K1Curve(); + } + + public boolean supportsCoordinateSystem(int coord) + { + switch (coord) + { + case COORD_JACOBIAN: + return true; + default: + return false; + } + } + + public BigInteger getQ() + { + return q; + } + + public int getFieldSize() + { + return q.bitLength(); + } + + public ECFieldElement fromBigInteger(BigInteger x) + { + return new SecP224K1FieldElement(x); + } + + protected ECPoint createRawPoint(ECFieldElement x, ECFieldElement y, boolean withCompression) + { + return new SecP224K1Point(this, x, y, withCompression); + } + + protected ECPoint createRawPoint(ECFieldElement x, ECFieldElement y, ECFieldElement[] zs, boolean withCompression) + { + return new SecP224K1Point(this, x, y, zs, withCompression); + } + + public ECPoint getInfinity() + { + return infinity; + } +} diff --git a/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP224K1Field.java b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP224K1Field.java new file mode 100644 index 00000000..0db90e56 --- /dev/null +++ b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP224K1Field.java @@ -0,0 +1,178 @@ +package org.spongycastle.math.ec.custom.sec; + +import java.math.BigInteger; + +import org.spongycastle.math.raw.Nat; +import org.spongycastle.math.raw.Nat224; + +public class SecP224K1Field +{ + // 2^224 - 2^32 - 2^12 - 2^11 - 2^9 - 2^7 - 2^4 - 2 - 1 + static final int[] P = new int[]{ 0xFFFFE56D, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, + 0xFFFFFFFF }; + static final int[] PExt = new int[]{ 0x02C23069, 0x00003526, 0x00000001, 0x00000000, 0x00000000, + 0x00000000, 0x00000000, 0xFFFFCADA, 0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF }; + private static final int[] PExtInv = new int[]{ 0xFD3DCF97, 0xFFFFCAD9, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, + 0xFFFFFFFF, 0xFFFFFFFF, 0x00003525, 0x00000002 }; + private static final int P6 = 0xFFFFFFFF; + private static final int PExt13 = 0xFFFFFFFF; + private static final int PInv33 = 0x1A93; + + public static void add(int[] x, int[] y, int[] z) + { + int c = Nat224.add(x, y, z); + if (c != 0 || (z[6] == P6 && Nat224.gte(z, P))) + { + Nat.add33To(7, PInv33, z); + } + } + + public static void addExt(int[] xx, int[] yy, int[] zz) + { + int c = Nat.add(14, xx, yy, zz); + if (c != 0 || (zz[13] == PExt13 && Nat.gte(14, zz, PExt))) + { + if (Nat.addTo(PExtInv.length, PExtInv, zz) != 0) + { + Nat.incAt(14, zz, PExtInv.length); + } + } + } + + public static void addOne(int[] x, int[] z) + { + int c = Nat.inc(7, x, z); + if (c != 0 || (z[6] == P6 && Nat224.gte(z, P))) + { + Nat.add33To(7, PInv33, z); + } + } + + public static int[] fromBigInteger(BigInteger x) + { + int[] z = Nat224.fromBigInteger(x); + if (z[6] == P6 && Nat224.gte(z, P)) + { + Nat.add33To(7, PInv33, z); + } + return z; + } + + public static void half(int[] x, int[] z) + { + if ((x[0] & 1) == 0) + { + Nat.shiftDownBit(7, x, 0, z); + } + else + { + int c = Nat224.add(x, P, z); + Nat.shiftDownBit(7, z, c); + } + } + + public static void multiply(int[] x, int[] y, int[] z) + { + int[] tt = Nat224.createExt(); + Nat224.mul(x, y, tt); + reduce(tt, z); + } + + public static void multiplyAddToExt(int[] x, int[] y, int[] zz) + { + int c = Nat224.mulAddTo(x, y, zz); + if (c != 0 || (zz[13] == PExt13 && Nat.gte(14, zz, PExt))) + { + if (Nat.addTo(PExtInv.length, PExtInv, zz) != 0) + { + Nat.incAt(14, zz, PExtInv.length); + } + } + } + + public static void negate(int[] x, int[] z) + { + if (Nat224.isZero(x)) + { + Nat224.zero(z); + } + else + { + Nat224.sub(P, x, z); + } + } + + public static void reduce(int[] xx, int[] z) + { + long cc = Nat224.mul33Add(PInv33, xx, 7, xx, 0, z, 0); + int c = Nat224.mul33DWordAdd(PInv33, cc, z, 0); + + // assert c == 0L || c == 1L; + + if (c != 0 || (z[6] == P6 && Nat224.gte(z, P))) + { + Nat.add33To(7, PInv33, z); + } + } + + public static void reduce32(int x, int[] z) + { + if ((x != 0 && Nat224.mul33WordAdd(PInv33, x, z, 0) != 0) + || (z[6] == P6 && Nat224.gte(z, P))) + { + Nat.add33To(7, PInv33, z); + } + } + + public static void square(int[] x, int[] z) + { + int[] tt = Nat224.createExt(); + Nat224.square(x, tt); + reduce(tt, z); + } + + public static void squareN(int[] x, int n, int[] z) + { +// assert n > 0; + + int[] tt = Nat224.createExt(); + Nat224.square(x, tt); + reduce(tt, z); + + while (--n > 0) + { + Nat224.square(z, tt); + reduce(tt, z); + } + } + + public static void subtract(int[] x, int[] y, int[] z) + { + int c = Nat224.sub(x, y, z); + if (c != 0) + { + Nat.sub33From(7, PInv33, z); + } + } + + public static void subtractExt(int[] xx, int[] yy, int[] zz) + { + int c = Nat.sub(14, xx, yy, zz); + if (c != 0) + { + if (Nat.subFrom(PExtInv.length, PExtInv, zz) != 0) + { + Nat.decAt(14, zz, PExtInv.length); + } + } + } + + public static void twice(int[] x, int[] z) + { + int c = Nat.shiftUpBit(7, x, 0, z); + if (c != 0 || (z[6] == P6 && Nat224.gte(z, P))) + { + Nat.add33To(7, PInv33, z); + } + } +} diff --git a/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP224K1FieldElement.java b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP224K1FieldElement.java new file mode 100644 index 00000000..655b9592 --- /dev/null +++ b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP224K1FieldElement.java @@ -0,0 +1,243 @@ +package org.spongycastle.math.ec.custom.sec; + +import java.math.BigInteger; + +import org.spongycastle.math.ec.ECFieldElement; +import org.spongycastle.math.raw.Mod; +import org.spongycastle.math.raw.Nat224; +import org.spongycastle.util.Arrays; + +public class SecP224K1FieldElement extends ECFieldElement +{ + public static final BigInteger Q = SecP224K1Curve.q; + + // Calculated as ECConstants.TWO.modPow(Q.shiftRight(2), Q) + private static final int[] PRECOMP_POW2 = new int[]{ 0x33bfd202, 0xdcfad133, 0x2287624a, 0xc3811ba8, + 0xa85558fc, 0x1eaef5d7, 0x8edf154c }; + + protected int[] x; + + public SecP224K1FieldElement(BigInteger x) + { + if (x == null || x.signum() < 0 || x.compareTo(Q) >= 0) + { + throw new IllegalArgumentException("x value invalid for SecP224K1FieldElement"); + } + + this.x = SecP224K1Field.fromBigInteger(x); + } + + public SecP224K1FieldElement() + { + this.x = Nat224.create(); + } + + protected SecP224K1FieldElement(int[] x) + { + this.x = x; + } + + public boolean isZero() + { + return Nat224.isZero(x); + } + + public boolean isOne() + { + return Nat224.isOne(x); + } + + public boolean testBitZero() + { + return Nat224.getBit(x, 0) == 1; + } + + public BigInteger toBigInteger() + { + return Nat224.toBigInteger(x); + } + + public String getFieldName() + { + return "SecP224K1Field"; + } + + public int getFieldSize() + { + return Q.bitLength(); + } + + public ECFieldElement add(ECFieldElement b) + { + int[] z = Nat224.create(); + SecP224K1Field.add(x, ((SecP224K1FieldElement)b).x, z); + return new SecP224K1FieldElement(z); + } + + public ECFieldElement addOne() + { + int[] z = Nat224.create(); + SecP224K1Field.addOne(x, z); + return new SecP224K1FieldElement(z); + } + + public ECFieldElement subtract(ECFieldElement b) + { + int[] z = Nat224.create(); + SecP224K1Field.subtract(x, ((SecP224K1FieldElement)b).x, z); + return new SecP224K1FieldElement(z); + } + + public ECFieldElement multiply(ECFieldElement b) + { + int[] z = Nat224.create(); + SecP224K1Field.multiply(x, ((SecP224K1FieldElement)b).x, z); + return new SecP224K1FieldElement(z); + } + + public ECFieldElement divide(ECFieldElement b) + { +// return multiply(b.invert()); + int[] z = Nat224.create(); + Mod.invert(SecP224K1Field.P, ((SecP224K1FieldElement)b).x, z); + SecP224K1Field.multiply(z, x, z); + return new SecP224K1FieldElement(z); + } + + public ECFieldElement negate() + { + int[] z = Nat224.create(); + SecP224K1Field.negate(x, z); + return new SecP224K1FieldElement(z); + } + + public ECFieldElement square() + { + int[] z = Nat224.create(); + SecP224K1Field.square(x, z); + return new SecP224K1FieldElement(z); + } + + public ECFieldElement invert() + { +// return new SecP224K1FieldElement(toBigInteger().modInverse(Q)); + int[] z = Nat224.create(); + Mod.invert(SecP224K1Field.P, x, z); + return new SecP224K1FieldElement(z); + } + + // D.1.4 91 + /** + * return a sqrt root - the routine verifies that the calculation returns the right value - if + * none exists it returns null. + */ + public ECFieldElement sqrt() + { + /* + * Q == 8m + 5, so we use Pocklington's method for this case. + * + * First, raise this element to the exponent 2^221 - 2^29 - 2^9 - 2^8 - 2^6 - 2^4 - 2^1 (i.e. m + 1) + * + * Breaking up the exponent's binary representation into "repunits", we get: + * { 191 1s } { 1 0s } { 19 1s } { 2 0s } { 1 1s } { 1 0s} { 1 1s } { 1 0s} { 3 1s } { 1 0s} + * + * Therefore we need an addition chain containing 1, 3, 19, 191 (the lengths of the repunits) + * We use: [1], 2, [3], 4, 8, 11, [19], 23, 42, 84, 107, [191] + */ + + int[] x1 = this.x; + if (Nat224.isZero(x1) || Nat224.isOne(x1)) + { + return this; + } + + int[] x2 = Nat224.create(); + SecP224K1Field.square(x1, x2); + SecP224K1Field.multiply(x2, x1, x2); + int[] x3 = x2; + SecP224K1Field.square(x2, x3); + SecP224K1Field.multiply(x3, x1, x3); + int[] x4 = Nat224.create(); + SecP224K1Field.square(x3, x4); + SecP224K1Field.multiply(x4, x1, x4); + int[] x8 = Nat224.create(); + SecP224K1Field.squareN(x4, 4, x8); + SecP224K1Field.multiply(x8, x4, x8); + int[] x11 = Nat224.create(); + SecP224K1Field.squareN(x8, 3, x11); + SecP224K1Field.multiply(x11, x3, x11); + int[] x19 = x11; + SecP224K1Field.squareN(x11, 8, x19); + SecP224K1Field.multiply(x19, x8, x19); + int[] x23 = x8; + SecP224K1Field.squareN(x19, 4, x23); + SecP224K1Field.multiply(x23, x4, x23); + int[] x42 = x4; + SecP224K1Field.squareN(x23, 19, x42); + SecP224K1Field.multiply(x42, x19, x42); + int[] x84 = Nat224.create(); + SecP224K1Field.squareN(x42, 42, x84); + SecP224K1Field.multiply(x84, x42, x84); + int[] x107 = x42; + SecP224K1Field.squareN(x84, 23, x107); + SecP224K1Field.multiply(x107, x23, x107); + int[] x191 = x23; + SecP224K1Field.squareN(x107, 84, x191); + SecP224K1Field.multiply(x191, x84, x191); + + int[] t1 = x191; + SecP224K1Field.squareN(t1, 20, t1); + SecP224K1Field.multiply(t1, x19, t1); + SecP224K1Field.squareN(t1, 3, t1); + SecP224K1Field.multiply(t1, x1, t1); + SecP224K1Field.squareN(t1, 2, t1); + SecP224K1Field.multiply(t1, x1, t1); + SecP224K1Field.squareN(t1, 4, t1); + SecP224K1Field.multiply(t1, x3, t1); + SecP224K1Field.square(t1, t1); + + int[] t2 = x84; + SecP224K1Field.square(t1, t2); + + if (Nat224.eq(x1, t2)) + { + return new SecP224K1FieldElement(t1); + } + + /* + * If the first guess is incorrect, we multiply by a precomputed power of 2 to get the second guess, + * which is ((4x)^(m + 1))/2 mod Q + */ + SecP224K1Field.multiply(t1, PRECOMP_POW2, t1); + + SecP224K1Field.square(t1, t2); + + if (Nat224.eq(x1, t2)) + { + return new SecP224K1FieldElement(t1); + } + + return null; + } + + public boolean equals(Object other) + { + if (other == this) + { + return true; + } + + if (!(other instanceof SecP224K1FieldElement)) + { + return false; + } + + SecP224K1FieldElement o = (SecP224K1FieldElement)other; + return Nat224.eq(x, o.x); + } + + public int hashCode() + { + return Q.hashCode() ^ Arrays.hashCode(x, 0, 7); + } +} diff --git a/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP224K1Point.java b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP224K1Point.java new file mode 100644 index 00000000..e33bc5fd --- /dev/null +++ b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP224K1Point.java @@ -0,0 +1,298 @@ +package org.spongycastle.math.ec.custom.sec; + +import org.spongycastle.math.ec.ECCurve; +import org.spongycastle.math.ec.ECFieldElement; +import org.spongycastle.math.ec.ECPoint; +import org.spongycastle.math.raw.Nat; +import org.spongycastle.math.raw.Nat224; + +public class SecP224K1Point extends ECPoint.AbstractFp +{ + /** + * Create a point which encodes with 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 SecP224K1Point(ECCurve curve, ECFieldElement x, ECFieldElement y) + { + this(curve, x, y, false); + } + + /** + * Create a point that encodes with or without point compresion. + * + * @param curve + * the curve to use + * @param x + * affine x co-ordinate + * @param y + * affine y co-ordinate + * @param withCompression + * if true encode with point compression + * + * @deprecated per-point compression property will be removed, refer + * {@link #getEncoded(boolean)} + */ + public SecP224K1Point(ECCurve curve, ECFieldElement x, ECFieldElement y, boolean withCompression) + { + super(curve, x, y); + + if ((x == null) != (y == null)) + { + throw new IllegalArgumentException("Exactly one of the field elements is null"); + } + + this.withCompression = withCompression; + } + + SecP224K1Point(ECCurve curve, ECFieldElement x, ECFieldElement y, ECFieldElement[] zs, + boolean withCompression) + { + super(curve, x, y, zs); + + this.withCompression = withCompression; + } + + protected ECPoint detach() + { + return new SecP224K1Point(null, getAffineXCoord(), getAffineYCoord()); + } + + // B.3 pg 62 + public ECPoint add(ECPoint b) + { + if (this.isInfinity()) + { + return b; + } + if (b.isInfinity()) + { + return this; + } + if (this == b) + { + return twice(); + } + + ECCurve curve = this.getCurve(); + + SecP224K1FieldElement X1 = (SecP224K1FieldElement)this.x, Y1 = (SecP224K1FieldElement)this.y; + SecP224K1FieldElement X2 = (SecP224K1FieldElement)b.getXCoord(), Y2 = (SecP224K1FieldElement)b.getYCoord(); + + SecP224K1FieldElement Z1 = (SecP224K1FieldElement)this.zs[0]; + SecP224K1FieldElement Z2 = (SecP224K1FieldElement)b.getZCoord(0); + + int c; + int[] tt1 = Nat224.createExt(); + int[] t2 = Nat224.create(); + int[] t3 = Nat224.create(); + int[] t4 = Nat224.create(); + + boolean Z1IsOne = Z1.isOne(); + int[] U2, S2; + if (Z1IsOne) + { + U2 = X2.x; + S2 = Y2.x; + } + else + { + S2 = t3; + SecP224K1Field.square(Z1.x, S2); + + U2 = t2; + SecP224K1Field.multiply(S2, X2.x, U2); + + SecP224K1Field.multiply(S2, Z1.x, S2); + SecP224K1Field.multiply(S2, Y2.x, S2); + } + + boolean Z2IsOne = Z2.isOne(); + int[] U1, S1; + if (Z2IsOne) + { + U1 = X1.x; + S1 = Y1.x; + } + else + { + S1 = t4; + SecP224K1Field.square(Z2.x, S1); + + U1 = tt1; + SecP224K1Field.multiply(S1, X1.x, U1); + + SecP224K1Field.multiply(S1, Z2.x, S1); + SecP224K1Field.multiply(S1, Y1.x, S1); + } + + int[] H = Nat224.create(); + SecP224K1Field.subtract(U1, U2, H); + + int[] R = t2; + SecP224K1Field.subtract(S1, S2, R); + + // Check if b == this or b == -this + if (Nat224.isZero(H)) + { + if (Nat224.isZero(R)) + { + // this == b, i.e. this must be doubled + return this.twice(); + } + + // this == -b, i.e. the result is the point at infinity + return curve.getInfinity(); + } + + int[] HSquared = t3; + SecP224K1Field.square(H, HSquared); + + int[] G = Nat224.create(); + SecP224K1Field.multiply(HSquared, H, G); + + int[] V = t3; + SecP224K1Field.multiply(HSquared, U1, V); + + SecP224K1Field.negate(G, G); + Nat224.mul(S1, G, tt1); + + c = Nat224.addBothTo(V, V, G); + SecP224K1Field.reduce32(c, G); + + SecP224K1FieldElement X3 = new SecP224K1FieldElement(t4); + SecP224K1Field.square(R, X3.x); + SecP224K1Field.subtract(X3.x, G, X3.x); + + SecP224K1FieldElement Y3 = new SecP224K1FieldElement(G); + SecP224K1Field.subtract(V, X3.x, Y3.x); + SecP224K1Field.multiplyAddToExt(Y3.x, R, tt1); + SecP224K1Field.reduce(tt1, Y3.x); + + SecP224K1FieldElement Z3 = new SecP224K1FieldElement(H); + if (!Z1IsOne) + { + SecP224K1Field.multiply(Z3.x, Z1.x, Z3.x); + } + if (!Z2IsOne) + { + SecP224K1Field.multiply(Z3.x, Z2.x, Z3.x); + } + + ECFieldElement[] zs = new ECFieldElement[] { Z3 }; + + return new SecP224K1Point(curve, X3, Y3, zs, this.withCompression); + } + + // B.3 pg 62 + public ECPoint twice() + { + if (this.isInfinity()) + { + return this; + } + + ECCurve curve = this.getCurve(); + + SecP224K1FieldElement Y1 = (SecP224K1FieldElement)this.y; + if (Y1.isZero()) + { + return curve.getInfinity(); + } + + SecP224K1FieldElement X1 = (SecP224K1FieldElement)this.x, Z1 = (SecP224K1FieldElement)this.zs[0]; + + int c; + + int[] Y1Squared = Nat224.create(); + SecP224K1Field.square(Y1.x, Y1Squared); + + int[] T = Nat224.create(); + SecP224K1Field.square(Y1Squared, T); + + int[] M = Nat224.create(); + SecP224K1Field.square(X1.x, M); + c = Nat224.addBothTo(M, M, M); + SecP224K1Field.reduce32(c, M); + + int[] S = Y1Squared; + SecP224K1Field.multiply(Y1Squared, X1.x, S); + c = Nat.shiftUpBits(7, S, 2, 0); + SecP224K1Field.reduce32(c, S); + + int[] t1 = Nat224.create(); + c = Nat.shiftUpBits(7, T, 3, 0, t1); + SecP224K1Field.reduce32(c, t1); + + SecP224K1FieldElement X3 = new SecP224K1FieldElement(T); + SecP224K1Field.square(M, X3.x); + SecP224K1Field.subtract(X3.x, S, X3.x); + SecP224K1Field.subtract(X3.x, S, X3.x); + + SecP224K1FieldElement Y3 = new SecP224K1FieldElement(S); + SecP224K1Field.subtract(S, X3.x, Y3.x); + SecP224K1Field.multiply(Y3.x, M, Y3.x); + SecP224K1Field.subtract(Y3.x, t1, Y3.x); + + SecP224K1FieldElement Z3 = new SecP224K1FieldElement(M); + SecP224K1Field.twice(Y1.x, Z3.x); + if (!Z1.isOne()) + { + SecP224K1Field.multiply(Z3.x, Z1.x, Z3.x); + } + + return new SecP224K1Point(curve, X3, Y3, new ECFieldElement[] { Z3 }, this.withCompression); + } + + public ECPoint twicePlus(ECPoint b) + { + if (this == b) + { + return threeTimes(); + } + if (this.isInfinity()) + { + return b; + } + if (b.isInfinity()) + { + return twice(); + } + + ECFieldElement Y1 = this.y; + if (Y1.isZero()) + { + return b; + } + + return twice().add(b); + } + + public ECPoint threeTimes() + { + if (this.isInfinity() || this.y.isZero()) + { + return this; + } + + // NOTE: Be careful about recursions between twicePlus and threeTimes + return twice().add(this); + } + + public ECPoint negate() + { + if (this.isInfinity()) + { + return this; + } + + return new SecP224K1Point(curve, this.x, this.y.negate(), this.zs, this.withCompression); + } +} diff --git a/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP224R1Curve.java b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP224R1Curve.java new file mode 100644 index 00000000..e81cca7f --- /dev/null +++ b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP224R1Curve.java @@ -0,0 +1,80 @@ +package org.spongycastle.math.ec.custom.sec; + +import java.math.BigInteger; + +import org.spongycastle.math.ec.ECCurve; +import org.spongycastle.math.ec.ECFieldElement; +import org.spongycastle.math.ec.ECPoint; +import org.spongycastle.util.encoders.Hex; + +public class SecP224R1Curve extends ECCurve.AbstractFp +{ + public static final BigInteger q = new BigInteger(1, + Hex.decode("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF000000000000000000000001")); + + private static final int SecP224R1_DEFAULT_COORDS = COORD_JACOBIAN; + + protected SecP224R1Point infinity; + + public SecP224R1Curve() + { + super(q); + + this.infinity = new SecP224R1Point(this, null, null); + + this.a = fromBigInteger(new BigInteger(1, + Hex.decode("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFE"))); + this.b = fromBigInteger(new BigInteger(1, + Hex.decode("B4050A850C04B3ABF54132565044B0B7D7BFD8BA270B39432355FFB4"))); + this.order = new BigInteger(1, Hex.decode("FFFFFFFFFFFFFFFFFFFFFFFFFFFF16A2E0B8F03E13DD29455C5C2A3D")); + this.cofactor = BigInteger.valueOf(1); + + this.coord = SecP224R1_DEFAULT_COORDS; + } + + protected ECCurve cloneCurve() + { + return new SecP224R1Curve(); + } + + public boolean supportsCoordinateSystem(int coord) + { + switch (coord) + { + case COORD_JACOBIAN: + return true; + default: + return false; + } + } + + public BigInteger getQ() + { + return q; + } + + public int getFieldSize() + { + return q.bitLength(); + } + + public ECFieldElement fromBigInteger(BigInteger x) + { + return new SecP224R1FieldElement(x); + } + + protected ECPoint createRawPoint(ECFieldElement x, ECFieldElement y, boolean withCompression) + { + return new SecP224R1Point(this, x, y, withCompression); + } + + protected ECPoint createRawPoint(ECFieldElement x, ECFieldElement y, ECFieldElement[] zs, boolean withCompression) + { + return new SecP224R1Point(this, x, y, zs, withCompression); + } + + public ECPoint getInfinity() + { + return infinity; + } +} diff --git a/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP224R1Field.java b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP224R1Field.java new file mode 100644 index 00000000..1722e158 --- /dev/null +++ b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP224R1Field.java @@ -0,0 +1,298 @@ +package org.spongycastle.math.ec.custom.sec; + +import java.math.BigInteger; + +import org.spongycastle.math.raw.Nat; +import org.spongycastle.math.raw.Nat224; + +public class SecP224R1Field +{ + private static final long M = 0xFFFFFFFFL; + + // 2^224 - 2^96 + 1 + static final int[] P = new int[]{ 0x00000001, 0x00000000, 0x00000000, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF }; + static final int[] PExt = new int[]{ 0x00000001, 0x00000000, 0x00000000, 0xFFFFFFFE, 0xFFFFFFFF, + 0xFFFFFFFF, 0x00000000, 0x00000002, 0x00000000, 0x00000000, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF }; + private static final int[] PExtInv = new int[]{ 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000001, 0x00000000, + 0x00000000, 0xFFFFFFFF, 0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000001 }; + private static final int P6 = 0xFFFFFFFF; + private static final int PExt13 = 0xFFFFFFFF; + + public static void add(int[] x, int[] y, int[] z) + { + int c = Nat224.add(x, y, z); + if (c != 0 || (z[6] == P6 && Nat224.gte(z, P))) + { + addPInvTo(z); + } + } + + public static void addExt(int[] xx, int[] yy, int[] zz) + { + int c = Nat.add(14, xx, yy, zz); + if (c != 0 || (zz[13] == PExt13 && Nat.gte(14, zz, PExt))) + { + if (Nat.addTo(PExtInv.length, PExtInv, zz) != 0) + { + Nat.incAt(14, zz, PExtInv.length); + } + } + } + + public static void addOne(int[] x, int[] z) + { + int c = Nat.inc(7, x, z); + if (c != 0 || (z[6] == P6 && Nat224.gte(z, P))) + { + addPInvTo(z); + } + } + + public static int[] fromBigInteger(BigInteger x) + { + int[] z = Nat224.fromBigInteger(x); + if (z[6] == P6 && Nat224.gte(z, P)) + { + Nat224.subFrom(P, z); + } + return z; + } + + public static void half(int[] x, int[] z) + { + if ((x[0] & 1) == 0) + { + Nat.shiftDownBit(7, x, 0, z); + } + else + { + int c = Nat224.add(x, P, z); + Nat.shiftDownBit(7, z, c); + } + } + + public static void multiply(int[] x, int[] y, int[] z) + { + int[] tt = Nat224.createExt(); + Nat224.mul(x, y, tt); + reduce(tt, z); + } + + public static void multiplyAddToExt(int[] x, int[] y, int[] zz) + { + int c = Nat224.mulAddTo(x, y, zz); + if (c != 0 || (zz[13] == PExt13 && Nat.gte(14, zz, PExt))) + { + if (Nat.addTo(PExtInv.length, PExtInv, zz) != 0) + { + Nat.incAt(14, zz, PExtInv.length); + } + } + } + + public static void negate(int[] x, int[] z) + { + if (Nat224.isZero(x)) + { + Nat224.zero(z); + } + else + { + Nat224.sub(P, x, z); + } + } + + public static void reduce(int[] xx, int[] z) + { + long xx10 = xx[10] & M, xx11 = xx[11] & M, xx12 = xx[12] & M, xx13 = xx[13] & M; + + final long n = 1; + + long t0 = (xx[7] & M) + xx11 - n; + long t1 = (xx[8] & M) + xx12; + long t2 = (xx[9] & M) + xx13; + + long cc = 0; + cc += (xx[0] & M) - t0; + long z0 = cc & M; + cc >>= 32; + cc += (xx[1] & M) - t1; + z[1] = (int)cc; + cc >>= 32; + cc += (xx[2] & M) - t2; + z[2] = (int)cc; + cc >>= 32; + cc += (xx[3] & M) + t0 - xx10; + long z3 = cc & M; + cc >>= 32; + cc += (xx[4] & M) + t1 - xx11; + z[4] = (int)cc; + cc >>= 32; + cc += (xx[5] & M) + t2 - xx12; + z[5] = (int)cc; + cc >>= 32; + cc += (xx[6] & M) + xx10 - xx13; + z[6] = (int)cc; + cc >>= 32; + cc += n; + +// assert cc >= 0; + + z3 += cc; + + z0 -= cc; + z[0] = (int)z0; + cc = z0 >> 32; + if (cc != 0) + { + cc += (z[1] & M); + z[1] = (int)cc; + cc >>= 32; + cc += (z[2] & M); + z[2] = (int)cc; + z3 += cc >> 32; + } + z[3] = (int)z3; + cc = z3 >> 32; + +// assert cc == 0 || cc == 1; + + if ((cc != 0 && Nat.incAt(7, z, 4) != 0) + || (z[6] == P6 && Nat224.gte(z, P))) + { + addPInvTo(z); + } + } + + public static void reduce32(int x, int[] z) + { + long cc = 0; + + if (x != 0) + { + long xx07 = x & M; + + cc += (z[0] & M) - xx07; + z[0] = (int)cc; + cc >>= 32; + if (cc != 0) + { + cc += (z[1] & M); + z[1] = (int)cc; + cc >>= 32; + cc += (z[2] & M); + z[2] = (int)cc; + cc >>= 32; + } + cc += (z[3] & M) + xx07; + z[3] = (int)cc; + cc >>= 32; + +// assert cc == 0 || cc == 1; + } + + if ((cc != 0 && Nat.incAt(7, z, 4) != 0) + || (z[6] == P6 && Nat224.gte(z, P))) + { + addPInvTo(z); + } + } + + public static void square(int[] x, int[] z) + { + int[] tt = Nat224.createExt(); + Nat224.square(x, tt); + reduce(tt, z); + } + + public static void squareN(int[] x, int n, int[] z) + { +// assert n > 0; + + int[] tt = Nat224.createExt(); + Nat224.square(x, tt); + reduce(tt, z); + + while (--n > 0) + { + Nat224.square(z, tt); + reduce(tt, z); + } + } + + public static void subtract(int[] x, int[] y, int[] z) + { + int c = Nat224.sub(x, y, z); + if (c != 0) + { + subPInvFrom(z); + } + } + + public static void subtractExt(int[] xx, int[] yy, int[] zz) + { + int c = Nat.sub(14, xx, yy, zz); + if (c != 0) + { + if (Nat.subFrom(PExtInv.length, PExtInv, zz) != 0) + { + Nat.decAt(14, zz, PExtInv.length); + } + } + } + + public static void twice(int[] x, int[] z) + { + int c = Nat.shiftUpBit(7, x, 0, z); + if (c != 0 || (z[6] == P6 && Nat224.gte(z, P))) + { + addPInvTo(z); + } + } + + private static void addPInvTo(int[] z) + { + long c = (z[0] & M) - 1; + z[0] = (int)c; + c >>= 32; + if (c != 0) + { + c += (z[1] & M); + z[1] = (int)c; + c >>= 32; + c += (z[2] & M); + z[2] = (int)c; + c >>= 32; + } + c += (z[3] & M) + 1; + z[3] = (int)c; + c >>= 32; + if (c != 0) + { + Nat.incAt(7, z, 4); + } + } + + private static void subPInvFrom(int[] z) + { + long c = (z[0] & M) + 1; + z[0] = (int)c; + c >>= 32; + if (c != 0) + { + c += (z[1] & M); + z[1] = (int)c; + c >>= 32; + c += (z[2] & M); + z[2] = (int)c; + c >>= 32; + } + c += (z[3] & M) - 1; + z[3] = (int)c; + c >>= 32; + if (c != 0) + { + Nat.decAt(7, z, 4); + } + } +} diff --git a/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP224R1FieldElement.java b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP224R1FieldElement.java new file mode 100644 index 00000000..3a82fcab --- /dev/null +++ b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP224R1FieldElement.java @@ -0,0 +1,273 @@ +package org.spongycastle.math.ec.custom.sec; + +import java.math.BigInteger; + +import org.spongycastle.math.ec.ECFieldElement; +import org.spongycastle.math.raw.Mod; +import org.spongycastle.math.raw.Nat; +import org.spongycastle.math.raw.Nat224; +import org.spongycastle.util.Arrays; + +public class SecP224R1FieldElement extends ECFieldElement +{ + public static final BigInteger Q = SecP224R1Curve.q; + + protected int[] x; + + public SecP224R1FieldElement(BigInteger x) + { + if (x == null || x.signum() < 0 || x.compareTo(Q) >= 0) + { + throw new IllegalArgumentException("x value invalid for SecP224R1FieldElement"); + } + + this.x = SecP224R1Field.fromBigInteger(x); + } + + public SecP224R1FieldElement() + { + this.x = Nat224.create(); + } + + protected SecP224R1FieldElement(int[] x) + { + this.x = x; + } + + public boolean isZero() + { + return Nat224.isZero(x); + } + + public boolean isOne() + { + return Nat224.isOne(x); + } + + public boolean testBitZero() + { + return Nat224.getBit(x, 0) == 1; + } + + public BigInteger toBigInteger() + { + return Nat224.toBigInteger(x); + } + + public String getFieldName() + { + return "SecP224R1Field"; + } + + public int getFieldSize() + { + return Q.bitLength(); + } + + public ECFieldElement add(ECFieldElement b) + { + int[] z = Nat224.create(); + SecP224R1Field.add(x, ((SecP224R1FieldElement)b).x, z); + return new SecP224R1FieldElement(z); + } + + public ECFieldElement addOne() + { + int[] z = Nat224.create(); + SecP224R1Field.addOne(x, z); + return new SecP224R1FieldElement(z); + } + + public ECFieldElement subtract(ECFieldElement b) + { + int[] z = Nat224.create(); + SecP224R1Field.subtract(x, ((SecP224R1FieldElement)b).x, z); + return new SecP224R1FieldElement(z); + } + + public ECFieldElement multiply(ECFieldElement b) + { + int[] z = Nat224.create(); + SecP224R1Field.multiply(x, ((SecP224R1FieldElement)b).x, z); + return new SecP224R1FieldElement(z); + } + + public ECFieldElement divide(ECFieldElement b) + { +// return multiply(b.invert()); + int[] z = Nat224.create(); + Mod.invert(SecP224R1Field.P, ((SecP224R1FieldElement)b).x, z); + SecP224R1Field.multiply(z, x, z); + return new SecP224R1FieldElement(z); + } + + public ECFieldElement negate() + { + int[] z = Nat224.create(); + SecP224R1Field.negate(x, z); + return new SecP224R1FieldElement(z); + } + + public ECFieldElement square() + { + int[] z = Nat224.create(); + SecP224R1Field.square(x, z); + return new SecP224R1FieldElement(z); + } + + public ECFieldElement invert() + { +// return new SecP224R1FieldElement(toBigInteger().modInverse(Q)); + int[] z = Nat224.create(); + Mod.invert(SecP224R1Field.P, x, z); + return new SecP224R1FieldElement(z); + } + + /** + * return a sqrt root - the routine verifies that the calculation returns the right value - if + * none exists it returns null. + */ + public ECFieldElement sqrt() + { + int[] c = this.x; + if (Nat224.isZero(c) || Nat224.isOne(c)) + { + return this; + } + + int[] nc = Nat224.create(); + SecP224R1Field.negate(c, nc); + + int[] r = Mod.random(SecP224R1Field.P); + int[] t = Nat224.create(); + + if (!isSquare(c)) + { + return null; + } + + while (!trySqrt(nc, r, t)) + { + SecP224R1Field.addOne(r, r); + } + + SecP224R1Field.square(t, r); + + return Nat224.eq(c, r) ? new SecP224R1FieldElement(t) : null; + } + + public boolean equals(Object other) + { + if (other == this) + { + return true; + } + + if (!(other instanceof SecP224R1FieldElement)) + { + return false; + } + + SecP224R1FieldElement o = (SecP224R1FieldElement)other; + return Nat224.eq(x, o.x); + } + + public int hashCode() + { + return Q.hashCode() ^ Arrays.hashCode(x, 0, 7); + } + + private static boolean isSquare(int[] x) + { + int[] t1 = Nat224.create(); + int[] t2 = Nat224.create(); + Nat224.copy(x, t1); + + for (int i = 0; i < 7; ++i) + { + Nat224.copy(t1, t2); + SecP224R1Field.squareN(t1, 1 << i, t1); + SecP224R1Field.multiply(t1, t2, t1); + } + + SecP224R1Field.squareN(t1, 95, t1); + return Nat224.isOne(t1); + } + + private static void RM(int[] nc, int[] d0, int[] e0, int[] d1, int[] e1, int[] f1, int[] t) + { + SecP224R1Field.multiply(e1, e0, t); + SecP224R1Field.multiply(t, nc, t); + SecP224R1Field.multiply(d1, d0, f1); + SecP224R1Field.add(f1, t, f1); + SecP224R1Field.multiply(d1, e0, t); + Nat224.copy(f1, d1); + SecP224R1Field.multiply(e1, d0, e1); + SecP224R1Field.add(e1, t, e1); + SecP224R1Field.square(e1, f1); + SecP224R1Field.multiply(f1, nc, f1); + } + + private static void RP(int[] nc, int[] d1, int[] e1, int[] f1, int[] t) + { + Nat224.copy(nc, f1); + + int[] d0 = Nat224.create(); + int[] e0 = Nat224.create(); + + for (int i = 0; i < 7; ++i) + { + Nat224.copy(d1, d0); + Nat224.copy(e1, e0); + + int j = 1 << i; + while (--j >= 0) + { + RS(d1, e1, f1, t); + } + + RM(nc, d0, e0, d1, e1, f1, t); + } + } + + private static void RS(int[] d, int[] e, int[] f, int[] t) + { + SecP224R1Field.multiply(e, d, e); + SecP224R1Field.twice(e, e); + SecP224R1Field.square(d, t); + SecP224R1Field.add(f, t, d); + SecP224R1Field.multiply(f, t, f); + int c = Nat.shiftUpBits(7, f, 2, 0); + SecP224R1Field.reduce32(c, f); + } + + private static boolean trySqrt(int[] nc, int[] r, int[] t) + { + int[] d1 = Nat224.create(); + Nat224.copy(r, d1); + int[] e1 = Nat224.create(); + e1[0] = 1; + int[] f1 = Nat224.create(); + RP(nc, d1, e1, f1, t); + + int[] d0 = Nat224.create(); + int[] e0 = Nat224.create(); + + for (int k = 1; k < 96; ++k) + { + Nat224.copy(d1, d0); + Nat224.copy(e1, e0); + + RS(d1, e1, f1, t); + + if (Nat224.isZero(d1)) + { + Mod.invert(SecP224R1Field.P, e0, t); + SecP224R1Field.multiply(t, d0, t); + return true; + } + } + + return false; + } +} diff --git a/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP224R1Point.java b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP224R1Point.java new file mode 100644 index 00000000..d44f2f8f --- /dev/null +++ b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP224R1Point.java @@ -0,0 +1,308 @@ +package org.spongycastle.math.ec.custom.sec; + +import org.spongycastle.math.ec.ECCurve; +import org.spongycastle.math.ec.ECFieldElement; +import org.spongycastle.math.ec.ECPoint; +import org.spongycastle.math.raw.Nat; +import org.spongycastle.math.raw.Nat224; + +public class SecP224R1Point extends ECPoint.AbstractFp +{ + /** + * Create a point which encodes with 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 SecP224R1Point(ECCurve curve, ECFieldElement x, ECFieldElement y) + { + this(curve, x, y, false); + } + + /** + * Create a point that encodes with or without point compresion. + * + * @param curve + * the curve to use + * @param x + * affine x co-ordinate + * @param y + * affine y co-ordinate + * @param withCompression + * if true encode with point compression + * + * @deprecated per-point compression property will be removed, refer + * {@link #getEncoded(boolean)} + */ + public SecP224R1Point(ECCurve curve, ECFieldElement x, ECFieldElement y, boolean withCompression) + { + super(curve, x, y); + + if ((x == null) != (y == null)) + { + throw new IllegalArgumentException("Exactly one of the field elements is null"); + } + + this.withCompression = withCompression; + } + + SecP224R1Point(ECCurve curve, ECFieldElement x, ECFieldElement y, ECFieldElement[] zs, boolean withCompression) + { + super(curve, x, y, zs); + + this.withCompression = withCompression; + } + + protected ECPoint detach() + { + return new SecP224R1Point(null, getAffineXCoord(), getAffineYCoord()); + } + + public ECPoint add(ECPoint b) + { + if (this.isInfinity()) + { + return b; + } + if (b.isInfinity()) + { + return this; + } + if (this == b) + { + return twice(); + } + + ECCurve curve = this.getCurve(); + + SecP224R1FieldElement X1 = (SecP224R1FieldElement)this.x, Y1 = (SecP224R1FieldElement)this.y; + SecP224R1FieldElement X2 = (SecP224R1FieldElement)b.getXCoord(), Y2 = (SecP224R1FieldElement)b.getYCoord(); + + SecP224R1FieldElement Z1 = (SecP224R1FieldElement)this.zs[0]; + SecP224R1FieldElement Z2 = (SecP224R1FieldElement)b.getZCoord(0); + + int c; + int[] tt1 = Nat224.createExt(); + int[] t2 = Nat224.create(); + int[] t3 = Nat224.create(); + int[] t4 = Nat224.create(); + + boolean Z1IsOne = Z1.isOne(); + int[] U2, S2; + if (Z1IsOne) + { + U2 = X2.x; + S2 = Y2.x; + } + else + { + S2 = t3; + SecP224R1Field.square(Z1.x, S2); + + U2 = t2; + SecP224R1Field.multiply(S2, X2.x, U2); + + SecP224R1Field.multiply(S2, Z1.x, S2); + SecP224R1Field.multiply(S2, Y2.x, S2); + } + + boolean Z2IsOne = Z2.isOne(); + int[] U1, S1; + if (Z2IsOne) + { + U1 = X1.x; + S1 = Y1.x; + } + else + { + S1 = t4; + SecP224R1Field.square(Z2.x, S1); + + U1 = tt1; + SecP224R1Field.multiply(S1, X1.x, U1); + + SecP224R1Field.multiply(S1, Z2.x, S1); + SecP224R1Field.multiply(S1, Y1.x, S1); + } + + int[] H = Nat224.create(); + SecP224R1Field.subtract(U1, U2, H); + + int[] R = t2; + SecP224R1Field.subtract(S1, S2, R); + + // Check if b == this or b == -this + if (Nat224.isZero(H)) + { + if (Nat224.isZero(R)) + { + // this == b, i.e. this must be doubled + return this.twice(); + } + + // this == -b, i.e. the result is the point at infinity + return curve.getInfinity(); + } + + int[] HSquared = t3; + SecP224R1Field.square(H, HSquared); + + int[] G = Nat224.create(); + SecP224R1Field.multiply(HSquared, H, G); + + int[] V = t3; + SecP224R1Field.multiply(HSquared, U1, V); + + SecP224R1Field.negate(G, G); + Nat224.mul(S1, G, tt1); + + c = Nat224.addBothTo(V, V, G); + SecP224R1Field.reduce32(c, G); + + SecP224R1FieldElement X3 = new SecP224R1FieldElement(t4); + SecP224R1Field.square(R, X3.x); + SecP224R1Field.subtract(X3.x, G, X3.x); + + SecP224R1FieldElement Y3 = new SecP224R1FieldElement(G); + SecP224R1Field.subtract(V, X3.x, Y3.x); + SecP224R1Field.multiplyAddToExt(Y3.x, R, tt1); + SecP224R1Field.reduce(tt1, Y3.x); + + SecP224R1FieldElement Z3 = new SecP224R1FieldElement(H); + if (!Z1IsOne) + { + SecP224R1Field.multiply(Z3.x, Z1.x, Z3.x); + } + if (!Z2IsOne) + { + SecP224R1Field.multiply(Z3.x, Z2.x, Z3.x); + } + + ECFieldElement[] zs = new ECFieldElement[]{ Z3 }; + + return new SecP224R1Point(curve, X3, Y3, zs, this.withCompression); + } + + public ECPoint twice() + { + if (this.isInfinity()) + { + return this; + } + + ECCurve curve = this.getCurve(); + + SecP224R1FieldElement Y1 = (SecP224R1FieldElement)this.y; + if (Y1.isZero()) + { + return curve.getInfinity(); + } + + SecP224R1FieldElement X1 = (SecP224R1FieldElement)this.x, Z1 = (SecP224R1FieldElement)this.zs[0]; + + int c; + int[] t1 = Nat224.create(); + int[] t2 = Nat224.create(); + + int[] Y1Squared = Nat224.create(); + SecP224R1Field.square(Y1.x, Y1Squared); + + int[] T = Nat224.create(); + SecP224R1Field.square(Y1Squared, T); + + boolean Z1IsOne = Z1.isOne(); + + int[] Z1Squared = Z1.x; + if (!Z1IsOne) + { + Z1Squared = t2; + SecP224R1Field.square(Z1.x, Z1Squared); + } + + SecP224R1Field.subtract(X1.x, Z1Squared, t1); + + int[] M = t2; + SecP224R1Field.add(X1.x, Z1Squared, M); + SecP224R1Field.multiply(M, t1, M); + c = Nat224.addBothTo(M, M, M); + SecP224R1Field.reduce32(c, M); + + int[] S = Y1Squared; + SecP224R1Field.multiply(Y1Squared, X1.x, S); + c = Nat.shiftUpBits(7, S, 2, 0); + SecP224R1Field.reduce32(c, S); + + c = Nat.shiftUpBits(7, T, 3, 0, t1); + SecP224R1Field.reduce32(c, t1); + + SecP224R1FieldElement X3 = new SecP224R1FieldElement(T); + SecP224R1Field.square(M, X3.x); + SecP224R1Field.subtract(X3.x, S, X3.x); + SecP224R1Field.subtract(X3.x, S, X3.x); + + SecP224R1FieldElement Y3 = new SecP224R1FieldElement(S); + SecP224R1Field.subtract(S, X3.x, Y3.x); + SecP224R1Field.multiply(Y3.x, M, Y3.x); + SecP224R1Field.subtract(Y3.x, t1, Y3.x); + + SecP224R1FieldElement Z3 = new SecP224R1FieldElement(M); + SecP224R1Field.twice(Y1.x, Z3.x); + if (!Z1IsOne) + { + SecP224R1Field.multiply(Z3.x, Z1.x, Z3.x); + } + + return new SecP224R1Point(curve, X3, Y3, new ECFieldElement[]{ Z3 }, this.withCompression); + } + + public ECPoint twicePlus(ECPoint b) + { + if (this == b) + { + return threeTimes(); + } + if (this.isInfinity()) + { + return b; + } + if (b.isInfinity()) + { + return twice(); + } + + ECFieldElement Y1 = this.y; + if (Y1.isZero()) + { + return b; + } + + return twice().add(b); + } + + public ECPoint threeTimes() + { + if (this.isInfinity() || this.y.isZero()) + { + return this; + } + + // NOTE: Be careful about recursions between twicePlus and threeTimes + return twice().add(this); + } + + public ECPoint negate() + { + if (this.isInfinity()) + { + return this; + } + + return new SecP224R1Point(curve, this.x, this.y.negate(), this.zs, this.withCompression); + } +} diff --git a/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP256K1Curve.java b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP256K1Curve.java new file mode 100644 index 00000000..85d31cc1 --- /dev/null +++ b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP256K1Curve.java @@ -0,0 +1,78 @@ +package org.spongycastle.math.ec.custom.sec; + +import java.math.BigInteger; + +import org.spongycastle.math.ec.ECConstants; +import org.spongycastle.math.ec.ECCurve; +import org.spongycastle.math.ec.ECFieldElement; +import org.spongycastle.math.ec.ECPoint; +import org.spongycastle.util.encoders.Hex; + +public class SecP256K1Curve extends ECCurve.AbstractFp +{ + public static final BigInteger q = new BigInteger(1, + Hex.decode("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F")); + + private static final int SECP256K1_DEFAULT_COORDS = COORD_JACOBIAN; + + protected SecP256K1Point infinity; + + public SecP256K1Curve() + { + super(q); + + this.infinity = new SecP256K1Point(this, null, null); + + this.a = fromBigInteger(ECConstants.ZERO); + this.b = fromBigInteger(BigInteger.valueOf(7)); + this.order = new BigInteger(1, Hex.decode("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141")); + this.cofactor = BigInteger.valueOf(1); + this.coord = SECP256K1_DEFAULT_COORDS; + } + + protected ECCurve cloneCurve() + { + return new SecP256K1Curve(); + } + + public boolean supportsCoordinateSystem(int coord) + { + switch (coord) + { + case COORD_JACOBIAN: + return true; + default: + return false; + } + } + + public BigInteger getQ() + { + return q; + } + + public int getFieldSize() + { + return q.bitLength(); + } + + public ECFieldElement fromBigInteger(BigInteger x) + { + return new SecP256K1FieldElement(x); + } + + protected ECPoint createRawPoint(ECFieldElement x, ECFieldElement y, boolean withCompression) + { + return new SecP256K1Point(this, x, y, withCompression); + } + + protected ECPoint createRawPoint(ECFieldElement x, ECFieldElement y, ECFieldElement[] zs, boolean withCompression) + { + return new SecP256K1Point(this, x, y, zs, withCompression); + } + + public ECPoint getInfinity() + { + return infinity; + } +} diff --git a/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP256K1Field.java b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP256K1Field.java new file mode 100644 index 00000000..3aae2f2f --- /dev/null +++ b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP256K1Field.java @@ -0,0 +1,179 @@ +package org.spongycastle.math.ec.custom.sec; + +import java.math.BigInteger; + +import org.spongycastle.math.raw.Nat; +import org.spongycastle.math.raw.Nat256; + +public class SecP256K1Field +{ + // 2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1 + static final int[] P = new int[]{ 0xFFFFFC2F, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, + 0xFFFFFFFF, 0xFFFFFFFF }; + static final int[] PExt = new int[]{ 0x000E90A1, 0x000007A2, 0x00000001, 0x00000000, 0x00000000, + 0x00000000, 0x00000000, 0x00000000, 0xFFFFF85E, 0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, + 0xFFFFFFFF, 0xFFFFFFFF }; + private static final int[] PExtInv = new int[]{ 0xFFF16F5F, 0xFFFFF85D, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, + 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0x000007A1, 0x00000002 }; + private static final int P7 = 0xFFFFFFFF; + private static final int PExt15 = 0xFFFFFFFF; + private static final int PInv33 = 0x3D1; + + public static void add(int[] x, int[] y, int[] z) + { + int c = Nat256.add(x, y, z); + if (c != 0 || (z[7] == P7 && Nat256.gte(z, P))) + { + Nat.add33To(8, PInv33, z); + } + } + + 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 (Nat.addTo(PExtInv.length, PExtInv, zz) != 0) + { + Nat.incAt(16, zz, PExtInv.length); + } + } + } + + public static void addOne(int[] x, int[] z) + { + int c = Nat.inc(8, x, z); + if (c != 0 || (z[7] == P7 && Nat256.gte(z, P))) + { + Nat.add33To(8, PInv33, z); + } + } + + public static int[] fromBigInteger(BigInteger x) + { + int[] z = Nat256.fromBigInteger(x); + if (z[7] == P7 && Nat256.gte(z, P)) + { + Nat256.subFrom(P, z); + } + return z; + } + + public static void half(int[] x, int[] z) + { + if ((x[0] & 1) == 0) + { + Nat.shiftDownBit(8, x, 0, z); + } + else + { + int c = Nat256.add(x, P, z); + Nat.shiftDownBit(8, z, c); + } + } + + public static void multiply(int[] x, int[] y, int[] z) + { + int[] tt = Nat256.createExt(); + Nat256.mul(x, y, tt); + reduce(tt, z); + } + + 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 (Nat.addTo(PExtInv.length, PExtInv, zz) != 0) + { + Nat.incAt(16, zz, PExtInv.length); + } + } + } + + public static void negate(int[] x, int[] z) + { + if (Nat256.isZero(x)) + { + Nat256.zero(z); + } + else + { + Nat256.sub(P, x, z); + } + } + + public static void reduce(int[] xx, int[] z) + { + long cc = Nat256.mul33Add(PInv33, xx, 8, xx, 0, z, 0); + int c = Nat256.mul33DWordAdd(PInv33, cc, z, 0); + + // assert c == 0L || c == 1L; + + if (c != 0 || (z[7] == P7 && Nat256.gte(z, P))) + { + Nat.add33To(8, PInv33, z); + } + } + + public static void reduce32(int x, int[] z) + { + if ((x != 0 && Nat256.mul33WordAdd(PInv33, x, z, 0) != 0) + || (z[7] == P7 && Nat256.gte(z, P))) + { + Nat.add33To(8, PInv33, z); + } + } + + public static void square(int[] x, int[] z) + { + int[] tt = Nat256.createExt(); + Nat256.square(x, tt); + reduce(tt, z); + } + + public static void squareN(int[] x, int n, int[] z) + { +// assert n > 0; + + int[] tt = Nat256.createExt(); + Nat256.square(x, tt); + reduce(tt, z); + + while (--n > 0) + { + Nat256.square(z, tt); + reduce(tt, z); + } + } + + public static void subtract(int[] x, int[] y, int[] z) + { + int c = Nat256.sub(x, y, z); + if (c != 0) + { + Nat.sub33From(8, PInv33, z); + } + } + + public static void subtractExt(int[] xx, int[] yy, int[] zz) + { + int c = Nat.sub(16, xx, yy, zz); + if (c != 0) + { + if (Nat.subFrom(PExtInv.length, PExtInv, zz) != 0) + { + Nat.decAt(16, zz, PExtInv.length); + } + } + } + + public static void twice(int[] x, int[] z) + { + int c = Nat.shiftUpBit(8, x, 0, z); + if (c != 0 || (z[7] == P7 && Nat256.gte(z, P))) + { + Nat.add33To(8, PInv33, z); + } + } +} diff --git a/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP256K1FieldElement.java b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP256K1FieldElement.java new file mode 100644 index 00000000..10d8a265 --- /dev/null +++ b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP256K1FieldElement.java @@ -0,0 +1,215 @@ +package org.spongycastle.math.ec.custom.sec; + +import java.math.BigInteger; + +import org.spongycastle.math.ec.ECFieldElement; +import org.spongycastle.math.raw.Mod; +import org.spongycastle.math.raw.Nat256; +import org.spongycastle.util.Arrays; + +public class SecP256K1FieldElement extends ECFieldElement +{ + public static final BigInteger Q = SecP256K1Curve.q; + + protected int[] x; + + public SecP256K1FieldElement(BigInteger x) + { + if (x == null || x.signum() < 0 || x.compareTo(Q) >= 0) + { + throw new IllegalArgumentException("x value invalid for SecP256K1FieldElement"); + } + + this.x = SecP256K1Field.fromBigInteger(x); + } + + public SecP256K1FieldElement() + { + this.x = Nat256.create(); + } + + protected SecP256K1FieldElement(int[] x) + { + this.x = x; + } + + public boolean isZero() + { + return Nat256.isZero(x); + } + + public boolean isOne() + { + return Nat256.isOne(x); + } + + public boolean testBitZero() + { + return Nat256.getBit(x, 0) == 1; + } + + public BigInteger toBigInteger() + { + return Nat256.toBigInteger(x); + } + + public String getFieldName() + { + return "SecP256K1Field"; + } + + public int getFieldSize() + { + return Q.bitLength(); + } + + public ECFieldElement add(ECFieldElement b) + { + int[] z = Nat256.create(); + SecP256K1Field.add(x, ((SecP256K1FieldElement)b).x, z); + return new SecP256K1FieldElement(z); + } + + public ECFieldElement addOne() + { + int[] z = Nat256.create(); + SecP256K1Field.addOne(x, z); + return new SecP256K1FieldElement(z); + } + + public ECFieldElement subtract(ECFieldElement b) + { + int[] z = Nat256.create(); + SecP256K1Field.subtract(x, ((SecP256K1FieldElement)b).x, z); + return new SecP256K1FieldElement(z); + } + + public ECFieldElement multiply(ECFieldElement b) + { + int[] z = Nat256.create(); + SecP256K1Field.multiply(x, ((SecP256K1FieldElement)b).x, z); + return new SecP256K1FieldElement(z); + } + + public ECFieldElement divide(ECFieldElement b) + { +// return multiply(b.invert()); + int[] z = Nat256.create(); + Mod.invert(SecP256K1Field.P, ((SecP256K1FieldElement)b).x, z); + SecP256K1Field.multiply(z, x, z); + return new SecP256K1FieldElement(z); + } + + public ECFieldElement negate() + { + int[] z = Nat256.create(); + SecP256K1Field.negate(x, z); + return new SecP256K1FieldElement(z); + } + + public ECFieldElement square() + { + int[] z = Nat256.create(); + SecP256K1Field.square(x, z); + return new SecP256K1FieldElement(z); + } + + public ECFieldElement invert() + { +// return new SecP256K1FieldElement(toBigInteger().modInverse(Q)); + int[] z = Nat256.create(); + Mod.invert(SecP256K1Field.P, x, z); + return new SecP256K1FieldElement(z); + } + + // D.1.4 91 + /** + * return a sqrt root - the routine verifies that the calculation returns the right value - if + * none exists it returns null. + */ + public ECFieldElement sqrt() + { + /* + * Raise this element to the exponent 2^254 - 2^30 - 2^7 - 2^6 - 2^5 - 2^4 - 2^2 + * + * Breaking up the exponent's binary representation into "repunits", we get: + * { 223 1s } { 1 0s } { 22 1s } { 4 0s } { 2 1s } { 2 0s} + * + * Therefore we need an addition chain containing 2, 22, 223 (the lengths of the repunits) + * We use: 1, [2], 3, 6, 9, 11, [22], 44, 88, 176, 220, [223] + */ + + int[] x1 = this.x; + if (Nat256.isZero(x1) || Nat256.isOne(x1)) + { + return this; + } + + int[] x2 = Nat256.create(); + SecP256K1Field.square(x1, x2); + SecP256K1Field.multiply(x2, x1, x2); + int[] x3 = Nat256.create(); + SecP256K1Field.square(x2, x3); + SecP256K1Field.multiply(x3, x1, x3); + int[] x6 = Nat256.create(); + SecP256K1Field.squareN(x3, 3, x6); + SecP256K1Field.multiply(x6, x3, x6); + int[] x9 = x6; + SecP256K1Field.squareN(x6, 3, x9); + SecP256K1Field.multiply(x9, x3, x9); + int[] x11 = x9; + SecP256K1Field.squareN(x9, 2, x11); + SecP256K1Field.multiply(x11, x2, x11); + int[] x22 = Nat256.create(); + SecP256K1Field.squareN(x11, 11, x22); + SecP256K1Field.multiply(x22, x11, x22); + int[] x44 = x11; + SecP256K1Field.squareN(x22, 22, x44); + SecP256K1Field.multiply(x44, x22, x44); + int[] x88 = Nat256.create(); + SecP256K1Field.squareN(x44, 44, x88); + SecP256K1Field.multiply(x88, x44, x88); + int[] x176 = Nat256.create(); + SecP256K1Field.squareN(x88, 88, x176); + SecP256K1Field.multiply(x176, x88, x176); + int[] x220 = x88; + SecP256K1Field.squareN(x176, 44, x220); + SecP256K1Field.multiply(x220, x44, x220); + int[] x223 = x44; + SecP256K1Field.squareN(x220, 3, x223); + SecP256K1Field.multiply(x223, x3, x223); + + int[] t1 = x223; + SecP256K1Field.squareN(t1, 23, t1); + SecP256K1Field.multiply(t1, x22, t1); + SecP256K1Field.squareN(t1, 6, t1); + SecP256K1Field.multiply(t1, x2, t1); + SecP256K1Field.squareN(t1, 2, t1); + + int[] t2 = x2; + SecP256K1Field.square(t1, t2); + + return Nat256.eq(x1, t2) ? new SecP256K1FieldElement(t1) : null; + } + + public boolean equals(Object other) + { + if (other == this) + { + return true; + } + + if (!(other instanceof SecP256K1FieldElement)) + { + return false; + } + + SecP256K1FieldElement o = (SecP256K1FieldElement)other; + return Nat256.eq(x, o.x); + } + + public int hashCode() + { + return Q.hashCode() ^ Arrays.hashCode(x, 0, 8); + } +} diff --git a/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP256K1Point.java b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP256K1Point.java new file mode 100644 index 00000000..fa939431 --- /dev/null +++ b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP256K1Point.java @@ -0,0 +1,298 @@ +package org.spongycastle.math.ec.custom.sec; + +import org.spongycastle.math.ec.ECCurve; +import org.spongycastle.math.ec.ECFieldElement; +import org.spongycastle.math.ec.ECPoint; +import org.spongycastle.math.raw.Nat; +import org.spongycastle.math.raw.Nat256; + +public class SecP256K1Point extends ECPoint.AbstractFp +{ + /** + * Create a point which encodes with 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 SecP256K1Point(ECCurve curve, ECFieldElement x, ECFieldElement y) + { + this(curve, x, y, false); + } + + /** + * Create a point that encodes with or without point compresion. + * + * @param curve + * the curve to use + * @param x + * affine x co-ordinate + * @param y + * affine y co-ordinate + * @param withCompression + * if true encode with point compression + * + * @deprecated per-point compression property will be removed, refer + * {@link #getEncoded(boolean)} + */ + public SecP256K1Point(ECCurve curve, ECFieldElement x, ECFieldElement y, boolean withCompression) + { + super(curve, x, y); + + if ((x == null) != (y == null)) + { + throw new IllegalArgumentException("Exactly one of the field elements is null"); + } + + this.withCompression = withCompression; + } + + SecP256K1Point(ECCurve curve, ECFieldElement x, ECFieldElement y, ECFieldElement[] zs, + boolean withCompression) + { + super(curve, x, y, zs); + + this.withCompression = withCompression; + } + + protected ECPoint detach() + { + return new SecP256K1Point(null, getAffineXCoord(), getAffineYCoord()); + } + + // B.3 pg 62 + public ECPoint add(ECPoint b) + { + if (this.isInfinity()) + { + return b; + } + if (b.isInfinity()) + { + return this; + } + if (this == b) + { + return twice(); + } + + ECCurve curve = this.getCurve(); + + SecP256K1FieldElement X1 = (SecP256K1FieldElement)this.x, Y1 = (SecP256K1FieldElement)this.y; + SecP256K1FieldElement X2 = (SecP256K1FieldElement)b.getXCoord(), Y2 = (SecP256K1FieldElement)b.getYCoord(); + + SecP256K1FieldElement Z1 = (SecP256K1FieldElement)this.zs[0]; + SecP256K1FieldElement Z2 = (SecP256K1FieldElement)b.getZCoord(0); + + int c; + int[] tt1 = Nat256.createExt(); + int[] t2 = Nat256.create(); + int[] t3 = Nat256.create(); + int[] t4 = Nat256.create(); + + boolean Z1IsOne = Z1.isOne(); + int[] U2, S2; + if (Z1IsOne) + { + U2 = X2.x; + S2 = Y2.x; + } + else + { + S2 = t3; + SecP256K1Field.square(Z1.x, S2); + + U2 = t2; + SecP256K1Field.multiply(S2, X2.x, U2); + + SecP256K1Field.multiply(S2, Z1.x, S2); + SecP256K1Field.multiply(S2, Y2.x, S2); + } + + boolean Z2IsOne = Z2.isOne(); + int[] U1, S1; + if (Z2IsOne) + { + U1 = X1.x; + S1 = Y1.x; + } + else + { + S1 = t4; + SecP256K1Field.square(Z2.x, S1); + + U1 = tt1; + SecP256K1Field.multiply(S1, X1.x, U1); + + SecP256K1Field.multiply(S1, Z2.x, S1); + SecP256K1Field.multiply(S1, Y1.x, S1); + } + + int[] H = Nat256.create(); + SecP256K1Field.subtract(U1, U2, H); + + int[] R = t2; + SecP256K1Field.subtract(S1, S2, R); + + // Check if b == this or b == -this + if (Nat256.isZero(H)) + { + if (Nat256.isZero(R)) + { + // this == b, i.e. this must be doubled + return this.twice(); + } + + // this == -b, i.e. the result is the point at infinity + return curve.getInfinity(); + } + + int[] HSquared = t3; + SecP256K1Field.square(H, HSquared); + + int[] G = Nat256.create(); + SecP256K1Field.multiply(HSquared, H, G); + + int[] V = t3; + SecP256K1Field.multiply(HSquared, U1, V); + + SecP256K1Field.negate(G, G); + Nat256.mul(S1, G, tt1); + + c = Nat256.addBothTo(V, V, G); + SecP256K1Field.reduce32(c, G); + + SecP256K1FieldElement X3 = new SecP256K1FieldElement(t4); + SecP256K1Field.square(R, X3.x); + SecP256K1Field.subtract(X3.x, G, X3.x); + + SecP256K1FieldElement Y3 = new SecP256K1FieldElement(G); + SecP256K1Field.subtract(V, X3.x, Y3.x); + SecP256K1Field.multiplyAddToExt(Y3.x, R, tt1); + SecP256K1Field.reduce(tt1, Y3.x); + + SecP256K1FieldElement Z3 = new SecP256K1FieldElement(H); + if (!Z1IsOne) + { + SecP256K1Field.multiply(Z3.x, Z1.x, Z3.x); + } + if (!Z2IsOne) + { + SecP256K1Field.multiply(Z3.x, Z2.x, Z3.x); + } + + ECFieldElement[] zs = new ECFieldElement[] { Z3 }; + + return new SecP256K1Point(curve, X3, Y3, zs, this.withCompression); + } + + // B.3 pg 62 + public ECPoint twice() + { + if (this.isInfinity()) + { + return this; + } + + ECCurve curve = this.getCurve(); + + SecP256K1FieldElement Y1 = (SecP256K1FieldElement)this.y; + if (Y1.isZero()) + { + return curve.getInfinity(); + } + + SecP256K1FieldElement X1 = (SecP256K1FieldElement)this.x, Z1 = (SecP256K1FieldElement)this.zs[0]; + + int c; + + int[] Y1Squared = Nat256.create(); + SecP256K1Field.square(Y1.x, Y1Squared); + + int[] T = Nat256.create(); + SecP256K1Field.square(Y1Squared, T); + + int[] M = Nat256.create(); + SecP256K1Field.square(X1.x, M); + c = Nat256.addBothTo(M, M, M); + SecP256K1Field.reduce32(c, M); + + int[] S = Y1Squared; + SecP256K1Field.multiply(Y1Squared, X1.x, S); + c = Nat.shiftUpBits(8, S, 2, 0); + SecP256K1Field.reduce32(c, S); + + int[] t1 = Nat256.create(); + c = Nat.shiftUpBits(8, T, 3, 0, t1); + SecP256K1Field.reduce32(c, t1); + + SecP256K1FieldElement X3 = new SecP256K1FieldElement(T); + SecP256K1Field.square(M, X3.x); + SecP256K1Field.subtract(X3.x, S, X3.x); + SecP256K1Field.subtract(X3.x, S, X3.x); + + SecP256K1FieldElement Y3 = new SecP256K1FieldElement(S); + SecP256K1Field.subtract(S, X3.x, Y3.x); + SecP256K1Field.multiply(Y3.x, M, Y3.x); + SecP256K1Field.subtract(Y3.x, t1, Y3.x); + + SecP256K1FieldElement Z3 = new SecP256K1FieldElement(M); + SecP256K1Field.twice(Y1.x, Z3.x); + if (!Z1.isOne()) + { + SecP256K1Field.multiply(Z3.x, Z1.x, Z3.x); + } + + return new SecP256K1Point(curve, X3, Y3, new ECFieldElement[] { Z3 }, this.withCompression); + } + + public ECPoint twicePlus(ECPoint b) + { + if (this == b) + { + return threeTimes(); + } + if (this.isInfinity()) + { + return b; + } + if (b.isInfinity()) + { + return twice(); + } + + ECFieldElement Y1 = this.y; + if (Y1.isZero()) + { + return b; + } + + return twice().add(b); + } + + public ECPoint threeTimes() + { + if (this.isInfinity() || this.y.isZero()) + { + return this; + } + + // NOTE: Be careful about recursions between twicePlus and threeTimes + return twice().add(this); + } + + public ECPoint negate() + { + if (this.isInfinity()) + { + return this; + } + + return new SecP256K1Point(curve, this.x, this.y.negate(), this.zs, this.withCompression); + } +} diff --git a/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP256R1Curve.java b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP256R1Curve.java new file mode 100644 index 00000000..f856bb34 --- /dev/null +++ b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP256R1Curve.java @@ -0,0 +1,80 @@ +package org.spongycastle.math.ec.custom.sec; + +import java.math.BigInteger; + +import org.spongycastle.math.ec.ECCurve; +import org.spongycastle.math.ec.ECFieldElement; +import org.spongycastle.math.ec.ECPoint; +import org.spongycastle.util.encoders.Hex; + +public class SecP256R1Curve extends ECCurve.AbstractFp +{ + public static final BigInteger q = new BigInteger(1, + Hex.decode("FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF")); + + private static final int SecP256R1_DEFAULT_COORDS = COORD_JACOBIAN; + + protected SecP256R1Point infinity; + + public SecP256R1Curve() + { + super(q); + + this.infinity = new SecP256R1Point(this, null, null); + + this.a = fromBigInteger(new BigInteger(1, + Hex.decode("FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC"))); + this.b = fromBigInteger(new BigInteger(1, + Hex.decode("5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B"))); + this.order = new BigInteger(1, Hex.decode("FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551")); + this.cofactor = BigInteger.valueOf(1); + + this.coord = SecP256R1_DEFAULT_COORDS; + } + + protected ECCurve cloneCurve() + { + return new SecP256R1Curve(); + } + + public boolean supportsCoordinateSystem(int coord) + { + switch (coord) + { + case COORD_JACOBIAN: + return true; + default: + return false; + } + } + + public BigInteger getQ() + { + return q; + } + + public int getFieldSize() + { + return q.bitLength(); + } + + public ECFieldElement fromBigInteger(BigInteger x) + { + return new SecP256R1FieldElement(x); + } + + protected ECPoint createRawPoint(ECFieldElement x, ECFieldElement y, boolean withCompression) + { + return new SecP256R1Point(this, x, y, withCompression); + } + + protected ECPoint createRawPoint(ECFieldElement x, ECFieldElement y, ECFieldElement[] zs, boolean withCompression) + { + return new SecP256R1Point(this, x, y, zs, withCompression); + } + + public ECPoint getInfinity() + { + return infinity; + } +} diff --git a/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP256R1Field.java b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP256R1Field.java new file mode 100644 index 00000000..78c15d17 --- /dev/null +++ b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP256R1Field.java @@ -0,0 +1,312 @@ +package org.spongycastle.math.ec.custom.sec; + +import java.math.BigInteger; + +import org.spongycastle.math.raw.Nat; +import org.spongycastle.math.raw.Nat256; + +public class SecP256R1Field +{ + private static final long M = 0xFFFFFFFFL; + + // 2^256 - 2^224 + 2^192 + 2^96 - 1 + static final int[] P = new int[]{ 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000000, 0x00000000, 0x00000000, + 0x00000001, 0xFFFFFFFF }; + static final int[] PExt = new int[]{ 0x00000001, 0x00000000, 0x00000000, 0xFFFFFFFE, 0xFFFFFFFF, + 0xFFFFFFFF, 0xFFFFFFFE, 0x00000001, 0xFFFFFFFE, 0x00000001, 0xFFFFFFFE, 0x00000001, 0x00000001, 0xFFFFFFFE, + 0x00000002, 0xFFFFFFFE }; + private static final int P7 = 0xFFFFFFFF; + private static final int PExt15 = 0xFFFFFFFF; + + public static void add(int[] x, int[] y, int[] z) + { + int c = Nat256.add(x, y, z); + if (c != 0 || (z[7] == P7 && Nat256.gte(z, P))) + { + addPInvTo(z); + } + } + + public static void addExt(int[] xx, int[] yy, int[] zz) + { + int c = Nat.add(16, xx, yy, zz); + if (c != 0 || ((zz[15] & PExt15) == PExt15 && Nat.gte(16, zz, PExt))) + { + Nat.subFrom(16, PExt, zz); + } + } + + public static void addOne(int[] x, int[] z) + { + int c = Nat.inc(8, x, z); + if (c != 0 || (z[7] == P7 && Nat256.gte(z, P))) + { + addPInvTo(z); + } + } + + public static int[] fromBigInteger(BigInteger x) + { + int[] z = Nat256.fromBigInteger(x); + if (z[7] == P7 && Nat256.gte(z, P)) + { + Nat256.subFrom(P, z); + } + return z; + } + + public static void half(int[] x, int[] z) + { + if ((x[0] & 1) == 0) + { + Nat.shiftDownBit(8, x, 0, z); + } + else + { + int c = Nat256.add(x, P, z); + Nat.shiftDownBit(8, z, c); + } + } + + public static void multiply(int[] x, int[] y, int[] z) + { + int[] tt = Nat256.createExt(); + Nat256.mul(x, y, tt); + reduce(tt, z); + } + + public static void multiplyAddToExt(int[] x, int[] y, int[] zz) + { + int c = Nat256.mulAddTo(x, y, zz); + if (c != 0 || ((zz[15] & PExt15) == PExt15 && Nat.gte(16, zz, PExt))) + { + Nat.subFrom(16, PExt, zz); + } + } + + public static void negate(int[] x, int[] z) + { + if (Nat256.isZero(x)) + { + Nat256.zero(z); + } + else + { + Nat256.sub(P, x, z); + } + } + + public static void reduce(int[] xx, int[] z) + { + long xx08 = xx[8] & M, xx09 = xx[9] & M, xx10 = xx[10] & M, xx11 = xx[11] & M; + long xx12 = xx[12] & M, xx13 = xx[13] & M, xx14 = xx[14] & M, xx15 = xx[15] & M; + + final long n = 6; + + xx08 -= n; + + long t0 = xx08 + xx09; + long t1 = xx09 + xx10; + long t2 = xx10 + xx11 - xx15; + long t3 = xx11 + xx12; + long t4 = xx12 + xx13; + long t5 = xx13 + xx14; + long t6 = xx14 + xx15; + + long cc = 0; + cc += (xx[0] & M) + t0 - t3 - t5; + z[0] = (int)cc; + cc >>= 32; + cc += (xx[1] & M) + t1 - t4 - t6; + z[1] = (int)cc; + cc >>= 32; + cc += (xx[2] & M) + t2 - t5; + z[2] = (int)cc; + cc >>= 32; + cc += (xx[3] & M) + (t3 << 1) + xx13 - xx15 - t0; + z[3] = (int)cc; + cc >>= 32; + cc += (xx[4] & M) + (t4 << 1) + xx14 - t1; + z[4] = (int)cc; + cc >>= 32; + cc += (xx[5] & M) + (t5 << 1) - t2; + z[5] = (int)cc; + cc >>= 32; + cc += (xx[6] & M) + (t6 << 1) + t5 - t0; + z[6] = (int)cc; + cc >>= 32; + cc += (xx[7] & M) + (xx15 << 1) + xx08 - t2 - t4; + z[7] = (int)cc; + cc >>= 32; + cc += n; + +// assert cc >= 0; + + reduce32((int)cc, z); + } + + public static void reduce32(int x, int[] z) + { + long cc = 0; + + if (x != 0) + { + long xx08 = x & M; + + cc += (z[0] & M) + xx08; + z[0] = (int)cc; + cc >>= 32; + if (cc != 0) + { + cc += (z[1] & M); + z[1] = (int)cc; + cc >>= 32; + cc += (z[2] & M); + z[2] = (int)cc; + cc >>= 32; + } + cc += (z[3] & M) - xx08; + z[3] = (int)cc; + cc >>= 32; + if (cc != 0) + { + cc += (z[4] & M); + z[4] = (int)cc; + cc >>= 32; + cc += (z[5] & M); + z[5] = (int)cc; + cc >>= 32; + } + cc += (z[6] & M) - xx08; + z[6] = (int)cc; + cc >>= 32; + cc += (z[7] & M) + xx08; + z[7] = (int)cc; + cc >>= 32; + +// assert cc == 0 || cc == 1; + } + + if (cc != 0 || (z[7] == P7 && Nat256.gte(z, P))) + { + addPInvTo(z); + } + } + + public static void square(int[] x, int[] z) + { + int[] tt = Nat256.createExt(); + Nat256.square(x, tt); + reduce(tt, z); + } + + public static void squareN(int[] x, int n, int[] z) + { +// assert n > 0; + + int[] tt = Nat256.createExt(); + Nat256.square(x, tt); + reduce(tt, z); + + while (--n > 0) + { + Nat256.square(z, tt); + reduce(tt, z); + } + } + + public static void subtract(int[] x, int[] y, int[] z) + { + int c = Nat256.sub(x, y, z); + if (c != 0) + { + subPInvFrom(z); + } + } + + public static void subtractExt(int[] xx, int[] yy, int[] zz) + { + int c = Nat.sub(16, xx, yy, zz); + if (c != 0) + { + Nat.addTo(16, PExt, zz); + } + } + + public static void twice(int[] x, int[] z) + { + int c = Nat.shiftUpBit(8, x, 0, z); + if (c != 0 || (z[7] == P7 && Nat256.gte(z, P))) + { + addPInvTo(z); + } + } + + private static void addPInvTo(int[] z) + { + long c = (z[0] & M) + 1; + z[0] = (int)c; + c >>= 32; + if (c != 0) + { + c += (z[1] & M); + z[1] = (int)c; + c >>= 32; + c += (z[2] & M); + z[2] = (int)c; + c >>= 32; + } + c += (z[3] & M) - 1; + z[3] = (int)c; + c >>= 32; + if (c != 0) + { + c += (z[4] & M); + z[4] = (int)c; + c >>= 32; + c += (z[5] & M); + z[5] = (int)c; + c >>= 32; + } + c += (z[6] & M) - 1; + z[6] = (int)c; + c >>= 32; + c += (z[7] & M) + 1; + z[7] = (int)c; +// c >>= 32; + } + + private static void subPInvFrom(int[] z) + { + long c = (z[0] & M) - 1; + z[0] = (int)c; + c >>= 32; + if (c != 0) + { + c += (z[1] & M); + z[1] = (int)c; + c >>= 32; + c += (z[2] & M); + z[2] = (int)c; + c >>= 32; + } + c += (z[3] & M) + 1; + z[3] = (int)c; + c >>= 32; + if (c != 0) + { + c += (z[4] & M); + z[4] = (int)c; + c >>= 32; + c += (z[5] & M); + z[5] = (int)c; + c >>= 32; + } + c += (z[6] & M) + 1; + z[6] = (int)c; + c >>= 32; + c += (z[7] & M) - 1; + z[7] = (int)c; +// c >>= 32; + } +} diff --git a/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP256R1FieldElement.java b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP256R1FieldElement.java new file mode 100644 index 00000000..ddbab1a3 --- /dev/null +++ b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP256R1FieldElement.java @@ -0,0 +1,189 @@ +package org.spongycastle.math.ec.custom.sec; + +import java.math.BigInteger; + +import org.spongycastle.math.ec.ECFieldElement; +import org.spongycastle.math.raw.Mod; +import org.spongycastle.math.raw.Nat256; +import org.spongycastle.util.Arrays; + +public class SecP256R1FieldElement extends ECFieldElement +{ + public static final BigInteger Q = SecP256R1Curve.q; + + protected int[] x; + + public SecP256R1FieldElement(BigInteger x) + { + if (x == null || x.signum() < 0 || x.compareTo(Q) >= 0) + { + throw new IllegalArgumentException("x value invalid for SecP256R1FieldElement"); + } + + this.x = SecP256R1Field.fromBigInteger(x); + } + + public SecP256R1FieldElement() + { + this.x = Nat256.create(); + } + + protected SecP256R1FieldElement(int[] x) + { + this.x = x; + } + + public boolean isZero() + { + return Nat256.isZero(x); + } + + public boolean isOne() + { + return Nat256.isOne(x); + } + + public boolean testBitZero() + { + return Nat256.getBit(x, 0) == 1; + } + + public BigInteger toBigInteger() + { + return Nat256.toBigInteger(x); + } + + public String getFieldName() + { + return "SecP256R1Field"; + } + + public int getFieldSize() + { + return Q.bitLength(); + } + + public ECFieldElement add(ECFieldElement b) + { + int[] z = Nat256.create(); + SecP256R1Field.add(x, ((SecP256R1FieldElement)b).x, z); + return new SecP256R1FieldElement(z); + } + + public ECFieldElement addOne() + { + int[] z = Nat256.create(); + SecP256R1Field.addOne(x, z); + return new SecP256R1FieldElement(z); + } + + public ECFieldElement subtract(ECFieldElement b) + { + int[] z = Nat256.create(); + SecP256R1Field.subtract(x, ((SecP256R1FieldElement)b).x, z); + return new SecP256R1FieldElement(z); + } + + public ECFieldElement multiply(ECFieldElement b) + { + int[] z = Nat256.create(); + SecP256R1Field.multiply(x, ((SecP256R1FieldElement)b).x, z); + return new SecP256R1FieldElement(z); + } + + public ECFieldElement divide(ECFieldElement b) + { +// return multiply(b.invert()); + int[] z = Nat256.create(); + Mod.invert(SecP256R1Field.P, ((SecP256R1FieldElement)b).x, z); + SecP256R1Field.multiply(z, x, z); + return new SecP256R1FieldElement(z); + } + + public ECFieldElement negate() + { + int[] z = Nat256.create(); + SecP256R1Field.negate(x, z); + return new SecP256R1FieldElement(z); + } + + public ECFieldElement square() + { + int[] z = Nat256.create(); + SecP256R1Field.square(x, z); + return new SecP256R1FieldElement(z); + } + + public ECFieldElement invert() + { +// return new SecP256R1FieldElement(toBigInteger().modInverse(Q)); + int[] z = Nat256.create(); + Mod.invert(SecP256R1Field.P, x, z); + return new SecP256R1FieldElement(z); + } + + /** + * return a sqrt root - the routine verifies that the calculation returns the right value - if + * none exists it returns null. + */ + public ECFieldElement sqrt() + { + // Raise this element to the exponent 2^254 - 2^222 + 2^190 + 2^94 + + int[] x1 = this.x; + if (Nat256.isZero(x1) || Nat256.isOne(x1)) + { + return this; + } + + int[] t1 = Nat256.create(); + int[] t2 = Nat256.create(); + + SecP256R1Field.square(x1, t1); + SecP256R1Field.multiply(t1, x1, t1); + + SecP256R1Field.squareN(t1, 2, t2); + SecP256R1Field.multiply(t2, t1, t2); + + SecP256R1Field.squareN(t2, 4, t1); + SecP256R1Field.multiply(t1, t2, t1); + + SecP256R1Field.squareN(t1, 8, t2); + SecP256R1Field.multiply(t2, t1, t2); + + SecP256R1Field.squareN(t2, 16, t1); + SecP256R1Field.multiply(t1, t2, t1); + + SecP256R1Field.squareN(t1, 32, t1); + SecP256R1Field.multiply(t1, x1, t1); + + SecP256R1Field.squareN(t1, 96, t1); + SecP256R1Field.multiply(t1, x1, t1); + + SecP256R1Field.squareN(t1, 94, t1); + SecP256R1Field.square(t1, t2); + + return Nat256.eq(x1, t2) ? new SecP256R1FieldElement(t1) : null; + } + + public boolean equals(Object other) + { + if (other == this) + { + return true; + } + + if (!(other instanceof SecP256R1FieldElement)) + { + return false; + } + + SecP256R1FieldElement o = (SecP256R1FieldElement)other; + return Nat256.eq(x, o.x); + } + + public int hashCode() + { + return Q.hashCode() ^ Arrays.hashCode(x, 0, 8); + } +} diff --git a/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP256R1Point.java b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP256R1Point.java new file mode 100644 index 00000000..8daaf049 --- /dev/null +++ b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP256R1Point.java @@ -0,0 +1,308 @@ +package org.spongycastle.math.ec.custom.sec; + +import org.spongycastle.math.ec.ECCurve; +import org.spongycastle.math.ec.ECFieldElement; +import org.spongycastle.math.ec.ECPoint; +import org.spongycastle.math.raw.Nat; +import org.spongycastle.math.raw.Nat256; + +public class SecP256R1Point extends ECPoint.AbstractFp +{ + /** + * Create a point which encodes with 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 SecP256R1Point(ECCurve curve, ECFieldElement x, ECFieldElement y) + { + this(curve, x, y, false); + } + + /** + * Create a point that encodes with or without point compresion. + * + * @param curve + * the curve to use + * @param x + * affine x co-ordinate + * @param y + * affine y co-ordinate + * @param withCompression + * if true encode with point compression + * + * @deprecated per-point compression property will be removed, refer + * {@link #getEncoded(boolean)} + */ + public SecP256R1Point(ECCurve curve, ECFieldElement x, ECFieldElement y, boolean withCompression) + { + super(curve, x, y); + + if ((x == null) != (y == null)) + { + throw new IllegalArgumentException("Exactly one of the field elements is null"); + } + + this.withCompression = withCompression; + } + + SecP256R1Point(ECCurve curve, ECFieldElement x, ECFieldElement y, ECFieldElement[] zs, boolean withCompression) + { + super(curve, x, y, zs); + + this.withCompression = withCompression; + } + + protected ECPoint detach() + { + return new SecP256R1Point(null, getAffineXCoord(), getAffineYCoord()); + } + + public ECPoint add(ECPoint b) + { + if (this.isInfinity()) + { + return b; + } + if (b.isInfinity()) + { + return this; + } + if (this == b) + { + return twice(); + } + + ECCurve curve = this.getCurve(); + + SecP256R1FieldElement X1 = (SecP256R1FieldElement)this.x, Y1 = (SecP256R1FieldElement)this.y; + SecP256R1FieldElement X2 = (SecP256R1FieldElement)b.getXCoord(), Y2 = (SecP256R1FieldElement)b.getYCoord(); + + SecP256R1FieldElement Z1 = (SecP256R1FieldElement)this.zs[0]; + SecP256R1FieldElement Z2 = (SecP256R1FieldElement)b.getZCoord(0); + + int c; + int[] tt1 = Nat256.createExt(); + int[] t2 = Nat256.create(); + int[] t3 = Nat256.create(); + int[] t4 = Nat256.create(); + + boolean Z1IsOne = Z1.isOne(); + int[] U2, S2; + if (Z1IsOne) + { + U2 = X2.x; + S2 = Y2.x; + } + else + { + S2 = t3; + SecP256R1Field.square(Z1.x, S2); + + U2 = t2; + SecP256R1Field.multiply(S2, X2.x, U2); + + SecP256R1Field.multiply(S2, Z1.x, S2); + SecP256R1Field.multiply(S2, Y2.x, S2); + } + + boolean Z2IsOne = Z2.isOne(); + int[] U1, S1; + if (Z2IsOne) + { + U1 = X1.x; + S1 = Y1.x; + } + else + { + S1 = t4; + SecP256R1Field.square(Z2.x, S1); + + U1 = tt1; + SecP256R1Field.multiply(S1, X1.x, U1); + + SecP256R1Field.multiply(S1, Z2.x, S1); + SecP256R1Field.multiply(S1, Y1.x, S1); + } + + int[] H = Nat256.create(); + SecP256R1Field.subtract(U1, U2, H); + + int[] R = t2; + SecP256R1Field.subtract(S1, S2, R); + + // Check if b == this or b == -this + if (Nat256.isZero(H)) + { + if (Nat256.isZero(R)) + { + // this == b, i.e. this must be doubled + return this.twice(); + } + + // this == -b, i.e. the result is the point at infinity + return curve.getInfinity(); + } + + int[] HSquared = t3; + SecP256R1Field.square(H, HSquared); + + int[] G = Nat256.create(); + SecP256R1Field.multiply(HSquared, H, G); + + int[] V = t3; + SecP256R1Field.multiply(HSquared, U1, V); + + SecP256R1Field.negate(G, G); + Nat256.mul(S1, G, tt1); + + c = Nat256.addBothTo(V, V, G); + SecP256R1Field.reduce32(c, G); + + SecP256R1FieldElement X3 = new SecP256R1FieldElement(t4); + SecP256R1Field.square(R, X3.x); + SecP256R1Field.subtract(X3.x, G, X3.x); + + SecP256R1FieldElement Y3 = new SecP256R1FieldElement(G); + SecP256R1Field.subtract(V, X3.x, Y3.x); + SecP256R1Field.multiplyAddToExt(Y3.x, R, tt1); + SecP256R1Field.reduce(tt1, Y3.x); + + SecP256R1FieldElement Z3 = new SecP256R1FieldElement(H); + if (!Z1IsOne) + { + SecP256R1Field.multiply(Z3.x, Z1.x, Z3.x); + } + if (!Z2IsOne) + { + SecP256R1Field.multiply(Z3.x, Z2.x, Z3.x); + } + + ECFieldElement[] zs = new ECFieldElement[]{ Z3 }; + + return new SecP256R1Point(curve, X3, Y3, zs, this.withCompression); + } + + public ECPoint twice() + { + if (this.isInfinity()) + { + return this; + } + + ECCurve curve = this.getCurve(); + + SecP256R1FieldElement Y1 = (SecP256R1FieldElement)this.y; + if (Y1.isZero()) + { + return curve.getInfinity(); + } + + SecP256R1FieldElement X1 = (SecP256R1FieldElement)this.x, Z1 = (SecP256R1FieldElement)this.zs[0]; + + int c; + int[] t1 = Nat256.create(); + int[] t2 = Nat256.create(); + + int[] Y1Squared = Nat256.create(); + SecP256R1Field.square(Y1.x, Y1Squared); + + int[] T = Nat256.create(); + SecP256R1Field.square(Y1Squared, T); + + boolean Z1IsOne = Z1.isOne(); + + int[] Z1Squared = Z1.x; + if (!Z1IsOne) + { + Z1Squared = t2; + SecP256R1Field.square(Z1.x, Z1Squared); + } + + SecP256R1Field.subtract(X1.x, Z1Squared, t1); + + int[] M = t2; + SecP256R1Field.add(X1.x, Z1Squared, M); + SecP256R1Field.multiply(M, t1, M); + c = Nat256.addBothTo(M, M, M); + SecP256R1Field.reduce32(c, M); + + int[] S = Y1Squared; + SecP256R1Field.multiply(Y1Squared, X1.x, S); + c = Nat.shiftUpBits(8, S, 2, 0); + SecP256R1Field.reduce32(c, S); + + c = Nat.shiftUpBits(8, T, 3, 0, t1); + SecP256R1Field.reduce32(c, t1); + + SecP256R1FieldElement X3 = new SecP256R1FieldElement(T); + SecP256R1Field.square(M, X3.x); + SecP256R1Field.subtract(X3.x, S, X3.x); + SecP256R1Field.subtract(X3.x, S, X3.x); + + SecP256R1FieldElement Y3 = new SecP256R1FieldElement(S); + SecP256R1Field.subtract(S, X3.x, Y3.x); + SecP256R1Field.multiply(Y3.x, M, Y3.x); + SecP256R1Field.subtract(Y3.x, t1, Y3.x); + + SecP256R1FieldElement Z3 = new SecP256R1FieldElement(M); + SecP256R1Field.twice(Y1.x, Z3.x); + if (!Z1IsOne) + { + SecP256R1Field.multiply(Z3.x, Z1.x, Z3.x); + } + + return new SecP256R1Point(curve, X3, Y3, new ECFieldElement[]{ Z3 }, this.withCompression); + } + + public ECPoint twicePlus(ECPoint b) + { + if (this == b) + { + return threeTimes(); + } + if (this.isInfinity()) + { + return b; + } + if (b.isInfinity()) + { + return twice(); + } + + ECFieldElement Y1 = this.y; + if (Y1.isZero()) + { + return b; + } + + return twice().add(b); + } + + public ECPoint threeTimes() + { + if (this.isInfinity() || this.y.isZero()) + { + return this; + } + + // NOTE: Be careful about recursions between twicePlus and threeTimes + return twice().add(this); + } + + public ECPoint negate() + { + if (this.isInfinity()) + { + return this; + } + + return new SecP256R1Point(curve, this.x, this.y.negate(), this.zs, this.withCompression); + } +} diff --git a/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP384R1Curve.java b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP384R1Curve.java new file mode 100644 index 00000000..cb5bab24 --- /dev/null +++ b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP384R1Curve.java @@ -0,0 +1,80 @@ +package org.spongycastle.math.ec.custom.sec; + +import java.math.BigInteger; + +import org.spongycastle.math.ec.ECCurve; +import org.spongycastle.math.ec.ECFieldElement; +import org.spongycastle.math.ec.ECPoint; +import org.spongycastle.util.encoders.Hex; + +public class SecP384R1Curve extends ECCurve.AbstractFp +{ + public static final BigInteger q = new BigInteger(1, + Hex.decode("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFF0000000000000000FFFFFFFF")); + + private static final int SecP384R1_DEFAULT_COORDS = COORD_JACOBIAN; + + protected SecP384R1Point infinity; + + public SecP384R1Curve() + { + super(q); + + this.infinity = new SecP384R1Point(this, null, null); + + this.a = fromBigInteger(new BigInteger(1, + Hex.decode("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFF0000000000000000FFFFFFFC"))); + this.b = fromBigInteger(new BigInteger(1, + Hex.decode("B3312FA7E23EE7E4988E056BE3F82D19181D9C6EFE8141120314088F5013875AC656398D8A2ED19D2A85C8EDD3EC2AEF"))); + this.order = new BigInteger(1, Hex.decode("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFC7634D81F4372DDF581A0DB248B0A77AECEC196ACCC52973")); + this.cofactor = BigInteger.valueOf(1); + + this.coord = SecP384R1_DEFAULT_COORDS; + } + + protected ECCurve cloneCurve() + { + return new SecP384R1Curve(); + } + + public boolean supportsCoordinateSystem(int coord) + { + switch (coord) + { + case COORD_JACOBIAN: + return true; + default: + return false; + } + } + + public BigInteger getQ() + { + return q; + } + + public int getFieldSize() + { + return q.bitLength(); + } + + public ECFieldElement fromBigInteger(BigInteger x) + { + return new SecP384R1FieldElement(x); + } + + protected ECPoint createRawPoint(ECFieldElement x, ECFieldElement y, boolean withCompression) + { + return new SecP384R1Point(this, x, y, withCompression); + } + + protected ECPoint createRawPoint(ECFieldElement x, ECFieldElement y, ECFieldElement[] zs, boolean withCompression) + { + return new SecP384R1Point(this, x, y, zs, withCompression); + } + + public ECPoint getInfinity() + { + return infinity; + } +} diff --git a/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP384R1Field.java b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP384R1Field.java new file mode 100644 index 00000000..d3b78762 --- /dev/null +++ b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP384R1Field.java @@ -0,0 +1,295 @@ +package org.spongycastle.math.ec.custom.sec; + +import java.math.BigInteger; + +import org.spongycastle.math.raw.Nat; +import org.spongycastle.math.raw.Nat384; + +public class SecP384R1Field +{ + private static final long M = 0xFFFFFFFFL; + + // 2^384 - 2^128 - 2^96 + 2^32 - 1 + static final int[] P = new int[]{ 0xFFFFFFFF, 0x00000000, 0x00000000, 0xFFFFFFFF, 0xFFFFFFFE, 0xFFFFFFFF, + 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF }; + static final int[] PExt = new int[]{ 0x00000001, 0xFFFFFFFE, 0x00000000, 0x00000002, 0x00000000, 0xFFFFFFFE, + 0x00000000, 0x00000002, 0x00000001, 0x00000000, 0x00000000, 0x00000000, 0xFFFFFFFE, 0x00000001, 0x00000000, + 0xFFFFFFFE, 0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF }; + private static final int[] PExtInv = new int[]{ 0xFFFFFFFF, 0x00000001, 0xFFFFFFFF, 0xFFFFFFFD, 0xFFFFFFFF, 0x00000001, + 0xFFFFFFFF, 0xFFFFFFFD, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000001, 0xFFFFFFFE, 0xFFFFFFFF, + 0x00000001, 0x00000002 }; + private static final int P11 = 0xFFFFFFFF; + private static final int PExt23 = 0xFFFFFFFF; + + public static void add(int[] x, int[] y, int[] z) + { + int c = Nat.add(12, x, y, z); + if (c != 0 || (z[11] == P11 && Nat.gte(12, z, P))) + { + addPInvTo(z); + } + } + + public static void addExt(int[] xx, int[] yy, int[] zz) + { + int c = Nat.add(24, xx, yy, zz); + if (c != 0 || (zz[23] == PExt23 && Nat.gte(24, zz, PExt))) + { + if (Nat.addTo(PExtInv.length, PExtInv, zz) != 0) + { + Nat.incAt(24, zz, PExtInv.length); + } + } + } + + public static void addOne(int[] x, int[] z) + { + int c = Nat.inc(12, x, z); + if (c != 0 || (z[11] == P11 && Nat.gte(12, z, P))) + { + addPInvTo(z); + } + } + + public static int[] fromBigInteger(BigInteger x) + { + int[] z = Nat.fromBigInteger(384, x); + if (z[11] == P11 && Nat.gte(12, z, P)) + { + Nat.subFrom(12, P, z); + } + return z; + } + + public static void half(int[] x, int[] z) + { + if ((x[0] & 1) == 0) + { + Nat.shiftDownBit(12, x, 0, z); + } + else + { + int c = Nat.add(12, x, P, z); + Nat.shiftDownBit(12, z, c); + } + } + + public static void multiply(int[] x, int[] y, int[] z) + { + int[] tt = Nat.create(24); + Nat384.mul(x, y, tt); + reduce(tt, z); + } + + public static void negate(int[] x, int[] z) + { + if (Nat.isZero(12, x)) + { + Nat.zero(12, z); + } + else + { + Nat.sub(12, P, x, z); + } + } + + public static void reduce(int[] xx, int[] z) + { + long xx16 = xx[16] & M, xx17 = xx[17] & M, xx18 = xx[18] & M, xx19 = xx[19] & M; + long xx20 = xx[20] & M, xx21 = xx[21] & M, xx22 = xx[22] & M, xx23 = xx[23] & M; + + final long n = 1; + + long t0 = (xx[12] & M) + xx20 - n; + long t1 = (xx[13] & M) + xx22; + long t2 = (xx[14] & M) + xx22 + xx23; + long t3 = (xx[15] & M) + xx23; + long t4 = xx17 + xx21; + long t5 = xx21 - xx23; + long t6 = xx22 - xx23; + + long cc = 0; + cc += (xx[0] & M) + t0 + t5; + z[0] = (int)cc; + cc >>= 32; + cc += (xx[1] & M) + xx23 - t0 + t1; + z[1] = (int)cc; + cc >>= 32; + cc += (xx[2] & M) - xx21 - t1 + t2; + z[2] = (int)cc; + cc >>= 32; + cc += (xx[3] & M) + t0 - t2 + t3 + t5; + z[3] = (int)cc; + cc >>= 32; + cc += (xx[4] & M) + xx16 + xx21 + t0 + t1 - t3 + t5; + z[4] = (int)cc; + cc >>= 32; + cc += (xx[5] & M) - xx16 + t1 + t2 + t4; + z[5] = (int)cc; + cc >>= 32; + cc += (xx[6] & M) + xx18 - xx17 + t2 + t3; + z[6] = (int)cc; + cc >>= 32; + cc += (xx[7] & M) + xx16 + xx19 - xx18 + t3; + z[7] = (int)cc; + cc >>= 32; + cc += (xx[8] & M) + xx16 + xx17 + xx20 - xx19; + z[8] = (int)cc; + cc >>= 32; + cc += (xx[9] & M) + xx18 - xx20 + t4; + z[9] = (int)cc; + cc >>= 32; + cc += (xx[10] & M) + xx18 + xx19 - t5 + t6; + z[10] = (int)cc; + cc >>= 32; + cc += (xx[11] & M) + xx19 + xx20 - t6; + z[11] = (int)cc; + cc >>= 32; + cc += n; + +// assert cc >= 0; + + reduce32((int)cc, z); + } + + public static void reduce32(int x, int[] z) + { + long cc = 0; + + if (x != 0) + { + long xx12 = x & M; + + cc += (z[0] & M) + xx12; + z[0] = (int)cc; + cc >>= 32; + cc += (z[1] & M) - xx12; + z[1] = (int)cc; + cc >>= 32; + if (cc != 0) + { + cc += (z[2] & M); + z[2] = (int)cc; + cc >>= 32; + } + cc += (z[3] & M) + xx12; + z[3] = (int)cc; + cc >>= 32; + cc += (z[4] & M) + xx12; + z[4] = (int)cc; + cc >>= 32; + +// assert cc == 0 || cc == 1; + } + + if ((cc != 0 && Nat.incAt(12, z, 5) != 0) + || (z[11] == P11 && Nat.gte(12, z, P))) + { + addPInvTo(z); + } + } + + public static void square(int[] x, int[] z) + { + int[] tt = Nat.create(24); + Nat384.square(x, tt); + reduce(tt, z); + } + + public static void squareN(int[] x, int n, int[] z) + { +// assert n > 0; + + int[] tt = Nat.create(24); + Nat384.square(x, tt); + reduce(tt, z); + + while (--n > 0) + { + Nat384.square(z, tt); + reduce(tt, z); + } + } + + public static void subtract(int[] x, int[] y, int[] z) + { + int c = Nat.sub(12, x, y, z); + if (c != 0) + { + subPInvFrom(z); + } + } + + public static void subtractExt(int[] xx, int[] yy, int[] zz) + { + int c = Nat.sub(24, xx, yy, zz); + if (c != 0) + { + if (Nat.subFrom(PExtInv.length, PExtInv, zz) != 0) + { + Nat.decAt(24, zz, PExtInv.length); + } + } + } + + public static void twice(int[] x, int[] z) + { + int c = Nat.shiftUpBit(12, x, 0, z); + if (c != 0 || (z[11] == P11 && Nat.gte(12, z, P))) + { + addPInvTo(z); + } + } + + private static void addPInvTo(int[] z) + { + long c = (z[0] & M) + 1; + z[0] = (int)c; + c >>= 32; + c += (z[1] & M) - 1; + z[1] = (int)c; + c >>= 32; + if (c != 0) + { + c += (z[2] & M); + z[2] = (int)c; + c >>= 32; + } + c += (z[3] & M) + 1; + z[3] = (int)c; + c >>= 32; + c += (z[4] & M) + 1; + z[4] = (int)c; + c >>= 32; + if (c != 0) + { + Nat.incAt(12, z, 5); + } + } + + private static void subPInvFrom(int[] z) + { + long c = (z[0] & M) - 1; + z[0] = (int)c; + c >>= 32; + c += (z[1] & M) + 1; + z[1] = (int)c; + c >>= 32; + if (c != 0) + { + c += (z[2] & M); + z[2] = (int)c; + c >>= 32; + } + c += (z[3] & M) - 1; + z[3] = (int)c; + c >>= 32; + c += (z[4] & M) - 1; + z[4] = (int)c; + c >>= 32; + if (c != 0) + { + Nat.decAt(12, z, 5); + } + } +} diff --git a/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP384R1FieldElement.java b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP384R1FieldElement.java new file mode 100644 index 00000000..3203bda9 --- /dev/null +++ b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP384R1FieldElement.java @@ -0,0 +1,211 @@ +package org.spongycastle.math.ec.custom.sec; + +import java.math.BigInteger; + +import org.spongycastle.math.ec.ECFieldElement; +import org.spongycastle.math.raw.Mod; +import org.spongycastle.math.raw.Nat; +import org.spongycastle.util.Arrays; + +public class SecP384R1FieldElement extends ECFieldElement +{ + public static final BigInteger Q = SecP384R1Curve.q; + + protected int[] x; + + public SecP384R1FieldElement(BigInteger x) + { + if (x == null || x.signum() < 0 || x.compareTo(Q) >= 0) + { + throw new IllegalArgumentException("x value invalid for SecP384R1FieldElement"); + } + + this.x = SecP384R1Field.fromBigInteger(x); + } + + public SecP384R1FieldElement() + { + this.x = Nat.create(12); + } + + protected SecP384R1FieldElement(int[] x) + { + this.x = x; + } + + public boolean isZero() + { + return Nat.isZero(12, x); + } + + public boolean isOne() + { + return Nat.isOne(12, x); + } + + public boolean testBitZero() + { + return Nat.getBit(x, 0) == 1; + } + + public BigInteger toBigInteger() + { + return Nat.toBigInteger(12, x); + } + + public String getFieldName() + { + return "SecP384R1Field"; + } + + public int getFieldSize() + { + return Q.bitLength(); + } + + public ECFieldElement add(ECFieldElement b) + { + int[] z = Nat.create(12); + SecP384R1Field.add(x, ((SecP384R1FieldElement)b).x, z); + return new SecP384R1FieldElement(z); + } + + public ECFieldElement addOne() + { + int[] z = Nat.create(12); + SecP384R1Field.addOne(x, z); + return new SecP384R1FieldElement(z); + } + + public ECFieldElement subtract(ECFieldElement b) + { + int[] z = Nat.create(12); + SecP384R1Field.subtract(x, ((SecP384R1FieldElement)b).x, z); + return new SecP384R1FieldElement(z); + } + + public ECFieldElement multiply(ECFieldElement b) + { + int[] z = Nat.create(12); + SecP384R1Field.multiply(x, ((SecP384R1FieldElement)b).x, z); + return new SecP384R1FieldElement(z); + } + + public ECFieldElement divide(ECFieldElement b) + { +// return multiply(b.invert()); + int[] z = Nat.create(12); + Mod.invert(SecP384R1Field.P, ((SecP384R1FieldElement)b).x, z); + SecP384R1Field.multiply(z, x, z); + return new SecP384R1FieldElement(z); + } + + public ECFieldElement negate() + { + int[] z = Nat.create(12); + SecP384R1Field.negate(x, z); + return new SecP384R1FieldElement(z); + } + + public ECFieldElement square() + { + int[] z = Nat.create(12); + SecP384R1Field.square(x, z); + return new SecP384R1FieldElement(z); + } + + public ECFieldElement invert() + { +// return new SecP384R1FieldElement(toBigInteger().modInverse(Q)); + int[] z = Nat.create(12); + Mod.invert(SecP384R1Field.P, x, z); + return new SecP384R1FieldElement(z); + } + + /** + * return a sqrt root - the routine verifies that the calculation returns the right value - if + * none exists it returns null. + */ + public ECFieldElement sqrt() + { + // Raise this element to the exponent 2^382 - 2^126 - 2^94 + 2^30 + + int[] x1 = this.x; + if (Nat.isZero(12, x1) || Nat.isOne(12, x1)) + { + return this; + } + + int[] t1 = Nat.create(12); + int[] t2 = Nat.create(12); + int[] t3 = Nat.create(12); + int[] t4 = Nat.create(12); + + SecP384R1Field.square(x1, t1); + SecP384R1Field.multiply(t1, x1, t1); + + SecP384R1Field.squareN(t1, 2, t2); + SecP384R1Field.multiply(t2, t1, t2); + + SecP384R1Field.square(t2, t2); + SecP384R1Field.multiply(t2, x1, t2); + + SecP384R1Field.squareN(t2, 5, t3); + SecP384R1Field.multiply(t3, t2, t3); + + SecP384R1Field.squareN(t3, 5, t4); + SecP384R1Field.multiply(t4, t2, t4); + + SecP384R1Field.squareN(t4, 15, t2); + SecP384R1Field.multiply(t2, t4, t2); + + SecP384R1Field.squareN(t2, 2, t3); + SecP384R1Field.multiply(t1, t3, t1); + + SecP384R1Field.squareN(t3, 28, t3); + SecP384R1Field.multiply(t2, t3, t2); + + SecP384R1Field.squareN(t2, 60, t3); + SecP384R1Field.multiply(t3, t2, t3); + + int[] r = t2; + + SecP384R1Field.squareN(t3, 120, r); + SecP384R1Field.multiply(r, t3, r); + + SecP384R1Field.squareN(r, 15, r); + SecP384R1Field.multiply(r, t4, r); + + SecP384R1Field.squareN(r, 33, r); + SecP384R1Field.multiply(r, t1, r); + + SecP384R1Field.squareN(r, 64, r); + SecP384R1Field.multiply(r, x1, r); + + SecP384R1Field.squareN(r, 30, t1); + SecP384R1Field.square(t1, t2); + + return Nat.eq(12, x1, t2) ? new SecP384R1FieldElement(t1) : null; + } + + public boolean equals(Object other) + { + if (other == this) + { + return true; + } + + if (!(other instanceof SecP384R1FieldElement)) + { + return false; + } + + SecP384R1FieldElement o = (SecP384R1FieldElement)other; + return Nat.eq(12, x, o.x); + } + + public int hashCode() + { + return Q.hashCode() ^ Arrays.hashCode(x, 0, 12); + } +} diff --git a/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP384R1Point.java b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP384R1Point.java new file mode 100644 index 00000000..47e5c793 --- /dev/null +++ b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP384R1Point.java @@ -0,0 +1,309 @@ +package org.spongycastle.math.ec.custom.sec; + +import org.spongycastle.math.ec.ECCurve; +import org.spongycastle.math.ec.ECFieldElement; +import org.spongycastle.math.ec.ECPoint; +import org.spongycastle.math.raw.Nat; +import org.spongycastle.math.raw.Nat384; + +public class SecP384R1Point extends ECPoint.AbstractFp +{ + /** + * Create a point which encodes with 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 SecP384R1Point(ECCurve curve, ECFieldElement x, ECFieldElement y) + { + this(curve, x, y, false); + } + + /** + * Create a point that encodes with or without point compresion. + * + * @param curve + * the curve to use + * @param x + * affine x co-ordinate + * @param y + * affine y co-ordinate + * @param withCompression + * if true encode with point compression + * + * @deprecated per-point compression property will be removed, refer + * {@link #getEncoded(boolean)} + */ + public SecP384R1Point(ECCurve curve, ECFieldElement x, ECFieldElement y, boolean withCompression) + { + super(curve, x, y); + + if ((x == null) != (y == null)) + { + throw new IllegalArgumentException("Exactly one of the field elements is null"); + } + + this.withCompression = withCompression; + } + + SecP384R1Point(ECCurve curve, ECFieldElement x, ECFieldElement y, ECFieldElement[] zs, boolean withCompression) + { + super(curve, x, y, zs); + + this.withCompression = withCompression; + } + + protected ECPoint detach() + { + return new SecP384R1Point(null, getAffineXCoord(), getAffineYCoord()); + } + + public ECPoint add(ECPoint b) + { + if (this.isInfinity()) + { + return b; + } + if (b.isInfinity()) + { + return this; + } + if (this == b) + { + return twice(); + } + + ECCurve curve = this.getCurve(); + + SecP384R1FieldElement X1 = (SecP384R1FieldElement)this.x, Y1 = (SecP384R1FieldElement)this.y; + SecP384R1FieldElement X2 = (SecP384R1FieldElement)b.getXCoord(), Y2 = (SecP384R1FieldElement)b.getYCoord(); + + SecP384R1FieldElement Z1 = (SecP384R1FieldElement)this.zs[0]; + SecP384R1FieldElement Z2 = (SecP384R1FieldElement)b.getZCoord(0); + + int c; + int[] tt1 = Nat.create(24); + int[] tt2 = Nat.create(24); + int[] t3 = Nat.create(12); + int[] t4 = Nat.create(12); + + boolean Z1IsOne = Z1.isOne(); + int[] U2, S2; + if (Z1IsOne) + { + U2 = X2.x; + S2 = Y2.x; + } + else + { + S2 = t3; + SecP384R1Field.square(Z1.x, S2); + + U2 = tt2; + SecP384R1Field.multiply(S2, X2.x, U2); + + SecP384R1Field.multiply(S2, Z1.x, S2); + SecP384R1Field.multiply(S2, Y2.x, S2); + } + + boolean Z2IsOne = Z2.isOne(); + int[] U1, S1; + if (Z2IsOne) + { + U1 = X1.x; + S1 = Y1.x; + } + else + { + S1 = t4; + SecP384R1Field.square(Z2.x, S1); + + U1 = tt1; + SecP384R1Field.multiply(S1, X1.x, U1); + + SecP384R1Field.multiply(S1, Z2.x, S1); + SecP384R1Field.multiply(S1, Y1.x, S1); + } + + int[] H = Nat.create(12); + SecP384R1Field.subtract(U1, U2, H); + + int[] R = Nat.create(12); + SecP384R1Field.subtract(S1, S2, R); + + // Check if b == this or b == -this + if (Nat.isZero(12, H)) + { + if (Nat.isZero(12, R)) + { + // this == b, i.e. this must be doubled + return this.twice(); + } + + // this == -b, i.e. the result is the point at infinity + return curve.getInfinity(); + } + + int[] HSquared = t3; + SecP384R1Field.square(H, HSquared); + + int[] G = Nat.create(12); + SecP384R1Field.multiply(HSquared, H, G); + + int[] V = t3; + SecP384R1Field.multiply(HSquared, U1, V); + + SecP384R1Field.negate(G, G); + Nat384.mul(S1, G, tt1); + + c = Nat.addBothTo(12, V, V, G); + SecP384R1Field.reduce32(c, G); + + SecP384R1FieldElement X3 = new SecP384R1FieldElement(t4); + SecP384R1Field.square(R, X3.x); + SecP384R1Field.subtract(X3.x, G, X3.x); + + SecP384R1FieldElement Y3 = new SecP384R1FieldElement(G); + SecP384R1Field.subtract(V, X3.x, Y3.x); + Nat384.mul(Y3.x, R, tt2); + SecP384R1Field.addExt(tt1, tt2, tt1); + SecP384R1Field.reduce(tt1, Y3.x); + + SecP384R1FieldElement Z3 = new SecP384R1FieldElement(H); + if (!Z1IsOne) + { + SecP384R1Field.multiply(Z3.x, Z1.x, Z3.x); + } + if (!Z2IsOne) + { + SecP384R1Field.multiply(Z3.x, Z2.x, Z3.x); + } + + ECFieldElement[] zs = new ECFieldElement[]{ Z3 }; + + return new SecP384R1Point(curve, X3, Y3, zs, this.withCompression); + } + + public ECPoint twice() + { + if (this.isInfinity()) + { + return this; + } + + ECCurve curve = this.getCurve(); + + SecP384R1FieldElement Y1 = (SecP384R1FieldElement)this.y; + if (Y1.isZero()) + { + return curve.getInfinity(); + } + + SecP384R1FieldElement X1 = (SecP384R1FieldElement)this.x, Z1 = (SecP384R1FieldElement)this.zs[0]; + + int c; + int[] t1 = Nat.create(12); + int[] t2 = Nat.create(12); + + int[] Y1Squared = Nat.create(12); + SecP384R1Field.square(Y1.x, Y1Squared); + + int[] T = Nat.create(12); + SecP384R1Field.square(Y1Squared, T); + + boolean Z1IsOne = Z1.isOne(); + + int[] Z1Squared = Z1.x; + if (!Z1IsOne) + { + Z1Squared = t2; + SecP384R1Field.square(Z1.x, Z1Squared); + } + + SecP384R1Field.subtract(X1.x, Z1Squared, t1); + + int[] M = t2; + SecP384R1Field.add(X1.x, Z1Squared, M); + SecP384R1Field.multiply(M, t1, M); + c = Nat.addBothTo(12, M, M, M); + SecP384R1Field.reduce32(c, M); + + int[] S = Y1Squared; + SecP384R1Field.multiply(Y1Squared, X1.x, S); + c = Nat.shiftUpBits(12, S, 2, 0); + SecP384R1Field.reduce32(c, S); + + c = Nat.shiftUpBits(12, T, 3, 0, t1); + SecP384R1Field.reduce32(c, t1); + + SecP384R1FieldElement X3 = new SecP384R1FieldElement(T); + SecP384R1Field.square(M, X3.x); + SecP384R1Field.subtract(X3.x, S, X3.x); + SecP384R1Field.subtract(X3.x, S, X3.x); + + SecP384R1FieldElement Y3 = new SecP384R1FieldElement(S); + SecP384R1Field.subtract(S, X3.x, Y3.x); + SecP384R1Field.multiply(Y3.x, M, Y3.x); + SecP384R1Field.subtract(Y3.x, t1, Y3.x); + + SecP384R1FieldElement Z3 = new SecP384R1FieldElement(M); + SecP384R1Field.twice(Y1.x, Z3.x); + if (!Z1IsOne) + { + SecP384R1Field.multiply(Z3.x, Z1.x, Z3.x); + } + + return new SecP384R1Point(curve, X3, Y3, new ECFieldElement[]{ Z3 }, this.withCompression); + } + + public ECPoint twicePlus(ECPoint b) + { + if (this == b) + { + return threeTimes(); + } + if (this.isInfinity()) + { + return b; + } + if (b.isInfinity()) + { + return twice(); + } + + ECFieldElement Y1 = this.y; + if (Y1.isZero()) + { + return b; + } + + return twice().add(b); + } + + public ECPoint threeTimes() + { + if (this.isInfinity() || this.y.isZero()) + { + return this; + } + + // NOTE: Be careful about recursions between twicePlus and threeTimes + return twice().add(this); + } + + public ECPoint negate() + { + if (this.isInfinity()) + { + return this; + } + + return new SecP384R1Point(curve, this.x, this.y.negate(), this.zs, this.withCompression); + } +} diff --git a/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP521R1Curve.java b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP521R1Curve.java new file mode 100644 index 00000000..fb53cfbb --- /dev/null +++ b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP521R1Curve.java @@ -0,0 +1,80 @@ +package org.spongycastle.math.ec.custom.sec; + +import java.math.BigInteger; + +import org.spongycastle.math.ec.ECCurve; +import org.spongycastle.math.ec.ECFieldElement; +import org.spongycastle.math.ec.ECPoint; +import org.spongycastle.util.encoders.Hex; + +public class SecP521R1Curve extends ECCurve.AbstractFp +{ + public static final BigInteger q = new BigInteger(1, + Hex.decode("01FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF")); + + private static final int SecP521R1_DEFAULT_COORDS = COORD_JACOBIAN; + + protected SecP521R1Point infinity; + + public SecP521R1Curve() + { + super(q); + + this.infinity = new SecP521R1Point(this, null, null); + + this.a = fromBigInteger(new BigInteger(1, + Hex.decode("01FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFC"))); + this.b = fromBigInteger(new BigInteger(1, + Hex.decode("0051953EB9618E1C9A1F929A21A0B68540EEA2DA725B99B315F3B8B489918EF109E156193951EC7E937B1652C0BD3BB1BF073573DF883D2C34F1EF451FD46B503F00"))); + this.order = new BigInteger(1, Hex.decode("01FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFA51868783BF2F966B7FCC0148F709A5D03BB5C9B8899C47AEBB6FB71E91386409")); + this.cofactor = BigInteger.valueOf(1); + + this.coord = SecP521R1_DEFAULT_COORDS; + } + + protected ECCurve cloneCurve() + { + return new SecP521R1Curve(); + } + + public boolean supportsCoordinateSystem(int coord) + { + switch (coord) + { + case COORD_JACOBIAN: + return true; + default: + return false; + } + } + + public BigInteger getQ() + { + return q; + } + + public int getFieldSize() + { + return q.bitLength(); + } + + public ECFieldElement fromBigInteger(BigInteger x) + { + return new SecP521R1FieldElement(x); + } + + protected ECPoint createRawPoint(ECFieldElement x, ECFieldElement y, boolean withCompression) + { + return new SecP521R1Point(this, x, y, withCompression); + } + + protected ECPoint createRawPoint(ECFieldElement x, ECFieldElement y, ECFieldElement[] zs, boolean withCompression) + { + return new SecP521R1Point(this, x, y, zs, withCompression); + } + + public ECPoint getInfinity() + { + return infinity; + } +} diff --git a/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP521R1Field.java b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP521R1Field.java new file mode 100644 index 00000000..5328a510 --- /dev/null +++ b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP521R1Field.java @@ -0,0 +1,156 @@ +package org.spongycastle.math.ec.custom.sec; + +import java.math.BigInteger; + +import org.spongycastle.math.raw.Nat; +import org.spongycastle.math.raw.Nat512; + +public class SecP521R1Field +{ + // 2^521 - 1 + static final int[] P = new int[]{ 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, + 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0x1FF }; + private static final int P16 = 0x1FF; + + public static void add(int[] x, int[] y, int[] z) + { + int c = Nat.add(16, x, y, z) + x[16] + y[16]; + if (c > P16 || (c == P16 && Nat.eq(16, z, P))) + { + c += Nat.inc(16, z); + c &= P16; + } + z[16] = c; + } + + public static void addOne(int[] x, int[] z) + { + int c = Nat.inc(16, x, z) + x[16]; + if (c > P16 || (c == P16 && Nat.eq(16, z, P))) + { + c += Nat.inc(16, z); + c &= P16; + } + z[16] = c; + } + + public static int[] fromBigInteger(BigInteger x) + { + int[] z = Nat.fromBigInteger(521, x); + if (Nat.eq(17, z, P)) + { + Nat.zero(17, z); + } + return z; + } + + public static void half(int[] x, int[] z) + { + int x16 = x[16]; + int c = Nat.shiftDownBit(16, x, x16, z); + z[16] = (x16 >>> 1) | (c >>> 23); + } + + public static void multiply(int[] x, int[] y, int[] z) + { + int[] tt = Nat.create(33); + implMultiply(x, y, tt); + reduce(tt, z); + } + + public static void negate(int[] x, int[] z) + { + if (Nat.isZero(17, x)) + { + Nat.zero(17, z); + } + else + { + Nat.sub(17, P, x, z); + } + } + + public static void reduce(int[] xx, int[] z) + { +// assert xx[32] >>> 18 == 0; + + int xx32 = xx[32]; + int c = Nat.shiftDownBits(16, xx, 16, 9, xx32, z, 0) >>> 23; + c += xx32 >>> 9; + c += Nat.addTo(16, xx, z); + if (c > P16 || (c == P16 && Nat.eq(16, z, P))) + { + c += Nat.inc(16, z); + c &= P16; + } + z[16] = c; + } + + public static void reduce23(int[] z) + { + int z16 = z[16]; + int c = Nat.addWordTo(16, z16 >>> 9, z) + (z16 & P16); + if (c > P16 || (c == P16 && Nat.eq(16, z, P))) + { + c += Nat.inc(16, z); + c &= P16; + } + z[16] = c; + } + + public static void square(int[] x, int[] z) + { + int[] tt = Nat.create(33); + implSquare(x, tt); + reduce(tt, z); + } + + public static void squareN(int[] x, int n, int[] z) + { +// assert n > 0; + + int[] tt = Nat.create(33); + implSquare(x, tt); + reduce(tt, z); + + while (--n > 0) + { + implSquare(z, tt); + reduce(tt, z); + } + } + + public static void subtract(int[] x, int[] y, int[] z) + { + int c = Nat.sub(16, x, y, z) + x[16] - y[16]; + if (c < 0) + { + c += Nat.dec(16, z); + c &= P16; + } + z[16] = c; + } + + public static void twice(int[] x, int[] z) + { + int x16 = x[16]; + int c = Nat.shiftUpBit(16, x, x16 << 23, z) | (x16 << 1); + z[16] = c & P16; + } + + protected static void implMultiply(int[] x, int[] y, int[] zz) + { + Nat512.mul(x, y, zz); + + int x16 = x[16], y16 = y[16]; + zz[32] = Nat.mul31BothAdd(16, x16, y, y16, x, zz, 16) + (x16 * y16); + } + + protected static void implSquare(int[] x, int[] zz) + { + Nat512.square(x, zz); + + int x16 = x[16]; + zz[32] = Nat.mulWordAddTo(16, x16 << 1, x, 0, zz, 16) + (x16 * x16); + } +} diff --git a/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP521R1FieldElement.java b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP521R1FieldElement.java new file mode 100644 index 00000000..b0b92b6e --- /dev/null +++ b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP521R1FieldElement.java @@ -0,0 +1,169 @@ +package org.spongycastle.math.ec.custom.sec; + +import java.math.BigInteger; + +import org.spongycastle.math.ec.ECFieldElement; +import org.spongycastle.math.raw.Mod; +import org.spongycastle.math.raw.Nat; +import org.spongycastle.util.Arrays; + +public class SecP521R1FieldElement extends ECFieldElement +{ + public static final BigInteger Q = SecP521R1Curve.q; + + protected int[] x; + + public SecP521R1FieldElement(BigInteger x) + { + if (x == null || x.signum() < 0 || x.compareTo(Q) >= 0) + { + throw new IllegalArgumentException("x value invalid for SecP521R1FieldElement"); + } + + this.x = SecP521R1Field.fromBigInteger(x); + } + + public SecP521R1FieldElement() + { + this.x = Nat.create(17); + } + + protected SecP521R1FieldElement(int[] x) + { + this.x = x; + } + + public boolean isZero() + { + return Nat.isZero(17, x); + } + + public boolean isOne() + { + return Nat.isOne(17, x); + } + + public boolean testBitZero() + { + return Nat.getBit(x, 0) == 1; + } + + public BigInteger toBigInteger() + { + return Nat.toBigInteger(17, x); + } + + public String getFieldName() + { + return "SecP521R1Field"; + } + + public int getFieldSize() + { + return Q.bitLength(); + } + + public ECFieldElement add(ECFieldElement b) + { + int[] z = Nat.create(17); + SecP521R1Field.add(x, ((SecP521R1FieldElement)b).x, z); + return new SecP521R1FieldElement(z); + } + + public ECFieldElement addOne() + { + int[] z = Nat.create(17); + SecP521R1Field.addOne(x, z); + return new SecP521R1FieldElement(z); + } + + public ECFieldElement subtract(ECFieldElement b) + { + int[] z = Nat.create(17); + SecP521R1Field.subtract(x, ((SecP521R1FieldElement)b).x, z); + return new SecP521R1FieldElement(z); + } + + public ECFieldElement multiply(ECFieldElement b) + { + int[] z = Nat.create(17); + SecP521R1Field.multiply(x, ((SecP521R1FieldElement)b).x, z); + return new SecP521R1FieldElement(z); + } + + public ECFieldElement divide(ECFieldElement b) + { +// return multiply(b.invert()); + int[] z = Nat.create(17); + Mod.invert(SecP521R1Field.P, ((SecP521R1FieldElement)b).x, z); + SecP521R1Field.multiply(z, x, z); + return new SecP521R1FieldElement(z); + } + + public ECFieldElement negate() + { + int[] z = Nat.create(17); + SecP521R1Field.negate(x, z); + return new SecP521R1FieldElement(z); + } + + public ECFieldElement square() + { + int[] z = Nat.create(17); + SecP521R1Field.square(x, z); + return new SecP521R1FieldElement(z); + } + + public ECFieldElement invert() + { +// return new SecP521R1FieldElement(toBigInteger().modInverse(Q)); + int[] z = Nat.create(17); + Mod.invert(SecP521R1Field.P, x, z); + return new SecP521R1FieldElement(z); + } + + // D.1.4 91 + /** + * return a sqrt root - the routine verifies that the calculation returns the right value - if + * none exists it returns null. + */ + public ECFieldElement sqrt() + { + // Raise this element to the exponent 2^519 + + int[] x1 = this.x; + if (Nat.isZero(17, x1) || Nat.isOne(17, x1)) + { + return this; + } + + int[] t1 = Nat.create(17); + int[] t2 = Nat.create(17); + + SecP521R1Field.squareN(x1, 519, t1); + SecP521R1Field.square(t1, t2); + + return Nat.eq(17, x1, t2) ? new SecP521R1FieldElement(t1) : null; + } + + public boolean equals(Object other) + { + if (other == this) + { + return true; + } + + if (!(other instanceof SecP521R1FieldElement)) + { + return false; + } + + SecP521R1FieldElement o = (SecP521R1FieldElement)other; + return Nat.eq(17, x, o.x); + } + + public int hashCode() + { + return Q.hashCode() ^ Arrays.hashCode(x, 0, 17); + } +} diff --git a/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP521R1Point.java b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP521R1Point.java new file mode 100644 index 00000000..c38132b5 --- /dev/null +++ b/core/src/main/java/org/spongycastle/math/ec/custom/sec/SecP521R1Point.java @@ -0,0 +1,333 @@ +package org.spongycastle.math.ec.custom.sec; + +import org.spongycastle.math.ec.ECCurve; +import org.spongycastle.math.ec.ECFieldElement; +import org.spongycastle.math.ec.ECPoint; +import org.spongycastle.math.raw.Nat; + +public class SecP521R1Point extends ECPoint.AbstractFp +{ + /** + * Create a point which encodes with 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 SecP521R1Point(ECCurve curve, ECFieldElement x, ECFieldElement y) + { + this(curve, x, y, false); + } + + /** + * Create a point that encodes with or without point compresion. + * + * @param curve + * the curve to use + * @param x + * affine x co-ordinate + * @param y + * affine y co-ordinate + * @param withCompression + * if true encode with point compression + * + * @deprecated per-point compression property will be removed, refer + * {@link #getEncoded(boolean)} + */ + public SecP521R1Point(ECCurve curve, ECFieldElement x, ECFieldElement y, boolean withCompression) + { + super(curve, x, y); + + if ((x == null) != (y == null)) + { + throw new IllegalArgumentException("Exactly one of the field elements is null"); + } + + this.withCompression = withCompression; + } + + SecP521R1Point(ECCurve curve, ECFieldElement x, ECFieldElement y, ECFieldElement[] zs, boolean withCompression) + { + super(curve, x, y, zs); + + this.withCompression = withCompression; + } + + protected ECPoint detach() + { + return new SecP521R1Point(null, getAffineXCoord(), getAffineYCoord()); + } + + public ECPoint add(ECPoint b) + { + if (this.isInfinity()) + { + return b; + } + if (b.isInfinity()) + { + return this; + } + if (this == b) + { + return twice(); + } + + ECCurve curve = this.getCurve(); + + SecP521R1FieldElement X1 = (SecP521R1FieldElement)this.x, Y1 = (SecP521R1FieldElement)this.y; + SecP521R1FieldElement X2 = (SecP521R1FieldElement)b.getXCoord(), Y2 = (SecP521R1FieldElement)b.getYCoord(); + + SecP521R1FieldElement Z1 = (SecP521R1FieldElement)this.zs[0]; + SecP521R1FieldElement Z2 = (SecP521R1FieldElement)b.getZCoord(0); + + int[] t1 = Nat.create(17); + int[] t2 = Nat.create(17); + int[] t3 = Nat.create(17); + int[] t4 = Nat.create(17); + + boolean Z1IsOne = Z1.isOne(); + int[] U2, S2; + if (Z1IsOne) + { + U2 = X2.x; + S2 = Y2.x; + } + else + { + S2 = t3; + SecP521R1Field.square(Z1.x, S2); + + U2 = t2; + SecP521R1Field.multiply(S2, X2.x, U2); + + SecP521R1Field.multiply(S2, Z1.x, S2); + SecP521R1Field.multiply(S2, Y2.x, S2); + } + + boolean Z2IsOne = Z2.isOne(); + int[] U1, S1; + if (Z2IsOne) + { + U1 = X1.x; + S1 = Y1.x; + } + else + { + S1 = t4; + SecP521R1Field.square(Z2.x, S1); + + U1 = t1; + SecP521R1Field.multiply(S1, X1.x, U1); + + SecP521R1Field.multiply(S1, Z2.x, S1); + SecP521R1Field.multiply(S1, Y1.x, S1); + } + + int[] H = Nat.create(17); + SecP521R1Field.subtract(U1, U2, H); + + int[] R = t2; + SecP521R1Field.subtract(S1, S2, R); + + // Check if b == this or b == -this + if (Nat.isZero(17, H)) + { + if (Nat.isZero(17, R)) + { + // this == b, i.e. this must be doubled + return this.twice(); + } + + // this == -b, i.e. the result is the point at infinity + return curve.getInfinity(); + } + + int[] HSquared = t3; + SecP521R1Field.square(H, HSquared); + + int[] G = Nat.create(17); + SecP521R1Field.multiply(HSquared, H, G); + + int[] V = t3; + SecP521R1Field.multiply(HSquared, U1, V); + + SecP521R1Field.multiply(S1, G, t1); + + SecP521R1FieldElement X3 = new SecP521R1FieldElement(t4); + SecP521R1Field.square(R, X3.x); + SecP521R1Field.add(X3.x, G, X3.x); + SecP521R1Field.subtract(X3.x, V, X3.x); + SecP521R1Field.subtract(X3.x, V, X3.x); + + SecP521R1FieldElement Y3 = new SecP521R1FieldElement(G); + SecP521R1Field.subtract(V, X3.x, Y3.x); + SecP521R1Field.multiply(Y3.x, R, t2); + SecP521R1Field.subtract(t2, t1, Y3.x); + + SecP521R1FieldElement Z3 = new SecP521R1FieldElement(H); + if (!Z1IsOne) + { + SecP521R1Field.multiply(Z3.x, Z1.x, Z3.x); + } + if (!Z2IsOne) + { + SecP521R1Field.multiply(Z3.x, Z2.x, Z3.x); + } + + ECFieldElement[] zs = new ECFieldElement[]{ Z3 }; + + return new SecP521R1Point(curve, X3, Y3, zs, this.withCompression); + } + + public ECPoint twice() + { + if (this.isInfinity()) + { + return this; + } + + ECCurve curve = this.getCurve(); + + SecP521R1FieldElement Y1 = (SecP521R1FieldElement)this.y; + if (Y1.isZero()) + { + return curve.getInfinity(); + } + + SecP521R1FieldElement X1 = (SecP521R1FieldElement)this.x, Z1 = (SecP521R1FieldElement)this.zs[0]; + + int[] t1 = Nat.create(17); + int[] t2 = Nat.create(17); + + int[] Y1Squared = Nat.create(17); + SecP521R1Field.square(Y1.x, Y1Squared); + + int[] T = Nat.create(17); + SecP521R1Field.square(Y1Squared, T); + + boolean Z1IsOne = Z1.isOne(); + + int[] Z1Squared = Z1.x; + if (!Z1IsOne) + { + Z1Squared = t2; + SecP521R1Field.square(Z1.x, Z1Squared); + } + + SecP521R1Field.subtract(X1.x, Z1Squared, t1); + + int[] M = t2; + SecP521R1Field.add(X1.x, Z1Squared, M); + SecP521R1Field.multiply(M, t1, M); + Nat.addBothTo(17, M, M, M); + SecP521R1Field.reduce23(M); + + int[] S = Y1Squared; + SecP521R1Field.multiply(Y1Squared, X1.x, S); + Nat.shiftUpBits(17, S, 2, 0); + SecP521R1Field.reduce23(S); + + Nat.shiftUpBits(17, T, 3, 0, t1); + SecP521R1Field.reduce23(t1); + + SecP521R1FieldElement X3 = new SecP521R1FieldElement(T); + SecP521R1Field.square(M, X3.x); + SecP521R1Field.subtract(X3.x, S, X3.x); + SecP521R1Field.subtract(X3.x, S, X3.x); + + SecP521R1FieldElement Y3 = new SecP521R1FieldElement(S); + SecP521R1Field.subtract(S, X3.x, Y3.x); + SecP521R1Field.multiply(Y3.x, M, Y3.x); + SecP521R1Field.subtract(Y3.x, t1, Y3.x); + + SecP521R1FieldElement Z3 = new SecP521R1FieldElement(M); + SecP521R1Field.twice(Y1.x, Z3.x); + if (!Z1IsOne) + { + SecP521R1Field.multiply(Z3.x, Z1.x, Z3.x); + } + + return new SecP521R1Point(curve, X3, Y3, new ECFieldElement[]{ Z3 }, this.withCompression); + } + + public ECPoint twicePlus(ECPoint b) + { + if (this == b) + { + return threeTimes(); + } + if (this.isInfinity()) + { + return b; + } + if (b.isInfinity()) + { + return twice(); + } + + ECFieldElement Y1 = this.y; + if (Y1.isZero()) + { + return b; + } + + return twice().add(b); + } + + public ECPoint threeTimes() + { + if (this.isInfinity() || this.y.isZero()) + { + return this; + } + + // NOTE: Be careful about recursions between twicePlus and threeTimes + return twice().add(this); + } + + protected ECFieldElement two(ECFieldElement x) + { + return x.add(x); + } + + protected ECFieldElement three(ECFieldElement x) + { + return two(x).add(x); + } + + protected ECFieldElement four(ECFieldElement x) + { + return two(two(x)); + } + + protected ECFieldElement eight(ECFieldElement x) + { + return four(two(x)); + } + + protected ECFieldElement doubleProductFromSquares(ECFieldElement a, ECFieldElement b, + ECFieldElement aSquared, ECFieldElement bSquared) + { + /* + * NOTE: If squaring in the field is faster than multiplication, then this is a quicker + * way to calculate 2.A.B, if A^2 and B^2 are already known. + */ + return a.add(b).square().subtract(aSquared).subtract(bSquared); + } + + public ECPoint negate() + { + if (this.isInfinity()) + { + return this; + } + + return new SecP521R1Point(curve, this.x, this.y.negate(), this.zs, this.withCompression); + } +} |