How does this happen in RSA malleability?

Question

I don't understand how the $E(m)$ turns into $E(mt)$. I mean, I don't know how does that transformation happen and how does the equation occur.

$$E(m) \cdot t^e \bmod n = (mt)^e \bmod n = E(mt)$$

See, $E(m)$ is $m^e \bmod n$, so if you plug in real values, it won't work.

For example:

• $c_1 = 17^{23} \bmod 35 = 33$
• $c_2 = 2^{23} \bmod 35 = 18$

Now, $c_1 \cdot c_2$ should result in $33 \cdot 18 = 594$, i.e. $E(mt)$. But if you plug in the values in $(mt)^e \bmod n$, you get $34$ instead of $594$.

How are these equal?

Answer 1

As mikeazo notes in the comments, RSA operates on the ring $\mathbb Z / n\mathbb Z$ of integers modulo $n$, for a given modulus $n = pq$. In this ring,

$$E(m) \cdot t^e \equiv m^e \cdot t^e \equiv (mt)^e \equiv E(mt)\ \pmod n.$$

In particular, for $n = 35$, $e = 23$,

$$17^{23} \cdot 2^{23} \equiv 33 \cdot 18 \equiv 594 \equiv 34 \equiv 34^{23}\ \pmod{35}.$$

The notation in your question,

"$E(m) \cdot t^e \bmod n = (mt)^e \bmod n = E(mt)$",

apparently using $\bmod$ as a modulo operator, is somewhat confusing here, although it's technically correct if you interpret the left hand side as "$(E(m) \cdot t^e) \bmod n$". I would much prefer the notation I've used above, which makes it clear that we're doing all arithmetic in the ring $\mathbb Z / n\mathbb Z$, and that we're thus free to reduce (or not to reduce) intermediate values modulo $n$ any time we want.

Answer 2

I just want to add some additional information to the answer of Ilmari.

As Ilmari has already described in his answer, when using RSA you work in the ring of integers ${\mathbb Z}/{\mathbb Z}_n$, which is also called a residue class ring. This means that it consists of the set of residue classes $[i]$, where the $i$'th class is defined as the set $\{a \in {\mathbb Z}, \exists k: a = k\cdot n + i\}$ or equivalently $\{a \in {\mathbb Z}: a \equiv i \pmod n\}$. Basically, the sets of integers that have the same remainder when dividing them by $n$. Note that $i$ is clearly from the set $\{0,\ldots,n-1\}$, i.e., there are $n$ distinct equivalence classes in this ring.

It is quite easy to check that $a$ congruent to $b$ modulo $n$ (the relation is denoted as $\equiv$) for any $a,b\in {\mathbb Z}$ defines an equivalence relation on ${\mathbb Z}$, i.e., it's reflexive, symmetric and transitive, which gives the partitioning of ${\mathbb Z}$ into these distinct equivalence classes (residue classes).

Even more, the relation $\equiv$ on ${\mathbb Z}$, written as $a\equiv b \pmod n$, actually represents a congruence relation, i.e., an equivalence relation which is compatible with the operations of the underlying algebraic structure.

In our specific case this means that for the ring of integers $({\mathbb Z},+,\cdot)$ and relation $\equiv$ (congruence modulo $n$) it holds that for any: $a_1, a_2, b_1, b_2 \in {\mathbb Z}$ where $a_1,a_2$ are from the same class and $b_1,b_2$ are from the same class, i.e., $a_1 \equiv a_2 \pmod n$ and $b_1 \equiv b_2 \pmod n$, it holds that:

• $a_1 + b_1 \equiv a_2 + b_2 \pmod n$
• $a_1 \cdot b_1 \equiv a_2 \cdot b_2 \pmod n$

This basically means that for any classes $i$ and $j$ we have that $[i] + [j] = [i+j]$ and $[i] \cdot [j] = [i\cdot j]$ and this in term means that it does not matter which representative from one class we take when performing the respective operation (addition or multiplication). This gives us the the ring ${\mathbb Z}/{\mathbb Z}_n$ is the set of equivalence classes modulo $n$ with addition and multiplication on these equivalence classes.

When operating on the residue class ring ${\mathbb Z}/{\mathbb Z}_n$ as in RSA, however, we typically do not consider working with the residue classes (at least we do not write that down), but we choose a system of representatives for all $n$ residue classes.

Tis means that for every class $[i]$, we choose an integer as representative. Since it is most meaningful, we therefore choose the least nonnegative system of representatives, namely the set $\{0,\ldots,n-1\}$ and identify the respective residue classes with its representatives, i.e., consider ${\mathbb Z}/{\mathbb Z}_n$ simply to be the set $\{0,\ldots,n-1\}$.

Consequently, we always reduce modulo $n$ to obtain the respective representative of the class, although we could work with any representative of the respective class.

As Ilmari says, if one reduces intermediate results or not does not make a difference in theory (but it makes a difference from an efficiency point of view in implementations). Nevertheless, the final result is always considered to be an element in the set $\{0,\ldots,n-1\}$ and thus reduced modulo $n$.