How to decrypt an RSA ciphertext given an oracle providing the lower 8 bits of decryptions? I have access to an oracle that can encrypt and partially decrypt a number with RSA-1024 algorithm. 

For encryption: 
\begin{equation}
C = M^e\bmod n
\end{equation} 
But for decryption, result will be $\bmod256$: 
\begin{equation}
\textit{partialM} = (C^d\bmod n)\bmod 256
\end{equation}
Also I know $e=65537$, and $d$ and $n$ will remain unchanged.
I want to know if it's possible for a given $C$ to find $M$.
If yes, how?
So this feels like a homework question, as such I"m not going to give you the full answer, but yes, yes you can.  https://en.wikipedia.org/wiki/Homomorphic_encryption#Unpadded_RSA
Is the best starting point I can give without giving away the barn, but essentially rsa is homomorphic, and you can exploit that and repeated calls to the oracle to do what you want.