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