Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

up vote 5 down vote accepted

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.

share|improve this answer
    
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! –  Patrick Oscity Jul 1 '12 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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