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)