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.

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 | |
  • $\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$ – Seed3Key Aug 3 '15 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 '15 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$ – Seed3Key Aug 3 '15 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 '15 at 18:32

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.