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 <der> <hash>
FF's are added until the entire byte string is the length of the RSA modulus.)
<der> 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.
As @Myria describes one common RSA signature scheme, defined in the original PKCS#1 as type 1 and retronymed RSASSA-PKCS1-v1_5 in the nearly current version encodes the hash inside the value computed modexp d (and modexp e for recover/verify). Other important RSA schemes like PSS and 9796 do not, and other algorithms like DSA and ECDSA cannot, so systems that use signatures generally either fix the hash (sometimes the PK algorithm also), or encode them either independently or together. Important examples:
- SSL and TLS through 1.1 for protocol signature (ServerKeyExchange and clientCertVerify) use a fixed hash for RSA (combined MD5 and SHA1), SHA1 for DSA (as required by the versions of FIPS186 then current) and SHA1 for ECDSA (arbitrary but consistent). TLS 1.2 uses an explicit encoding: one octet for hash, and one for PK algorithm. SSL/TLS also uses X.509 certificates which contain their own signatures, see separately.
- SSH uses a string that specifies the PK algorithm and either specifies or implies the hash.
- X.509 defines an AlgorithmIdentifier data structure containing an OID identifying the signature scheme, which can include both hash and PK, plus optional parameters. 1.2.840.113549.1.1.(4,5,11-14) are (md5,sha1,sha256,sha384,sha512,sha224)withRSA; 1.2.840.1135184.108.40.206 is PSS, with the data hash and several other pieces of data used by PSS in the parameters.
- PKCS#7/CMS and SMIME use AlgorithmIdentifer from X.509.
- PGP has octet values to specify the PK algorithm and hash.