RSA Proof using CRTs
in [Cryptography]
|
Prev: Scalar methods in the XY plane.
Next: sphlib-2.1
From: jeff on 22 Jun 2010 19:41 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
From: Kristian Gj�steen on 23 Jun 2010 04:13 jeff <dude000(a)gmail.com> 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
From: Wolfgang Ehrhardt on 23 Jun 2010 12:16 On Wed, 23 Jun 2010 08:13:56 +0000 (UTC), Kristian Gj�steen <kristiag+news(a)math.ntnu.no> wrote: >jeff <dude000(a)gmail.com> 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. I think the '+' is correct, c.f. the RSADP primitive from PKCS #1 V2.x with the parameters (p, q, dp, dq, qinv) m1 = c^dp mod p m2 = c^dq mod q h = (m1-m2)*qinv mod p m = m2+q*h Jeff's expression combines these steps into a one-liner. The number-theoretic background is Garner's algorithm for CRT with just two moduli.
From: Wolfgang Ehrhardt on 23 Jun 2010 12:26 On Wed, 23 Jun 2010 16:16:02 GMT, WE(a)completely.invalid (Wolfgang Ehrhardt) wrote: >On Wed, 23 Jun 2010 08:13:56 +0000 (UTC), Kristian Gj�steen ><kristiag+news(a)math.ntnu.no> wrote: > >>jeff <dude000(a)gmail.com> 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. > >I think the '+' is correct, c.f. the RSADP primitive from PKCS #1 V2.x >with the parameters (p, q, dp, dq, qinv) > >m1 = c^dp mod p >m2 = c^dq mod q >h = (m1-m2)*qinv mod p >m = m2+q*h > >Jeff's expression combines these steps into a one-liner. The >number-theoretic background is Garner's algorithm for CRT with just >two moduli. Sorry, Kristian! I first overlooked your second '-'. What remains is the keyword 'Garner's algorithm'. Wolfgang
From: Bryan on 23 Jun 2010 13:25
Kristian Gjøsteen wrote: > jeff 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 -. Sort of. The problem is that the terms inside the inner-most parenthesis are reversed. It should be: m = c^dQ mod q + ( ( c^dP mod p - c^dQ mod q) . qInv mod p).q Is flipping the + to - equivalent to reversing the difference? I'd say not quite, because for this algorithm when we say "mod p" we mean the least residue mod p. The expression: ( c^dP mod p - c^dQ mod q) . qInv mod p is evaluated mod p and and is thus an integer in [0..p). The resulting m is always in the range [0..n) where n=p*q, without the need for any final "mod n". > 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. Right. The only issue is that the result might be negative, which we would fix by adding n=p*q. The corrected version I showed avoids that final simple step. -- --Bryan Olson |