Proof help: RSA Encryption

551 Views Asked by At

I am trying to fill in the middle of this proof:

$$ \begin{align} m_1 ^e \mod N \cdot \left( m_2 ^e \mod N\right)^{-1}\mod N & = \\ & \quad \vdots \\ & = \left( \frac {m_1}{m_2}\right)^e\mod N \end{align}$$

where:

  • $e$ is a random number such that $\gcd \left( \varphi(N),e \right)=1$

  • $N=pq$ for $p,q$ prime

  • $m_1$ and $m_2$ can be any integer such that $m_1=k\cdot m_2$ for $k\in\mathbb{Z}$

Simply put, I am trying to prove RSA Encryption is a partially homomorphic encryption system for division.

I have the proof for multiplication, but I'm struggling to modify it to account for the inverses. Any help is much appreciated!


Edit: This is my current attempt at a proof

The following is RSA encryption and decryption of messages $m_1$ and $m_2$:

$$ \begin{align} c_1 = m_1^e \mod N & \Longleftrightarrow m_1 = c_1^d \mod N\\ c_2 = m_2^e \mod N & \Longleftrightarrow m_2 = c_2^d \mod N \end{align} $$

For multiplication, I have the following proof:

$$\begin{align*} m & =\left(c_{1}c_{2}\right)^{d}\mod N\\ & =\left(c_{1}c_{2}\mod N\right)^{d}\mod N\\ & =\left(\left(c_{1}\mod N\times c_{2}\mod N\right)\mod N\right)^{d}\mod N\\ & =\left(c_{1}\mod N\times c_{2}\mod N\right)^{d}\mod N\\ & =\left(\left(c_{1}\mod N\right)^{d}\times\left(c_{2}\mod N\right)^{d}\right)\mod N\\ & =\left(\left(c_{1}^{d}\mod N\right)\times\left(c_{2}^{d}\mod N\right)\right)\mod N\\ & =\left(m_{1}m_{2}\right)\mod N\\ & =m_{1}m_{2} \end{align*}$$

For division I have the following attempt:

$$\begin{align*} m & = \left(c_{1}\cdot c_{2}^{-1}\mod N\right)^{d}\\ & =\left(\left(c_{1}\mod N\times c_{2}^{-1}\mod N\right)\mod N\right)^{d}\\ & =\left(c_{1}\mod N\times c_{2}^{-1}\mod N\right)^{d}\\ & =\left(c_{1}\mod N\right)^{d}\times\left(c_{2}^{-1}\mod N\right)^{d}\\ & =\left(c_{1}^{d}\mod N\right)\times\left(c_{2}^{-1}\mod N\right)^{d}\\ & =m_{1}\times\left(c_{2}^{-1}\mod N\right)^{d}\\ & =m_{1}\times\left(c_{2}^{d}\mod N\right)^{-1}\tag{this step looks dodgy}\\ & =m_{1}\times m_{2}^{-1}\\ & =\frac{m_{1}}{m_{2}} \end{align*}$$