# Re: RSA Proof using CRTs

jeff <dude000@xxxxxxxxx> wrote:
Assuming that p, q, dP, dQ, and qInv are known, this is as far as I
have got using the chinese remainder theorem:

m= ( c^dP . q (qInv mod p) + c^dQ . p (pInv mod q) ) mod (pq)

but the according to the 2nd method the following is how m can be
calculated (and I hope i translated it properly):

m = c^dQ mod q + ( ( c^dQ mod q - c^dP mod p ) . qInv mod p).q

I think this is wrong, the + should be -. Because then modulo q we have

m = c^dQ = (m^e)^dQ = m (mod q)

and modulo p

m = c^dQ mod q - (c^dQ mod q - c^dP mod p) * 1
= c^dP = (m^e)^dP = m (mod p) .

When two integers are congruent modulo p and modulo q, CRT says they
are congruent modulo p*q.

--
kg
.

## Relevant Pages

• Re: polynomials over Z_p
... Suppose that a and b are not congruent modulo p; ... and so we can cancel them modulo p to get ... fwill define a permutation if and only if there does not ...
(sci.math)
• Re: inverse modulos
... use of the extended Euclidean algorithm, but it's not giving the result ... The inverse of a modulo m is unique *modulo m*, ... congruent modulo 5 (i.e. they differ from each other by a multiple ...
(sci.math)
• Re: RSA Proof using CRTs
... Because then modulo q we have ... When two integers are congruent modulo p and modulo q, CRT says they ... is the keyword 'Garner's algorithm'. ...
(sci.crypt)
• Re: polynomials over Z_p
... fwill define a permutation if and only if there does not ... exist a and b, not congruent modulo p, such that u= -v. ... But in the rest of your explanation I'm ... multiplicative inverse of u modulo p. ...
(sci.math)
• Re: RSA Proof using CRTs
... have got using the chinese remainder theorem: ... Because then modulo q we have ... When two integers are congruent modulo p and modulo q, CRT says they ...
(sci.crypt)