RSA (cryptosystem): Difference between revisions

→‎Proof using Fermat's little theorem: add note about modern RSA implementations often not requiring ed ≡ 1 (mod (p − 1)(q − 1)) but only ed ≡ 1 (mod λ(pq))
(Undid revision 772388398 by Special:Contributions/2600:1000:B12D:A28F:2D62:F629:5451:F9CF: using phi(pq)=(p-1)(q-1) instead of lambda(pq) here gives a weaker result that doesn't actually prove the correctness of RSA as commonly used today)
(→‎Proof using Fermat's little theorem: add note about modern RSA implementations often not requiring ed ≡ 1 (mod (p − 1)(q − 1)) but only ed ≡ 1 (mod λ(pq)))
: <math>e d \equiv 1 \pmod{\lambda(pq)}.</math>
 
Since {{nowrap|1=''λ''(''pq'') = [[least common multiple|lcm]](''p'' − 1, ''q'' − 1)}} is, by construction, divisible by both {{nowrap|''p'' − 1}} and {{nowrap|''q'' − 1}}, we can write
: <math>ed - 1 = h(p - 1) = k(q - 1)</math>
for some nonnegative integers ''h'' and ''k''.
 
(Note: In particular, any ''e'' and ''d'' that satisfy {{nowrap|1=''ed'' ≡ 1 (mod (''p'' − 1)(''q'' − 1))}} also satisfy the congruences above, since {{nowrap|1=(''p'' − 1)(''q'' − 1)}} is divisible by {{nowrap|1=''λ''(''pq'')}}, and thus trivially also by {{nowrap|''p'' − 1}} and {{nowrap|''q'' − 1}}. However, in modern RSA implementations it's common to use a reduced private exponent ''d'' that only satisfies the weaker but sufficient condition {{nowrap|1=''ed'' ≡ 1 (mod ''λ''(''pq''))}}.)
 
To check whether two numbers, like ''m<sup>ed</sup>'' and ''m'', are congruent mod ''pq'' it suffices (and in fact is equivalent) to check they are congruent mod ''p'' and mod ''q'' separately. (This is part of the [[Chinese remainder theorem]], although it is not the significant part of that theorem.) To show {{nowrap|''m<sup>ed</sup>'' ≡ ''m'' (mod ''p'')}}, we consider two cases: {{nowrap|''m'' ≡ 0 (mod ''p'')}} and {{nowrap|''m'' <math>\not\equiv</math> 0 (mod ''p'')}}.