Digital Signatures

Digital Signatures are used ubiquitously across the internet to provide two guarantees:

The contents of the message have not been modified
The sender is indeed the one who they claim to be

You can think of them as normal signatures, used to "guarantee" identity when signing documents. Except that traditional signatures do not ensure that the text above them has not been modified. In contrast to traditional signatures, which are easily forgeable, digital signatures rely on mathematical guarantees to ensure their security.

Digital Signatures are implemented in almost every application you use on a daily basis. Financial transactions to guarantee you are the one making the request. End-to-end encrypted conversation to ensure the other party is who they claim to be. Software distribution, so that a user can be sure that the file has not been tampered with prior to downloading. In the EU and the USA, digital signatures are admissible in court, just as much as traditional signatures [1] [2].

So how do they work? Well, if you have read our article on Hashing, what was described above may read like Message Authentication Codes. The only difference is that MACs do not prove who the sender was - anyone with the key can produce a valid MAC. So we will combine MACs with Asymmetric Encryption to get Digital Signatures. Let us consider a concrete example

If you remember RSA from Introduction to Cryptography, you will know it consists of a public key (e,n) and a private one (d). Everyone has access to the public key and can use it to encrypt a message, which can then be read only by the person with the private key. The encryption/decryption process worked as follows:

Bob finds two very large prime numbers (ideally they would each be 1024 bits, however here for this example we will use much smaller ones) - 23 and 53.
Bob calculates n = 23 * 53 = 1219
Bob calculates phi(n) = (23 - 1) * (53 - 1) = 22 * 52 = 1144
Bob chooses a public key, such that the greatest common divisor (gcd) of phi(n) and PubKey is 1 (they don't have common divisors). For this example we will choose 3.
Bob finds a private key, such that PubKey * PrivKey mod phi(n) = 1. For our example this gives us PrivKey of 763
Bob publishes n and PubKey.
Alice encrypts a message (m = 13 in this example) computing CT = m^PubKey mod n = 13³ mod 1219 = 2197 mod 1219 = 978
Alice sends 978 to Bob
Bob decrypts 978 by computing m = CT^PrivKey mod n = 978⁷⁶³ mod 1219 = 13

This all works because of the simple mathematical property that :

a^e*d mod n = a

Looking at the equation above, one can easily see that inverting the encryption and decryption process will still result in the original message. So if Bob used his private key to "encrypt" a message, and Alice - the public one to decrypt it, she will still get the original message. This is the property used in digital signatures (kind of with some small caveats). Bob will now sign the message with his key, send the signature with the message, and everyone can decrypt his signature to check if the get the message. If they do get it, they know that Bob was the one who sent the message and that it has not been tampered with by a third party. However, if one applies this algorithm, they will get a signature as large as the original message, which is less than desirable (so instead of sending 2 MBs, now you have to send 4 MBs). That is why Bob will sign not the message, but the HASH of it. That will reduce the signature to only some number between 1 and n-1 (which for RSA-PSS should be 4098 bits or larger).

The process described above is more of a "textbook" example. It demonstrates the general idea for constructing digital signatures (hashing + public-key cryptography). However, it is not secure by itself [3]. Additionally, most hash functions output digests a lot smaller than the domain of RSA (256 bits vs 4096 bits for example). Improvements have been proposed like the RSASSA-PSS. To combat how expensive the computations of RSA are, Eliptic-curve-based digital signatures have been proposed.

Below you can play around with a very simple signature system (RSA with only 32-bits of security):

A Note on Security

It is very important to realise that with digital signatures your private key is your identity. If someone can get access to your private key they can impersonate you, sign legally binding documents on your behalf, etc. One should store their keys with great care and most important of all NEVER LET SOMEONE ELSE GENERATE IT FOR THEM. You should use carefully tested prime number generators to create your keys. You should use above the recommended key lengths to ensure resistance against brute-force attacks. Digital signatures by themselves DO NOT provide security against replay attacks. You can sign the message "send 100 euro to B" and send it to your bank. An attacker can intercept it and then keep sending it to the bank, until you become broke. Additional measures need to be taken to protect against replay attacks. Lastly, digital signatures are not encryption mechanisms. They only sign the message. You need to use another algorithm to encrypt your message.