# Proof in RSA encryption over multiplicative group

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.

First, I want to prove that $$H=\{x^4|x\in G\}$$ actually 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?

I have tried the following for the first task:

Letting $$x,y \in H$$, then set $$x=a^4$$ and $$y=b^4$$ for $$a,b\in G$$. And then I have looked at $$xy=a^4b^4$$. But how to go from here?

• Please define that you are using textbook RSA or not. – kelalaka Jan 29 '19 at 15:34
• Hint for first task: prove that the restriction to $H$ of the multiplicative law in $G$ is internal, that the neutral is in $H$, and that the inverse of an element of $H$ is in $H$. Now are you missing any defining group property? – fgrieu Jan 29 '19 at 16:12
• Hint for the second task: find a lower bound on the size of $H$ compared to $G$... – poncho Jan 29 '19 at 16:23
• @fgrieu: actually, to prove that a nonempty subset of a finite group is a subgroup, all you need is to prove closure (that is, the operation of two elements of the subset always yields an element within the subset); all the other properties of the subgroup (the identity, inverses) can be deduced... – poncho Jan 29 '19 at 16:27
• @poncho: right. I now see why that holds in a finite group. Forgot that, math getting rusty.. – fgrieu Jan 29 '19 at 17:04