I don't have a clue how to solve this exercise:
Let m be an RSA modulus, g an encryption Exponent and N be a space of Messages. You know that $k^g$ is such that $k \in S \subset N$ with an S of cardinality $\log_2{(m)} $. How do you find m?
It seems that this exercise wants to stress the fact that small messages are a bad idea?? But since g can be arbitrary big we don't have to calculate the g^th root in $\mathbb{Z}$ we still have to calculate the third root (in a way) in $\mathbb{Z}_m$ but how does one do that?
If gcd(g,m-1)=1 one can find $d_g , d_{m-1}$ such that $ 1=d_g*g+d_{m-1}*(m-1) $? Since the inverse of $k^g$ exists this property has to be fulfilled or the encryption map is the identity map? So I simply apply the advanced euclidean algorithm to find $d_g , d_{m-1}$ but then? How to calculate $k^{d_{m-1}*(m-1)}$ i.e. the inverse of $k^{d_g * g}$ ??? On the other Hand I Need not m-1, I Need to do this with g and the euler phi function. In fact I have to Play this game if $gcd(g,\phi(m))=1$. One has to find $1=f_g*g+f_{\phi(m)}*\phi(m)$. What do you think?
Am I on the wrong track?
What algorithm do I have to find here?
Best Regards