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?

  • $\begingroup$ Please define that you are using textbook RSA or not. $\endgroup$ – kelalaka Jan 29 '19 at 15:34
  • $\begingroup$ 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? $\endgroup$ – fgrieu Jan 29 '19 at 16:12
  • $\begingroup$ Hint for the second task: find a lower bound on the size of $H$ compared to $G$... $\endgroup$ – poncho Jan 29 '19 at 16:23
  • 2
    $\begingroup$ @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... $\endgroup$ – poncho Jan 29 '19 at 16:27
  • $\begingroup$ @poncho: right. I now see why that holds in a finite group. Forgot that, math getting rusty.. $\endgroup$ – fgrieu Jan 29 '19 at 17:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.