Cryptography RSA system

Question

I everyone,

I am considering an RSA encryption over the multiplicative group $G = (Z/nZ)$ of the ring $Z/nZ$, where $n = pq$, and $p$ and $q$ are distinct odd primes.

I assume that $H=\{x^4|x\in G\}$ is a subgroup of $G$.

Next, I am assuming that there comes a probabilistic polynomial-time algorithm $A$ that recovers a correct plaintext $m$ from any given ciphertext $c$ which belongs to the subgroup $H$ with nonnegligible probability. What kind of impact would the algorithm $A$ have on the security of the RSA encryption scheme over the group $G$, where $G$ is the same group as before?

by using Lagrange I have concluded that $|H|/|G|=\frac{1}{16}$.

But how can I interpretate anything from that?

Answer 1

An almost (but not quite) complete idea. I first thought I had it, but I was too optimistic :-( This needs more work!

I think having an algorithm like $A$ would open the road for the following attack.

1. Generate a "probable" set $D$ of representatives of cosets of the subgroup $H$. Observe that the index of $H$ in $G$ is at most sixteen, so $D$ is a reasonably small set. We may actually use a bigger set in place of $D$ as long as it is still reasonably small, and likely to contain a set of representatives of cosets of $H$.
2. If $e$ is the public exponent, and $c$ is the given ciphertext, then one of $c\ell^{-e}$, $\ell\in D$ will be in the subgroup $H$. This is because $xH=\ell H$ for one $\ell\in D$ (as per the wishful assumption).
3. So for each candidate $\ell\in D$ we try the algorithm $A$ with the input $c\ell^{-e}$. If successful we move to step 4. Otherwise try another $\ell$.
4. If $x$ is the plaintext corresponding to $c\ell^{-e}$. Then $x'=x\ell$ is the plaintext corresponding to $x$. In other words, you cracked $c$.

---

I am a bit uncertain about the best way of locating $D$. My first thought was to look for a prime numbers $\ell\equiv1\pmod4$ such that $\left(\dfrac n\ell\right)=-1$. Then either $\left(\dfrac p\ell\right)=-1$ or $\left(\dfrac q\ell\right)=-1$ and, by quadratic reciprocity, either $\left(\dfrac \ell p\right)=-1$ or $\left(\dfrac \ell q\right)=-1$. If we find enough such primes $\ell_i, i=1,2,\ldots,m,$ then it soon becomes likely that their cosets generate the group $G/H$. At that point the set of numbers $\prod_{j=1}^m\ell_j^{a_j}, 0\le a_j<4$ can serve in the role of $D$.

---

An even simpler (non-deterministic) possibility is to simply keep trying random numbers in the role of $\ell$ in step 3.