The original poster clarified that:
- the application of RSA is signature (not encryption as originally stated);
- at least one signature $s$, the value of $N$, and $e=3$ are given;
- the signature is by signing an MD5 hash of a message, and a hash of the message matching the signature $s$ is also a given.
The first, low-effort thing to do with the givens is computing $r=s^e\bmod N$, which in most RSA signature schemes is the so-called message representative (single practical exception: in some schemes including some in ISO/IEC 9796:1991, ISO/IEC 9796-2, ISO/IEC 14888-2, the message representative could also be $N-r$).
The message representative $r$ that we now have was determined by the signer from the MD5 hash (that we know) of some message, using some in principle public process that we are not given. That process usually involves padding on the left or/and right with repetitive constant bytes, or randomness; perhaps hashing; and in modern schemes XORing some portions with the result of some public mask generating function of some other section of the message representative. Many paddings found in practice are easily recognizable by some prescribed constant byte at some prescribed location; all are bound to be unambiguously detectable if one has the specification and parameters necessary to check a signature.
Doing the above, the original poster reported that $r$ is exactly the hash (the tool computing $r=s^e\bmod N$ has output the 16-byte hash with a 00 on the left, perhaps because the hash starts with the byte B5 and that's in the range 80..FF of negative byte values for two's complement).
So we conclusively know that there is no padding; in other words, it is used textbook RSA signature, or equivalently the padding type 00 of section 8.1 of PKCS#1 Version 1.5 of 1993, also RFC2313 of 1998 (I find it unjustifiable that this non-padding is in these documents with so little warning).
We know the padding, and it is so lacking that we know the signature matching many hash values: for example the all-zero bitstring of 1024-bit ($s=0$) is the signature of the hash consisting of the all-zero 128-bit bitstring ($r=0=s^e$); the bitstring with only the $k^{th}$ bit set ($s=2^k$) and $k\le42=\lfloor{128\over e}\rfloor$ is the signature of the hash with only the $3k^{th}$ bit set ($r=2^{3k}=s^e$); more generally we know the signature for any hash which value is a cube in $\mathbb N$. However that is not solving the concrete problem of forging a message passing a signature check of its MD5 hash, thus does not answer the question. We have several options to proceed towards that goal:
- Trying to find $d$ (or more precisely, one of several working private exponents $d$), which would trivially allow to sign any message. In RSA, example cryptograms (if valid) are of no help towards that (we do not know how to prove it, but if such a mean was found after 38 years of public research, it would make the headlines). The only practical way we could find such $d$ is by factoring $N$. Factoring a properly generated 1024-bit RSA modulus is currently well beyond the possibility of anything but deep-pocketed organizations like the NSA, which would not claim that capability if they had it (a plausible but unproven conjecture). Thus if we try factoring $N$, it will only succeed if $N$ was poorly chosen. If the teacher mentioned some factoring method (like Fermat's, or Pollard's $p-1$), it might be worth trying that.
- Trying to find a message that matches the existing signature. That's a preimage attack on MD5 (first preimage since we do not have a message), and although the collision-resistance of MD5 is now broken, its preimage resistance stands valiantly; so that won't work. We are not in a position to obtain the signature of a chosen message, thus we can't make use of MD5 collisions.
- Trying to find a message and a new matching signature going with that. If we had many signatures, that would be feasible by a transposition to signature of the attack on textbook RSA encryption of Y. Desmedt and A. M. Odlyzko: A chosen text attack on the RSA cryptosystem and some discrete logarithm schemes (in proceedings of Crypto 1985). It is re-explained in the context of signature by Jean-Sebastien Coron, David Naccache, Mehdi Tibouchi and Ralf-Philipp Weinmann in section 3 of Practical Cryptanalysis of ISO/IEC 9796-2 and EMV Signatures (extended abstract in proceedings of Crypto 2009). But unless we have many valid signatures, that can't work.
- [Late addition, independently found by Poncho] Another method to try to find a message and a new matching signature going with that, but without requiring extra valid signature, would be hashing messages with a random ending until their hash happens to be a cube (it is then trivial to find their signature). This is expected to require about $2^{{e-1\over e}128}=2^{85.3\dots}$ hashes, which would require the resources devoted to bitcoin mining in like a year (and can't be done with exactly that hardware: it seems to consist of ASICs hard-wired for SHA-256 rather than MD5, and no way to stop hashing on cubeness, or likelihood of that).
- [Credit goes to Poncho in this comment] Trying to find a message and some value that the verifier will accept as a valid signature, even though it is not the normal signature. That might be possible in particular if the verifier checks a signature $s$ by computing $s^e\bmod N$ and checking that the rightmost 16 bytes match the MD5 hash of the alleged message $M$, but fails to fully check the rest of the padding (something similar was a formerly common goof).
Assuming checks are made on at most the $w\le\lfloor{\log_2(N)\over e}\rfloor$ rightmost bits of $s^e\bmod N$ (here $w$ can be up to $341$, much more than the hash width), we can pick messages $M$ (e.g. at random within messages that it is useful to get signed) until $r=\operatorname{MD5}(M)$ is odd (or more generally $r=u\cdot2^{e\cdot v}$ with odd $u$, which gives a little extra freedom in the choice of $M$); and then find a $w$-bit number $s$ with $s^e\equiv r\pmod{2^w}$, which will exist. $s$ can be found in $w$ steps each finding an additional bit for $s$ starting from the right, with $s^e\equiv r\pmod{2^k}$ for $k$ increasing from $0$.
Then $s$ (zero-padded on the left to the width of a signature) will be accepted as a signature for message $M$ !! Notice that $s^e<N$, thus $(s^e\bmod N)=s^e$, and we know that the rightmost $w$ bits of $s^e$ (which we assumed are the only ones checked) match the true message representative $r$ for our message $M$. We don't need any signature to carry that attack, which fits the problem statement; but since we do not have the code of the verifier, we will only know if it works by trying.
If Poncho and I missed any other avenue for attack that might fit the question, I want to know!
Attack 5 assumes an hypothetical verifier goof. Attacks 3, 4 and 5 depend entirely on the disastrous/absent padding. Attacks 4, 5, and to a lesser degree 3, also depends on $e$ being very small, with the common $e=65537$ enough to block 4 and 5, and appreciably slow 3. The lesson about RSA signature should be to
- Ensure that verifier code is correct in how it checks padding, which is done with best confidence by a combination of scrutinizing the source code and testing; the most critical being that what's been reviewed is what's actually used (including but not limited to that the compiler did not goof, and that an adversary can't zap some of the checks by altering what's run, which could be at any point from the developer's penetrated development machine, to the internals of the target CPU in a fault attack).
- Use a proper padding for RSA signature, with the bare minimum PKCS#1 V1.5 type 01 (now officially named EMSA-PKCS1-V1_5), and EMSA-PSS preferable (specially in circumstances where the attacker might obtain the signature of even partially chosen messages).
- Use $e=65537$ (or more, but that's technically unjustified) unless it is used a padding with a strong security argument (including EMSA-PSS). There might be additional reasons to stick to $e=65537$, see this.
