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