Blockchain & Cryptocurrency #3: Digital signatures

We are a group composed by some Informatics and Mathematics who like to share their IT, Math and Cryptographic knowledge with people. It is possible to find our complete courses on http://learningspot.altervista.org website. Since we think that Steemit is a great opportunity to share knowledge, we are proposing our most interesting lessons here, too.

==================================================

In this post we are going to talk about digital signatures. This is the second cryptographic primitive along with hash functions that we need as building blocks for cryptocurrency.

Digital Signature Definition

A digital signature is supposed to be just like a signature on paper only in digital form. And there are mainly two things that we want from signatures:

1. only the owner can make the signature, but everyone seeing it can verify it's validity
2. the signature must be tied to a particular document. So that anyone can copy it and sign another document

In fact, a signature is not just a signature, but certifies your agreement or endorsement of a particular document.

Signature scheme

How can we build this in a digital form using cryptography? There are three operations that we need to be able to do:

• Generate a pair of keys: sk = secret signing key, and pk = public verification key of length in bit equal to keysize. So we will need an operation (sk, pk) := generateKeys(keysize). sk will be the key to make the signature and pk will be the key that let other subjects verify the signature.
• Sign documents: takes the secret key sk and a message m and returns the message signed sig. So we will need an operation sig := sign(sk, message).
• Signature verification: takes the public key pk, the message m and the supposed signature and returns yes or no, whether the signature is valid or not

These three operations constitute a signature scheme. The first two can be randomized algorithms, while the verification will always be deterministic. Infact, generateKeys must generate different keys for different people.

Signature requirements

The requirements for the signatures, at a slightly more technical level, are the following two:

1. A valid signature must always verify. So if I sign a message with my secret key sk and someones tries to check it with my public key pk, it has to be validated correctly.
2. It must be impossible to forge signatures. An adversary who knows my public key and verifies my signatures on some messages, can't forge my signature on some other messages.

Signatures Unforgeability

Suppose that an attacker claims that he can forge signatures and a judge wants to verify if its true or not.

We use generateKeys to obtain a secret signing key and a public verification key. We give the secret key to the judge and the public key to both parties. So the judge can make signatures and attacker knows only the public key and can see if a signature is valid or not. We will allow the attacker to see signatures on documents of his choice.

So the test can be made with following steps:

• the attacker sends a message m0, the judge signs it and sends it back
• then he sends another message m1, the judge signs it and sends it back
• the previous steps can be repeated over and over, until the attacker is satisfied
• after that, the attacker picks a new message m and tries to forge a signature.
• the judge will run the verification algorithm to check whether it verifies or not.

We will base our unforgeability definition on the chances of the attacker of winning this game.

Def. The signature scheme is unforgeable if the attacker has only a negligible chance of successfully forging a message no matter what algorithm the attacker is using.

Practical considerations

Good randomness

The algorithms that we talked about are randomized, so we need a good source of randomness. In fact, bad randomness will take to an insecure algorithm. Attacks on the source of randomness are the favourites from intelligence agencies. And the people who know what kinds of attacks are likely to be successful.

Limits to message size

In practice, there's a limit on the message size that you're able to sign. In fact, real schemes operate on bit strings of limited length.

This problem can be fixed easily signing the hash of the message rather than the message itself. So the message can be really big, but the hash will only be 256 bits. And because hash functions are collision free, it's safe to use the hash of the message as the input to the digital signature scheme.

A nice thing we will see later, is that it is also possible to sign a hash pointer. And if you sign a hash pointer then the signature covers or protects the whole structure, not just the hash pointer itself, but also everything it points to. For example, if you sign the hash pointer at the end of a blockchain, the result is that you are digitally signing the entire contents of that blockchain.

ECDSA

Bitcoin uses a particular digital signature scheme called ECDSA. It's an Elliptic Curve Digital Signature Algorithm, which belongs to US government standards.

We won't go into all the details of how ECDSA works, since it relies on some extremely hairy math.

ECDSA has good randomness, and this in very important with Elliptic Curves. Since, if you use bad randomness in general in generating a key, then it is maybe not secure. In addition for ECDSA, even if the key is perfectly secure, and the bad randomness only regards the signature generation, this will also lead to private key discovery.

So we need to be especially careful about this in practice. This is a common mistake.