|
According to the wiki article on the RSA encryption function, the valid range of input $m$ is $0 \leq m \lt n$. However I have found that the following values of $m$ always return themselves when encrypted:
Have I implemented the algorithm incorrectly or am I misreading the wiki article? |
||||
|
|
|
Yes, this is textbook RSA, so by definition: $0^e \equiv 0 \pmod{n}$ $1^e \equiv 1 \pmod{n}$ $(n - 1)^e \equiv (-1)^e \equiv -1 \equiv n - 1 \pmod{n}$ (since $e$ must be odd as $\varphi{(n)}$ is even and thus $2$ has no modular inverse modulo $\varphi{(n)}$) This is (obviously) bad since an observer can immediately deduce the plaintext for those messages even without knowing the decryption exponent, but normally you use padding in real life RSA which makes those kind of inputs essentially impossible. However you are wrong for $n - 2$. It does not necessarily encrypt to itself. How did you get that? You must be making some mistake in your implementation, or perhaps got lucky with a few small inputs. Counterexample, $n = 377$, $e = 17$ ($d = 257$, $\varphi{(377)} = 336$): $(n - 2)^e \equiv 375^{17} \equiv 124 \pmod{377}$ Are you sure you are calculating $e$ right? |
||||
|
