diff options
| -rw-r--r-- | integer.cpp | 20 | ||||
| -rw-r--r-- | integer.h | 5 | ||||
| -rw-r--r-- | test.cpp | 8 | ||||
| -rw-r--r-- | validat0.cpp | 122 | ||||
| -rw-r--r-- | validate.h | 4 |
5 files changed, 152 insertions, 7 deletions
diff --git a/integer.cpp b/integer.cpp index e9846bde..cf6c6ee9 100644 --- a/integer.cpp +++ b/integer.cpp @@ -4380,7 +4380,20 @@ Integer Integer::InverseMod(const Integer &m) const CRYPTOPP_ASSERT(m.NotNegative());
if (IsNegative())
- return Modulo(m).InverseMod(m);
+ return Modulo(m).InverseModNext(m);
+
+ // Place *this in the range [0, 2m-1]
+ // http://github.com/weidai11/cryptopp/issues/602
+ if (*this >= (m << 1))
+ return Modulo(m).InverseModNext(m);
+
+ return InverseModNext(m);
+}
+
+Integer Integer::InverseModNext(const Integer &m) const
+{
+ CRYPTOPP_ASSERT(m.NotNegative());
+ CRYPTOPP_ASSERT(*this < 2*m);
if (m.IsEven())
{
@@ -4389,11 +4402,12 @@ Integer Integer::InverseMod(const Integer &m) const if (*this == One())
return One();
- Integer u = m.Modulo(*this).InverseMod(*this);
+ Integer u = m.Modulo(*this).InverseModNext(*this);
return !u ? Zero() : (m*(*this-u)+1)/(*this);
}
- SecBlock<word> T(m.reg.size() * 4);
+ // AlmostInverse requires a 4x workspace
+ IntegerSecBlock T(m.reg.size() * 4);
Integer r((word)0, m.reg.size());
unsigned k = AlmostInverse(r.reg, T, reg, reg.size(), m.reg, m.reg.size());
DivideByPower2Mod(r.reg, r.reg, k, m.reg, m.reg.size());
@@ -630,6 +630,11 @@ public: CRYPTOPP_DLL friend Integer CRYPTOPP_API a_exp_b_mod_c(const Integer &x, const Integer& e, const Integer& m);
#endif
+protected:
+
+ // https://github.com/weidai11/cryptopp/issues/602
+ Integer InverseModNext(const Integer &n) const;
+
private:
Integer(word value, size_t length);
@@ -956,12 +956,14 @@ bool Validate(int alg, bool thorough, const char *seedInput) case 9998: result = TestPolynomialMod2(); break;
// http://github.com/weidai11/cryptopp/issues/336
case 9997: result = TestIntegerBitops(); break;
+ // http://github.com/weidai11/cryptopp/issues/602
+ case 9996: result = TestIntegerOps(); break;
// http://github.com/weidai11/cryptopp/issues/360
- case 9996: result = TestRounding(); break;
+ case 9995: result = TestRounding(); break;
// http://github.com/weidai11/cryptopp/issues/242
- case 9995: result = TestHuffmanCodes(); break;
+ case 9994: result = TestHuffmanCodes(); break;
// http://github.com/weidai11/cryptopp/issues/346
- case 9994: result = TestASN1Parse(); break;
+ case 9993: result = TestASN1Parse(); break;
#endif
default: return false;
diff --git a/validat0.cpp b/validat0.cpp index 6ee466bd..9ff983c3 100644 --- a/validat0.cpp +++ b/validat0.cpp @@ -3193,6 +3193,128 @@ bool TestIntegerBitops() return opa && opo && opx;
}
+
+bool TestIntegerOps()
+{
+ std::cout << "\nTesting Integer operations...\n\n";
+ bool pass=true, result;
+
+ // http://github.com/weidai11/cryptopp/issues/602
+ Integer a("0x2F0500010000018000000000001C1C000000000000000A000B0000000000000000000000000000FDFFFFFF00000000");
+ Integer b("0x3D2F050001");
+
+ result = (0x3529E4FEBC == a.InverseMod(b));
+ pass = result && pass;
+ if (!result)
+ std::cout << "FAILED: InverseMod operation\n";
+
+ RandomNumberGenerator& prng = GlobalRNG();
+ for (unsigned int i=0; i<128; ++i)
+ {
+ Integer a(prng, 1024), m(prng, 1024);
+ a++, m++; // make non-0
+
+ // Corner cases
+ switch (i)
+ {
+ case 0:
+ a = 0;
+ break;
+ case 1:
+ a = m-1;
+ break;
+ case 2:
+ a = m;
+ break;
+ case 3:
+ a = m+1;
+ break;
+ case 4:
+ a = 2*m-1;
+ break;
+ case 5:
+ a = 2*m;
+ break;
+ case 6:
+ a = 2*m+1;
+ break;
+ case 7:
+ a = (m<<256)-1;
+ break;
+ case 8:
+ a = (m<<256);
+ break;
+ case 9:
+ a = (m<<256)+1;
+ default:
+ ;;
+ }
+
+ Integer x = a.InverseMod(m);
+ Integer y = (a % m).InverseMod(m);
+ Integer z = (a * y).Modulo(m);
+
+ if (GCD(a,m) == 1) // coprime?
+ result = (x == y) && (z == 1) && (a_times_b_mod_c(a, x, m) == 1);
+ else
+ result = (x == y);
+
+ pass = result && pass;
+ if (!result)
+ std::cout << "FAILED: InverseMod operation\n";
+ }
+
+ for (unsigned int i=0; i<128; ++i)
+ {
+ Integer m(prng, 32);
+ m++; // make non-0
+
+ for (unsigned int j=0; j<256; j+=4)
+ {
+ Integer a((m << j)-1);
+
+ Integer x = a.InverseMod(m);
+ Integer y = (a % m).InverseMod(m);
+ Integer z = (a * y).Modulo(m);
+
+ if (GCD(a,m) == 1) // coprime?
+ result = (x == y) && (z == 1) && (a_times_b_mod_c(a, x, m) == 1);
+ else
+ result = (x == y);
+
+ pass = result && pass;
+ if (!result)
+ std::cout << "FAILED: InverseMod operation\n";
+ }
+ }
+
+ for (unsigned int i=0; i<128; ++i)
+ {
+ Integer a(prng, 4096), m(prng, 32);
+ a++, m++; // make non-0
+
+ Integer x = a.InverseMod(m);
+ Integer y = (a % m).InverseMod(m);
+ Integer z = (a * y).Modulo(m);
+
+ if (GCD(a,m) == 1) // coprime?
+ result = (x == y) && (z == 1) && (a_times_b_mod_c(a, x, m) == 1);
+ else
+ result = (x == y);
+
+ pass = result && pass;
+ if (!result)
+ std::cout << "FAILED: InverseMod operation\n";
+ }
+
+ if (pass)
+ std::cout << "passed:";
+ else
+ std::cout << "FAILED:";
+ std::cout << " Integer::InverseMod operations\n";
+
+ return pass;
+}
#endif
NAMESPACE_END // Test
@@ -128,6 +128,8 @@ bool TestSecBlock(); bool TestPolynomialMod2();
// http://github.com/weidai11/cryptopp/issues/336
bool TestIntegerBitops();
+// http://github.com/weidai11/cryptopp/issues/602
+bool TestIntegerOps();
// http://github.com/weidai11/cryptopp/issues/360
bool TestRounding();
// http://github.com/weidai11/cryptopp/issues/242
@@ -189,7 +191,7 @@ private: };
#endif
-// Safer functions on Windows for C&A, https://github.com/weidai11/cryptopp/issues/55
+// Safer functions on Windows for C&A, http://github.com/weidai11/cryptopp/issues/55
inline std::string TimeToString(const time_t& t)
{
#if (CRYPTOPP_MSC_VERSION >= 1400)
|