RSA (cryptosystem): Difference between revisions

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
(Reverted to revision 792345786 by Timtempleton (talk): Completing vandalism revert. (TW))
(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)
 
We want to show that {{nowrap|''m<sup>ed</sup>'' ≡ ''m'' (mod ''pq'')}} for every integer ''m'' when ''p'' and ''q'' are distinct prime numbers and ''e'' and ''d'' are positive integers satisfying
: <math>e d \equiv 1 \pmod{\lambda(p-1)(q-1pq)}.</math>
 
Since {{nowrap|1=''λ''(''pq'') = lcm(''p'' − 1, ''q'' − 1)}} is, by construction, divisible by both {{nowrap|p − 1}} and {{nowrap|q − 1}}, we can write
Write
: <math>ed - 1 = h(p - 1) = k(q - 1)</math>
for some nonnegative integers ''h'' and ''k''.
 
: <math>m^{ed} = m^{ed - 1} m = m^{k(q - 1)} m = (m^{q - 1})^k m \equiv 1^k m \equiv m \pmod{q}</math>
 
This completes the proof that, for any integer ''m'', and integers ''e'', ''d'' such that <math>e d \equiv 1 \pmod{\lambda(p-1)(q-1pq)}</math>,
: <math>(m^e)^d \equiv m \pmod{pq}.</math>