RSA proof regarding m % n I have a question regarding the proof that RSA works
I understand that $m^{(ed \bmod z)} \bmod n = m \bmod n$ , but I don't understand why $m \bmod n = m$
(This question assumes m is the message, $z=(p-1)(q-1)$, $d$ is such that $(ed \bmod z) = 1$, and $e$ is such that $e$ is relatively prime with $z$)
All is solved in the comments, but I thought this would be a good opportunity to tell a real story. I was once called urgently by a company that I consulted for due to a bug discovered by their QA department. When they encrypted and decrypted with plain RSA, they would sometimes not get the same input back. The problem was simple, they were using RSA1024 at the time (many years ago) and would take random 1024-bit strings as input. But as good QA people, they also tested the &quot;edge cases&quot;, so they would encrypt the string of all zeroes and the string of all ones. Needless to say, the string of all ones would not decrypt correctly. This is exactly the case that $m \geq n$ and so &quot;decryption&quot; indeed doesn't work. It's a nice story and just goes to show that even QAing crypto requires some math understanding!