Skip to main content
New
Stack Overflow Jobs powered by Indeed: A job site that puts thousands of tech jobs at your fingertips (U.S. only). Search jobs
4 of 5
added 97 characters in body
conchild
  • 675
  • 5
  • 18

Simple RSA proof of correctness using Bézout's identity

To show that $m^{ed} \equiv m \; (mod \; pq)$ with $de \equiv 1 \; (mod \; \phi(pq))$,

Choose $e$ coprime to $\phi(pq)$ so that $gcd(e,\phi(pq)) = 1$ and

$$m^{gcd(e,\phi(pq))} \equiv m \; (mod \; pq).$$

Using B├ęzout's identity we expand the gcd thus

$$m^{gcd(e,\phi(pq))} = m^{ed + \phi(pq)k} \; (mod \; pq)$$

where $d$ appears as the multiplicative inverse of $e$ and we expand the exponent

$$m^{ed + \phi(pq)k} = m^{ed} (m^{\phi(pq)})^{k} \; (mod \; pq)$$

By Fermat's little theorem this is reduced to

$$m^{ed} 1^{k} = m^{ed} \equiv m \; (mod \; pq)$$

which is the original claim.


Please review this simple proof and help me fix it, if it is not correct.

conchild
  • 675
  • 5
  • 18