diff options
author | Peter Dettman <peter.dettman@bouncycastle.org> | 2015-06-19 15:45:30 +0700 |
---|---|---|
committer | Peter Dettman <peter.dettman@bouncycastle.org> | 2015-06-19 15:45:30 +0700 |
commit | 2b2c2b9b3d50ba833d3f140b21a352b44ccac921 (patch) | |
tree | 2f629b5232fc231b40a1e1b067be5ea9e4092ddb /crypto/src/math/ec/custom/sec | |
parent | Merge branch 'FancyFon-master' (diff) | |
download | BouncyCastle.NET-ed25519-2b2c2b9b3d50ba833d3f140b21a352b44ccac921.tar.xz |
Latest custom EC updates from Java API
Diffstat (limited to 'crypto/src/math/ec/custom/sec')
-rw-r--r-- | crypto/src/math/ec/custom/sec/SecT131Field.cs | 4 | ||||
-rw-r--r-- | crypto/src/math/ec/custom/sec/SecT163Field.cs | 4 | ||||
-rw-r--r-- | crypto/src/math/ec/custom/sec/SecT193Field.cs | 239 | ||||
-rw-r--r-- | crypto/src/math/ec/custom/sec/SecT193FieldElement.cs | 213 | ||||
-rw-r--r-- | crypto/src/math/ec/custom/sec/SecT193R1Curve.cs | 190 | ||||
-rw-r--r-- | crypto/src/math/ec/custom/sec/SecT193R1Point.cs | 283 | ||||
-rw-r--r-- | crypto/src/math/ec/custom/sec/SecT193R2Curve.cs | 190 | ||||
-rw-r--r-- | crypto/src/math/ec/custom/sec/SecT193R2Point.cs | 283 | ||||
-rw-r--r-- | crypto/src/math/ec/custom/sec/SecT233Field.cs | 4 | ||||
-rw-r--r-- | crypto/src/math/ec/custom/sec/SecT239Field.cs | 4 | ||||
-rw-r--r-- | crypto/src/math/ec/custom/sec/SecT283Field.cs | 4 | ||||
-rw-r--r-- | crypto/src/math/ec/custom/sec/SecT409Field.cs | 2 | ||||
-rw-r--r-- | crypto/src/math/ec/custom/sec/SecT571Field.cs | 2 |
13 files changed, 1410 insertions, 12 deletions
diff --git a/crypto/src/math/ec/custom/sec/SecT131Field.cs b/crypto/src/math/ec/custom/sec/SecT131Field.cs index df75dfcd7..6a1d2a960 100644 --- a/crypto/src/math/ec/custom/sec/SecT131Field.cs +++ b/crypto/src/math/ec/custom/sec/SecT131Field.cs @@ -231,7 +231,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec Debug.Assert(y >> 45 == 0); ulong[] u = new ulong[8]; - // u[0] = 0; + //u[0] = 0; u[1] = y; u[2] = u[1] << 1; u[3] = u[2] ^ y; @@ -247,7 +247,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec int k = 33; do { - j = (uint)(x >> k); + j = (uint)(x >> k); g = u[j & 7] ^ u[(j >> 3) & 7] << 3 ^ u[(j >> 6) & 7] << 6 diff --git a/crypto/src/math/ec/custom/sec/SecT163Field.cs b/crypto/src/math/ec/custom/sec/SecT163Field.cs index 2a775e20d..165d5b841 100644 --- a/crypto/src/math/ec/custom/sec/SecT163Field.cs +++ b/crypto/src/math/ec/custom/sec/SecT163Field.cs @@ -230,7 +230,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec Debug.Assert(y >> 56 == 0); ulong[] u = new ulong[8]; - // u[0] = 0; + //u[0] = 0; u[1] = y; u[2] = u[1] << 1; u[3] = u[2] ^ y; @@ -244,7 +244,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec int k = 47; do { - j = (uint)(x >> k); + j = (uint)(x >> k); g = u[j & 7] ^ u[(j >> 3) & 7] << 3 ^ u[(j >> 6) & 7] << 6; diff --git a/crypto/src/math/ec/custom/sec/SecT193Field.cs b/crypto/src/math/ec/custom/sec/SecT193Field.cs new file mode 100644 index 000000000..85db061c3 --- /dev/null +++ b/crypto/src/math/ec/custom/sec/SecT193Field.cs @@ -0,0 +1,239 @@ +using System; +using System.Diagnostics; + +using Org.BouncyCastle.Math.Raw; + +namespace Org.BouncyCastle.Math.EC.Custom.Sec +{ + internal class SecT193Field + { + private const ulong M01 = 1UL; + private const ulong M49 = ulong.MaxValue >> 15; + + public static void Add(ulong[] x, ulong[] y, ulong[] z) + { + z[0] = x[0] ^ y[0]; + z[1] = x[1] ^ y[1]; + z[2] = x[2] ^ y[2]; + z[3] = x[3] ^ y[3]; + } + + public static void AddExt(ulong[] xx, ulong[] yy, ulong[] zz) + { + zz[0] = xx[0] ^ yy[0]; + zz[1] = xx[1] ^ yy[1]; + zz[2] = xx[2] ^ yy[2]; + zz[3] = xx[3] ^ yy[3]; + zz[4] = xx[4] ^ yy[4]; + zz[5] = xx[5] ^ yy[5]; + zz[6] = xx[6] ^ yy[6]; + } + + public static void AddOne(ulong[] x, ulong[] z) + { + z[0] = x[0] ^ 1UL; + z[1] = x[1]; + z[2] = x[2]; + z[3] = x[3]; + } + + public static ulong[] FromBigInteger(BigInteger x) + { + ulong[] z = Nat256.FromBigInteger64(x); + Reduce63(z, 0); + return z; + } + + public static void Multiply(ulong[] x, ulong[] y, ulong[] z) + { + ulong[] tt = Nat256.CreateExt64(); + ImplMultiply(x, y, tt); + Reduce(tt, z); + } + + public static void MultiplyAddToExt(ulong[] x, ulong[] y, ulong[] zz) + { + ulong[] tt = Nat256.CreateExt64(); + ImplMultiply(x, y, tt); + AddExt(zz, tt, zz); + } + + public static void Reduce(ulong[] xx, ulong[] z) + { + ulong x0 = xx[0], x1 = xx[1], x2 = xx[2], x3 = xx[3], x4 = xx[4], x5 = xx[5], x6 = xx[6]; + + x2 ^= (x6 << 63); + x3 ^= (x6 >> 1) ^ (x6 << 14); + x4 ^= (x6 >> 50); + + x1 ^= (x5 << 63); + x2 ^= (x5 >> 1) ^ (x5 << 14); + x3 ^= (x5 >> 50); + + x0 ^= (x4 << 63); + x1 ^= (x4 >> 1) ^ (x4 << 14); + x2 ^= (x4 >> 50); + + ulong t = x3 >> 1; + z[0] = x0 ^ t ^ (t << 15); + z[1] = x1 ^ (t >> 49); + z[2] = x2; + z[3] = x3 & M01; + } + + public static void Reduce63(ulong[] z, int zOff) + { + ulong z3 = z[zOff + 3], t = z3 >> 1; + z[zOff ] ^= t ^ (t << 15); + z[zOff + 1] ^= (t >> 49); + z[zOff + 3] = z3 & M01; + } + + public static void Square(ulong[] x, ulong[] z) + { + ulong[] tt = Nat256.CreateExt64(); + ImplSquare(x, tt); + Reduce(tt, z); + } + + public static void SquareAddToExt(ulong[] x, ulong[] zz) + { + ulong[] tt = Nat256.CreateExt64(); + ImplSquare(x, tt); + AddExt(zz, tt, zz); + } + + public static void SquareN(ulong[] x, int n, ulong[] z) + { + Debug.Assert(n > 0); + + ulong[] tt = Nat256.CreateExt64(); + ImplSquare(x, tt); + Reduce(tt, z); + + while (--n > 0) + { + ImplSquare(z, tt); + Reduce(tt, z); + } + } + + protected static void ImplCompactExt(ulong[] zz) + { + ulong z0 = zz[0], z1 = zz[1], z2 = zz[2], z3 = zz[3], z4 = zz[4], z5 = zz[5], z6 = zz[6], z7 = zz[7]; + zz[0] = z0 ^ (z1 << 49); + zz[1] = (z1 >> 15) ^ (z2 << 34); + zz[2] = (z2 >> 30) ^ (z3 << 19); + zz[3] = (z3 >> 45) ^ (z4 << 4) + ^ (z5 << 53); + zz[4] = (z4 >> 60) ^ (z6 << 38) + ^ (z5 >> 11); + zz[5] = (z6 >> 26) ^ (z7 << 23); + zz[6] = (z7 >> 41); + zz[7] = 0; + } + + protected static void ImplExpand(ulong[] x, ulong[] z) + { + ulong x0 = x[0], x1 = x[1], x2 = x[2], x3 = x[3]; + z[0] = x0 & M49; + z[1] = ((x0 >> 49) ^ (x1 << 15)) & M49; + z[2] = ((x1 >> 34) ^ (x2 << 30)) & M49; + z[3] = ((x2 >> 19) ^ (x3 << 45)); + } + + protected static void ImplMultiply(ulong[] x, ulong[] y, ulong[] zz) + { + /* + * "Two-level seven-way recursion" as described in "Batch binary Edwards", Daniel J. Bernstein. + */ + + ulong[] f = new ulong[4], g = new ulong[4]; + ImplExpand(x, f); + ImplExpand(y, g); + + ImplMulwAcc(f[0], g[0], zz, 0); + ImplMulwAcc(f[1], g[1], zz, 1); + ImplMulwAcc(f[2], g[2], zz, 2); + ImplMulwAcc(f[3], g[3], zz, 3); + + // U *= (1 - t^n) + for (int i = 5; i > 0; --i) + { + zz[i] ^= zz[i - 1]; + } + + ImplMulwAcc(f[0] ^ f[1], g[0] ^ g[1], zz, 1); + ImplMulwAcc(f[2] ^ f[3], g[2] ^ g[3], zz, 3); + + // V *= (1 - t^2n) + for (int i = 7; i > 1; --i) + { + zz[i] ^= zz[i - 2]; + } + + // Double-length recursion + { + ulong c0 = f[0] ^ f[2], c1 = f[1] ^ f[3]; + ulong d0 = g[0] ^ g[2], d1 = g[1] ^ g[3]; + ImplMulwAcc(c0 ^ c1, d0 ^ d1, zz, 3); + ulong[] t = new ulong[3]; + ImplMulwAcc(c0, d0, t, 0); + ImplMulwAcc(c1, d1, t, 1); + ulong t0 = t[0], t1 = t[1], t2 = t[2]; + zz[2] ^= t0; + zz[3] ^= t0 ^ t1; + zz[4] ^= t2 ^ t1; + zz[5] ^= t2; + } + + ImplCompactExt(zz); + } + + protected static void ImplMulwAcc(ulong x, ulong y, ulong[] z, int zOff) + { + Debug.Assert(x >> 49 == 0); + Debug.Assert(y >> 49 == 0); + + ulong[] u = new ulong[8]; + //u[0] = 0; + u[1] = y; + u[2] = u[1] << 1; + u[3] = u[2] ^ y; + u[4] = u[2] << 1; + u[5] = u[4] ^ y; + u[6] = u[3] << 1; + u[7] = u[6] ^ y; + + uint j = (uint)x; + ulong g, h = 0, l = u[j & 7] + ^ (u[(j >> 3) & 7] << 3); + int k = 36; + do + { + j = (uint)(x >> k); + g = u[j & 7] + ^ u[(j >> 3) & 7] << 3 + ^ u[(j >> 6) & 7] << 6 + ^ u[(j >> 9) & 7] << 9 + ^ u[(j >> 12) & 7] << 12; + l ^= (g << k); + h ^= (g >> -k); + } + while ((k -= 15) > 0); + + Debug.Assert(h >> 33 == 0); + + z[zOff ] ^= l & M49; + z[zOff + 1] ^= (l >> 49) ^ (h << 15); + } + + protected static void ImplSquare(ulong[] x, ulong[] zz) + { + Interleave.Expand64To128(x[0], zz, 0); + Interleave.Expand64To128(x[1], zz, 2); + Interleave.Expand64To128(x[2], zz, 4); + zz[6] = (x[3] & M01); + } + } +} diff --git a/crypto/src/math/ec/custom/sec/SecT193FieldElement.cs b/crypto/src/math/ec/custom/sec/SecT193FieldElement.cs new file mode 100644 index 000000000..995d2ebdd --- /dev/null +++ b/crypto/src/math/ec/custom/sec/SecT193FieldElement.cs @@ -0,0 +1,213 @@ +using System; + +using Org.BouncyCastle.Math.Raw; +using Org.BouncyCastle.Utilities; + +namespace Org.BouncyCastle.Math.EC.Custom.Sec +{ + internal class SecT193FieldElement + : ECFieldElement + { + protected readonly ulong[] x; + + public SecT193FieldElement(BigInteger x) + { + if (x == null || x.SignValue < 0 || x.BitLength > 193) + throw new ArgumentException("value invalid for SecT193FieldElement", "x"); + + this.x = SecT193Field.FromBigInteger(x); + } + + public SecT193FieldElement() + { + this.x = Nat256.Create64(); + } + + protected internal SecT193FieldElement(ulong[] x) + { + this.x = x; + } + + public override bool IsOne + { + get { return Nat256.IsOne64(x); } + } + + public override bool IsZero + { + get { return Nat256.IsZero64(x); } + } + + public override bool TestBitZero() + { + return (x[0] & 1UL) != 0UL; + } + + public override BigInteger ToBigInteger() + { + return Nat256.ToBigInteger64(x); + } + + public override string FieldName + { + get { return "SecT193Field"; } + } + + public override int FieldSize + { + get { return 193; } + } + + public override ECFieldElement Add(ECFieldElement b) + { + ulong[] z = Nat256.Create64(); + SecT193Field.Add(x, ((SecT193FieldElement)b).x, z); + return new SecT193FieldElement(z); + } + + public override ECFieldElement AddOne() + { + ulong[] z = Nat256.Create64(); + SecT193Field.AddOne(x, z); + return new SecT193FieldElement(z); + } + + public override ECFieldElement Subtract(ECFieldElement b) + { + // Addition and Subtraction are the same in F2m + return Add(b); + } + + public override ECFieldElement Multiply(ECFieldElement b) + { + ulong[] z = Nat256.Create64(); + SecT193Field.Multiply(x, ((SecT193FieldElement)b).x, z); + return new SecT193FieldElement(z); + } + + public override ECFieldElement MultiplyMinusProduct(ECFieldElement b, ECFieldElement x, ECFieldElement y) + { + return MultiplyPlusProduct(b, x, y); + } + + public override ECFieldElement MultiplyPlusProduct(ECFieldElement b, ECFieldElement x, ECFieldElement y) + { + ulong[] ax = this.x, bx = ((SecT193FieldElement)b).x; + ulong[] xx = ((SecT193FieldElement)x).x, yx = ((SecT193FieldElement)y).x; + + ulong[] tt = Nat256.CreateExt64(); + SecT193Field.MultiplyAddToExt(ax, bx, tt); + SecT193Field.MultiplyAddToExt(xx, yx, tt); + + ulong[] z = Nat256.Create64(); + SecT193Field.Reduce(tt, z); + return new SecT193FieldElement(z); + } + + public override ECFieldElement Divide(ECFieldElement b) + { + return Multiply(b.Invert()); + } + + public override ECFieldElement Negate() + { + return this; + } + + public override ECFieldElement Square() + { + ulong[] z = Nat256.Create64(); + SecT193Field.Square(x, z); + return new SecT193FieldElement(z); + } + + public override ECFieldElement SquareMinusProduct(ECFieldElement x, ECFieldElement y) + { + return SquarePlusProduct(x, y); + } + + public override ECFieldElement SquarePlusProduct(ECFieldElement x, ECFieldElement y) + { + ulong[] ax = this.x; + ulong[] xx = ((SecT193FieldElement)x).x, yx = ((SecT193FieldElement)y).x; + + ulong[] tt = Nat256.CreateExt64(); + SecT193Field.SquareAddToExt(ax, tt); + SecT193Field.MultiplyAddToExt(xx, yx, tt); + + ulong[] z = Nat256.Create64(); + SecT193Field.Reduce(tt, z); + return new SecT193FieldElement(z); + } + + public override ECFieldElement SquarePow(int pow) + { + if (pow < 1) + return this; + + ulong[] z = Nat256.Create64(); + SecT193Field.SquareN(x, pow, z); + return new SecT193FieldElement(z); + } + + public override ECFieldElement Invert() + { + return new SecT193FieldElement( + AbstractF2mCurve.Inverse(193, new int[] { 15 }, ToBigInteger())); + } + + public override ECFieldElement Sqrt() + { + return SquarePow(M - 1); + } + + public virtual int Representation + { + get { return F2mFieldElement.Tpb; } + } + + public virtual int M + { + get { return 193; } + } + + public virtual int K1 + { + get { return 15; } + } + + public virtual int K2 + { + get { return 0; } + } + + public virtual int K3 + { + get { return 0; } + } + + public override bool Equals(object obj) + { + return Equals(obj as SecT193FieldElement); + } + + public override bool Equals(ECFieldElement other) + { + return Equals(other as SecT193FieldElement); + } + + public virtual bool Equals(SecT193FieldElement other) + { + if (this == other) + return true; + if (null == other) + return false; + return Nat256.Eq64(x, other.x); + } + + public override int GetHashCode() + { + return 1930015 ^ Arrays.GetHashCode(x, 0, 4); + } + } +} diff --git a/crypto/src/math/ec/custom/sec/SecT193R1Curve.cs b/crypto/src/math/ec/custom/sec/SecT193R1Curve.cs new file mode 100644 index 000000000..802954b01 --- /dev/null +++ b/crypto/src/math/ec/custom/sec/SecT193R1Curve.cs @@ -0,0 +1,190 @@ +using System; + +using Org.BouncyCastle.Utilities.Encoders; + +namespace Org.BouncyCastle.Math.EC.Custom.Sec +{ + internal class SecT193R1Curve + : AbstractF2mCurve + { + private const int SecT193R1_DEFAULT_COORDS = COORD_LAMBDA_PROJECTIVE; + + protected readonly SecT193R1Point m_infinity; + + public SecT193R1Curve() + : base(193, 15, 0, 0) + { + this.m_infinity = new SecT193R1Point(this, null, null); + + this.m_a = FromBigInteger(new BigInteger(1, Hex.Decode("0017858FEB7A98975169E171F77B4087DE098AC8A911DF7B01"))); + this.m_b = FromBigInteger(new BigInteger(1, Hex.Decode("00FDFB49BFE6C3A89FACADAA7A1E5BBC7CC1C2E5D831478814"))); + this.m_order = new BigInteger(1, Hex.Decode("01000000000000000000000000C7F34A778F443ACC920EBA49")); + this.m_cofactor = BigInteger.Two; + + this.m_coord = SecT193R1_DEFAULT_COORDS; + } + + protected override ECCurve CloneCurve() + { + return new SecT193R1Curve(); + } + + public override bool SupportsCoordinateSystem(int coord) + { + switch (coord) + { + case COORD_LAMBDA_PROJECTIVE: + return true; + default: + return false; + } + } + + public override ECPoint Infinity + { + get { return m_infinity; } + } + + public override int FieldSize + { + get { return 193; } + } + + public override ECFieldElement FromBigInteger(BigInteger x) + { + return new SecT193FieldElement(x); + } + + protected internal override ECPoint CreateRawPoint(ECFieldElement x, ECFieldElement y, bool withCompression) + { + return new SecT193R1Point(this, x, y, withCompression); + } + + protected internal override ECPoint CreateRawPoint(ECFieldElement x, ECFieldElement y, ECFieldElement[] zs, bool withCompression) + { + return new SecT193R1Point(this, x, y, zs, withCompression); + } + + public override bool IsKoblitz + { + get { return false; } + } + + /** + * Decompresses a compressed point P = (xp, yp) (X9.62 s 4.2.2). + * + * @param yTilde + * ~yp, an indication bit for the decompression of yp. + * @param X1 + * The field element xp. + * @return the decompressed point. + */ + protected override ECPoint DecompressPoint(int yTilde, BigInteger X1) + { + ECFieldElement x = FromBigInteger(X1), y = null; + if (x.IsZero) + { + y = B.Sqrt(); + } + else + { + ECFieldElement beta = x.Square().Invert().Multiply(B).Add(A).Add(x); + ECFieldElement z = SolveQuadraticEquation(beta); + if (z != null) + { + if (z.TestBitZero() != (yTilde == 1)) + { + z = z.AddOne(); + } + + switch (this.CoordinateSystem) + { + case COORD_LAMBDA_AFFINE: + case COORD_LAMBDA_PROJECTIVE: + { + y = z.Add(x); + break; + } + default: + { + y = z.Multiply(x); + break; + } + } + } + } + + if (y == null) + throw new ArgumentException("Invalid point compression"); + + return this.CreateRawPoint(x, y, true); + } + + /** + * Solves a quadratic equation <code>z<sup>2</sup> + z = beta</code>(X9.62 + * D.1.6) The other solution is <code>z + 1</code>. + * + * @param beta + * The value to solve the quadratic equation for. + * @return the solution for <code>z<sup>2</sup> + z = beta</code> or + * <code>null</code> if no solution exists. + */ + private ECFieldElement SolveQuadraticEquation(ECFieldElement beta) + { + if (beta.IsZero) + { + return beta; + } + + ECFieldElement zeroElement = FromBigInteger(BigInteger.Zero); + + ECFieldElement z = null; + ECFieldElement gamma = null; + + Random rand = new Random(); + do + { + ECFieldElement t = FromBigInteger(new BigInteger(193, rand)); + z = zeroElement; + ECFieldElement w = beta; + for (int i = 1; i < 193; i++) + { + ECFieldElement w2 = w.Square(); + z = z.Square().Add(w2.Multiply(t)); + w = w2.Add(beta); + } + if (!w.IsZero) + return null; + gamma = z.Square().Add(z); + } + while (gamma.IsZero); + + return z; + } + + public virtual int M + { + get { return 193; } + } + + public virtual bool IsTrinomial + { + get { return true; } + } + + public virtual int K1 + { + get { return 15; } + } + + public virtual int K2 + { + get { return 0; } + } + + public virtual int K3 + { + get { return 0; } + } + } +} diff --git a/crypto/src/math/ec/custom/sec/SecT193R1Point.cs b/crypto/src/math/ec/custom/sec/SecT193R1Point.cs new file mode 100644 index 000000000..062fce9d4 --- /dev/null +++ b/crypto/src/math/ec/custom/sec/SecT193R1Point.cs @@ -0,0 +1,283 @@ +using System; + +namespace Org.BouncyCastle.Math.EC.Custom.Sec +{ + internal class SecT193R1Point + : AbstractF2mPoint + { + /** + * @deprecated Use ECCurve.createPoint to construct points + */ + public SecT193R1Point(ECCurve curve, ECFieldElement x, ECFieldElement y) + : this(curve, x, y, false) + { + } + + /** + * @deprecated per-point compression property will be removed, refer {@link #getEncoded(bool)} + */ + public SecT193R1Point(ECCurve curve, ECFieldElement x, ECFieldElement y, bool withCompression) + : base(curve, x, y, withCompression) + { + if ((x == null) != (y == null)) + throw new ArgumentException("Exactly one of the field elements is null"); + } + + internal SecT193R1Point(ECCurve curve, ECFieldElement x, ECFieldElement y, ECFieldElement[] zs, bool withCompression) + : base(curve, x, y, zs, withCompression) + { + } + + protected override ECPoint Detach() + { + return new SecT193R1Point(null, AffineXCoord, AffineYCoord); + } + + public override ECFieldElement YCoord + { + get + { + ECFieldElement X = RawXCoord, L = RawYCoord; + + if (this.IsInfinity || X.IsZero) + return L; + + // Y is actually Lambda (X + Y/X) here; convert to affine value on the fly + ECFieldElement Y = L.Add(X).Multiply(X); + + ECFieldElement Z = RawZCoords[0]; + if (!Z.IsOne) + { + Y = Y.Divide(Z); + } + + return Y; + } + } + + protected internal override bool CompressionYTilde + { + get + { + ECFieldElement X = this.RawXCoord; + if (X.IsZero) + return false; + + ECFieldElement Y = this.RawYCoord; + + // Y is actually Lambda (X + Y/X) here + return Y.TestBitZero() != X.TestBitZero(); + } + } + + public override ECPoint Add(ECPoint b) + { + if (this.IsInfinity) + return b; + if (b.IsInfinity) + return this; + + ECCurve curve = this.Curve; + + ECFieldElement X1 = this.RawXCoord; + ECFieldElement X2 = b.RawXCoord; + + if (X1.IsZero) + { + if (X2.IsZero) + return curve.Infinity; + + return b.Add(this); + } + + ECFieldElement L1 = this.RawYCoord, Z1 = this.RawZCoords[0]; + ECFieldElement L2 = b.RawYCoord, Z2 = b.RawZCoords[0]; + + bool Z1IsOne = Z1.IsOne; + ECFieldElement U2 = X2, S2 = L2; + if (!Z1IsOne) + { + U2 = U2.Multiply(Z1); + S2 = S2.Multiply(Z1); + } + + bool Z2IsOne = Z2.IsOne; + ECFieldElement U1 = X1, S1 = L1; + if (!Z2IsOne) + { + U1 = U1.Multiply(Z2); + S1 = S1.Multiply(Z2); + } + + ECFieldElement A = S1.Add(S2); + ECFieldElement B = U1.Add(U2); + + if (B.IsZero) + { + if (A.IsZero) + return Twice(); + + return curve.Infinity; + } + + ECFieldElement X3, L3, Z3; + if (X2.IsZero) + { + // TODO This can probably be optimized quite a bit + ECPoint p = this.Normalize(); + X1 = p.XCoord; + ECFieldElement Y1 = p.YCoord; + + ECFieldElement Y2 = L2; + ECFieldElement L = Y1.Add(Y2).Divide(X1); + + X3 = L.Square().Add(L).Add(X1).Add(curve.A); + if (X3.IsZero) + { + return new SecT193R1Point(curve, X3, curve.B.Sqrt(), IsCompressed); + } + + ECFieldElement Y3 = L.Multiply(X1.Add(X3)).Add(X3).Add(Y1); + L3 = Y3.Divide(X3).Add(X3); + Z3 = curve.FromBigInteger(BigInteger.One); + } + else + { + B = B.Square(); + + ECFieldElement AU1 = A.Multiply(U1); + ECFieldElement AU2 = A.Multiply(U2); + + X3 = AU1.Multiply(AU2); + if (X3.IsZero) + { + return new SecT193R1Point(curve, X3, curve.B.Sqrt(), IsCompressed); + } + + ECFieldElement ABZ2 = A.Multiply(B); + if (!Z2IsOne) + { + ABZ2 = ABZ2.Multiply(Z2); + } + + L3 = AU2.Add(B).SquarePlusProduct(ABZ2, L1.Add(Z1)); + + Z3 = ABZ2; + if (!Z1IsOne) + { + Z3 = Z3.Multiply(Z1); + } + } + + return new SecT193R1Point(curve, X3, L3, new ECFieldElement[] { Z3 }, IsCompressed); + } + + public override ECPoint Twice() + { + if (this.IsInfinity) + { + return this; + } + + ECCurve curve = this.Curve; + + ECFieldElement X1 = this.RawXCoord; + if (X1.IsZero) + { + // A point with X == 0 is it's own Additive inverse + return curve.Infinity; + } + + ECFieldElement L1 = this.RawYCoord, Z1 = this.RawZCoords[0]; + + bool Z1IsOne = Z1.IsOne; + ECFieldElement L1Z1 = Z1IsOne ? L1 : L1.Multiply(Z1); + ECFieldElement Z1Sq = Z1IsOne ? Z1 : Z1.Square(); + ECFieldElement a = curve.A; + ECFieldElement aZ1Sq = Z1IsOne ? a : a.Multiply(Z1Sq); + ECFieldElement T = L1.Square().Add(L1Z1).Add(aZ1Sq); + if (T.IsZero) + { + return new SecT193R1Point(curve, T, curve.B.Sqrt(), IsCompressed); + } + + ECFieldElement X3 = T.Square(); + ECFieldElement Z3 = Z1IsOne ? T : T.Multiply(Z1Sq); + + ECFieldElement X1Z1 = Z1IsOne ? X1 : X1.Multiply(Z1); + ECFieldElement L3 = X1Z1.SquarePlusProduct(T, L1Z1).Add(X3).Add(Z3); + + return new SecT193R1Point(curve, X3, L3, new ECFieldElement[] { Z3 }, IsCompressed); + } + + public override ECPoint TwicePlus(ECPoint b) + { + if (this.IsInfinity) + return b; + if (b.IsInfinity) + return Twice(); + + ECCurve curve = this.Curve; + + ECFieldElement X1 = this.RawXCoord; + if (X1.IsZero) + { + // A point with X == 0 is it's own Additive inverse + return b; + } + + ECFieldElement X2 = b.RawXCoord, Z2 = b.RawZCoords[0]; + if (X2.IsZero || !Z2.IsOne) + { + return Twice().Add(b); + } + + ECFieldElement L1 = this.RawYCoord, Z1 = this.RawZCoords[0]; + ECFieldElement L2 = b.RawYCoord; + + ECFieldElement X1Sq = X1.Square(); + ECFieldElement L1Sq = L1.Square(); + ECFieldElement Z1Sq = Z1.Square(); + ECFieldElement L1Z1 = L1.Multiply(Z1); + + ECFieldElement T = curve.A.Multiply(Z1Sq).Add(L1Sq).Add(L1Z1); + ECFieldElement L2plus1 = L2.AddOne(); + ECFieldElement A = curve.A.Add(L2plus1).Multiply(Z1Sq).Add(L1Sq).MultiplyPlusProduct(T, X1Sq, Z1Sq); + ECFieldElement X2Z1Sq = X2.Multiply(Z1Sq); + ECFieldElement B = X2Z1Sq.Add(T).Square(); + + if (B.IsZero) + { + if (A.IsZero) + return b.Twice(); + + return curve.Infinity; + } + + if (A.IsZero) + { + return new SecT193R1Point(curve, A, curve.B.Sqrt(), IsCompressed); + } + + ECFieldElement X3 = A.Square().Multiply(X2Z1Sq); + ECFieldElement Z3 = A.Multiply(B).Multiply(Z1Sq); + ECFieldElement L3 = A.Add(B).Square().MultiplyPlusProduct(T, L2plus1, Z3); + + return new SecT193R1Point(curve, X3, L3, new ECFieldElement[] { Z3 }, IsCompressed); + } + + public override ECPoint Negate() + { + if (this.IsInfinity) + return this; + + ECFieldElement X = this.RawXCoord; + if (X.IsZero) + return this; + + // L is actually Lambda (X + Y/X) here + ECFieldElement L = this.RawYCoord, Z = this.RawZCoords[0]; + return new SecT193R1Point(Curve, X, L.Add(Z), new ECFieldElement[] { Z }, IsCompressed); + } + } +} diff --git a/crypto/src/math/ec/custom/sec/SecT193R2Curve.cs b/crypto/src/math/ec/custom/sec/SecT193R2Curve.cs new file mode 100644 index 000000000..b5345730c --- /dev/null +++ b/crypto/src/math/ec/custom/sec/SecT193R2Curve.cs @@ -0,0 +1,190 @@ +using System; + +using Org.BouncyCastle.Utilities.Encoders; + +namespace Org.BouncyCastle.Math.EC.Custom.Sec +{ + internal class SecT193R2Curve + : AbstractF2mCurve + { + private const int SecT193R2_DEFAULT_COORDS = COORD_LAMBDA_PROJECTIVE; + + protected readonly SecT193R2Point m_infinity; + + public SecT193R2Curve() + : base(193, 15, 0, 0) + { + this.m_infinity = new SecT193R2Point(this, null, null); + + this.m_a = FromBigInteger(new BigInteger(1, Hex.Decode("0163F35A5137C2CE3EA6ED8667190B0BC43ECD69977702709B"))); + this.m_b = FromBigInteger(new BigInteger(1, Hex.Decode("00C9BB9E8927D4D64C377E2AB2856A5B16E3EFB7F61D4316AE"))); + this.m_order = new BigInteger(1, Hex.Decode("010000000000000000000000015AAB561B005413CCD4EE99D5")); + this.m_cofactor = BigInteger.Two; + + this.m_coord = SecT193R2_DEFAULT_COORDS; + } + + protected override ECCurve CloneCurve() + { + return new SecT193R2Curve(); + } + + public override bool SupportsCoordinateSystem(int coord) + { + switch (coord) + { + case COORD_LAMBDA_PROJECTIVE: + return true; + default: + return false; + } + } + + public override ECPoint Infinity + { + get { return m_infinity; } + } + + public override int FieldSize + { + get { return 193; } + } + + public override ECFieldElement FromBigInteger(BigInteger x) + { + return new SecT193FieldElement(x); + } + + protected internal override ECPoint CreateRawPoint(ECFieldElement x, ECFieldElement y, bool withCompression) + { + return new SecT193R2Point(this, x, y, withCompression); + } + + protected internal override ECPoint CreateRawPoint(ECFieldElement x, ECFieldElement y, ECFieldElement[] zs, bool withCompression) + { + return new SecT193R2Point(this, x, y, zs, withCompression); + } + + public override bool IsKoblitz + { + get { return false; } + } + + /** + * Decompresses a compressed point P = (xp, yp) (X9.62 s 4.2.2). + * + * @param yTilde + * ~yp, an indication bit for the decompression of yp. + * @param X1 + * The field element xp. + * @return the decompressed point. + */ + protected override ECPoint DecompressPoint(int yTilde, BigInteger X1) + { + ECFieldElement x = FromBigInteger(X1), y = null; + if (x.IsZero) + { + y = B.Sqrt(); + } + else + { + ECFieldElement beta = x.Square().Invert().Multiply(B).Add(A).Add(x); + ECFieldElement z = SolveQuadraticEquation(beta); + if (z != null) + { + if (z.TestBitZero() != (yTilde == 1)) + { + z = z.AddOne(); + } + + switch (this.CoordinateSystem) + { + case COORD_LAMBDA_AFFINE: + case COORD_LAMBDA_PROJECTIVE: + { + y = z.Add(x); + break; + } + default: + { + y = z.Multiply(x); + break; + } + } + } + } + + if (y == null) + throw new ArgumentException("Invalid point compression"); + + return this.CreateRawPoint(x, y, true); + } + + /** + * Solves a quadratic equation <code>z<sup>2</sup> + z = beta</code>(X9.62 + * D.1.6) The other solution is <code>z + 1</code>. + * + * @param beta + * The value to solve the quadratic equation for. + * @return the solution for <code>z<sup>2</sup> + z = beta</code> or + * <code>null</code> if no solution exists. + */ + private ECFieldElement SolveQuadraticEquation(ECFieldElement beta) + { + if (beta.IsZero) + { + return beta; + } + + ECFieldElement zeroElement = FromBigInteger(BigInteger.Zero); + + ECFieldElement z = null; + ECFieldElement gamma = null; + + Random rand = new Random(); + do + { + ECFieldElement t = FromBigInteger(new BigInteger(193, rand)); + z = zeroElement; + ECFieldElement w = beta; + for (int i = 1; i < 193; i++) + { + ECFieldElement w2 = w.Square(); + z = z.Square().Add(w2.Multiply(t)); + w = w2.Add(beta); + } + if (!w.IsZero) + return null; + gamma = z.Square().Add(z); + } + while (gamma.IsZero); + + return z; + } + + public virtual int M + { + get { return 193; } + } + + public virtual bool IsTrinomial + { + get { return true; } + } + + public virtual int K1 + { + get { return 15; } + } + + public virtual int K2 + { + get { return 0; } + } + + public virtual int K3 + { + get { return 0; } + } + } +} diff --git a/crypto/src/math/ec/custom/sec/SecT193R2Point.cs b/crypto/src/math/ec/custom/sec/SecT193R2Point.cs new file mode 100644 index 000000000..18d89e316 --- /dev/null +++ b/crypto/src/math/ec/custom/sec/SecT193R2Point.cs @@ -0,0 +1,283 @@ +using System; + +namespace Org.BouncyCastle.Math.EC.Custom.Sec +{ + internal class SecT193R2Point + : AbstractF2mPoint + { + /** + * @deprecated Use ECCurve.createPoint to construct points + */ + public SecT193R2Point(ECCurve curve, ECFieldElement x, ECFieldElement y) + : this(curve, x, y, false) + { + } + + /** + * @deprecated per-point compression property will be removed, refer {@link #getEncoded(bool)} + */ + public SecT193R2Point(ECCurve curve, ECFieldElement x, ECFieldElement y, bool withCompression) + : base(curve, x, y, withCompression) + { + if ((x == null) != (y == null)) + throw new ArgumentException("Exactly one of the field elements is null"); + } + + internal SecT193R2Point(ECCurve curve, ECFieldElement x, ECFieldElement y, ECFieldElement[] zs, bool withCompression) + : base(curve, x, y, zs, withCompression) + { + } + + protected override ECPoint Detach() + { + return new SecT193R2Point(null, AffineXCoord, AffineYCoord); + } + + public override ECFieldElement YCoord + { + get + { + ECFieldElement X = RawXCoord, L = RawYCoord; + + if (this.IsInfinity || X.IsZero) + return L; + + // Y is actually Lambda (X + Y/X) here; convert to affine value on the fly + ECFieldElement Y = L.Add(X).Multiply(X); + + ECFieldElement Z = RawZCoords[0]; + if (!Z.IsOne) + { + Y = Y.Divide(Z); + } + + return Y; + } + } + + protected internal override bool CompressionYTilde + { + get + { + ECFieldElement X = this.RawXCoord; + if (X.IsZero) + return false; + + ECFieldElement Y = this.RawYCoord; + + // Y is actually Lambda (X + Y/X) here + return Y.TestBitZero() != X.TestBitZero(); + } + } + + public override ECPoint Add(ECPoint b) + { + if (this.IsInfinity) + return b; + if (b.IsInfinity) + return this; + + ECCurve curve = this.Curve; + + ECFieldElement X1 = this.RawXCoord; + ECFieldElement X2 = b.RawXCoord; + + if (X1.IsZero) + { + if (X2.IsZero) + return curve.Infinity; + + return b.Add(this); + } + + ECFieldElement L1 = this.RawYCoord, Z1 = this.RawZCoords[0]; + ECFieldElement L2 = b.RawYCoord, Z2 = b.RawZCoords[0]; + + bool Z1IsOne = Z1.IsOne; + ECFieldElement U2 = X2, S2 = L2; + if (!Z1IsOne) + { + U2 = U2.Multiply(Z1); + S2 = S2.Multiply(Z1); + } + + bool Z2IsOne = Z2.IsOne; + ECFieldElement U1 = X1, S1 = L1; + if (!Z2IsOne) + { + U1 = U1.Multiply(Z2); + S1 = S1.Multiply(Z2); + } + + ECFieldElement A = S1.Add(S2); + ECFieldElement B = U1.Add(U2); + + if (B.IsZero) + { + if (A.IsZero) + return Twice(); + + return curve.Infinity; + } + + ECFieldElement X3, L3, Z3; + if (X2.IsZero) + { + // TODO This can probably be optimized quite a bit + ECPoint p = this.Normalize(); + X1 = p.XCoord; + ECFieldElement Y1 = p.YCoord; + + ECFieldElement Y2 = L2; + ECFieldElement L = Y1.Add(Y2).Divide(X1); + + X3 = L.Square().Add(L).Add(X1).Add(curve.A); + if (X3.IsZero) + { + return new SecT193R2Point(curve, X3, curve.B.Sqrt(), IsCompressed); + } + + ECFieldElement Y3 = L.Multiply(X1.Add(X3)).Add(X3).Add(Y1); + L3 = Y3.Divide(X3).Add(X3); + Z3 = curve.FromBigInteger(BigInteger.One); + } + else + { + B = B.Square(); + + ECFieldElement AU1 = A.Multiply(U1); + ECFieldElement AU2 = A.Multiply(U2); + + X3 = AU1.Multiply(AU2); + if (X3.IsZero) + { + return new SecT193R2Point(curve, X3, curve.B.Sqrt(), IsCompressed); + } + + ECFieldElement ABZ2 = A.Multiply(B); + if (!Z2IsOne) + { + ABZ2 = ABZ2.Multiply(Z2); + } + + L3 = AU2.Add(B).SquarePlusProduct(ABZ2, L1.Add(Z1)); + + Z3 = ABZ2; + if (!Z1IsOne) + { + Z3 = Z3.Multiply(Z1); + } + } + + return new SecT193R2Point(curve, X3, L3, new ECFieldElement[] { Z3 }, IsCompressed); + } + + public override ECPoint Twice() + { + if (this.IsInfinity) + { + return this; + } + + ECCurve curve = this.Curve; + + ECFieldElement X1 = this.RawXCoord; + if (X1.IsZero) + { + // A point with X == 0 is it's own Additive inverse + return curve.Infinity; + } + + ECFieldElement L1 = this.RawYCoord, Z1 = this.RawZCoords[0]; + + bool Z1IsOne = Z1.IsOne; + ECFieldElement L1Z1 = Z1IsOne ? L1 : L1.Multiply(Z1); + ECFieldElement Z1Sq = Z1IsOne ? Z1 : Z1.Square(); + ECFieldElement a = curve.A; + ECFieldElement aZ1Sq = Z1IsOne ? a : a.Multiply(Z1Sq); + ECFieldElement T = L1.Square().Add(L1Z1).Add(aZ1Sq); + if (T.IsZero) + { + return new SecT193R2Point(curve, T, curve.B.Sqrt(), IsCompressed); + } + + ECFieldElement X3 = T.Square(); + ECFieldElement Z3 = Z1IsOne ? T : T.Multiply(Z1Sq); + + ECFieldElement X1Z1 = Z1IsOne ? X1 : X1.Multiply(Z1); + ECFieldElement L3 = X1Z1.SquarePlusProduct(T, L1Z1).Add(X3).Add(Z3); + + return new SecT193R2Point(curve, X3, L3, new ECFieldElement[] { Z3 }, IsCompressed); + } + + public override ECPoint TwicePlus(ECPoint b) + { + if (this.IsInfinity) + return b; + if (b.IsInfinity) + return Twice(); + + ECCurve curve = this.Curve; + + ECFieldElement X1 = this.RawXCoord; + if (X1.IsZero) + { + // A point with X == 0 is it's own Additive inverse + return b; + } + + ECFieldElement X2 = b.RawXCoord, Z2 = b.RawZCoords[0]; + if (X2.IsZero || !Z2.IsOne) + { + return Twice().Add(b); + } + + ECFieldElement L1 = this.RawYCoord, Z1 = this.RawZCoords[0]; + ECFieldElement L2 = b.RawYCoord; + + ECFieldElement X1Sq = X1.Square(); + ECFieldElement L1Sq = L1.Square(); + ECFieldElement Z1Sq = Z1.Square(); + ECFieldElement L1Z1 = L1.Multiply(Z1); + + ECFieldElement T = curve.A.Multiply(Z1Sq).Add(L1Sq).Add(L1Z1); + ECFieldElement L2plus1 = L2.AddOne(); + ECFieldElement A = curve.A.Add(L2plus1).Multiply(Z1Sq).Add(L1Sq).MultiplyPlusProduct(T, X1Sq, Z1Sq); + ECFieldElement X2Z1Sq = X2.Multiply(Z1Sq); + ECFieldElement B = X2Z1Sq.Add(T).Square(); + + if (B.IsZero) + { + if (A.IsZero) + return b.Twice(); + + return curve.Infinity; + } + + if (A.IsZero) + { + return new SecT193R2Point(curve, A, curve.B.Sqrt(), IsCompressed); + } + + ECFieldElement X3 = A.Square().Multiply(X2Z1Sq); + ECFieldElement Z3 = A.Multiply(B).Multiply(Z1Sq); + ECFieldElement L3 = A.Add(B).Square().MultiplyPlusProduct(T, L2plus1, Z3); + + return new SecT193R2Point(curve, X3, L3, new ECFieldElement[] { Z3 }, IsCompressed); + } + + public override ECPoint Negate() + { + if (this.IsInfinity) + return this; + + ECFieldElement X = this.RawXCoord; + if (X.IsZero) + return this; + + // L is actually Lambda (X + Y/X) here + ECFieldElement L = this.RawYCoord, Z = this.RawZCoords[0]; + return new SecT193R2Point(Curve, X, L.Add(Z), new ECFieldElement[] { Z }, IsCompressed); + } + } +} diff --git a/crypto/src/math/ec/custom/sec/SecT233Field.cs b/crypto/src/math/ec/custom/sec/SecT233Field.cs index 165fadbf3..b36ffba2e 100644 --- a/crypto/src/math/ec/custom/sec/SecT233Field.cs +++ b/crypto/src/math/ec/custom/sec/SecT233Field.cs @@ -200,7 +200,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec Debug.Assert(y >> 59 == 0); ulong[] u = new ulong[8]; - // u[0] = 0; + //u[0] = 0; u[1] = y; u[2] = u[1] << 1; u[3] = u[2] ^ y; @@ -215,7 +215,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec int k = 54; do { - j = (uint)(x >> k); + j = (uint)(x >> k); g = u[j & 7] ^ u[(j >> 3) & 7] << 3; l ^= (g << k); diff --git a/crypto/src/math/ec/custom/sec/SecT239Field.cs b/crypto/src/math/ec/custom/sec/SecT239Field.cs index 1e0824af9..6dab907dd 100644 --- a/crypto/src/math/ec/custom/sec/SecT239Field.cs +++ b/crypto/src/math/ec/custom/sec/SecT239Field.cs @@ -204,7 +204,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec Debug.Assert(y >> 60 == 0); ulong[] u = new ulong[8]; - // u[0] = 0; + //u[0] = 0; u[1] = y; u[2] = u[1] << 1; u[3] = u[2] ^ y; @@ -219,7 +219,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec int k = 54; do { - j = (uint)(x >> k); + j = (uint)(x >> k); g = u[j & 7] ^ u[(j >> 3) & 7] << 3; l ^= (g << k); diff --git a/crypto/src/math/ec/custom/sec/SecT283Field.cs b/crypto/src/math/ec/custom/sec/SecT283Field.cs index 9afb27461..435787467 100644 --- a/crypto/src/math/ec/custom/sec/SecT283Field.cs +++ b/crypto/src/math/ec/custom/sec/SecT283Field.cs @@ -292,7 +292,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec Debug.Assert(y >> 57 == 0); ulong[] u = new ulong[8]; - // u[0] = 0; + //u[0] = 0; u[1] = y; u[2] = u[1] << 1; u[3] = u[2] ^ y; @@ -306,7 +306,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec int k = 48; do { - j = (uint)(x >> k); + j = (uint)(x >> k); g = u[j & 7] ^ u[(j >> 3) & 7] << 3 ^ u[(j >> 6) & 7] << 6; diff --git a/crypto/src/math/ec/custom/sec/SecT409Field.cs b/crypto/src/math/ec/custom/sec/SecT409Field.cs index d71f5b5f9..ce6f43f2e 100644 --- a/crypto/src/math/ec/custom/sec/SecT409Field.cs +++ b/crypto/src/math/ec/custom/sec/SecT409Field.cs @@ -196,7 +196,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec Debug.Assert(y >> 59 == 0); ulong[] u = new ulong[8]; - // u[0] = 0; + //u[0] = 0; u[1] = y; u[2] = u[1] << 1; u[3] = u[2] ^ y; diff --git a/crypto/src/math/ec/custom/sec/SecT571Field.cs b/crypto/src/math/ec/custom/sec/SecT571Field.cs index 0711ee4aa..921c841a9 100644 --- a/crypto/src/math/ec/custom/sec/SecT571Field.cs +++ b/crypto/src/math/ec/custom/sec/SecT571Field.cs @@ -199,7 +199,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec protected static void ImplMulwAcc(ulong[] xs, ulong y, ulong[] z, int zOff) { ulong[] u = new ulong[32]; - // u[0] = 0; + //u[0] = 0; u[1] = y; for (int i = 2; i < 32; i += 2) { |