Emilio Ferrucci
Reputation
Top tag
Next privilege 150 Rep.
Create tags
 Jan5 comment Cycle attack on RSA @PeterTaylor Yes, by " $k$ might have not much to do with the order of $\mathbb{Z}_{\phi(n)}^{\times}$" I meant in terms of magnitude - it could be a divisor and still be small. Jan5 comment Cycle attack on RSA Thank you for your answer, this is what I was looking for. I still don't understand one thing though: why is the probability of $|e|$ not being a multiple of $r$ at most $1/r$? Jan5 comment Cycle attack on RSA By $$i mean the group generated by e, =\{1,e,e^2,...,e^{k-1} \} (yes, |e|=k). I don't see the connection with factoring or with evaluating \phi(n) (which are computationally equivalent, up to polynomial transformations), since in theory k could be much smaller than |\mathbb{Z}_{\phi(n)}^{\times}|=\phi(\phi(n)) (I'm guessing it probably isn't - this is the type of result I was looking for). Jan5 comment Cycle attack on RSA Then regarding the first highlighted part you quoted: I am not wondering about the order of \space \mathbb{Z}_{\phi(n)}^{\times} (which of course is fixed), but about the order of e in \mathbb{Z}_{\phi(n)}^{\times}, that is the order of the subgroup$$ of $\mathbb{Z}_{\phi(n)}^{\times}$. This might not have much to do with the order of $\mathbb{Z}_{\phi(n)}^{\times}$ : for example the group $\mathbb{Z}_{8}^{\times}$ has order 4, but the only possible orders of elements are $1$ or $2$, since it is the klein group. Jan5 comment Cycle attack on RSA Thank you for your answer. I was expecting th first objection you made: even if I came across $m$ I might not be able to tell it's the plaintext, and distinguish it from any other element in $\mathbb{Z_n}$. I don't know much about padding, and I can see how this is possible.