0
$\begingroup$

I know that there are cases when RSA will not work like when the number to feed into the system is greater than the modulus. I was wondering if there were any other cases when RSA won't work

I looked all over and tried rephrasing the question in google many times

Edit: I am looking for what cases exist with a valid n, e and d used properly will not encrypt and decrypt correctly eg: message <= n

$\endgroup$
3
  • $\begingroup$ try using 0 or 1 as plaintext... $\endgroup$
    – SEJPM
    Commented Jul 5, 2015 at 22:06
  • 3
    $\begingroup$ This contains some related information crypto.stackexchange.com/questions/1004/… $\endgroup$
    – mikeazo
    Commented Jul 5, 2015 at 22:10
  • 4
    $\begingroup$ @SEJPM 0 and 1 actually encrypt and decrypt just fine. Not securely, but yes correctly. $\endgroup$
    – cpast
    Commented Jul 6, 2015 at 0:02

1 Answer 1

4
$\begingroup$

It should be proven in any presentation of RSA that, with a correct public modulus $N$, public exponent $e$ and private exponent $d$, all integers $m \in \{0,1,\dots,N-1\}$ satisfy $$\left(m^e\bmod N\right)^d\bmod N = m.$$ So it is only possible for a number to "not encrypt or decrypt correctly" when it is not in $\{0,1,\dots,N-1\}$. Moreover, this necessary condition is obviously also sufficient, because the result of a $\bmod N$ operation will be in this set, so if $m$ is outside it, it can't possibly equal the result of the above computation.

$\endgroup$
1
  • $\begingroup$ Search the forum for 'unconcealed messages'. There are a minimum of 9 messages which result as the original message (quine). $\endgroup$
    – Carl Knox
    Commented Nov 5, 2017 at 18:53

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