# RSA: Probalistic algorithm to compute $x$ from $y$ and $(n,e)$ with probability $\epsilon>0$ given set of weak ciphertexts?

Suppose there exists a set of ciphertexts $S \subset Z_n^*$ of size $\epsilon (p-1)(q-1)$ for $\epsilon>0$, that is easy to decrypt, i.e. there exist some algorithm $A_1 : \mathcal C \rightarrow \mathcal P \cup \{\text{void}\}$ that given ciphertext $y \in S$ and public key $(n,e)$ outputs correspoding plaintext $x$ and otherwise returns $\text{void}$.

I want to create a probalistic algorithm $A_2$ that given ciphertext $y$ and public key $(n,e)$ returns corresponding plaintext $x$ with probability at least $\epsilon$.

In the textbook a hint is given: Use $A_1$ as a subroutine and the RSA multiplicative property $$e_K(x_1x_2 \bmod n) = e_K(x_1)e_K(x_2) \bmod n$$

I've already proven that if $y\in Z_n \setminus Z_n^*$ then the secret key $(n,d)$ can be computed easily, which in turn yields the ciphertext $x$.

However, I'm stuck in the case $y\in Z_n^*$.

I've tried to consider how to split $y$ into prime factors $\prod_i p_i$, and then use the RSA multiplicative property, but this gets me nowhere.

Also, I've tried to consider picking plaintexts (or ciphertexts) at random, and then see if the product of their encryption their yields $y$.

Note:

For $y \in Z_n^*$, I cannot simply run $A_1$, because then the probability of returning $x$ would be $0$.

• What type has $\epsilon$ ? Please note that It cannot be from $Z^*_n$, because on the modular multiplicative group there cannot be defined an order .
– user27950
Commented Oct 16, 2016 at 7:23
• @Cryptostasis - Epsilon is a real number. I've corrected several typos. Commented Oct 16, 2016 at 7:37

Let $d_k$ denote decryption and $x = d_K(y)$. I further assume that $\epsilon < 1$.
First note that $A_1$ calculates a randomly chosen cipher text $y$ with probability $\epsilon$. But the task is to construct a probabilistic algorithm $A_2$ which decrypts a fixed cipher text $y$.
Therefore, proceed as follows:

1. choose a random $r \in Z^*_n$
2. calculate $y' = y* e_K(r)$
3. Use $A_1$ to decrypt $y'$ to $x'$
4. calculate $x = r^{-1}*x'$

This algorithm calculates the decryption of $y$ with probability $\epsilon$:
- In step 2, $y'$ lands with probability $\epsilon$ in $S$
- In step 3, the calculation yields $$x'= d_k(y') = d_k(y*e_K(r)) = d_K(y)*d_K(e_K(r)) = d_K(y)*r = x*r$$

• Are you sure about your argument for step 2? I mean, $e_K(r)$ is not guaranteed to be in ${Z_n}^*$ ? Commented Oct 16, 2016 at 10:29
• Sure, $e_K$ maps $Z_n^* \mapsto Z_n^*$
– user27950
Commented Oct 16, 2016 at 10:37
• Ahh, yes, I just confused myself by thinking of an arbitrary cryptosystem, like AES... Commented Oct 16, 2016 at 10:39
• Do you know what is done in practice if the ciphertext $y \in Z_n \setminus Z_n^*$? This would reveal the secret key? Commented Oct 16, 2016 at 10:46
• If $n= p*q$ and you know any $y$ in $Z_n \setminus Z_n^*$, you can calculate $p = \gcd(y, n)$.
– user27950
Commented Oct 16, 2016 at 10:51