1024 RSA Hash Signature attack. Forge a valid signature I have an RSA signature of 1024 bit where i know the following:


Public modulus N
Public exponent (0x03)
Cypher message


Summary:

An MD5 hash is calculated from a collection of byte and is used as message (M).

Having an hash that is a perfect cube forge a signature accepted as valid will be easy.

Question:

Can someone give advice to find a pratical way to hashing messages changing ending until their hash will be a perfect cube?
A random 128 bit value has a tiny ($2^{-85}$) probability of being a perfect cube, and so that doesn't look like a viable approach.  And, you can't control the output of MD5, and so it'll give you effectively random values.

A better way may be to collect a large number of signatures (with their messages); that is, $S_i = M_i^3 \bmod N$ values (where $M_i$ is the MD5 hash of the $i$th message).  Then, you would factor each $M_i$, and look for linear combinations of common factors.  At the same time, you would hash a large number of messages, and look for a message  with an MD5 hash $M$ that can be represented by a linear combination of signed messages $M = M_a^{i_a} M_b^{i_b} ... M_z^{i_z}$.  When you find such a linear combintation, you then have the signature for that message $S = S_a^{i_a}S_b^{i_b} ... S_z^{i_z}$