Page 1 of 1

Problems with modular inversion

PostPosted: Sat Mar 26, 2016 3:51 am
by swbrenneis
First, thank you for this wonderful library. It's been a lifesaver.

I am using the ZZ class for a cryptography project. I am generating RSA keys, and using the Chinese Remainder Theorem RSASP1 primitive. One of the quantities needed is the modular inverse of the two primes, p and q : qInv = 1/q mod p; In the tests I'm running, 3 <= p <= 2^512 - 1 and 3 <= q <= 2^512 -1. When I call InvMod(q, p) I get a LogicError exception thrown about 50% of the time. It says that the first input is too large. I don't see that error mentioned in the documentation for the ZZ class. When I track it down in the code, it seems to be coming from an _ntl_gcompare operation when a >= n (q >= p) in g_lip_impl.h. Both q and p are of type ZZ.

I am not sure why this limitation exists. Both p and q are prime and greater than 0, so the inverse should exist. Am I missing something?

Thank you.

Re: Problems with modular inversion

PostPosted: Sun Mar 27, 2016 6:50 pm
by swbrenneis

By coding the extended Euclidean algorithm. I was able to successfully complete the operation 100% of the time. If this is not a configuration error on my part, it would seem to be a bug. A similar error seems to exist in the PowerMod function. By coding the function using modular exponentiation by squaring, the operation is successful 100% of the time.

Re: Problems with modular inversion

PostPosted: Wed Apr 20, 2016 8:46 pm
by victorshoup
Sorry for the delay getting back to you.
For some reason, I wasn't getting activity notifications on the board.

Anyway, yes...if you call InvMod(a, n), you have to have 0 <= a < n.
That should be clear in the documentation (I hope).
If need be, you can always use the rem function to reduce a mod n first.