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?


2 Answers 2


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.

  • $\begingroup$ i am not really going to use this, it's just an exercise from an old crypto class, and i am trying to prepare for the exam ;-). Thanks a lot for your answer, this made a lot of things clearer! $\endgroup$ Commented Jul 1, 2012 at 16:44

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.