diff options
| -rw-r--r-- | crypto/src/crypto/parameters/DHPublicKeyParameters.cs | 100 | ||||
| -rw-r--r-- | crypto/src/math/raw/Nat.cs | 28 |
2 files changed, 122 insertions, 6 deletions
diff --git a/crypto/src/crypto/parameters/DHPublicKeyParameters.cs b/crypto/src/crypto/parameters/DHPublicKeyParameters.cs index e7aeeff19..19e732b89 100644 --- a/crypto/src/crypto/parameters/DHPublicKeyParameters.cs +++ b/crypto/src/crypto/parameters/DHPublicKeyParameters.cs @@ -2,6 +2,8 @@ using System; using Org.BouncyCastle.Asn1; using Org.BouncyCastle.Math; +using Org.BouncyCastle.Math.Raw; +using Org.BouncyCastle.Utilities; namespace Org.BouncyCastle.Crypto.Parameters { @@ -13,18 +15,33 @@ namespace Org.BouncyCastle.Crypto.Parameters if (y == null) throw new ArgumentNullException("y"); + BigInteger p = dhParams.P; + // TLS check - if (y.CompareTo(BigInteger.Two) < 0 || y.CompareTo(dhParams.P.Subtract(BigInteger.Two)) > 0) + if (y.CompareTo(BigInteger.Two) < 0 || y.CompareTo(p.Subtract(BigInteger.Two)) > 0) throw new ArgumentException("invalid DH public key", "y"); - // we can't validate without Q. - if (dhParams.Q != null - && !y.ModPow(dhParams.Q, dhParams.P).Equals(BigInteger.One)) + BigInteger q = dhParams.Q; + + // We can't validate without Q. + if (q == null) + return y; + + if (p.TestBit(0) + && p.BitLength - 1 == q.BitLength + && p.ShiftRight(1).Equals(q)) { - throw new ArgumentException("y value does not appear to be in correct group", "y"); + // Safe prime case + if (1 == Legendre(y, p)) + return y; + } + else + { + if (BigInteger.One.Equals(y.ModPow(q, p))) + return y; } - return y; + throw new ArgumentException("value does not appear to be in correct group", "y"); } private readonly BigInteger y; @@ -75,5 +92,76 @@ namespace Org.BouncyCastle.Crypto.Parameters { return y.GetHashCode() ^ base.GetHashCode(); } + + private static int Legendre(BigInteger a, BigInteger b) + { + //int r = 0, bits = b.IntValue; + + //for (;;) + //{ + // int lowestSetBit = a.GetLowestSetBit(); + // a = a.ShiftRight(lowestSetBit); + // r ^= (bits ^ (bits >> 1)) & (lowestSetBit << 1); + + // int cmp = a.CompareTo(b); + // if (cmp == 0) + // break; + + // if (cmp < 0) + // { + // BigInteger t = a; a = b; b = t; + + // int oldBits = bits; + // bits = b.IntValue; + // r ^= oldBits & bits; + // } + + // a = a.Subtract(b); + //} + + //return BigInteger.One.Equals(b) ? (1 - (r & 2)) : 0; + + int bitLength = b.BitLength; + uint[] A = Nat.FromBigInteger(bitLength, a); + uint[] B = Nat.FromBigInteger(bitLength, b); + + int r = 0; + + int len = B.Length; + for (;;) + { + while (A[0] == 0) + { + Nat.ShiftDownWord(len, A, 0); + } + + int shift = Integers.NumberOfTrailingZeros((int)A[0]); + if (shift > 0) + { + Nat.ShiftDownBits(len, A, shift, 0); + int bits = (int)B[0]; + r ^= (bits ^ (bits >> 1)) & (shift << 1); + } + + int cmp = Nat.Compare(len, A, B); + if (cmp == 0) + break; + + if (cmp < 0) + { + r ^= (int)(A[0] & B[0]); + uint[] t = A; A = B; B = t; + } + + while (A[len - 1] == 0) + { + len = len - 1; + } + + Nat.Sub(len, A, B, A); + } + + return Nat.IsOne(len, B) ? (1 - (r & 2)) : 0; + } } } diff --git a/crypto/src/math/raw/Nat.cs b/crypto/src/math/raw/Nat.cs index 8ec328d11..69942661f 100644 --- a/crypto/src/math/raw/Nat.cs +++ b/crypto/src/math/raw/Nat.cs @@ -278,6 +278,34 @@ namespace Org.BouncyCastle.Math.Raw //} } + public static int Compare(int len, uint[] x, uint[] y) + { + for (int i = len - 1; i >= 0; --i) + { + uint x_i = x[i]; + uint y_i = y[i]; + if (x_i < y_i) + return -1; + if (x_i > y_i) + return 1; + } + return 0; + } + + public static int Compare(int len, uint[] x, int xOff, uint[] y, int yOff) + { + for (int i = len - 1; i >= 0; --i) + { + uint x_i = x[xOff + i]; + uint y_i = y[yOff + i]; + if (x_i < y_i) + return -1; + if (x_i > y_i) + return 1; + } + return 0; + } + public static void Copy(int len, uint[] x, uint[] z) { Array.Copy(x, 0, z, 0, len); |