How to decrypt this RSA-like cipher Suppose we have a RSA-type Modulus $n = pq$ with $p,q$ prime. We also pick a random public exponent $e$ with $\gcd(e,\varphi(n)) = 1$ and compute the private exponent $d$ with $de \equiv 1 \pmod{\varphi(n)}$. $(n,e)$ is the public key, $(n,d)$ is the private key. Just like RSA, so far.

Now we encrypt a message representative $m$ with $0 \leq m &lt; n$ by applying the following steps:


Choose a random $r$ with $1 \leq r &lt; n$
Compute $y = (r^e)^e \pmod{n}$
Compute $z = (r \cdot m)^e \pmod{n}$ 
$(y,z)$ is the Ciphertext


How is it possible to decrypt this cipher using just the ciphertext $(y,z)$ and the private key $(n,d)$?



Here's what i have so far for the decryption algorithm:


Compute $r = (y^d)^d$
Compute $rm = z^d$
Find the multiplicative inverse $r^{-1}$ of $r$ modulo $n$
Compute $m = rm \cdot r^{-1}$


The problem with this is, that $r^{-1}$ only exists, when $\gcd(r,n) = 1$ and thus the decryption fails, when this is not the case. Is there a better way to do this?
A slightly more efficient method to perform decryption would be:


Compute $r^e = (y^d)$
Find the multiplicative inverse $r^{-e}$ of $r^e$ modulo $n$
Compute $m = (r^{-e} \cdot z)^d = (r^{-e} \cdot r^e \cdot m^e) ^d$


This has two computations of $x^d$ for some $x$; your method has three.

On the other hand, this doesn't address your question; if $r^{-1}$ doesn't exist, neither will $(r^e)^{-1}$.

For your question, well, there is no such "better" algorithm, because the decryption is inherently ambiguous.

Suppose that $n = pq$ (where $p$ and $q$ are distinct primes), and you selected a value $r = kp$ (for some integer k).  Then, if we consider two distinct messages $m_1$ and $m_2$ with $m_1 = m_2 \mod q$, and the encryption of both these messages with that same $r$.  They share the same $y$ value (because $y$ depends only on $r$), and as for the $z$ value:

$z_1 = (r \cdot m_1)^e \mod n$

$z_2 = (r \cdot m_2)^e \mod n$

we see that:

$(z_1 - z_2) \bmod p = r^e \cdot (m_1^e - m_2^e) \bmod p = 0$  (because $r$ is a multiple of $p$

$(z_1 - z_2) \bmod q = r^e \cdot (m_1^e - m_2^e) \bmod q = r^e \cdot 0 = 0$ (because $m_1^e$ and $m_2^e$ are the same modulo q)

and hence (by the Chinese Remainder Theorem), $z_1 = z_2 \mod n$

So, if you attempt to decrypt the message $(y, z_1)$, there are at least two valid decryptions ($m_1$ and $m_2$), and no algorithm can distinguish which is meant.

If you prefer a concrete example, consider the case where $p=5$ and $q = 11$.  We can select $e = 3$ and $d = 27$ (actually, $d=7$ would work just as well).  Then, if we select $r = 10$ and $m_1 = 2$ and $m_2 = 13$, then the encryption of $m_1$ would be:

$((10^3)^3, (10\cdot2)^3) = (10, 25)$

and the encryption of $m_2$ would be:

$((10^3)^3, (10\cdot13)^3) = (10, 25)$

Hence if we get the ciphertext $(10, 25)$, we can't tell if the original message with 2, 13, or even a bunch of other values (24, 35, 46)

Now, in practice, this is not likely to be a concern; the probability of this happening with a random $r$ is about $1/p + 1/q$; if $p$ and $q$ are large enough to make factorization difficult, this failure probability is negligible.

BTW: why are you considering this method, rather than a more straightforward RSA-based approach?  If it is to get some homomorphic properties, well, it doesn't hide the encryption of 0 very well, and that's really what we would like in a multiplicative homomorphic encryption.