diff options
Diffstat (limited to 'crypto')
| -rw-r--r-- | crypto/src/math/ec/ECCurve.cs | 117 | ||||
| -rw-r--r-- | crypto/src/math/ec/ECPoint.cs | 306 |
2 files changed, 354 insertions, 69 deletions
diff --git a/crypto/src/math/ec/ECCurve.cs b/crypto/src/math/ec/ECCurve.cs index 9679fdb89..4b58d7626 100644 --- a/crypto/src/math/ec/ECCurve.cs +++ b/crypto/src/math/ec/ECCurve.cs @@ -95,7 +95,11 @@ namespace Org.BouncyCastle.Math.EC return CreatePoint(x, y, false); } - public abstract ECPoint CreatePoint(BigInteger x, BigInteger y, bool withCompression); + [Obsolete("Per-point compression property will be removed")] + public virtual ECPoint CreatePoint(BigInteger x, BigInteger y, bool withCompression) + { + return CreateRawPoint(FromBigInteger(x), FromBigInteger(y), withCompression); + } protected abstract ECCurve CloneCurve(); @@ -343,7 +347,7 @@ namespace Org.BouncyCastle.Math.EC public class FpCurve : ECCurve { - private const int FP_DEFAULT_COORDS = COORD_HOMOGENEOUS; + private const int FP_DEFAULT_COORDS = COORD_JACOBIAN_MODIFIED; protected readonly BigInteger m_q, m_r; protected readonly FpPoint m_infinity; @@ -383,8 +387,8 @@ namespace Org.BouncyCastle.Math.EC { case COORD_AFFINE: case COORD_HOMOGENEOUS: - //case COORD_JACOBIAN: - //case COORD_JACOBIAN_MODIFIED: + case COORD_JACOBIAN: + case COORD_JACOBIAN_MODIFIED: return true; default: return false; @@ -416,17 +420,26 @@ namespace Org.BouncyCastle.Math.EC return new FpPoint(this, x, y, withCompression); } - public override ECPoint CreatePoint( - BigInteger X1, - BigInteger Y1, - bool withCompression) + public override ECPoint ImportPoint(ECPoint p) { - // TODO Validation of X1, Y1? - return new FpPoint( - this, - FromBigInteger(X1), - FromBigInteger(Y1), - withCompression); + if (this != p.Curve && this.CoordinateSystem == COORD_JACOBIAN && !p.IsInfinity) + { + switch (p.Curve.CoordinateSystem) + { + case COORD_JACOBIAN: + case COORD_JACOBIAN_CHUDNOVSKY: + case COORD_JACOBIAN_MODIFIED: + return new FpPoint(this, + FromBigInteger(p.RawXCoord.ToBigInteger()), + FromBigInteger(p.RawYCoord.ToBigInteger()), + new ECFieldElement[] { FromBigInteger(p.GetZCoord(0).ToBigInteger()) }, + p.IsCompressed); + default: + break; + } + } + + return base.ImportPoint(p); } protected override ECPoint DecompressPoint( @@ -744,24 +757,54 @@ namespace Org.BouncyCastle.Math.EC return base.CreateDefaultMultiplier(); } - protected internal override ECPoint CreateRawPoint(ECFieldElement x, ECFieldElement y, bool withCompression) + public override int FieldSize { - return new F2mPoint(this, x, y, withCompression); + get { return m; } } - public override ECPoint Infinity + public override ECFieldElement FromBigInteger(BigInteger x) { - get { return m_infinity; } + return new F2mFieldElement(this.m, this.k1, this.k2, this.k3, x); } - public override int FieldSize + public override ECPoint CreatePoint(BigInteger x, BigInteger y, bool withCompression) { - get { return m; } + ECFieldElement X = FromBigInteger(x), Y = FromBigInteger(y); + + switch (this.CoordinateSystem) + { + case COORD_LAMBDA_AFFINE: + case COORD_LAMBDA_PROJECTIVE: + { + if (X.IsZero) + { + if (!Y.Square().Equals(B)) + throw new ArgumentException(); + } + else + { + // Y becomes Lambda (X + Y/X) here + Y = Y.Divide(X).Add(X); + } + break; + } + default: + { + break; + } + } + + return CreateRawPoint(X, Y, withCompression); } - public override ECFieldElement FromBigInteger(BigInteger x) + protected internal override ECPoint CreateRawPoint(ECFieldElement x, ECFieldElement y, bool withCompression) { - return new F2mFieldElement(this.m, this.k1, this.k2, this.k3, x); + return new F2mPoint(this, x, y, withCompression); + } + + public override ECPoint Infinity + { + get { return m_infinity; } } /** @@ -818,36 +861,6 @@ namespace Org.BouncyCastle.Math.EC return si; } - public override ECPoint CreatePoint(BigInteger x, BigInteger y, bool withCompression) - { - ECFieldElement X = FromBigInteger(x), Y = FromBigInteger(y); - - switch (this.CoordinateSystem) - { - case COORD_LAMBDA_AFFINE: - case COORD_LAMBDA_PROJECTIVE: - { - if (X.IsZero) - { - if (!Y.Square().Equals(B)) - throw new ArgumentException(); - } - else - { - // Y becomes Lambda (X + Y/X) here - Y = Y.Divide(X).Add(X); - } - break; - } - default: - { - break; - } - } - - return CreateRawPoint(X, Y, withCompression); - } - protected override ECPoint DecompressPoint( int yTilde, BigInteger X1) diff --git a/crypto/src/math/ec/ECPoint.cs b/crypto/src/math/ec/ECPoint.cs index 67cbebcda..036da0d7d 100644 --- a/crypto/src/math/ec/ECPoint.cs +++ b/crypto/src/math/ec/ECPoint.cs @@ -189,6 +189,11 @@ namespace Org.BouncyCastle.Math.EC get { return m_y; } } + protected internal ECFieldElement[] RawZCoords + { + get { return m_zs; } + } + protected virtual void CheckNormalized() { if (!IsNormalized()) @@ -202,7 +207,7 @@ namespace Org.BouncyCastle.Math.EC return coord == ECCurve.COORD_AFFINE || coord == ECCurve.COORD_LAMBDA_AFFINE || IsInfinity - || GetZCoord(0).IsOne; + || RawZCoords[0].IsOne; } /** @@ -227,7 +232,7 @@ namespace Org.BouncyCastle.Math.EC } default: { - ECFieldElement Z1 = GetZCoord(0); + ECFieldElement Z1 = RawZCoords[0]; if (Z1.IsOne) { return this; @@ -530,6 +535,16 @@ namespace Org.BouncyCastle.Math.EC get { return this.AffineYCoord.TestBitZero(); } } + public override ECFieldElement GetZCoord(int index) + { + if (index == 1 && ECCurve.COORD_JACOBIAN_MODIFIED == this.CurveCoordinateSystem) + { + return GetJacobianModifiedW(); + } + + return base.GetZCoord(index); + } + // B.3 pg 62 public override ECPoint Add( ECPoint b) @@ -580,8 +595,8 @@ namespace Org.BouncyCastle.Math.EC case ECCurve.COORD_HOMOGENEOUS: { - ECFieldElement Z1 = this.GetZCoord(0); - ECFieldElement Z2 = b.GetZCoord(0); + ECFieldElement Z1 = this.RawZCoords[0]; + ECFieldElement Z2 = b.RawZCoords[0]; bool Z1IsOne = Z1.IsOne; bool Z2IsOne = Z2.IsOne; @@ -620,6 +635,136 @@ namespace Org.BouncyCastle.Math.EC return new FpPoint(curve, X3, Y3, new ECFieldElement[] { Z3 }, IsCompressed); } + case ECCurve.COORD_JACOBIAN: + case ECCurve.COORD_JACOBIAN_MODIFIED: + { + ECFieldElement Z1 = this.RawZCoords[0]; + ECFieldElement Z2 = b.RawZCoords[0]; + + bool Z1IsOne = Z1.IsOne; + + ECFieldElement X3, Y3, Z3, Z3Squared = null; + + if (!Z1IsOne && Z1.Equals(Z2)) + { + // TODO Make this available as public method coZAdd? + + ECFieldElement dx = X1.Subtract(X2), dy = Y1.Subtract(Y2); + if (dx.IsZero) + { + if (dy.IsZero) + { + return Twice(); + } + return curve.Infinity; + } + + ECFieldElement C = dx.Square(); + ECFieldElement W1 = X1.Multiply(C), W2 = X2.Multiply(C); + ECFieldElement A1 = W1.Subtract(W2).Multiply(Y1); + + X3 = dy.Square().Subtract(W1).Subtract(W2); + Y3 = W1.Subtract(X3).Multiply(dy).Subtract(A1); + Z3 = dx; + + if (Z1IsOne) + { + Z3Squared = C; + } + else + { + Z3 = Z3.Multiply(Z1); + } + } + else + { + ECFieldElement Z1Squared, U2, S2; + if (Z1IsOne) + { + Z1Squared = Z1; U2 = X2; S2 = Y2; + } + else + { + Z1Squared = Z1.Square(); + U2 = Z1Squared.Multiply(X2); + ECFieldElement Z1Cubed = Z1Squared.Multiply(Z1); + S2 = Z1Cubed.Multiply(Y2); + } + + bool Z2IsOne = Z2.IsOne; + ECFieldElement Z2Squared, U1, S1; + if (Z2IsOne) + { + Z2Squared = Z2; U1 = X1; S1 = Y1; + } + else + { + Z2Squared = Z2.Square(); + U1 = Z2Squared.Multiply(X1); + ECFieldElement Z2Cubed = Z2Squared.Multiply(Z2); + S1 = Z2Cubed.Multiply(Y1); + } + + ECFieldElement H = U1.Subtract(U2); + ECFieldElement R = S1.Subtract(S2); + + // Check if b == this or b == -this + if (H.IsZero) + { + if (R.IsZero) + { + // this == b, i.e. this must be doubled + return this.Twice(); + } + + // this == -b, i.e. the result is the point at infinity + return curve.Infinity; + } + + ECFieldElement HSquared = H.Square(); + ECFieldElement G = HSquared.Multiply(H); + ECFieldElement V = HSquared.Multiply(U1); + + X3 = R.Square().Add(G).Subtract(Two(V)); + Y3 = V.Subtract(X3).Multiply(R).Subtract(S1.Multiply(G)); + + Z3 = H; + if (!Z1IsOne) + { + Z3 = Z3.Multiply(Z1); + } + if (!Z2IsOne) + { + Z3 = Z3.Multiply(Z2); + } + + // Alternative calculation of Z3 using fast square + //X3 = four(X3); + //Y3 = eight(Y3); + //Z3 = doubleProductFromSquares(Z1, Z2, Z1Squared, Z2Squared).multiply(H); + + if (Z3 == H) + { + Z3Squared = HSquared; + } + } + + ECFieldElement[] zs; + if (coord == ECCurve.COORD_JACOBIAN_MODIFIED) + { + // TODO If the result will only be used in a subsequent addition, we don't need W3 + ECFieldElement W3 = CalculateJacobianModifiedW(Z3, Z3Squared); + + zs = new ECFieldElement[] { Z3, W3 }; + } + else + { + zs = new ECFieldElement[] { Z3 }; + } + + return new FpPoint(curve, X3, Y3, zs, IsCompressed); + } + default: { throw new InvalidOperationException("unsupported coordinate system"); @@ -661,7 +806,7 @@ namespace Org.BouncyCastle.Math.EC case ECCurve.COORD_HOMOGENEOUS: { - ECFieldElement Z1 = this.GetZCoord(0); + ECFieldElement Z1 = this.RawZCoords[0]; bool Z1IsOne = Z1.IsOne; @@ -689,6 +834,70 @@ namespace Org.BouncyCastle.Math.EC return new FpPoint(curve, X3, Y3, new ECFieldElement[] { Z3 }, IsCompressed); } + case ECCurve.COORD_JACOBIAN: + { + ECFieldElement Z1 = this.RawZCoords[0]; + + bool Z1IsOne = Z1.IsOne; + + ECFieldElement Y1Squared = Y1.Square(); + ECFieldElement T = Y1Squared.Square(); + + ECFieldElement a4 = curve.A; + ECFieldElement a4Neg = a4.Negate(); + + ECFieldElement M, S; + if (a4Neg.ToBigInteger().Equals(BigInteger.ValueOf(3))) + { + ECFieldElement Z1Squared = Z1IsOne ? Z1 : Z1.Square(); + M = Three(X1.Add(Z1Squared).Multiply(X1.Subtract(Z1Squared))); + S = Four(Y1Squared.Multiply(X1)); + } + else + { + ECFieldElement X1Squared = X1.Square(); + M = Three(X1Squared); + if (Z1IsOne) + { + M = M.Add(a4); + } + else if (!a4.IsZero) + { + ECFieldElement Z1Squared = Z1IsOne ? Z1 : Z1.Square(); + ECFieldElement Z1Pow4 = Z1Squared.Square(); + if (a4Neg.BitLength < a4.BitLength) + { + M = M.Subtract(Z1Pow4.Multiply(a4Neg)); + } + else + { + M = M.Add(Z1Pow4.Multiply(a4)); + } + } + //S = two(doubleProductFromSquares(X1, Y1Squared, X1Squared, T)); + S = Four(X1.Multiply(Y1Squared)); + } + + ECFieldElement X3 = M.Square().Subtract(Two(S)); + ECFieldElement Y3 = S.Subtract(X3).Multiply(M).Subtract(Eight(T)); + + ECFieldElement Z3 = Two(Y1); + if (!Z1IsOne) + { + Z3 = Z3.Multiply(Z1); + } + + // Alternative calculation of Z3 using fast square + //ECFieldElement Z3 = doubleProductFromSquares(Y1, Z1, Y1Squared, Z1Squared); + + return new FpPoint(curve, X3, Y3, new ECFieldElement[] { Z3 }, IsCompressed); + } + + case ECCurve.COORD_JACOBIAN_MODIFIED: + { + return TwiceJacobianModified(true); + } + default: { throw new InvalidOperationException("unsupported coordinate system"); @@ -762,6 +971,10 @@ namespace Org.BouncyCastle.Math.EC return new FpPoint(Curve, X4, Y4, IsCompressed); } + case ECCurve.COORD_JACOBIAN_MODIFIED: + { + return TwiceJacobianModified(false).Add(b); + } default: { return Twice().Add(b); @@ -807,6 +1020,10 @@ namespace Org.BouncyCastle.Math.EC ECFieldElement Y4 = (X1.Subtract(X4)).Multiply(L2).Subtract(Y1); return new FpPoint(Curve, X4, Y4, IsCompressed); } + case ECCurve.COORD_JACOBIAN_MODIFIED: + { + return TwiceJacobianModified(false).Add(this); + } default: { // NOTE: Be careful about recursions between twicePlus and threeTimes @@ -873,6 +1090,61 @@ namespace Org.BouncyCastle.Math.EC return new FpPoint(curve, XCoord, YCoord.Negate(), IsCompressed); } + + protected virtual ECFieldElement CalculateJacobianModifiedW(ECFieldElement Z, ECFieldElement ZSquared) + { + ECFieldElement a4 = this.Curve.A; + if (a4.IsZero) + return a4; + + if (ZSquared == null) + { + ZSquared = Z.Square(); + } + + ECFieldElement W = ZSquared.Square(); + ECFieldElement a4Neg = a4.Negate(); + if (a4Neg.BitLength < a4.BitLength) + { + W = W.Multiply(a4Neg).Negate(); + } + else + { + W = W.Multiply(a4); + } + return W; + } + + protected virtual ECFieldElement GetJacobianModifiedW() + { + ECFieldElement[] ZZ = this.RawZCoords; + ECFieldElement W = ZZ[1]; + if (W == null) + { + // NOTE: Rarely, twicePlus will result in the need for a lazy W1 calculation here + ZZ[1] = W = CalculateJacobianModifiedW(ZZ[0], null); + } + return W; + } + + protected FpPoint TwiceJacobianModified(bool calculateW) + { + ECFieldElement X1 = this.RawXCoord, Y1 = this.RawYCoord, Z1 = this.RawZCoords[0], W1 = GetJacobianModifiedW(); + + ECFieldElement X1Squared = X1.Square(); + ECFieldElement M = Three(X1Squared).Add(W1); + ECFieldElement _2Y1 = Two(Y1); + ECFieldElement _2Y1Squared = _2Y1.Multiply(Y1); + ECFieldElement S = Two(X1.Multiply(_2Y1Squared)); + ECFieldElement X3 = M.Square().Subtract(Two(S)); + ECFieldElement _4T = _2Y1Squared.Square(); + ECFieldElement _8T = Two(_4T); + ECFieldElement Y3 = M.Multiply(S.Subtract(X3)).Subtract(_8T); + ECFieldElement W3 = calculateW ? Two(_8T.Multiply(W1)) : null; + ECFieldElement Z3 = Z1.IsOne ? _2Y1 : _2Y1.Multiply(Z1); + + return new FpPoint(this.Curve, X3, Y3, new ECFieldElement[] { Z3, W3 }, IsCompressed); + } } /** @@ -961,7 +1233,7 @@ namespace Org.BouncyCastle.Math.EC ECFieldElement Y = L.Subtract(X).Multiply(X); if (ECCurve.COORD_LAMBDA_PROJECTIVE == coord) { - ECFieldElement Z = GetZCoord(0); + ECFieldElement Z = RawZCoords[0]; if (!Z.IsOne) { Y = Y.Divide(Z); @@ -1082,8 +1354,8 @@ namespace Org.BouncyCastle.Math.EC } case ECCurve.COORD_HOMOGENEOUS: { - ECFieldElement Y1 = this.RawYCoord, Z1 = this.GetZCoord(0); - ECFieldElement Y2 = b.RawYCoord, Z2 = b.GetZCoord(0); + ECFieldElement Y1 = this.RawYCoord, Z1 = this.RawZCoords[0]; + ECFieldElement Y2 = b.RawYCoord, Z2 = b.RawZCoords[0]; bool Z2IsOne = Z2.IsOne; @@ -1125,8 +1397,8 @@ namespace Org.BouncyCastle.Math.EC return b.AddSimple(this); } - ECFieldElement L1 = this.RawYCoord, Z1 = this.GetZCoord(0); - ECFieldElement L2 = b.RawYCoord, Z2 = b.GetZCoord(0); + 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; @@ -1267,7 +1539,7 @@ namespace Org.BouncyCastle.Math.EC case ECCurve.COORD_HOMOGENEOUS: case ECCurve.COORD_LAMBDA_PROJECTIVE: { - ECFieldElement Y1 = this.RawYCoord, Z1 = this.GetZCoord(0); + ECFieldElement Y1 = this.RawYCoord, Z1 = this.RawZCoords[0]; return new F2mPoint(curve, X1.Square(), Y1.Square(), new ECFieldElement[] { Z1.Square() }, IsCompressed); } default: @@ -1311,7 +1583,7 @@ namespace Org.BouncyCastle.Math.EC } case ECCurve.COORD_HOMOGENEOUS: { - ECFieldElement Y1 = this.RawYCoord, Z1 = this.GetZCoord(0); + ECFieldElement Y1 = this.RawYCoord, Z1 = this.RawZCoords[0]; bool Z1IsOne = Z1.IsOne; ECFieldElement X1Z1 = Z1IsOne ? X1 : X1.Multiply(Z1); @@ -1331,7 +1603,7 @@ namespace Org.BouncyCastle.Math.EC } case ECCurve.COORD_LAMBDA_PROJECTIVE: { - ECFieldElement L1 = this.RawYCoord, Z1 = this.GetZCoord(0); + ECFieldElement L1 = this.RawYCoord, Z1 = this.RawZCoords[0]; bool Z1IsOne = Z1.IsOne; ECFieldElement L1Z1 = Z1IsOne ? L1 : L1.Multiply(Z1); @@ -1413,13 +1685,13 @@ namespace Org.BouncyCastle.Math.EC // case ECCurve.COORD_LAMBDA_PROJECTIVE: // { // // NOTE: twicePlus() only optimized for lambda-affine argument - // ECFieldElement X2 = b.RawXCoord, Z2 = b.GetZCoord(0); + // ECFieldElement X2 = b.RawXCoord, Z2 = b.RawZCoords[0]; // if (X2.IsZero || !Z2.IsOne) // { // return Twice().Add(b); // } - // ECFieldElement L1 = this.RawYCoord, Z1 = this.GetZCoord(0); + // ECFieldElement L1 = this.RawYCoord, Z1 = this.RawZCoords[0]; // ECFieldElement L2 = b.RawYCoord; // ECFieldElement X1Sq = X1.Square(); @@ -1467,7 +1739,7 @@ namespace Org.BouncyCastle.Math.EC } case ECCurve.COORD_HOMOGENEOUS: { - ECFieldElement Y = this.RawYCoord, Z = this.GetZCoord(0); + ECFieldElement Y = this.RawYCoord, Z = this.RawZCoords[0]; return new F2mPoint(curve, X, Y.Add(X), new ECFieldElement[] { Z }, IsCompressed); } case ECCurve.COORD_LAMBDA_AFFINE: @@ -1478,7 +1750,7 @@ namespace Org.BouncyCastle.Math.EC case ECCurve.COORD_LAMBDA_PROJECTIVE: { // L is actually Lambda (X + Y/X) here - ECFieldElement L = this.RawYCoord, Z = this.GetZCoord(0); + ECFieldElement L = this.RawYCoord, Z = this.RawZCoords[0]; return new F2mPoint(curve, X, L.Add(Z), new ECFieldElement[] { Z }, IsCompressed); } default: |