there's a lot of mathematical proofs of the original RSA algorithm
around. However I have not found one that describes the 2nd
alternative using prime factors or CRT.

Could someone please shed some light on the mathematics behind the 2nd
method as described in PKCS#1 v2.0 and above?

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

so somehow mathematically I must go from mod(pq) to mod(p) or mod(q)
only. Obviously i'm missing a few theorems on Number Theory in
between.

thanks
jeff

[ reply ]