WEBVTT 99:59:59.999 --> 99:59:59.999 "efficiente" significa che può essere eseguito in un dato tempo. Così per esempio, 99:59:59.999 --> 99:59:59.999 1101110 che è il testo cifrato. E ora, come faccio a decifrarlo? 99:59:59.999 --> 99:59:59.999 Abbiamo appena visto alcuni esempi storici di cifrari, tutti facilmente 99:59:59.999 --> 99:59:59.999 Dunque one time pad è davvero interessante dal punto di vista delle prestazioni: tutto quello che bisogna fare 99:59:59.999 --> 99:59:59.999 L'algoritmo di decifratura riceve in input chiavi e testi cifrati e restituisce messaggi. 99:59:59.999 --> 99:59:59.999 L'unico requisito è che questi due algoritmi siano consistenti, che soddisfino cioè 99:59:59.999 --> 99:59:59.999 La cifratura di m usando k, non è altro che l'XOR fra m e k per definizione. In che consiste la decifratura di (k xor m) 99:59:59.999 --> 99:59:59.999 Si chiama "one time pad" OTP (chiave usata una sola volta) e fu inventato da Vernam all'inizio del 99:59:59.999 --> 99:59:59.999 Si tratta spesso di un algoritmo di tipo random il che significa che quando dobbiamo cifrare 99:59:59.999 --> 99:59:59.999 Sostanzialmente faccio la stessa cosa, cioè decifro un testo cifrato usando 99:59:59.999 --> 99:59:59.999 Spero che tutti voi abbiate capito che infatti dato un messaggio e il 99:59:59.999 --> 99:59:59.999 Vi ricordo che l'XOR, questo + con un cerchio significa addizione 99:59:59.999 --> 99:59:59.999 XOR m, il che , visto che come sapete k XOR k vale 0 e 0 XOR m vale m qualunque sia m, 99:59:59.999 --> 99:59:59.999 XX secolo. Prima di spiegarvi effettivamente in che cosa consiste, 99:59:59.999 --> 99:59:59.999 a farvi riferimento mettendo le virgolette e, come ho già detto, chi è più incline alla teoria 99:59:59.999 --> 99:59:59.999 ad inviare anche soltanto ad inviare il primo bit del messaggio, deve trasmettere a Bo una chiave che 99:59:59.999 --> 99:59:59.999 all'algoritmo E si può richiedere di impiegare un tempo inferiore al minuto per cifrare un gigabyte di 99:59:59.999 --> 99:59:59.999 altrimenti non è possibile decifrare. Una cosa che voglio sottolineare è 99:59:59.999 --> 99:59:59.999 bit, cioè di caratteri 0 e 1. Anche lo spazio delle chiavi è sostanzialmente lo stesso dei messaggi 99:59:59.999 --> 99:59:59.999 che chiamerò K, e qualche volta lo chiamerò anche spazio delle chiavi 99:59:59.999 --> 99:59:59.999 che dobbiamo fare è verificare che siano soddisfatti i requisiti di consistenza. Ora 99:59:59.999 --> 99:59:59.999 che sono sostanzialmente lunghe quanto il messaggio. Così se Alice e Bob vogliono comunicare 99:59:59.999 --> 99:59:59.999 che è il risultato della cifratura del messaggio con una data chiave, è semplicemente 99:59:59.999 --> 99:59:59.999 che è l'insieme di tutte le chiavi possibili. C'è poi l'insieme di tutti i possibili messaggi e anche 99:59:59.999 --> 99:59:59.999 che è stato cifrato usando una chiave particolare ottengo 99:59:59.999 --> 99:59:59.999 come un limite di tempo effettivo. Un altro commento che voglio fare è relativo all'algoritmo E. 99:59:59.999 --> 99:59:59.999 coppia di "efficienti" algoritmi E e D. E è l'algoritmo di cifratura; D è 99:59:59.999 --> 99:59:59.999 dalla randomizzazione usata dall'algoritmo. OK, ora che sappiamo 99:59:59.999 --> 99:59:59.999 data la coppia m e c, potete pensare di ricavare la chiave one time pad che è stata usata 99:59:59.999 --> 99:59:59.999 dati. Comunque, la parola "efficiente" può essere interpretata in entrambi i modi e ciascuno può 99:59:59.999 --> 99:59:59.999 deve essere lunga quanto il messaggio. Bene, se lei avesse un modo per inviare a Bob in modo sicuro una chiave 99:59:59.999 --> 99:59:59.999 di sicurezza del cifrario fra un attimo. Prima, consentitemi di porvi rapidamente 99:59:59.999 --> 99:59:59.999 difficile da usare in pratica. Il motivo è che è difficile usare chiavi 99:59:59.999 --> 99:59:59.999 due algoritmi. Abbiamo un algoritmo per cifrare e un algoritmo per decifrare. Ma 99:59:59.999 --> 99:59:59.999 e per ogni chiave dell'insieme delle chiavi. Il che vale a dire che se criptiamo 99:59:59.999 --> 99:59:59.999 ed è anch'esso l'insieme di tutte le stringhe binarie di lunghezza n. Quindi una chiave nel sistema OTP 99:59:59.999 --> 99:59:59.999 equazione di consistenza e ogni cifrario, può essere considerato tale, solo se la soddisfa 99:59:59.999 --> 99:59:59.999 esattamente l'insieme di tutte le stringhe binarie di n bit cioé tutte le sequenze di 99:59:59.999 --> 99:59:59.999 ha significati diversi per persone diverse. Per coloro più inclini alla 99:59:59.999 --> 99:59:59.999 i messaggi, l'algoritmo E genera un insieme di bit bit casuali che poi 99:59:59.999 --> 99:59:59.999 il cifrario di Vernam (per il one-time-pad) coincide con lo spazio dei messaggi cifrati che è 99:59:59.999 --> 99:59:59.999 il cifrario funziona il che in realtà è molto semplice. Quindi, essenzialmente il testo cifrato 99:59:59.999 --> 99:59:59.999 il corrispondente testo cifrato è molto facile risalire alla chiave. In particolare la chiave è 99:59:59.999 --> 99:59:59.999 il messaggio M. Cosa succede nel nostro caso? Vediamolo. 99:59:59.999 --> 99:59:59.999 il messaggio originale da cui eravamo partiti. Questa uguaglianza è ciò che chiamiamo 99:59:59.999 --> 99:59:59.999 il messaggio stesso. Per cui il fatto che la chiave sia lunga quanto il messaggio è davvero 99:59:59.999 --> 99:59:59.999 il motivo per cui ho virgolettato la parola "efficiente". La ragione è che la parola "efficiente" 99:59:59.999 --> 99:59:59.999 in effetti, una cifrario viene definito su una terna. Così: l'insieme di tutte le possibili chiavi 99:59:59.999 --> 99:59:59.999 in maniera sicura, voi sapete che Alice vuole inviare un messaggio a Bob, prima di cominciare 99:59:59.999 --> 99:59:59.999 interpretarla nel modo che gli è più congeniale. In ogni caso io continuerò 99:59:59.999 --> 99:59:59.999 l'XOR delle due parti. Basta semplicemente eseguire l'XOR fra K ed M, vediamone un veloce esempio 99:59:59.999 --> 99:59:59.999 l'algoritmo di decifratura. Naturalmente, E riceve in input chiavi e messaggi e restituisce testi cifrati. 99:59:59.999 --> 99:59:59.999 l'algoritmo di decifrazione è sempre deterministico. In altre parole, data 99:59:59.999 --> 99:59:59.999 l'ambiente su cui il cifrario viene definito. E allora il cifrario stesso è una 99:59:59.999 --> 99:59:59.999 l'insieme di tutti i possibili messaggi cifrati. OK, così questa terna definisce in qualche modo 99:59:59.999 --> 99:59:59.999 la chiave e il testo cifrato l'output è sempre il medesimo, perché non dipende in alcun modo 99:59:59.999 --> 99:59:59.999 la interpreterà come tempo polinomiale, gli altri invece la interpreteranno 99:59:59.999 --> 99:59:59.999 la stessa lunghezza del messaggio da cifrare. OK, ora che abbiamo 99:59:59.999 --> 99:59:59.999 lo farò lentamente una volta e d'ora in avanti assumerò che questo sia semplice 99:59:59.999 --> 99:59:59.999 lunga quanto il messaggio, allora potrebbe usare lo stesso metodo per trasmettere anche 99:59:59.999 --> 99:59:59.999 ma non ci dice nulla sulla sicurezza del cifrario. E noi parleremo 99:59:59.999 --> 99:59:59.999 meglio cosa si intende per cifrario, voglio mostrarvi il primo esempio di cifrario sicuro. 99:59:59.999 --> 99:59:59.999 modulo 2. Quindi se io ho un dato messaggio, diciamo 0110111 e prendiamo 99:59:59.999 --> 99:59:59.999 ne vedremo la ragione un po' più avanti nella lezione. Bene. 99:59:59.999 --> 99:59:59.999 per cifrario. Quindi, innanzi tutto, ricordiamo che un cifrario è composto da 99:59:59.999 --> 99:59:59.999 per generare c partendo da m? 99:59:59.999 --> 99:59:59.999 per voi. Quindi facciamolo, dobbiamo essere certi che se decifro un testo 99:59:59.999 --> 99:59:59.999 precisato su che cosa il cifrario è definito, possiamo passare specificare come 99:59:59.999 --> 99:59:59.999 problematico e rende one-time pad un metodo difficile da usare in pratica. 99:59:59.999 --> 99:59:59.999 progettati. Ma prima di fare ciò, voglio definire, prima di tutto, più precisamente cosa si intende 99:59:59.999 --> 99:59:59.999 quella che viene detta proprietà di correttezza. E questo per ogni messaggio dell'insieme dei messaggi 99:59:59.999 --> 99:59:59.999 semplicemente m XOR c. Allora vedremo che se non è immediatamente ovvio 99:59:59.999 --> 99:59:59.999 sia cifrando che decifrando messaggi molto lunghi. Sfortunatamente è molto 99:59:59.999 --> 99:59:59.999 stringhe. In altre parole, eseguiamo l'addizione modulo 2 bit per bit. Quindi otteniamo 99:59:59.999 --> 99:59:59.999 teoria, "efficiente" significa che può essere eseguito in un tempo polinomiale. Pertanto gli algoritmi E e D devono essere eseguiti in 99:59:59.999 --> 99:59:59.999 tutto ciò che avete è il messaggio m e il testo cifrato c. La mia domanda è: 99:59:59.999 --> 99:59:59.999 un messaggio con una chiave K e poi lo decriptiamo usando la stessa chiave K dobbiamo ottenere 99:59:59.999 --> 99:59:59.999 un messaggio m e la cifratura del messaggio stesso ottenuta usando one-time pad. Così 99:59:59.999 --> 99:59:59.999 un tempo polinomiale qualunque sia l'input che ricevono. Per le persone più inclini alla pratica 99:59:59.999 --> 99:59:59.999 un'addizione modulo 2, l'addizione gode della proprietà associativa, quindi equivale a calcolare (k XOR k) 99:59:59.999 --> 99:59:59.999 una chiave particolare, diciamo 1011001, per eseguire la cifratura del messaggio 99:59:59.999 --> 99:59:59.999 una domanda, per essere certi che siamo sincronizzati. Supponete di avere 99:59:59.999 --> 99:59:59.999 una particolare chiave, quello che faccio è un XOR fra una chiave e il testo cifrato. Così tutto ciò 99:59:59.999 --> 99:59:59.999 usando k? Non è altro che l'XOR fra k e (k XOR m). Perciò visto che ho detto che XOR è 99:59:59.999 --> 99:59:59.999 usando questa chiave, basta calcolare l'XOR di queste due 99:59:59.999 --> 99:59:59.999 utilizza per effettuare al cifratura vera e propria del messaggio che gli è stato fornito in input. Invece 99:59:59.999 --> 99:59:59.999 violati, passiamo ora a parlare di cifrari meglio 99:59:59.999 --> 99:59:59.999 voglio riferirlo alla terminologia che abbiamo appena visto. Quindi, lo spazio dei messaggi per 99:59:59.999 --> 99:59:59.999 è eseguire l'XOR fra la chiave e il messaggio quindi è un cifrario super super veloce 99:59:59.999 --> 99:59:59.999 è semplicemente m. OK, questo effettivamente dimostra che one-time pad è davvero un cifrario, 99:59:59.999 --> 99:59:59.999 è semplicemente un lunga stringa di tipo random, cioè una sequenza casuale di bit che ha