Editing RSA cryptosystem (section)

==Proofs of correctness==

===Proof using Fermat's little theorem===
The proof of the correctness of RSA is based on [[Fermat's little theorem]], stating that {{math| ''a''<sup>''p'' − 1</sup> ≡ 1 (mod ''p'')}} for any integer {{mvar|a}} and prime {{mvar|p}}, not dividing {{mvar|a}}.{{refn|group=note|We cannot trivially break RSA by applying the theorem (mod ''pq'') because {{math|''pq''}} is not prime.}}

We want to show that
<math display="block">(m^e)^d \equiv m \pmod{pq}</math>
for every integer {{mvar|m}} when {{mvar|p}} and {{mvar|q}} are distinct prime numbers and {{mvar|e}} and {{mvar|d}} are positive integers satisfying {{math|1=''ed'' ≡ 1 (mod ''&lambda;''(''pq''))}}.

Since {{math|1=''&lambda;''(''pq'') = [[least common multiple|lcm]](''p'' − 1, ''q'' − 1)}} is, by construction, divisible by both {{math|''p'' − 1}} and {{math|''q'' − 1}}, we can write
<math display="block">ed - 1 = h(p - 1) = k(q - 1)</math>
for some nonnegative integers {{mvar|h}} and {{mvar|k}}.{{refn|group=note|In particular, the statement above holds for any {{mvar|e}} and {{mvar|d}} that satisfy {{math|1=''ed'' ≡ 1 (mod (''p'' − 1)(''q'' − 1))}}, since {{math|1=(''p'' − 1)(''q'' − 1)}} is divisible by {{math|1=''&lambda;''(''pq'')}}, and thus trivially also by {{math|''p'' − 1}} and {{math|''q'' − 1}}. However, in modern implementations of RSA, it is common to use a reduced private exponent {{mvar|d}} that only satisfies the weaker, but sufficient condition {{math|1=''ed'' ≡ 1 (mod ''&lambda;''(''pq''))}}.}}

To check whether two numbers, such as {{mvar|m''<sup>ed</sup>''}} and {{mvar|m}}, are congruent {{math|mod&nbsp;''pq''}}, it suffices (and in fact is equivalent) to check that they are congruent {{math|mod&nbsp;''p''}} and {{math|mod&nbsp;''q''}} separately.{{refn|group=note|This is part of the [[Chinese remainder theorem]], although it is not the significant part of that theorem.}}

To show {{math|''m<sup>ed</sup>'' ≡ ''m'' (mod ''p'')}}, we consider two cases:
# If {{math|''m'' ≡ 0 (mod ''p'')}}, {{mvar|m}} is a multiple of {{mvar|p}}. Thus ''m<sup>ed</sup>'' is a multiple of {{mvar|p}}. So {{math|''m<sup>ed</sup>'' ≡ 0 ≡ ''m'' (mod ''p'')}}. 
# If {{math|''m'' <math>\not\equiv</math> 0 (mod ''p'')}}, 
#: <math>m^{ed} = m^{ed - 1} m = m^{h(p - 1)} m = (m^{p - 1})^h m \equiv 1^h m \equiv m \pmod{p},</math>
#: where we used [[Fermat's little theorem]] to replace {{math|''m''<sup>''p''−1</sup> mod ''p''}} with 1.

The verification that {{math|''m<sup>ed</sup>'' ≡ ''m'' (mod ''q'')}} proceeds in a completely analogous way:
# If {{math|''m'' ≡ 0 (mod ''q'')}}, ''m<sup>ed</sup>'' is a multiple of {{mvar|q}}. So {{math|''m<sup>ed</sup>'' ≡ 0 ≡ ''m'' (mod ''q'')}}. 
# If {{math|''m'' <math>\not\equiv</math> 0 (mod ''q'')}},
#: <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 {{mvar|m}}, and integers {{mvar|e}}, {{mvar|d}} such that {{math|1=''ed'' ≡ 1 (mod ''&lambda;''(''pq''))}},
<math display="block">(m^e)^d \equiv m \pmod{pq}.</math>

====Notes====
{{reflist|group=note}}

===Proof using Euler's theorem===
Although the original paper of Rivest, Shamir, and Adleman used Fermat's little theorem to explain why RSA works, it is common to find proofs that rely instead on [[Euler's theorem]].

We want to show that {{math|''m<sup>ed</sup>'' ≡ ''m'' (mod ''n'')}}, where {{math|1=''n'' = ''pq''}} is a product of two different prime numbers, and {{mvar|e}} and {{mvar|d}} are positive integers satisfying {{math|''ed'' ≡ 1 (mod ''&phi;''(''n''))}}. Since {{mvar|e}} and {{mvar|d}} are positive, we can write {{math|1=''ed'' = 1 + ''h&phi;''(''n'')}} for some non-negative integer {{mvar|h}}. ''Assuming'' that {{mvar|m}} is relatively prime to {{mvar|n}}, we have
<math display="block">m^{ed} = m^{1 + h\varphi(n)} = m (m^{\varphi(n)})^h \equiv m (1)^h \equiv m \pmod{n},</math>

where the second-last congruence follows from [[Euler's theorem]].

More generally, for any {{mvar|e}} and {{mvar|d}} satisfying {{math|''ed'' ≡ 1 (mod ''&lambda;''(''n''))}}, the same conclusion follows from [[Carmichael function#Carmichael's theorem|Carmichael's generalization of Euler's theorem]], which states that {{math|''m''<sup>''&lambda;''(n)</sup> ≡ 1 (mod ''n'')}} for all {{mvar|m}} relatively prime to {{mvar|n}}.

When {{mvar|m}} is not relatively prime to {{mvar|n}}, the argument just given is invalid. This is highly improbable (only a proportion of {{math|1/''p'' + 1/''q'' − 1/(''pq'')}} numbers have this property), but even in this case, the desired congruence is still true. Either {{math|''m'' ≡ 0 (mod ''p'')}} or {{math|''m'' ≡ 0 (mod ''q'')}}, and these cases can be treated using the previous proof.