diff options
Diffstat (limited to 'bcprov/src/main/java/org/bouncycastle/math/ec')
17 files changed, 1580 insertions, 0 deletions
diff --git a/bcprov/src/main/java/org/bouncycastle/math/ec/DoubleAddMultiplier.java b/bcprov/src/main/java/org/bouncycastle/math/ec/DoubleAddMultiplier.java new file mode 100644 index 0000000..aae2e00 --- /dev/null +++ b/bcprov/src/main/java/org/bouncycastle/math/ec/DoubleAddMultiplier.java @@ -0,0 +1,24 @@ +package org.bouncycastle.math.ec; + +import java.math.BigInteger; + +public class DoubleAddMultiplier extends AbstractECMultiplier +{ + /** + * Joye's double-add algorithm. + */ + protected ECPoint multiplyPositive(ECPoint p, BigInteger k) + { + ECPoint[] R = new ECPoint[]{ p.getCurve().getInfinity(), p }; + + int n = k.bitLength(); + for (int i = 0; i < n; ++i) + { + int b = k.testBit(i) ? 1 : 0; + int bp = 1 - b; + R[bp] = R[bp].twicePlus(R[b]); + } + + return R[0]; + } +} diff --git a/bcprov/src/main/java/org/bouncycastle/math/ec/MixedNafR2LMultiplier.java b/bcprov/src/main/java/org/bouncycastle/math/ec/MixedNafR2LMultiplier.java new file mode 100644 index 0000000..6d5fe92 --- /dev/null +++ b/bcprov/src/main/java/org/bouncycastle/math/ec/MixedNafR2LMultiplier.java @@ -0,0 +1,77 @@ +package org.bouncycastle.math.ec; + +import java.math.BigInteger; + +/** + * Class implementing the NAF (Non-Adjacent Form) multiplication algorithm (right-to-left) using + * mixed coordinates. + */ +public class MixedNafR2LMultiplier extends AbstractECMultiplier +{ + protected int additionCoord, doublingCoord; + + /** + * By default, addition will be done in Jacobian coordinates, and doubling will be done in + * Modified Jacobian coordinates (independent of the original coordinate system of each point). + */ + public MixedNafR2LMultiplier() + { + this(ECCurve.COORD_JACOBIAN, ECCurve.COORD_JACOBIAN_MODIFIED); + } + + public MixedNafR2LMultiplier(int additionCoord, int doublingCoord) + { + this.additionCoord = additionCoord; + this.doublingCoord = doublingCoord; + } + + protected ECPoint multiplyPositive(ECPoint p, BigInteger k) + { + ECCurve curveOrig = p.getCurve(); + + ECCurve curveAdd = configureCurve(curveOrig, additionCoord); + ECCurve curveDouble = configureCurve(curveOrig, doublingCoord); + + int[] naf = WNafUtil.generateCompactNaf(k); + + ECPoint Ra = curveAdd.getInfinity(); + ECPoint Td = curveDouble.importPoint(p); + + int zeroes = 0; + for (int i = 0; i < naf.length; ++i) + { + int ni = naf[i]; + int digit = ni >> 16; + zeroes += ni & 0xFFFF; + + Td = Td.timesPow2(zeroes); + + ECPoint Tj = curveAdd.importPoint(Td); + if (digit < 0) + { + Tj = Tj.negate(); + } + + Ra = Ra.add(Tj); + + zeroes = 1; + } + + return curveOrig.importPoint(Ra); + } + + protected ECCurve configureCurve(ECCurve c, int coord) + { + if (c.getCoordinateSystem() == coord) + { + return c; + } + + if (!c.supportsCoordinateSystem(coord)) + { + throw new IllegalArgumentException("Coordinate system " + coord + " not supported by this curve"); + } + + return c.configure().setCoordinateSystem(coord).create(); + } +} diff --git a/bcprov/src/main/java/org/bouncycastle/math/ec/MontgomeryLadderMultiplier.java b/bcprov/src/main/java/org/bouncycastle/math/ec/MontgomeryLadderMultiplier.java new file mode 100644 index 0000000..cd969b5 --- /dev/null +++ b/bcprov/src/main/java/org/bouncycastle/math/ec/MontgomeryLadderMultiplier.java @@ -0,0 +1,25 @@ +package org.bouncycastle.math.ec; + +import java.math.BigInteger; + +public class MontgomeryLadderMultiplier extends AbstractECMultiplier +{ + /** + * Montgomery ladder. + */ + protected ECPoint multiplyPositive(ECPoint p, BigInteger k) + { + ECPoint[] R = new ECPoint[]{ p.getCurve().getInfinity(), p }; + + int n = k.bitLength(); + int i = n; + while (--i >= 0) + { + int b = k.testBit(i) ? 1 : 0; + int bp = 1 - b; + R[bp] = R[bp].add(R[b]); + R[b] = R[b].twice(); + } + return R[0]; + } +} diff --git a/bcprov/src/main/java/org/bouncycastle/math/ec/NafL2RMultiplier.java b/bcprov/src/main/java/org/bouncycastle/math/ec/NafL2RMultiplier.java new file mode 100644 index 0000000..91d91d1 --- /dev/null +++ b/bcprov/src/main/java/org/bouncycastle/math/ec/NafL2RMultiplier.java @@ -0,0 +1,30 @@ +package org.bouncycastle.math.ec; + +import java.math.BigInteger; + +/** + * Class implementing the NAF (Non-Adjacent Form) multiplication algorithm (left-to-right). + */ +public class NafL2RMultiplier extends AbstractECMultiplier +{ + protected ECPoint multiplyPositive(ECPoint p, BigInteger k) + { + int[] naf = WNafUtil.generateCompactNaf(k); + + ECPoint addP = p.normalize(), subP = addP.negate(); + + ECPoint R = p.getCurve().getInfinity(); + + int i = naf.length; + while (--i >= 0) + { + int ni = naf[i]; + int digit = ni >> 16, zeroes = ni & 0xFFFF; + + R = R.twicePlus(digit < 0 ? subP : addP); + R = R.timesPow2(zeroes); + } + + return R; + } +} diff --git a/bcprov/src/main/java/org/bouncycastle/math/ec/NafR2LMultiplier.java b/bcprov/src/main/java/org/bouncycastle/math/ec/NafR2LMultiplier.java new file mode 100644 index 0000000..aed2336 --- /dev/null +++ b/bcprov/src/main/java/org/bouncycastle/math/ec/NafR2LMultiplier.java @@ -0,0 +1,31 @@ +package org.bouncycastle.math.ec; + +import java.math.BigInteger; + +/** + * Class implementing the NAF (Non-Adjacent Form) multiplication algorithm (right-to-left). + */ +public class NafR2LMultiplier extends AbstractECMultiplier +{ + protected ECPoint multiplyPositive(ECPoint p, BigInteger k) + { + int[] naf = WNafUtil.generateCompactNaf(k); + + ECPoint R0 = p.getCurve().getInfinity(), R1 = p; + + int zeroes = 0; + for (int i = 0; i < naf.length; ++i) + { + int ni = naf[i]; + int digit = ni >> 16; + zeroes += ni & 0xFFFF; + + R1 = R1.timesPow2(zeroes); + R0 = R0.add(digit < 0 ? R1.negate() : R1); + + zeroes = 1; + } + + return R0; + } +} diff --git a/bcprov/src/main/java/org/bouncycastle/math/ec/ReferenceMultiplier.java b/bcprov/src/main/java/org/bouncycastle/math/ec/ReferenceMultiplier.java new file mode 100644 index 0000000..107e193 --- /dev/null +++ b/bcprov/src/main/java/org/bouncycastle/math/ec/ReferenceMultiplier.java @@ -0,0 +1,11 @@ +package org.bouncycastle.math.ec; + +import java.math.BigInteger; + +public class ReferenceMultiplier extends AbstractECMultiplier +{ + protected ECPoint multiplyPositive(ECPoint p, BigInteger k) + { + return ECAlgorithms.referenceMultiply(p, k); + } +} diff --git a/bcprov/src/main/java/org/bouncycastle/math/ec/ScaleYPointMap.java b/bcprov/src/main/java/org/bouncycastle/math/ec/ScaleYPointMap.java new file mode 100644 index 0000000..a7a8790 --- /dev/null +++ b/bcprov/src/main/java/org/bouncycastle/math/ec/ScaleYPointMap.java @@ -0,0 +1,16 @@ +package org.bouncycastle.math.ec; + +public class ScaleYPointMap implements ECPointMap +{ + protected final ECFieldElement scale; + + public ScaleYPointMap(ECFieldElement scale) + { + this.scale = scale; + } + + public ECPoint map(ECPoint p) + { + return p.scaleY(scale); + } +} diff --git a/bcprov/src/main/java/org/bouncycastle/math/ec/ZSignedDigitL2RMultiplier.java b/bcprov/src/main/java/org/bouncycastle/math/ec/ZSignedDigitL2RMultiplier.java new file mode 100644 index 0000000..b478dc7 --- /dev/null +++ b/bcprov/src/main/java/org/bouncycastle/math/ec/ZSignedDigitL2RMultiplier.java @@ -0,0 +1,29 @@ +package org.bouncycastle.math.ec; + +import java.math.BigInteger; + +public class ZSignedDigitL2RMultiplier extends AbstractECMultiplier +{ + /** + * 'Zeroless' Signed Digit Left-to-Right. + */ + protected ECPoint multiplyPositive(ECPoint p, BigInteger k) + { + ECPoint addP = p.normalize(), subP = addP.negate(); + + ECPoint R0 = addP; + + int n = k.bitLength(); + int s = k.getLowestSetBit(); + + int i = n; + while (--i > s) + { + R0 = R0.twicePlus(k.testBit(i) ? addP : subP); + } + + R0 = R0.timesPow2(s); + + return R0; + } +} diff --git a/bcprov/src/main/java/org/bouncycastle/math/ec/ZSignedDigitR2LMultiplier.java b/bcprov/src/main/java/org/bouncycastle/math/ec/ZSignedDigitR2LMultiplier.java new file mode 100644 index 0000000..baa702f --- /dev/null +++ b/bcprov/src/main/java/org/bouncycastle/math/ec/ZSignedDigitR2LMultiplier.java @@ -0,0 +1,30 @@ +package org.bouncycastle.math.ec; + +import java.math.BigInteger; + +public class ZSignedDigitR2LMultiplier extends AbstractECMultiplier +{ + /** + * 'Zeroless' Signed Digit Right-to-Left. + */ + protected ECPoint multiplyPositive(ECPoint p, BigInteger k) + { + ECPoint R0 = p.getCurve().getInfinity(), R1 = p; + + int n = k.bitLength(); + int s = k.getLowestSetBit(); + + R1 = R1.timesPow2(s); + + int i = s; + while (++i < n) + { + R0 = R0.add(k.testBit(i) ? R1 : R1.negate()); + R1 = R1.twice(); + } + + R0 = R0.add(R1); + + return R0; + } +} diff --git a/bcprov/src/main/java/org/bouncycastle/math/ec/custom/djb/Curve25519.java b/bcprov/src/main/java/org/bouncycastle/math/ec/custom/djb/Curve25519.java new file mode 100644 index 0000000..e7839ce --- /dev/null +++ b/bcprov/src/main/java/org/bouncycastle/math/ec/custom/djb/Curve25519.java @@ -0,0 +1,80 @@ +package org.bouncycastle.math.ec.custom.djb; + +import java.math.BigInteger; + +import org.bouncycastle.math.ec.ECCurve; +import org.bouncycastle.math.ec.ECFieldElement; +import org.bouncycastle.math.ec.ECPoint; +import org.bouncycastle.math.raw.Nat256; +import org.bouncycastle.util.encoders.Hex; + +public class Curve25519 extends ECCurve.AbstractFp +{ + public static final BigInteger q = Nat256.toBigInteger(Curve25519Field.P); + + private static final int Curve25519_DEFAULT_COORDS = COORD_JACOBIAN_MODIFIED; + + protected Curve25519Point infinity; + + public Curve25519() + { + super(q); + + this.infinity = new Curve25519Point(this, null, null); + + this.a = fromBigInteger(new BigInteger(1, + Hex.decode("2AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA984914A144"))); + this.b = fromBigInteger(new BigInteger(1, + Hex.decode("7B425ED097B425ED097B425ED097B425ED097B425ED097B4260B5E9C7710C864"))); + this.order = new BigInteger(1, Hex.decode("1000000000000000000000000000000014DEF9DEA2F79CD65812631A5CF5D3ED")); + this.cofactor = BigInteger.valueOf(8); + + this.coord = Curve25519_DEFAULT_COORDS; + } + + protected ECCurve cloneCurve() + { + return new Curve25519(); + } + + public boolean supportsCoordinateSystem(int coord) + { + switch (coord) + { + case COORD_JACOBIAN_MODIFIED: + return true; + default: + return false; + } + } + + public BigInteger getQ() + { + return q; + } + + public int getFieldSize() + { + return q.bitLength(); + } + + public ECFieldElement fromBigInteger(BigInteger x) + { + return new Curve25519FieldElement(x); + } + + protected ECPoint createRawPoint(ECFieldElement x, ECFieldElement y, boolean withCompression) + { + return new Curve25519Point(this, x, y, withCompression); + } + + protected ECPoint createRawPoint(ECFieldElement x, ECFieldElement y, ECFieldElement[] zs, boolean withCompression) + { + return new Curve25519Point(this, x, y, zs, withCompression); + } + + public ECPoint getInfinity() + { + return infinity; + } +} diff --git a/bcprov/src/main/java/org/bouncycastle/math/ec/custom/djb/Curve25519Field.java b/bcprov/src/main/java/org/bouncycastle/math/ec/custom/djb/Curve25519Field.java new file mode 100644 index 0000000..2e8e335 --- /dev/null +++ b/bcprov/src/main/java/org/bouncycastle/math/ec/custom/djb/Curve25519Field.java @@ -0,0 +1,254 @@ +package org.bouncycastle.math.ec.custom.djb; + +import java.math.BigInteger; + +import org.bouncycastle.math.raw.Nat; +import org.bouncycastle.math.raw.Nat256; + +public class Curve25519Field +{ + private static final long M = 0xFFFFFFFFL; + + // 2^255 - 2^4 - 2^1 - 1 + static final int[] P = new int[]{ 0xFFFFFFED, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, + 0xFFFFFFFF, 0x7FFFFFFF }; + private static final int P7 = 0x7FFFFFFF; + private static final int[] PExt = new int[]{ 0x00000169, 0x00000000, 0x00000000, 0x00000000, 0x00000000, + 0x00000000, 0x00000000, 0x00000000, 0xFFFFFFED, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, + 0xFFFFFFFF, 0x3FFFFFFF }; + private static final int PInv = 0x13; + + public static void add(int[] x, int[] y, int[] z) + { + Nat256.add(x, y, z); + if (Nat256.gte(z, P)) + { + subPFrom(z); + } + } + + public static void addExt(int[] xx, int[] yy, int[] zz) + { + Nat.add(16, xx, yy, zz); + if (Nat.gte(16, zz, PExt)) + { + subPExtFrom(zz); + } + } + + public static void addOne(int[] x, int[] z) + { + Nat.inc(8, x, z); + if (Nat256.gte(z, P)) + { + subPFrom(z); + } + } + + public static int[] fromBigInteger(BigInteger x) + { + int[] z = Nat256.fromBigInteger(x); + while (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 + { + Nat256.add(x, P, z); + Nat.shiftDownBit(8, z, 0); + } + } + + 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) + { + Nat256.mulAddTo(x, y, zz); + if (Nat.gte(16, zz, PExt)) + { + subPExtFrom(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) + { +// assert xx[15] >>> 30 == 0; + + int xx07 = xx[7]; + Nat.shiftUpBit(8, xx, 8, xx07, z, 0); + int c = Nat256.mulByWordAddTo(PInv, xx, z) << 1; + int z7 = z[7]; + c += (z7 >>> 31) - (xx07 >>> 31); + z7 &= P7; + z7 += Nat.addWordTo(7, c * PInv, z); + z[7] = z7; + if (Nat256.gte(z, P)) + { + subPFrom(z); + } + } + + public static void reduce27(int x, int[] z) + { +// assert x >>> 26 == 0; + + int z7 = z[7]; + int c = (x << 1 | z7 >>> 31); + z7 &= P7; + z7 += Nat.addWordTo(7, c * PInv, z); + z[7] = z7; + if (Nat256.gte(z, P)) + { + subPFrom(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) + { + addPTo(z); + } + } + + public static void subtractExt(int[] xx, int[] yy, int[] zz) + { + int c = Nat.sub(16, xx, yy, zz); + if (c != 0) + { + addPExtTo(zz); + } + } + + public static void twice(int[] x, int[] z) + { + Nat.shiftUpBit(8, x, 0, z); + if (Nat256.gte(z, P)) + { + subPFrom(z); + } + } + + private static int addPTo(int[] z) + { + long c = (z[0] & M) - PInv; + z[0] = (int)c; + c >>= 32; + if (c != 0) + { + c = Nat.decAt(7, z, 1); + } + c += (z[7] & M) + ((P7 + 1) & M); + z[7] = (int)c; + c >>= 32; + return (int)c; + } + + private static int addPExtTo(int[] zz) + { + long c = (zz[0] & M) + (PExt[0] & M); + zz[0] = (int)c; + c >>= 32; + if (c != 0) + { + c = Nat.incAt(8, zz, 1); + } + c += (zz[8] & M) - PInv; + zz[8] = (int)c; + c >>= 32; + if (c != 0) + { + c = Nat.decAt(15, zz, 9); + } + c += (zz[15] & M) + ((PExt[15] + 1) & M); + zz[15] = (int)c; + c >>= 32; + return (int)c; + } + + private static int subPFrom(int[] z) + { + long c = (z[0] & M) + PInv; + z[0] = (int)c; + c >>= 32; + if (c != 0) + { + c = Nat.incAt(7, z, 1); + } + c += (z[7] & M) - ((P7 + 1) & M); + z[7] = (int)c; + c >>= 32; + return (int)c; + } + + private static int subPExtFrom(int[] zz) + { + long c = (zz[0] & M) - (PExt[0] & M); + zz[0] = (int)c; + c >>= 32; + if (c != 0) + { + c = Nat.decAt(8, zz, 1); + } + c += (zz[8] & M) + PInv; + zz[8] = (int)c; + c >>= 32; + if (c != 0) + { + c = Nat.incAt(15, zz, 9); + } + c += (zz[15] & M) - ((PExt[15] + 1) & M); + zz[15] = (int)c; + c >>= 32; + return (int)c; + } +} diff --git a/bcprov/src/main/java/org/bouncycastle/math/ec/custom/djb/Curve25519FieldElement.java b/bcprov/src/main/java/org/bouncycastle/math/ec/custom/djb/Curve25519FieldElement.java new file mode 100644 index 0000000..010b6f5 --- /dev/null +++ b/bcprov/src/main/java/org/bouncycastle/math/ec/custom/djb/Curve25519FieldElement.java @@ -0,0 +1,234 @@ +package org.bouncycastle.math.ec.custom.djb; + +import java.math.BigInteger; + +import org.bouncycastle.math.ec.ECFieldElement; +import org.bouncycastle.math.raw.Mod; +import org.bouncycastle.math.raw.Nat256; +import org.bouncycastle.util.Arrays; + +public class Curve25519FieldElement extends ECFieldElement +{ + public static final BigInteger Q = Curve25519.q; + + // Calculated as ECConstants.TWO.modPow(Q.shiftRight(2), Q) + private static final int[] PRECOMP_POW2 = new int[]{ 0x4a0ea0b0, 0xc4ee1b27, 0xad2fe478, 0x2f431806, + 0x3dfbd7a7, 0x2b4d0099, 0x4fc1df0b, 0x2b832480 }; + + protected int[] x; + + public Curve25519FieldElement(BigInteger x) + { + if (x == null || x.signum() < 0 || x.compareTo(Q) >= 0) + { + throw new IllegalArgumentException("x value invalid for Curve25519FieldElement"); + } + + this.x = Curve25519Field.fromBigInteger(x); + } + + public Curve25519FieldElement() + { + this.x = Nat256.create(); + } + + protected Curve25519FieldElement(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 "Curve25519Field"; + } + + public int getFieldSize() + { + return Q.bitLength(); + } + + public ECFieldElement add(ECFieldElement b) + { + int[] z = Nat256.create(); + Curve25519Field.add(x, ((Curve25519FieldElement)b).x, z); + return new Curve25519FieldElement(z); + } + + public ECFieldElement addOne() + { + int[] z = Nat256.create(); + Curve25519Field.addOne(x, z); + return new Curve25519FieldElement(z); + } + + public ECFieldElement subtract(ECFieldElement b) + { + int[] z = Nat256.create(); + Curve25519Field.subtract(x, ((Curve25519FieldElement)b).x, z); + return new Curve25519FieldElement(z); + } + + public ECFieldElement multiply(ECFieldElement b) + { + int[] z = Nat256.create(); + Curve25519Field.multiply(x, ((Curve25519FieldElement)b).x, z); + return new Curve25519FieldElement(z); + } + + public ECFieldElement divide(ECFieldElement b) + { +// return multiply(b.invert()); + int[] z = Nat256.create(); + Mod.invert(Curve25519Field.P, ((Curve25519FieldElement)b).x, z); + Curve25519Field.multiply(z, x, z); + return new Curve25519FieldElement(z); + } + + public ECFieldElement negate() + { + int[] z = Nat256.create(); + Curve25519Field.negate(x, z); + return new Curve25519FieldElement(z); + } + + public ECFieldElement square() + { + int[] z = Nat256.create(); + Curve25519Field.square(x, z); + return new Curve25519FieldElement(z); + } + + public ECFieldElement invert() + { +// return new Curve25519FieldElement(toBigInteger().modInverse(Q)); + int[] z = Nat256.create(); + Mod.invert(Curve25519Field.P, x, z); + return new Curve25519FieldElement(z); + } + + /** + * 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^252 - 2^1 (i.e. m + 1) + * + * Breaking up the exponent's binary representation into "repunits", we get: + * { 251 1s } { 1 0s } + * + * Therefore we need an addition chain containing 251 (the lengths of the repunits) + * We use: 1, 2, 3, 4, 7, 11, 15, 30, 60, 120, 131, [251] + */ + + int[] x1 = this.x; + if (Nat256.isZero(x1) || Nat256.isOne(x1)) + { + return this; + } + + int[] x2 = Nat256.create(); + Curve25519Field.square(x1, x2); + Curve25519Field.multiply(x2, x1, x2); + int[] x3 = x2; + Curve25519Field.square(x2, x3); + Curve25519Field.multiply(x3, x1, x3); + int[] x4 = Nat256.create(); + Curve25519Field.square(x3, x4); + Curve25519Field.multiply(x4, x1, x4); + int[] x7 = Nat256.create(); + Curve25519Field.squareN(x4, 3, x7); + Curve25519Field.multiply(x7, x3, x7); + int[] x11 = x3; + Curve25519Field.squareN(x7, 4, x11); + Curve25519Field.multiply(x11, x4, x11); + int[] x15 = x7; + Curve25519Field.squareN(x11, 4, x15); + Curve25519Field.multiply(x15, x4, x15); + int[] x30 = x4; + Curve25519Field.squareN(x15, 15, x30); + Curve25519Field.multiply(x30, x15, x30); + int[] x60 = x15; + Curve25519Field.squareN(x30, 30, x60); + Curve25519Field.multiply(x60, x30, x60); + int[] x120 = x30; + Curve25519Field.squareN(x60, 60, x120); + Curve25519Field.multiply(x120, x60, x120); + int[] x131 = x60; + Curve25519Field.squareN(x120, 11, x131); + Curve25519Field.multiply(x131, x11, x131); + int[] x251 = x11; + Curve25519Field.squareN(x131, 120, x251); + Curve25519Field.multiply(x251, x120, x251); + + int[] t1 = x251; + Curve25519Field.square(t1, t1); + + int[] t2 = x120; + Curve25519Field.square(t1, t2); + + if (Nat256.eq(x1, t2)) + { + return new Curve25519FieldElement(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 + */ + Curve25519Field.multiply(t1, PRECOMP_POW2, t1); + + Curve25519Field.square(t1, t2); + + if (Nat256.eq(x1, t2)) + { + return new Curve25519FieldElement(t1); + } + + return null; + } + + public boolean equals(Object other) + { + if (other == this) + { + return true; + } + + if (!(other instanceof Curve25519FieldElement)) + { + return false; + } + + Curve25519FieldElement o = (Curve25519FieldElement)other; + return Nat256.eq(x, o.x); + } + + public int hashCode() + { + return Q.hashCode() ^ Arrays.hashCode(x, 0, 8); + } +} diff --git a/bcprov/src/main/java/org/bouncycastle/math/ec/custom/djb/Curve25519Point.java b/bcprov/src/main/java/org/bouncycastle/math/ec/custom/djb/Curve25519Point.java new file mode 100644 index 0000000..b2700e3 --- /dev/null +++ b/bcprov/src/main/java/org/bouncycastle/math/ec/custom/djb/Curve25519Point.java @@ -0,0 +1,348 @@ +package org.bouncycastle.math.ec.custom.djb; + +import org.bouncycastle.math.ec.ECCurve; +import org.bouncycastle.math.ec.ECFieldElement; +import org.bouncycastle.math.ec.ECPoint; +import org.bouncycastle.math.raw.Nat256; + +public class Curve25519Point 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 Curve25519Point(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 Curve25519Point(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; + } + + Curve25519Point(ECCurve curve, ECFieldElement x, ECFieldElement y, ECFieldElement[] zs, boolean withCompression) + { + super(curve, x, y, zs); + + this.withCompression = withCompression; + } + + protected ECPoint detach() + { + return new Curve25519Point(null, getAffineXCoord(), getAffineYCoord()); + } + + public ECFieldElement getZCoord(int index) + { + if (index == 1) + { + return getJacobianModifiedW(); + } + + return super.getZCoord(index); + } + + public ECPoint add(ECPoint b) + { + if (this.isInfinity()) + { + return b; + } + if (b.isInfinity()) + { + return this; + } + if (this == b) + { + return twice(); + } + + ECCurve curve = this.getCurve(); + + Curve25519FieldElement X1 = (Curve25519FieldElement)this.x, Y1 = (Curve25519FieldElement)this.y, + Z1 = (Curve25519FieldElement)this.zs[0]; + Curve25519FieldElement X2 = (Curve25519FieldElement)b.getXCoord(), Y2 = (Curve25519FieldElement)b.getYCoord(), + Z2 = (Curve25519FieldElement)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; + Curve25519Field.square(Z1.x, S2); + + U2 = t2; + Curve25519Field.multiply(S2, X2.x, U2); + + Curve25519Field.multiply(S2, Z1.x, S2); + Curve25519Field.multiply(S2, Y2.x, S2); + } + + boolean Z2IsOne = Z2.isOne(); + int[] U1, S1; + if (Z2IsOne) + { + U1 = X1.x; + S1 = Y1.x; + } + else + { + S1 = t4; + Curve25519Field.square(Z2.x, S1); + + U1 = tt1; + Curve25519Field.multiply(S1, X1.x, U1); + + Curve25519Field.multiply(S1, Z2.x, S1); + Curve25519Field.multiply(S1, Y1.x, S1); + } + + int[] H = Nat256.create(); + Curve25519Field.subtract(U1, U2, H); + + int[] R = t2; + Curve25519Field.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 = Nat256.create(); + Curve25519Field.square(H, HSquared); + + int[] G = Nat256.create(); + Curve25519Field.multiply(HSquared, H, G); + + int[] V = t3; + Curve25519Field.multiply(HSquared, U1, V); + + Curve25519Field.negate(G, G); + Nat256.mul(S1, G, tt1); + + c = Nat256.addBothTo(V, V, G); + Curve25519Field.reduce27(c, G); + + Curve25519FieldElement X3 = new Curve25519FieldElement(t4); + Curve25519Field.square(R, X3.x); + Curve25519Field.subtract(X3.x, G, X3.x); + + Curve25519FieldElement Y3 = new Curve25519FieldElement(G); + Curve25519Field.subtract(V, X3.x, Y3.x); + Curve25519Field.multiplyAddToExt(Y3.x, R, tt1); + Curve25519Field.reduce(tt1, Y3.x); + + Curve25519FieldElement Z3 = new Curve25519FieldElement(H); + if (!Z1IsOne) + { + Curve25519Field.multiply(Z3.x, Z1.x, Z3.x); + } + if (!Z2IsOne) + { + Curve25519Field.multiply(Z3.x, Z2.x, Z3.x); + } + + int[] Z3Squared = (Z1IsOne && Z2IsOne) ? HSquared : null; + + // TODO If the result will only be used in a subsequent addition, we don't need W3 + Curve25519FieldElement W3 = calculateJacobianModifiedW((Curve25519FieldElement)Z3, Z3Squared); + + ECFieldElement[] zs = new ECFieldElement[]{ Z3, W3 }; + + return new Curve25519Point(curve, X3, Y3, zs, this.withCompression); + } + + public ECPoint twice() + { + if (this.isInfinity()) + { + return this; + } + + ECCurve curve = this.getCurve(); + + ECFieldElement Y1 = this.y; + if (Y1.isZero()) + { + return curve.getInfinity(); + } + + return twiceJacobianModified(true); + } + + 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 twiceJacobianModified(false).add(b); + } + + public ECPoint threeTimes() + { + if (this.isInfinity()) + { + return this; + } + + ECFieldElement Y1 = this.y; + if (Y1.isZero()) + { + return this; + } + + return twiceJacobianModified(false).add(this); + } + + public ECPoint negate() + { + if (this.isInfinity()) + { + return this; + } + + return new Curve25519Point(this.getCurve(), this.x, this.y.negate(), this.zs, this.withCompression); + } + + protected Curve25519FieldElement calculateJacobianModifiedW(Curve25519FieldElement Z, int[] ZSquared) + { + Curve25519FieldElement a4 = (Curve25519FieldElement)this.getCurve().getA(); + if (Z.isOne()) + { + return a4; + } + + Curve25519FieldElement W = new Curve25519FieldElement(); + if (ZSquared == null) + { + ZSquared = W.x; + Curve25519Field.square(Z.x, ZSquared); + } + Curve25519Field.square(ZSquared, W.x); + Curve25519Field.multiply(W.x, a4.x, W.x); + return W; + } + + protected Curve25519FieldElement getJacobianModifiedW() + { + Curve25519FieldElement W = (Curve25519FieldElement)this.zs[1]; + if (W == null) + { + // NOTE: Rarely, twicePlus will result in the need for a lazy W1 calculation here + this.zs[1] = W = calculateJacobianModifiedW((Curve25519FieldElement)this.zs[0], null); + } + return W; + } + + protected Curve25519Point twiceJacobianModified(boolean calculateW) + { + Curve25519FieldElement X1 = (Curve25519FieldElement)this.x, Y1 = (Curve25519FieldElement)this.y, + Z1 = (Curve25519FieldElement)this.zs[0], W1 = getJacobianModifiedW(); + + int c; + + int[] M = Nat256.create(); + Curve25519Field.square(X1.x, M); + c = Nat256.addBothTo(M, M, M); + c += Nat256.addTo(W1.x, M); + Curve25519Field.reduce27(c, M); + + int[] _2Y1 = Nat256.create(); + Curve25519Field.twice(Y1.x, _2Y1); + + int[] _2Y1Squared = Nat256.create(); + Curve25519Field.multiply(_2Y1, Y1.x, _2Y1Squared); + + int[] S = Nat256.create(); + Curve25519Field.multiply(_2Y1Squared, X1.x, S); + Curve25519Field.twice(S, S); + + int[] _8T = Nat256.create(); + Curve25519Field.square(_2Y1Squared, _8T); + Curve25519Field.twice(_8T, _8T); + + Curve25519FieldElement X3 = new Curve25519FieldElement(_2Y1Squared); + Curve25519Field.square(M, X3.x); + Curve25519Field.subtract(X3.x, S, X3.x); + Curve25519Field.subtract(X3.x, S, X3.x); + + Curve25519FieldElement Y3 = new Curve25519FieldElement(S); + Curve25519Field.subtract(S, X3.x, Y3.x); + Curve25519Field.multiply(Y3.x, M, Y3.x); + Curve25519Field.subtract(Y3.x, _8T, Y3.x); + + Curve25519FieldElement Z3 = new Curve25519FieldElement(_2Y1); + if (!Nat256.isOne(Z1.x)) + { + Curve25519Field.multiply(Z3.x, Z1.x, Z3.x); + } + + Curve25519FieldElement W3 = null; + if (calculateW) + { + W3 = new Curve25519FieldElement(_8T); + Curve25519Field.multiply(W3.x, W1.x, W3.x); + Curve25519Field.twice(W3.x, W3.x); + } + + return new Curve25519Point(this.getCurve(), X3, Y3, new ECFieldElement[]{ Z3, W3 }, this.withCompression); + } +} diff --git a/bcprov/src/main/java/org/bouncycastle/math/ec/custom/djb/package.html b/bcprov/src/main/java/org/bouncycastle/math/ec/custom/djb/package.html new file mode 100644 index 0000000..344418b --- /dev/null +++ b/bcprov/src/main/java/org/bouncycastle/math/ec/custom/djb/package.html @@ -0,0 +1,7 @@ +<html> +<body bgcolor="#ffffff"> +Experimental implementation of curve25519. Note that the curve implementation is in the short-Weierstrass form, +which is not the recommended (nor most suitable) approach. In particular, the input/output conventions are not +compliant with standard implementations, and point conversions would be needed to interoperate. +</body> +</html> diff --git a/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/package.html b/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/package.html new file mode 100644 index 0000000..bb2845c --- /dev/null +++ b/bcprov/src/main/java/org/bouncycastle/math/ec/custom/sec/package.html @@ -0,0 +1,6 @@ +<html> +<body bgcolor="#ffffff"> +Custom implementations of (most of) the curves over Fp from the SEC specification. Uses the new "raw" math classes +in place of BigInteger, and includes customized modular reductions taking advantage of the special forms of the primes. +</body> +</html> diff --git a/bcprov/src/main/java/org/bouncycastle/math/ec/package.html b/bcprov/src/main/java/org/bouncycastle/math/ec/package.html new file mode 100644 index 0000000..a02605b --- /dev/null +++ b/bcprov/src/main/java/org/bouncycastle/math/ec/package.html @@ -0,0 +1,5 @@ +<html> +<body bgcolor="#ffffff"> +Math support for Elliptic Curve. +</body> +</html> diff --git a/bcprov/src/main/java/org/bouncycastle/math/ec/tools/DiscoverEndomorphisms.java b/bcprov/src/main/java/org/bouncycastle/math/ec/tools/DiscoverEndomorphisms.java new file mode 100644 index 0000000..4ee2de6 --- /dev/null +++ b/bcprov/src/main/java/org/bouncycastle/math/ec/tools/DiscoverEndomorphisms.java @@ -0,0 +1,373 @@ +package org.bouncycastle.math.ec.tools; + +import java.math.BigInteger; +import java.security.SecureRandom; + +import org.bouncycastle.asn1.x9.ECNamedCurveTable; +import org.bouncycastle.asn1.x9.X9ECParameters; +import org.bouncycastle.math.ec.ECAlgorithms; +import org.bouncycastle.math.ec.ECConstants; +import org.bouncycastle.math.ec.ECCurve; +import org.bouncycastle.math.ec.ECFieldElement; +import org.bouncycastle.math.ec.ECPoint; +import org.bouncycastle.util.BigIntegers; + +public class DiscoverEndomorphisms +{ + private static final int radix = 16; + + public static void main(String[] args) + { + if (args.length < 1) + { + System.err.println("Expected a list of curve names as arguments"); + return; + } + + for (int i = 0; i < args.length; ++i) + { + discoverEndomorphism(args[i]); + } + } + + private static void discoverEndomorphism(String curveName) + { + X9ECParameters x9 = ECNamedCurveTable.getByName(curveName); + if (x9 == null) + { + System.err.println("Unknown curve: " + curveName); + return; + } + + ECCurve c = x9.getCurve(); + if (ECAlgorithms.isFpCurve(c)) + { + BigInteger characteristic = c.getField().getCharacteristic(); + + if (c.getA().isZero() && characteristic.mod(ECConstants.THREE).equals(ECConstants.ONE)) + { + System.out.println("Curve '" + curveName + "' has a 'GLV Type B' endomorphism with these parameters: "); + printGLVTypeBParameters(x9); + } + } + } + + private static void printGLVTypeBParameters(X9ECParameters x9) + { + BigInteger n = x9.getN(); + BigInteger[] v1 = null; + BigInteger[] v2 = null; + + // x^2 + x + 1 = 0 mod n + BigInteger lambda = solveQuadraticEquation(n, ECConstants.ONE, ECConstants.ONE); + + BigInteger[] rt = extEuclidGLV(n, lambda); + v1 = new BigInteger[]{ rt[2], rt[3].negate() }; + v2 = chooseShortest(new BigInteger[]{ rt[0], rt[1].negate() }, new BigInteger[]{ rt[4], rt[5].negate() }); + + /* + * If elements of v2 are not bounded by sqrt(n), then if r1/t1 are relatively prime there + * _may_ yet be a GLV generator, so search for it. See + * "Integer Decomposition for Fast Scalar Multiplication on Elliptic Curves", D. Kim, S. Lim + * (SAC 2002) + */ + if (!isVectorBoundedBySqrt(v2, n) && areRelativelyPrime(v1[0], v1[1])) + { + BigInteger r = v1[0], t = v1[1], s = r.add(t.multiply(lambda)).divide(n); + + BigInteger[] vw = extEuclidBezout(new BigInteger[]{ s.abs(), t.abs() }); + BigInteger v = vw[0], w = vw[1]; + + if (s.signum() < 0) + { + v = v.negate(); + } + if (t.signum() > 0) + { + w = w.negate(); + } + + BigInteger check = s.multiply(v).subtract(t.multiply(w)); + if (!check.equals(ECConstants.ONE)) + { + throw new IllegalStateException(); + } + + BigInteger x = w.multiply(n).subtract(v.multiply(lambda)); + + BigInteger base1 = v.negate(); + BigInteger base2 = x.negate(); + + /* + * We calculate the range(s) conservatively large to avoid messy rounding issues, so + * there may be spurious candidate generators, but we won't miss any. + */ + BigInteger sqrtN = isqrt(n.subtract(ECConstants.ONE)).add(ECConstants.ONE); + + BigInteger[] I1 = calculateRange(base1, sqrtN, t); + BigInteger[] I2 = calculateRange(base2, sqrtN, r); + + BigInteger[] range = intersect(I1, I2); + if (range != null) + { + for (BigInteger alpha = range[0]; alpha.compareTo(range[1]) <= 0; alpha = alpha.add(ECConstants.ONE)) + { + BigInteger[] candidate = new BigInteger[]{ x.add(alpha.multiply(r)), v.add(alpha.multiply(t)) }; + if (isShorter(candidate, v2)) + { + v2 = candidate; + } + } + } + } + + /* + * 'Beta' is a field element of order 3. There are only two such values besides 1; determine which of them + * corresponds to our choice for 'Lambda'. + */ + ECFieldElement beta; + { + ECPoint G = x9.getG().normalize(); + ECPoint mapG = G.multiply(lambda).normalize(); + if (!G.getYCoord().equals(mapG.getYCoord())) + { + throw new IllegalStateException("Derivation of GLV Type B parameters failed unexpectedly"); + } + + BigInteger q = x9.getCurve().getField().getCharacteristic(); + BigInteger e = q.divide(ECConstants.THREE); + + SecureRandom random = new SecureRandom(); + BigInteger b; + do + { + BigInteger r = BigIntegers.createRandomInRange(ECConstants.TWO, q.subtract(ECConstants.TWO), random); + b = r.modPow(e, q); + } + while (b.equals(ECConstants.ONE)); + + beta = x9.getCurve().fromBigInteger(ECConstants.TWO.modPow(e, q)); + + if (!G.getXCoord().multiply(beta).equals(mapG.getXCoord())) + { + beta = beta.square(); + if (!G.getXCoord().multiply(beta).equals(mapG.getXCoord())) + { + throw new IllegalStateException("Derivation of GLV Type B parameters failed unexpectedly"); + } + } + } + + /* + * These parameters are used to avoid division when decomposing the scalar in a GLV point multiplication + */ + BigInteger d = (v1[0].multiply(v2[1])).subtract(v1[1].multiply(v2[0])); + + int bits = n.bitLength() + 16 - (n.bitLength() & 7); + BigInteger g1 = roundQuotient(v2[1].shiftLeft(bits), d); + BigInteger g2 = roundQuotient(v1[1].shiftLeft(bits), d).negate(); + + printProperty("Beta", beta.toBigInteger().toString(radix)); + printProperty("Lambda", lambda.toString(radix)); + printProperty("v1", "{ " + v1[0].toString(radix) + ", " + v1[1].toString(radix) + " }"); + printProperty("v2", "{ " + v2[0].toString(radix) + ", " + v2[1].toString(radix) + " }"); + printProperty("(OPT) g1", g1.toString(radix)); + printProperty("(OPT) g2", g2.toString(radix)); + printProperty("(OPT) bits", Integer.toString(bits)); + } + + private static void printProperty(String name, Object value) + { + StringBuffer sb = new StringBuffer(" "); + sb.append(name); + while (sb.length() < 20) + { + sb.append(' '); + } + sb.append("= "); + sb.append(value.toString()); + System.out.println(sb.toString()); + } + + private static boolean areRelativelyPrime(BigInteger a, BigInteger b) + { + return a.gcd(b).equals(ECConstants.ONE); + } + + private static BigInteger[] calculateRange(BigInteger mid, BigInteger off, BigInteger div) + { + BigInteger i1 = mid.subtract(off).divide(div); + BigInteger i2 = mid.add(off).divide(div); + return order(i1, i2); + } + + private static BigInteger[] extEuclidBezout(BigInteger[] ab) + { + boolean swap = ab[0].compareTo(ab[1]) < 0; + if (swap) + { + swap(ab); + } + + BigInteger r0 = ab[0], r1 = ab[1]; + BigInteger s0 = ECConstants.ONE, s1 = ECConstants.ZERO; + BigInteger t0 = ECConstants.ZERO, t1 = ECConstants.ONE; + + while (r1.compareTo(ECConstants.ONE) > 0) + { + BigInteger[] qr = r0.divideAndRemainder(r1); + BigInteger q = qr[0], r2 = qr[1]; + + BigInteger s2 = s0.subtract(q.multiply(s1)); + BigInteger t2 = t0.subtract(q.multiply(t1)); + + r0 = r1; + r1 = r2; + s0 = s1; + s1 = s2; + t0 = t1; + t1 = t2; + } + + if (r1.signum() <= 0) + { + throw new IllegalStateException(); + } + + BigInteger[] st = new BigInteger[]{ s1, t1 }; + if (swap) + { + swap(st); + } + return st; + } + + private static BigInteger[] extEuclidGLV(BigInteger n, BigInteger lambda) + { + BigInteger r0 = n, r1 = lambda; + // BigInteger s0 = ECConstants.ONE, s1 = ECConstants.ZERO; + BigInteger t0 = ECConstants.ZERO, t1 = ECConstants.ONE; + + for (;;) + { + BigInteger[] qr = r0.divideAndRemainder(r1); + BigInteger q = qr[0], r2 = qr[1]; + + // BigInteger s2 = s0.subtract(q.multiply(s1)); + BigInteger t2 = t0.subtract(q.multiply(t1)); + + if (isLessThanSqrt(r1, n)) + { + return new BigInteger[]{ r0, t0, r1, t1, r2, t2 }; + } + + r0 = r1; + r1 = r2; + // s0 = s1; + // s1 = s2; + t0 = t1; + t1 = t2; + } + } + + private static BigInteger[] chooseShortest(BigInteger[] u, BigInteger[] v) + { + return isShorter(u, v) ? u : v; + } + + private static BigInteger[] intersect(BigInteger[] ab, BigInteger[] cd) + { + BigInteger min = ab[0].max(cd[0]); + BigInteger max = ab[1].min(cd[1]); + if (min.compareTo(max) > 0) + { + return null; + } + return new BigInteger[]{ min, max }; + } + + private static boolean isLessThanSqrt(BigInteger a, BigInteger b) + { + a = a.abs(); + b = b.abs(); + int target = b.bitLength(), maxBits = a.bitLength() * 2, minBits = maxBits - 1; + return minBits <= target && (maxBits < target || a.multiply(a).compareTo(b) < 0); + } + + private static boolean isShorter(BigInteger[] u, BigInteger[] v) + { + BigInteger u1 = u[0].abs(), u2 = u[1].abs(), v1 = v[0].abs(), v2 = v[1].abs(); + + // TODO Check whether "shorter" just means by rectangle norm: + // return u1.max(u2).compareTo(v1.max(v2)) < 0; + + boolean c1 = u1.compareTo(v1) < 0, c2 = u2.compareTo(v2) < 0; + if (c1 == c2) + { + return c1; + } + + BigInteger du = u1.multiply(u1).add(u2.multiply(u2)); + BigInteger dv = v1.multiply(v1).add(v2.multiply(v2)); + + return du.compareTo(dv) < 0; + } + + private static boolean isVectorBoundedBySqrt(BigInteger[] v, BigInteger n) + { + BigInteger max = v[0].abs().max(v[1].abs()); + return isLessThanSqrt(max, n); + } + + private static BigInteger[] order(BigInteger a, BigInteger b) + { + if (a.compareTo(b) <= 0) + { + return new BigInteger[]{ a, b }; + } + return new BigInteger[]{ b, a }; + } + + private static BigInteger roundQuotient(BigInteger x, BigInteger y) + { + boolean negative = (x.signum() != y.signum()); + x = x.abs(); + y = y.abs(); + BigInteger result = x.add(y.shiftRight(1)).divide(y); + return negative ? result.negate() : result; + } + + private static BigInteger solveQuadraticEquation(BigInteger n, BigInteger r, BigInteger s) + { + BigInteger det = r.multiply(r).subtract(s.shiftLeft(2)).mod(n); + + BigInteger root = new ECFieldElement.Fp(n, det).sqrt().toBigInteger(); + if (!root.testBit(0)) + { + root = n.subtract(root); + } + + return root.shiftRight(1); // NOTE: implicit -1 of the low-bit + } + + private static BigInteger isqrt(BigInteger x) + { + BigInteger g0 = x.shiftRight(x.bitLength() / 2); + for (;;) + { + BigInteger g1 = g0.add(x.divide(g0)).shiftRight(1); + if (g1.equals(g0)) + { + return g1; + } + g0 = g1; + } + } + + private static void swap(BigInteger[] ab) + { + BigInteger tmp = ab[0]; + ab[0] = ab[1]; + ab[1] = tmp; + } +} |