Fix incorrect InverseMod (GH #602)

cryptest.sh revealed a corner case still producing an incorrect result. We need to check for '*this > m', not '*this > 2m-1'.

The corner case looks obscure. The failure surfaced as 1 failed self test for about every 2048 tests. It was also in a code path where 'a' was explicitly set to '2m-1', with 'm' random.

The test result can be duplicated with 'cryptest.exe v 9996 1521969687'. The value '1521969687' is a seed for the random number generator to reproduce.

1 files changed, 1 insertions, 2 deletions

diff --git a/integer.cpp b/integer.cpp
index cf6c6ee9..48ae5470 100644
--- a/integer.cpp
+++ b/integer.cpp
@@ -4382,9 +4382,8 @@ Integer Integer::InverseMod(const Integer &m) const
 	if (IsNegative())

 		return Modulo(m).InverseModNext(m);

 

-	// Place *this in the range [0, 2m-1]

 	// http://github.com/weidai11/cryptopp/issues/602

-	if (*this >= (m << 1))

+	if (*this > m)

 		return Modulo(m).InverseModNext(m);

 

 	return InverseModNext(m);