# 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
Oct 16 '16 at 7:23
• @Cryptostasis - Epsilon is a real number. I've corrected several typos. Oct 16 '16 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}^*$ ? Oct 16 '16 at 10:29
• Sure, $e_K$ maps $Z_n^* \mapsto Z_n^*$
– user27950
Oct 16 '16 at 10:37
• Ahh, yes, I just confused myself by thinking of an arbitrary cryptosystem, like AES... Oct 16 '16 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? Oct 16 '16 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
Oct 16 '16 at 10:51