1
$\begingroup$

In RSA encryption, we use $c = M^e (mod N)$ where $(e, N)$ is the public key, $M$ is the plaintext message, and $c$ is the encrypted message or ciphertext.

How do we know all message $M$ (for $M<N$) will result in a unique $c$ value? Isn't it possible there exists two numbers $M_1$ and $M_2$ such that $M_1^e (mod N) = M_2^3 (mod N)$?

Thanks.

$\endgroup$
1
$\begingroup$

Obviously you must assume that your parameters are valid RSA, e.g. you must have $c\ne 0$ etc. Let $N=p\times q\;$ with $p,q$ odd primes, the private exponent $d$ with $e d \equiv 1 \pmod {\varphi(N)}$, and thus $(M^e)^d \equiv M \pmod N\;$ for all $M$ (here is a Proof of correctness). Now assume $$\left(M_1^e\right)^d \equiv\left(M_2^e\right)^d \pmod N.$$ Since we assume valid RSA we have $$M_1 \equiv \left(M_1^e\right)^d \equiv \left(M_2^e\right)^d \equiv M_2 \pmod N,$$ showing that the plaintexts are identical $\bmod N$ if the cryptotext are the same.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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