W01.03 – FIRME DIGITALI


WEEK 1
Introduzione alla Crittografia e alle Criptovalute

Learn about cryptographic building blocks (“primitives”) and reason about their security. Work through how these primitives can be used to construct simple cryptocurrencies. Imparare a costruire blocchi di crittografici (“primitivi”) e la ragione dietro la loro sicurezza. Imparare come utilizzare questi “primitivi” per costruire semplici criptovalute.

Edward W. Felten
Professor of Computer Science and Public affairs – Princeton University

Sezione 01.03 – Firme digitali
01.03.01
In segment 1.3, we’re going to talk about digital signatures. This is the second cryptographic primitive along with hash functions that we need as building blocks for the cryptocurrency discussion later on.

So a digital signature is supposed to be just like a signature on paper only in digital form. And what that means is this, what we want from signatures is two things. First, that just like an ideal paper signature, only you can make your signature, but anyone who sees your signature can verify that it’s valid. And then the second thing you want is that the signature is tied to a particular document. So that somebody can’t take your signature and snip it off one document and glue it onto the bottom of another one because the signature is not just a signature. It signifies your agreement or endorsement of a particular document. Okay, so the question is how can we build this in a digital form using cryptography?
Nella sezione 1.3 parleremo delle firme digitali. Questa è la seconda primitiva crittografica insieme alle funzioni di hash di cui abbiamo bisogno come elementi costitutivi per la discussione sulla criptovaluta in seguito.

Quindi una firma digitale dovrebbe essere proprio come una firma su carta solo in forma digitale. E quello che vogliamo dalle firme sono due cose. Innanzitutto, proprio come una firma cartacea ideale, solo tu puoi fare la tua firma, ma chiunque veda la tua firma può verificare che sia valida. E poi la seconda cosa che vuoi è che la firma sia legata ad un particolare documento. In modo che qualcuno non possa prendere la tua firma e tagliarla da un documento e incollarla sul fondo di un altro perché la firma non è solo una firma. Significa l’accordo o l’approvazione di un determinato documento. Ok, quindi la domanda è: come possiamo costruire questo in una forma digitale usando la crittografia?
01.03.02
So let’s get into the nuts and bolts. Here’s an API for digital signatures.

There are three things, three operations that we need to be able to do. The first one is we need, in the beginning, to be able to generate keys, and so we have a generateKeys operation. And we tell it a keysize, how big in bits should the keys be? And this produced two keys, sk and pk. sk will be a secret signing key, this is information you keep secret that you use for making your signature. And pk is a public verification key that you’re going to give to everybody and that anybody can use to verify your signature when they see it.

The second operation is the sign operation. The sign operation, you take your secret signing key and you take some message that you wanna put your signature on. And it returns, sig which is a signature. It’s just some string of bits that represent your signature. And then, the third operation is a verify, that takes something that claims to be a valid signature and verifies that it’s correct. It takes the public key of the signer, it takes the message that the signature is supposedly on and it takes the supposed signature. And it just says yes or no, is this a valid signature?

Okay, so these three operations, these three algorithms constitute a signature scheme. And I’ll note that the first two can be randomized algorithms. The verification won’t be. It will always be deterministic. And in fact if you think about it, generateKeys had better be randomized, because it ought to be generating different keys for different people.
Quindi entriamo nei dadi e bulloni. Ecco un’API per le firme digitali.

Ci sono tre cose, tre operazioni che dobbiamo essere in grado di fare. Il primo è che abbiamo bisogno, all’inizio, di essere in grado di generare chiavi, e quindi abbiamo un’operazione generateKeys. E gli diamo una keysize (“grandezza di chiave”), quanto grande in bit dovrebbero essere le chiavi? E questo ha prodotto due chiavi, sk e pk. sk sarà una chiave di firma segreta, questa è l’informazione che tieni segreta e che usi per rendere la tua firma. E pk è una chiave pubblica di verifica che darai a tutti e che chiunque può usare per verificare la tua firma quando la vedono.

La seconda operazione è l’operazione di segno. Prendi la tua chiave di firma segreta e porti un messaggio a cui vuoi mettere la tua firma. E di ritorno, sig, è una firma. È solo una stringa di bit che rappresenta la tua firma. E poi, la terza operazione è una verifica, che prende qualcosa che afferma di essere una firma valida e verifica che sia corretta. Prende la chiave pubblica del firmatario, prende il messaggio che la firma è presumibilmente accesa e prende la firma presunta. E dice solo sì o no, è una firma valida?

Bene, quindi queste tre operazioni, questi tre algoritmi costituiscono uno schema di firma. E noterò che i primi due possono essere algoritmi randomizzati. La verifica non sarà. Sarà sempre deterministico. E infatti se ci pensate, generateKeys dovrebbe essere meglio randomizzato, perché dovrebbe generare chiavi diverse per persone diverse.
01.03.03
Okay, so the requirements for the signatures, at a slightly more technical level, are the following two requirements.

First of all, that valid signatures will verify. If a signature is valid, that is, if I sign a message with sk, with my secret key, that if someone then later tries to valid that using my public key and the same message, that that will validate correctly. So this says that signatures are useful at all. But then the second thing you want is that it’s impossible to forge signatures. That is, an adversary who knows your public key, who knows your verification key and gets to see signatures on some other messages, can’t forge your signature on some message that he wants to forge it on.
Ok, quindi i requisiti per le firme, a un livello leggermente più tecnico, sono i seguenti due requisiti.

Prima di tutto, verificheranno le firme valide. Se una firma è valida, cioè, se firmo un messaggio con sk, con la mia chiave segreta, che se qualcuno poi cerca di convalidare usando la mia chiave pubblica e lo stesso messaggio, quello verrà validato correttamente. Quindi questo dice che le firme sono utili a tutti. Ma poi la seconda cosa che vuoi è che è impossibile creare firme. Cioè, un avversario che conosce la tua chiave pubblica, che conosce la tua chiave di verifica e riesce a vedere le firme su altri messaggi, non può falsificare la tua firma su un messaggio che vuole forgiare.
01.03.04
And in order to explain this property in more detail, it is normally formulated in terms of a game that we play with an adversary. So he game I’ll depicted here with this diagram. So over here on the left is the challenger who is a TV judge and the challenger is going to test a claim by an attacker. The attacker claims that he can forge signatures. And we’re going to test that claim and the judge will pass judgement on it. The attacker here, this guy, is actually Whit Diffie, who is one of the inventors of digital signatures, of the concept of digital signatures, and a distinguished cryptographer. So I thought I’d let him play the attacker role here. Okay, so the game works like this. The first thing we do is we use generate keys to generate a secret key, a secret sign in key, and a public verification key that match up. E per spiegare questa proprietà in modo più dettagliato, è normalmente formulata in termini di un gioco che giochiamo con un avversario. Quindi, gioco che descriverò qui con questo diagramma. Quindi qui a sinistra c’è lo sfidante che è un giudice TV e lo sfidante sta per testare un reclamo da parte di un aggressore. L’attaccante afferma di poter falsificare le firme. E testeremo questa richiesta e il giudice emetterà un giudizio in merito. L’aggressore qui, questo ragazzo, è in realtà Whit Diffie, che è uno degli inventori delle firme digitali, del concetto di firma digitale ed è un eminente crittografo. Quindi ho pensato di lasciargli giocare il ruolo dell’attaccante qui. Ok, il gioco funziona così. La prima cosa che facciamo è utilizzare le chiavi generate per generare una chiave segreta, una chiave di accesso segreta e una chiave pubblica di verifica che corrisponde.
01.03.05
Now we give the secret key to the challenger, to the judge. And we give the public key to both parties, both to the challenger and the attacker. So the attacker only knows information that’s public, he only knows the public key. And his mission is going to be to try to forge a message. The challenger knows the secret key, so he can make signatures. Right now, if you think about a real-life application, and a real-life attacker would be able to see valid signatures from their would-be victim on a number of different documents. And maybe the attacker could even manipulate the victim into signing innocuous-looking documents, if that’s useful to the attacker. So in our game, we’re going to allow the attacker to get signatures on some documents of his choice. And we see that in the diagram like this. Ora diamo la chiave segreta allo sfidante, al giudice. E diamo la chiave pubblica ad entrambe le parti, sia allo sfidante che all’attaccante. Quindi l’attaccante conosce solo le informazioni pubbliche, conosce solo la chiave pubblica. E la sua missione sarà cercare di forgiare un messaggio. Lo sfidante conosce la chiave segreta, quindi può fare le firme. In questo momento, se si pensa a un’applicazione reale, e un aggressore reale sarebbe in grado di vedere firme valide dalla propria potenziale vittima su un certo numero di documenti diversi. E forse l’aggressore potrebbe persino manipolare la vittima nel firmare documenti dall’aspetto innocuo, se questo è utile per l’aggressore. Quindi, nel nostro gioco, permetteremo all’attaccante di ottenere firme su alcuni documenti di sua scelta. E lo vediamo nel diagramma come questo.
 
01.03.06
The attacker’s going to send over a message, m0, to the challenger. And the challenger’s going to sign that message and send the signature back. The attacker can look at that, scratch his head a little bit, and send over another message, m1. The challenger will sign that. And we do that for as long as the attacker wants. The attacker can send over any sequence of messages he wants and get signatures on them.

Once the attacker is satisfied that he’s seen enough signatures, and we’re gonna let him see only a plausible number. Then he’s going to pick some message m that he wants to forge a signature on, and he’s gonna try to forge a signature. And of course, there’s a rule that says that this m, this message that he’s trying to forge a signature on, isn’t one of the messages that he’s already seen. Cuz it would be really easy for him to send over a valid signature on m0, I mean we sent him a valid signature on m0 earlier. So he’s going to pick some other message that he hasn’t seen a signature for all ready. And he’s going to send over what he claims is a signature on that message.

And then the question is, can he succeed? So the challenger is going to run the verify algorithm, use the public verification key on that message, and the signature that the attacker provided, and is going to check whether it verifies. And if it does verify, if this returns true, then the attacker wins, the attacker has forged a message.

And so this game is what we use to define what it means for a digital signature scheme to have the unforgeablility property. And if we want to get really precise, what we say is that the attacker’s probability of winning this game is negligible, and that that’s true no matter what algorithm the attacker is using. In other words, we’re going to say that the signature scheme is unforgeable if, no matter what algorithm the attacker is using, the attacker has only a negligible chance of successfully forging a message. And if we have that property together with a much easier property that valid messages verify, then we have a digital signature scheme that is suitable.
L’attaccante invierà un messaggio, m0, allo sfidante. E lo sfidante firmerà quel messaggio e restituirà la firma. L’attaccante può guardarlo, grattarsi un pò la testa e inviare un altro messaggio, m1. Lo sfidante lo firmerà. E lo facciamo per tutto il tempo che vuole l’attaccante. L’utente malintenzionato può inviare qualsiasi sequenza di messaggi che desidera e ottenere firme su di essi.

Una volta che l’attaccante è soddisfatto di aver visto abbastanza firme, gli permettiamo di vedere solo un numero plausibile. Poi sceglierà un messaggio su cui vuole creare una firma, e proverà a creare una firma. E, naturalmente, c’è una regola che dice che questo messaggio, che sta cercando di creare una firma, non è uno dei messaggi che ha già visto. Perchè sarebbe davvero facile per lui mandare una firma valida su m0, voglio dire che gli abbiamo mandato una firma valida su m0 prima. Quindi sceglierà un altro messaggio che non ha visto una firma pronta per tutti. E invierà ciò che afferma essere una firma su quel messaggio.

E allora la domanda è, può avere successo? Quindi lo sfidante eseguirà l’algoritmo di verifica, userà la chiave pubblica di verifica su quel messaggio e la firma fornita dall’attaccante e verificherà se verifica. E se verifica, se questo restituisce true, l’attaccante vince, l’attaccante ha falsificato un messaggio.

E così questo gioco è ciò che usiamo per definire cosa significa per uno schema di firma digitale avere la proprietà infalsicabilità. E se vogliamo essere veramente precisi, quello che diciamo è che la probabilità che l’attaccante vincerà questo gioco è trascurabile, e questo è vero indipendentemente dall’algoritmo che l’attaccante sta usando. In altre parole, stiamo dicendo che lo schema della firma è infalsicabile se, indipendentemente dall’algoritmo che sta usando l’aggressore, l’aggressore ha solo una possibilità trascurabile di falsificare con successo un messaggio. E se abbiamo quella proprietà insieme a una proprietà molto più semplice che i messaggi validi verificano, allora abbiamo uno schema di firma digitale che è adatto.
01.03.07
Okay, now, there’s a bunch of practical things that we need to do to turn that algorithmic idea into a more practically implementable signature mechanism. For example, the algorithms that we talked about are randomized, at least some of them will be. And so we need a good source of randomness, and the importance of this really can’t be underestimated. Band randomness will sink you, your algorithm will be insecure. And I’ll just point out here that attacks on the source of randomness are a favorite trick of intelligence agencies. And those are the people who know what kinds of attacks are likely to be successful.

In practice, there’s a limit on the message size that you’re able to sign because real schemes are going to operate on bit strings of limited length. And the fix to that is simply to use the hash of the message rather than the message itself. That way 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 rather than the message. And by the way a fun trick which we’ll see used later is that you can 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 everything it points to and everything it points to. For example, if you were to sign the hash pointer that was at the end of a block chain, the result is that you would effectively be digitally signing the entire contents of that block chain. That’s a useful trick that we’ll see used later.
Ok, ora ci sono un sacco di cose pratiche che dobbiamo fare per trasformare quell’idea algoritmica in un meccanismo di firma più praticamente attuabile. Ad esempio, gli algoritmi di cui abbiamo parlato sono randomizzati, almeno alcuni di essi lo saranno. E quindi abbiamo bisogno di una buona fonte di casualità, e l’importanza di questa realtà non può essere sottovalutata. La casualità delle bande ti affonderà, il tuo algoritmo sarà insicuro. E qui farò notare che gli attacchi alla fonte della casualità sono un trucco preferito delle agenzie di intelligence. E quelle sono le persone che sanno quali tipi di attacchi possono avere successo.

In pratica, c’è un limite alle dimensioni del messaggio che puoi firmare perché gli schemi reali funzioneranno su stringhe di bit di lunghezza limitata. E la soluzione è semplicemente usare l’hash del messaggio piuttosto che il messaggio stesso. In questo modo il messaggio può essere veramente grande, ma l’hash sarà di soli 256 bit.

E poiché le funzioni di hash sono prive di collisioni, è sicuro utilizzare l’hash del messaggio come input per lo schema di firma digitale piuttosto che per il messaggio. E tra l’altro un trucco divertente che vedremo usato in seguito è che puoi firmare un puntatore hash. E se si firma un puntatore hash, la firma copre o protegge l’intera struttura, non solo il puntatore hash stesso, ma tutto ciò a cui punta e tutto ciò a cui punta. Ad esempio, se si dovesse firmare il puntatore hash che si trovava alla fine di una catena di blocchi, il risultato è che si firmerebbe digitalmente l’intero contenuto di tale catena di blocchi. Questo è un trucco utile che vedremo usato in seguito.
01.03.08
Okay, now let’s get into the nuts and bolts. Bitcoin uses a particular digital signature scheme that’s called ECDSA. That’s the Elliptic Curve Digital Signature Algorithm. And it’s a US government standard. And we won’t go into all the details of how ECDSA works. It relies on some extremely hairy math. And trust me, you don’t want to see all the details of how that works, you can look it up if you’re interested. So we’ll skip that. One thing I’ll note though, with ECDSA good randomness, I said this before but I’ll say it again because it’s really essential. Good randomness is especially essential with ECDSA. If you use bad randomness in generating keys or even in signing, you probably leaked your private key. It stands to reason that if you use bad randomness in generating a key that the key you generate is maybe not secure. But it’s a quirk of ECDSA that even if you use bad randomness just in making a signature using your perfectly good key, that also will leak your private key and then it’s game over. So we need to be especially careful about this in practice. This is a common mistake. So that completes the discussion of digital signatures as a cryptographic primitive. And in the next segment, we’ll move on and talk about some applications of digital signatures that will turn out to be useful in building crypto-currencies. Ok, ora entriamo nei dadi e bulloni. Bitcoin utilizza un particolare schema di firma digitale chiamato ECDSA. Questo è l’Algoritmo di firma digitale a curva ellittica. Ed è uno standard del governo statunitense. E non approfondiremo tutti i dettagli su come funziona ECDSA. Si basa su una matematica estremamente pelosa. E credimi, non vuoi vedere tutti i dettagli di come funziona, puoi cercarlo se sei interessato. Quindi lo salteremo. Una cosa che noterò comunque, con ECDSA buona casualità, l’ho detto prima, ma lo ripeto perché è davvero essenziale. Una buona casualità è particolarmente essenziale con ECDSA. Se utilizzi una cattiva casualità nella generazione di chiavi o persino nella firma, probabilmente hai perso la tua chiave privata. È ovvio che se si utilizza la casualità errata nel generare una chiave, la chiave che si genera potrebbe non essere sicura. Ma è una stranezza di ECDSA che anche se usi una casualità cattiva solo facendo una firma usando la tua chiave perfettamente buona, questo perderà anche la tua chiave privata e poi il gioco finirà. Quindi dobbiamo essere particolarmente attenti a questo nella pratica. Questo è un errore comune. Così questo completa la discussione sulle firme digitali come una primitiva crittografica. E nel prossimo segmento andremo avanti e parleremo di alcune applicazioni delle firme digitali che si riveleranno utili nella costruzione di cripto-valute.

[top]
© Edward W. Felten – Professor of Computer Science and Public affairs – Princeton University

W01.02
Puntatori Hash e Strutture di Dati
W01.04
Chiavi pubbliche come identità