In RSA, to encrypt a message, the following formula is used: $$c=m^e\bmod n$$ For decryption, $$m = c^d\bmod n$$ is used. However, when I try to substitute the value of $c$ from the first into the second formula, I am unable to satisfy the equation, or rather unable to simplify the expression below: $$m = (m^e\bmod n)^d\bmod n$$ What am I missing here?
$\begingroup$
$\endgroup$
0
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
You appear to be confused about a couple of different things, at least if I have correctly interpreted your confusion. First, the relation you should be using is congruence, not equality. The encryption congruence (not equation) is thus more precisely: $$c \equiv m^e \pmod n$$ Note that this uses the triple congruence sign rather than the equals sign. They are similar relations, but there are some important differences between equality and congruence.
The second thing that you appear to be confused by is the $\pmod n$ statement. This is not one of the right-hand side terms like $m^e$, instead it specifies the modulus of the congruence relation. So long as you have congruences with the same modulus you can substitute terms just like with equations, but the $\pmod n$ statement is not one of the things you substitute into the congruence. So the decryption statement should read: $$m \equiv c^d \pmod n$$ And you can substitute like so: $$m \equiv (m^e)^d \equiv m^{ed} \pmod n$$ Why is this congruence true? Well, it's because $e \cdot d \equiv 1 \pmod {\varphi(n)}$. Or in other words, $e$ and $d$ are multiplicative inverses modulo the totient of $n$, which means that due to Euler's theorem, $m^{ed} \equiv m^1 \equiv m \pmod n$.
-
$\begingroup$ it seems i was a little confused about the modulus operator all together. The congruence relation is in itself a binary operator which includes the (mod n) term as well. And what if the two equations had different modulus operators. i.e. (mod n) and (mod m) . How would it make the things different? The operation will become sequential? $\endgroup$ Commented Jul 7, 2016 at 12:55
-
$\begingroup$ They're not equations, they're congruences. Two congruences that share one or more variables but which have different moduli cannot be substituted into each other as two equations can. But there are things you can do to find solutions to systems of congruences with different moduli (see e.g. the Chinese Remainder Theorem for finding solutions to systems of linear congruences in one variable). $\endgroup$– J.D.Commented Jul 7, 2016 at 13:14
-
$\begingroup$ $c \equiv m^e \pmod n$ does not uniquely define the ciphertext $c$, and allows $c=m^e$, which would be insecure as it allows to find $m$ from $c$ by non-modular e-th root extraction. On the other hand, $c=m^e\bmod n$ uniquely defines $c$, as the single integer with $0\le c<n$ matching $c \equiv m^e \pmod n$. The expression $c=m^e\bmod n$ is the canonical, perfectly fine and notionally correct way to define textbook RSA encryption. $\;$ Also: that answer applies Euler's theorem without invoking that $m$ is coprime with $n$, thus wrongly. $\endgroup$– fgrieu ♦Commented Jul 26, 2016 at 16:44
$\begingroup$
$\endgroup$
4
RSA is based on the Carmichael function $\lambda$ (or if you prefer Euler's totient function $\varphi$):
$$x^{\lambda(n)} \equiv 1 \pmod n$$
for every integer x that is coprime to n.
From this you trivially get:
$$x^{k\lambda(n)} \equiv (x^{\lambda(n)})^k \equiv 1^k \equiv 1 \pmod n$$
and multiplying both sides with x:
$$x^{k\lambda(n)+1} \equiv x \pmod n$$
the last equation holds for all integers even if they're not co-prime to n.
We chose $e$ and $d$ such that their product is 1 modulo $\lambda(n)$ or equivalently $e \cdot d = k\lambda(n)+1$ for some $k$.
Thus $(x^e)^d \equiv x^{ed} \equiv x \mod n$ which means that encryption followed by decryption returns an integer equivalent to the plaintext. By limiting $x$ to $0 \leq x < n$ you will get the original integer.
The wikipedia page for RSA lists proofs for the correctness of RSA as well.
answered Jul 4, 2016 at 10:31
-
1$\begingroup$ I don't understand why some people feel compelled to bring up the Carmichael function all the time. It may be a nice optimisation in practical implementations, but it is of no fundamental importance (indeed, the RSA paper does not mention it at all) and it only complicates matters since it is not immediately obvious how to compute it. $\endgroup$– fkraiemCommented Jul 4, 2016 at 10:41
-
1$\begingroup$ @fkraiem The reasons why I prefer $\lambda$ is because it gives you all solutions instead of just some of them and that its defining property is the property we need for RSA to work. $\endgroup$ Commented Jul 4, 2016 at 10:45
-
$\begingroup$ @fkraiem The reason why I prefer $\lambda$ is because it is conceptually the right thing. (However, when playing around with RSA, I've nevertheless found myself using $\varphi$ for simplicity...) $\endgroup$– yyyyyyyCommented Jul 4, 2016 at 10:50
-
$\begingroup$ @fkraiem: For an RSA modulus $n = pq$, $\lambda(n) = \operatorname{lcm}(p-1, q-1)$. That's not really significantly more complicated to compute than $\varphi(n) = (p-1)(q-1)$, at least not if you already know how to calculate the least common multiple / greatest common divisor of two numbers. (And yes, I know this is an old thread, but I figured this would be a useful note to include for other readers who may stumble across this answer too.) $\endgroup$ Commented Dec 18, 2018 at 3:30