Information theoretic security and the one time pad (19 min)

"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