RSA decryption with some additional condition I’m to find the message in RSA with an additional condition. Suppose $M$ is the message and $n$ is the large prime used here. What I know is $n,e,c$ where $c \equiv M^e \pmod n$.
If I know that there is some integer $s$ such that $M^s \equiv 1 \pmod n$, can I do the decryption?
Note that I don’t know the factorization $n=pq$ or $\phi(n)$.
For example, if I know $M^{12345} \equiv 1 \pmod n$, can I find the message $m$ without factoring $n$?
I have tried to use the original decryption (finding $d$ first), but I found it seems to be impossible.
 A: Yes, if you can somehow manage to get hold of a non-zero integer $\ s\ $ such that $\ M^s\equiv1$$\pmod{n}\ $, then you can recover $\ M\ $ from $\ n, e, c\ $ and $\ s\ $.  A procedure for doing so is:

*

*let $\ v\ $ be the smallest positive integer such that  $\ \gcd\big(e^v,s\big)=\gcd\big(e^{v+1},s\big)\ $,$\ h=\gcd\big(e^v,s\big)\ $, and $\ \sigma=\frac{s}{h}\ $.  Then $\ \gcd\big(\sigma,e\big)=1\ $, and $\ M^\sigma\equiv1$$\pmod{n}\ .^\text{see proofs below}$

*If $\ \sigma=1\ $, then $\ M=M^\sigma\equiv1\pmod{n}\ $, so $\ M=1\ $ in this case.

*If $\ \sigma\ne1\ $, use the extended Euclidean algorithm to find integers $\  a\ $ and $\ b\ $ such that $\ ae+b\sigma=1\ $, then compute $\ c^a\pmod{n}\ $.  Since $\ c\equiv M^e\pmod{n}\ $, we have
\begin{align}
c^a&\equiv M^{ea}\pmod{n}\\
&\equiv M^{1-b\sigma}\pmod{n}\\
&\equiv M\big(M^\sigma\big)^{-b}\pmod{n}\\
&\equiv M\pmod{n}\ .
\end{align}
Proof that $\ \gcd(e,\sigma)=1\ $
Let $\ w=\gcd(e,\sigma)\ $ and $\ e^v=h\mu\ $. Then $\ e^{v+1}=eh\mu\ $, so $\ wh|e^{v+1}\ $, and $\ s=\sigma h\ $, so $\ wh|s\ $. Therefore $\ wh|\gcd\big(e^{v+1},s\big)\ $.  But $\ h=\gcd\big(e^{v+1},s\big)\ $ by definition of $\ v\ $. Therefore $\ w=1\ $.
Proof that $\ M^\sigma\equiv1$$\pmod{n}\ $:
case $\mathbf{1:}\ \ \sigma\ne1\ $.
Since $\ h\mid e^v\ $, and $\ e, \phi(n)\ $ must be relatively prime, then so must $\ h, \phi(n)\ $. Let  $\ g=\gcd(s,\phi(n))\ $. Then $\ h,g\ $ must be relatively prime, and there must exist integers $\ q, r\ $ such that
$$
g=qs+r\phi(n)\ .
$$
Therefore,
\begin{align}
M^g&\equiv \big(M^s\big)^q\big(M^{\phi(n)}\big)^r\pmod{n}\\
&\equiv 1\pmod{n}\ .
\end{align}
Now $\ g\,|s=\sigma h\ $, and since $\ h,g\ $ are relatively prime, then $\ g\ $ must divide $\ \sigma\ $. Therefore
\begin{align}
M^\sigma&\equiv M^{gt}\pmod{n}\ \ \text{ for some integer }\ t\\
&\equiv 1\pmod{n}\ .
\end{align}
case $\ \mathbf{2:}\ \ \sigma=1\ $.
Since $\ s=h|e^v\ $ in this case, then $\ M^{e^v}\equiv1\pmod{n}\ $ and $\ 1\equiv\big(M^{e^v}\big)^{d^v}\equiv M^{(ed)^v}\pmod{n} $. But for any positive integer $\ u\ $, $\ M^{(ed)^{u+1}}\equiv$$\big(M^{ed}\big)^{(ed)^u}\equiv$$M^{(ed)^u}\pmod{n}\ $. By induction, therefore, $\ M^{(ed)^u}$$\equiv M^{ed}$$\equiv M\pmod{n}\ $ for all positive integers $\ u\ $. In particular, $\ M^\sigma= M\equiv M^{(ed)^v}$$\equiv1\pmod{n}\ $.
Acknowledgement
Thanks to Bill Dubuque for pointing out an error in an earlier version of this answer.
