PriMeD5

Thanks to JosePisco for the very useful hint of “a property md5 has on collisions”. Completely shifted my approach. The server is signing the hash of the prime sent using RSA, and there is no information to figure out the private keys so we have to forge two numbers $n_1$ and $n_2$ such that $MD5(n_1) = MD5(n_2)$. Initially my approach is to use fastcoll to generate MD5 collisions with a given prefix, but this approach is just too unreliable, as the probability of finding a prime with some reasonably chosen prefix is too low - fastcoll always generate 1024-bit messages anyways....