1
$\begingroup$

In the proof that RSA successfully decrypts the message $x$, we show that $x^{e^{d}}\equiv x \pmod N$. However, I am wondering whether it is a problem that we don't recover $x$ exactly, but merely a number congruent to it in mod $N$. Does this cause problems as far as decrypting the message successfully?

Also, the text teaching me RSA says we may assume "$x$ is an integer mod $N$". Does this mean $x$ comes to us belonging to $\{0,1,\ldots,N-1\}$, or that $x$ can be regarded as being in the system of mod $N$, meaning that it could be any integer?

$\endgroup$

2 Answers 2

1
$\begingroup$

In practice $N$ is very large (roughly a 4000 bit or 1200 decimal digit number) and any message can be encoded as an integer in $\{0,1,\ldots,N\}$. So $x$ is drawn from this set.

Also all your computations are performed by reduction modulo $N$ not kept as larger integers so while you can pretend $x$ is an arbitrary integer, this makes no difference.

$\endgroup$
2
  • $\begingroup$ do we choose $p$ and $q$ after we have determined the $x$ representing the message? So that we could make $N$ bigger than $x$? Also, how do we not lose information when an $x$ bigger than $N-1$ is reduced? $\endgroup$ Aug 26, 2023 at 20:05
  • $\begingroup$ @Shmuel: typically, we do key generation (which picks the $p$ and $q$ values) before we have a message to encrypt. In any case, we generally encrypt only short messages (for example, a 128 or 256 bit AES key), and so how to handle huge messages directly simply doesn't come up. If we do have a huge message, we can pick a random AES key, encrypt the message with that, and RSA encrypt the random AES key $\endgroup$
    – poncho
    Aug 26, 2023 at 20:33
1
$\begingroup$

Does it matter that we recover something congruent to $x$ rather than equal to it?

It would matter, but to avoid that issue we insure that $0\le x<N$.

RSA textbook encryption has plaintext and ciphertext in the set $\{0,1,\ldots,N-1\}$. Encryption of $x\in\{0,1,\ldots,N-1\}$ goes $c:=x^e\bmod n$, with by definition of the$\bmod$ operator $c\in\{0,1,\ldots,N-1\}$. Decryption can go $m:=c^d\bmod n$ which also is in that set, and $m=x$ for proper choice of $N$, $e$, $d$.

Said RSA textbook encryption has numerous flaws. From a security standpoint, among other serious issues, a guess of $x$ can easily be verified from $c$ and the public key $(N,e)$. From a practical standpoint, large messages do not fit the message space, as rightly pointed in the question.

The security issues (except for implementation-related ones perhaps) can be fixed with proper random padding e.g. RSAES-OAEP, but that further reduces the maximum size of message: with 2048-bit $N$ (enough for 255 bytes and 7 bits in RSA textbook encryption) and SHA-256, RSAES-OAEP limits the message to 190 bytes.

The message size issue is dealt with by restricting to small messages. These often consist of symmetric key(s) that then are used to encipher the bulk of the message with a symmetric algorithm. That's hybrid encryption. For such key establishment, we can use RSA-KEM, which is simpler than using RSAES-OAEP to encipher a random key.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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