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:
- only the owner can make the signature, but everyone seeing it can verify it's validity
- the signature must be tied to a particular document. So that anyone can copy it and sign another 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, andpk= public verification key of length in bit equal tokeysize. So we will need an operation(sk, pk) := generateKeys(keysize).skwill be the key to make the signature andpkwill be the key that let other subjects verify the signature. - Sign documents: takes the secret key
skand a messagemand returns the message signedsig. So we will need an operationsig := sign(sk, message). - Signature verification: takes the public key
pk, the messagemand the supposed signature and returns yes or no, whether the signature is valid or not
Signature requirements
The requirements for the signatures, at a slightly more technical level, are the following two:- A valid signature must always verify. So if I sign a message with my secret key
skand someones tries to check it with my public keypk, it has to be validated correctly. - 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
mand tries to forge a signature. - the judge will run the verification algorithm to check whether it verifies or not.
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.
Congratulations @rosargia! You have completed some achievement on Steemit and have been rewarded with new badge(s) :
Click on any badge to view your own Board of Honor on SteemitBoard.
For more information about SteemitBoard, click here
If you no longer want to receive notifications, reply to this comment with the word
STOP