RSA: does it matter that we recover something congruent to x rather than equal to it?

Shmuel

8/26/24, 7:25 PM

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?

2 + 0

number-theory

modular-arithmetic

Score:1

Crypto

kodlu

8/26/24, 7:45 PM

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.

+ 2

Shmuel

8/26/24, 8:05 PM

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?

poncho

8/26/24, 8:33 PM

@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

Score:1

Crypto

fgrieu

8/26/24, 8:42 PM

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.

+ 0

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: RSA: does it matter that we recover something congruent to x rather than equal to it?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.