From: Erik De Bonte [mailto:[EMAIL PROTECTED]
Sent: Wednesday, February 11, 2004 11:52 AM
To: [EMAIL PROTECTED]
Subject: DivideByZero exception from InvertibleRSAFunction(n, e, d)
I just upgraded from Crypto++ 4.2 to 5.1 and I've run into what I believe is a bug in InvertibleRSAFunction::Initialize(n, e, d).
If you generate a new RSA key with Crypto++ 5.1 (via InvertibleRSAFunction::Initialize(rng, keysize)) and then take the modulus, pub exponent, and priv exponent (n, e, d) and initialize another InvertibleRSAFunction with them, about 22% of keys (based on my experiments) will cause a DivideByZero exception in PositiveDivide (line 3481 of integer.cpp) while calculating m_dp (m_dp = m_d % (m_p-1)) because Initialize believes that m_p is 1. The other 78% of the keys never cause this exception.
InvertibleRSAFunction objects that generate the exception work fine for me (encrypting and decrypting), but I'd guess that CalculateInverse (which seems to be the only method that uses p, q, u, dp, and dq) wouldn't work properly on them. What's CalculateInverse used for anyhow?
I've included source for a small program that reproduces the problem. It loops generating keys and logs the number of keys that throw the DivideByZero exception and the number that don't. In a recent test I got 2211 failures out of 10000 keys generated. Btw, I also see the DivideByZero exception when using keys generated with Crypto++ 4.2. I'm not sure if the frequency of this "bad case" is the same, but I assume that it is.
As a workaround, I'm considering removing the p, q, u, dp, and dq members from InvertibleRSAFunction since I don't seem to need them for anything once keys are generated. If I find that I need to call CalculateInverse for something, I believe ModularExponentiation(x, d, n) worked for me back in 4.2. Maybe I'm wrong about that, or perhaps it's slower than the current implementation?
Any thoughts would be appreciated. Am I doing something wrong? Is there a bug that's obvious and easy to fix? If not, would you expect any problems with my workaround?
Thanks,
Erik
#include <rsa.h>
#include <osrng.h>
const unsigned int USER_KEY_MODULUS_SIZE = 96;
int main(int argc, char** argv)
{
const unsigned int aNumKeysToGenerate = 10000;
unsigned int aNumSuccesses = 0;
unsigned int aNumFailures = 0;
CryptoPP::AutoSeededRandomPool aRandomNumberGenerator;
for (unsigned int iKey = 1; iKey <= aNumKeysToGenerate; ++iKey)
{
try
{
//
create a new RSA key pair
CryptoPP::InvertibleRSAFunction aKey;
aKey.Initialize(aRandomNumberGenerator, USER_KEY_MODULUS_SIZE*8);
//
validate the key
bool
bValid = false;
bValid = aKey.Validate(aRandomNumberGenerator, 2);
if
(!bValid)
__asm
int 3;
//
create a new RSA object based on the key's n, e, and d components
CryptoPP::InvertibleRSAFunction aKey2;
aKey2.Initialize(aKey.GetModulus(), aKey.GetPublicExponent(),
aKey.GetPrivateExponent());
//
validate the new RSA object
bValid = aKey2.Validate(aRandomNumberGenerator, 2);
if
(!bValid)
__asm
int 3;
++aNumSuccesses;
printf(".");
}
catch
(CryptoPP::Exception e)
{
++aNumFailures;
printf("!");
}
}
printf("Out of %d keys: %d successes, %d failures.\n", aNumKeysToGenerate, aNumSuccesses, aNumFailures);
return 0;
}
_________________________________________________
Scanned on 11 Feb 2004 19:51:13
Scanning by http://erado.com
_________________________________________________
Scanned on 11 Feb 2004 22:59:44
Scanning by http://erado.com
_________________________________________________
Scanned on 16 Mar 2004 18:25:22
Scanning by http://erado.com
