-1

The actuall message M in the RSA system can be any number between 0 and n-1. The coded message R is also a number between 0 and n-1, but can it be any such number? I am litlle confuse about the question it asks, "can it be any such number?" so what number does it refer to? is it between 0 and n-1?

ssyylar
  • 9

2 Answers2

1

The RSA system (the textbook one, that sends $M$ to $M^e \mod N$) is bijective on the all $M$ with $\gcd(M,N) = 1$ or we could not decrypt. And we even know its inverse: $x \rightarrow x^d \mod N$. So it's a bijective map on $\{0,\ldots,N-1\}$, indeed. So not all $M$ in $\{0,\ldots,N-1\}$ can be messages, only those with no divisor with $N$ in common (so no factor $p$ or $q$ when $N = pq$ with $p,q$ both prime), call this set $M'$. And all those restricted $x \in M'$ can also be encrypted messages, as the power $d$ map is its inverse.

(Added) In fact, the system is a bijection, also for the bad messages that are multiples of $p$ or $q$, see these notes, e.g. So in practice one should never choose such $M$, but one could... And then all $\{0,\ldots,N_1\}$ occur as images, indeed.

Henno Brandsma
  • 242,131
  • @MorganRodgers one could check $\gcd(M,N)=1$. But if it failed, you would have broken the other person's key. Chances of this are very small for used sizes of keys. – Henno Brandsma Nov 01 '15 at 15:06
-1

The wording means can the coded message R potentially be every possible number from 0 to n-1 (for different messages M). Or are there some values which it is impossible for R to take.

For the message to uniquely decode every M must give a unique R. As M can be any possible value from 0 to n-1 then every value from 0 to n-1 must be possible for R.

Ian Miller
  • 11,844
  • so the answer should be yes? because I know the relationship between N and R and M is R^d congruent M (mod N), which means R^d=N*k+M , but I don't know how to justify this. – ssyylar Oct 31 '15 at 07:17