What are the differences between MD5, SHA and RSA?

Question

MD5 tools output hexadecimal values. In the same manner, do SHA and RSA together produce a hexadecimal (or any other) output?

What are the differences between the MD5, SHA and RSA algorithms?

Answer 1

It's not the type of output. Hex is just the way the data is formatted - since all of them are working on binary data, hex makes a great deal of sense.

The important part is what they do and how they do it:

• MD5 and SHA are hash functions (SHA is actually a family of hash functions) - they take a piece of data, compact it and create a suitably unique output that is very hard to emulate with a different piece of data. They don't encrypt anything - you can't take MD5 or SHA output and "unhash" it to get back to your starting point. The difference between the two lies in what algorithm they use to create the hash. Also note that MD5 is now broken as a way was discovered to easily generate collisions and should not be used nor trusted anymore.

• RSA is an assymetric encryption algorithm. You have two keys (private and public) and you can perform a function with one key (encrypt or decrypt) and reverse with the other key. Which key you use depends on whether you are trying to do a digital signature or an encryption.

Answer 2

MD5 is a cryptographic hash function. "SHA" is the name for a family of hash functions; first a short-lived "SHA" which was renamed "SHA-0", then "SHA-1" was defined (a best seller). Later on, new members of the family were added, collectively designated as "SHA-2", and consisting of SHA-224, SHA-256, SHA-384 and SHA-512. Recently, a new SHA generation was designed, called "SHA-3" but also "Keccak" (this was an open competition, Keccak being the codename of one of the candidates, who ultimately won).

A cryptographic hash function is a fully defined, deterministic function which uses no secret key. It takes as input a message of arbitrary length (a stream of bits, any bits) and produces a fixed-size output. Output size depends on the function; it is 128 bits for MD5, 160 bits for SHA-1, 256 bits for SHA-256... Everybody can compute a given hash function on a given input, and they all get the same results. Hash functions are also called digests because they somehow produce a kind of "checksum" or "summary" of the input. Robust hash functions must be such that nobody knows how to "invert" them or even find two distinct inputs which yield the same output. The latter is called a collision and it is a mathematical necessity that collisions exist (since the function can accept many more distinct inputs than it can produce distinct outputs), but we require that it is unfeasible to find even one collision.

MD5 turned out to be very broken with regards to collisions (we can produce a collision in a few seconds of work on a PC) and SHA-0 is also broken in that respect; SHA-1 is a bit flaky; the rest of the SHA family appears to be robust so far. How a hash function achieves collision resistance is a bit of a miracle since the whole function is completely known, with no secret value; it just mixes the data too much for the best cryptographers to unravel the process.

RSA is two algorithms: an asymmetric encryption algorithm and a digital signature algorithm. Although both algorithms build on the same kind of mathematics, they are quite distinct (a lot of people describe signatures as "encryption with the private key", which is a flaw analogy and at best confusing, so don't do that). Both algorithms uses keys, i.e. pieces of data which must be kept secret. It so happens that for RSA signatures, what is signed is not directly a given message (a sequence of bits) but a hash of the message: the message is first processed with a cryptographic hash function like SHA-256, and the hash value is then used. This is done that way because the mathematics of RSA can handle only values of moderate size, a few hundred bits at best. Cryptographic hash functions are such that signing the hash is as good as signing the original data.

That way, RSA and cryptographic hash functions are often used together; but they are not the same thing at all.

Hexadecimal is a way to represent a sequence of bits into a sequence of characters: hexadecimal uses digits and letters from 'A' to 'F'; each character encodes exactly four bits ('0' encodes '0000', '7' encodes '0111', 'D' encodes '1101'...). Any sequence of bits (and in particular the output of a hash function) can be converted to hexadecimal and back. Hexadecimal is popular because human eyes and brain are good at reading characters, and not at reading bits. Command-line tools which compute cryptographic hash functions on files traditionally output hexadecimal characters for that reason. However, there is nothing which intrinsically ties hash functions with hexadecimal: everything which fits in a computer one way or another is a sequence of bits, and so is amenable to hexadecimal; and a hash function output is just a sequence of bits, which can be encoded in various ways, hexadecimal being just the "traditional" way (although Base64 is also often encountered, especially when dealing with databases).