0
$\begingroup$

I am referring to solution given in this question

I need help to implement Poncho hint in this comment:

As the first question i have an RSA signature of 1024 bit applied on an hash (MD5) of the message.

I am trying to get a valid result coding it in Java but i don't get any result from my iterations.

Can someone help me to find out why i don't get results as mentioned by @Poncho?

Example of hash: 0xCC844F9AF903BCB3CB0A7F0433AF70D3 Decimal representation: 271849508914011436342484527734062018771

Thanks a lot.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$ 
if(checkValue.compareTo(resultOfModulus) == 0)

Here's your problem; you're checking if $y^3 = (md5BigInteger \bmod 2^i)$; that's wrong (as $md5BigInteger \bmod 2^i$ won't typically be a cube).

Instead, what you want is to check if $y^3 \equiv md5BigInteger \pmod{2^i}$; or, in other words (thinking less like a mathematician, and more like a programmer) if $(y^3 \bmod 2^i) = (md5BigInteger \bmod 2^i)$

Also, don't forget to check if $md5BigInteger$ is odd (or more generally, $8^k w$ for integer $k$ and odd $w$); if it's not of that form, no such simple cube will exist.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks a lot for your clarification. I updated my code and i am sure that md5BigInteger is odd but again i didn't get results. I start to work with y from 1 and then increment it at each iteration. Is that right? Can you check my code and tell me where i am wrong please? $\endgroup$
    – itseeder
    Aug 3, 2015 at 17:29
  • $\begingroup$ That's wrong as well. If the $y^3$ and $hash$ agree in the lower $i$ bits, then you don't need to update $y$ at all (because you know that the lower $i$ bits are correct. If they don't agree, then you know you need to flip bit $i-1$ of $y$ (and since you initialize that bit to 0, that's the same as adding two,pow(i-1) to it. $\endgroup$
    – poncho
    Aug 3, 2015 at 17:52
  • $\begingroup$ I misstyped my edit and now i think that the code is correct. Right? Again i don't get a valid result. I added for further experiments the sample hash i am working on. Thanks again for your help. $\endgroup$
    – itseeder
    Aug 3, 2015 at 18:08
  • $\begingroup$ @Seed3Key: look at what I wrote; not y = y.add(two) but y = y.add(two.pow(i-1)) $\endgroup$
    – poncho
    Aug 3, 2015 at 18:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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