Re: RSA Proof using CRTs
 From: Kristian Gjøsteen <kristiag+news@xxxxxxxxxxxx>
 Date: Wed, 23 Jun 2010 08:13:56 +0000 (UTC)
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
.
 FollowUps:
 Re: RSA Proof using CRTs
 From: Bryan
 Re: RSA Proof using CRTs
 From: Wolfgang Ehrhardt
 Re: RSA Proof using CRTs
 References:
 RSA Proof using CRTs
 From: jeff
 RSA Proof using CRTs
 Prev by Date: Re: Encrypting odd sized buffers
 Next by Date: Re: Encrypting odd sized buffers
 Previous by thread: RSA Proof using CRTs
 Next by thread: Re: RSA Proof using CRTs
 Index(es):
Relevant Pages
