How does this happen in RSA malleability?

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?

-
Anyone folks? Anyone who can clarify this. –  Ali Gajani Dec 8 '13 at 22:15
What is 594 mod 35? –  mikeazo Dec 8 '13 at 22:25
It's 34. But we have taken the results of c1 and c2 already, which gives us 594. Why should we mod again? @mikeazo At this stage it's like 594 = 34 which is weird. –  Ali Gajani Dec 8 '13 at 22:31
RSA works in the multiplicative group of integers $\mathbb{Z}_n$ or the integers mod n. In this group $594\equiv 34$. I'd suggest reading up on abstract algebra, groups in particular. –  mikeazo Dec 8 '13 at 22:41
I have read up but I am not getting this specific example, can you enlighten me how does this come around. I know what congruence is, it means 594 is in the same equivalence class is 34 w.r.t mod 35. –  Ali Gajani Dec 8 '13 at 22:44

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}.$$

"$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.

-
Makes more sense if Wikipedia said congruent to instead of using the equality operator. I believe you're right. –  Ali Gajani Dec 9 '13 at 1:23
You do not have to "believe" that Ilmari is right, he is correct ;) –  DrLecter Dec 9 '13 at 1:33
@AliGajani: The point is, it is an equality in the ring $\mathbb{Z}/n\mathbb{Z}$, because two elements are equal if they are in the same equivalence class modulo $n$. –  figlesquidge Dec 9 '13 at 10:01

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$.

-