How do you communicate the hash function used with RSA signing? When it comes to RSA signing, I understand why you need to hash the data before signing it, but don't you need to communicate what hash algorithm you use to whoever will need to verify the signature? How does that normally work? How do you communicate the hash function used with RSA signing?
Normally, yes, the hash algorithm in use is communicated beforehand.  For example, sending an algorithm identifier during the TLS/SSL handshake process.  However, depending upon the "padding scheme" in use with RSA, it may be possible to determine which hash algorithm was used from the signatures themselves.

Some padding schemes encode information specifying the hash algorithm that was used to generate the hash into the padding data.  "PKCS #1" is possibly the most well-known padding schemes that does this.

When data is signed in this manner, you can determine the hash algorithm used to generate the hash by decrypting the signature--taking it to the power e--then examining the data.  This check must be done carefully, because otherwise you might cause security breaks (Nintendo Wii comes to mind).

In PKCS #1, you take a hexadecimal representation of the hash, shown here in big-endian form, and prepend padding to the front.  The format of PKCS #1's padding is like this:

00 01 FF FF FF ... FF FF 00 &lt;der&gt; &lt;hash&gt;


(FF's are added until the entire byte string is the length of the RSA modulus.)

The &lt;der&gt; is an ASN.1-encoded identifier of the hash algorithm unique to that algorithm.  For example, the following identifier represents SHA-256:

30 31 30 0D 06 09 60 86 48 01 65 03 04 02 01 05 00 04 20


Thus, the following would be a 768-bit big-endian signature block of an empty string, using SHA-256:

00 01 FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF 00 30 31 30
0D 06 09 60 86 48 01 65 03 04 02 01 05 00 04 20
E3 B0 C4 42 98 FC 1C 14 9A FB F4 C8 99 6F B9 24
27 AE 41 E4 64 9B 93 4C A4 95 99 1B 78 52 B8 55


If you saw this string, you could determine the hash algorithm by checking for the 00 01, followed by a string of FF bytes, then a 00 byte.  Following it should be a known hash algorithm's DER, then the number of bytes present in that algorithm's digest, then the end of the block.  If all of these exactly match, it is a possible signature, so you could then use that hash algorithm to verify that the data matches.

Just make sure that you only allow hash algorithms that you approve of.