1
99:59:59,999 --> 99:59:59,999
"efficiente" significa che può essere eseguito in un dato tempo. Così per esempio,

2
99:59:59,999 --> 99:59:59,999
1101110 che è il testo cifrato. E ora, come faccio a decifrarlo?

3
99:59:59,999 --> 99:59:59,999
Abbiamo appena visto alcuni esempi storici di cifrari, tutti facilmente

4
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

5
99:59:59,999 --> 99:59:59,999
L'algoritmo di decifratura riceve in input chiavi e testi cifrati e restituisce messaggi.

6
99:59:59,999 --> 99:59:59,999
L'unico requisito è che questi due algoritmi siano consistenti, che soddisfino cioè

7
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)

8
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

9
99:59:59,999 --> 99:59:59,999
Si tratta spesso di un algoritmo di tipo random il che significa che quando dobbiamo cifrare

10
99:59:59,999 --> 99:59:59,999
Sostanzialmente faccio la stessa cosa, cioè decifro un testo cifrato usando

11
99:59:59,999 --> 99:59:59,999
Spero che tutti voi abbiate capito che infatti dato un messaggio e il

12
99:59:59,999 --> 99:59:59,999
Vi ricordo che l'XOR, questo + con un cerchio significa addizione

13
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,

14
99:59:59,999 --> 99:59:59,999
XX secolo. Prima di spiegarvi effettivamente in che cosa consiste,

15
99:59:59,999 --> 99:59:59,999
a farvi riferimento mettendo le virgolette e, come ho già detto, chi è più incline alla teoria

16
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

17
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

18
99:59:59,999 --> 99:59:59,999
altrimenti non è possibile decifrare. Una cosa che voglio sottolineare è

19
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

20
99:59:59,999 --> 99:59:59,999
che chiamerò K, e qualche volta lo chiamerò anche spazio delle chiavi

21
99:59:59,999 --> 99:59:59,999
che dobbiamo fare è verificare che siano soddisfatti i requisiti di consistenza. Ora

22
99:59:59,999 --> 99:59:59,999
che sono sostanzialmente lunghe quanto il messaggio. Così se Alice e Bob vogliono comunicare

23
99:59:59,999 --> 99:59:59,999
che è il risultato della cifratura del messaggio con una data chiave, è semplicemente

24
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

25
99:59:59,999 --> 99:59:59,999
che è stato cifrato usando una chiave particolare ottengo

26
99:59:59,999 --> 99:59:59,999
come un limite di tempo effettivo. Un altro commento che voglio fare è relativo all'algoritmo E.

27
99:59:59,999 --> 99:59:59,999
coppia di "efficienti" algoritmi E e D. E è l'algoritmo di cifratura; D è

28
99:59:59,999 --> 99:59:59,999
dalla randomizzazione usata dall'algoritmo. OK, ora che sappiamo

29
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

30
99:59:59,999 --> 99:59:59,999
dati. Comunque, la parola "efficiente" può essere interpretata in entrambi i modi e ciascuno può

31
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

32
99:59:59,999 --> 99:59:59,999
di sicurezza del cifrario fra un attimo. Prima, consentitemi di porvi rapidamente

33
99:59:59,999 --> 99:59:59,999
difficile da usare in pratica. Il motivo è che è difficile usare chiavi

34
99:59:59,999 --> 99:59:59,999
due algoritmi. Abbiamo un algoritmo per cifrare e un algoritmo per decifrare. Ma

35
99:59:59,999 --> 99:59:59,999
e per ogni chiave dell'insieme delle chiavi. Il che vale a dire che se criptiamo

36
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

37
99:59:59,999 --> 99:59:59,999
equazione di consistenza e ogni cifrario, può essere considerato tale, solo se la soddisfa

38
99:59:59,999 --> 99:59:59,999
esattamente l'insieme di tutte le stringhe binarie di n bit cioé tutte le sequenze di

39
99:59:59,999 --> 99:59:59,999
ha significati diversi per persone diverse. Per coloro più inclini alla

40
99:59:59,999 --> 99:59:59,999
i messaggi, l'algoritmo E genera un insieme di bit bit casuali che poi

41
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 è

42
99:59:59,999 --> 99:59:59,999
il cifrario funziona il che in realtà è molto semplice. Quindi, essenzialmente il testo cifrato

43
99:59:59,999 --> 99:59:59,999
il corrispondente testo cifrato è molto facile risalire alla chiave. In particolare la chiave è

44
99:59:59,999 --> 99:59:59,999
il messaggio M. Cosa succede nel nostro caso? Vediamolo.

45
99:59:59,999 --> 99:59:59,999
il messaggio originale da cui eravamo partiti. Questa uguaglianza è ciò che chiamiamo

46
99:59:59,999 --> 99:59:59,999
il messaggio stesso. Per cui il fatto che la chiave sia lunga quanto il messaggio è davvero

47
99:59:59,999 --> 99:59:59,999
il motivo per cui ho virgolettato la parola "efficiente". La ragione è che la parola "efficiente"

48
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

49
99:59:59,999 --> 99:59:59,999
in maniera sicura, voi sapete che Alice vuole inviare un messaggio a Bob, prima di cominciare

50
99:59:59,999 --> 99:59:59,999
interpretarla nel modo che gli è più congeniale. In ogni caso io continuerò

51
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

52
99:59:59,999 --> 99:59:59,999
l'algoritmo di decifratura. Naturalmente, E riceve in input chiavi e messaggi e restituisce testi cifrati.

53
99:59:59,999 --> 99:59:59,999
l'algoritmo di decifrazione è sempre deterministico. In altre parole, data

54
99:59:59,999 --> 99:59:59,999
l'ambiente su cui il cifrario viene definito. E allora il cifrario stesso è una

55
99:59:59,999 --> 99:59:59,999
l'insieme di tutti i possibili messaggi cifrati. OK, così questa terna definisce in qualche modo

56
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

57
99:59:59,999 --> 99:59:59,999
la interpreterà come tempo polinomiale, gli altri invece la interpreteranno

58
99:59:59,999 --> 99:59:59,999
la stessa lunghezza del messaggio da cifrare. OK, ora che abbiamo

59
99:59:59,999 --> 99:59:59,999
lo farò lentamente una volta e d'ora in avanti assumerò che questo sia semplice

60
99:59:59,999 --> 99:59:59,999
lunga quanto il messaggio, allora potrebbe usare lo stesso metodo per trasmettere anche

61
99:59:59,999 --> 99:59:59,999
ma non ci dice nulla sulla sicurezza del cifrario. E noi parleremo

62
99:59:59,999 --> 99:59:59,999
meglio cosa si intende per cifrario, voglio mostrarvi il primo esempio di cifrario sicuro.

63
99:59:59,999 --> 99:59:59,999
modulo 2. Quindi se io ho un dato messaggio, diciamo 0110111 e prendiamo

64
99:59:59,999 --> 99:59:59,999
ne vedremo la ragione un po' più avanti nella lezione. Bene.

65
99:59:59,999 --> 99:59:59,999
per cifrario. Quindi, innanzi tutto, ricordiamo che un cifrario è composto da

66
99:59:59,999 --> 99:59:59,999
per generare c partendo da m?

67
99:59:59,999 --> 99:59:59,999
per voi. Quindi facciamolo, dobbiamo essere certi che se decifro un testo

68
99:59:59,999 --> 99:59:59,999
precisato su che cosa il cifrario è definito, possiamo passare specificare come

69
99:59:59,999 --> 99:59:59,999
problematico e rende one-time pad un metodo difficile da usare in pratica.

70
99:59:59,999 --> 99:59:59,999
progettati. Ma prima di fare ciò, voglio definire, prima di tutto, più precisamente cosa si intende

71
99:59:59,999 --> 99:59:59,999
quella che viene detta proprietà di correttezza. E questo per ogni messaggio dell'insieme dei messaggi

72
99:59:59,999 --> 99:59:59,999
semplicemente m XOR c. Allora vedremo che se non è immediatamente ovvio

73
99:59:59,999 --> 99:59:59,999
sia cifrando che decifrando messaggi molto lunghi. Sfortunatamente è molto

74
99:59:59,999 --> 99:59:59,999
stringhe. In altre parole, eseguiamo l'addizione modulo 2 bit per bit. Quindi otteniamo

75
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

76
99:59:59,999 --> 99:59:59,999
tutto ciò che avete è il messaggio m e il testo cifrato c. La mia domanda è:

77
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

78
99:59:59,999 --> 99:59:59,999
un messaggio m e la cifratura del messaggio stesso ottenuta usando one-time pad. Così

79
99:59:59,999 --> 99:59:59,999
un tempo polinomiale qualunque sia l'input che ricevono. Per le persone più inclini alla pratica

80
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)

81
99:59:59,999 --> 99:59:59,999
una chiave particolare, diciamo 1011001, per eseguire la cifratura del messaggio

82
99:59:59,999 --> 99:59:59,999
una domanda, per essere certi che siamo sincronizzati. Supponete di avere

83
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ò

84
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 è

85
99:59:59,999 --> 99:59:59,999
usando questa chiave, basta calcolare l'XOR di queste due

86
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

87
99:59:59,999 --> 99:59:59,999
violati, passiamo ora a parlare di cifrari meglio

88
99:59:59,999 --> 99:59:59,999
voglio riferirlo alla terminologia che abbiamo appena visto. Quindi, lo spazio dei messaggi per

89
99:59:59,999 --> 99:59:59,999
è eseguire l'XOR fra la chiave e il messaggio quindi è un cifrario super super veloce

90
99:59:59,999 --> 99:59:59,999
è semplicemente m. OK, questo effettivamente dimostra che one-time pad è davvero un cifrario,

91
99:59:59,999 --> 99:59:59,999
è semplicemente un lunga stringa di tipo random, cioè una sequenza casuale di bit che ha