When one is computing $E(x) \equiv x^e \pmod N$ (where $N = pq$) in RSA, what is the precedent for which number in the residue class of $x^e$ to have as the result of this computation? Does this mean that we compute $x^e$ and then apply the mod function %$N$ to this, such that $E(x)$ is always in $\{0,1,. . .,N-1\}$? Or is there no precedent on which number we use for $E(x)$ as long as it's congruent mod $N$ to $x^e$?
6
-
1$\begingroup$ How much does it differ from this? RSA: does it matter that we recover something congruent to x rather than equal to it? $\endgroup$– kelalakaSep 3 at 20:33
-
1$\begingroup$ Did you see this Definition of textbook RSA or read the RSA paper? also see this Does RSA work for any message M? $\endgroup$– kelalakaSep 3 at 20:35
-
$\begingroup$ @kelalaka : IMHO, this question is not a duplicate. It is about notation leading to insufficiently specified ciphertext, in a way that allows decryption, but could make RSA insecure. The question marked as duplicate is about plaintext not in [0,N) making RSA decipher incorrectly, but still secure for high-enough entropy plaintext. $\endgroup$– fgrieu ♦Sep 5 at 19:22
-
$\begingroup$ @fgrieu you may be right, however, there are tons of answer that tells that RSA is a trapdoor permutation, that is, as you already know, the output must be in the range. The real dupe should be the Definition of textbook RSA. Interestingly, the Anu Davis answer tells, it. If you consider it is not the dupe ( I've looked some of your to find one but failed) you can change it for the community. $\endgroup$– kelalakaSep 5 at 21:41
-
$\begingroup$ @kelalaka I've reopened it (fgrieu flagged it for one of the other mods). If you still see a dupe then please indicate which one + reason and I'll merge if I think it is correct. I think especially with RSA we get a lot of related questions, but I guess that's OK. $\endgroup$– Maarten Bodewes ♦Sep 5 at 22:52
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
$E(x) \equiv x^e \pmod N$ as in the question means that $E(x)$ is congruent to $x^e$ modulo $N$, equivalently that $x^e-E(x)$ is a multiple of $N$. But it gives not bound for $E(x)$, thus does not uniquely define it. In particular it allows $E(x)=x^e$, and using that function for encryption would be totally insecure.
The encryption function in textbook RSA is such that $E(x)=x^e\bmod N$, which by definition of the notation$\bmod$ without an opening parenthesis immediately on the left means that $0\le E(x)<N$ and $E(x) \equiv x^e \pmod N$. For non-negative $x^e$, it's equivalent to $E(x)$ being the remainder of the Euclidean division of $E(x)$ by $N$.
Does this mean that we compute $x^e$ and then apply the mod function $\%N$ to this?
Mathematically yes, for non-negative $x^e$ that would be one way to obtain the uniquely defined $E(x)$. But that's not how it's done in practice, and it would be impossible for very large $e$. Rather, it's performed modular reduction modulo $N$ while the exponentiation proceeds. For example, with $e=2^4+1=17$, we typically compute $x_2=x^2\bmod N$, $x_4={x_2}^2\bmod N$, $x_8={x_4}^2\bmod N$, $x_{16}={x_8}^2\bmod N$, and $E(x)=x_{16}x\bmod N$.
Note: in most uses of textbook RSA, $x$ is restricted to $0\le x<N$, so that at decryption $(E(x))^d\bmod N$ always recovers $x$. That's untold by the above formulas.
