How to decrypt this RSA-like cipher

Question

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 < n$ by applying the following steps:

1. Choose a random $r$ with $1 \leq r < n$
2. Compute $y = (r^e)^e \pmod{n}$
3. Compute $z = (r \cdot m)^e \pmod{n}$
4. $(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:

1. Compute $r = (y^d)^d$
2. Compute $rm = z^d$
3. Find the multiplicative inverse $r^{-1}$ of $r$ modulo $n$
4. 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?

Answer 1

A slightly more efficient method to perform decryption would be:

1. Compute $r^e = (y^d)$

2. Find the multiplicative inverse $r^{-e}$ of $r^e$ modulo $n$

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

Answer 2

When $\gcd(r,n) \neq 1$, then we either have $\gcd(r,n) = p$ or $\gcd(r,n) = q$ (or $\gcd(r,n) = n$, but this can't be because of $r < n$), i.e. $r$ must be a multiple of either $p$ or $q$. The probability of choosing such an $r$ is about $\frac 1p + \frac 1q$, which for key sizes as used for RSA is such a tiny number that we don't expect it to occur at all.

In either case, whoever guessed this $r$ now is able to factor $n$, and also calculate your private key. The size of $p$ and $q$ should be chosen such that even with quite an effort of calculation this should not be doable. I.e. the probability of just guessing $r$ with $\gcd(r,n) \neq 1$ is way lower than that the system breaks down on other places.

So, if this is the only worry in your system, don't worry.