0
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ What is $d=\mathit{ct}$ and $n=\mathit{ct}$ supposed to mean? $\endgroup$ – yyyyyyy May 12 '16 at 9:56
  • $\begingroup$ Means that $d$ and $n$ will remain unchanged. $\endgroup$ – user34194 May 12 '16 at 10:55
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ It's not a homework, I want to learn about cryptography and reverse engineering. @Ben can you tell me please if I am on the right path? I was thinking to compute $C_i = i^e \bmod n$ and $C'=C*C_i$ with $i = 2,3,4..$ and then I will be able to find $r_i=i*M\bmod 256$ (constraint). Now I have to find $M$ that satisfy as many possible constraints? Or I must focus finding $N$ first and then compute $M$? Also, can you recommend me some article about this problem? $\endgroup$ – Jorj May 12 '16 at 16:24
  • $\begingroup$ Since you know what N is you can actually multiply by a number which is equivalent to dividing by 256. On each iteration you multiply by this constant which will give you the next lowest byte until you've done it to each byte. This would be exploiting the homomorphic property from wikipedia above, and a little bit of number theory. $\endgroup$ – Ben May 13 '16 at 3:45

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.