Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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:

  • $0$
  • $1$
  • $n - 1$
  • $n - 2$

Have I implemented the algorithm incorrectly or am I misreading the wiki article?

share|improve this question

1 Answer 1

up vote 5 down vote accepted

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?

share|improve this answer
    
Indeed. And that's why RSA is used with padding, to ensure that values like that cannot occur, and to ensure that the same message will have different encryptions at different times (which is another desirable property: the ciphertext leaks as little information as possible). –  Henno Brandsma Oct 7 '12 at 14:46

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.